Scientific journal
Modern problems of science and education
ISSN 2070-7428
"Перечень" ВАК
ИФ РИНЦ = 0,940

EXTRACTION OF INFORMATION FROM TEXT: PREDICTING THE RELATIONSHIP BETWEEN GIVEN ENTITIES

Manucharyan L.A. 1
1 Voronezh state academy of forestry and technologies, Voronezh, Russia
In this article the methods of predicting the relationship between a given entity pair are provided. Given a fixed set R of relationship types each having a pair of entity types, the final aim is to identify all occurrences of the relationships in R in an input natural language text in which all entities have been marked. The task of the prediction is easier than the task of the extraction of entities, because the latter case involves only scalar prediction instead of the vector one. Surface tokens are reviewed, the important role of part of speech tags is accentuated and a compare analysis between dependency graphs and parse trees is provided for various scenarios of extraction tasks. A short review of popular types of extraction is provided further and an extraction method of entities is suggested.
Entity pair relationship
information extraction
Введение

В основном при извлечении связей из текста на естественном языке подразумевается, что двe аргументные сущности находятся в непосредственной близости или же являются частью одного и того же предложения. Таким образом, базовая задача распознавания имеет следующий вид: если на входе имеется фрагмент текста х и две помеченные сущности Е1 и Е2 в х, нужно определить, существует ли связь Y междy E1 и E2. Множество Y указывает на все типы связей R, а также на специальный тип «другое» для случая, когда ни одна из связей не применима к паре сущностей. Данная задача распознавания более легкая по сравнению с задачей по извлечению сущностей, так как в данном случае необходимо сделать только скалярный прогноз вместо векторного. Однако извлечение связей считается более сложной проблемой, чем извлечение сущностей, так как нахождение связей между двумя словами в предложении требует применения искусной комбинации локальных и нелокальных подсказок с «шумом» из разнообразных синтаксических и семантических структур в предложении. Далее будет представлен анализ наиболее общих типов ресурсов, полезных для извлечения связей:

Анализ типов ресурсов для извлечения связей

Поверхностные репрезентации: репрезентации вокруг и между двумя сущностями часто включают в себя информацию, необходимую для извлечения связей. Например, связь «расположена» между сущностями «Компания» и «Расположение», четко обозначается присутствием репрезентаций N-граммы «расположена» и биграммы «расположена» между двумя сущностями, как в примере:

<Компания>Роснефть</ Компания > расположена по адресу

<Расположение>г. Москва, ул. Харькова</ Расположение >.

Аналогично, связь между «болезнью» и «расположением» четко выделяется присутствием слов вроде «эпидемия». Например - центр за контролем и предотвращением заболеваний выявил случаи эпидемии <Болезнь>чумы</Болезнь> в нескольких городах <Расположение>Египта</Расположение>.

Часто репрезентация обобщается или приводится к своему морфологическому корню. Напр., «расположен» приводится к слову «расположение».

Теги части речи. Теги части речи играют более существенную роль в извлечении связей, чем в извлечении сущностей. Глаголы в предложении являются ключевым фактором в определении связи между сущностями, которые в большинстве случаев представляют собой именные группы. Например в предложении - «В этом году < Расположение > Воронежскaя лесотехническся академия</ Расположение > выступит в роли принимающей стороны в проведении <Олимпиада>ПБГ </Олимпиада>» более достоверное извлечение связи «проведение» между «олимпиадой» и «расположением» было бы возможно, если бы фраза «принимающая сторона» была тегирована как глагол, вместо именной.

Структура дерева синтаксического разбора. Дерево синтаксического разбора группирует слова в предложении в выступающие типы грамматических оборотов, такиe как именные группы, предложные группы и глагольные группы и таким образом представляет намного большую ценность в определении связей между сущностями в предложении, нежели теги POS (POS - Part Of Speech, Часть речи).

Например, в предложении «В <Расположение>Воронеже</Расположение>, находящeмся в 500 километрах от <Расположение> Москвы </Расположение>, будет проводится олимпиада <Олимпиада>ПБГ</Олимпиада> в 2012 году» предпочтение, скореe всего, будет отдано «Москва, ПБГ», чем «Воронеж, ПБГ», как экземпляру связи «будет проводится», основанному на относительной близости к «ПБГ». Однако дерево грамматического разбора для выше иллюстрированного предложения приносит «ПБГ» ближе к слову «Воронеж», чем «Москва», так как «Воронеж» является главной именной в предложении «Воронеж, расположенный в 520 километрах от Москвы», который в свою очередь формирует подлежащее глагольной группы «будет проводится в 2010».

