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

Фуджу Халід Ісса Мохамед

УДК 004.82:004.89

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

05.13.23 – системи та засоби штучного інтелекту

Автореферат

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

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

Харків - 2004

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

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

Науковий керівник – кандидат технічних наук, доцент, Дюбко Геннадій Федорович, Харківський національний університет радіоелектроніки, професор кафедри програмного забезпечення ЕОМ.

Офіційні опоненти: доктор технічних наук, професор

Авраменко Валерій Павлович, професор

кафедри інформаційно-управляючих систем,

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

радіоелектроніки;

кандидат технічних наук Шостак Ігор Володимирович,

доцент кафедри програмного забезпечення

комп’ютерних систем,

Національний аерокосмічний Університет

ім. М.Є. Жуковського „ХАІ”, м. Харків.

Провідна установа Національний технічний університет України

„КПІ”, кафедра прикладної математики,

м. Київ.

Захист відбудеться „ 16 ” лютого 2005 р.

о 1500 годині на засіданні спеціалізованої вченої ради Д 64.052.01 в Харківському національному університеті радіоелектроніки за адресою: 61166, м. Харків, просп. Леніна, 14, тел. 7021-306.

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

Автореферат розісланий „ 14 ” січня 2005 р.

Вчений секретар

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

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

Актуальність теми. Прикладні інтелектуальні системи використовуються зараз у десятках тисяч застосувань. Річний дохід від продажів прикладних засобів штучного інтелекту (ШІ) ще в 1990 р. становив 870 млн доларів, а в 1998 р. – 1.1 млрд доларів. Зараз цей приріст відбувається більш плавно, але суми, затрачувані на придбання продуктів ШІ, значні.

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

Великий внесок в розроботку теоретичніх і прикладніх питань формування різних моделей знань внесли Попов Е.В., Поспелов Д.А., Гаврилова Т.А., Шабанов-Кушнаренко Ю.П., Бондаренко М.Ф., М. Мінський, Дж. Робінсон, Н. Хомський.

Створення прикладної експертної системи, яка обслуговує предметні області проектування і планування, є складною задачею. Тут необхідно акумулювати знання, що відносяться до аналізу мови, на якій формулюються завдання для ЕС, і виявлення семантики мовних конструкцій, знання для прийняття рішень ЕС за сформульованими правилами і виявленою семантикою. Під семантикою маються на увазі об’єкти предметної області та співвідношення між ними. Всі знання можна подати деякою уніфікованою моделлю знань. Але більшість моделей подання знань – спеціалізовані і ефективно працюють на обмежених предметних областях. Тому раціонально використати різні моделі подання знань. Для подання знань про синтаксис і семантику мови використовують формальну систему (граматику), котра аналізує мову. Для прийняття рішень застосовують логічну модель. Для узгодження функціонування між цими двома моделями знань використовуються метазнання (продукційна модель), що трансформують знання з мережевої форми у логічну. Комплексна модель подання знань, що складається з вищезазначених компонент одержала назву „трикомпонентна модель подання знань”.

Дисертаційна робота присвячена розробці засобів проектування й реалізації експертної системи, що автоматично генерує програмну модель для дослідження певної інженерної системи. Експертна система базується на трикомпонентній моделі подання знань і може бути настроєна на конкретну мову моделювання. Особлива увага при розробці ЕС приділена мовним проблемам. Важливість цього питання пов'язана з постійним ростом числа інтелектуальних систем, що функціонують у мовному інформаційному середовищі. Тенденція дослідження проектного простору на рівні архітектури, представленої на мовах візуального опису проектованих систем, простежується в областях створення сучасних інформаційних систем (BPwіn, ERwіn), існуючих підходів до розробки програмного забезпечення (UML), створення програмних моделей апаратури (VHDL, Verіlog). Однак ручна генерація кодів мови моделювання досить трудовитратна операція. Створення ефективних систем автоматичної генерації моделюючого коду може бути успішно вирішене шляхом створення прикладних інтелектуальних систем, що й обґрунтовує актуальність досліджень у цій області.

