А.Михаилян

Введение
Исследования и разработки в области автоматической обработки текста в Европе и США привлекают внимание крупнейших частных фирм и государственных организаций самого высокого уровня. Европейский союз уже несколько лет координирует различные программы в области автоматической обработки текста. Например, Human Language Technology Sector of the Information Society Technologies (IST) Programme 1998 - 2000. Один из наиболее интересных проектов в рамках данной программы - SPARKLE (Shallow PARsing and Knowledge Extraction for Language Engeneering). В числе его участников - Dimler-Benz, Xerox Research Centre in Europe и Cambridge University Computer Laboratory. Цель проекта - создание частичных синтаксических анализаторов для основных языков Европейского союза.

В США с 1991 до осени 1998 года существовал проект TIPSTER, организованный DARPA, Департаментом Обороны и ЦРУ совместно с Национальным Институтом Стандартов и Технологий и Центром военно-воздушных и военно-морских вооружений (SPAWAR). В работе консультативного совета программы участвовали также ФБР, Национальный Научный Фонд и некоторые другие организации. Основной целью программы было сравнение и оценка результатов работы различных поисковых систем и систем реферирования.

Необходимо отметить, что такие задачи как распознование и генерация речи, создание поисковых систем до настоящего времени решаются с минимальным участием лингвистов. Это обусловлено использованием при решении вышеупомянутых задач в основном статистических методов.

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

Лексико-грамматический анализ (Part-of-Speech-tagging)

Задача лексико-грамматического анализа - автоматически распознать, какой части речи принадлежит каждое слово тексте. На рис.1 показан пример текста, в котором каждому слову поставлен в соответствие лексико-грамматический класс [Francis and Kucera, 1979].

Цитата :

When/WRB you/PPSS access/VB the/AT BIB/NN record/NN you/PPSS
want/VB ,/, you/PPSS can/MD print/VB the/AT screen/NN ,/, write/VB
down/RP any/DTI information/NN you/PPSS need/VB ,/, or/CC select/VB
the/AT item/NN if/CS you/PPSS are/BER placing/VBG a/AT hold/NN ./.

Обозначения

WRB - Wh-наречие
PSS - личное местоимение 3 л., ед.ч.
VB - инфинитив или глагол не 3-е л., ед.ч.
AT - опр.артикль
NN - существительное ед.ч.
MD - модальный глагол
RP - послелог
DTI - предопределитель
CC - сочинительный союз
CS - подчинительный союз
BER - глагол be, 3 л., ед.ч.
VBG - participle I или герундий
. - точка


Данную задачу не представляет труда выполнить для русского языка благодаря его развитой морфологии практически со стопроцентной точностью. В английском языке простой алгоритм, присваивающий каждому слову в тексте наиболее вероятный для данного слова лексико-грамматический класс (син. часть речи) работает с точностью около 90 %, что обусловлено лексической многозначностью английского языка.

Для улучшения точности лексико-грамматического анализа используются два типа алгоритмов: вероятностно-статистические и основанные на продукционных правилах, оперирующих словами и кодами.

Большинство вероятностно-статистических алгоритмов [Linda Van Guilder, 1995] использует два источника информации:

1. Словарь словоформ языка, в котором каждой словоформе соответствует множество лексико-грамматических классов, которые могут иметься у данной словоформы. Например, для словоформы well в словаре указано, что она может быть наречием, существительным, прилагательным и междометием. Для каждого лексико-грамматического класса словоформы указывается частота его встречаемости относительно других лексико-грамматических классов данной словоформы. Частота обычно подсчитывается на корпусе текстов, в котором предварительно вручную каждому слову приведен в соответствие лексико-грамматический класс. Таким образом, словоформа well в словаре будет представлена следующим образом:

Цитата :

well noun 4 occurences in corpus
well adverb 1567 occurences in corpus
well adjective 6 occurences in corpus
well interjection 1 occurences in corpus

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

Цитата :

