Моделирование адаптивного логического анализа в процессе человеко-машинного взаимодействия на естественном языке тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Крайванова, Варвара Андреевна

• Крайванова, Варвара Андреевна
• кандидат физико-математических наук
• 2010

Оглавление диссертации кандидат физико-математических наук Крайванова, Варвара Андреевна

Список используемых сокращений

Введение

1. Проблема человеко-машинного взаимодействия на естественном языке

1.1 Интеллектуальные человеко-машинные интерфейсы.

1.2 Актуальность проблемы построения ЕЯ-интерфейса.

1.3 Специфика и современное состояние проблемы.

1.4 Обзор существующих подходов к анализу ЕЯ

1.5 Постановка задачи исследования.

1.6 Выводы к первой главе.

2. Математическая модель представления знаний

2.1 Структура лексикона.

2.2 Представление фраз естественного языка.

2.3 Получение функционального представления фразы из ее синтаксической структуры.

2.4 Представление команд объекта управления.

2.5 Выводы к главе

3. Математическая модель логического анализа

3.1 Правила контекстной замены.

3.2 Механизм логического анализа.

3.3 Доказательство NP-трудности задачи.

3.4 Проверка адекватности модели.

3.5 Выводы к главе

4. Механизмы адаптивного обучения

4.1 Расширение множества правил при пополнении лексикона.

4.2 Достраивание лексикона.

4.3 Пополнение базы правил из неструктурированных текстов.

4.4 Оптимизация базы знаний

4.5 Проверка адекватности обучения.

4.6 Выводы к главе

5. Проблема темпоральной эффективности

5.1 Тривиальный алгоритм реализации модели.

5.2 Улучшенный механизм выбора правила.

5.3 Проблема экстенсивных правил

5.4 Отсечение по структурным характеристикам дерева фразы

5.5 Предотвращение повторного вывода.

5.6 Выводы к главе

Введение диссертации (часть автореферата) на тему «Моделирование адаптивного логического анализа в процессе человеко-машинного взаимодействия на естественном языке»

Актуальность темы

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

• интерфейсы к базам данных;

• управление «умными домами»;

• диалоговые справочные системы;

• персональный электронный секретарь.

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

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

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

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

• достаточная адекватность и вычислительная эффективность для практического использования;

• минимальные усилия для построения базы знаний;

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

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

• Анализ специфики проблемы и обзор существующих подходов к созданию естественно-языковых интерфейсов.

• Разработка, исследование и обоснование модели представления знаний и механизма логического анализа.

• Разработка алгоритмов пополнения знаний модели и анализ их адекватности.

• Разработка алгоритмов реализации логического вывода. Обоснование и анализ их производительности на основе вычислительного эксперимента на тестовых примерах.

Методы исследования: теория формальных систем, методы математической логики, методы искусственного интеллекта, методы теории алгоритмов, вычислительный эксперимент.

Научная новизна

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

2. Разработаны и обоснованы эффективные механизмы автоматизированного построения и адаптации знаний модели под конкретный технический объект.

3. Реализованы и протестированы эффективные алгоритмы в виде комплекса программ, предназначенных для решения проблемы человеко-машинного взаимодействия.

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

Практическая значимость

На основе результатов исследования разработана программная библиотека для реализации адаптивных естественно-языковых интерфейсов AL System. Получено свидетельство об официальной регистрации программы для ЭВМ №2009610579 в Реестре программ для ЭВМ.

Апробация

Основные положения и результаты работы апробированы на 13 конференциях:

• Всероссийская научно-техническая конференция студентов, аспирантов и молодых ученых «Наука и молодежь» (Барнаул, 2006, 2007, 2008, 2009).

• IV Всероссийская научно-практическая конференция «Технологии Microsoft в теории и практике программирования» (Новосибирск, 2007, 2008).

• Всероссийская научно-техническая конференция студентов, аспирантов и молодых ученых «Научная сессия ТУСУР - 2008» (Томск, 2008).

• Международная научно-практическая конференция «Перспективные технологии искусственного интеллекта» (Пенза, 2008).

• VII Всероссийская научно-практическая конференция студентов, аспирантов и молодых ученых «Молодежь и современные информационные технологии» (Томск, 2009).

• VI Всероссийская научно-практическая конференция «Технологии Microsoft в теории и практике программирования» (Томск, 2009).

• XII Региональная конференция по математике МАК-2009 (Барнаул, 2009).

• XIII International conference "Speech and computer"(Санкт-Петербург, 2009).

• II Всероссийская конференция с международным участием «Знания-Онтологии-Теории» (Новосибирск, 2009).

Публикации

