Технология построения многовариантных объектно-ориентированных структур текстов

Вид материала

Диссертация

Содержание 1.2.  Классы задач 9 2.3.  Построение системы классов и шаблонов 14 3.1.  Модель классов и шаблонов 28 3.2.  Ядро системы анализа: компилятор и исполнитель 36 4.1.  Роль базовой реализации 40 4.3.  Представление для системы классов и шаблонов 41 4.5.  Архитектура ядра системы 45 4.6.  Морфологический препроцессор 49 Подходы к распознаванию структур текстов Обзор подходов Порождающие грамматики и их расширения Продукционные системы Подходы, основанные на шаблонах Country Capital Language Классы задач Объектно-ориентированный подход Продукционный подход Абстрагирование от вычислительной модели Индустриальная реализация и расширяемость Концепция предлагаемой технологии ... Полное содержание

Подобный материал:

• Ландшафт области управления данными: аналитический обзор, 531.27kb.
• Развитие объектно-ориентированных систем управления базами данных, 122.52kb.
• Лекция № Элементы управления в графических и объектно-ориентированных интерфейсах, 307.9kb.
• Сводный научный отчет за 2010 г по совместному проекту «Разработка объектно-ориентированных, 204.3kb.
• Врамках настоящей работы на примере четырех произведений будут рассмотрены некоторые, 228.04kb.
• Программа вступительного экзамена по специальности 05. 13. 18 Математическое моделирование,, 115.33kb.
• Рабочая программа учебной дисциплины (модуля) Объектно-ориентированное программирование, 99.17kb.
• Исследование организационных структур управления, 469.08kb.
• Темы: Введение в язык rsl, 123.68kb.
• Программа дисциплины Объектно-ориентированное программирование Рекомендуется для направления, 591.42kb.

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
им. М.В. ЛОМОНОСОВА
ФАКУЛЬТЕТ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И КИБЕРНЕТИКИ


На правах рукописи


ШЕВЧЕНКО Михаил Игоревич


Технология построения многовариантных
объектно-ориентированных структур текстов


Специальность 05.13.11 — Математическое и программное обеспечение
вычислительных машин, комплексов и компьютерных сетей


Диссертация на соискание ученой степени
кандидата физико-математических наук


Научный руководитель:


Москва  2005

Оглавление

Введение

В настоящее время одной из проблемных задач в области информационных технологий и искусственного интеллекта является задача по извлечению информации из текста или — более широко — задача понимания текста. Было предложено множество подходов по решению данной задачи, рассмотренных в соответствующей главе данной работы, а также создан ряд прикладных систем, реализующих эти подходы, но в целом решение пока далеко от диктуемого практической потребностью. Это обусловлено различными аспектами. С одной стороны, довлеет требование эффективности, поэтому, как правило, решение строится индивидуально под каждую конкретную задачу, где требуется извлечение смысла из текста; подходы, инновации и ноу-хау глубоко зашиты в программный код и не переносимы на другие схожие задачи. Из-за требования же эффективности, решение, как правило, строится на основе модели конечных автоматов, которая проста в реализации и является наиболее проработанной и быстрой вычислительной моделью. С другой стороны, под каждый подход к анализу текста (а таких подходов существует немало, например, дискурсивный подход, семантически ориентированный подход, поэтапный лингвистический анализ и др.) строится своя система, со своим формализмом и вычислительной моделью, которая реализует данный подход. И таким образом, различные удачные подходы, которые на самом деле являются дополняющими друг друга, оказываются на практике несовместимыми. И, наконец, отсутствует связующее звено между разработчиками, работающими в области анализа текста. Таким звеном для программистов являются алгоритмические языки общего назначения, например, C++ или Object Pascal.

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

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

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

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

В настоящей работе предлагается описание технологии, получившей название "ТОМАТ" — Технология Объектно-ориентированного Многовариантного Анализа Текстов, удовлетворяющей изложенным выше требованиям. Данная технология разрабатывалась автором на факультете ВМиК МГУ им. М.В. Ломоносова при участии РосНИИ Искусственного Интеллекта — в этом институте несколько лет назад был разработан проект под названием "Alex" [Жигалов, Жуков 2002], который был ориентирован на аналогичный круг задач, хотя и более узкий, чем у предлагаемого подхода. Некоторые идеи из этого проекта, а именно, использование шаблонных моделей в качестве системы продукций, были развиты в предлагаемой технологии "ТОМАТ". Новая технология также значительно выиграла благодаря использованию объектно-ориентированного подхода к построению системы шаблонов, а также использованию концепции недоопределенных вычислений для полей классов. Также технология предлагает поддержку многовариантного анализа. Совместное использование перечисленных подходов применительно к задачам построения различных структур текстов (распознавания сложных текстовых конструкций) впервые предлагается автором в данной работе.

