УДК 519.767.6

Обобщение и специализация при построении правил извлечения информации*

Авторы: Д.А. Кормалев1

Источник: http://www.raai.org/resurs/papers/kii-2006/doklad/Kormalev.doc

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

Введение  

В области автоматической обработки текста наряду с другими методиками широко используется сопоставление образцу. Образец чаще всего задается при помощи правил, включающих в себя описание собственно образца и действий, которые должны быть выполнены при успешном сопоставлении. Яркими примерами задач, решаемых при помощи этого подхода, являются извлечение информации [Appelt et al., 1999] и распознавание именованных сущностей [Hirschman et al., 1997] (иногда эту задачу рассматривают как  разновидность извлечения информации).

Технология извлечения информации по глубине анализа текста и степени перехода от текста к модели предметной области занимает промежуточное место между информационным поиском и гипотетической технологией понимания текстов. Извлечение информации, в отличие от информационного поиска, подразумевает обязательное использование специфики предметной области и ориентацию на конкретную предметную область. С другой стороны, извлечение информации относится к так называемым поверхностным технологиям обработки текста — вполне возможно создание системы извлечения информации, в которой не используются средства семантического анализа общего назначения.

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

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

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

3. Достаточность средств разметки и предобработки: подавляющее большинство систем извлечения информации опирается на контекстные правила, которые позволяют выделить описания целевых объектов в тексте. Если, например, оказывается, что для точного описания контекста требуется учет синтаксических связей, а лингвистический процессор системы не предоставляет таких возможностей, то система извлечения информации не сможет достичь приемлемого качества работы (или придется описывать синтаксис при помощи правил извлечения информации, что не всегда удобно).

Трудоемкость построения правил вручную высока, поэтому для облегчения разработки и настройки приложений желательно использовать средства автоматизированного создания правил. Методы символьного машинного обучения, хорошо подходящие для решения задачи построения правил, опираются на два основных механизма: обобщение и специализация. Рассмотрим особенности этих механизмов при построении правил.

1. Основные определения

На некоторых этапах обработки текста (например, для выделения объектов в тексте) используются правила, записанные средствами некоторого формального языка. Эти правила позволяют описать образец для сопоставления и действия, которые должны быть произведены после успешного сопоставления. Ряд современных систем извлечения информации использует различные диалекты языка CPSL [Appelt, 1996].

Использование этого языка подразумевает также использование архитектуры, сходной по свойствам с эталонной архитектурой TIPSTER [Grishman, 1998]. Лингвистические и экстралингвистические сущности текста описываются при помощи так называемых аннотаций (аннотирующих отношений, описаний). Аннотация — объект, который приписывается фрагменту текста (слово, словосочетание, предложение, сущность предметной области) и описывает свойства этого фрагмента. Аннотации разбиты на классы. Каждый класс аннотаций описывает текст с определенной точки зрения. Информация о фрагменте заключена в атрибутах аннотации в виде «имя атрибута = значение атрибута».

На основе множества аннотаций можно построить граф аннотаций. Возможны различные представления графа в зависимости от задачи анализа. Для применения правил удобно представлять аннотации вершинами, а отношения между ними — дугами. В классическом случае отношения сводятся к отношению непосредственного следования (без транзитивно замыкающих дуг) на множестве интервалов. Оказывается полезно рассматривать дополнительные виды дуг в графе аннотаций, например, дуги, выражающие отношения взаимного расположения аннотаций или структурные отношения [Кормалев, 2005].

Интерпретация правил (сопоставление образцу) осуществляется в довольно узком контексте (чаще всего такой контекст — предложение). Для интерпретации правила транслируются в конечные преобразователи особого вида: , где  – множество состояний;  – начальное состояние;  – множество конечных состояний;  – множество тестов (высказываний о классах аннотаций и значениях их атрибутов);  – выходной алфавит (границы, классы и значения атрибутов вновь создаваемых аннотаций);  – функция переходов; – функция выходов.

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

Элементарный тест (элемент множества T) представляет собой конъюнкцию высказываний о значениях атрибутов аннотаций разных классов. Элементарный тест считается выполненным успешно, если в множестве кандидатов найдено подмножество аннотаций, для которых высказывания истинны. Для каждого класса аннотаций, на который есть ссылка в тесте, в подмножество попадает только один экземпляр этого класса. Роль элементарных тестов в правилах аналогична роли символов (не метасимволов) в регулярных выражениях; из элементарных тестов могут образовываться сложные конструкции с использованием конкатенации, альтернативы и квантификаторов.

2. Задача построения правил