Зв'язок з науковими програмами, роботами, планами, темами. Робота виконувалася на кафедрі ПЗ ЕОМ згідно із планом науково-дослідних робіт Харківського національного університету радіоелектроніки в рамках держбюджетної теми № 159, 0103U001545, „Моделі механізмів інтелекту людини та їх застосування у інформаційних системах зі штучним інтелектом”, наказ Міністерства освіти і науки України № 633 від 5.12.2002 р. , де автор працював як виконавець.

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

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

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

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

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

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

- продемонструвати на прикладах можливімть побудови фрагментів баз знань, алгоритмів, "життєздатність" розробленої методики побудови експертної системи для конкретної проблемної області (VHDL).

Об'єктом дослідження є технологія побудови прикладних експертних систем.

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

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

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

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

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

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

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

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

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

- запропоновано засіб виявлення об’єктів проектування і зв’язків між ними, що відображені у деревах виведення, у вигляді алгоритмів, готових до використання у СКВ;

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

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

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

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

Основні положення, висновки й рекомендації, викладені в дисертаційній роботі, використані в розробках підприємства ALDEC club (акт впровадження від 03.09.2004).

Особистий внесок здобувача. Всі результати дисертації отримані автором самостійно. У роботі [1] проаналізовані способи рішення завдань інтелектуальними системами, а саме експертними системами з вибором ЕС на трикомпонентній моделі знань. Запропоновано метод створення ЕС на базі формальних систем, зокрема , продемонстровано процес створення елементів ЕС для перетворення проекту в програмну модель, показана методика формування синтаксично керованого визначення, правил предметної бази знань для конкретних мов проектування й моделювання. У роботі [2] розглядається процес розробки ЕС на основі трикомпонентної моделі знань: структура ЕС, механізми функціонування формальних систем, що входять в ЕС, алгоритми перетворення структур даних, що відображають значення семантичних елементів, в оператори мови моделювання. Продемонстровано методику побудови бази знань, що представляє лінгвістичні аспекти, на прикладі конкретної предметної області. У роботі [3] запропоновано формалізм для маніпуляції лінгвістичними знаннями у вигляді синтаксичного аналізатора без глухих кутів, що базується на анотованій граматиці. Розглянуто методику побудови аналізатора для фрагмента атрибутної граматики, що працює з використанням характеристичного автомату, сформованого на конкретному фрагменті лінгвістичних знань. У роботі [4] розглянуто прикладні аспекти використання розроблених засобів для створення ЕС, що транслює візуальне подання проекту в програмну модель мовою VHDL. Запропоновано мову опису проекту і спосіб заповнення структур даних, що настроюють ЕС на розв’язування завдань у конкретній предметній області, а також середовище реалізації ЕС на платформі UNІX, ORACLE.

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

Основні результати дисертаційної роботи були представлені на: 7-мому (2003 р.), 8-мому (2004 р.) Міжнародному форумі "Радіоелектроніка й молодь у ХХ1 столітті", Харків; на Міжнародній науковій конференції "Теорія і техніка передачі інформації". Харків-Туапсе 2003 р. [6, 7, 8]

Публікації. За результатами досліджень опубліковано 7 робіт, з них 4 статті в наукових спеціалізованих виданнях, відповідно до переліків ВАК України, 3 тези доповідей на міжнародних конференціях.

Структура та обсяг роботи. Дисертація складається із вступу, п'яти розділів і висновків, та має обсяг основного тексту 142с., загальний обсяг 184с. Містить 35 рисунків, 2 таблиці, 4 додатка на 28 сторінках, список використаних літературних джерел, що включає 87 найменувань на 8 сторінках.

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

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

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

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

За результатами проведеного аналізу сформульовані мета та задачі дисертаційної роботи:

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

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

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

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

- побудувати фрагменти баз знань (логічних і лінгвістичних) для адаптації ЕС до моделювання на мові VHDL цифрових пристроїв.

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

Процес розв’язання завдань інтелектуальною системою складається з певних етапів (рис.1).

Рис.1. Структурна схема інтелектуальної системи з МП

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

