Построение вопросно-ответной системы с использованием метода математической формализации естественных языков тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

ВВЕДЕНИЕ.

ГЛАВА L ОСНОВНЫЕ ПРИНЦИПЫ ФОРМАЛИЗАЦИИ ПРЕДЛОЖЕНИЙ НА РУССКОМ ЯЗЫКЕ.

§1. Базовые тезисы.

§2. Иерархия базисных понятий.

§3. Семантика предложно-падежных форм.

ГЛАВА II. СЕМАНТИКА ПРЕДЛОЖЕНИЯ.

§1. Предварительная (морфологическая) обработка предложения. п.1 Создание морфологической структуры предложения. п.2 Простейший отброс альтернатив.

§2. Объектная обработка предложения. п.1 Создание и заполнение 0-формы.,. п.2 Создание и заполнение 1-формы. п.З Создание и заполнение 2-формы.

§3. Первичная обработка операций над действиями.

§4. Первичный анализ однородных членов предложения.

§5. Первичная обработка причастных и деепричастных оборотов.

§6. Алгоритм склейки части предложения, для которой определено центральное слово.

§7. Построение семантической формулы для причастных оборотов.

§8. Построение семантической формулы для деепричастных оборотов.

§9. Генеральная склейка простого предложения в семантическую формулу.

ГЛАВА III. ПОСТРОЕНИЕ ВОПРОСНО-ОТВЕТНОЙ СИСТЕМЫ.

§1. Постановка задачи.

§2. Некоторые особенности семантического анализа текста.

§3. Организация базы знаний.

§4. Обработка входного текста и запросов. Организация уровней понимания вВОС.

§5. Организация механизма доступа.

Мы живем во время бурного развития информационных и компьютерных технологий. Задачи передачи, хранения и использования информации являются сегодня одними из самых актуальных проблем в области кибернетики и информатики. При решении конкретных задач в этой области непременно сталкиваешься с проблемой анализа текстов на естественных языках, будь то английский, русский или какой-нибудь другой язык общения людей между собой. Эта проблема стала в некотором роде «бичом» разработчиков интеллектуальных систем, таких как системы машинного перевода ([1,2, 3]), системы автоматического поиска текста в массивах «необработанных» данных ([4, 5]), заполнение баз знаний и т. п.

Между тем, эта проблема родилась не сегодня, а в конце пятидесятых годов, когда появление первых компьютеров вызвало «интеллектуальный взрыв» в научном обществе, связанный с постановкой новых задач перед разработчиками систем искусственного интеллекта. В отличие от других задач для ЭВМ, которые имеют некоторое алгоритмическое решение, задачи данного класса характеризуются отсутствием известных схем решения априори. Для их решения используются иерархические построения и программы, имитирующие механизмы мышления человека [6]. Традиционно «узким» местом здесь является автоматическое выделение хотя бы элементарного смысла из текста на естественном языке.

Пионерами в области автоматического распознавания текстов принято считать специалистов Кембриджской школы семантики [7], в частности, М. Мастермана. Английскими учеными уже в начале 60-х годов была построена целая серия семантических языков, наибольший интерес из них представляет поздняя версия. В языке (английском) было выделено 58 элементарных смыслов - сем, или классификаторов, а также были введены рекурсивные правила построения из них формул. Классификаторы были сведены в несколько сот шаблонов, каждый из которых содержит по 3 классификатора, определяющих класс элементарных ситуаций. К таким шаблонам, к примеру, относятся формы «человек-место-делать», или «человек-движение-место». Далее анализ производится в два этапа. На первом этапе текст при помощи специального алгоритма разбивается на фрагменты, которые затем проверяются на содержание троек классификаторов, соответствующим шаблонам, которые далее и заменяются шаблонами. Разбиение предложения на шаблоны при этом может быть и неоднозначным (перекрещивающимся). На втором этапе для каждого варианта разбиения устанавливается, является ли полученная последовательность шаблонов семантически связанной. Два следующих друг за другом шаблона считаются семантически связанными, если какой-нибудь классификатор первого шаблона совпадает с каким-нибудь классификатором (или отрицанием классификатора) второго шаблона. Подробней об этом алгоритме можно узнать в [8].