1. ^ Подходы к распознаванию структур текстов
   

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

1. ^ Обзор подходов
   

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

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

левая часть -> правая часть

(результат) (образец)


Левая часть представляет собой некоторый объект, конструируемый над текстом, а правая часть задает образец текста, который будет соответствовать данному объекту.

Известен ряд формализмов, позволяющих выразить приведенное соответствие (данная классификация основывается на обзоре [Шаров 1996]):

• конечные автоматы,
  
• конечные преобразователи (Finite State Transducers, FST),
  
• расширенные сети переходов (Augmented Transition Networks, ATN),
  
• порождающие грамматики (контекстно-свободные и контекстно-зависимые, категориальные),
  
• формализмы, основанные на продукциях и правилах,
  
• формализмы, основанные на шаблонах.
  

1. Модель конечных автоматов и ее модификации
   

С помощью регулярного выражения, которое затем транслируется в конечный автомат, можно задать некий текстовый образец. Регулярные выражения являются гибким средством для задания как простых текстовых образцов, так и более сложных, представляющих собой составные текстовые конструкции. Благодаря своей гибкости и эффективности, конечные автоматы используют в системах поиска текстовых конструкций. Примерами таких систем могут служить различные программы поиска по текстовым массивам (корпусам) — см. например, [Шаров БОКР], [Сокирко 2003] и т.п. Язык задания запросов в данных системах либо эквивалентен языку регулярных выражений, либо является незначительным его расширением. Так, в систему DDC введены расширения для поиска по морфологическим классам слов и грамматическим категориям.

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

Кроме того, известным фактом является то, что не все текстовые конструкции можно задать с помощью конечных автоматов. В связи с этим был создан ряд надстроек над традиционной моделью конечных автоматов. Широкой популярностью пользуется формализм расширенных сетей переходов (Augmented Transition Networks, ATN [Вудс 1976], [Woods 1980]). Формализм ATN расширяет грамматику конечных автоматов, вводя аппарат рекурсивного вызова новой подсети переходов (операция PUSH) и набор регистров, в которых хранятся текущие результаты разбора фразы, а также средства работы с этими регистрами. Благодаря регистрам и операциям над значениями, которые там хранятся, ATN-формализм эквивалентен процедурному языку программирования, в котором можно описать образцы произвольной сложности. Популярность ATN-формализма привела к реализации на его основе большого количества инструментальных систем, например, [Хорошевский 1983]. Из-за такого расширения модели теряется декларативная семантика описания и процесс разработки структуры текста становится неразрывно связанным с методом ее построения, таким образом, описание в данной модели практически эквивалентно программированию на алгоритмическом языке, со всеми вытекающими отсюда недостатками.

Другим расширением модели конечных автоматов являются конечные преобразователи. В них имеется две ленты, и сеть переходов устанавливает соответствие между этими лентами. Достоинством данной модели является обратимость описания (то есть с помощью одного и того же набора образцов можно производить и анализ и генерацию), а также возможность многовариантного параллельного анализа [Koskinniemi 1982]. Модели конечных преобразователей присущи те же недостатки, что и конечным автоматам, а именно, не все конструкции текста на естественном языке могут быть заданы с помощью конечного преобразователя [Karttunen 1991], а сами эти выражения, описывающие структуры текста, слишком громоздки и трудны для разработки, отладки и развития. В связи с этим системы, основанные на конечных преобразователях, используются при поиске образцов, структура которых редко меняется, — это относится к фонетическому и морфологическому анализу текстов. Хотя был сделан ряд попыток построения более сложных систем на основе модели конечных преобразователей: например разметчик текста по частям речи для английского языка [Brill 1992], система извлечения данных из текста [Appelt et al. 1993], разметчик именных групп для английского языка [Schiller 1996] и др.

2. ^ Порождающие грамматики и их расширения
   

Порождающие грамматики позволяют описать структуру текста непосредственно в виде множества продукций. Описание синтаксической структуры английского предложения в рамках контекстно-свободной порождающей грамматики выглядит следующим образом (см. [Хомский 1962]):

S -> NP VP

NP -> Adj NP

NP -> Det N

NP -> N

VP -> MV NP

VP -> MV

MV -> Aux V

Det -> a

Det -> the

