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

На правах рукописи

Крайванова Варвара. Андреевна

МОДЕЛИРОВАНИЕ АДАПТИВНОГО ЛОГИЧЕСКОГО АНАЛИЗА В ПРОЦЕССЕ ЧЕЛОВЕКО-МАШИННОГО ВЗАИМОДЕЙСТВИЯ НА ЕСТЕСТВЕННОМ ЯЗЫКЕ

Специальность 05.13.18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических паук

Барнаул 2010

1 1 ФЕВ 2010

003491669

Работа выполнена на кафедре прикладной математики факультета информационных технологий ГОУ ВПО «Алтайский государственный технический университет им. И.И. Ползунова».

Научный руководитель -- кандидат физико-математических наук,

доцент Крючкова Елена Николаевна

Официальные оппоненты - доктор физико-математических наук,

профессор Алгазин Геннадий Иванович

доктор технических паук,

доцент Тузовский Анатолий Федорович

Ведущая организация

Институт систем информатики имени А.П. Ершова СО РАН

Защита состоится 26 февраля 2010 г. в 11 час. 00 мин. на заседании диссертационного совета Д 212.005.04 при ГОУ ВПО «Алтайский государственный университет» по адресу: 656049, г. Барнаул, пр. Ленина, 61.

С диссертацией можно ознакомиться в библиотеке ГОУ ВПО «Алтайский государственный упиверситег».

Автореферат разослан января 2010 г.

Ученый секретарь

диссертационного совета,

доктор физико-математических наук.

профессор

С.А. Безиосюк

Общая характеристика работы

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

Актуальность темы. Во многих прикладных областях применения компьютерных технологий взаимодействие с компьютером на естественном языке было бы наиболее эффективным. Примерами таких областей служат:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Апробация. Основные положения и результаты работы апробированы на 13 конференциях: III Всероссийская научно-техническая конференция студентов, аспирантов и молодых ученых «Наука и молодежь» (Барнаул, 2006, 2007, 2008, 2009); IV Всероссийская научно-практическая конференция «Технологии Microsoft в теории и практике программирования» (Новосибирск, 2007, 2008); Всероссийская научно-техническая конференция студентов, аспирантов и молодых ученых «Научная сессия ТУСУР - 2008» (Томск, 2008); Международная научно-практическая конференция «Перспективные технологии искусственного интеллекта» (Пенза, 2008); VII Всероссийская научно-практическая конференция студентов, аспирантов и молодых ученых «Молодежь и современные информационные технологии» (Томск, 2009); VI Всероссийская научно-практическая конференция «Технологии Microsoft в теории

4

