Содержание к диссертации
Введение
1. Проблема человеко-машинного взаимодействия на естественном языке 11
1.1 Интеллектуальные человеко-машинные интерфейсы 11
1.2 Актуальность проблемы построения ЕЯ-интерфейса 14
1.3 Специфика и современное состояние проблемы 15
1.4 Обзор существующих подходов к анализу ЕЯ 20
1.5 Постановка задачи исследования 22
1.6 Выводы к первой главе 24
2. Математическая модель представления знаний 25
2.1 Структура лексикона 26
2.2 Представление фраз естественного языка 28
2.3 Получение функционального представления фразы из ее синтаксической структуры 32
2.4 Представление команд объекта управления 34
2.5 Выводы к главе 2 39
3. Математическая модель логического анализа 40
3.1 Правила контекстной замены 40
3.2 Механизм логического анализа 42
3.3 Доказательство NP-трудности задачи 44
3.4 Проверка адекватности модели 46
3.5 Выводы к главе 3 47
4. Механизмы адаптивного обучения 48
4.1 Расширение множества правил при пополнении лексикона 49
4.2 Достраивание лексикона 52
4.3 Пополнение базы правил из неструктурированных текстов 55
4.4 Оптимизация базы знаний 56
4.5 Проверка адекватности обучения 58
4.6 Выводы к главе 4 61
5. Проблема темпоральной эффективности 62
5.1 Тривиальный алгоритм реализации модели 62
5.2 Улучшенный механизм выбора правила 63
5.3 Проблема экстенсивных правил 69
5.4 Отсечение по структурным характеристикам дерева фразы . 70
5.5 Предотвращение повторного вывода 72
5.6 Выводы к главе 5 75
Заключение 76
Литература 76
Приложение
- Актуальность проблемы построения ЕЯ-интерфейса
- Получение функционального представления фразы из ее синтаксической структуры
- Доказательство NP-трудности задачи
- Пополнение базы правил из неструктурированных текстов
Введение к работе
Диссертация посвящена созданию и комплексному исследованию имитационной модели человеко-машинного интерфейса на естественном языке. Основными свойствами предлагаемой модели являются адаптивность знаний и высокая вычислительная эффективность алгоритмов, ее реализующих. Синтаксический анализ естественного языка вынесен за пределы модели, что делает полученные в ходе диссертационного исследования результаты в значительной степени независимыми от используемого естественного языка.
Актуальность темы. Во многих прикладных областях применения компьютерных технологий взаимодействие с компьютером на естественном языке было бы наиболее эффективным. Примерами таких областей служат:
интерфейсы к базам данных;
управление «умными домами»;
диалоговые справочные системы;
персональный электронный секретарь.
Следует отметить, что во всех этих областях сейчас используются интерфейсы, требующие от пользователя специальных навыков, строго говоря, неадекватных содержанию предметной области.
В настоящее время не выработано единого подхода к построению естественно-языкового интерфейса, а существующие модели и практические решения зависят от конкретного используемого языка и предметной области. Кроме того, трудоемкая в построении структура знаний препятствует их практическому применению. В связи с этим актуальным является построение имитационной динамической модели адаптивного логического анализа в процессе человеко-машинного взаимодействия на естественном языке.
Целью настоящей работы является разработка фундаментальных основ и применение математического моделирования при построении и комплексном исследовании логико-графовой модели адаптивного логического анализа для решения научных и социально-технических прикладных проблем человеко-машинного взаимодействия на естественном языке. Основными требованиями к модели являются:
достаточная адекватность и вычислительная эффективность для практического использования;
минимальные усилия для построения базы знаний;
возможность адаптации модели под изменяющийся технический объект.
При этом модель должна не только осуществлять буквальный перевод ко
манд с естественного языка на формальный, но и производить логический
анализ фраз, не являющихся командами. Поскольку задача синтаксическо
го разбора фраз естественного языка в значительной степени уже решена,
то входной информацией для модели выбраны результаты синтаксического
анализа.
Для достижения данной цели ставятся следующие задачи:
Анализ специфики проблемы и обзор существующих подходов к созданию естественно-языковых интерфейсов.
Разработка, исследование и обоснование модели представления знаний и механизма логического анализа.
Разработка алгоритмов пополнения знаний модели и анализ их адекватности.
Разработка алгоритмов реализации логического вывода. Обоснование и анализ их производительности на основе вычислительного эксперимента на тестовых примерах.
Методы исследования: теория формальных систем, методы математической логики, методы искусственного интеллекта, методы теории алгоритмов, вычислительный эксперимент.
Научная новизна.
Разработана математическая модель логического анализа в процессе человеко-машинного взаимодействия на естественном языке, независимая от конкретной предметной области и используемого естественного языка, и адекватная при небольшой базе знаний.
Разработаны и обоснованы эффективные механизмы автоматизированного построения и адаптации знаний модели под конкретный технический объект.
Реализованы и протестированы эффективные алгоритмы в виде комплекса программ, предназначенных для решения проблемы человеко-машинного взаимодействия.
Предлагаемый адаптивный подход позволяет преодолеть существующие ограничения (высокая сложность алгоритмов, большая трудоемкость формирования базы знаний) на практическое применение естественно-языковых интерфейсов для социально-технических систем.
Практическая значимость. На основе результатов исследования разработана программная библиотека для реализации адаптивных естественноязыковых интерфейсов AL System. Получено свидетельство об официальной регистрации программы для ЭВМ №2009610579 в Реестре программ для ЭВМ.
Апробация. Основные положения и результаты работы апробированы на 13 конференциях: III Всероссийская научно-техническая конференция студентов, аспирантов и молодых ученых «Наука и молодежь» (Барнаул, 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 авторских листа-На защиту выносятся:
Логико-графовая имитационная динамическая модель адаптивного логического анализа в процессе человеко-машинного взаимодействия на естественном языке.
Алгоритмы реализации математической модели на основе линейного выбора правила и на основе дерева схем, а также результаты анализа их эффективности.
Механизмы автоматического построения и адаптации знаний модели под изменяющиеся внешние условия: построение лексикона, генерация правил контекстной замены на основе ассоциаций, извлечение правил контекстной замены из фраз на естественном языке, а также алгоритмы их реализации.
Структура и объем работы Диссертация состоит из введения, пяти глав, заключения и двух приложений. Диссертация изложена на 111 страницах и содержит 28 рисунков. Список литературы содержит 85 наименований, включая работы автора-Содержание работы
Актуальность проблемы построения ЕЯ-интерфейса
Рассмотрим, почему проблема эффективного человеко-машинного интерфейса, возникшая вместе с появлением вычислительных машин, сохраняет свою остроту и актуальность. Причину этого удачно сформулировал Эндрю вэн Дам [8]: сколь «дружественным» ни был бы интерфейс, всегда существует некоторый люфт между намерениями пользователя и реализацией этих намерений средствами интерфейса. Иными словами, всякий интерфейс предполагает наличие слоя когнитивной обработки, явно или неявно располагающегося между пользователем и компьютерным исполнением заданных им целей. В этом контексте идеальным было бы полное отсутствие интерфейса. Реалистичной альтернативой этому вэн Дам называет идеального слугу, который знает весь тот контекст, в котором происходит работа с пользователем, и тактично исполняет приказания, даже предсказывая некоторые действия без необходимости явного руководства со стороны пользователя. Когда же появляется необходимость в явном направлении действий слуги, то взаимодействие с ним происходит посредством разговора и других форм, принятых в человеческом общении, не отказываясь при этом от таких бесспорно эффективных форм взаимодействия, как выбор нужного пункта меню или ввод информации с клавиатуры.
Задача построения модели взаимодействия с компьютером на естественном человеческом языке (ЕЯ) не нова. Одна из первых успешных работ в этом направлении - программа SHRDLU [85] Терри Винограда. Предметная область программы ограничена миром трехмерных блоков различной формы, а используемый естественный язык - английский. Однако, предложенный Виноградом подход не давал какой-либо общности, и применение его идей к реальным предметным областям оказалось невозможным. Нехватка вычислительной мощности и развитие универсальных человеко-машинных интерфейсов, таких, как мышь, привело к тому, что создание естественно-языкового ЧМИ отошло на второй план. Однако сейчас проблема ЕЯ-интерфейса вновь обретает остроту и актуальность в свете особенностей современных компьютерных систем. Это связано, прежде всего, со следующими тремя факторами:
1. На сегодняшний день сфера применения компьютеров настолько широка и разнообразна, что использовать для всех задач универсальный интерфейс человеко-машинного взаимодействия неэффективно. Каждый вид интерфейса становится все более специализированным. Например, «мышь», с помощью которой удобно манипулировать виртуальными объектами [55], не позволяет эффективно вводить текст.
2. Нарастание сложности технических систем требует от субъекта управления все больших усилий по запоминанию сценариев взаимодействия: комбинаций действий, нажатий кнопок, голосовых команд.
3. Пользователю приходится приспосабливаться к формальному компьютерному интерфейсу.
Как было сказано выше, альтернативой формальным знаковым системам является построение человеко-машинного взаимодействия на основе естественного человеческого языка, но данная задача необычайно сложна с точки зрения формализации [52, 7] и входит в список AI-полных [79] проблем, то есть требует для своего решения полного моделирования интеллекта человека.
Задача синтаксического разбора фраз ЕЯ в значительной степени уже решена [59, 44, 74, 81, 40, 80, 83] для большинства распространенных языков (например, английского [78, 69, 67, 47], испанского и японского [67, 82, 47], французского, норвежского, корейского и греческого [67], турецкого [82], русского [50, 34], чешского [76], румынского [65] и т.д.), чего нельзя сказать о смысловом анализе фраз.
Так как в современных компьютерных системах информация хранится в формализованном виде, то ЕЯ-интерфейсы должны решать следующие основные задачи [4, 54]:
1. Задача перехода, от текстов входных информационных запросов и сообщений на естественном языке к представлению их смысла на формализованном языке (при вводе информации в ЭВМ).
2. Задача перехода от формализованного представления смысла выходных сообщений к его представлению на естественном языке (при выдаче информации человеку).
Одним из прикладных вопросов в этой области является перевод задания, сформулированного в виде фраз ЕЯ, в формальные команды исполнителя-компьютера. Классическим приложением для ЕЯ-интерфейса является построение диалога с экспертными системами [70]. Но вопрос имеет значительно более широкую сферу применения: от построения естественно-языковых интерфейсов к базам данных до сред программирования сверхвысокого уровня.
На практике, как правило, для каждой такой задачи строится своя семантическая модель. Это связано с тем, что глубокий семантический анализ текстов на ЕЯ, независимый от предметной области, находится за пределами существующих методологий [1, 33]. Такие модели сложны (например, семантическая сеть [5], нейронная сеть 11], байесова сеть [71] алгоритмы Гиисбурга [б], онтологии [46]), так как в каждой из них, как правило, делается попытка моделирования максимального количества аспектов языка (синонимия, и квазисинонимия, антонимия, словообразование, обобщение понятием и проч. [3, 36, 1, 2]). Это приводит к двум основным проблемам на пути практического применения естественно-языкового ЧМИ. Во-первых, чрезвычайная многозначность ЕЯ на вычислительном уровне приводит к комбинаторному взрыву [38, 73, 77, 60], то есть алгоритмы недостаточно эффективны для использования в человеко-машинных интерфейсах. Во-вторых, процесс со- здания баз знаний для таких моделей требует большого труда специалиста по лингвистике.
Получение функционального представления фразы из ее синтаксической структуры
На сегодняшний день существуют два основных подхода к представлению синтаксической информации на ЕЯ [38]: Построение графа зависимостей. Построение системы синтаксических составляющих. Для целей логического анализа от синтаксического анализатора требуется, чтобы результат синтаксического анализа был размечен подчинительными отношениями. Из этих пометок формируется множество Rel. Рассмотрим способ преобразования графа зависимостей и системы составляющих в функциональное представление. Существует множество модификаций определения графа зависимостей, в зависимости от конкретной решаемой задачи. Классическое определение графа зависимостей ([38]) не предполагает разметки синтаксическими отношениями.
Приведем наиболее общее определение графа зависимостей, учитывающего подчинительные отношения [3]. Определение 2.5 Граф зависимостей (X, — ) - это граф, в котором X - множество слов некоторой фразы ф, — - размеченное бинарное отношение синтаксического подчинения. Такой граф является ациклическим, но в общем случае не является деревом. Пусть и - вершина графа, полустепень захода в которую больше 1, Childs(u) = {(v,t)\u — v,t Є Rel}, Parents(u) — {{v,t)\v — ut Є Rel, t-ТИП связи между и и v. Выполним следующее преобразование: для каждой вершины vi Є Parents создадим вершину щ, помеченную тем же словом, что и и, такую, что Childs(ui) = Childs(u), Parents(ui) {{vi,ti}}, U- тип связи между и и vi. Так как граф зависимостей ациклический, то количество таких преобразований конечно. После выполнения всех возможных таких преобразований полустепень захода во всех вершинах графа не будет превышать единицы, то есть граф будет являться лесом. Рассмотрим множество Roots вершин графа с полустепеныо захода, равной нулю.
Для каждой такой вершины г Є Roots сформируем дерево достижимых из нее вершин. Полученное множество деревьев - это представление графа зависимостей в виде функционального дерева фразы, используемого в описываемой модели. Заметим, что некоторые вершины графа зависимостей могут входить в функциональное представление несколько раз. Перейдем к рассмотрению системы синтаксических составляющих. Определение 2.6 Система синтаксических составляющих представляет собой бинарное дерево помеченное дерево, обладающее следующим свойством. Пусть и - узел системы синтаксических составляющих, а uieft и uright - его левый и правый потомки соответственно. Тогда: где Label (u) - пометка узла, H— операция конкатенации строк. Корень дерева составляющих помечен целым предложением, листья - отдельными словами из предложения. Ребра дерева составляющих помечены типами подчинительных отношений. Обозначим связь узла и с родительским как Relation(u). Пусть Parent(u) - родительский узел для узла и. Чтобы преобразовать дерево составляющих в функциональную форму, проделаем следующую операцию. 1. Листья дерева составляющих являются функциональными формами. 2. Для каждого узла и, который помечен более чем одним словом, а его аргументы Argsiu) помечены отдельными словами: Если существует множество узлов Vmax С Args(u) такое, что УУтах Є Vmax Priority(Relation(vmax)) = max (Priority(Relation(v))), то vGArgs(u) Args(Parent(u)) = (Args(Parent(u)) U Vmax)\{u}, Vvmax Є VmaxArgs(vmax) = (Args(vmax) U Args(u))\Vmax. Если приоритеты Priority (Relation(v)) для всех v Є Args(u) рав ны, то Args(Parent(u)) — (Args(Parent(u)) U (Args(u))){u}. 3. Повторять пункт 2 до тех пор, пока корень дерева не будет помечен отдельным словом. Построим представление команд объекта управления в виде функциональных форм. Будем считать, что объект управления может выполнять конечный набор операций, или команд к(рі,Р2, Рп) Є К, где рі,Р2, Рп набор параметров [22]. В формальной системе параметр pi операции к однозначно идентифицируется парой (г,), где і - номер параметра, t - формальный тип параметра. Пусть D(pi) - множество допустимых значений параметра pi. Определение 2.7 Назовем семантическим типом SemType(pi) параметра pi операции к, набор (K,i,t). Операции и допустимые значения параметров представляются словами формального языка. Рассмотрим два возможных подхода к преобразованию операций в функциональные формы, описанные в п. 2.2.
Доказательство NP-трудности задачи
Для проверки адекватности модели был проведен эксперимент, заключающийся в следующем. Выбран гипотетический робот с фиксированной функциональностью (домашнее хозяйство) из 11 команд. Для модели человеко-машинного интерфейса робота составлена база знаний (50 правил). Составлен набор S из ситуаций, на которых модель предлагает выполнить команды. Ни одна ситуация из S не содержала прямой команды роботу. Множество предлагаемых моделью команд обозначим Cmodei(S). В первой части эксперимента независимым экспертам (15 человек) было предложено назвать свои команды для каждой ситуации из набора S. Множество команд, предложенных экспертами Cexpert(S). Эксперты разошлись во мнении относительно некоторых ситуаций. Пусть So _ множество ситуаций, где мнения экспертов относительно применяемых команд совпали. Точность и полнота результатов, получаемых моделью, оценивались по следующим формулам: Результаты эксперимента показали, что Precisionm{S) 0,81 и Recallm{S) « 0,83. При этом Precisionm(So) « 0, 96 и Recallm(So) 0,95, то есть адекватность модели очень высока, и возможные ошибки связаны с предпочтениями пользователей. Во второй части эксперимента эксперты сами предложили набор Se ситуаций, в которых можно применить команды робота.
При этом Precisionm(Se) 0,85 и Recallm(Sc) « 0,38, то есть точность результатов модели осталась примерно на том же уровне, а полнота значительно упала. Таким образом требуются механизмы, позволяющие адаптировать знания модели под конкретного пользователя и повышать адекватность модели. 1. Предложен механизм перевода фраз ЕЯ в конструкции формального языка на основе логического анализа. 2. Предложена модель логических знаний в виде правил контекстной замены. 3. Сформулирована задача логического анализа и доказана се NP-трудность. 4. Разработан алгоритм проверки адекватности модели. 5. Проведен эксперимент, показавший высокую адекватность модели при достаточном количестве знаний. 6. Проанализированы причины падения адекватности модели. Главным следствием вышесказанного является необходимость построения механизм динамического пополнения базы знаний. Важным свойством интеллектуальных моделей является обучаемость, способность сохранять свою адекватность в изменяющихся внешних условиях. В современных условиях развития информационных технологий это особенно актуально, так как нарастание сложности технических систем требует от субъекта управления все больших усилий [84]. Рассмотрим внешние для модели факторы, изменение которых ведет к снижению адекватности модели.
Функциональность объекта управления может активно изменяться и усложняться. Этот фактор не должен приводить к усложнению модели управления. Объектом управления может пользоваться несколько субъектов управления, кроме того, язык каждого субъекта изменяется со временем. Количественный рост знаний (см. п.5.2) модели снижает ее темпоральную эффективность, а значит, требуются механизмы самоорганизации и оптимизации знаний. Чтобы адаптироваться под изменившиеся внешние условия, модель должна быть дополнена механизмом получения информации об изменении и модификации имеющихся знаний. Возможными источниками информации об изменениях внешних условий для модели являются [25]: модификация знаний экспертом по знаниям; фразы на ЕЯ, поступающие в модель для анализа. Знания модели представляют собой двухуровневую структуру: лексикон W и множество правил Rules [28]. В рассматриваемом контексте можно сформулировать следующие задачи. пополнение лексикона новыми словами и достраивание отношений обобщения и синонимичности в процессе логического анализа; достраивание множества правил при пополнении лексикона; формирование принципиально новых логических правил; оптимизация множества правил. Построение множества W и отношений Syn и Gen вручную - менее трудоемкая задача, чем построение множества правил Rules. Рассмотрим возможности модификации множества правил на основе изменений, внесенных в лексикон экспертом по знаниям [26]. Логические знания близких предметных областей имеют схожее внутреннее строение. Правила имеют одинаковую структуру, отличаясь лишь па лексическом уровне. Определение 4.1 Тема Т С. W - это поименованное подмножество слов лексикона, принадлежащих к одной предметной области. Обозначим Name(T) - название темы, представляющее собой некоторое словосочетание. В отличие от отношения обобщения, которое определяет для данного слова понятие на более высоком уровне абстракции, принадлежность к теме фиксирует раздел предметной области, к которой относится слово. Так, например, понятие животное обобщает слова корова и собака, однако слово собака относится к теме кинология, а слово КОРОВА -к теме разведение КРС.
Пополнение базы правил из неструктурированных текстов
Исходные данные для экспериментов - тексты советов по различным тематикам, взятые из сети Интернет. Рассмотрены три предметные области: 1. советы по ведению домашнего хозяйства; 2. советы по уходу за комнатными растениями; 3. советы начинающим программистам. Тексты для каждой предметной области составлены на основе нескольких сайтов. В первой предметной области правила сформулированы наиболее четко. Тексты третьей предметной области фактически не содержат четко сформулированных правил. В связи с особенностями представления информации в Интернет исходные тексты прошли предварительную техническую подготовку, которая позволяет избежать ошибок на этапе синтаксического анализа. Это удаление нетекстовых объектов (рисунков, таблиц) и исправление орфографических и синтаксических ошибок. Авторские формулировки полностью сохранены. Под необработанными текстами ниже подразумевается текст, прошедший предварительную техническую подготовку. Роль человека в гибридной человеко-машинной системе извлечения знаний для предложенной модели логического анализа заключается в адаптации необработанного текста. Это устранение местоимений, упрощение формулировок, выделение неявных определений в отдельные предложения.
При адаптации текста фразы, не содержащие правил, сохранялись в тексте, чтобы смоделировать поведение модели в процессе эксплуатации. Для оценки результатов извлечения знаний введем обозначения. Rexperi - количество правил, обнаруженных экспертом. Учитываются только правила, полностью содержащиеся в одном предложении, например, «Чтобы сервировочные ножи блестели, их нужно почистить» - это правило, а такая конструкция: «Для той же цели подойдет разбавленный настой чая» - нет. Rauto - количество правил, извлеченных автоматической системой. Rreievant - количество релевантных правил, извлеченных автоматической системой. Качество извлеченных знаний оценивалось по двум параметрам: Precision = Rreievant/Rauto ТОЧНОСТЬ; Recall = Rreievant/Rexpert полнота; Как видно из рисунка 4.4, поведение модели на необработанных текстах существенно зависит от текста. Полнота результатов анализа адаптированных текстов мало зависит от типа текста и составляет в среднем 0, 77, что значительно выше аналогичного показателя для необработанных текстов. Точность анализа адаптированных текстов зависит от сложности текста, но при этом заметно выше точности для необработанных текстов. важным количественным Показателем В Эксперименте является Rreievant - количество полученных релевантных .правил [29]. 1
Предложен механизм адаптивного достраивания лексического уровня модели в процессе логического анализа. 2. Разработан способ ассоциативного расширения множества правил при пополнении лексикона новой темой. 3. Разработан и обоснован алгоритм адаптивного пополнения знаний модели на основе самоприменения. 4.
Предложена методика слияния правил для более компактного представления знаний. Рассмотренные механизмы позволяют пополнять ту часть знаний модели, которая содержит в себе слова только естественного языка. Для пополнения формальной части знаний, если таковая имеется (см. раздел 2.4), более эффективным является пополнение традиционными способами. Как показано в 3.3, Задача 1 является NP-трудной. Практическое применение модели требует построения достаточно эффективного по временным характеристикам алгоритма. В этой главе приведены результаты вычислительных экспериментов, оценивающие темпоральные характеристики модели в зависимости от различных параметров и эффективность разработанных оптимизирующих эвристик.
В вычислительных экспериментах измерялось только «чистое» время работы системы, не включающее время перевода ЕЯ-фраз в функциональные формы. Поведение системы значительно зависит от конкретного содержания предложений. Это связано с наличием экстенсивных правил (подробнее см.5.3). Для более объективной оценки времени работы системы каждая точка графика получается как среднее значение времени работы нескольких тестов. В качестве входного текста для каждого из тестов использовалась случайная выборка предложений требуемого размера.