Можно сказать, что результаты исследований ученых из Кембриджа повлияли на возникновение и все дальнейшее развитие новой по тем временам науки - компьютерной лингвистики (см. о компьютерной лингвистике в [9]). Несмотря на то, что представителям Кембриджской школы семантики не удалось по чисто техническим причинам довести свой проект до логической точки, основные результаты этих исследований, а также их некоторые методы и приемы легли в основу, или хотя бы эхом отозвались в работах многих известных ученых в этой области, таких как Н. Хомский [10], И.А. Мельчук [11, 12], Ю.Д. Апресян [7].

В нашей стране «бум» компьютерной лингвистики пришелся на середину-конец 70-х годов прошлого века (см., например [13, 14, 15, 16]). После некоторого периода скептицизма (80-е годы) вновь начал возрастать интерес к прикладным задачам теории искусственного интеллекта и компьютерной лингвистики ([17, 18, 19, 20, 21]). Этот рост продолжается и по сей день.

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

Постановка задачи: Конструируется интеллектуальная система анализа текста на русском языке. На вход системы подается текст, состоящий из одного или нескольких предложений. От системы требуется, после соответствующей обработки входного текста, «умение» отвечать на вопросы по введенному тексту (более полную постановку задачи построения ВОС см. в § 1 Главы III). См. также [22].

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

Предположим, на вход ВОС подается фраза «Миша и Коля - одноклассники». Вопрос «Кто учится в одном классе?» одолеет, скорее всего, каждая ВОС, а вот вопрос «Кто учится в одной школе?» в большинстве случаев потребует перефразировать вопрос. Возможно, даже не со второго раза удастся «угадать» нужную форму вопроса.

Это неудобство и послужило поводом к разработке систем автоматического перефразирования текстов, пик создания которых пришелся на середину 70-х годов прошлого века. С некоторыми результатами в этой области можно ознакомиться, к примеру, в работах [7, 11]. В данной работе проблема необходимости перефразировки отсутствует. Подробнее об этом можно прочитать Главе III.

Целями настоящей работы являются:

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

2. Решение задачи построения вопросно-ответной системы с использованием указанного семантического графа.

Для достижения поставленных целей выполнялись следующие задачи:

1. Построение иерархии базисных существительных (§2 Главы I).

2. Семантический анализ предложно-падежных форм с целью определения их семантико-грамматического типа (§3 Главы I).

3. Построение семантического анализатора предложения, преобразующего предложение на русском языке в формульную структуру (см. Главу II).

4. Установление кореференциальных и анафорических связей между предложениями (см. §2 Главы III).

5. Преобразование полученной формульной структуры в семантическую сеть (см. §3 Главы III).

6. Решение задачи построения вопросно-ответной системы. В рамках этой задачи предложена семантическая операция сопоставления, позволяющая находить релевантные запросу ответы (см. §§4-5 Главы III).

На защиту выносятся:

1. Иерархия базисных существительных русского языка, построенная в виде ориентированного дерева типа РОД-ВИД и определяющая значительную часть структурных и ассоциативных связей в тексте.

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

3. Концепция построения вопросно-ответной системы с помощью семантической сети.

Скажу несколько слов об актуальности проведенных исследований. Компьютер не может понимать естественные языки, как, впрочем, не понимает он и языки программирования. Но можно и нужно заставить машину уметь выполнять задания, представленные ей в форме естественного языка. Вот здесь как раз и возникает вопрос о формализации этого языка, то есть переработки данных на естественном, понятном для человека языке на некоторый формальный (созданный программистом) язык, работа с которым была бы более удобной именно для компьютера. Формализация естественного языка позволила бы решить много насущных проблем, таких как задача автоматического перевода, задача сортировки документов (как в электронном, так и в бумажном виде), задача автоматического поиска информации (в том числе, в электронных сетях) и другие. Подробнее об использовании формализации естественных языков можно прочитать в работах [1, 4, 5, 23, 24]. Мною были проведены исследования в области формализации русского языка и разработан алгоритм формализации произвольного предложения на русском языке. Важную роль в исследованиях сыграли идеи, изложенные в [25, 26, 27, 28]. Методика исследования и результаты подробно описаны в Главах I и II.