Aux -> do

V -> go

N -> boy

...


Процедуры анализа структуры текста, основанные на порождающих грамматиках, более многообразны, нежели основанные на регулярных выражениях. Существует два способа применения правил, подобных приведенным выше: снизу вверх (bottom-up) и сверху вниз (top-down). В первом случае, исходя из данного текста, применяются правила, заменяющие структуру, описанную в правой части, символом, представленным в левой. Во втором случае доказывается выводимость данного предложения из начального символа S. Часто оказывается возможным применить правила несколькими способами при анализе снизу вверх. Например, в соответствии с в вышеприведенными правилами построить глагольную группу пятым и шестым правилом или при анализе сверху вниз применить несколько возможных правил. Две стандартные стратегии применения правил при возможности альтернативного выбора: поиск "в ширину" и "в глубину". В первом случае запоминаются все возможные варианты, и каждый из них разворачивается параллельно (или по очереди в случае последовательного анализа), при неудаче какого-либо варианта разбора соответствующий вариант удаляется из набора возможностей. Во втором случае, при анализе "в глубину", выбирается одна из альтернатив, а при неудаче построения разбора происходит возврат на точку последней альтернативы и выбор другого варианта.

Использование анализа с проходом сверху-вниз позволяет не порождать неграмматичные варианты, с другой стороны, анализ снизу-вверх позволяет не генерировать гипотезы разбора, невозможные для данного предложения. Комбинацию достоинств этих вариантов представляет анализ с помощью таблиц хорошо сформированных составляющих, которые являются результатами частичного разбора. В случае, если разбор по какому-то пути зашел в тупик, происходит возврат на точку последнего выбора правил и делается попытка использовать другое правило. Однако составляющие , порожденные предыдущим способом разбора, сохраняются в таблицах и могут быть использованы в разборе по текущей ветке. Все же эта информация еще не запрещает проход анализа по тем веткам, которые уже были опробованы, но неудачно. Для этой цели применяется запоминание также и гипотез, выдвигаемых при разборе, и результатов их проверки. Такой подход называется анализом с помощью схем (chart parsing). Впервые его предложил Мартин Кэй в системе Powerful Parser [Kay 1976]. Варианты построения системы правил и реализации анализа, избавленного от недетерминизма при из выборе в большинстве случаев, были предложены Маркусом [Marcus 1980] и Томитой [Tomita 1986].

Классические порождающие грамматики, предложенные Хомским, имеют ряд недостатков. В первую очередь к ним относится невозможность представления такого феномена естественного языка, как субкатегоризации, то есть специфических свойств подкласса какой-либо категории. Например, КС-грамматика, приведенная в начале раздела, не отличает переходные и непереходные глаголы, поэтому она принимает предложения, содержащие прямые дополнения у непереходных глаголов. Если же ввести два нетерминальных символа, TV (transitive verb) и IV (intransitive verb) для переходных и непереходных глаголов соответственно, то в этом формализме невозможно будет отразить свойства, общие для обеих групп глаголов.

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

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

Так, система построения грамматик LIFER [Hendrix 1977], обладает возможность использовать ЛИСП-функции в правых частях правил. Система MCHART реализует базовый компонент анализа с помощью схем, позволяет определять стратегии применения правил переходов, выполнять алгоритмы анализа сверху-вниз и слева-направо [Thompson 1983]. В данный класс расширений КС-грамматик можно отнести также уже упоминавшиеся сети Вудса (см. выше), позволяющие алгоритмически управлять процессом анализа.

Другим расширением порождающих грамматик стало добавление возможности использования наследования [Шаров 1996], [Daelemans et al 1992]. Организация структур в виде классов, отличающихся степенью абстракции, является естественным способом описания многих лингвистических, в том числе текстовых, структур. Классификация позволяет вобрать информацию, общую для группы конструкций, в описание соответствующего класса, которое наследуется этими конструкциями. Развитие принципа классификации приводит к развитой иерархии классов, например, феномен субкатегоризации можно описать введением абстрактного класса глаголов и наследованием его классами переходных и непереходных глаголов. Возможны два типа наследования: одиночное и множественное. Большую гибкость и полноту описания допускает множественное наследование [Шаров 1996].

Формализм PATR II [Shieber 1986] расширяет синтаксис описания КС-правил введением атрибутов и их значений. Это означает, что нетерминальные символы могут иметь внутреннюю структуру, в частности это дает возможность представлять подкатегоризацию. Ниже в первом блоке строк записаны три правила. Первые два описывают фразы с переходным и непереходным глаголами, последнее предлагает элегантное решение для представления однородных членов любого типа (именные группы, глагольные группы, предложения): для построения составляющей однородного выражения компоненты этого выражения должны быть соединены союзом (категория C), иметь одинаковую категорию и согласовательные признаки. В следующем блоке строк записан словарь.