Лінгвістичні знання для МП подаються за допомогою СКВ. Результатом роботи МП буде семантичний еквівалент МК у вигляді дерева виведення (ДВ). У вузлах ДВ, як зображено на рис.. 2, розміщуються “нетермінали” (прямокутники, позначені числами-кодами понять), які співвідносяться з поняттями предметної області та “символи дії”. Листями ДВ є термінали серед яких ідентифікатори інтерфейсу (А,В). Це дозволяє організовувати процес аналізу інформації як строго формальну процедуру – обхід дерева. Крім того, ДВ будується на основі однозначного формального процесу виведення у граматиці. Для обходу ДВ запропоновано наступний алгоритм. ДВ перетворюється на бінарне дерево, потім застосовується прямий рекурсивний обхід. Таким чином, вузли ДВ обходяться у ієрархічному порядку (family order). Це дає змогу обробляти спочатку верхні вузли, що мають більше семантичне навантаження.

Рис. 2. ДВ для лічильника одиниць

Знання про предметну область та правила прийняття рішень подаються за допомогою числення предикатів. Правила прийняття рішень подаються у вигляді хорнівських диз’юнктів. Для подання процедурних знань (вмінь) пропонується використовувати функціональні символи, для яких відомий алгоритм обчислення. Для уніфікації таких функціоналів під час логічного виведення розроблені власні правила, які розглянуті у четвертому розділі. Таким чином, у правилах з’являються такі елементи: літерали, змінні, константи, функціональні символи як структури даних, функціональні символи з алгоритмом обчислення їх значення. Оскільки результатом функціонування МП є ДВ мовної конструкції, а для подання знань про предметну область використовується числення предикатів, то виникає потреба у формальному способі перетворення ДВ на набір предикатів робочої БЗ, що використовується на етапі логічного виведення. Наявність таких предикатів визначається за допомогою обходу ДВ.

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

К(1:3, 2:3, 3:5) К1.К2.К3(4.1.0, 3-2.0.0, 1.0.0, 5.0.2, 0.2.0, 0.3.4, 0.4.3,0.0.1).

Рис.3. Граф з трьох компонент

Для надбання знань по прийняттю рішень у вигляді бібліотеки процедур розроблено правила (хорнівські диз’юнкти):

код-схема : - код-схема (),

код-имя ;

код-схема ;

код-имя : - вход ,

выход ,

поведение .

Третій розділ дисертаційної роботи присвячено аналізу подання знань в СКВ, розробці СКВ для графових продукцій та розробці алгоритмів виведення та семантичного аналізу в СКВ. Показано, що можливості граматики і СКВ дозволяють замінити логічний вивід у хорнівських диз’юнктах. Множина хорнівских диз’юнктів складається з фактів (один позитивний литерал), правил (один позитивний литерал і множина негативних), цілей (немає позитивного литерала). Наприклад, є хорновский диз’юнкт, що виражає правило. Існує імпликативна форма запису диз’юнкта: q :- p, r, де ліворуч від знака :- записаний позитивний литерал (заголовок правила), праворуч– негативні. Якщо для утворення резольвенти r по алгоритму взяти дизъюнкти q:-p,s й p , то r є q:-s. Із синтаксичної точки зору перетворення в резольвенту полягає в тому, щоб у диз’юнкті q :- p, s замінити p на e. Це наводить на думку замінити подання знань формулою числення висловлень на продукцію граматики. При цьому правила типу q :- p, s заміняються на продукцію q –> ps, факт (p :-) заміняється на p –> e, ціль (:- z) заміняється на l –> z. Всі символи граматики, що відповідають пропозиційним змінним у дизъюнкті, будуть нетермінальними символами. Виведення методом резолюцій у хорнівських диз’юнктах замінюється на виведення у граматиці. Наведені вище міркування про еквівалентності стосуються числення висловлень. Але їх можна поширити на числення предикатів, тому що одержання резольвенти у численні предикатів вимагає додатково уніфікованості литералів і застосування до резольвенти найбільш загального уніфікатора. Синтаксичне ж правило утворення резольвенти залишається таким, як було.