Однако, только формализация естественного языка не дает нам немедленного решения поставленной выше задачи. Предположим, удалось перевести входной текст и текст вопроса в некоторый формальный вид. Теперь нужно разработать некоторые правила, с помощью которых возможно определить, имеет ли вопрос адекватный ответ в исходном тексте. Кроме того, в случае возникновения нескольких альтернатив ответа желательно иметь и правила, позволяющие нам отбросить максимальное число ненужных альтернатив. Иными словами, необходимо выявить критерии наибольшей связанности семантической формулы вопроса и некоторой, по возможности единственной, части входного текста. Решение этих задач, а также вопросы хранения и обработки формализованного входного текста обсуждаются в Главе III. Некоторые идеи и методы исследования в этой области заимствованы в [7, 11, 12]; в этом случае будут даны соответствующие указания. Вопросы, связанные с конструированием ВОС, весьма актуальны особенно сейчас, в век бурного развития информатики, информационных и сетевых технологий. Пользователю электронных сетей не нужно будет часами проглядывать массивы информации, а можно будет лишь с помощью 2-3 вопросов выяснить, имеется ли в текущей базе данных необходимая ему информация. Также изменится и подход к проблеме автоматического поиска, сортировки информации, появится возмож

Заключение.

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

В ходе исследований были получены следующие теоретические и практические результаты:

1. Создана иерархия базисных существительных (см. §2 Главы I). Разбиение множества существительных по базисным классам было проведено в 1998-2000 годах Тузовым В.А. при моем непосредственном участии. Незначительные поправки постоянно вносятся и в настоящее время. На данный момент существует порядка 1100 классов базисных существительных. Множество всех классов представляет собой древовидную структуру типа РОД-ВИД. Построены также аналогичные иерархии базисных прилагательных ([35]) и наречий (находится в доработке).

2. Построен алгоритм семантического анализа предложно-падежных форм (см. §3 Главы I). Получена зависимость семантико-грамматического типа предложно-падежной формы от базисного класса существительного предложно-падежной формы и, в некоторых случая, от морфологических (совершенность глагола, число, часть речи) и семантических (базисный класс) свойств присоединяющего предложно-падежную форму слова. Для каждого предлога русского языка представлены правила распознавания се-мантико-грамматического типа, которое имеет большое значение для определения семантики свободных предложно-падежных форм. Зная семантико -грамматический тип свободной предложно-падежной формы, можно с большой долей вероятности определить связи этой предложно-падежной формы с другими словами предложения, построить для нее семантическую формулу (если она отсутствует в семантическом словаре) и привязать ее к семантической формуле всего предложения.

3. Разработан семантический анализатор простых распространенных предложений на русском языке (за исключением предложений, содержащих тире) - см. Главу II. Полученный семантический анализатор тестировался на нескольких тысячах предложений, адекватность семантического перевода -70-80%. Описанный в Главе II алгоритм обладает следующими основными характеристиками:

1) Построена стройная морфологическая структура. Для каждого слова предложения можно быстро найти его морфологические описания, удалить ненужные альтернативы, вставить новые и т.п. (см. §1 Главы II). В основе алгоритма лежит объектно-ориентированный подход. Каждая форма ЧИСЛО-ПАДЕЖ, каждое слово и все предложение целиком представляют собой объекты морфологической структуры.

2) За объекты семантической структуры принимаются существительные, личные местоимения, количественные числительные, присутствующие в предложении (см. §2 Главы II). Для удобства работы с объектами созданы специальные объектные формы:

• 0-форма для хранения самих объектов и первичной информации об их связях, а также предположений об их истинных морфологических (иногда и лексических) альтернативах.

• 1 -форма (и форма описаний) для хранения информации о свойствах объектов.

• 2-форма для хранения информации о предложно-падежных формах, их семантико-грамматическом типе и семантической формуле.

• Форма операций над действиями (ФОД) для хранения информации о наречиях и эквивалентных им предложно-падежных формах. Здесь также находится информация о том объекте морфологической структуры, к которому применяется та или иная операция над действием (см. §3 Главы II).

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

3) Организована обработка предложений, содержащих однородные члены. Для этого строится специальная синтаксическая структура, позволяющая практически однозначно распознавать однородные члены для всех знаменательных частей речи (глагол, существительное, прилагательное, местоимение, наречие), а также предложно-падежных форм (по семантико-грамматическому типу) - см. об этом §4 Главы II. Дополнительно разработана процедура склейки единой семантической формулы для группы однородных членов в зависимости от их типа и вида однородности (см. §6 Главы II).

4) При построении семантической формулы предложения учитывается наличие или отсутствие в предложении центрального слова. Для предложений, имеющих непустое центральное слово, построен специальный алгоритм «склейки» семантической формулы, описанный в §6 Главы II.