Граф зависимостей. Создание полноценного дерева разбора обходится дорого. Граф зависимостей, который связывает каждое слово со словами, находящимся в зависимости от него, зачастую может быть настолько полезным, насколько дерево разбора. Например, граф зависимостей для вышеописанного предложения показан на рис. 1. Из графа видно, что глагол «проводится» связан с обеими сущностями: «Воронеж» - сущность «Расположение» и «ПБГ» - сущность «Олимпиада». Это напрямую создает близкую связь между обеими сущностями.

Рис. 1. Разбор зависимостей предложения.

В отличие от этого путь между «ПБГ» и «Москва» идет через «Воронеж» и «расположенный». Далее будут рассмотрены методы, которые используют вышеописанную информацию в разных вариациях для классификации входного (x, E1, E2) в одного из Y классов. Предположим, имеется N обучительных примеров в виде (xi, E1i, E2i, ri): i=1....N, где ri∈Y обозначает связь, которая существует между сущностями E1i,, E2i, в предложении xi. Главной проблемой является обработка разнообразных структурных видов, которые включают в себя разные входные данные. Например, репрезентации и теги части речи образуют последовательность, выходная информация при грамматическом разборе является деревом, а структура зависимостей - графом. Далее могли бы присутствовать ошибки в любом из входных ключей, так как лингвистические библиотеки, используемые для задач извлечения, несовершенны. Несмотря на то что избыточность придает устойчивость ошибкам, переизбыток может привести к информационному шуму и увеличить длительность работы приложения. Методы, используемые в извлечении связей, могут быть распределены по следующим трем главным типам.

  • Методы, ориентированные на топологию: извлекается фиксированное множество дифференциальных признаков из входной информации с дальнейшим запуском готового классификатора (напр., дерево решений или SVM [4]).
  • Методы, базированные на ядре: создаются специальные ядра для перехвата сходств между структурами вроде дерева или графов. Ядро в большинстве представляет собой ключевое слово в предложении.
  • Методы, основанные на правилах: создаются пропозициональные правила и правила первого порядка для структур вокруг двух сущностей. Для примеров разных систем извлечения связей [1; 2].

Методика извлечения

Методы, ориентированные на топологию: большое разнообразие методов использовалось для конвертации ключей извлечения структур вида последовательностей, дерев или графов, в фиксированное множество признаков - для использования стандартными классификаторами. Авторы в [5] представляют систематический метод проектирования таких признаков, одновременно включая большинство ранее предложенных методов извлечения связей, основанных на признаках [6; 7].

Обозначим входное предложение X, где xi обозначает слово в позиции i, a E1, E2 обозначают сегменты в x, соответствующие двум сущностям, связь которых желаем прогнозировать. Для простоты предположим, что и E1 и E2 состоят из одного слова. Каждое слово xi связано со множеством свойств p1....pk, так же как признаки используются при извлечении сущностей X. Примеры таких свойств включают строчную форму xi, орфографический тип xi, класс xi в заданной онтологии, помеченная сущность xi, а также POS тег xi. Первое множество функциональных возможностей приобретается путем перехвата всех возможных союзов свойств двух репрезентации, представляющих собой две сущности E1 и E2. Примеры таких случаев следующие.

[[Помеченная сущность от E1 = Личность, Помеченная сущность от E1 = Расположение]].

[[Строка E1 = «Эйнштейн», Орфографический тип от E2 =4-цифры]].

Первая функция могла бы быть полезной для связи «проживает в», когда первая сущность в предложении - «Личность», а вторая помеченая сущность - «Расположение».

Второй признак мог бы быть полезным для связи «рожден», когда Е1 равняется «Энштейн» и Е2 состоит из 4-х цифр. Далее представим, как нужно извлекать дифференциальные признаки из структурных входных данных, что включает связи между словами в предложении. Имеется три типа входных данных: последовательности, дерево разбора и графы зависимостей. Для объединения шага генерации дифференциальных признаков от этих входных данных каждый будет рассматриваться как граф, вершины которого являются словами, а также нетерминалы (NNP, VP, и т.д.) в случае с деревом грамматического разбора. Каждое слово-вершина ассоциировано с K множеством p1.....pk. Вдобавок специальный признак добавляется к каждой вершине, который может принять четыре значения: 1 - если относится к Е1, 2 - если относится к Е2, «обе» - если относится к обеим, и «никакой», если ни к которой не относится. Дифференциальные признаки являются производными от свойств индивидуальных вершин, а также пар вершин, связанных краем, или троицами вершин, связанных по крайней мере двумя краями, и для каждой комбинации значений спецпризнака, связанного с краями. Пример вышеописанного может быть иллюстрирован при помощи предложения X с Е1= «Воронеж» и Е2= «ПБГ».