По теме диссертации опубликовано 19 работ, в том числе 1 статья в журнале из списка ведущих рецензируемых научных журналов, рекомендованных ВАК Министерства образования и науки РФ, 1 свидетельство об официальной регистрации программы для ЭВМ в Реестре программ для ЭВМ, 4 статьи в научных журналах и сборниках работ конференций, 13 тезисов докладов на конференциях. Общий объем публикаций - 24 авторских листа.

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

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

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

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

Структура и объем работы

Диссертация состоит из введения, пяти глав, заключения и двух приложений. Диссертация изложена на 111 страницах и содержит 28 рисунков. Список литературы содержит 85 наименований, включая работы автора.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Крайванова, Варвара Андреевна

Основные результаты диссертационной работы состоят в следующем.

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

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

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

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

Рассмотренный адаптивный подход позволяет преодолеть существующие ограничения на практическое применение ЕЯ-интерфейсов.

Заключение

Список литературы диссертационного исследования кандидат физико-математических наук Крайванова, Варвара Андреевна, 2010 год

1. Апресян Ю.Д., Богуславский И.М., Иомдин Л. Л. Лингвистический процессор для сложных информационных систем.— М.: Наука, 1991.— 256 с.

2. Батура, Т. В. К вопросу об анализе текстов на естественном языке / Т. В. Батура, О. Н. Еркаева, Ф. А. Мурзин // Новые информационные технологии в науке и образовании. — Новосибирск, 2003. — С. 7-58.

3. Батура Т.В., Мурзин Ф.А. Машинно-ориентированные логические методы отображения семантики текста на естественном языке: монография / Институт систем информатики им. А.П. Ершова СО РАН. — Новосибирск: Изд-во НГТУ, 2008. ISBN 978-5-7782-1138-4.- 248 с.

4. Белоногое Г.Г., Калинин Ю.П., Хорошилов А.А. Компьютерная лингвистика и перспективные информационные технологии : теория и практика построения систем автоматической обработки текстовой информации. -М.: Рус. мир. 2004. ISBN: 5-85810-077-9. 246 с.

5. Воронина, И. Е. Программные средства выявления семантического поля слов / И. Е. Воронина, А. А. Кретов, О. С. Титова // Вестник ВГУ, серия: Системный анализ и информационные технологии. — 2008. — № 2,- С. 111-122.

6. Гладкий, А. В. Языки и грамматики. — М.: Наука, 1973.

7. Гэри М., Джонсон Д. Вычислительные машины и труднорешаем ые задачи. — М.: Мир, 1982.

8. Дударь, 3. В. Семантическая нейронная сеть как формальный язык описания и обработки смысла текстов на естественном языке / 3. В. Дударь, Д. Е. Шуклин // Радиоэлектроника и информатика. — Харьков: Изд-во ХТУРЭ, 2000. № 3. - С. 72-76.

9. Жигалов, В. Естественное общение с приложением Электронный ресурс. / В. Жигалов // Открытые системы. — 2001.— № 12.— URL: http://www.osp.ru/text/302/180708.html (дата обращения: 29.12.2009).

10. К взаимодействию компьютера и человека на естественном языке / К. Страндсон, О. Герасименко, Р. Кастсрпалу et al. // Диалог 2008: труды международной конференции. — С. 495-502.

11. Коломойцева, И. А. Функциональная модель медицинского естественноязыкового текста / И. А. Коломойцева // Научные труды Донецкого национального технического университета. Серия Информатика, кибернетика и вычислительная техника. — 2008.

12. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — М.: МЦНМО, 1990.- 960 с.

13. Крайванова, В. А. Методы обобщения правил логического вывода в процессе обучения системы анализа текстов на естественном языке /

14. B. А. Крайванова // Технологии Microsoft в теории и практике программирования 2008 : тезисы докладов конференции-конкурса работ студентов, аспирантов и молодых ученых. — Бердск: Оригинал 2, 2008. —1. C. 139-141.

15. Крайванова, В. А. Вычислительная сложность задачи логического анализа для адаптивно-логической модели естественного языка / В. А. Крайванова // МАК-2009 : материалы двенадцатой конференции по математике. — Барнаул: Изд-во АГУ, 2009. — С. 130-132.

16. Крайванова, В. А. Логический вывод и проблемы отсечения на основе кластеризации базы знаний / В. А. Крайванова, Е. Н. Крючкова // Математическое образование на Алтае МОНА-2005 : труды региональной конференции. — Барнаул, 2005. — С. 56-60.

17. Крайванова, В. А. Концепция адаптивного управления интеллектуальными объектами на основе логического вывода / В. А. Крайванова, Е. Н. Крючкова // Ползуновский альманах. - 2008.— JYQ 4.— С. 2630.

18. Крайванова, В. А. Методы организации базы знаний системы логического анализа текстов на естественном языке / В. А. Крайванова,

19. Е. Н. Крючкова // Перспективные технологии искусственного интеллекта : сборник трудов научно-практической конференции.— Пенза: Информационно-издательский центр ПензГУ, 2008. — С. 202-207.