5) Причастные и деепричастные обороты анализируются как отдельные предложения, что придает анализатору определенную гибкость и расширяет поле действия для решения прикладных задач (особенно таких, как машинный перевод или автореферирование). Причастные и деепричастные обороты анализируются как предложения, имеющие центральное слово (причастие и деепричастие, соответственно). Для каждого из оборотов создается своя специальная индексная форма, где хранится информация о месте расположения оборота в предложении и о базовом слове. Принципы анализа причастных и деепричастных оборотов описаны в §§5, 7-8 Главы II.

6) Приведены правила определения центрального слова предложения. Для анализа предложений с пустым центральным словом разработан отдельный алгоритм. Выявлено 20 классов предложений (за исключением предложений, содержащих тире), имеющих центральное слово, не являющееся глаголом в личной или безличной форме. Для каждого из этих классов описан способ построения семантической формулы (см. §9 Главы II).

Указанный семантический анализатор практически реализован на языке С++.

4. Раскрыты принципы семантического анализа небольшого текста или части большого текста (главы, параграфа, пункта и т.п.), такие как фиксирование последовательности разверстки текста, установление связей преференции и анафорических связей, морфологическое и синтаксическое сопоставление предложений (см. §2 Главы III).

5. Разработана схема построения базы знаний по входному тексту. При этом используются результаты, полученные в Главах I-II, а именно, морфологическая структура, иерархия базисных слов, объектные и индексные формы, семантические формулы слов, предложения целиком и его частей. В базе знаний между сущностями устанавливается три вида связей (помимо связей кореференции): структурные, логические и ассоциативные (введено 6 видов ассоциативности). Построенная база знаний позволяет ввести общую модель представления знаний - семантическую сеть (граф). Принципы построения семантической сети по входному тексту описаны в §3 Главы III.

6. Описанные выше результаты позволили реализовать вопросно-ответную систему по методам, описанным в §§4-5 Главы III. В целях возможности логического вывода к построенной базе знаний подключаются дополнительные базы знаний логик текста, а также сценарии (если это целесообразно). Построены базы знаний логик текста для описания временных и пространственных закономерностей и некоторые сценарии для неспециализированных предметных областей. Представлен алгоритм для операции сопоставления запрашиваемых сущностей информационным единицам построенной базы знаний. Данная операция сопоставления полностью реализована для вопросительных слов групп I-II (см. таблицу 17). Таким образом, поставленную в §1 Главы III задачу построения ВОС можно считать решенной в рамках настоящей работы.

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

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

1. Корхова О.В. Формализация естественных языков как метод машинного перевода. Деп. в ВИНИТИ, М.: № 3893-В99.

2. Мартемьянов Ю.С. Проблемы актуального членения в исследованиях по автоматическому переводу и реферированию. М., 1981.

3. Нелюбин JI.JI. Компьютерная лингвистика и машинный перевод. М., 1991.

4. Корхов А.В. Использование формализации естественных языков в задаче автоматического поиска. Деп. в ВИНИТИ, М.: № 3892-В99.

5. Корхов А.В., Корхова О.В. Алгоритм решения задачи автоматического поиска с использованием метода формализации русского языка. Деп. в ВИНИТИ, М.: № 70-В01.

6. Болотова JI.C. и др. Системы искусственного интеллекта. М., 1998.

7. Апресян Ю.Д. Лексическая семантика (избранные труды). Том 1. М., 1995.

8. Математическая лингвистика / сборник переводов. М., 1961.

9. Анисимов А.В. Компьютерная лингвистика для всех: Мифы. Алгоритмы. Язык. Киев, 1991.

10. Хомский Н. Аспекты теории синтаксиса. М., 1972.

11. Мельчук И.А. Опыт теории лингвистических моделей "Смысл-текст ". М, 1999.

12. Мельчук И.А. Русский язык в модели "Смысл-текст ". М.-Вена, 1995.

13. Городецкий Б.Ю. Семантические проблемы построения автоматизированных систем обработки текстовой информации II Вычислительная лингвистика. М., 1976.

14. Виноград Т.А. Программа, понимающая естественный язык. М., 1976.

15. Минский М. Фреймы для представления знаний II Психология машинного зрения. М., 1978.

16. Статистика речи и автоматический анализ текста I Отв. ред. Пиотровский Р.Г. Л., 1980.

17. Сэцуо Осуга Обработка знаний. М., 1989.

