А.Михаилян

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

Description of state-of-the-art Natural Language Processing Technologies. Topics concerned include POS tagging, Text Parsing, Automatic Text Summarization. A lot of information on successful linguistic enterprises and research groups is also provided.

Исследования и разработки в области автоматической обработки текста в Европе и США привлекают внимание крупнейших частных фирм и государственных организаций самого высокого уровня. Европейский союз уже несколько лет координирует различные программы в области автоматической обработки текста. Например, 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. Словарь словоформ языка, в котором каждой словоформе соответствует множество лексико-грамматических классов, которые могут иметься у данной словоформы. Например, для словоформы 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

(S (NP-SBJ there)

   (VP is

         (NP-PRD a dog

             (PP-LOC on

                    (NP the porch)))))

Рис 2. Пример анализа текста синтаксическим анализатором ERGO.

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
          $.

Обозначения

Рис 3. Пример анализа текста синтаксическим анализатором FDG;
текстовое представление.

Рис 4. Пример анализа текста синтаксическим анализатором FDG;
визуальное представление.

Один из наиболее оригинальных подходов к синтаксическому анализу текста — 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 .

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

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

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

1. Наличие одного из наиболее совершенных алгоритмов оценки качества реферата.
2. Параллельное использование нескольких широко известных алгоритмов реферирования; непосредственная связь между алгоритмами реферирования и алгоритмом оценки качества реферата.
3. Продажа не готовых программных продуктов, а модулей реферирования (динамических библиотек для Win32 и Solaris платформ).

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

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

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

TextAnalyst

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

Библиография

1. Eric Brill Unsupervised learning of disambiguation rules for part of speech tagging, — Proceedings of ACL-95, 1995.
2. From Language Engeneering to Human Language Technologies (European Commisson report) — MIKADO SA, Luxemburg, 1998.
3. Christer Samuelsson, Atro Voutilainen Comparing a Linguistic and a Stochastic Tagger — Proceedings of 35 Annual Meeting of the Association for Computational Linguistics and 8^th conference of the European Chapter of the Association for Computational Linguistics, ACL, Madrid, 1997.
4. W. N. Francis H. Kucera Manual of Information to accompany A Standard Corpus of Present-Day Edited American English, for use with Digital Computers.— Brown University Providence, Rhode Island Department of Linguistics Brown University, 1979.
5. Linda Van Guilder Automated Part of Speech Tagging: A Brief Overview (Handout for LING361, Fall 1995 Georgetown University) — Georgetown University, 1995.
6. Julian Kupiec, Jan Pedersen, Francine Chen A Trainable Document Summarizer — Xerox Palo Alto Research Centre, Palo Alto, CA, 1995.
7. Hans Jurgen Heringer Dependency syntax - basic ideas and the classical model. — Joachim Jacobs, Arnim von Stechow, Wolfgang Sternefeld, and Theo Venneman, editors // Syntax — An International Handbook of Contemporary Research, volume 1, chapter 12, pages 298-316. Walter de Gruyer, Berlin — New York.
8. Lucien Tesniere Elements de syntaxe structurale. — Editions Klincksieck, 1959, Paris.
9. Daniel D.K.Sleator, David Temperly Parsing English with a Link Grammar — School of Computer Studies, Carnegie-Melon University, Pittsburg, PA, 1991.
10. Pasi Tapanainen, Timo Jarvinen A non-projective dependency parser — Proceedings of Fifth Conference on Applied Natural Language Processing, Washington, D.C., 1997
11. Pasi Tapanainen, Atro Voutilainen Tagging accurately - Don’t'guess if you know. — Computational and Language E-print Archive, 1994
12. Martin Volk, Gerold Schneider Comparing a statistical and a rule-based tagger for German — Proceedings of KONVENS-98, Bonn, 1998.
13. Ellen M.Voorhes, Donna Harman. Overview of Sixth Text Retrieval Conference (TREC-6). — National Institute of Standards and Technology Gaithersburg, MD 20899, 1998

1. Human Language Technology Sector of the Information Society Technologies (IST) Programme 1998 - 2000 — http://www.linglink.lu
2. SPARKLE (Shallow PARsing and Knowledge Extraction for Language Engeneering) — http://www.ilc.pi.cnr.it/sparkle/sparkle.html
3. TIPSTER Text Program archive — http://www.nist.gov/itl/div894/894.02/related_projects/tipster/
4. Linda Van Guilder Handout for LING361, Fall 1995 Georgetown University http://www.georgetown.edu/cball/ling361/tagging_overview.html
5. Teragram Corporation (OEM POS tagger)— http://www.teragram.com/w3/home.htm
6. ERGO Linguistic Technologies — http://www.ergo-ling.com
7. Virtual Reality and Multimedia Conference — http://www.vsmm.vsl.gifu-u.ac.jp/vsmm98
8. Lingsoft (ENGCG)— http://lwww.lingsoft.fi
9. Conexor (Functional Dependency Grammar) — http://www.conexor.fi
10. Link Grammar Homepage — http://bobo.link.cs.cmu.edu/link
11. Inxight — http://www.inxight.com
12. Prosum Summarizer — http://transend.labs.bt.com/cgi-bin/prosum/prosum
13. Extractor — http://ai.iit.nrc.ca/II_public/extractor.html
14. TextAnalyst — http://www.host.ru/~analyst/
15. Computational and Language E-print Archive http://xxx.lanl.gov/find/cmp-lg