Способи логічного виводу

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

	modus-ponens X-->y (принцип міркувань): “з істинності Х слідує істинність затвердження Y”;
	modus-tollens (логічний принцип): “якщо висновок істинний, то істинно і умова X”.

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

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

При управлінні виводом повинен бути реалізований хоч один спосіб управління виводом. Спосіб управління виводом визначається 2-мя ознаками:

1. звідки починається процес міркувань;

2. як поступати в точках галуження рішень.

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

У ЕС і прямому і зворотному ланцюжках міркувань можуть міняти свій напрям.

Зворотний ланцюжок міркувань простіше реалізувати (реалізована в інтерпретаторі Prolog).

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

Розглянемо задачу:

1. Людина (M), вовк (W), коза (G) і капуста (C) знаходяться на лівому березі - початковий стан.

2. Вовк (W), коза (G) і капуста (C) знаходяться на правом бережу - кінцевий стан.

Треба перебратися на інший берег на човні.

1. Човен перевозить тільки двох.

2. Не можна залишати на одному березі козу і капусту, козу і вовка.

Простір рішень складається з безлічі станів і набору операторів:

	Л	А		П	ОП	Л	В		П
1	W|G|C|M				M|G—>	W|C		M|G
2	W|C		M|G		<—M	W|C|M		G
3	W|C|M		G		M|C—>	W		M|G|C
4	W		M|G|C		<—M|G	W|G|M		C
5	W|G|M		C		M|W—>	G		M|W|C
6	G		M|W|C		<—M	G|M		W|C
7	G|M		W|C		M|G—>			W|G|M|C
8	W|C|M		G		M|W—>	C		W|G|M
9	C		W|G|M		<—M|G	C|G|M		W
10	C|G|M		W		M|C—>	G		C|W|M

Л - лівий берег, П - правий берег.

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

Алгоритм зворотного ланцюжка:

1. Зробити кінцевий стан поточною підціллю;

2. Відшукати правила, висновок яких співпадає з поточною підціллю;

3. Якщо знайдене правило приводить до початкового стану, то знайдено рішення;

4. Інакше умову правила робимо поточною підціллю і переходимо до пункту 2.

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

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

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

Всі відповіді на питання залишаються в базі даних. 

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

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

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

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

При пошуку завширшки - немає послідовності, перескакують з однієї теми на іншу.

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

Прямий ланцюжок міркувань

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

З правил в базі знань вибираються ті, умови яких співпадають з поточною підціллю. Виконання цих правил приводить до нової підцілі.

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

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

Часто ситуація виникає в ЕС, призначених для оптимального планування рішень. В цьому випадку мета не визначена, а є частиною проблеми.

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

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