18. Городецкий Б.Ю. Компьютерная лингвистика: моделирование языкового общения II Новое в зарубежной лингвистике. Вып. 24. М., 1989.

19. Васильев В.В. Компьютерное понимание текстов. М., 1988.

20. Дудко А.Л. Язык представления знаний со встроенной интерпретацией. М., 1991.

21. Иомдин Л. Автоматическая обработка текста на естественном языке: модель согласования. М., 1990.

22. Корхов А.В. Метод построения вопросно-ответной системы с использованием математической формализации русского языка // Труды XXXII научной конференции факультета ПМ-ПУ СПбГУ. СПб., 2001.

23. Боярский К.К., Каневский Г.В., Лезин А.И., Попова А.И. Формализация знаний в гуманитарных исследованиях II Экономико-математическиеисследования: математические модели и информационные технологии, СПбНЦ РАН, 2000, с. 248-264.

24. Лезин Г.В., Боярский К.К., Каневский Е.А., Попова А.И. Программирование концептуальной обработки текстов II Информационные технологии в гуманитарных и общественных науках. Вып. 3. СПб, 1996, с. 1927.

25. Тузов В.А. Компьютерная лингвистика (опыт построения компьютерных словарей). В печати (изд-во СПбГУ).

26. Тузов В.А. Языки представления знаний. С.-Петербург, изд-во СПбГУ, 1990.

27. Каневский Е.А. Методы классификации текста // Труды Международного семинара Диалог-98 по компьютерной лингвистике и ее приложениям. Том 2. Казань, 1998, с. 488-497.

28. Лезин Г.В., Боярский К.К., Каневский Е.А., Попова А.И. Анализ текстов: представление и обработка концептуальной информации II Труды международного семинара Диалог-97 по компьютерной лингвистике и ее приложениям. Ясная Поляна, 1997, с. 170-174.

29. Боброва А.В. Грамматика русского языка. М., 1999.

30. Рубашкин В.Ш. Представление и анализ смысла в интеллектуальных информационных системах. М., 1989.

31. Сидоров Г.О., Гельбух А.Ф. К вопросу установления и разрешения скрытой анафоры // Труды Международного семинара Диалог-99 по компьютерной лингвистике и ее приложениям. Том 2. Таруса, 1999, с. 288-297.

32. Карпова Г.Д., Пирогова Ю.К., Кобзарева Т.Ю., Микаэлян Е.В. Компьютерный синтаксический анализ: описание моделей и направлений разработок II Итоги науки и техники. Серия "Вычислительные науки". Том 6. М, 1991.

33. Лезин Г.В., Мамедниязова Н.С. О представлении семантики концептуальных моделей в базах знаний II Труды Международного семинара Диалог-2000 по компьютерной лингвистике и ее приложениям. Том 2. Протвино, 2000, с. 235-242.

34. Каневский Е.А., Клименко Е.Н., Тузов В.А. Об одном подходе к классификации прилагательных // Труды Международного семинара Диалог-2000 по компьютерной лингвистике и ее приложениям. Том 2. Протвино, 2000, с. 162-167.

35. Ермаков А.Е., Плешко В.В. Ассоциативная модель смысла текста в прикладных задачах компьютерного анализа полнотекстовых документов II Труды международного конгресса «Русский язык: исторические судьбы и современность». М., МГУ, 2001.

36. Ермаков А.Е., Плешко В.В. Ассоциативная семантическая сеть: статистическая модель восприятия и порождения текста II Труды Международного семинара Диалог-2001 по компьютерной лингвистике и ее приложениям. Том 2. Аксаково, 2001.

37. Скрэгг Г. Семантические сети как модели памяти II Новое в зарубежной лингвистике. Вып. 12. М., 1983.

38. Елашкина А.В., Разумов A.M., Русин А.О. Экспертная информационно-поисковая система, основанная на семантической сети II Труды международной конференции «Информационные системы и технологии». М., 2000.

39. Guha R.V., Lenat D.B., Pittman К., Pratt D., Shepherd M. Cyc: A Midterm Report II Communications of the ACM 33 , no. 8, 1990.

40. Lenat D. В., Guha R.V. Building Large Knowledge Based Systems. Reading, Massachusetts: Addison Wesley, 1990.

41. Lenat D. B. Cyc: A Large-Scale Investment in Knowledge Infrastructure II Communications of the ACM 38, no. 11,1995.