неопр.артикль + сущ.ед.ч 35983 occurences in corpus
неопр.артикль + сущ.мн.ч 7494 occurences in corpus
опр.артикль + сущ.ед.ч 13838 occurences in corpus
неопр.артикль + сущ.мн.ч 47 occurences in corpus
неопр.артикль + глагол 3 л., ед.ч 0 occurences in corpus
глагол 3 л., ед.ч + предлог 3744 occurences in corpus

В триграмной модели и квадриграмной модели используется соответственно информация о всех возможных последовательностях из 3-х и 4-х кодов.

Данная информация обрабатывается программой, использующей статистические алгоритмы, чаще всего алгоритм скрытых цепей Маркова [Linda Van Guilder, 1995] для нахождения наиболее вероятного лексико-грамматического класса для каждого слова в предложении.

Алгоритмы, основанные на продукционных правилах, используют правила собранные автоматически с корпуса текстов [Brill, 1995], либо подготовленные квалифицированными лингвистами [Tapanainen and Voutilainen, 1994]. Примером могут быть следующие правила:

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

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

Оба подхода дают примерно одинаковый результат [Samuelsson and Voutilainen, 1997] [Volk and Schneider, 1998]. При их использовании раздельно либо в различных комбинациях точность лексико-грамматического анализа улучшается до 96-98 %. Поскольку точность при лексико-грамматическом анализа текста вручную также имеет определенную погрешность (0,5-2 %) согласно сведениям, предоставленным создателями Penn Treebank), можно считать, что точность лексико-грамматического анализа в автоматическом режиме достигла практически точности лексико-грамматического анализа в ручном режиме.

Синтаксический анализ (Text Parsing)

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

Ergo Linguistic Technologies Parser

Синтаксический анализатор (parser), разработанный Дереком Бикертоном и Филипом Браликом из Университета Гонолулу использует схему аннотации, принятую в Penn Treebank. Данная схема широко известна и имеет очень наглядное представление. Наибольший интерес представляет маркетинговая политика фирмы. ERGO ориентирует свой парсер на использование в вопросно-ответных интерфейсах. Данная особенность привлекла к ERGO внимание производителей компьютерных игр, VRML Consortsium, HAPTEK, и позволила ERGO получить "Первую техническую премию" на Конференции по Виртуальной Реальности и Мультимедиа (Virtual Reality and Multi-Media Conference in Japan - 98). ERGO пока является единственной компанией, которая имеет парсер, способный определять тип вопроса (вопрос к подлежащему, субъекту, прямому или косвенному дополнению, или обстоятельству) и конструировать "на лету" ответ. Наиболее известная система, использующая парсер ERGO - Virtual Friend - выпускается фирмой HAPTEK Technologies и представляет собой виртуальную игрушку.

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

Цитата :

(S (NP-SBJ there)
(VP is
(NP-PRD a dog
(PP-LOC on
(NP the porch)))))

Обозначения S - предложение
NP - именная группа
NP-SBJ - именная группа - субъект
VP - verb phrase
NP-PRD - именная группа - объект
PP_LOC - предложно-именная группа, локатив


Functional Dependency Grammar

Создан исследователями из Хельсинского Университета, позднее основавшими две фирмы: Lingsoft и Conexor. Один из наиболее удачных синтаксических анализаторов. Ранняя версия под названием ENGCG (English Constraint Grammar) была использована для аннотации самого большого в мире корпуса - Bank of English, принадлежащего издательству Collins/Harper Publishers. Отличительной особенностью данного синтаксического анализатора является то, что в случаях, когда невозможно снять многозначность, синтаксический анализатор либо выдает несколько вариантов анализа, либо не достраивает дерево для данной части предложения. В основе FDG лежит теория зависимостей, впервые предложенная Л.Теньером [Tesniere, 1959], позднее описанная Герингером [Heringer, 1993] и реализованная в рамках контекстно-зависимой грамматики [Tapanainen and Jarvinen, 1997]. На рис. 3 и 4 показан пример разбора фразы синтаксическим анализатором FDG.

Цитата :