и практике программирования» (Томск, 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. Логико-графовая имитационная динамическая модель адаптивного логического анализа в процессе человеко-машинного взаимодействия на естественном языке.'

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

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

5

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

Класс анализируемой текстовой информации ограничен советами и описаниями ситуаций. При этом предполагается, что ситуация или совет описывается одним предложением - фразой.

Модель состоит из следующих элементов:

• лексикон как множество известных в модели слов;

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

• представление команд системы управления;

• механизм анализа фраз.

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

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

Из множества W выделим множество N понятий естественного языка. Нечеткое отношение обобщения Gen : W х N —* [0,1] определяет степень уверенности модели в том, что некоторое понятие р £ N обобщает слово w 6 W.

Нечеткое отношение синонимичности Syn : W х W —* [0..1] определяет степень уверенности системы в том, что некоторое слово wa € W является синонимом к слову w¡¡ 6 W.

Отношения обобщения и синонимичности в общем случае несимметричны. В диссертации приведен подробный анализ свойств введенных отношений.

Для дальнейшей иллюстрации будем рассматривать приведенный ниже начальный лексикон.

W = {НАПИСАТЬ, НАБРАТЬ, НАПЕЧАТАТЬ, 'ТЕКСТОВЫЙ ДОКУМЕНТ", СТАТЬЯ, ПИСЬМО, ЗАПУСТИТЬ, БЛОКНОТ, ПРОИГРЫВАТЕЛЬ, ПРОГРАММА, ВКЛЮЧИТЬ, ПРИБОР, ПОМЕЩЕНИЕ, ТЕМНО, СВЕТИЛЬНИК, ЧАЙНИК, КОМНАТА, КУХНЯ}

• Gen(CTATbH,"ТЕКСТОВЫЙ ДОКУМЕНТ") = 1;

• Gen(nHCbMO,"ТЕКСТОВЫЙ ДОКУМЕНТ") = 1;

• Сеп(БЛОКНОТ,ПРОГРАММА) = 1;

. Сеп(СВЕТИЛЬНИК,ПРИБОР) = 1;

• Gen(KOMHATA, ПОМЕЩЕНИЕ) = 1;

• Сеп(КУХНЯ,КОМНАТА) = 1;

• Syn(HAnE4ATATb, НАБРАТЬ) = 1;

6

• Syn(HABPATb,НАПЕЧАТАТЬ) = 1.

Все прочие отношения равны нулю. Все новые для модели слова также добавляются в лексикон.

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

Формально, фразу на естественном языке определим как функциональную форму, в которой в качестве функциональных символов выступают слова лексикона W:

• w € W - любое слово из лексикона модели является фразой;

• ^ф - отрицание фразы является фразой;

• w([r! : фг], [гг : Ф2], -\гп Фп]),п > 0, <¡í>¡ - подчиненная фраза, r¿ - тип аргумента, w 6 W - слово с перечисленными в скобках подчиненными фразами.

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

Пусть Reí - конечное множество типов аргументов модели. Фактически, это типы возможных в языке подчинительных отношений.

Функциональную форму фразы ф удобно изобразить в виде дерева, вершины которого помечены словами w е W, а ребра - типами аргументов г €Е Reí (рис. 1). Корень дерева фразы ф будем обозначать как Root(ф).

Завтра на десерт испечем украшенный кремом и орехами торт.

(ИСПЕЧЬ)

ИСПЕЧЬ( 4-'

[TRGPNT:flECEPT], [OBJ.-TOPT1 (

[PROPERT:y«PACHTbJ (

[AGENT:KPEM], ,--—ч ,-■-v ,—--N

[AGENT:OPEX])), (ДЕСЕРТ) (УКРАСИТЬ) (ЗАВТРА)

[Т1МЕ:ЗАВТРА]) кззп/^^^сшт

( КРЕМ ) (ОРЕХИ)

Рис. 1. Пример построения дерева фразы

Пусть и - узел помеченного дерева фразы. Тогда И^огс^(и) - пометка узла и, Relation(u) - пометка ребра, соединяющего узел и с родительским, Агдз(и) -множество дочерних узлов узла и. НедаИоп(и) - признак отрицания узла и. Получить такое помеченное дерево фразы из предложения на естественном языке можно с помощью тривиальных преобразований графа синтаксических отношений или дерева непосредственной входимости. Эти преобразования подробно описаны в диссертации. Большинство синтаксических анализаторов

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

Команда объекта управления представляется парой:

е = (и, Parameters), где v - функциональная форма, задающая определение команды на естественном языке. Некоторые функциональные символы в v могут быть помечены не словами из W, а параметрами из множества Parameters. Parameters = {р|р = (name;, N(). Ni С N} - множество параметров команды, где пате, - имя параметра, N - множество понятий.

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

В узлы дерева и, помеченные параметром name;, может быть подставлено некоторое дерево ф, такое, что 3п : Gen(Word(Root((j>)),n) > 0,п 6 Лг;.

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

{7, Values) = Unificaticmfy,e). (1)

Результатом унификации являются:

• уровень релевантности 7, который определяет степень уверенности системы в наличии команды.

• множество Values — {{р,, ф{)}, где рг - параметры команды е, ф, -значения параметров. Причем для каждого параметра р, должно существовать единственное значение

Обозначим Value(pi) = ф{.

Задача логического анализа заключается в том, чтобы свести некоторую начальную фразу ф к множеству фраз, определяющих команды и понятных объекту управления. Механизм преобразования фраз описывается конечным множеством правил контекстной замены Rules. Введем три группы правил контекстной замены.

Логическое правило задается следующим образом:

rL = (v <х, Parameters), где una- гипотеза и следствие правила, представленные двумя суперпозициями, некоторые функциональные символы которых, возможно, помечены не словами естественного языка, а параметрами из множества Parameters. Parameters - множество параметров правила, аналогичное множеству параметров команды.

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

ro = {v —> с, Parameters}, где v - словосочетание в функциональной форме, содержащее, возможно, параметры; с - определяемое слово из лексикона W, Parameters - множество параметров.

Заключительное правило представляет собой шаблон команды для объекта управления или фразу-ответ на естественном языке. Заключительное правило задается парой

ГЕ = (¡Л Parameters}, где ь> - функциональная форма, представляющая шаблон команды объекта управления или фразу-ответ на естественном языке.

Цепочка вывода из функциональной формы 6 - это конечная последовательность функциональных форм {фо,ф\, ...фт,), таких, что фо = ф, форма и ф1+1 непосредственно выводима из для 0 < г < п — 1 с помощью некоторого правила Г; € Rules, форма фп получена из формы фп_i с помощью заключительного правила rn е Rules.

На основе введенных определений сформулируем задачу логического анализа фразы ф.

Задача 1: найти множество Еф всех заключительных функциональных форм, выводимых из данной функциональной формы ф в состоянии знаний (If, Rules) с помощью цепочек вывода длины не более Length и с уровнем релевантности не менее 7ц. Очевидно, что при такой постановке задачи множество Еф конечно.

Еф = Цф, (W, Rules), Length, 7о)- (2)

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

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

Rules = {

1. ЗАПУСТИТЬ ($Х) Parameters = {{$Х, "ПРОГРАММА"}};

2. ВКЛЮЧИТЬ ($Х, SY) Parameters = {{$Х, "ПОМЕЩЕНИЕ"}, {SY. "ПРИБОР"}};

3. НАПИСАТЬ ($Х) НАБРАТЬ ($Х) , Parameters = {{$Х, "ТЕКСТОВЫЙ ДОКУМЕНТ"}} ;

4. НАБРАТЬ ($Х) ЗАПУСТИТЬ (БЛОКНОТ), Parameters = {{$Х, "ТЕКСТОВЫЙ ДОКУМЕНТ"}};

5. ТЕМНО ($Х) — ВКЛЮЧИТЬ ($Х, СВЕТИЛЬНИК) Parameters = {{$Х, "ПОМЕЩЕНИЕ"}}.

}

Рассмотрим анализ фразы «Нужно срочно написать статью для журнала». Заметим, что эта фраза не является явной командой объекту управления. Функциональная форма, представляющая фразу: НУЖ-НО(СРОЧНО, ЖУРНАЛ, НАПИСАТЬ(СТАТЬЯ)). Применение правила 3 к функциональной форме: НУЖНО(СРОЧНО, ЖУРНАЛ, НА-БРАТЬ(СТАТЬЯ)). Применение правила 4: НУЖНО(СРОЧНО, ЖУРНАЛ, ЗАПУСТИТЬ(БЛОКНОТ)). Применение заключительного правила 1 дает команду: ЗАПУСТИТЬ(БЛОКНОТ). Таким образом, предложенная модель позволяет описывать принципиально более сложную логику, чем простая интерпретация команд, к примеру, «Включи чайник». Пример показывает, что адекватность результатов логического вывода определяется наполнением множества правил и отношениями на лексиконе и не зависит от используемого языка.

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

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

Схема Template((j)) - это дерево фразы ф без пометок вершин. Для организации хранения гипотез всех правил базы и целевых шаблонов команд предлагается специальная структура данных - дерево схем (ДС). Ребра ДС помечены типами подчинительных синтаксических отношений, возможными между лексемами во фразах на анализируемом языке. Каждый узел может быть связан данным типом отношения не более чем с одним потомком. Таким образом, каждый узел щ ДС однозначно задается упорядоченным набором пометок ребер Ь{щ) вдоль пути от корня дерева к узлу щ. Каждый узел ut содержит список правил, в гипотезе которой существует узел и, такой что L(u) = L(ut).

В диссертации приведены теоретические оценки производительности алгоритмов.

Время выполнения операции унификации функциональной формы ф и гипотезы правила г оценивается следующим образом:

tunification = 0(| фтах | * log2 (| фтах |) * | Гтах |) ). (3)

Теоретическая оценка времени работы ticR ЛВП при анализе функциональной формы ф:

tiCR = 0[(RulesSubmitted * {\ф„шх\ * RulesCount * i[/m/ic„<;m))ie"sift), (4) где

Rules Submitted - максимальное количество применяемых за один шаг

правил;

RulesCount - общее количество правил;

Ismail ~ максимальное количество узлов в суперпозиции из графа вывода;

lrmaxj ~ максимальное количество узлов в правиле из Rules;

Length - ограничение на длину вывода.

Теоретически временная сложность t-rrcR алгоритма ДС оценивается следующей формулой:

tncR — 0((RulesSubmitted* . ,

(|0ma*l * log2{RulesCount) * tUniiicatiBn))Lm3th). W

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

Условия эксперимента (рис. 2): максимальная глубина дерева вывода - 5 шагов; размер текста: 128 предложений. Пунктирными линиями обозначены коридоры значений. Широкой серой линией показан результат аппроксимации результатов квадратичной функцией, что подтверждает теоретические оценки производительности алгоритмов.

Количество правил Количество правил

Рис. 2. Сравнение алгоритмов выбора правила ЛВП и ДС.

Зависимость от количества правил

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

Производительность модели при росте ограничения на максимальную глубину дерева вывода очень быстро падает (рис. 3). Условия эксперимента: база правил - 200 правил, линейный выбор правила.

t, мс

8000

7000 6000 5000 4000 3000 2000 1000 0

^'v.........

-Л..." ..............

4 5

Глубина вывода

— "60 правил ■80 правил

— • -100 правил

120 правил ' 140 правил

— — 160 правил ...... 180 правил

Рис. 3. Зависимость времени работы алгоритма от глубины вывода

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

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

В рассматриваемом контексте решены следующие задачи:

• оптимизация множества правил для уменьшения их количества;

• достраивание множества правил при пополнении лексикона;

• пополнение лексикона новыми словами и достраивание отношений обобщения и синонимичности в процессе логического анализа;

• формирование принципиально новых логических правил.

Модель изначально построена на предположении, что логические и лексические знания неполны. Состояние знаний модели описывается парой {W, Rules), где W - лексикон модели, Rules - множество правил модели.

Оптимизация базы знаний основана на слиянии правил. Пусть Word(r) - множество слов-пометок вершин гипотезы и следствия правила г. Пусть также 3wi 6 Word{r\) : wi ^ Wordfo) и 3w2 6 Wordfa), такое, что если в гипотезе и следствии правила г2 заменить слово W2 на слово ui\, то правила Г\ и будут совпадать. Тогда правила г\ и г2 можно обобщить новым правилом го = (i^o —> Parameter sq), где Parameter sq = Parameters2 U {{name, {mi, »2})}: a 1/0 и сг0 получены из v2 и 02 соответственно заменой пометок вершин и : Word(u) = W2 именем нового параметра пате. Пусть существуют pi = {namei, Ni) £ Parameters 1 и pj = (namef^N-) £ Parameters2,

12

такие, что при замене множества Лг,; на N- правила г\ и гг будут совпадать. Тогда правила г\ и r-i можно обобщить новым правилом гц = (щ —> сто, Parameter so), где Parameterso = (Parameter S2\p'i) И{(пате\, N¡11 N{)}, I/O = i/2, &o ~ ""2- В диссертации доказано, что слияние правил сохраняет уровень адекватности модели.

Достраивание множества правил при пополнении лексикона основано на предположении, что правила из близких предметных областей имеют одинаковую структуру, отличаясь лишь на лексическом уровне.

Тема Т С 1У - это поименованное подмножество слов лексикона, принадлежащих к одной предметной области. Обозначим Name(T) - название темы, представляющее собой некоторое словосочетание. В отличие от отношения обобщения, которое определяет для данного слова понятие на более высоком уровне абстракции, принадлежность к теме фиксирует раздел предметной области, к которой относится слово. Так, например, понятие ЖИВОТНОЕ обобщает слова КОРОВА и СОБАКА, однако слово СОБАКА относится к теме КИНОЛОГИЯ, а слово КОРОВА - к теме РАЗВЕДЕНИЕ КРС.

Рассмотрим механизм перестройки базы правил при пополнении лексикона новой темой.

Для решения поставленной задачи на лексиконе модели вводится отношение ассоциации. Пусть Т и G - некоторые темы. Два слова t 6 Т и д £ G связаны отношением ассоциации t = Association(g), если слово t относится к словосочетанию Name(T) так же, как слово д относится к Name(G). На множествах слов Aj С Г и Ас С G установлено отношение ассоциации Ат ~ Ас, если:

• Vi £ АтВд £ Aq : t = Association(g);

• при замене в произвольной фразе ф всех слов t £ Ат на соответствующие им слова д £ Ас получаемая при этом фраза ф' остается осмысленной при условии, что Vuj £ Т : Эи £ ф : (Word(u) = w) —> (w £ Ay).

Отношение ассоциации строится экспертом в процессе описания лексикона предметной области. На рисунке 4 приведен пример построения такого отношения. Отношением ассоциации могут быть связаны только слова, отнесенные к некоторым темам.

Пусть (Wо, Rulesn) - начальное состояние знаний модели. Рассмотрим изменение множества правил при добавлении в лексикон новой темы TV, связанной отношениями ассоциации с уже имеющимися в лексиконе темами. Для этого введем следующие обозначения:

А^ С Tjv - множество слов и понятий новой темы, связанные отношением ассоциации с другими словами.

AssThemes(Aiv) = {Т\ЗА Q Т : А ~ А^} - множество тем, со словами из которых множество An связано отношениями ассоциации.

Nodesrir) - множество узлов правила г, помеченных словами из темы Т.

Тогда (И^ею, Rulesnew) - новое состояние знаний модели, где

Wnew = W0UTN,

Rulesnew = Ruleso U Rules a-

Rules a ~ множество всех новых правил га — (va о A, Parameter s а). Эти правила получены из уже имевшихся правил г = (v —* a. Parameters) £

( крольчонок у

-фжонокУ

( кролик-)

(крольчиха)-

ЕЖ

С заболевание кролика )-

( ринит ) (лишай ) ( едадля кролика )

ЕЖИХА У

-^ЗАБОЛЕВАНИЕ ЕЖА>

<ЛЯЕВЖ>ЯЙЯ>

(морковь) (капуста)

<НАСЕКОМЫЕ>

( комбикорм для кролика у—^КОМБИКОРМДЛЯ ЕЖАУ

| КОРМИТЬСЯ-] - >| ПИТАТЬСЯ | [ КЛЕТКА ] | БОЛЕТЬ ]| КОРМИТЬ~|

| КЛЕТКА | слова, не отнесенные к темам - - > отношение синонимии

/_„. „—\ глг^^гтг.ггтт —> отношение обобщения

( ТРАВА ) слова, отнесенные к теме «КРОЛИКИ»

' —ассоциация

КмясоУ слова, отнесенные к теме «ЕЖИ»

Рис. 4. Отношение ассоциации

Ruleso, таких, что 3Т 6Е AssThemes(Aff) ■ NodesA(r) / 0и Nodes^(r) = Nodesr{r).

Преобразование осуществляется следующим образом:

• Деревья и а а получены из деревьев и и а соответственно заменой пометок узлов и 6 NodesA(r) на ассоциированные с ними слова Association(Word(u)) из темы 7дг.

• Параметр p¿¡ £ ParametersA совпадает с p¡ е Parameters, если p¡ = (name, N) и jüw € N : w € Л.

• Если для некоторого параметра p¿ = (name, N) € Parameters 3w 6 iV : w e А, то параметр p^j = (name, Na) € ParametersA получен из Pi следующей заменой множества допустимых значений: Na = N\A U

= Association(w),w € ЛГ П Л}.

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

Достраивание отношений Gen и Syn основано на анализе позиции в дереве фразы, на которой встретилось незнакомое слово. Введем следующие обозначения: AssGeno - начальный уровень достоверности предположения о существовании отношения обобщения между словами, AssGen - уровень подтверждения достоверности предположения о существовании отношения обобщения.

Чтобы модифицировать отношение Gen, модель строит предположение о том, что слово, подставляемое в параметр, соответствует данному параметру.

14

Например, модели известно, что завядшие растения нужно поливать, а также что растения - это фиалки и герань:

ЗАВЯНУТЬ ([SUB: $х]) ПОЛИТЬ([ОВЛ:$х]) Parameters = {{$х, {РАСТЕНИЕ} } }

Gen(PACTEHHE, ФИАЛКА) = 1, Gen(PACTEHHE, ГЕРАНЬ) = 1 Модель получает от пользователя фразу «Фикус в спальне совсем завял». ЗАВЯНУТЬ([311В:ФИКУС])

Слово ФИКУС встретилось на месте параметра, описываемого понятием РАСТЕНИЕ, поэтому можно предположить, что ФИКУС обобщается понятием РАСТЕНИЕ. Предположение будет подтверждаться, если слово ФИКУС снова встретится на месте понятия РАСТЕНИЕ, то есть уверенность модели в наличии отношения обобщения между РАСТЕНИЕ и ФИКУС будет расти. Если, несмотря па сделанное предположение, в результате дальнейшего вывода не будет получено ни одной заключительной функциональной формы, то предположение считается неверным, и уровень уверенности модели в наличии отношения снижается.

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

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

Механизм формирования принципиально новых логических правил основан на том, что правило контекстной замены может быть описано фразой на естественном языке. Рассмотрим в качестве объекта управления саму модель. Множество параметров для заключительных правил в этом случае состоит из двух элементов: SHYPOTHESIS (гипотеза найденного правила)« SCONSEQUENCE (следствие найденного правила). В эти параметры могут быть подставлены любые функциональные формы.

Например, правило выбора действия «Для SHYPOTHESIS надо сделать SCONSEQUENCE» задается следующим образом: $CONSEQUENCE([AIM:$HYPOTESIS]) Пример правила-определения синонимичных конструкций: BbITb([SACT:$HYPOTESIS],[FACT:$CONSEQUENCE]) Результатом логического анализа в этом случае являются пары пропозициональных (т.е. не содержащих параметров) функциональных форм {4>kyp, Фот) - Параметрами становятся узлы, помеченные понятиями естественного языка.

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

• правило должно описываться одним предложением;

• при формировании параметров не учитываются синонимы и местоимения.

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

Исходные данные для экспериментов - тексты советов по различным тематикам, взятые из сети Интернет.

Рассмотрены три предметные области:

1. Советы по ведению домашнего хозяйства.

2. Советы по уходу за комнатными растениями.

3. Советы начинающим программистам.

Тексты для каждой предметной области составлены на основе нескольких интернет-сайтов.

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

Качество извлеченных знаний оценивалось по двум параметрам:

• Precision = Relevant/Rauto ~ ТОЧНОСТЬ;

• Recall = Rrücvant/Rexpcrt ~ полнота;

где RexlKrt - количество правил, обнаруженных экспертом; Rauto ~ количество правил, извлеченных автоматической системой; Rreievant ~ количество релевантных правил, извлеченных автоматической системой.

Как видно из рисунка 5, поведение модели на необработанных текстах существенно зависит от текста. Полнота результатов анализа адаптированных

0.9

0.8 I.....

0.7 ■{0.6 4™

0.5 h 0.4 —

0.3 —

0.2 ь 0.1 f-

0 -U-

Точносгь ^ Необработанные ш Адаптированные

0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 О

Полнота ш Необработанные ж Адаптированные

Рис. 5. Точность и полнота

текстов мало зависит от типа текста и составляет в среднем 0, 77, что значительно выше аналогичного показателя для необработанных текстов. Точность анализа адаптированных текстов зависит от сложности текста, но при этом заметно выше точности для необработанных текстов.

Основные результаты

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

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

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

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

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

Публикации автора по теме диссертации

Работы, опубликованные автором в ведущих рецензируемых научных журналах, рекомендованных ВАК Министерства образования и науки Российской Федерации:

1. Крайванова, В.А. Модель естественно-языкового интерфейса для систем управления сложными техническими объектами и оценка эффективности алгоритмов на ее основе / В.А. Крайванова // Управление большими системами. - М.: ИПУ РАН, 2009. - Выпуск 26. - С. 159-179.

Другие работы, опубликованные автором по теме диссертации:

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

3. Крайванова, В.А. Оптимизация алгоритма логического вывода на основе кластеризации базы знаний контекстной замены / В.А. Крайванова, E.H. Крючкова // Наука и молодежь : материалы 3-ей всероссийской научно-технической конференции конференции студентов, аспирантов и молодых ученых. - Барнаул: Изд-во АлтГТУ, 2006. - С. 4-6 (авт. -ОД п.л.).

4. Крайванова, В. А. Автоматизация логического вывода в условиях неполного описания базы знаний / В.А. Крайванова // Технологии Microsoft в теории и практике программирования 2007 : тезисы докладов конференции-конкурса работ студентов, аспирантов и молодых ученых.

- Бердск: Оригинал 2, 2007. - С. 123-125.

5. Крайванова, В.А. Методы обобщения правил логического вывода в процессе обучения системы анализа текстов на естественном языке / В.А. Крайванова // Технологии Microsoft в теории и практике программирования 2008 : тезисы докладов конференции-конкурса работ студентов, аспирантов и молодых ученых. - Бердск: Оригинал 2, 2007.

- С. 139-141.

6. Крайванова, В.А. Алгоритмы обучения базы знаний для системы семантического анализа текстов / В.А. Крайванова, E.H. Крючкова // Наука и молодежь : материалы IV Всероссийской научно-технической конференции студентов, аспирантов и молодых ученых. - Барнаул: Изд-во АлтГТУ, 2007. - С. 15-18 (авт. - 0,2 пл.).

7. Крайванова, В.А. Анализ структурных характеристик деревьев в процессе унификации / В.А. Крайванова // Новые информационные технологии в научных исследованиях и образовании: материалы XIII Всероссийской научно-технической конференции студентов. - Рязань: Редакционно-издательский центр РГРТУ, 2008. - С. 104-106.

8. Крайванова, В.А. Реализация концепции типовых решений адаптивного управления интеллектуальными объектами / В.А. Крайванова // Ин-фокоммуникационные технологии в науке, производстве и образовании: материалы третьей международной научно-технической конференции, часть I. - Ставрополь: Изд-во Северо-Кавказского ГТУ, 2008. - С. 21-23.

9. Крайванова, В.А. Система интеллектуального управления сложными адаптирующимися объектами / В.А. Крайванова // Научная сессия ТУСУР-2008 : материалы докладов Всероссийской научно-технической конференции студентов, аспирантов и молодых ученых. Ч. 2. - Томск: В-Спектр, 2008. - С. 78-81.

10. Крайванова, В.А. Алгоритмы ассоциативного обучения интеллектуального робота / В.А. Крайванова, E.H. Крючкова // Высокие технологии, фундаментальные и прикладные исследования, образование. Т. 12 : сборник трудов Пятой международной научно-практической конференции «Исследование, разработка и применение высоких технологий в промышленности». - СПб.: Изд-во Политехи, ун-та, 2008. - С. 92-93 (авт. - 0,1 п.л.).

11. Крайванова, В.А. Методы организации базы знаний системы логического анализа текстов на естественном языке / В.А. Крайванова, E.H. Крючкова // Перспективные технологии искусственного интеллекта : сборник трудов научно-практической конференции. - Пенза: Информационно-издательский центр ПензГУ, 2008. - С. 202-207 (авт. -0,25 п.л.).

12. Крайванова, В.А. Разработка адаптивных логических приложений (AL System) / В.А. Крайванова. Свидетельство об официальной регистрации программы для ЭВМ №2009610579. - 2009.

13. Крайванова, В.А. Концепция адаптивного управления интеллектуальными объектами на основе логического вывода / В.А. Крайванова, E.H. Крючкова // Ползуновский альманах. - 2008, JYM. - С. 26-30 (авт.

- 0,2 п.л.).

14. Крайванова, В.А. Технология AL SYSTEM в человеко-машинных интерфейсах на естественных языках / В.А. Крайванова, E.H. Крючкова // Молодежь и современные информационные технологии : сборник трудов VII Всероссийской научно-практич. конференции студентов, аспирантов и молодых ученых. 4.1. - Томск: Изд-во СПБ Графике, 2009.

- С. 291-293 (авт. - 0,15 п.л.).

15. Крайванова, В.А. Проблема интерпретации результатов логического анализа ЕЯ-фраз в технологии AL-System. / В.А. Крайванова // Технологии Microsoft в теории и практике программирования: сборник трудов VI Всероссийской научно-практической конференции студентов, аспирантов и молодых ученых. - Томск: Изд-во ТПУ, 2009. - С. 158-159.

16. Крайванова, В.А. Механизмы пополнения знаний модели логического вывода на основе лексикона / В.А. Крайванова, E.H. Крючкова // Наука и молодежь: материалы VI Всероссийской научно-технической конференции студентов, аспирантов и молодых ученых. - Барнаул: изд-во АлтГТУ, 2009. - С. 48-50 (авт. - 0,1 п.л.).

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

18. Krayvanova, V. The mathematical model of the semantic analysis of phrases based on the trivial logic / V. Krayvanova, E. Kryuchkova // "Speech and Computer" SPECOM'2009 : proceedings of the 13-th International Conference. - St.Peterburg: SUAI, 2009. - P. 543-546 (авт. - 0,15 п.л.).

19. Крайванова, В.А. Оценка эффективности автоматического и гибридного подхода к извлечению знаний из текстов на ЕЯ на примере модели логического анализа фраз / В.А. Крайванова, E.H. Крючкова // Знания-Онтологии-Теории : материалы всероссийской конференции с международным участием. - Новосибирск: «РИЦ Прайс-Курьер», 2009.

- С. 132-136 (авт. - 0,2 п.л.).

Подписано в печать 20.01.2010. Печать — цифровая. Усл.п.л. 1,16. Тираж 120 экз. Заказ 2010 - 23.

Отпечатано в типографии АлтГТУ, 656038, г.Барнаул, пр-т Ленина, 46 тел.: (8-3852) 36-84-61

Лицензия на полиграфическую деятельность ПЛД №28-35 от 15.07.97 г.

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

Введение

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. Разработаны эффективные алгоритмы реализации математической модели на основе линейного выбора правила и на основе дерева схем. Проведены вычислительные эксперименты по анализу их производительности.

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

Заключение

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.