20. Кузнецов, Н. А. Информационное взаимодействие в технических и живых системах / Н. А. Кузнецов // Информационные процессы. 2001. — Т. 1, № 1.-С. 1-9.

21. Линник Ю.В. Метод наименьших квадратов и основы математико-статистической теории обработки наблюдений.— М.: Физматиздат, 1962.- 360 с.

22. Люгер Д. Ф. Искусственный интеллект: стратегии и методы решения сложных проблем. 4-е издание. — М.: Вильяме, 2003.

23. Мальковский, М. Г. Алгоритм синтаксического анализа, используемый в системе морфо-синтаксического анализа «TREETON» / М. Г. Мальковский, А. С. Старостин // Диалог'2007: труды международной конференции. М.: Изд-во РГГУ, 2007. - С. 516-524.

24. Манин Ю. И. Вычислимое и иевычислимое. — М.: Сов. радио, 1980.

25. Мельчук И.А. Опыт лингвистических моделей «Смысла Текст». — М.: Школа «Языки русской культуры», 1999. — 436 с.

26. Найханова, Л.В., Евдокимова И. С. Методы и алгоритмы трансляции естественно-языковых запросов к базе данных в SQL-запросы: монография. Улан-Удэ: Изд-во ВСГТУ, 2004. - 148 с.

27. Никитин А., Райков П. Вопросно-ответные системы Электронный ресурс.— URL: http://logic.pdmi.ras.ru/ yura/internet/06ia-seminar.ppt (дата обратцения: 29.12.2009).

28. Hooicoe И.М. Морфологическая и синтаксическая обработка текста (модели и программы) Электронный ресурс.— 2003. URL: http://www.aot.ru/docs/Nozhov/msot.pdf (дата обращения: 29.12.2009).

29. Окатьев В.В., Баркалов К.А. Патент №2320005 на изобретение «Способ поиска информации». — 2006.

30. Поспелов, Д. А. Интеллектуальные интерфейсы для ЭВМ новых поколений / Д. А. Поспелов // Электронная вычислительная техника: сборник статей. — М.: Радио и связь, 1989. Вып. 3.— С. 4-20.

31. Розенталь Д.Э., Теленкова М. Словарь лингвистических терминов.— М.: Оникс, 2008.- 624 с.

32. Рубашкин, В. Ш. Семантический компонент в системах понимания текста Электронный ресурс. / В. Ш. Рубашкин // Десятая национальная конференция по искусственному интеллекту с международным участием (КИИ-2006) : труды конференции. Т. 2.—

33. М.: Физматлит, 2006.— URL: http://www.raai.org/resurs/papers/kii-2006/cloklad/Rubashkin.doc (дата обращения: 29.12.2009).

34. Сайт компании Apple Электронный ресурс.— URL: http://apple.com (дата обращения: 29.12.2009).

35. Сайт компании «Сусогр» Электронный ресурс. — 2009. URL: http://www.cyc.com (дата обращения: 29.12.2009).

36. Сайт лаборатории «Speech Technology» в Редмонде корпорации Microsoft Электронный ресурс.— URL: http://research.microsoft.com/en-us/groups/srg/default.aspx (дата обращения: 29.12.2009).

37. Сайт проекта «Nalaps» Электронный ресурс).— 2009. URL: http://nalaps.ru (дата обращения: 29.12.2009).

38. Сайт проекта «Pegasus» Электронный ресурс. — 2009. URL: http://www.pegasus-project.org (дата обращения: 29.12.2009).

39. Сайт рабочей группы "Автоматическая обработка текстов" Электронный ресурс. URL: http://aot.ru (дата обращения: 29.12.2009).

40. Сайт «Российский НИИ искусственного интеллекта» Электронный ре-СУРС1 • — URL: http://artint.ru (дата обращения: 29.12.2009).

41. Самарский А.А., Михайлов А.П. Математическое моделирование: Идеи. Методы. Примеры. 2-е издание, исправл.— М.: Физматлит. 2002. ISBN 5-9221-0120-Х. 320 с.

42. Свами М., Туласимаран К. Графы , сети и алгоритмы. — М.: Мир, 1984.

43. Тельное Ю.Ф. Интеллектуальные информационные системы / Московский международный институт эконометрики, информатики, финансов и права. — М., 2004. 82 с.

44. Тихонов, К. Руками не трогать? Электронный ресурс. / К. Тихонов / / Компьютерра Online. — 2008. — ноябрь. — № 40. — URL: http://offline.computerra.ru/2008/756/378604/ (дата обращения: 29.12.2009).

45. Толпегин, П. В. Информационные технологии анализа русских естественно-языковых текстов, часть 2 / П. В. Толпегин // Информационные технологии. — 2006. — N2 9. — С. 2-7.