Уніфікація й одержання значень аргументами литералів у численні предикатів відбивається виведенням в атрибутній граматиці й одержанням значень атрибутами в кожній продукції. Для коректного висновку в атрибутной граматиці введено умову застосованості продукції Xb1,...,bk –> e до символу Xl1,...,lk. По-перше, Xb1,...,bk повинен бути повністю конкретизованным литералом; по-друге, атрибути {b1,...,bk} й {l1,...,lk} повинні бути унифікованими.Продемонстровано на прикладі заміну логічного виведення у численні предикатів на виведення в атрибутній граматиці.

В атрибутній граматиці кожний граматичний символ має зв'язану множину атрибутів, розділену на дві підмножини - синтезовані й наслідувані атрибути цього граматичного символу. Якщо розглядати вузол граматичного символу (Х) у дереві розбору як запис із полями для зберігання інформації, де атрибут відповідає імені поля (attr), звернення до цього атрибуту можна подати у вигляді X.attr. Значенням атрибуту може бути число, рядок, тип, адреса пам'яті, структура даних. Значення атрибуту у вузлі дерева розбору визначається семантичними правилами, пов'язаними з використаною в даному вузлі продукцією. Значення синтезованого атрибуту у вузлі обчислюється за значеннями атрибутів у вузлах - нащадках даного вузла; значення наслідуваних атрибутів обчислюються за значеннями атрибутів батьківського вузла й вузлів одного рівня стосовно розглянутому батьківському.

Семантичні правила визначають залежності між атрибутами, які можна представити графом залежності, що задає порядок виконання семантичних правил. Семантичні правила можуть задавати не тільки алгоритми обчислення значень атрибутів, але також можуть змінювати змінні, що не є атрибутами. Семантичні правила можна вводити як граматичні символи в продукції граматики. Наприклад, Xа –>YbZc{f}d,e,h d=b, e=c, а=h є продукція, у якій: а, b, c - атрибути граматичних символів (терміналів і нетерміналів); d, e, h - атрибути символу дії f , представленого як граматичний символ; рівності позначають правила присвоювання значень атрибутам (мається на увазі, що значення атрибута h - це результат семантичної дії f). У випадку подібного подання семантичних функцій дерево розбору містить вузол {f}, що збільшує загальну кількість вузлів, котрі підлягають обробці, і зменшує загальну ефективність системи. Щоб уникнути витрат цього виду, використаємо синтаксично кероване визначення. У СКВ кожна продукція КС-граматики A–> зв'язується з множиною семантичних правил. Для вищенаведеної продукції X–>YZ з атрибутами а, b, c, d, e, h і процедурою f множина семантичних правил представляється як X.а =f(Y.b, Z.c). Таким чином, для кожної продукції A–> є пов'язана з нею множина семантичних правил виду a=f(b1,...,bk), де f - функція, b1,...,bk - атрибути граматичних символів продукції, "а"-синтезований атрибут символу А або наслідуваний атрибут одного із граматичних символів правої частини продукції. У цьому випадку атрибут „а” залежить від атрибутів b1,...,bk. При обчисленні значень одиниць, що мають сенс у завданнях проектування й планування використовуються семантичні правила синтаксично керованого визначення, які записуються як виклики процедур або фрагменти програм. Якщо одиниця з сенсом є структурою даних, що складається з окремих елементів, значення цих елементів будуть розосереджені по різних вершинах дерева висновку, і їх можна "зібрати" у єдину структуру за допомогою семантичних правил. У роботі побудовано СКВ для графової продукції. Як вивідна система обрано синтаксичний аналіз згорткою без глухих кутів. Для забезпечення детермінованості висновку будується характеристичний кінцевий автомат. Для граматики, що описує графову продукцію виробляється анотація. По анотованій граматиці побудовано характеристичний кінцевий автомат і алгоритм синтаксичного аналізу. Запропоновано алгоритми присвоєння значень атрибутам і зроблені оцінки їхньої часової складності, які знаходяться в рамках (n). Побудовано й проаналізовано алгоритми обходу дерева висновку для формування семантичних структур.j

Основою СКВ є граматика. На прикладі графової продукції

VHDL_таблиця ONES_CNT (A bit_vector in; bit_vector out) –>