Сформулируем задачу построения правил извлечения информации и обозначим некоторые общие подходы к ее решению. Требуется для заданного множества  обучающих примеров построить набор правил, осуществляющих дополнительную разметку текста. В примерах каждая аннотация помечена либо как «исходная», либо как «целевая». Без потери общности можно считать, что целевые аннотации относятся к особому классу (классам), который не встречается среди исходных аннотаций. Построенные правила должны, получая на вход исходные аннотации, создавать целевые аннотации в подобных контекстах.

Заметим, что в такой постановке задачи не накладывается ограничений на количество правил или на количество фаз, в которые группируются правила — некоторые из правил могут использовать результаты, полученные другими правилами.

Желательно, чтобы результат — построенные правила — был выражен в текстовом виде, это позволит вручную анализировать и при необходимости модифицировать построенные правила. Ясно, что строить правила сразу в текстовом виде неудобно. Однако, если нам удастся получить в том или ином виде конечный преобразователь, соответствующий правилу, переход собственно к правилу не вызовет больших трудностей.

3. Обобщение и специализация при построении правил

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

3.1. Обобщение на уровне правил

Рассмотрим графы аннотаций примеров из обучающего множества. Если бы каждый из них представлял собой цепь, то можно было бы сразу на основании графа построить конечный преобразователь — пусть и очень примитивный — и правило. Предположим, что язык описания правил достаточно богат, чтобы описать не только путь в графе аннотаций, но и произвольный подграф (частично эту проблему могут решить предложенные нами расширения языка правил [Александровский и др., 2006]). Предположим также, что существует функция R(g), позволяющая по графу аннотаций построить его описание в виде правила.

Заметим, что если при помощи функции R построить правила, соответствующие каждому примеру обучающего множества, то задача будет решена (за исключением замечания о количестве правил). Чтобы избежать такой перетренированности, естественное решение — воспользоваться операцией обобщения, которая позволит перейти от конкретных описаний к правилам. Будем обозначать эту операцию . Здесь G — множество обобщенных графов аннотаций — надмножество множества графов аннотаций, соответствующих конкретным фрагментам текста. Обобщенный граф аннотаций (обобщенный граф) отличается тем, что, во-первых, в нем используются не конкретные значения атрибутов аннотаций, а некоторый аналог элементарных тестов из определенного выше конечного преобразователя; во-вторых, в нем не запрещаются обратные дуги. Граф аннотаций может сопоставляться обобщенному графу аннотаций так же, как и правилу. С помощью обобщенного графа можно выразить не меньший класс контекстов, чем с помощью конечного преобразователя.

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

Один из очевидных вариантов определения операции — поиск общего подграфа наибольшего веса [Кормалев, 2005]. У такого подхода, впрочем, есть ряд недостатков, не считая вычислительной неэффективности для графов общего вида. Во-первых, в результате обобщения может получиться несвязный обобщенный граф, что требует при построении правил использования заполнителей, связанных квантификатором, а это отрицательно сказывается на точности получающейся системы правил. Во-вторых, вместо «пропусков», которыми обусловлена несвязность получающегося графа, в нем могут возникать вершины с минимальными ограничениями (например, ограничения только на класс аннотаций), а это уже понижает полноту правил. В-третьих, получающиеся графы (и правила) могут содержать излишние элементы, которые присутствуют и в положительных, и в отрицательных примерах (например, требование наличия точки в конце предложения, без которого можно было бы и обойтись).

По результатам предварительных экспериментов представляется полезным двухфазный сценарий работы: построение описания целевого объекта с помощью обобщения и последующая специализация для описания контекста, в котором встречаются целевые объекты (это позволяет повысить точность извлечения информации). Отличие состоит в том, что обобщение идет не на уровне всего графа, а на уровне его подграфов, соответствующих описаниям целевых объектов. Надо отметить, что такой сценарий схож с действиями эксперта при разработке правил: сначала формируются предварительные, неточные описания объектов, а окончательное решение о том, что обнаружен интересующий объект, принимается после анализа контекста, в котором встретилось предварительное описание. Качество обобщения проверяется сразу же после построения обобщенного графа — для этого можно использовать любые разработанные методы, например, кросс-валидацию.

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

Еще одна параллель с кластеризацией обнаруживается, если вернуться к постановке задачи. Нужно построить множество правил, которые успешно срабатывают на всем множестве обучающих примеров. Может быть построено небольшое количество очень сложных правил, а может — большое относительно простых. Не существует быть «единственно правильного» решения — как и в случае с кластеризацией.

3.2. Обобщение на уровне аннотаций

