Формалізоване проектування природно-мовних діалогових комп'ютерних систем

Размещено на http://www.allbest.ru/

ВІННИЦЬКИЙ ДЕРЖАВНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ

УДК 658.512.011.56:519.87

Формалізоване проектування природно-мовних діалогових комп'ютерних систем

Спеціальність 01.05.02 - "Математичне моделювання та обчислювальні методи"

Автореферат

дисертації на здобуття наукового ступеня

кандидата технічних наук

Комісаренко Дмитро Юрійович

Вінниця 2001

Дисертацією є рукопис.

Робота виконана у Вінницькому державному технічному університеті Міністерства освіти і науки України.

Захист відбудеться 25 травня 2001 р. о 12 годині на засіданні спеціалізованої вченої ради Д 05.052.01 у Вінницькому державному технічному університеті за адресою: 21021, м. Вінниця, Хмельницьке шосе, 95.

З дисертацією можна ознайомитись у бібліотеці Вінницького державного технічного університету за адресою: 21021, м. Вінниця, Хмельницьке шосе, 95.

Автореферат розісланий 24 квітня 2001 р.

Вчений секретар спеціалізованої вченої ради Захарченко С.М.

АННОТАЦИЯ

Комисаренко Д.Ю. Формализованное проектирование естественно-языковых диалоговых компьютерных систем. - Рукопись.

Эффективность взаимодействия человека с компьютерной системой в значительной степени определяется тем, насколько удобным для пользователя является интерфейс системы. Именно поэтому большое внимание уделяется принципам и методам построения интерфейса. На протяжении последних десятилетий наиболее распространенным был графический интерфейс, построенный по известному принципу "What you see is what you get". С развитием вычислительной техники стало возможным использование других способов общения между человеком и компьютером, которые могут поднять их взаимодействие на качественно новый уровень. Наиболее важным из этих способов является реализации естественно-языкового диалога. При условии использования естественного языка значительно уменьшается время, необходимое на ознакомление пользователя с системой, увеличивается эффективность взаимодействия и т.д.

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

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

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

В связи с этим создание систем интерпретации естественно-языковых команд вызывает некоторые трудности, связанные с синхронизацией систем задания и интерпретации множества естественно-языковых фраз, которые воспринимаются системой.

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

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

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

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

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

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

АНОТАЦІЯ

Комісаренко Д.Ю. Формалізоване проектування природно-мовних діалогових комп'ютерних систем. - Рукопис.

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

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

Ключові слова: природна мова, командний інтерфейс, діалоговий інтерфейс, контекстно-вільна граматика, граматичний розбір, логіко-граматичний формалізм

ANNOTATION

Komisarenko D.Y. Formalized design of the natural language dialog computer systems. - Manuscript.

In this dissertation the model of interaction between the systems of recognition and interpretation of a natural language is proposed. It allows to combine the processes of definition of the input language of the system and its interpretation. A new approach to the natural language phrases intepretation based on the ismorphismus of Kleene algebra and finite state automaton algebra is proposed as well. Besides the net approach to the natural language commands interpretation was developed. This approach allows to define an input language by any context-free grammar. A new approach to the natural language dialog systems is suggested, that includes logical grammatical formalism and non-classical logic, so-called optional logic.

The theoretical part of this investigation and the development environment can be used for the natural language command and dialog interfaces development.

Key words: natural language, command interface, dialog interface, context-free grammar, parsing, logic-grammatical formalism.

інтерфейс комп'ютерний мова

1. ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність. Останні досягнення в галузі розпізнавання мови актуалізували дослідження, пов'язані з теорією побудови природно-мовних інтерфейсів спілкування людини з комп'ютерними системами.

Створення природно-мовних інтерфейсів пов'язане з двома основними проблемами. Перша - розпізнавання мови, тобто перетворення звукової інформації у текст. Друга - проблема розуміння природно-мовних запитів або команд. Остання проблема є найменш дослідженою і найбільш актуальною.