поведінка in A [8, 3] (0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1); out B [8, 2] (0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1)

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

1. <схема>> VHDL_таблиця імен (<інтерфейс>) ‘–>’ <поведінка>

2. <інтерфейс>>ім’я <тип>in; ім’я <тип> out

3. <тип>? bit_vector (число to число )

4. <поведінка>> поведінка in ім’я [число, число] (<список даних>);out им’я [число, число] (<список даних>)

5. <список даних>?<список даних>, <дане>

6. <список даних>? <дане> 7. <дане>?0 8. <дане>?1.

Вищезазначена граматика анотується, у результаті чого одержується анотована граматика:

1. H--? 1V2 i3 (4I5)6:7 C8 2. I?4 i9T10 e11; 12 i13 T14 S15

3. T?9,13 b16 (17 n18 t19 n20)21

4. C?7 P22 e23 i24[25 n26, 27n28]29 (30 L31)32;33 S34 i35 [36 n37, 38 n39]40 (41 L42)43

5. L?30,41 L44, 45 D46 6. L?30,41 D47

7. D?30, 41, 45 048 8. D?30, 41, 45 149 ;

де нетермінали: <схема> - Н, <інтерфейс> - І, <поведінка> - С, <тип> - Т, <список даних> - L, <дане> - D;

термінали: VHDL_таблиця – v, ‘–>’ , :, им’я – i, in – е, out – s, bit_vector – b, число – n, to – t є умовні позначення символів граматики.

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

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

Наприклад, літерал код-ім’я () відбиває сенс: “компонент, що має ім’я К і належить до архітектури з ім’ям N, має у якості модельованого коду значення змінної S”. Значення змінної S співпадає з значенням функції , використаної як терм літералу. Процедура безпосередньо формує програмний код, а є інформація про структуру проектованої системи та її поведінку.

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

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

Запропоновано низку лексичних перетворень для стрічок, що презентують предикати. Робоча база знань може складатись з великої кількісті предикатів, тому даже бінарний пошук, часова складність якого О(log N), може вимагати неприпустимих часових витрат. Тому треба індексувати РБЗ, створюючі список індексів, з яких починається группа дизъюнктов, що мають однакові імена головних предикатів. Після приведення РБЗ до універсального вигляду усі предикати одержують індексні імена вигляду pXXXX, тому номер запису у списку індексів буде відповідати конкретному предикату. Це дозволить взагалі не здійснювати пошук підходящих диз’юнктів, а зразу обчислювати точне їх месце знаходження в РБЗ.

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

поведінка

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

У п,ятому розділі наведена методика побудови експертної системи для генерації коду на мові VHDL, виходячі з візуально поданого проекту цифрового пристрою на мові розробника. Сформульованно структуру правил (хорнівських диз,юнктів) предметної бази знань. Виділено два типа правил: для компонента (примітива), тобто ізольованого пристрою, поведінка і інтерфейси якого описані; для схеми, що складається з компонентів, поведінка і інтерфейси кожного з яких описані. Правило для компонента має вигляд:

код-ім,я(f (Х1, Х2, Х3, Х)):- ім,я-компонента (Х1), вхід (Х1, Х2), вихід(Х1, Х3), поведінка-ім,я (Х1, Х),

де Х1 – ім,я компонента; Х2, Х3 – інтерфейси компонента, подані списками (у сенсі ПРОЛОГу);

Х – поведінка компонента, що подається структурою даних відповідно до предикату ”поведінка-ім,я”.

Функція f формує код VHDL, виходячи з Х2,Х3,Х, а також списки вхідних та вихідних сигналів.

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

код-схема (Х, [Кt|Кl], fi(Z, Kp)):- код-схема (X, Kl, Z), код-ім,я (X, Kt, Kp);

kод-схема (X, [], пусто);

kод-ім,я (X, Kt, f(Kt, X2, X3, Y)): - вхід (X, Kt, X2), вихід (Х, Кt, Х3),

поведінка-ім,я (Х, Кt, Y).

