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

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

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

Вступ

Актуальність теми. Спроби вирішити задачу повноцінної обробки інформації, представленої природною мовою, шляхом складання спеціально призначених для цього комп'ютерних програм, роблять вже протягом більше 50 років. Разом з тим дотепер немає повноцінного рішення таких задач, як спілкування людини з ЕОМ природною мовою, машинний переклад, пошук за змістом необхідної ділової і наукової інформації в Інтернеті. Рішення цих задач істотно стримується недостатньою глибиною формального опису механізмів природної мови.

Зручним математичним апаратом для опису природної мови є алгебра скінченних предикатів (АКП), мовою якої можуть бути записані у вигляді рівнянь будь-які скінченні відношення. Уже розроблено ряд моделей, які описують різні частини російської й української мов за допомогою даного формального апарата. Однак у процесі інтеграції отриманих моделей в єдину семантико-синтаксичну систему обробки фраз виникає проблема рішення великої кількості рівнянь у реальному режимі часу.

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

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

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

Мета й задача дослідження.

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

Основні задачі дослідження:

- проаналізувати сучасний стан проблеми в області розробки логічних мереж і математичних засобів для побудови їх моделей;

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

- на основі реляційного твердження про залежності розвинути метод декомпозиції предикатів;

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

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

1. Аналіз досягнень в області розробки логічних мереж і способів побудови їх моделей

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

Охарактеризовано формальний апарат для опису природної мови - алгебру скінченних предикатів. Цей апарат оперує літерними змінними й дозволяє представляти математичні моделі механізмів мови у вигляді логічних рівнянь. У результаті всі види граматичної обробки зводяться до рішення рівнянь АКП.

Розглянуто перспективні апаратні засоби для рішення рівнянь АКП - логічні мережі, які орієнтовані на паралельні обчислення й покликані стати основою обчислювальних модулів паралельної дії. Наводиться опис логічної мережі, а також приклад її роботи для конкретної моделі. Визначено поняття моделі логічної мережі. Як апаратна реалізація логічної мережі, розглянуті інтегральні схеми програмувальної логіки типу FPGA. Приводиться схема апаратної інтеграції логічної мережі в персональний комп'ютер через PCI-інтерфейс; тим самим логічна мережа розглянута як апаратний акселератор персонального комп'ютера для вирішення задачі обробки природно-мовної інформації.

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

Бінарна декомпозиція предикатів розглянута як спосіб побудови моделей логічних мереж. До теперішнього часу розроблено ряд моделей, кожна з яких описує за допомогою рівнянь АКП деякий невеликий фрагмент природної мови. Зараз стала актуальною задача інтеграції побудованих моделей в єдину модель мови. Ефективне використання такої моделі можливо тільки при її реалізації у вигляді логічної мережі. Для цього необхідно перетворити існуючі моделі мови в моделі логічних мереж, інакше кажучи, потрібно виконати їх бінарну декомпозицію. У зв'язку з цим проаналізовані наявні засоби кон'юнктивної декомпозиції предикатів, які спрощують перетворення предикатів у бінарну форму. Особлива увага приділена засобам бінарної декомпозиції.

На основі проведеного аналізу сформульовані мета та задачі дослідження.

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

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

Установлено ізоморфне відображення між булевою алгеброю множин (відношень) і булевою алгеброю предикатів на базі однакового предметного простору.

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

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

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

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

У реляційній алгебрі розглянуто шість основних операцій: три теоретико-множинні (об'єднання, перетинання, різниця) і три реляційні (проекції, природне з'єднання й оператор вибору).

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

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

Перестановочність кванторів гарантує для кожної множини та будь-якого предиката коректність формули.

На основі згаданої вище теореми, що зв'язує операції в реляційній алгебрі Re(T) з операціями циліндричної алгебри множин без діагоналей, і рівності був установлений наступний наслідок.

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

Задача рішення рівнянь алгебри предикатів і робота логічної мережі інтерпретовані в термінах реляційної алгебри.

Модель процесу, що досліджується, яка представлена системою рівнянь АКП, виділяє в просторі S скінченну підмножину - відношення R.

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

Цей результат утримується в полюсах мережі після зупинки її роботи.

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

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

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

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

Нехай R - деяке відношення, а сімейство множин утворює покриття множини at(R). Відношення R задовольняє залежності з'єднання.