Цій проблемі приділяють велику увагу як виробники програмного та апаратного забезпечення комп'ютерних та інформаційних систем, так і провідні наукові заклади. Проте не всі аспекти цієї проблематики досліджено та впроваджено. Перш за все, інтерпретація природно-мовних команд не пов'язана з описом множини команд, що є необхідним для системи розпізнавання мови. В зв'язку з цим створення систем інтерпретації природно-мовних команд викликає певні труднощі, пов'язані з синхронізацією систем задання та інтерпретації множини природно-мовних фраз, що сприймаються системою.

Задача діалогової взаємодії людини з комп'ютером також повністю не розв'язана. Саме цей факт зумовив вибір теми дослідження.

Зв'язок роботи з науковими програмами, планами, темами. Вибраний напрямок досліджень відповідає напрямку досліджень за науковою держбюджетною роботою "Розробка алгоритмічних засад і програмних засобів моделювання інформаційних систем" (№ держреєстрації 0197U012883), яка виконувалась згідно координаційного плану науково-дослідних робіт, затвердженого наказом Міністерства освіти України, у Вінницькому державному технічному університеті протягом 1997-1999 та науковою держбюджетною роботою "Розробка математичних моделей та алгоритмізація сучасних задач моделювання вимірювальних інформаційних систем (№ держреєстрації 0100U002939), яка виконується згідно тематичного плану науково-дослідних робіт ВДТУ, затвердженого Міністерством освіти і науки України.

Об'єктом дослідження є процес природно-мовної діалогової взаємодії між користувачем та комп'ютерною системою. Предмет дослідження - методи моделювання природно-мовного інерфейсу. Методи дослідження - методи теорії формальних граматик і побудови компіляторів для реалізації мережевого підходу до інтерпретації природно-мовних команд, теорії скінченних автоматів для інтерпретації фраз регулярної контекстно-вільної граматики.

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

Задачі дослідження:

1. Проведення аналітичного огляду і аналіз досягнень в галузі створення природно-мовних інтерфейсів.

2. Розробка підходу до взаємодії між системами розпізнавання та інтерпретації природної мови, що дозволяє інтегрувати процеси розпізнавання та розуміння природної мови.

3. Розробка математичного апарату інтерпретації природно-мовних фраз для регулярних мов (що базується на алгебраїчному підході Кліні).

4. Розробка мережевої моделі інтерпретації природно-мовних фраз.

5. Розробка логіко-граматичних моделей конструювання діалога користувача з комп'ютерною системою.

6. Розробка середовища проектування природно-мовних інтерфейсів людини з комп'ютером.

7. Розробка природно-мовного інтерфейса для роботи з системами електронної пошти.

Наукова новизна отриманих результатів:

1. Створена нова модель взаємодії між системами розпізнавання та інтерпретації природної мови, що дозволяє сумістити процеси задання вхідної мови системи та її інтерпретації.

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

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

4. Запропоновано новий підхід до проектування діалогових природно-мовних систем, логіко-граматичний формалізм та некласична логіка, а саме опціональна логіка.

Практична цінність отриманих результатів:

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

2. Запропоновано алгоритми парсування контекстно-вільних формальних граматик, що базуються на ізоморфізмі алгебри Кліні та алгебри скінченних автоматів та мережевих моделях формальних граматик.

3. Створено програмне забезпечення для тестування моделей природно-мовного командного та діалогових інтерфейсів.

4. Розроблені алгоритми генерації програмного коду і природно-мовних відповідей системи в процесі діалога та логіко-граматичний формалізм, що орієнтований на створення діалогових систем, впроваджені та використовуються у ряді програмних продуктів фірм КМС (Україна) та Lernout&Hauspie (Бельгія) для реалізації природно-мовного інтерфейсу для Windows-програм.

Впровадження результатів підтверджується відповідними актами.

Особистий внесок здобувача.

Здобувачу належать такі ідеї та розробки: розробка нового підходу до взаємодії систем розпізнавання та інтерпретації природно-мовних команд, інтерпретації фраз природної мови за допомогою алгебраїчного підходу Кліні, суміщення систем опису та інтерпретації природно-мовних команд, системи компіляції та парсування природно-мовних команд, системи проектування діалогової взаємодії між користувачем та системою, які містять всі алгоритми і методики, та застосування цих алгоритмів до реалізації природно-мовних систем для популярних Windows-програм.

