ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ
Харківський національний університет радіоелектроніки
Калиниченко Ольга Вікторівна
УДК 004.8
АЛГЕБРА ІДЕЙ ЯК АПАРАТ ФОРМАЛІЗАЦІЇ СЕМАНТИКИ ПРИРОДНОЇ МОВИ В СИСТЕМАХ ШТУЧНОГО ІНТЕЛЕКТУ
05. 13. 23 – Системи та засоби штучного інтелекту
А В Т О Р Е Ф Е Р А Т
дисертації на здобуття наукового ступеня
кандидата технічних наук
Харків 2004
Дисертацією є рукопис.
Робота виконана у Харківському національному університеті радіоелектроніки, Міністерство освіти і науки України.
Науковий керівник: - доктор технічних наук, професор Шабанов-Кушнаренко Сергій Юрійович, Харківський національний університет радіоелектроніки, провідний науковий співробітник кафедри програмного забезпечення ЕОМ.
Офіційні опоненти:–
доктор технічних наук, професор Шаронова Наталія Валеріївна, Національний технічний університет „Харківський політехнічний інститут”, кафедра педагогіки і психології управління соціальними системами;–
доктор технічних наук, професор Асєєв Георгій Георгійович, Харківська державна академія культури, завідувач кафедрою інформаційних технологій.
Провідна установа:
Донецький державний інститут штучного інтелекту, кафедра програмного забезпечення інтелектуальних систем, м. Донецьк.
Захист відбудеться “24” березня 2004 р. о 13.00 годині на засіданні спеціалізованої вченої ради Д 64.052.01 в Харківському національному університеті радіоелектроніки за адресою: 61166, м. Харків, пр. Леніна, 14, тел. (0572) 702-14-51.
З дисертацією можна ознайомитись у бібліотеці Харківського національного університету радіоелектроніки за адресою: 61166, м. Харків, пр. Леніна, 14.
Автореферат розісланий “20” лютого 2004 р.
Вчений секретар
спеціалізованої вченої ради Саєнко В.І.
ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ
Актуальність теми. Суттєвим недоліком штучного інтелекту, що істотно обмежує сферу його практичного застосування, є нездатність обчислювальних машин розуміти людську мову і, як наслідок, неможливість автоматичної обробки сенсу текстів природної мови. Ця проблема актуальна вже понад 50 років. Зусилля вчених усього світу за цей час не дали визначних результатів – про це свідчить недосконалий автоматичний переклад текстів з однієї природної мови на іншу. З аналізу спроб вирішення цієї проблеми випливає, по-перше, що формалізація сенсу природної мови – винятково складна задача, вона, по суті, рівноцінна побудові математичної моделі мислення людини. По-друге, застосовані алгоритмічні методи вивчення виявилися недостатньо ефективними, і виникає нагальна потреба шукати принципово інший підхід.
З іншого боку, на відміну від спроб створення автоматичного перекладача за допомогою алгоритмічних підходів, деякими науковими школами систематично розвивається математичне моделювання механізмів розуміння природної мови. Хоча на цьому шляху ще багато невирішених проблем, але принципових перешкод немає, і вже отримано багато важливих результатів, зокрема розроблено ефективний алгебро-логічний апарат для формального опису сенсу природно-мовних текстів – алгебри скінченних предикатів та предикатних операцій, знайдено результативні методи об’єктивного аналізу сенсу висловлювань природної мови та отримано ряд моделей багатьох семантичних структур.
На цей час вже створено багато конструктивних алгебро-логічних моделей окремих механізмів семантики природної мови. Зараз їх загальний об’єм зробив актуальним задачу наступного рівня – синтезу локальних конструктивних моделей у межах єдиної аксіоматичної теорії, побудованої на принципах суто об’єктивного фізичного вивчення сенсу висловлювань природної мови, – на базі системи аксіом, які можна експериментально перевірити.
Дисертаційна робота являє собою один із перших кроків на шляху розробки аксіоматичної теорії семантики природної мови. Вона присвячена розробці та практичному застосуванню методів формального опису деяких структур природної мови за допомогою алгебри ідей – математичного апарату, побудованого як алгебро-логічний аналог природної мови. Як математична структура алгебра ідей – це алгебра одномісних предикатів, з практичного боку вона охоплює прості оповідальні речення природної мови. Актуальність цієї теми визначається перспективністю застосування отриманих методів для розробки широкого спектру систем спілкування з комп'ютером природною мовою – від автоматизованих систем управління нового покоління до автоматичних перекладачів, що оперують сенсом текстів на природній мові.
Впровадження результатів дисертаційної роботи буде сприяти підвищенню рівня комп'ютерних технологій на Україні. Успішне вивчення механізму мови і його адекватний математичний опис, особливо розробка ефективного методу формального опису сенсу текстів, веде до суттєвого удосконалення систем штучного інтелекту, зокрема систем автоматизації виробництва, комп'ютерного проектування та навчання, експертних систем, підтримки прийняття рішень та ін.
У своїх дослідженнях автор ґрунтувався на роботах М.Ф. Бондаренко, П. Грибомона, Н. Нільсона, С. Осуги, Д.А. Поспєлова, А. Робінсона, А. Тейза, Ю.П. Шабанова-Кушнаренко, Н.В. Шаронової.
Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконувалася на кафедрі програмного забезпечення ЕОМ Харківського національного університету радіоелектроніки згідно з планом науково-технічних робіт Харківського державного університету радіоелектроніки в рамках держбюджетної теми № 105 “Розробка теорії штучного інтелекту на базі дослідження механізмів інтелекту людини і її застосування для проектування систем штучного інтелекту” (№ДР 0100U005436), де автор працювала молодшим науковим співробітником за сумісництвом.
Мета і задачі дослідження. Метою дисертаційної роботи є розробка комплексу алгебро-логічних засобів формалізації інтелектуальної діяльності людини, зокрема семантики текстів природної мови, для розширення можливостей інтелектуального інтерфейсу; реалізація отриманих моделей у вигляді програмного продукту.
Основні задачі дослідження:
? провести аналіз моделей формальної обробки текстів природної мови, що вже існують, та обґрунтувати необхідність розробки системи, яка обробляє природну мову на основі алгебраїчних моделей семантики;
? розробити алгебру ідей, носій якої природно інтерпретується як множина ідей інтелекту (термін “ідея” використовується в широкому та вузькому сенсі. В широкому сенсі під ідеєю розуміється множина суб’єктивних станів інтелекту, а у вузькому – множина думок, які можна сформулювати у вигляді оповідальних речень);
? розробити модифіковану предикатну модель, що дозволяє структурувати задачу формалізації інтелектуальної діяльності;
? розробити формульний опис операцій і відношень в алгебрі ідей;
? розробити методики використання отриманої моделі для математичного опису інтелекту людини;
? розробити методи і алгоритми застосування отриманого формального апарата для опису сенсу текстів – побудова формул алгебри ідей за текстами природної мови;
? створити програмний продукт, в основу якого покладені розроблені алгоритми формалізації сенсу текстів у вигляді формул алгебри ідей.
Об'єктом дослідження є структура семантики текстів природної мови, зокрема простих оповідальних речень.
Предметом дослідження є аксіоматичні алгебро-логічні моделі семантики текстів природної мови.
Методи дослідження засновані на математичному апараті алгебри скінченних предикатів та предикатних операцій, на ідеях і принципах штучного інтелекту, методах формалізації семантики текстів природної мови.
Наукова новизна отриманих результатів.
- Вперше аксіоматично створено алгебру предикатів зі структурою, що побудована за аналогією з логічною структурою семантики простих оповідальних речень. Ця алгебра виконує роль аксіоматичної бази для багатьох існуючих алгебраїчних моделей, побудованих конструктивно, що дозволило перекласти сенс досить великого класу природно-мовних семантичних структур на мову логічних рівнянь.
- Вперше розроблено аксіоматичну модель предиката рівності ідей, доведено необхідність і достатність аксіоматики предиката рівності ідей для однозначної формалізації структури семантики речень. Вперше створена система лінгвістичних експериментів, яка дозволяє однозначно формалізувати семантику простих оповідальних речень. Це дозволило проводити формалізацію семантики мови на об'єктивному, експериментальному рівні методами компараторної ідентифікації.
- Удосконалено стандартну предикатну модель: за допомогою апарату універсальної алгебри розроблено модифіковану предикатну модель, що дозволяє вирішити задачу об’єднання часткових моделей на базі підмножин множин ідей; вирішено задачу конгруентних моделей, що виникає з-за частковості предикату та необхідності його довизначення; за допомогою введеного поняття нормального образу моделі отримана практична процедура, що дозволяє вирішити питання про скорочення неістотних змінних моделі.
Практичне значення отриманих результатів. Розроблені в дисертаційній роботі математичні методи формалізації механізмів інтелектуальної діяльності людини, алгоритми і програмні системи призначені для автоматизованих інформаційних систем із природномовним інтелектуальним інтерфейсом, для логічної підтримки проектування інформаційних структур. Математичні і програмні результати роботи можуть бути використані в системах автоматичної обробки текстової інформації (ефективна підтримка і реалізація баз даних, баз знань, експертних систем, АСУ), САПР нових інформаційних технологій.
Результати, які отримані в ході даної дисертаційної роботи, знайшли своє практичне застосування в інституті фізики високих енергій та ядерної фізики Національного наукового центра “Харківський фізико-технологічний інститут” для прийняття керуючих дій та контролю результатів керування в автоматизованій інформаційно-вимірювальної системі лінійного прискорювача електронів на 2 Гев (ЛУЕ-2 Гев) (акт впровадження від 11.09.2002); у торгівельно-виробничому підприємстві “Європейське торгівельне обладнання” для розробки комп’ютерного дизайнерського комплексу у вигляді програмного керуючого модуля автоматизації праці по розробці, комплектації та розміщенню торгівельного обладнання в службових та офісних приміщеннях (акт впровадження від 23.09.2002); на кафедрі автоматизації та проектування обчислювальної техніки для синтаксичного аналізу прикметників російської мови в системах, реалізованих на кристалі FPGA (акт впровадження від 12.02.2003).
Теоретичні результати дисертації були використані в навчальному процесі на кафедрі Програмного забезпечення ЕОМ ХНУРЕ при підготовці курсів лекцій “Теорія інтелекту” та “Алгебраїчна логіка” для спеціальності “Програмне забезпечення автоматизованих систем” (акт впровадження від 18.05.2002).
Програмне забезпечення, розроблене в дисертації, використовується в курсовому і дипломному проектуванні, у науково-дослідній роботі студентів на кафедрі ПЗ ЕОМ.
Особистий внесок здобувача. Всі результати, представлені в роботі, отримані автором самостійно.
У роботах [1-5], написаних у співавторстві, особисто автором проведена теоретична робота з розвитку алгебро-логічного апарату опису інтелектуальної діяльності людини на базі алгебри ідей. У роботі [1] запропоновано поняття алгебри ідей для формалізації суб'єктивних станів людини, зокрема змісту текстів природної мови, яке дозволило структурувати цю проблему та запропонувати формальні моделі, що виявилися на практиці більш ефективними, ніж існуючі аналоги.
На базі розробленого апарату алгебри ідей – носія алгебри, її операцій та аксіоматики автору вдалося побудувати методи та алгоритми для ефективного моделювання змістовних структур природної мови [2].
Розроблено модифіковану предикатну модель, що дозволяє вирішити практично важливу задачу об'єднання отриманих в експериментах часткових моделей, побудованих на базі підмножин множини змістів текстів [3].
Запропоновано правила побудови формул алгебри ідей за текстами природної мови для предикатів 1-го і 2-го рівнів з використанням кванторів і логічних зв'язків [4, 5].
Апробація результатів дисертації. Основні результати дисертаційної роботи доповідалися й обговорювалися на конференціях: 1) 5-й міжнародний молодіжний форум “Радіоелектроніка і молодь у 21 столітті” (24-26 квітня 2001), 2) 6-й міжнародний молодіжний форум “Радіоелектроніка і молодь у 21 столітті” (15-20 квітня 2002), 3) 8 Міжнародна конференція “Теория и техника передачи, приема и обработки информации” ИИСТ-2002 (г. Туапсе, 2002).
Публікації. Основні результати роботи опубліковані в 8 наукових працях, з них 5 статей, опублікованих у наукових спеціалізованих виданнях, затверджених ВАК України, 3 – тези конференцій.
Структура й обсяг дисертаційної роботи. Дисертаційна робота складається з вступу, п'яти розділів, висновків, списку використаної літератури, одного додатка. Повний обсяг роботи – 156 сторінок. Дисертація містить 9 малюнків, 6 таблиць, 1 додаток на 5 сторінках, список використаної літератури з 107 найменувань на 8 сторінках.
ОСНОВНИЙ ЗМІСТ РОБОТИ
У вступі обґрунтовано актуальність теми, сформульовано основну мету і задачі дослідження, наведено відомості про зв’язки обраного напрямку досліджень із планами організації, де виконана робота. Дана загальна характеристика роботи, сформульовано основні положення, що винесено автором на захист, визначено їх практичну цінність. Наведено дані про використання результатів дисертації в народному господарстві.
Перший розділ присвячено аналізу основних наукових досягнень у галузі алгебро-логічного аналізу та моделювання інтелектуальної діяльності людини.
Проаналізовані дослідження в області систем штучного інтелекту. Проведено класифікацію інтелектуальних систем з точок зору галузі застосування – обробка природної мови, обробка сигналів і розпізнавання образів, машинний зір і обробка зображень, робототехніка й автоматизація виробництва, комп'ютерне проектування, автоматичне програмування і навчання, експертні системи, символьні й алгебраїчні обчислення, докази і логічне програмування, моделювання; по типу розв'язуваних задач – інтерпретація даних, моніторинг, проектування, прогнозування, планування, навчання, керування, підтримка прийняття рішень, діагностика.
Розглянуто різні мови і моделі представлення знань: продукції, семантичні мережі, фрейми, логічне програмування, об’єктно-орієнтовані мови; класифікація існуючих формальних моделей спілкування природною мовою відповідно до використовуваного в них метода: 1) модель “концептуальної залежності”; 2) модель “семантик переваги”; 3) модель семантичних ролей, 4) модель “сенс-текст”. Проведено огляд методів логічної формалізації семантики текстів природної мови.
На основі проведеного аналізу літературних джерел показано, що, незважаючи на великі досягнення в теорії інтелектуальних інформаційних систем, багато задач у цій області ще чекають свого теоретичного і практичного рішення – недостатньо розроблений математичний апарат для формалізації семантики природної мови, немає досить повних і ефективних методів, реалізація яких дозволила б вільне спілкування людини з комп'ютером. У зв'язку з цим у дисертаційній роботі ставляться задачі, зв'язані з математичним моделюванням функціональної структури людського інтелекту, серед яких основною є здатність комп'ютера до спілкування природною мовою.
З математичної точки зору природна мова людини являє собою деяку алгебру, точніше – деякий алгебраїчний апарат у дії, очевидно, одна з різновидів алгебри предикатних операцій. Потрібно довідатися, який саме варіант алгебри предикатних операцій реалізований у природній мові та чи немає в природній мові ще яких-небудь алгебраїчних структур понад це. При побудові такої алгебри хотілося б, щоб її апарат міг бути надалі природно розширений на вивчення не тільки семантики текстів природної мови, але і на будь-які суб'єктивні стани людини – його думки, поняття, відчуття.
Другий розділ присвячено проблемам побудови ефективного математичного апарата для формалізації механізмів інтелекту. Вводиться алгебра ідей, носій якої природно інтерпретується як множина ідей (думок, понять, взагалі – будь-яких суб'єктивних станів людини) інтелекту. Розробляються методи застосування отриманого формального апарата для опису сенсу текстів.
Для формального опису закономірностей інтелектуальної діяльності мовою алгебри кінцевих предикатів для теорії інтелекту вводиться абстрактний еквівалент цієї алгебри - алгебра ідей. Елементи множини – носія алгебри ідей, природним образом інтерпретується як ідеї інтелекту (тобто думки, поняття, узагалі – будь-які суб'єктивні стани людини), а операції алгебри ідей над цими елементами – як дії інтелекту над ідеями.
У ролі прототипу алгебри ідей використовується алгебра одномісних _їчних предикатів першого порядку. Виявляється, що саме алгебра одномісних -їчних предикатів першого порядку приводить до потрібного нам загального визначення алгебри ідей. Абстрактні аналоги більш загальних алгебр скінченних предикатів (багатомісних і довільного порядку) виходять просто деталізацією вихідної алгебри ідей.
Побудову алгебри ідей почнемо з введення її носія – множини всіх ідей. Позначимо символом Sk множину, що складається з 2k різних елементів s0, s1, … s2k-1. Приймаємо множину Sk у ролі носія алгебри ідей розмірності k. Елементи множини Sk називаємо ідеями розмірності k. Прототипами елементів множини Sk для нас служать одномісні k-їчні предикати першого порядку. Число елементів 2k множини Sk обрано з таким розрахунком, щоб воно збігалося з числом всіх одномісних k-їчних предикатів першого порядку. Множину Sk назвемо k-мірним простором ідей.
Введемо бієкцію Ф: SkMk що встановлює взаємно однозначну відповідність між всіма ідеями розмірності k і всіма k-їчними предикатами, заданими на множині Ak. Це завжди можна зробити, оскільки множини Sk і Mk містять однакову кількість елементів. Предикат P=Ф(х) будемо називати предикатом, що відповідає ідеї х, а ідею х=Ф-1(Р)–
ідеєю, що відповідає предикату P.
Розглянемо предикат рівності Dk(P,Q) предикатів Р и Q, заданий на декартовому квадраті множини Mk всіх одномісних k-їчних предикатів першого порядку. Він визначається рівнянням:
Dk (P, Q) = x(P(x)~Q(x)) (2.1)
справедливим для будь-яких P,Q Mk. Предикат Dk ставить у відповідність рівним предикатам P і Q логічну константу 1, нерівним – 0. Рівняння Dk (P, Q) =1 задає відношення рівності P=Q предикатів P,Q Mk. Відношення рівності предикатів можна розглядати як діагональне відношення, задане на декартовому квадраті множини Mk, тобто як множина усіх пар виду (P, P) де P = Mk. У нашому прикладі відношенням рівності предикатів служить множина(P0, P0), (P1, P1),…, (P7, P7) . Рівняння Dk (P, Q) = 0 задає відношення нерівності PQ предикатів P і Q. Відношення нерівності предикатів можна розглядати як антидіагональне відношення, задане на декартовій множині Mk.
Уведемо на множині Sk Sk предикат рівності ідей Dk, визначаючи його для будь-яких x, y Sk у такий спосіб:
Dk (x, y) = Dk (Ф(х), Ф (y) ) (2.2)
Тут Ф – бієкція, що відображає множину Sk на множину Mk. Предикат Dk ( x, y) відображає множину Sk Sk на множину . Відправляючись від визначення (2.2) і використовуючи відношення рівності і нерівності предикатів, можемо предикат представити у виді
Dk (x, y) = (2.3)
Розглянемо властивості предиката . Він підкоряється законам рефлексивності, підстановчості, симетричності і транзитивності (висновок цих аксіом див. у [1]). У формальному записі ці закони мають вигляд наступних логічних рівнянь:
x Dk (x, x) = 1, (2.5)
x y(Dk (x, y) Dk (y, x))=1, (2.6)
x y z(Dk (x, y) Dk ( y,z) Dk (x,z))=1, (2.7)
Rkx y(Rk (x) Dk (x, y) Rk (y))=1, (2.8)
Тут змінні x, y, z задані на множині всіх ідей Sk, змінна Rk задана на множині всіх предикатів, що визначені на множині Sk. Символом Dk позначений змінний предикат, що зв'язується логічними рівняннями (2.5)-(2.8).
Наступне твердження дає аксіоматичне визначення предиката рівності ідей:
Твердження 2.1. Для того щоб предикат Dk, заданий на множині Sk Sk можна було представити у формі (2.1), необхідно і достатньо, щоб він задовольняв умовам рефлексивності, симетричності, транзитивності і підстановчості.
У третьому розділі на основі введеної раніше моделі рівності ідей запропонована модифікована предикатна модель, що дозволяє структурувати задачу формалізації інтелектуальної діяльності. Розглянуто теоретичні і практичні питання методики використання отриманої моделі для математичного опису інтелекту людини.
Введено новий варіант поняття моделі, визначене з таким розрахунком, щоб воно задовольняло вимогам теорії інтелекту більше, ніж класичне загальне поняття моделі, наведене вище. Моделлю над універсумом букв A=(a1, a2,…, ak) і універсумом змінних B= (x1, x2,…, xn) назвемо будь-яку пару M, P , у якої в ролі першого компонента виступає яка-небудь підмножина M n-го декартового ступеня множини A, тобто MAn, а роль другого компонента виконує який-небудь n-місний предикат B= (x1, x2,…, xn), заданий на An. Перший компонент M моделі M, P називаємо її носієм, або основною множиною моделі. Число елементів у множині M називаємо потужністю моделі. Другий компонент P називаємо предикатом моделі M, P. Множину An назвемо універсальним простором розмірності n. Вона складається з усіх n-компонентних наборів букв, узятих із множини A. Потужністю простору An назвемо число kn наборів букв, що містяться в ньому. Для розрізнення введеного нами поняття моделі з класичним, моделі тільки що описаного виду будемо називати модифікованими.
Довизначення предиката P моделі M, P можливо, очевидно, багатьма різними способами. Це приводить до того, що результати однієї серії експериментів можуть бути формально представлені різними моделями. Будь-які моделі, що задають те саме поводження людини, будемо називати конгруентними одна одній. Дамо формальне визначення відношення конгруенції моделей. Дві моделі M1=M, P та M2=M2, P2 називаємо конгруентними M1 M1, якщо: 1) їхні носії рівні M1 = M2 = M; 2) значення предикатів цих моделей для всіх наборів ідей M збігаються P1()=P2().
Формально-логічною мовою тільки що сформульовані умови запишуться у вигляді наступних рівнянь:
(M1*() M2*())=1, (3.1)
(M*() P1()~P2())=1, (3.2)
Предикати M*(), M1*(), M2*(), що фігурують у рівняннях, відповідають множинам M, M1 і M2. Закон відповідності задається співвідношенням (3.2).
Змінну називаємо несуттєвої щодо моделі M, P, якщо для всіх наборів (x1, x2,…, xn)M при довільній фіксації змінних x1, x2,…, xi-1, xi+1,…, xn значення предиката P не залежать від значень змінної xi. Математично цю умову можна записати у вигляді наступного логічного рівняння:
x1x2…xi-1xi`xi``xi+1…xn(M*(x1,x2,… xi-1,xi`,xi+1,… xn)
(M*(x1,x2,… xi-1,xi`,xi+1,… xn)) (P (x1,x2,… xi-1,xi`,xi+1,… xn) ~ (3.3)
~P(x1,x2,… xi-1,xi`,xi+1,… xn)) =1
Змінну x1 будемо називати істотною щодо моделі M, P, якщо остання не задовольняє умові (3.3). Введення позначення (x1,x2,… xi-1,xi`,xi+1,… xn)=, дозволяє переписати умову (3.3) у більш компактній формі:
```(M*(`) M*(``))(P(`) P(``))=1 (3.4)
Розглянемо операцію нормалізації моделі, задану на множині всіх моделей L, що приймає значення в тій же множині. По визначенню операція нормалізації ставить у відповідність моделі M, P модель M, M* P,. Модель N=F(M), яку одержуємо в результаті виконання операції нормалізації F над моделлю M, назвемо нормальним образом моделі M. Справедливо наступне твердження: дві моделі M1=M, P і M2=M, P2 конгруентні в тому і тільки в тому випадку, якщо їхні нормальні образи збігаються, тобто якщо F(M1)=F(M2).
Можливість переходити до нормальних образів будь-яких моделей дає практичну процедуру, за допомогою якої вирішується питання про конгруентність будь-яких моделей. Якщо дві моделі мають однакові нормальні образи, то вони конгруентні, якщо ж нормальні образи різні, то вихідні моделі не конгруентні.
Важливо вміти вирішувати також зворотну задачу: по даній стандартній моделі знайти весь клас конгруентних їй моделей. Ця задача зводиться до відшукання загального рішення рівняння P`=M*P щодо предикатної змінної P. Воно виражається в наступному вигляді:
___
P=P`M*C (3.5)
де C – довільний предикат, заданий на An. Згідно (3.5), для всіх M значення предиката P() збігаються зі значеннями предиката P`(). За межами області M значення предиката P можуть вибиратися довільно.
Справедливість рівняння (3.5) обґрунтовує
Твердження 3.1. Нехай a і b – булеві константи, що задовольняють умові ab=b (а). Тоді рівняння ax=b (б) має відносно булевій перемінної x наступне загальне рішення: x=bac. Символом c позначена довільна булева константа. При невиконанні умови (а) рівняння (б) рішень не має.
Четвертий розділ присвячений аксіоматичному введенню структури алгебри ідей і вивченню формальних та змістовних інтерпретацій цієї алгебри.
Будь-яку алгебраїчну систему Ln, що складається з множини Sn(n{1,2,…}) що утримує 2n елементів, відношення рівності x=y та операції xy(x, y, xySn) назвемо алгеброю ідей, якщо для неї виконуються наступні аксіоми: ідемпотентності, комутативності, асоциативності, аксіоми нуля і n-мірності (докладніше про аксіоматику див. [4]). Алгебри ідей L1, L2, … є частковим випадком комутативних ідемпотентів.
Множину Sn назвемо носієм алгебри ідей Ln, число n – розмірністю алгебри Ln, елементи множини Sn – ідеями алгебри Ln. Будемо говорити, що ідеї алгебри Ln n-мірні. Операцію xy називаємо диз'юнкцією ідей x і y. Ідею z=xy, що одержуємо в результаті виконання операції диз'юнкції над ідеями x і y, будемо називати їх логічною сумою. Ідеї x і y будемо називати додатками суми xy. Елемент 0 називаємо нульовою ідеєю або нулем алгебри Ln. Елементи e1, e2, …, en називаємо базисними ідеями алгебри Ln, а множину Bn={ e1, e2, …, en } – її базисом. Нульову і базисні ідеї будемо називати утворюючими ідеями алгебри Ln.
Поняття алгебри ідей розмірності n(n{1,2,…}) було введено не прямим визначенням, а задано неявно системою логічних умов. Тому важливо показати, що для кожного n{1,2,…} існує хоча б одна конкретна алгебра Ln, що є алгеброю ідей розмірності n. Для цього доведемо наступне твердження.
Твердження 4.1. Алгебра ідей будь-якої розмірності n (n={1,2,…}) існує.
Для позначення n-мірних ідей алгебри Ln вводимо формули алгебри ідей Ln. Формули будемо будувати із символів 0, e1, e2, …, en, що позначають утворюючі ідеї алгебри Ln, символу , що позначає операцію диз'юнкції алгебри Ln, і двох допоміжних символів – дужок ( і ). Символи 0, e1, e2, …, en будемо називати утворюючими символами алгебри Ln, а символи e1, e2, …, en – базисними символами алгебри Ln. Будь-які скінченні послідовності введених символів будемо називати вираженнями алгебри Ln.
Поняття формули визначаємо індуктивно за допомогою породжуючої процедури: 1) Всі утворюючі символи називаємо формулами алгебри Ln. 2) Якщо вираження A і B – формули алгебри Ln, то вираження (A B) називаємо формулою алгебри Ln. Вважаємо, що формула (A B) позначає ідею, одержувану в результаті диз'юнкції ідей, позначених формулами A і B.
З аксіоми n-мірності випливає, що для кожної ідеї алгебри Ln знайдеться хоча б одна її формула. Це означає, що мова формул логічної алгебри Ln при кожнім n={1,2,…} повна. Формулу 0 та всі бездужкові форми, у які не входить символ 0, а базисні символи входять не більш, ніж по одному разу і розташовані в порядку росту їх номерів, будемо називати стандартними формами ідей. Формулу 0 будемо називати нульовою стандартною формою. Нижче формулюється твердження про стандартну форму.
Твердження 4.2. Для кожної ідеї алгебри Ln n=(1,2,…) існує єдина стандартна форма.
Також формулюється і доводиться твердження про ізоморфізм алгебр ідей.
Твердження 4.3. Усі алгебри ідей розмірності n (n{1,2,…}) ізоморфні одна одній.
Поєднуючи твердження про існування й ізоморфізм алгебр ідей, ми можемо затверджувати, що алгебра ідей кожної розмірності n (n{1,2,…}) існує та єдина (з точністю до ізоморфізму).
Розглянемо одну з інтерпретацій алгебри ідей – алгебру чисел. До алгебри чисел приходимо, заміняючи елементи канонічної алгебри ідей їх номерами. У таблиці 4.1 представлені, як приклад, операції диз'юнкції ідей (у даній інтерпретації – натуральних чисел) при n=1, 2 і 3.
Табл. 4.1
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7
0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7
1 | 1 | 1 | 3 | 3 | 5 | 5 | 7 | 7
2 | 2 | 3 | 2 | 3 | 6 | 7 | 6 | 7
3 | 3 | 3 | 3 | 3 | 7 | 7 | 7 | 7
4 | 4 | 5 | 6 | 7 | 4 | 5 | 6 | 7
5 | 5 | 5 | 7 | 7 | 5 | 5 | 7 | 7
6 | 6 | 7 | 6 | 6 | 6 | 7 | 6 | 7
7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7
Можна вважати, що таблицею 4.1 задані деякі функції 2-, 4-, і 8-значної логіки. При n=1 приходимо до такої алгебри чисел, для якої роль диз'юнкції ідей виконує операція диз'юнкції двозначної логіки. Є важлива відмінність сімейства всіх алгебр чисел від сімейства всіх багатозначних логік з операцією диз'юнкції. Вона полягає в тому, що алгебри чисел можуть бути задані лише на множинах, що складаються з 2n елементів. Багатозначні ж логіки можуть бути задані на множині з будь-яким числом елементів k.
Нехай Ln – довільно обрана алгебра ідей розмірності n, задана на носії Sn, для якої визначена операція диз'юнкції ідей . Введемо на множині Sn бінарне відношення , визначивши його наступною умовою: для будь-яких x, y Sn твердження x y рівносильне рівнянню xy=y. Доведемо, що відношення є частковий порядок. За аксіомою ідемпотентності для кожного xSn маємо xx=x. Це означає, що xy, тобто відношення рефлексивне. Припустимо, що x, y, zSn такі, що x y і y z. Це означає, що xy=y і yz=z. Відповідно до аксіоми асоціативності xz=x(yz)=(xy)z=yz=z відкіля xz=z. Ми одержали, що x z. Таким чином, відношення транзитивно. Нехай x, y Sk такі, що xy і yx. Це означає, що xy=y і yx=x. Скориставшись законом комутативності, одержуємо x=yx=xy=y. Ми вивели рівняння x=y, а це означає, що відношення антисиметричне. Отже, ми довели, що відношення задовольняє усім властивостям, що визначають відношення часткового порядку. Приклад побудови відносини часткового порядку на множині S3 в канонічної алгебрі ідей L3 розглянуто у [5].
Вище була описана алгебра ідей та одна її формальна інтерпретація. Розглянемо також дві змістовні інтерпретації алгебри ідей. Першу з них назвемо значеннєвою інтерпретацією алгебри ідей. Множину Sn інтерпретуємо як сукупність будь-яких думок, що дослідник може збудити в розумі випробуваної людини, пред'являючи їй спеціально підібраний текст. Думка, що виникає в розумі випробуваної людини в результаті розуміння запропонованого тексту, назвемо сенсом цього тексту.
Кожен текст, що використовується дослідником, повинний бути зрозумілим випробуваній людині, тобто повинний викликати в її розумі цілком визначену думку. Цю вимогу назвемо умовою значеннєвої визначеності тексту. Тексти, що мають кілька різних значеннєвих значень, допускаються. У цьому випадку під сенсом тексту розуміється сукупність усіх можливих його значеннєвих значень.
Кожна думка, порушувана дослідником у розумі випробуваної людини, повинна однозначно визначатися текстом, що її породжує. Цю вимогу назвемо умовою значеннєвої однозначності тексту. Цього можна досягти, якщо кожен текст буде сприйматися як ізольований, тобто він не повинний зв'язуватися з будь-яким контекстом. Тексти, що мають однаковий сенс, будемо називати тотожними.
Утворення думки c, заданої текстом C, з довільно узятих думок a і b, заданих текстами A і B, розглядаємо як операцію диз'юнкції c=ab алгебри ідей. Сенс пропозиції C розглядаємо як логічну суму сенсів пропозицій A і B. Так задана операція диз'юнкції думок підкоряється аксіомам ідемпотентності, комутативності й асоциативності. Союз „або” розглядаємо як ім'я операції диз'юнкції думок. Сенс будь-якого суперечливого тексту розглядаємо як нульову ідею. Такий сенс задовольняє аксіомі нуля. Сенс будь-якого безсенсовного тексту розглядаємо як одиничну ідею. Такий сенс підкоряється закону одиниці.
Ситуаційно-предикатна інтерпретація алгебри ідей. Формально представимо випробувану людину у вигляді цілком скінченного автомату, що задається функцією переходів
U(t)=G(U(t-1), V(t-1))
і функцією виходів
V(t)=H(U(t-1), V(t-1)).
Тут t – поточне значення дискретного часу. Моменти дискретного часу, що випливають безпосередньо друг за другом, позначаємо числами натурального ряду 0, 1, 2, .., m. Момент 0 називаємо початковим, момент m – кінцевим. У ролі m приймаємо досить велике натуральне число. Змінна t визначена на множині {0, 1, 2, …, m}... Число t-1 позначає момент дискретного часу, безпосередньо попередньому моменту t. У ролі такту часу, тобто інтервалу фізичного часу між сусідніми моментами дискретного часу, приймаємо досить малу величину.
Символом U(t) позначаємо стан пам'яті випробуваної людини в сучасний момент дискретного часу. Символ V(t) позначає стан фізичного світу, що оточує випробуваного у сучасний момент. Вираження U(t-1), і V(t-1) позначають стан пам'яті випробуваної людини і стан фізичного світу в момент дискретного часу, безпосередньо попередній сучасному моменту. Функція переходів G описує закон, по якому пам'ять випробуваної людини переходить зі стану U(t-1) в стан U(t). Функція виходів H описує закон, за яким фізичний світ переходить зі стану V(t-1) в стан V(t) у результаті дій випробуваної людини, обумовленим станом його пам'яті U(t-1).
Стан U(t) пам'яті випробуваної людини в заданий момент дискретного часу t будемо характеризувати за допомогою слова T=y1y2…yr, що представляє собою послідовність букв y1y2…yr, узятих з досить великого алфавіту R. Вважаємо, що довжина r слова T досить велика і не міняється з часом. Кожне слово будемо формально представляти у вигляді бінарного предиката T(x, y), де x – номер букви y в слові T (x{1, 2, …, r}), y – буква, що стоїть на x-му місці в слові T (xR). Вважаємо, що предикат T задовольняє умові визначеності
xyT(x, y)=1
і умові однозначності
xy`y``(T(x, y`)T(x, y``) (y`= y``))=1
П'ятий розділ присвячений програмної реалізації отриманих у попередніх розділах алгебро-логічних структур для формалізації сенсу текстів природної мови.
Розробляються алгоритми побудови формул алгебри ідей, що відповідають текстам природної мови. Сенс кожного тексту природної мови розглядається як залежність його істинності від предметних перемінних, що неявно є у цьому тексті.
Комплекс програм "ЛОГОС" вирішує задачу перевірки коректності введення (для файлу – це контрольна сума, а для даних із клавіатури – перевіряється за допомогою спеціального транслятора на підставі побудованих граматик), збереження й обробки відносин і предикатів. Програмно задано універсум предметів, спосіб кодування предметів і предметних перемінних; засіб введення і висновку формул алгебри ідей, алгоритм переходу від формул до таблиць, побудовано інтерпретатор алгебро-логічної символіки в термінах предметної області. Розроблено модулі для приведення формул алгебри ідей до стандартних форм та для розкладання предикатів по змінним і їх значенням, для спрощення формул, для виконання дій в алгебрі ідей.
Створена програмна система вирішує наступні задачі формалізації сенсу текстів: обчислює значення введеного користувачем ситуаційного предиката щодо заданої їм ситуації; для завдання предиката має розширювану бібліотеку слів, операцій, кванторів і універсумів; ситуації задаються множиною об'єктів і множиною зв'язаних з ними відносин. Для рішення поставлених задач реалізований спосіб ручного перекладу сенсу тексту на мову алгебри ідей. Створено словник понять, якими володіє комп'ютерна система, що розуміє тексти природної мови. Розроблено наступні програмні модулі: автоматизований формальний запис значеннєвого предиката пропозиції і формування відповідних зображень на дисплеї комп'ютера; модуль визначення відносин, у яких знаходяться предмети ситуації; модуль розбирання формального запису сенсу тексту; система встановлення відповідності значеннєвої і графічної інформації про ситуацію.
Програмна система “LOGOS for BD” являє собою демонстраційну версію, що реалізує основні принципи нового підходу моделювання логічних мереж на основі синтезу математичних результатів дисертаційної роботи у галузі теорії одномісних предикатів та предикатних операцій у рамках алгебри ідей та апарату категорного аналізу логіки. Система створена з метою показати принципові переваги застосування запропонованого математичного апарата алгебри ідей.
У додатку приведені акти впровадження теоретичних і практичних результатів дисертаційної роботи.
ВИСНОВКИ
У дисертаційній роботі наведено результати, котрі, у відповідності з метою дослідження, в сукупності є вирішенням актуальної наукової задачі – розробки комплексу алгебро-логічних засобів формалізації семантики текстів природної мови для розширення можливостей інтелектуального інтерфейсу та реалізації отриманих моделей у вигляді програмного продукту. Вирішення цієї задачі полягає в застосуванні розроблених моделей в системах автоматичної обробки текстів природної мови та має велике значення для створення ефективного інтерфейсу спілкування між рядовими користувачами та автоматичними системами. У результаті вирішення сформульованої задачі:
1. Проведено аналіз моделей формальної обробки текстів природної мови, що вже існують, та обґрунтована необхідність розробки системи, яка формалізує сенс текстів природної мови на основі алгебраїчних моделей семантики.
2. На базі алгебри одномісних k-їчних предикатів першого порядку розроблено аксіоматично алгебру ідей, яка призначена для формалізації сенсу текстів природної мови. Розвинуто її структуру – носій алгебри та її аксіоматика; введено поняття канонічної алгебри ідей і операції на ній. Алгебра ідей виконує роль аксіоматичної бази для багатьох попередніх алгебраїчних моделей, побудованих конструктивно, що дозволило проводити формалізацію семантики мови на цілком об’єктивному, експериментальному рівні.
3. Введено предикат рівності ідей – інструмент для експериментального вивчення речень природної мови, визначена аксіоматика цього предиката. Доведено необхідність і достатність введеної аксіоматики предиката рівності ідей. Розроблено питання повноти і нескоротності аксіоматики моделі рівності ідей. Аксіоматично визначені операції заперечення, кон’юнкції і диз'юнкції ідей. Це дозволило знаходити закономірності семантики природної мови в результаті аналітичної обробки експериментальних даних, що, в свою чергу, відкрило шлях до безперешкодного перекладу сенсу досить великого класу природно-мовних текстів на мову логічних рівнянь.
4. Розроблено модифіковану предикатну модель, що дозволяє вирішити задачу об'єднання часткових моделей, побудованих на базі підмножин множини ідей. За допомогою введеного поняття нормального образа моделі отримана практична процедура, що дозволяє вирішити питання про скорочення несуттєвих змінних моделі.
5. Вирішено задачу конгруентних моделей, що виникає через частковість предиката і необхідність його довизначення. Розвинуто метод порівняння для стандартної моделі – загальний метод математичного опису інтелектуальної діяльності людини. Результати останніх трьох пунктів необхідні для проведення та оптимізації лінгвістичних експериментів.
6. Розроблено деякі формальні та сенсовні інтерпретації алгебри ідей розмірності n, зокрема – алгебру чисел. Ці інтерпретації дали змогу визначати, який конкретно набір базисних елементів та операцій фактично використовується в структурі текстів природної мови.
7. Запропоновано правила побудови формул алгебри ідей за текстами природної мови для предикатів 1-го і 2-го рівнів із використанням кванторів і логічних зв'язків. На основі створеного апарата алгебри ідей розроблена програмна система, що реалізує алгоритми формалізації сенсу текстів у вигляді формул алгебри ідей. Ця система може використовуватися як компонент обробки сенсу текстів природної мови в автоматизованих системах.
8. Розроблені математичні методи та алгоритми формалізації механізмів інтелектуальної діяльності людини застосовано в автоматизованих інформаційних системах з природно-мовним інтелектуальним інтерфейсом, для логічної підтримки проектування інформаційних структур (Інститут фізики високих енергій та ядерної фізики Національного наукового центра “Харківський фізико-технологічний інститут”, акт впровадження від 11.09.2002; торгівельно-виробниче підприємство “Європейське торгівельне обладнання”, акт впровадження від 23.09.2002), що дозволило структурувати задачу формалізації інтелектуальної діяльності.
9. Реалізований в дисертації
