Лінійні логічні перетворення та їх застосування в штучному інтелекті

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

Харківський національний університет радіоелектроніки

УДК 519.7:007.52; 519.711.3

Автореферат

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

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

Спеціальність 05. 13. 23 - Системи та засоби штучного інтелекту

Лінійні логічні перетворення та їх застосування в штучному інтелекті

Вечірська Ірина Дмитрівна

Харків 2007

Дисертація є рукописом

Робота виконана у Харківському національному університеті радіоелектроніки, Міністерство освіти і науки України

Науковий керівник: заслужений діяч науки і техніки, доктор технічних наук, професор Шабанов-Кушнаренко Юрій Петрович, Харківський національний університет радіоелектроніки

Офіційні опоненти: доктор технічних наук, професор Шаронова Наталія Валеріївна, Національний технічний університет «Харківський політехнічний інститут», завідувач кафедри інтелектуальних комп'ютерних систем кандидат технічних наук, доцент Шостак Ігор Володимирович, Національний аерокосмічний університет ім. М.Є. Жуковського «Харківський авіаційний інститут», доцент кафедри програмного забезпечення комп'ютерних систем

Захист відбудеться «19» березня 2008 р. о 14 годині на засіданні спеціалізованої вченої ради Д 64.052.01 в Харківському національному університеті радіоелектроніки за адресою: 61166, м. Харків, пр. Леніна, 14, тел. (0572) 702-14-51.

З дисертацією можна ознайомитись у бібліотеці Харківського національного університету радіоелектроніки, м. Харків, пр. Леніна, 14.

Автореферат розісланий «18» лютого 2008 р.

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

Загальна характеристика роботи

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

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

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконувалася згідно з планом науково-технічних робіт Харківського державного університету радіоелектроніки в рамках держбюджетної теми № 202 «Розробка принципів побудови мозкоподібних ЕОМ» (№ ДР 0106U003292), розділ 1 «Розробка та застосування логічних мереж мозкоподібних ЕОМ» (виконавець теми).

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

Для досягнення поставленої мети потрібно вирішити наступні задачі:

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

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

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

розробити метод обчислення лінійних логічних перетворень, який дозволяє збільшити розмірність ядра лінійних логічних перетворень;

побудувати алгоритми та програмно реалізувати розроблені методи.

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

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

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

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

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

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

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

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

Результати, отримані в дисертаційній роботі, знайшли своє практичне застосування для розв'язання задачі знаходження гіпотетично зв'язаних абонентів автоматичної системи комплексних розрахунків (АСКР) інтегрованої інформаційно-обчислювальної системи підприємства електрозв'язку ВАТ «Укртелеком» (акт впровадження від 09.03.2006 р.). Використання розроблених алгебро-логічних засобів дозволило мінімізувати час пошуку і підвищити ефективність виводу в цій задачі.

Розроблені математичні методи було використано для побудови комп'ютерного комплексу для автоматизації керування фірмою та узгодження роботи її відділів (ТОВ фірма «Регіон. Будзв'язок», акт впровадження від 09.06.2007 р.). Це дозволило зменшити час на прийняття рішень і тим самим привело до ефективного використання праці співробітників різного профілю та повного своєчасного їх інформування про стан роботи.

Теоретичні результати дисертації були використані в навчальному процесі на кафедрі програмного забезпечення ЕОМ Харківського національного університету радіоелектроніки під час підготовки курсів лекцій «Теорія інтелекту» та «Алгебраїчна логіка» для спеціальності «Програмне забезпечення автоматизованих систем» (акт впровадження від 12.06.2007 р.). Програмне забезпечення, розроблене в дисертації, використовується в курсовому й дипломному проектуванні, у науково-дослідній роботі студентів на кафедрі програмного забезпечення ЕОМ.