Апробація результатів дисертації.

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

1) на другій конференції соросівських вчителів (Київ, 1996);

2) на 5-й Міжнародній науково-технічній конференції "Контроль і управління в складних системах" (КУСС) (Вінниця, 1999);

3) на 4-й Міжнародній науково-технічній конференції "Контроль і управління в технічних системах" (КУТС) (Вінниця, 1997);

4) на 3-й Міжнародній науково-технічній конференції "Контроль і управління в технічних системах" (КУТС) (Вінниця, 1998);

5) на форумі "Электроника и молодежь в XXI веке" (Харків, 1997);

6) на шести науково-практичних конференціях професорсько-викладацького складу, співробітників та студентів ВДТУ з участю інженерно-технічних працівників підприємств міста Вінниці та області (Вінниція, 1995, 1996, 1997, 1998, 1999, 2000).

Публікації.

Результати дисертації опубліковано в 4-х статтях в наукових журналах, що визнаються ВАК, в 5-ти збірках тез та матеріалів конференцій і семінарів.

Обсяг і структура дисертації. Дисертаційна робота складається з вступу, 5 розділів, загальних висновків, списка використаних літературних джерел і додатку. Загальний обсяг дисертації 134 сторінки, з яких основний зміст викладено на 116 сторінках друкованого тексту та містить 68 рисунків. Список використаних джерел складається зі 121 найменування.

2. ОСНОВНИЙ ЗМІСТ РОБОТИ

У вступі розглянуто актуальність проблеми досліджень, зазначено зв'язок роботи з науковим програмами, темами. Обгрунтовано мету та задачі досліджень. Наведено характеристику наукової новизни та практичного значення одержаних результатів, а також описано їх апробацію, публікації та впровадження.

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

На основі аналізу стану розв'язання проблеми створення природно-мовних командних та діалогових систем можна сформулювати такі задачі, що повинні бути розв'язані у цьому дослідженні:

- розробити новий підхід до взаємодії між системами розпізнавання та інтерпретації природної мови;

- розробити математичний апарат інтерпретації природно-мовних фраз, що базується на алгебраїчному підході Кліні;

- розробити логіко-граматичні моделі конструювання діалогу користувача з комп'ютерною системою;

- розробити середовище проектування природно-мовних інтерфейсів людини з комп'ютером;

- розробити природно-мовний інтерфейс для роботи з системами електронної пошти.

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

Запропоновано вдосконалену схему природно-мовного командного інтерфейсу (рис. 1).

Рис. 1 Схема природно-мовного інтерфейсу, що пропонується

Схема, що наведена вище, має такі переваги:

1) дозволяє використовувати будь-яку систему розпізнавання мови, що має можливість задання множини фраз у вигляді контекстно-вільної формальної граматики;

2) не має необхідності окремо розробляти систему інтерпретації фреймового подання природно-мовної фрази у вихідну мову, оскільки механізм інтерпретації фраз задається граматикою транслюючого типу.

В розділі також описано мережевий підхід до моделювання природно-мовного командного інтерфейсу. Цей підхід дозволяє сумістити задання вхідної мови довільною контекстно-вільною граматикою та її інтерпретацію.

Цей підхід будує певний граф за відповідною контекстно-вільною граматикою. Розроблені алгоритми, які дозволяють визначити, чи належить деяка фраза мові, що описується контекстно-вільною граматикою та, якщо фраза цій мові належить, сформувати відповідну її інтерпретацію. Ці алгоритми здійснюють пошук на графі, що відповідає контекстно-вільній граматиці. Фраза належить чи не належить граматиці визначається тим, чи можливо провести шлях від вершини, що відповідає цільовому нетерміналу граматики, до вершини, що помічена знаком „!".Іншими словами, множина шляхів із вершини, що відповідає цільовому нетерміналу, у фіктивну вершину „!" визначає множину фраз мови.

Нехай дана граматика Draw Object:

<goal>: Draw <color> <object>;

<color>: blue;

<color>: red;

<object>: square;

<object>: circle;

Зобразимо цю граматику у вигляді такої схеми:

Рис. 2 Схема граматики Draw Object