0
1 Lots+of lots+of det:>2 @DN> DET
2 people people subj:>3 @SUBJ N
3 act act main:>0 @+FMAINV V
4 well well man:>3 @ADVL ADV
5 but but cc:>3 @CC CC
6 very very @AD-A> ADV
7 few few det:>8 @DN> DET
8 people people subj:>9 @SUBJ N
9 talk talk cc:>3 @+FMAINV V
10 well well man:>9 @ADVL ADV
$.

Обозначения

Идентификаторы дерева фразы:

det: - определитель
subj: - субъект
main: - основной элемент
man: - обстоятельство образа действи
сс: - сочинительный союз

Функциональные идентификаторы:

@DN> - определитель
@SUBJ - субъект
@+FMAINV - личный предикатор
@ADVL - обстоятельство
@CC - сочинительный союз
@AD-A> - интенсификатор


PROGRAM Conexor Functional Dependency Grammar of English (visual output)
OUTPUT:

Link Parser

Один из наиболее оригинальных подходов к синтаксическому анализу текста - Link Parser, разработанный в Carnegie-Melon University. Этот синтаксический анализатор - единственный, чьи исходные коды были опубликованы он-лайн. Тогда как большинство систем синтаксического анализа используют структуры уровня именных и глагольных групп, при построении дерева фразы, Link Grammar, лежащая в основе Link Parser'а, использует информацию о типах связей, которые каждое слово может иметь со словами, находящимися справа или слева и несколько общих грамматических правил. На рис.5 показано предложение, анализированное с помощью Link Parser.

Цитата :

+-----------------Xp-----------------+
| +--------Sp--------+ |
+--Wd--+-Mp-+--Jp-+ +--MVa-+ |
| | | | | | |
///// lots.n of people.p talk.v well.e .

Обозначения

Xp - связь между началом и концом предложени
Sp - связь между существительным и глаголом
Wd - связь между началом предложения и предложением
Mp - связь между именной группой и модифицирующей ее предложно-именной группой
Jp - связь между предлогом и относящейся к нему именной группой
MVa - связь между глаголом (прилагательным) и модификатором


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

Автоматическое реферирование(Automatic Text Summarization)

На рынке присутствует очень небольшое количество традиционных программ реферирования, то есть таких, которые выделяют наиболее весомые предложения из текста используя статистические алгоритмы, либо слова-подсказки. Inxight Summarizer [Kupiec, Pedersen and Chen, 1995] - одна из наиболее известных коммерчески распространяемых систем реферирования. Inxight Summarizer был создан в Исследовательском центре Ксерокса в Пало Альто. Причин успеха данной системы несколько:
Наличие одного из наиболее совершенных алгоритмов оценки качества реферата.
Параллельное использование нескольких широко известных алгоритмов реферирования; непосредственная связь между алгоритмами реферирования и алгоритмом оценки качества реферата.
Продажа не готовых программных продуктов, а модулей реферирования (динамических библиотек для Win32 и Solaris платформ).

Среди коммерческих систем также можно отметить Prosum - систему реферирования, разработанную British Telecommunications Laboratories в рамках экспериментальной коммерческой он-лайн платформы TranSend и представляет собой cgi-скрипт, встроенный в веб-страницу. Каждый реферат стоит 0,25 пенсов и оплачивается с помощью кредитных карточек MicroCredit.

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

Extractor

Extractor создан в Институте Информационных Технологий Национального исследовательского Совета Канады. Он представляет собой модуль, выделяющий из представленного ему на вход текста наиболее информативные именные группы. По умолчанию количество таких групп - 7 вне зависимости от длины текста. Extractor используется в программных продуктах фирм ThinkTank Technologies и Tetranet, а также в поисковой системе Журнала Исследований в Области Искусственного Интеллекта.

TextAnalyst

Данная программа создана в московском Научно-производственном инновационном центре "МикроСистемы". TextAnalyst работает только с русским языком, выделяя именные группы и строя на их основе семантическую сеть - структуру взаимозависимостей между именными группами.