Особистий внесок здобувача. Усі результати, представлені в роботі, отримані автором самостійно. Їх основний зміст викладений у роботах [1 - 15], деякі з них написані в співавторстві. В роботі [1] досліджувались способи представлення багатомісного відношення у вигляді композиції бінарних предикатів, особисто автором було наведено формальну постановку задачі та обґрунтовано її актуальність. В [2] особисто автором було розроблено приклад побудови дводольного графа відношення між першою буквою закінчення повних неприсвійних прикметників і родом, реалізовано вихідним та зворотними ланцюгами перемикання. В роботі [3] було досліджено внутрішню структуру алгебро-логічного апарату для побудови логічних мереж, а саме вивчено закономірність, на основі якої було виведено та досліджено формулу для побудови n-ого перетворення в загальному вигляді. В [4] особисто автором було наведено формули для знаходження елементів матриці перетворення в загальному вигляді. В [5] було розв'язано обернену задачу для лінійних логічних перетворень. В статті [6] особисто автором було доведено твердження про ступінь лінійного логічного перетворення, наведено приклад застосування. В роботі [7] особисто автором було проведено теоретичну роботу по інтерпретації поняття категорії з об'єктами. В роботі [8] особисто автором було доведено узагальнення твердження про вигляд лінійного логічного перетворення на випадок трьох змінних, наведено формули для обчислення лінійних логічних перетворень в залежності від способу задання області визначення. В статті [9] особисто автором було наведено приклад суперпозиції лінійних логічних перетворень та наведено метод знаходження n-ого лінійного логічного перетворення.

У тезах доповіді [10] особисто автором було проведено аналіз областей застосування логічних мереж для формалізації природної мови. У тезах доповіді [11] особисто автором було доведено твердження про суперпозицію лінійних логічних перетворень. У тезах доповіді [12] особисто автором було проведено аналіз методів розв'язання бінарних предикатних рівнянь. В [13] особисто автором було доведено твердження про загальний вигляд лінійного логічного перетворення на випадок n змінних. У тезах доповіді [14] було наведено приклад розв'язання оберненої задачі для лінійних логічних перетворень, коли вхідний та вихідний вектори задані базисними векторами. У тезах доповіді [15] особисто автором було обґрунтовано роботу логічної мережі з точки зору лінійних логічних перетворень.