Граматика, що тут розглядається, задає мову з чотирьох фраз.

Якщо вдається побудувати шлях у цьому графі (рис. 2.3), що починається у вершині <goal>, послідовно проходить через усі термінали даної фрази і закінчується у вершині, то ця фраза належить мові.

На рисунку пунктирною лінією зображено шлях для фрази: Draw blue circle.

Ця фраза належить мові, що аналізується. Для фрази ж Draw blue red такий шлях побудувати не вдається. Отже, ця фраза мові не належить.

У розділі також розглядається підхід до інтерпретації природно-мовних команд, що базується на ізоморфізмі алгебри Кліні та алгебри скінченних автоматів. Цей підхід дозволяє по зображенню граматики в BNF формі отримати вираз в алгебрі Кліні, після чого транслювати цей вираз в польску нотацію. Далі в процесі сканування польського запису виразу Кліні конструюється необхідний автомат. Автомат, що ми отримали, не тільки розпізнає фрази данної граматики, але й транслює ці фрази у відповідні командні рядки.

Проілюструємо це на прикладі. Нехай граматика, що задає множину фраз, має такий вигляд:

<Start> : make {Act1} <Object> {Act2} <Color> {Act3};

<Object> : line;

<Object> : character;

<Color> : red;

<Color> : blue,

де Act1, Act2, Act3 - символи вихідної (інтерпретаційної) граматики.

Приклад граматики задає такі фрази:

make line red,

make line blue,

make character red,

make character blue.

Записуємо вираз граматики в алгебрі Кліні:

make{Act1}*(line+character){Act2}*(red+blue){Act3}

Перетворимо вираз алгебри Кліні в польський запис:

make{Act1} line character + {Act2} red blue + {Act3} * *

За цим польським записом будуємо автомати:

+ S0 S1

Line S1

Character S1

3 Ok {Act2}

+ S0 S1

Red S1

Blue S1

3 Ok {Act3}

Знаходимо композицію попередніх автоматів:

S0 S1 S2

Line S1

Character S1

Red {Act2}S2