В <Расположение>Воронеже</Расположение>, расположенном в 520 километрах от <Расположение>Москвы</Расположение>, будет проведена олимпиада <Олимпиада>ПБГ</ Олимпиада>, которая состоится в 2012 году.

Признаки от последовательности слов: в первую очередь будут приведены примеры дифференциальных признаков для графа последовательности, прeобразованного словами между Е1 и Е2. В этом случае единственные края находятся между смежными словами. Каждая вершина включает К признаков и один из возможных специальных признаков - (1, 2, «никакой»).

Примеры дифференциальных признаков n-граммы следующие.

[[строка =«проводить», спецпризнак =« никакой»]]

[[Часть речи = Глагол, спецпризнак =« никакой»]].

 

Примеры дифференциальных признаков биграмм следующие.

[[строка = «(проводить, ПБГ)», спецпризнаки= «(никакой, 2)», тип =«последовательность»]]

[[Часть речи = (Глагол, существительное), спецпризнаки= «(никакой, 2)», тип =«последовательность»]]

 

Примеры дифференциальных признаков триграмм следующие.

 [[Строки = «(будет, проводить, «ПБГ»)», спецпризнаки= «(никакой, никакой, 2)», тип =«последовательность»]]

[[Часть речи = (модификатор, глагол, существительное), спецпризнаки= «(никакой, никакой, 2)», тип =«последовательность»]]

Используя этот шаблон, можно с легкостью рассчитать максимальное число дифференциальных признаков для каждого типа. Обозначим d(pi) число возмозных значений, которые может принимать признак i, а также обозначим  сумму величины всех признаков. Тогда число для N-грамм признаков будет 3d, биграмм - , и для триграмм - . На практике число признаков намного меньше, так как во время обучения учитывается только комбинация признаков, присутствующая хотя бы в одном экземпляре обучения.

Дифференциальные признаки от графа зависимостей. Рассмотрим граф зависимостей из рис. 1. Так как множество вершин то же, что и при последовательностях, больше не требуется генерировать n-грамм признаки. Края в графе создают множество биграмма и триграмма признаков. Вот несколько примеров.

 [[(пометка сущности = «Расположение», Часть речи = (Глагол), спецпризнаки= «(1, никакой)», тип =«зависимость»]].

Этот признак запускается на паре вершин «(Воронеж, проводится)», связанных в графе зависимостей как «проводится ← Воронеж». Одно из полезных триграммных свойств, полученных из графа зависимостей, следующее:

 [[(POS = (существительное, Глагол, существительное), спецпризнак = «(1, никакой, 2)», тип =«зависимость»]].

Это свойство запускается на вершинах «(Воронеж, проводится, «ПБГ»)», из-за шаблона края - «Воронеж → проводится ← ПБГ».

Дифференциальные признаки от дерева грамматического разбора. Множество вершин в дереве разбора состоит из вершин-слов в краях и внутренних вершин. Это открывает новые N-грамм свойства следующего вида:

[[вершина = «VP», спецпризнак = «2»]].

Также некоторые из внутрeнних вершин, которые относятся к сущностям вершин Е1 и Е2, теперь могут иметь спецпризнак «обе». Например, в рис. 1, вершина «S» относится к сущностям, а также ассоциирована со спецпризнаком «обе». Вдобавок, используя края от «родителя до детей» в дереве разбора, можно определить биграммные и триграммные признаки, как в случае с графами зависимостей. Авторы в [5] утверждают, что в восьми задачах по извлечению из АCE корпусов, достигнутая точность с этими простыми признаками, производными от N-грамм, Биграмм и триграмм от входных графов является конкурентоспособной с другими методами, которые интерпретируют структуру более глобально.

Заключение

В данной статье были рассмотрены методы прогнозирования связей между заданной парой сущностей при помощи анализа существующих методов и экспериментальным путем были выявлены наиболее эффективные варианты извлечения.

Рецензенты:

  • Сербулов Ю.С., д.т.н., профессор, проректор по научной работе Воронежского института высоких технологий, г. Воронеж.
  • Янсков А.И., к.т.н., начальник лаборатории ФГУП «Научно-исследовательский институт электронной техники».
  • Гаджиахмедов Н.Э., д.филос.н., профессор, зав. кафедрой теоретической и прикладной лингвистики Дагестанского государственного университета, г. Махачкала.

Работа получена 25.11.2011