Апробація результатів дисертації. Основні результати дисертаційної роботи доповідалися й обговорювалися на наступних конференціях: 1) науково-практична конференція «Інформаційні технології - в науку та освіту», (м. Харків, 21-22 березня 2005 р.); 2) VIII Міжнародна науково-практична конференція «Наука та освіта 2005», (м. Дніпропетровськ, 7-21 лютого 2005 р.); 3) 9-й Міжнародний молодіжний форум «Радіоелектроніка та молодь в 21 столітті», (м. Харків, 19-21 квітня 2005р.); 4) Міжнародна науково-практична конференція «Дні науки 2005», (м. Дніпропетровськ, 15-27 квітня 2005 р.; 5) Міжнародна науково-практична конференція «Наукові дослідження та їх практичне застосування», (м. Одеса, 1-15 жовтня 2005 р.); 6) Міжнародна наукова конференція «Горизонти прикладної лінгвістики та лінгвістичних технологій» (MegaLing'2007), (м. Партеніт, Крим, Україна 25-28 вересня 2007 р.).

Публікації. Основні результати роботи опубліковані в 15 наукових працях, з них 9 статей - у наукових спеціалізованих виданнях, затверджених ВАК України, 6 - тези конференцій.

Структура й обсяг дисертаційної роботи. Дисертаційна робота складається з вступу, п'ятьох розділів, висновків, списку використаних джерел, додатків. Повний обсяг роботи - 149 сторінок. Дисертація містить 14 рисунків на 11 сторінках, 13 таблиць на 12 сторінках, 3 додатки на 3 сторінках, список використаних джерел з 102 найменувань на 9 сторінках.

Основний зміст роботи

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

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

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

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

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

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

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

,

де - коефіцієнти комбінації.

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

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

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

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

Нехай система залежна, тоді існує вектор

,

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



Тоді породжуюча сукупність перестає бути мінімальною, що суперечить умові. Звідси випливає, що сукупність являється незалежною.

Tвердження. Будь-яка максимальна (за кількістю векторів) незалежна сукупність векторів є породжуючою.

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

Для того, щоб функція

була лінійним логічним перетворенням, необхідно та достатньо, щоб вона мала вигляд

для будь-якого , де - предикат з

Таким чином було введено поняття лінійного логічного перетворення на логічних просторах.

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

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

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

: ,

де ,

була лінійним логічним перетворенням, необхідно та достатньо, щоб вона мала вигляд:

для будь-якого , де задана на , .

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

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

Далі наведемо правило обчислення лінійного логічного перетворення з в за аналогією з формулою (аналог повторного інтеграла) матиме вигляд:

,

де .

Далі представимо правило обчислення лінійного логічного перетворення з в наступною формулою:

,

де .

Ми розглянули простий випадок, де усі змінні перетворення визначені на універсумі. Виявляється, при іншому заданні області визначення зміниться й саме правило обчислення.

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

Далі представимо правило обчислення лінійного логічного перетворення з в наступною формулою:

.

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

.

Далі виразимо правило обчислення лінійного логічного перетворення з в наступною формулою:

.

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

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

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

, де

, де.

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

.

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

Таким чином, можно зробити висновок, что n - а ступінь лінійного логічного перетворення () залежить від виду матриці . Представляє інтерес те, що матриця , залежить тільки від області визначення змінної x. Тобто крок, на якому ступінь лінійного логічного перетворення при подальших діях не змінюється, безпосередньо залежить від розмірності області визначення змінної x.

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

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

Введемо необхідні визначення та твердження.

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

Поняття досконалої диз'юнктивної нормальної форми (ДДНФ) визначається так, як і в алгебрі логіки, проте слід відмітити, що в даному випадку змінні, які входять до ДДНФ, можуть приймати значення не тільки 0 та 1.

Твердження 1. Будь-яку булеву форму можна привести до ДДНФ.

Твердження 2. Будь-яку булеву форму можна виразити:

Твердження 3. Для будь-якої булевої алгебри рівносильно .

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

~.

За допомогою твердження 3 виразимо систему в такому вигляді:

,(2)

де - змінна. Отже, виразимо задачу у канонічному вигляді:

.(3)

Твердження 4. Рівняння (2) має хоча б один розв'язок, тоді и тільки тоді, якщо

де

Сам розв'язок у цьому випадку виражається деякою формою:

,

Твердження 4. Будь-який елемент , який задовольняє рівнянню

можна представити наступним чином

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

Перейдемо до самого опису методу. Спочатку розв'язуємо рівняння (3) відносно змінної , вважаючи - параметрами. Для цього випадку отримаємо критерій існування розв'язку (твердження 4):

де

Таким чином, для того щоб перевірити виконання критерію існування розв'язку рівняння необхідно знайти функцій. Сам розв'язок буде виражено деякою булевою формою (твердження 5):

.

Далі аналогічно розв'язуємо рівняння (3) відносно змінної , де - параметри. Розв'язок буде виражено деякою формою:

.

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

При розв'занні задачі ідентифікації лінійних логічних перетворень аналогічним методом знаходимо розв'язки, вважаючи невідомими, а - параметрами:

,

де , , - як і раніше, розмірності відповідних вектор-стовпчиків.

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

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

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

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

, (4)

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

, (5)

де - область визначення змінної .

Далі визначимо на першому напівтакті значення (4) та/або (5). Щоб перейти до наступного такту, на другому напівтакті -го такту необхідно знайти як перетин знайдених знань про значення змінної :

,

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

.

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

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

Висновки

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

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

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

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

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

Отримані методи побудови логічних мереж впроваджені у комп'ютерному комплексі для автоматизованого керування фірмою та узгодження роботи її відділів (ТОВ фірма «Регіон. Будзв'язок», акт впровадження від 09.06.2007). Результати, які отримано в дисертаційній роботі, знайшли своє практичне застосування при розв'язанні задачі знаходження гіпотетично зв'язаних абонентів АСКР інтегрованої інформаційно-обчислювальної системи підприємства електрозв'язку ВАТ «Укртелеком» (акт впровадження від 09.03.2006 р.). Теоретичні результати дисертації були використані у навчальному процесі на кафедрах програмного забезпечення ЕОМ та прикладної математики ХНУРЕ під час підготовки курсів лекцій «Теорія інтелекту» та «Алгебраїчна логіка» для спеціальності «Програмне забезпечення автоматизованих систем»(акт впровадження від 12.06.2007 р.).

Список опублікованих автором праць за темою дисертації

1. Синельникова О.И., Вечирская И.Д. Представление многоместных отношений в виде композиции бинарных отношений // Радиоэлектроника и информатика. - 2001. - № 3. - С.147 - 150.

2. Вечирская И.Д., Дударь З.В., Иванилов А.А., Лещинский В.А. Линейные логические операторы в виде схем и графов // Бионика интеллекта. - 2004. - № 1 (61). - С. 38 - 41.