46. Тузов, В. Семантический анализ текста на русском языке: функциональная модель предложения / В. Тузов // Экономико-математические исследования: математические модели и информационные технологии. — СПб: ЭМИ РАН., 2003. Вып. 3.~~ С. 30-328.

47. Фомичев, В. А. Формализация структуры основных словарей лингвистической базы данных / В. А. Фомичев // Внедрение ИПИ (CALS)-технологий. 2005. — № 3. — С. 30-38.

48. Циликов, И. С. Моделирование семантики естественных языков Электронный ресурс. / И. С. Циликов // Телематика'2008: материалы конференции. — URL: http://tm.ifmo.ru/tm2008/db/doc/getthes.php?id=8 (дата обращения: 29.12.2009).

49. Чеповский A.M. Неразрешимая проблема компьютерной лингвистики / Чеповский A.M. // Компьютерра. — 2002. — № 30.

50. Annika W&rn. What is an Intelligent Interface? Электронный ресурс.— 1997. URL: http://www.sics.se/annika/papers/intint.html (дата обращения: 29.12.2009).

51. Calacean, M. A Data-Driven Dependency Parser for Romanian / M. Calacean, J. Nivre // Proceedings of TLT-7. 2009. - Pp. 65-76.

52. Chomsky, N. The logical basis of linguistic theory / N. Chomsky // Preprints of papers for ninth international congress of linguistics. — Cambridge: Mass, 1962.

53. Deep linguistic processing with HPSG Электронный ресурс. — 2007. URL: http://www.delph-in.net (дата обращения: 29.12.2009).

54. Forgy, С. "Rete: A Fast Algorithm for the Many Pattern/Many Object Pattern Match Problem / C. Forgy // Artificial Intelligence. — 1982. — № 19. C. 17-37.

55. Grinberg D., Lafferty J., Sleator D. A robust parsing algorithm for link grammars. — Carnegie Mellon University Computer Science technical report CMU-CS-95-125. 1995.

56. Hardy H., Strzalkowski Т., Wu M., Ursu C., Webb N. Biermann A., Inouye R.B., Mckenzie A. Data-Driven Strategies for an Automated Dialogue System Электронный ресурс.— 2004. URL: www.aclweb.org/anthology/P/P04/P04-1010.pdf (дата обращения: 29.12.2009).

57. Horvitz E. Lumiere Project: Bayesian Reasoning for Automated Assistance Электронный ресурс.— 1998. URL: http://research.microsoft.com/en-us/um/People/horvitz/lum.htrn (дата обращения: 29.12.2009).

58. Long B. Natural Language as an Interface Style Электронный ресурс. — 1994. URL: http://www.dgp.toronto.edu/people/byron/papers/nli.html (дата обращения: 29.12.2009).

59. Mooney, R. J. Learning for semantic parsing / R. J. Mooney // Proceedings of the Eighth International Conference on Computational Linguistics and Intelligent Text Processing. Mexico City, Mexico. Springer. — 2007. — Pp. 311-Ц324.

60. Nirenburg S., Raskin V. Ontological Semantics. — Cambridge, MA: MIT Press, 2004.

61. Nivre, J. Pseudo-Projective Dependency Parsing / J. Nivre, J. Nilsson j j Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL). — 2005. Pp. 99-106.

62. Oepen, S. An Overview of Natural Language Understanding Электронный ресурс.— 2007. URL: http://www.delph-in.net/courses/07/nlp/overview.pdf (дата обращения: 29.12.2009).

63. Shahaf, D. Towards a Theory of AI Completeness Электронный pe-СУРС. / D. Shahaf, E. Amir / / 8th International Symposium on Logical Formalizations of Commonsense Reasoning. — 2007. — URL: www.ucl.ac.uk/commonsense07 (дата обращения: 29.12.2009).

64. The Natural Language Processing Laboratory at the University of Pittsburgh Электронный ресурс.— URL: http://nlp.cs.pitt.edu (дата обращения: 29.12.2009).

65. The Stanford Natural Language Processing Group Электронный ресурс. — / URL: http://nlp.stanford.edu (дата обращения: 29.12.2009).

66. Thompson, С. Acquiring Word-Meaning Mappings for Natural Language Interfaces / C. Thompson // Journal of Artificial Intelligence Research. — 2003. Vol. 18. - Pp. 1-44.

67. Uszkoreit, H. New chances for deep linguistic processing / H. Uszkoreit // Proceedings of the 19th International Conference on Computational Linguistics. — Taipei, Taiwan: 2002.

68. Want, R. Comparing autonomic and proactive computing / R. Want, T. Pering, D. Tennenhouse // IBM Systems Journal- 2003,- Vol. 42, no. 1.

69. Winograd T. Understanding Natural Language. — New York: Academic Press, 1972.