У правилах для генерації коду із схем позначення [w] означає, що w –список. Kt є ім,я поточного компонента списка, Kl-хвіст списка, X-ім,я схеми, Kp – код VHDL для компонента. Функція fі формує код VHDL, виходячи з уже сформованих кодів підсхеми Z і поточного елементу Kt, а також списки вхідних та вихідних сигналів. На прикладі лічильника одиниць побудовано граматику, предметну базу знань і базу метазнань та продеманстрованно функціонування експертної системи. Для компонент, що базуються на комбінаційній логіці у вигляді таблиць або булевих функцій розроблено СКВ:

1. <программа TI_VHDL>?TI_VHDL <описание>:-<поведение>

2. <описание>><имя компонента>(<вход-выход>)

3. <имя компонента>>идентификаторj

l ? i

4.<вход-выход>><список входов>r1,r2,r3; <список выходов>r4,r5,r6

l1?r1, l2?r2, l3?r3, l4?r4, l5?r5, l6?r6

5.1 <список входов>r1,r2,r3>целоес: идентификаторi: in: typet

r1?c, r2?i, r3?t

5.2 <список входов>r1,r2,r3;><список номеров>n:<список идентификаторов>i:in<список спецификаций>t

r1?c, r2?i, r3?t

5.3 <список входов>r1,r2,r3;><список входов>l1,l2,l3; целоес; идентификаторi: in: typet

r1?list(l1,c), r2? list(l2,i), r3? list(l3,t)

6.1 <список номеров>n><список номеров>n1, целоес

n?list(n1,c)

6.2 <список номеров>n?

n?nul

7.1 <список идентификаторов>i> <список идентификаторов>l идентификаторk i?list(i1,k)

7.2 <список идентификаторов>i ? i?nul

8.1 <список спецификаций>t><список спецификаций>t1, typet2

t?list(t1,t2)

8.2 <список спецификаций>t? t?nul

9.1 <список выходов>r1,r2,r3> целоес: идентификаторi:out: typet

r1?c, r2?i, r3? t

9.2 <список выходов>r1,r2,r3><список номеров>n:<список идентификаторов>i:out:<список спецификаций>t

r1?n, r2?i, r3?t

9.3 <список выходов>r1,r2,r3><список выходов>l1,l2,l3 ; целоес: идентификаторi: out: typet

r1?list(l1,c), r2? list(l2,i), r3? list(l3,t)

10. <Поведение>><список входных имен>r1(<входная таблица>r2);

<список выходных имен>r3(<выходнатаблица>r4)

l1?r1, l2?r2, l3?r3, l4?r4

11.1 <список входных имен>r>идентификаторi [целоес1, целоес2]

r?list(i,c1,c2)

11.2 <список входных имен>r<список входных имен>r1,идентификаторi rlist(r1,i)

11.3 <список входных имен>r rnul

12.1 <список выходных имен>rидентификаторi [целоес1, целоес2]

rlist(i, c1, c2)

12.2 <список выходных имен>r<список входных имен>r1,

идентификаторi rlist(r1,i)

12.3 <список выходных имен>r rnul

13.1 <входная таблица>rбитB rlist(в)

13.2 <входная таблица>r<входная таблица >r1,битв

rlist(r1,в)

14.1 <выходная таблица>rбитв rlist(в)

14.2 <выходная таблица>r<выходная таблица >r1,битв

rlist(r1,в).

Побудовано алгорітми (функції f із правил предметної бази знань) генерації коду VHDL. Для компонент з послідовною логікою розглянуто принцип побудови алгорітму для формування коду VHDL. Запропоновано обчислювальне середовище UNIX – ORACLE, у якому повинна функціонувати розроблена експертна система.

У додатках наведено алгоритми на псевдомові, схеми алгоритмів, структурні схеми блоків експертної системи; сформульовані граматики та СУВ фрагментів ЕС генерації коду на VHDL, а також програми на VHDL.

ВИСНОВКИ

У дисертації наведені теоретичні узагальнення і нове вирішення наукової задачі, що виявляється в:

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

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

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

- розробці засобів адаптації експертної системи до використання у сфері проектування цифрових пристроїв.