3. Вечирская И.Д. Действия над линейными логическими преобразованиями // Новые технологии. - 2005. - № 1 - 2 (7 - 8). - С. 162 - 168.

4. Вечірська І.Д., Дудар З.В. Розв'язання задачі ідентифікації довільного лінійного логічного перетворення // Східно-Європейський журнал передових технологій. - 2006. - № 5/2 (23). - С.63 - 66.

5. Вечирская И.Д. О решении обратной задачи для линейных логических преобразований // Бионика интеллекта. - 2006. - № 2 (65). - С.36 - 40.

6. Вечирская И.Д., Шабанов-Кушнаренко Ю.П. О методе нахождения n-ого линейного логического преобразования // Искусственный интеллект. - 2007. - № 3. - С. 382 - 389.

7. Вечирская И.Д., Дударь З.В., Иванилов А.А., Лещинский В.А. О категорном анализе алгебры предикатов // Вестник НТУ «ХПИ»: Сб. науч. трудов. - Харьков: НТУ «ХПИ», 2002. - № 20. - С. 38 - 42.

8. Вечирская И.Д., Иванилов А.А. О вычислении линейных логических преобразований // Вестник НТУ «ХПИ»: Сб. науч. трудов. - Харьков: НТУ «ХПИ», 2005. - № 18. - С. 29 - 32.

9. Вечірська І.Д., Шабанов-Кушнаренко Ю.П. Про дослідження властивостей лінійних логічних перетворень // Системи обробки інформації: Зб. наук. праць. - Харків: ХУПС, 2007. - № 6. - С. 86 - 90.

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

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

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

13. Вечирская И.Д., Шабанов-Кушнаренко Ю.П. Об общем виде линейных логических преобразований // Дни науки 2005: междунар. науч.-практич. конф. Днепропетровск, 15-27 апреля 2005 г. - Днепропетровск; Кривой Рог; Запорожье; Желтые Воды; Белгород; Прага, 2005 - Т. 18. - С. 21 - 22.

14. Вечирская И.Д. Об обратной задаче и задаче идентификации для линейных логических преобразований // Научные исследования и их практическое применение. Современное состояние и пути развития: междунар. науч.-практич. конф. Одесса, 1 - 15 октября 2005 г. - Одесса, 2005 - Т. 9. - С. 74 - 75.

15. Вечирская И.Д., Валенда Н.А., Колтун Ю.Н., Токарев В.В., Четвериков Г.Г. О формальных аспектах реализации фрагмента русского языка логической сетью // Горизонты прикладной лингвистики и лингвистических технологий: междунар. науч. конф. Партенит, 23 - 29 сентября 2007 г. - М.; Симферополь; К.; Харьков; СПб., 2007. - С. 257 - 259.

Анотація

Вечірська І.Д. Лінійні логічні перетворення та їх застосування в штучному інтелекті. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.23 - системи та засоби штучного інтелекту - Харківський національний університет радіоелектроніки, Харків, 2007.

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

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

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

Аннотация

Вечирская И.Д. Линейные логические преобразоваия и их применение в искусственном интеллекте. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.23 - системы и средства искусственного интеллекта - Харьковский национальный университет радиоэлектроники, Харьков, 2007.

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

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

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

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

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

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

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

Abstract

Vechirskaya I. D. Linear logical transformations and their application in an artificial intellect. - Manuscript.

The thesis on competition of a scientific degree of the candidate of technical science on a speciality 05.13.23 - system and means of an artificial intelligence - Kharkov's National University of Radio Electronics, Kharkov, 2007.

The dissertation is devoted to building of formalization methods of the relation with linear logical transformation. It is a main tools for realization of logic network which focused on parallel information processing and its program realization.

The received methods of logic networks construction are applied at a computer complex construction for automated firm management. Besides, received method well founded the functioning of logic networks and applied in complex accounts computer-based system of integrated data-processing system of enterprise. The utilization of developed outlet's instruction strategics is minimized the search time and this is to increase the efficiency of outlet. Developed logical algebra mathematical tool is simplified of given types problem for both knowledge engineer and user.

Key words: algebra-logical tools, identification problem, linear logical transformations, logical space, parametric equations method of solution, predicate operation, power of linear logical transformations, natural language formalization.

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

...