Чтобы проводить обобщение на уровне графов (или подграфов), необходимо определить, что представляет собой операция обобщения на уровне аннотаций (или элементарных тестов). Обозначим эту операцию . Как и в случае с операцией обобщения графов, конкретные реализации могут различаться. Можно предложить следующий вариант. Сначала строится двудольный граф с взвешенными ребрами. В этом графе вершины соответствуют отдельным высказываниям, составляющим элементарный тест.  На каждом ребре проставляется вес — количественная мера сходства высказываний, которые соответствуют вершинам, инцидентным этому ребру. Исходя из способа представления информации о тексте, естественно определить меру сходства так, чтобы для разных атрибутов (и тем более, классов) аннотаций получалось нулевое значение. Потом в графе выполняется поиск паросочетания максимального веса — тем самым в элементарных тестах обнаруживаются наиболее схожие части.

После обнаружения схожих частей необходимо выполнить обобщение. Во-первых, отбрасываются все вершины (высказывания), не вошедшие в паросочетание. Во-вторых, можно на основании эвристик дополнительно отбросить некоторые пары высказываний, сходство которых невелико. После этого нужно перейти от двух высказываний к одному — как и в случае с обобщением графов, необходимо выделить общую часть. Для выделения общей части могут использоваться три операции: собственно обобщение, дизъюнкция ограничений, снятие ограничения. Собственно обобщение требует наличия знаний о предметной области. Например, если известно, что значения атрибутов присутствуют в онтологии предметной области, естественным шагом обобщения будет выбор общего класса, к которому относятся оба значения. Решение о дизъюнкции или снятии ограничения принимается на основании тестирования каждого построенного варианта. Нужно отметить, что может быть полезным сохранять дизъюнкцию (в неактивном состоянии) даже если тестирование показало, что снятие ограничения не ухудшает результатов — это позволит при необходимости в дальнейшем вернуться к дизъюнкции, если  создается пошаговая версия алгоритма обучения. Дополнительно могут использоваться знания о замкнутых и незамкнутых множествах значений конкретного атрибута. Например, морфологический атрибут «Падеж» может принимать (для русского языка) лишь шесть значений, поэтому при сохранении дизъюнкции опасность недостаточного обобщения мала, а множество возможных значений атрибута «Каноническая форма» практически не ограничено — здесь снятие ограничения может быть полезным. Вопрос о конкретном способе обобщения может также решаться интерактивно.

3.3. Специализация при построении правил

При использовании двухфазного сценария построения правил вторая фаза нацелена на повышение точности. Предполагается, что на первом фазе были построены правила, описывающие целевые фрагменты с приемлемой полнотой (без контекста). Специализация может осуществляться непосредственно для правил, полученных на первой фазе, или может проводиться обучение для построения правил, опирающихся на разметку, которую осуществляют правила первого этапа. В последнем случае сокращается общий объем набора правил. Будем рассматривать этот вариант.

Специализация заключается в постепенном расширении контекста. Изначально каждое правило второй фазы состоит из простейшего ограничения на класс аннотации, строящейся правилом первой фазы. Шаг специализации состоит в том, что рассматриваются все возможные переходы слева и справа от этой аннотации и осуществляется поиск наиболее похожих переходов (так же, как при обобщении графов на первой фазе). Критерий остановки специализации: достижение компромисса между точностью полученной результирующей  системы правил и количеством порожденных правил. Критерий задается параметрами алгоритма и нацелен на то, чтобы избежать перетренированности системы правил, но достичь достаточной точности.

Заключение

Мы надеемся, что рассмотренные особенности обобщения и специализации при построении правил позволят вплотную подойти к решению задачи автоматического (или автоматизированного) построения правил и улучшить качество работы систем построения правил. Для окончательного решения обозначенных в работе проблем и выбора конкретных алгоритмов требуются дополнительные теоретические и экспериментальные исследования.

Список литературы

[Александровский и др., 2006] Александровский Д.А., Кормалев Д.А., Кормалева М.С., Куршев Е.П., Сулейманова Е.А., Трофимов И.В. ИСИДА-Т: новый инструмент для создания систем извлечения информации из текстов // Наст. сборник.

[Кормалев, 2005] Кормалев Д.А. Автоматическое построение правил извлечения информации из текста // Тр. Первой междунар. конф. «Системный анализ и информационные технологии» САИТ-2005, Переславль-Залесский, сентябрь 2005 г.: В 2 т. — М.: КомКнига, 2005. — Т. 2. — С. 205-209.

[Appelt, 1996] Appelt D.E. The Common Pattern Specification Language: Technical report / SRI International, Artificial Intelligence Center. — 1996.

[Appelt et al., 1999] Appelt D.E., Israel D.J. Introduction to Information Extraction Technology // Proc. of IJCAI-99. Stockholm, Sweden, 1999.

[Grishman, 1998] Grishman R. TIPSTER Text Architecture Design. Version 3.1. — New York: NYU, 1998.

[Hirschman et al., 1997] L. Hirschman and N. Chinchor. Muc-7 named entity task definition. // Proceedings of the 7th Message Understanding Conference (MUC-7), 1997.