Для функціональних залежностей наведена теорема Хеза й сформульовано її наслідок.

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

Твердження 1. Нехай R - довільне відношення, X й Y - довільні підмножини множини at(R), Z=at(R). Відношення R задовольняє залежності тоді й тільки тоді, коли для кожного й для кожного.

Твердження 2. Нехай - довільне відношення, а X й Y - довільні підмножини множини at(R), Z=at(R). Відношення R задовольняє залежності тоді й тільки тоді, коли.

Для твердження 2 сформульоване й доведене узагальнення у вигляді твердження 3.

Твердження 3. Нехай R - деяке відношення з Re(T), а сімейство множин утворює розбивку множини at(R). Відношення R задовольняє залежності з'єднання тоді й тільки тоді, коли.

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

Твердження 4. Нехай R - деяке відношення з Re(T), а сімейство множин утворює розбивку множини at(R). Відношення R задовольняє залежності з'єднання тоді й тільки тоді, коли воно одночасно задовольняє багатозначним залежностям.

На практиці можливі як дві, так і більш багатозначні залежності, що забезпечує практичну цінність твердження 4. Як і теорему Фейгина, це твердження можна використовувати для приведення схеми відношення до четвертої нормальної форми при проектуванні реляційної бази даних.

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

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

Теорема Хеза для предикатів. Нехай. Якщо P задовольняє функціональної залежності, то для нього виконується залежність кон'юнкції.

Наслідок теореми Хеза для предикатів. Нехай. Якщо для P, то P задовольняє залежності кон'юнкції.

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

Висновки

логічний реляційний предикат

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

Перераховані нижче результати відображають рішення всіх поставлених у дисертації задач у повному обсязі.

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

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

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

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

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

6. Розроблені засоби декомпозиції відношень впроваджені в науково-дослідному й проектному інституті транспорту газу при проектуванні інтегрованої автоматизованої системи керування діяльністю дочірньої компанії «Укртрансгаз» (акт впровадження від 17.03.2008 р.). Теоретичні результати дисертації були використані в навчальному процесі на кафедрах Програмного забезпечення ЕОМ і Прикладної математики (акт впровадження від 23.05.2008 р.).

Література

1. Логическая сеть для модели глагольной флексии русского языка / Дударь З.В., Иванилов А.А., Климушев В.В., Обризан В.И. // Восточно-европейский журнал передовых технологий. - 2006. - № 4/2. - С. 80-89.

2. Иванилов А.А. Реляционные алгебры и алгебры предикатов / Иванилов А.А., Шабанов-Кушнаренко Ю.П. // Восточно-европейский журнал передовых технологий. - 2007. - № 4/2. - С. 43-48.

3. Иванилов А.А. Метод бинарной декомпозиции функциональных предикатов / Иванилов А.А. // Системи обробки інформації: Зб. наук. праць. -Харків, 2006. - №6. - С. 86-97.

4. Дударь З.В. Применение элементов теории баз данных к разработке средств декомпозиции предикатов / Дударь З.В., Иванилов А.А. // Системи управління, навігації та зв'язку: Зб. наук. праць. - К.: Центральний НДІ навігації і управління, 2007. - № 3. - С. 52-58.

5. Вечирская И.Д. Суперпозиция линейных преобразований предикатов / Вечирская И.Д., Иванилов А.А. // Наука і освіта - 2005. Том 22. Математика: VIII міжнар. наук.-практ. конф. Дніпропетровськ, 7-21 лютого 2005 р.: тези доп. - Дніпропетровськ, 2005. - С. 3-4.

6. Шабанов-Кушнаренко Ю.П. Логическая сеть как технология моделирования естественного языка / Шабанов-Кушнаренко Ю.П., Хаханов В.И., Процай Н.Т. и др. // Информационные технологии - в науку и образование: наук.-практ. конф. Харків, 21-22 березня 2005 г.: тези доп. - Харків, 2005. - С. 30-33.

7. Вечирская И.Д. Логическая сеть как метод решения системы бинарных уравнений алгебры предикатов / Вечирская И.Д., Иванилов А.А. // Радіоелектроніка і молодь в XXI ст.: 9-й міжнар. молодіжний форум, 19-21 квітня 2005 р.: тези доп. - Харків, 2005. - С. 441.

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