Розроблені прикладні інтелектуальні системи використовуються в багатьох застосуваннях. Існує значна кількість експертних систем, що у різних областях: медицина, математика, геологія, військова галузь і т.д. Не втрачає своєї актуальності задача генерації програмного коду, виходячи з високорівневого подання проекту. При цьому автоматична генерація коду використовується не тільки для програмних систем, але і для інших інженерних проектів (наприклад, цифрових пристроїв), де за високорівневим поданням проекту на мові проектувальника генерується програмна модель для тотального тестування проектованої системи. Використання для автоматичної генерації коду CАSE-засобів, побудованих на традиційних обчислювальних підходах не дало бажаних результатів, тому що різні аспекти системи автоматичної генерації коду потребують застосування інтелектуальних здібностей. Тому виникає потреба дослідження можливості побудови і реалізації експертної системи, що генерує код у заданій мові програмування, виходячи з високоуровневого подання проекту на мові проектувальника.

Побудовано основні засоби реалізації ЕС, показана можливість побудови експертної системи, що автоматично генерує код за описанням проекту, на основі трикомпонентної моделі знань (граматика, числення предикатів, продукційна система). Застосування трикомпонентної моделі знань дозволяє гнучко й адекватно описувати знання різної природи і добре структурувати програмну реалізацію експертної системи: граматика описує синтаксично і семантично мову проектування, числення предикатів – правила прийняття рішень при формуванні програмного компонента і його інтерфейсів, продукційна система трансформує семантичні відношення мови проектувальника у формули числення предикатів для одержання коду як результату логічного висновку.

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

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

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

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

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

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

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

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

1. Дюбко Г.Ф., Фуджу Халид Исса Мохамед. Застосування граматик у базах знань експертних систем // Проблеми біоніки. Всеукраїнський міжвідомчий науково-технічний збірник.- 2003.- Вып. 59.- С. 19-26.

2. Дюбко Г.Ф., Фуджу Халид Исса Мохамед. Розробка експертних систем для рішення завдань планування й проектування // Радіоелектроніка й інформатика. Науково-технічний журнал.- 2004.- №1(26).- C. 141-146.

3. Дюбко Г.Ф., Фуджу Халид Исса Мохамед. Синтаксичний аналіз язикових конструкцій, що описують цифрові пристрої // Радіотехніка. Всеукраїнський міжвідомчий науково-технічний збірник.- 2004.- Вип. 137. - C. 60-66.

4. Дюбко Г.Ф., Харченко С.Л., Фуджу Халид Исса Мохамед. Проектування програмних моделей цифрових пристроїв // Автоматизовані системи керування й прилади автоматики. Всеукраїнський міжвідомчий науково-технічний збірник.- 2004.- - Вип. 126.- C. 37-47.

5. Фуджу Халид Исса Мохамед. Компонентна технологія програмування для опису моделей цифрових пристроїв // Матеріали 7-го міжнародного молодіжного форуму "Радіоелектроніка й молодь у ХХ1 столітті".- Харків: ХНУРЕ.- 2003.- С. 630.

6. Дюбко Г.Ф., Харченко С.Л., Фуджу Халид Исса Мохамед. Методи штучного інтелекту в проектуванні й реалізації програмного забезпечення // Збірник тез доповідей за матеріалами Міжнародної наукової конференції "Теорія й техніка передачі, прийому й обробки інформації".- Харків-Туапсе: ХНУРЕ.- 2003.- С. 254-255.

7. Фуджу Халид Исса Мохамед. Подання знань грамматиками // Матеріали 8-го міжнародного молодіжного форуму "Радіоелектроніка й молодь у ХХ1 столітті". Частина 2.- Харків: ХНУРЕ.- 2004. С. 63.

АНОТАЦІЯ

Фуджу Халид Ісса Мохамед. Засоби побудови прикладної експертної системи на базі трикомпонентної моделі. - Рукопис.

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

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

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

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

АННОТАЦИЯ

Фуджу Халид Исса Мохамед. Средства построения прикладной экспертной системы на базе трехкомпонентной модели. – Рукопись.

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

Диссертация посвящена разработке экспертной системы,