Blue {Act2 S2

3 {Act3}Ok

У результаті маємо:

S0 S1 S2 S3

Make S1

Line {Act1} S2

Character {Act1} S2

Red {Act2} S3

Blue {Act2} S3

3 {Act3} Ok

До переваг такого підходу можна віднести ефективність за часом роботи, можливість реалізувати необхідну діагностику розпізнаних фраз.

Недоліком такого підходу є деяка обмеженість сфери його застосування. Він може бути використаний лише для випадку регулярних граматик.

В третьому розділі розглянуто підхід до проектування природно-мовного діалогового інтерфейсу, опціональну логіку, алгоритми генерації вихідної мови, природно-мовних відповідей системи та ходу діалогу.

Нехай задана деяка множина Х та її власна підмножина X0 (X0 М X). Множину Х будемо називати множиною задач, а її підмножину X0 - множиною тривіальних задач. Будемо вважати також, що на множині Х визначене відображення a зі значеннями у множині підмножин множини Х: .

Це відображення будемо називати відображенням переходу до підзадач або просто переходом до підзадач.

Нехай х О Х, тоді множину a (х) будемо називати множиною підзадач задачі х, а її елементи - підзадачами задачі х.

Будемо вимагати, щоб відображення a задовольняло наведеним нижче аксіомам.

Аксіома 1. Тривіальні задачі не мають підзадач: Ж.

Будь-яка нетривіальна задача має хоча б одну підзадачу: Ж.

Аксіома 2.

В множині Х будемо вважати виділеним елемент , який будемо називати цільовою задачею. Цільова задача не є підзадачею жодної задачі з Х:

~ .

Аксіома 3.

Будь-яка задача, яка не є цільовою, є підзадачею деякої задачі:

.

Аксіома 4 (антисиметричності).

Якщо х є підзадачею y, то у не може бути підзадачею х:

у О a(х) Ю х a(у).

Означення.

Нехай

Тоді послідовність: будемо називати ланцюгом підзадач задачі , чи просто ланцюгом підзадач.

Будемо вимагати також виконання такої аксіоми.

Аксіома 5.

Нехай - довільний ланцюг підзадач.

Тоді усі підзадачі цього ланцюга різні, тобто: .

На множині задач Х визначимо два відображення: відображення визначення статусу задачі і відображення визначення стану задачі.

Нехай завдана двоелементна множина: S = {n, un}і відображення s : X ® S.

Це відображення будемо називати визначенням статуса задачі.

Якщо s(х) = n, то задачу х будемо називати необхідною (neсessary) для розв'язання цільової задачі . Якщо ж s(х) = un, то задачу х будемо називати не необхідною (чи опціональною) для розв'язання цілоьвої задачі .

Розглянемо також множину T = {t, i, f} і відображення t : Х ® Т.

Це відображення будемо називати відображенням визначення стану задачі, а множину Т будемо називати множиною логічних значень або множиною станів.

Якщо t(х) = t, то задачу х будемо вважати розв'язаною в позитивному сенсі (true-стан).

Якщо t(х) = f, то задачу будемо вважати розв'язаною в негативному сенсі (false-стан). Елементи множини Т будемо називати значеннями вірності задач.

Нижче наведені правила виконання операцій кон'юкції та диз'юнкції в тризначній логіці, які знадобляться нам в подальшому.

Аксіома 6.

Мають місце співвідношення:

Щ.1. t Щ t = t Ъ. 1. t Ъ t = t

Щ. 2. t Щ f = f Ъ. 2. t Ъ f = t

Щ. 3. t Щ i = I Ъ. 3. t Ъ i = t

Щ. 4. f Щ f =f Ъ. 4. f Ъ f = f

Щ. 5. f Щ i = f Ъ. 5. f Ъ i = i

Щ. 6. i Щ i = i Ъ. 6. i Ъ i = i

Крім того, ми постулюємо комутативність цих операцій. Ці операції природним чином розповсюджуються на довільну кількість операндів.

Сформулюємо деякі додаткові аксіоми.

Аксіома 7.

Нехай х ОХ, a(х) = {x1, …, xk} та s(хi) = n для i = 1, …, k, тоді

Щ Щ ... Щ .

Аксіома 8.

Нехай х ОХ, a(х) = {x1, …, xk} та s(хi) = un для i = 1, …, k, тоді

Ъ Ъ ... Ъ .

Аксіома 9.

Нехай х ОХ, a(х) = {x1, …, xm, xm+1, …, xk } та s(хi) = n для i = 1, …, m, s(хi) = un для i = m+1, …, k,

тоді

Щ Щ ... Щ .

Дамо тепер означення цільової структури.

Означення.

Кортеж B = <X, X0, {n, un}, {t, i, f}, ,

де Х - множина, яка називається множиною задач,

Х0 - власне підмножина Х, яка називається множиною тривіальних задач,

{u, un} - множина значень статуса задач,

{t, i, f} - множина станів задач,

- елемент Х, який називається цільовою задачею,

a - відображення множини Х в множину його підмножин, який називається переходом до підзадач,

t - відображення Х в {t, i, f},

s - відображення Х в {n, un}.

Будемо називати цільовою структурою, якщо виконуються наведені вище аксіоми 1 - 10.

Для цільових структур зі скінченною множиною задач має місце лема, яка називається лемою обриву ланцюгів.

Лема 1.

Якщо В - цільова структура зі скінченною множиною задач Х, то довільний ланцюг підзадач обривається на деякій тривіальній задачі. Іншими словами, довільний ланцюг задач скінченний, а останнім елементом цього ланцюга є тривіальна задача.

Теорема 1.

Система аксіом 1 -10 несуперечлива.

Будемо розглядати змінні двох типів S1, S2, …, Sn, …, які називаються змінними типу "статус задачі" чи просто S-змінними та змінні P1, P2, …, Pn, …, які називаються змінними типу "стан задачі" чи просто P-змінними.

Атомарним виразом (чи А-виразом) будемо називати вираз виду (u, v), де

u- чи s-змінна, чи одна з констант n, un;

v- чи р-змінна, чи одна з констант t, i, f.

Комплексним виразом (чи С-виразом) будемо називати вираз виду (A1, …, An), де A1, …, An - атомарні вирази.

Наприклад, С-виразами є вирази: ((s1, p1)), ((s1, p1), (n, p2), (un, f)).

Тепер введемо поняття передформул опціональної логіки. Передформули визначаються рекурсивно такими правилами:

А-вираз є передформулою;

Заміна р-змінної в будь-якій передформулі на С-вираз також є передформулою.

Наприклад, передформулами є вирази (s1, p1), (s1, ((s2, p2), (s3, p3))), (s1, ((s2, ((s4, p4), (s5, p5), (s3, p3)).

Введемо поняття формули опціональної логіки. Формула опціональної логіки визначається рекурсивно такими правилами:

Вираз виду t F, де t - спеціальний символ, який називається оператором стану, а F - передформула, є формулою. Нехай формула F містить рядок: t ( (u1, E1), …, (un, En) ), де ui, i = 1, …, n- чи s-змінна, чи одна з констант n, un, а Ei, i = 1, …, u- чи p-змінна, чи передформули, тоді заміна в формулі F наведеного вище виразу на вираз: t ( t(u1, E1), t(u2, E2), …, t(un, En) ) також є формулою опціональної логіки.

Константи t, i, f є формулами.

Вирази виду:

V1 l1 V2l2 … lk-1 Vk,

де V1, ..., Vk - константи t, i, f, чи р - змінна, а l1, …, lk-1 - чи символ Щ, чи символ Ъ, є формулами.

Наприклад, формулами опціональної логіки є вирази: t ( s1, ((s2,p2), (s3, p3)) ), t ( s1, t ((s2,p2), (s3, p3)) ), t ( s1, t (t (s2,p2), t (s3, p3)) ), p1 Щ t Щ p2 Ъ f Ъ i Ъ pn.

Введемо поняття еквівалентних формул опціональної логіки. Еквівалентність формул F1 і F2 будемо позначати F1 = F2.

Постулюємо еквівалентність деяких формул.

Аксіома 10.

t(s, i) = i; t(s, f) = f; t(s, t) = t;

t(n, i) = i; t(n, f) = f; t(n, t) = t;

t(un, i) = i; t(un, f) = f; t(n, t) = t;

Аксіома 11.

Нехай в формулу F входить вираз виду t( (u1, E1), …, (un, En) ).

Замінимо в формулі F цей вираз на виразt( t (u1, E1), …, t (u1, En) ).

Отриману формулу F1 будемо вважати еквівалентною формулі F.

Аксіома 12.

t( t (n, u1), …, t (n, uk) ) = u1 Щ … Щ uk, де ui, i = 1, …, k чи одна з констант t, i, f, чи р-змінна.

Аксіома 13.

t( t (un, u1), …, t (un, uk) ) = u1 Ъ … Ъ uk, де ui, i = 1, …, k чи одна з констант t, i, f, чи р-змінна.

Аксіома 14.

t( t (u, u1), …, t (n, um), t (un, um+1), …, t (un, uk) ) = t(u1) Щ … Щ t(um), де ui, i = 1, …, k чи одна з констант t, i, f, чи р-змінна.

Аксіома 15.

Нехай в формули F і F1 входять одні й тіж s-змінні та р-змінні. Замінимо кожну s-змінну в F і F1 на одну й ту ж константу з множини {n, un}, а кожну р-змінну на одну й ту ж константу з множини {t, i, f}. Отримані таким чином формули позначимо через та .

Якщо виявиться, що і чи і чи і то будемо вважати, що формули і еквівалентні.

Аксіома 16.

Легко бачити, що співвідношення еквівалентності формул рефлексивно симетричне і транзитивне.

Дамо, нарешті, визначення опціональної логіки.

Визначення.

Кортеж < F, = >, де F - множина формул, а = - відношення еквівалентності формул. будемо називати опціональною логікою, якщо виконуються аксіоми 10 - 17.

Мають місце такі теореми:

Теорема 2.

Якщо формула опціональної логіки не містить s-змінних і р-змінних, то вона еквівалентна одній з формул: t, i, f.

Теорема 3.

Система аксіом опціональной логіки 10 - 16 несуперечлива.

Нехай В - цільова структура. Поставимо у відповідність усякій задачі хi цільової структури змінну рi опціональної логіки. Нехай ця відповідність встановлюється оператором l, тобто для будь-якої задачі х, р = l(х).

Нехай В - цільова структура.

Тоді будь-якій задачі х О Х можна поставити у відповідність формулу опціональної логіки F, яка містить тільки змінні асоційовані з тривіальними задачами цільової структури.

При цьому, якщо t (х) = С, де С О {t, i, f}, то формула F еквівалентно логіці еквівалентна С.

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

Аналізуючи логічну структуру, діалоговий engine (DE) задає питання користувачу, аналізує його, змінює зовнішній світ і повідомляє інформацію про його стан.

Мета діалогу - розв'язання деякої задачі.

Саме в процесі розв'язання задачі і виникає діалог із користувачем.

Справа в тому, що користувач може не знати, яка інформація необхідна для розв'язання задачі, не цілком розуміти стан зовнішнього світу. Крім того, інформація, повідомлена користувачем, може трактуватися неоднозначно або бути суперечливою. У таких і подібних випадках Dialog Manager аналізує стан логічної структури і генерує необхідне питання користувачу. Коли інформація, що повідомлена користувачем, непротирічна і достатня для вирішення задачі, Dialog Manager починає її розв'язання.

Логічна структура - це дерево підзадач. Кожна підзадача зображається вершиною (вузлом) у цьому дереві. Ці вершини (підзадачі) позначаються символом n (necessary - обов'язкова вершина) або символом un (unnecessary - необов'язкова вершина)

Позначка n означає, що підзадача є необхідною для материнської задачі. Іншими словами її розв'язання є обов'язковим для розв'язання материнської задачі.

Позначка un означає, що підзадача не є необхідною для материнської задачі. Тобто її розв'язання не є обов'язковим для розв'язання материнської задачі.

Відзначимо відразу, що будь-яка вершина дерева (підзадача) у кожний момент часу може знаходитися в одному із трьох станів:

t (true) - задача розв'язана позитивно;

f (false) - задача розв'язана негативно;

i (indefinite) - невизначений стан, тобто підзадача ще не розв'язувалася.

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

GSF (Grammar Source File) - це транслюючі граматики. Іншими словами за допомогою таких граматик розв'язується задача трансляції фраз вхідної мови у фрази вихідної мови.

Це можна зобразити так:

Рис. 3 Схема трансляції природно-мовних команд

Таким чином, будь-яке правило граматики містить не тільки конструкції вхідної мови, але також може містити конструкції вихідної мови.

Для моделювання природно-мовних командних систем розроблено програму GCompiler, що дозволяє проводити синтаксичний аналіз коду формальної граматики згідно з запропонованим синтаксисом.

Крім синтаксичного аналізу тексту формальної граматики, програма реалізує таку функціональність:

отримання двійкового подання формальної граматики;

отримання текстового запису формальної граматики у різних форматах (Microsoft SAPI, L&H KNLP, L&H ASR 1600 тощо);

отримання репрезентативної множини фраз, що належать мові, яка задана формальною граматикою;

парсування фраз; цей модуль дозволяє визначити, чи належить деяка фраза множині фраз мови, заданої формальною граматикою, та отримати її інтерпретацію, якщо фраза належить мові; крім того можливе отримання протоколу алгоритму парсування;

пакетне тестування формальної граматики дозволяє перевіряти довільну множину фраз на приналежність мові та отримати їх інтерпретацію;

перевірка належності термінальних символів граматики словнику системи розпізнавання;

побудова дерева команд, що належать мові.

З використанням цього інструментарію були розроблені природно-мовні інтерфейси для Windows-програм. Зокрема, для програм пакету Microsft Office 95/97/2000, а саме, Microsoft Word, Excel, PowerPoint та Outlook. Ці природно-мовні інтерфейси підтримують майже всю функціональність цих програмних продуктів відповідними природно-мовними командами.

Крім того, були розроблені природно-мовні інтерфейси для ряду програм, орієнтованих на глобальну комп'ютерну мережу Internet. Серед них: Microsoft Outlook Express, Microsoft Chat, Eudora Pro, Netscape Communicator тощо.

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

Інструментарій для проектування природно-мовних діалогових систем складається з трьох основних модулей: VDCompiler, GCompiler та VDSimulator.

VDCompiler призначений для компіляції текстових файлів, що містять описання логічної структури та формальних граматик, у двійкове подання, необхідне для функціонування діалогової системи. Ця програма використовує GCompiler, що описаний вище, для перетворення формальних граматик у двійкове подання.

VDSimulator призначений для тестування моделі діалогового інтерфейсу.

Це програмне забезпечення використовувалось для реалізації діалогового інтерфейсу для програми Microsoft Outlook. Ця система реалізує функціональність Microsoft Outlook у діалоговому режимі.

ВИСНОВКИ

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

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

Запропоновано нову схему побудови системи, що реалізує природно-мовний інтерфейс. Ця схема, що суміщує процеси задання вхідної мови системи та її інтерпретації, дозволяє значно спростити проектування природно-мовних інтерфейсів.

Розроблено математичний апарат інтерпретації природно-мовних фраз, що базується на алгебраїчному підході Кліні. Цей апарат дозволяє розробляти природно-мовні системи, вхідна мова яких може бути задана регулярною формальною граматикою. Вказано основні вимоги до вхідної мови системи та можливості генерації вихідної мови з орієнтацією на різні типи інтерпретаторів.

Розроблені логіко-граматичні моделі конструювання діалога користувача з комп'ютерною системою. Запропонована некласична логіка - "опціональна логіка" - для конструювання діалогової взаємодії людини з комп'ютерною системою. Розроблені алгоритми, що генерують програмний код для взаємодії з зовнішнім світом та природно-мовні відповіді системи в процесі діалога з користувачем.

Створено середовище проектування природно-мовних інтерфейсів людини з комп'ютером.

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

СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Винничук И. П., Грузман М. З., Комисаренко Д. Ю., Усач А. Г. Технология "понимания" программными системами естественной речи // Математические машины и системы. - 1999. - № 1. - С. 71-76.

2. Квєтний Р. Н., Комісаренко Д. Ю. Використання транслюючих граматик для побудови природно-мовного інтерфейсу // Вісник ВПІ. - 1999. - №5. - С. 10-12.

3. Квєтний Р. Н., Комісаренко Д. Ю. Автоматна модель природно-мовного інтерфейсу в комп'ютерних системах // Вісник ВПІ. - 1999. - №2. - С. 5-7.

4. Комісаренко Д. Ю. Розробка голосового інтерфейсу на базі візард-діалогів // Вісник ВПІ. - №3. - 1998. - С. 9-12.

5. Вінничук І. П., Гордійчук О. Л., Комісаренко Д. Ю. Візуальні засоби автоматизації проектування // Праці 4-ої Міжнародної конф. "Контроль і управління в технічних системах" (КУТС-97). - Т.3. - Вінниця: УНІВЕРСУМ-Вінниця, 1997. - С. 58-64.

6. Кветный Р. Н., Комисаренко Д. Ю., Грузман Д. М. Принципы создания человеко-машинного интерфейса для слепых пользователей // Сборник материалов международного симпозиума "Наука и предпринимательство" - Львов: изд-во Львовского университета, 1997. - С. 217-226

7. Комисаренко Д. Ю. Использование визард-диалогов для построения речевого интерфейса // Сборник тезисов докладов Всероссийской молодежной научной конференции. - М.: Изд. ЛАТМЭС. - 1998. - С. 12-14.

8. Комисаренко Д. Ю. Специализированный интерфейс для пользователей с дефектами зрения // Сборник тезисов докладов 1-го международного молодежного форума "Электроника и молодежь в XXI веке". - Харьков: Наука, 1997. - С. 187-188.

9. Цейтлин Г.Е., Грузман Д.М., Комисаренко Д.Ю., Пилипенко В.В., Терзян Т.К., Юсим Г.В. Алгоритмика - ОКНО В МИР. Система озвученного взаимодействия инвалидов с компьютером.//II Конференцiя Соросiвських учителiв - 1996 -С. 213-222.

Размещено на Allbest.ru

...