У завданнях штучного інтелекту застосовуються різні моделі представлення знань і методи обчислень - м'які обчислення, генетичні алгоритми, нейромережі, логічні моделі та інші підходи. Всі ці методи засновані на символьних обчисленнях і тому можуть бути реалізовані на основі мови PROLOG.
Тут ми розглянемо методи побудови інтелектуальних систем на основі логічного підходу, який найбільш близький природі логічного програмування і часто застосовується в експертних системах.
В основі логічного висновку лежить математичне поняття «формальна система (ФС)». ФС - це сукупність абстрактних об'єктів, пов'язаних між собою певними правилами. Згадаймо визначення. Формальна система F вказана, якщо визначена четвірка:
F = (Al, Sn, Ax, Ru)
Al - алфавіт - кінцева безліч символів;
Sn - синтаксис - процедура побудови правильно побудованих формул ФС;
Ax - аксіоми - сукупність правильних формул, заданих спочатку;
Ru - правила висновку - кінцеве безліч правил, що дозволяють отримувати нові формули з інших формул ФС.
Будь-яка програма мовою ПРОЛОГ є ФС, яких в одній програмі може бути декілька. У ПРОЛОЗІ важливу роль відіграє поняття уніфікації, що дозволяє більш широко застосовувати правила ФС за рахунок підстановки параметрів. Гарним прикладом ФС у програмі є синтаксичний аналізатор мовою ПРОЛОГ ().
ФС можна застосувати для породження нових тверджень (прямий висновок) або для доведення правильності тверджень (зворотний висновок). У ПРОЛОГу можна реалізувати обидва варіанти висновку, хоча зворотний висновок реалізується безпосередньо, оскільки закладений у структуру мови.
Мова логічного програмування дає багато цікавих можливостей для вирішення інтелектуальних завдань, тобто потребують логічного висновку для отримання рішення. Як правило, можливості мови зі створення різних типів прикладних систем демонструються на досить простих прикладах, призначених більше для демонстрації парадигми логічного програмування, в навчальних цілях.
Для створення практично корисних прикладних систем потрібен ряд властивостей, відсутніх у системі ПРОЛОГ, але які можна в неї додати.
Про всяк випадок, згадаймо, що обчислення в логічному програмуванні полягає в пошуку логічного висновку. Цим терміном називається дерево, коренем якого є доказове твердження, а інші вершини містять твердження, пов'язані між собою логічним слідуванням. При цьому термінальні вершини (листя) дерева повинні бути вихідними даними - твердженнями, сформульованими в умові завдання.
Побудова дерева логічного виведення полягає в пошуку взаємопов'язаних ланцюжків тверджень від листя до вершини серед безлічі всіх можливих шляхів від вершини до листя. Це безліч називають простором пошуку завдання.
Пошук може бути прямий - від даних до шуканого і зворотний - від шуканого до даних. У першому підході з умов завдання обчислюють те, що можна - нові твердження, збільшуючи тим самим кількість відомого про завдання.
У другому підході будуються гіпотези - будується послідовність, точніше дерево, гіпотез, яке має привести до відомих даних.
Оскільки ПРОЛОГ заснований на зворотному висновку, спочатку розглянемо зворотний висновок.
Для ілюстрації проблем, що виникають при побудові незіграшкових експертних систем, використовуємо в якості предметної області ^ метрію, точніше кажучи, її невелику частину, пов'язану з вирішенням трикутників.
Розглянемо конкретне завдання.
У рівнобедреному трикутнику проведена висота з вершини, розташованої між рівними сторонами. В внутрішньому трикутнику знову проведена висота, потім в новому трикутнику ще висота, і т. д. всього - 10 висот. Відомі довжина основи трикутника AC і бокової сторони BC. Потрібно вирішити будь-який трикутник, утворений проведеними висотами.
Подання основних об'єктів може бути таким:
- seg (A, B) - відрізок з кінцевими точками A і B;
- tri (A, B, C) - трикутник з вершинами А, В, С;
- length (seg (A, B), L) - довжина відрізка;
- equal (tri (A, B, C), tri (X, Y, Z)) - рівність трикутників.
Для простоти викладу розглянемо обчислення другої висоти трикутника - DE. Запишемо умови завдання засобами мови ПРОЛОГ:
s(1,exist(d,tri(a,b,c))).
s(2,height(seg(b,d),tri(a,b,c))).
s(3,height(seg(d,e),tri(b,c,d))).
s(4,height(seg(f,e),tri(b,e,d))).
s(5,height(seg(f,g),tri(f,e,d))).
s(6,height(seg(h,g),tri(f,g,e))).
s(7,height(seg(h,i),tri(g,h,e))).
s(8,height(seg(i,k),tri(h,i,e))).
s(9,height(seg(k,l),tri(i,k,e))).
s(10,height(seg(l,m),tri(l,k,e))).
s(11,height(seg(m,n),tri(m,l,e))).
s(12,equal(seg(a,b),seg(b,c))).
s(13,length(seg(a,b),10)).
s(14,length(seg(a,c),16)).
s(15,length(seg(d,e),x)).
Для нумерації умов завдання предикати записані в додаткових дужках у вигляді s (N, P).
Останній рядок у вихідних даних завдання визначає мету - затвердження, яке необхідно довести. У нашому випадку мета length (seg (d, e), x) містить змінну х, що дозволяє - обчислити значення довжини відрізка DE.
Одна з основних труднощів у застосуванні ПРОЛОГу для реалізації комерційних систем - виникнення зациклювання програми в процесі обчислень. Причиною цього може бути не помилка в програмі, а рекурсивність властивостей об'єктів предметної області і, відповідно - рекурсивність правил логічного висновку.
Наприклад, у правилах логічного виведення для вирішення трикутників неминуче відбувається звернення до аналогічних правил.
Приклад 1, Обчислення довжини відрізка у трикутнику.
Обчислення довжини сторони трикутника через висоту і площу:
length(seg(A,C),L):-
height(seg(B,D),tri(A,B,C)),
length(seg(B,D),L1),
area(tri(A,B,C),S1),
L is (2*S1)/L1.
Обчислення довжини висоти трикутника через основу і площу:
length(seg(B,D),L):-
height(seg(B,D),tri(A,B,C)),
length(seg(A,C),L1),
area(tri(A,B,C),S1),
L is (2*S1)/L1.
Для вирішення нашого завдання достатньо чотирьох правил для обчислення довжини відрізка - обчислення довжини відрізка, утвореного висотою рівнобедреного трикутника, теорема Піфагора, обчислення довжини висоти через площу і основа трикутника, отримання значення від рівного відрізка.
У процесі пошуку рішення всі виникаючі цілі нумеруються. Всі розглянуті в процесі пошуку рішення цілі утворюють простір пошуку завдання, з якого лише невелика частина потрапляє в результуюче дерево логічного виведення.
Рішення - дерево логічного виводу для нашого завдання можна записати у вигляді списку пронумерованих предикатів наступним чином:
- (78) hypot(tri(d,b,c),seg(b,c)) [79]
- (45) exist_rect(tri(d,b,c),seg(d,b)) [2]
- (46) length(seg(d,c),8) [14,47]
- (66) length(seg(b,c),10) [13,12]
- (77) pif_length([seg(d,b),6],[[seg(d,c),8],[seg(b,c),10]]) [78]
- (47) median(tri(a,b,c),seg(b,d)) [2,48]
- (333) rectangle(tri(c,d,b),_2F28) [2]
- (334) catets(tri(c,d,b),[seg(b,d),seg(d,c)]) [78]
- (44) length(seg(d,b),6) [77,66,46,45]
- (46) length(seg(d,c),8) [14,47]
- (332) area(tri(c,d,b),24) [46,44,334,333]
- (66) length(seg(b,c),10) [13,12]
- (331) length(seg(d,e),4.8) [66,332,3]
Кожен предикат являє собою мету, виведену в процесі вирішення завдання і має номер, присвоєний йому в процесі обчислень. Праворуч, у квадратних дужках, записано список номерів предикатів, використаних в однойменному правилі для отримання результату.
Те ж дерево в графічному уявленні має такий вигляд:
Як можна бачити з малюнка, всі термінальні вершини дерева - затвердження з вихідних даних.
Наведемо текстову інтерпретацію отриманого рішення.
1) Для обчислення довжини відрізка seg (d, e) (331) використано правило: якщо шуканий відрізок є висотою в трикутнику, то його довжина дорівнює площі трикутника поділеної на основу і помноженої на два. Аргументи для цього правила отримані з цілей з номерами 66,332,3,
Площа трикутника cdb дорівнює 24 - ціль 332. Довжина основи bc дорівнює 10 - ціль 66. Шукана довжина дорівнює 2 * (24/10) = 4.8. Відрізок de є висотою трикутника cdb - ціль 3 (вихідні дані).
2) Довжина відрізка bc (66) обчислена з правила - якщо шуканий відрізок дорівнює іншому відрізку з відомою довжиною, то шукана довжина дорівнює довжина рівного відрізку.
У нашому випадку шуканий відрізок bc дорівнює відрізку ab - це задано у вихідних даних - мета 12, довжина відрізка ab задана в затвердженні 13.
3) Площа трикутника cdb (332) обчислюється за правилом для прямокутних трикутників за довжинами катетів, аргументи задані цілями 46,44, 333, 334.
Прямокутність трикутника cdb (333) випливає з того, що відрізок bd є висотою в трикутнику abc (2). Звідси слід визначити відрізки, які є катетами в цьому трикутнику - bd і dc (334). Далі слід обчислення довжин катетів (44) і (46).
4) Довжина катета db (44) обчислюється через прямокутний трикутник bdc з цілей з номерами 77,66,46,45.
Мета 77 - застосування теореми Піфагора для обчислення відрізка db. Мета 66 - обчислення довжини відрізка bc. Мета 46 - довжина відрізка dc. Мета 45- наявність прямокутного трикутника dbc з шуканим відрізком db.
5) Довжина катета dc (46) обчислюється з цілей 14, 47 за правилом відрізка при медіані трикутника. Мета 14 задана у вихідних даних - довжина відрізка ac, на який опущена медіана bd (47). Застосовується правило - висота в рівнобедреному трикутнику, опущена на його основу, є медіаною.
Оскільки в наведеному прикладі дані отримані в результаті застосування конкретної логічної програми, можна припустити, що обсяг пошуку склав 334 цілі, з яких 13 склали необхідне рішення завдання.
Для більш складного випадку, наприклад для обчислення десятої висоти в нашому трикутнику - відрізка LM, обсяг пошуку склав 1667 цілей, а в процесі пошуку виведення було отримано 138 тверджень, з яких далеко не всі увійшли в шукане рішення. Незначний обсяг пошуку пов'язаний з тим, що було використано всього чотири правила для обчислення довжини відрізка.
Ми розглянули спрощений приклад для ілюстрації основних аспектів вирішення завдань, які потребують логічного висновку. Якщо ж спробувати описати всі теореми в метрії для обчислення довжини відрізка - подоба і рівність трикутників, тригонометричні функції, складові відрізки, обсяг необхідних обчислень зростає на порядки і тут знадобиться мати додаткові можливості, щоб впоратися з усіма виникаючими складнощами.
Для того, щоб вирішувати досить об'ємні інтелектуальні завдання недостатньо звичайної мови ПРОЛОГ, оскільки в ньому відсутній ряд властивостей, без яких складно побудувати практично корисну програму. Ці удосконалення системи мови ПРОЛОГ можна розділити на дві групи - управління пошуком виведення (логічні) і технологічні.
Необхідні такі удосконалення управління пошуком:
- захист від зациклювання;
- збереження створеного виводу;
- можливість працювати з великими обсягами правил;
- збереження траси пошуку виведення в просторі станів предметної області для налагодження;
- управління обсягом обчислень для захисту від зайвих неефективних пошуків за наявності помилки або відсутності рішення;
- побудова пояснення отриманого рішення.
Технологічні удосконалення:
- інтеграція з процедурними мовами програмування;
- інтеграція із засобами операційної системи;
- ефективність коду;
- можливість створення автономних програм.
Більшість сучасних систем мови ПРОЛОГ мають компілятор та інші засоби, які забезпечують можливість створення прикладних програм, застосовних без інтерпретатора мови ПРОЛОГ, спільно з програмами іншими мовами програмування або автономно.
Для отримання удосконалень пошуку необхідно в кожне правило ПРОЛОГу в прикладній програмі вставити додаткові перевірки і, відповідно, додаткові аргументи.
Щоб не робити це вручну, можна використовувати спеціальні інструментальні системи. Науково-виробнича фірма «Semantics Research» розробила таку систему під назвою Exxlog, яку можна завантажити безкоштовно на сайті компанії (exxlog.ru).
Ув'язнення
Ми розглянули основні аспекти побудови формальної системи у вигляді програми для вирішення логічних завдань. ФС вирішує завдання шляхом повного перебору варіантів.
Якщо тут можна описати правила для всіх необхідних теорем в метрії, простір пошуку буде непідйомним для середнього комп'ютера, а може бути і суперкомп'ютера. Однак ми добре знаємо, що розумний школяр вирішить майже будь-яке вирішуване завдання за прийнятний час, не виконуючи занадто великого перебору.
Як він це робить? За рахунок аналізу і планування рішення, намічаючи найперспективніші підходи і не розглядаючи свідомо марні. Знання, якими він скористається для планування рішення, не є геометричними теоремами - це і є ті знання, які називають експертними - знання про методи пошуку рішення, які зазвичай експерт отримує в процесі навчання і виробляє самостійно, в процесі набуття досвіду.
Висновок - одна ФС не є експертною системою. Для ЕС потрібно об'єднати кілька ФС. Надалі розглянемо більш детально, як це зробити.