Rule {непереходный глагол}

VP -> V:

= .

Rule {переходный глагол}

VP -> V X

= .

Rule {однородные члены}

X0 -> X1 C X2

=

=

=

= .


Word идет:

= V

= .

Word видит:

= V

= NP.

Word и:

= C.

Word или:

= C.


Обзор расширений порождающих грамматик был бы неполным без упоминания формализма TAG (Text Adjoining Grammar), используемого для описания иерархических структур предложения [Joshi 1987]. Формализм TAG предназначен для разделения двух типов данных, описывающих иерархическую структуру предложения: необходимых нерекурсивных структур, соответствующих видам фраз, и структур, способных рекурсивно разворачиваться.

3. ^ Продукционные системы
   

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

Одной из систем подобного рода является система TULIPS [Мальковский 1985]. В системе TULIPS средствами языка ПЛЭНЕР [Пильщиков 1983] реализован гибкий механизм сопоставления с образцом. В качестве примера приведем образец, задающий именную группу в форме винительного падежа, множественного числа, управляющее существительное которой принадлежит классу LOC:

((27 0 0 0 4) (=ROOT (=SUP = LOC)))


С помощью правил, основанных на образцах, в системе TULIPS проводится синтаксический, лексико-семантический и прагматический анализ.

Другим примером системы, основанной на продукциях, является система SNOOP [Шаров 1997]. В ней на основе текста строится цепочка объектов (каждый объект является экземпляром некоторого класса), которая затем модифицируются с помощью правил-продукций. В результате может получиться сложноорганизованная семантическая сеть. Механизм продукций системы SNOOP позволяет эффективно работать с объектно-ориентированными семантическими сетями, однако первичное построение сети по тексту проработано не очень глубоко (задается простейшими образцами, напоминающими регулярные выражения), в связи с чем возникает потребность во вспомогательных процедурах обработки текста для построения семантической сети (см., например, [Ажичаков, Егорушкин 2001]).

Дальнейшее развитие продукционных систем привело к выделению особого этапа — этапа подготовки текстов к их последующему анализу с помощью продукционных правил. Данный этап носит название лексического анализа. На этапе лексического анализа должны распознаваться текстовые конструкции, из которых конструируются объекты, которые впоследствии обрабатываются продукционными механизмами самой системы. Такой подход реализован в системе СемП [Semp-F 1997], объединяющей идеи, предложенные в SNOOP, и вычислительную мощь механизма недоопределенных вычислений [Нариньяни 1980a].

4. ^ Подходы, основанные на шаблонах
   

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

Примером систем подобного рода может служить система анализа на ЕЯ-запросов к базам данных, реализованная в Microsoft SQL Server 97 [Жигалов 2000]. Рассмотрим таблицу базы данных, содержащую информацию о странах:

^ Country Capital Language


France Paris French

Italy Rome Italian

... ... ...


Простейшую основанную на шаблонах систему можно построить с помощью следующих шаблонов:

Шаблон:

... "capital"... .


Запрос:

SELECT Capital FROM Table WHERE Country =


Шаблон:

... "capital" . . ."country"


Действие:

SELECT Capital, Country FROM Table


Согласно первому шаблону, если ЕЯ-запрос содержит слово "capital" перед названием страны (т.е. значением поля Country), то система найдет записи, содержащие это название страны, и выведет соответствующую столицу. Например, для запроса "What is the capital of Italy?" будет использовано первое правило, и ответ будет "Rome". То же самое правило применится для запроса "Print the capital of Italy.", "Could you please tell me what is the capital of Italy?", и т.д. Во всех этих случаях ответ будет одинаковым.

В соответствии со вторым правилом, любой ЕЯ-запрос, в котором слово "capital" предшествует слову "country", вернет столицу каждой страны в соответствии с содержимым таблицы. Так, запросы "What is the capital of each country?", "List the capital of every country.", "Capital and country, please." будут подходить под второе правило.

Система "Alex 0" также основана на модели шаблонов. Основной задачей системы является структурирование текста на основе лексических шаблонов. Лексический шаблон представляет выражение, задающее текстовую конструкцию, состоящую из слов, пробелов и знаков препинания. Приведем пример лексического шаблона "Alex 0":