Машина висновування

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

Компоненти машини висновування

Правила продукційної моделі не впорядковані. Кожне з них існує незалежно від інших правил. У зв'язку з цим потрібний спеціальний механізм, який керуватиме перебиранням правил. Такий механізм і є машиною висновування.

Машина висновування є однією із складових експертної системи і своєю чергою складається з двох компонентів:

  • Компонент висновування реалізує власний дедуктивний висновок. Тобто якщо в базі фактів є факт A, а в базі правил є правило If A then B, то робиться висновок про необхідність застосування дії B.
  • Компонент керування, або інтерпретатор правил керує процесом перебирання фактів і застосування правил.

Інтерпретатор правил працює за таким алгоритмом:

  1. Зіставлення. Здійснюється пошук множини правил, посилки яких зіставляються хоча б з одним фактом із бази фактів. Усі правила з цієї множини є застосовними до поточної бази фактів. Якщо правил у цій множині більше одного, то кажуть, що множина правил є конфліктною (у тому розумінні, що будь-яке з правил можна застосувати і невідомо, яке саме).
  2. Вибір. Алгоритм роботи інтерпретатора є циклічним. На кожній ітерації циклу може бути застосовано лише одне правило. Якщо правил більше одного, інтерпретатор має вирішити конфлікт, тобто обрати з правил найвідповідніше. Вибір здійснюється на основі критерію, який може встановлюватися ззовні.
  3. Виконання. Відібране правило запускається на виконання (спрацьовує). Суть спрацьовування полягає у виконанні дії, описаної у висновку правила. Такими діями можуть бути:
  • коректування критерію вибору правил;
  • запис, видалення або коректування фактів у базі фактів;
  • запис, видалення або коректування фактів у базі правил;
  • виконання інших дій (ведення діалогу з людиною, перевірка цілісності тощо).

Схематично процес інтерпретації правил зображено на рисунку:

рис.1 Інтерпретації правил

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

Стратегії керування висновуванням

Стратегії виведення

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

Розробляючи стратегію керування висновуванням, слід вирішити такі питання:

  • Яку точку в просторі станів обрати як початкову? Від вибору цієї точки залежить спосіб виконання пошуку — в прямому чи зворотному напрямку.
  • Якою має бути стратегія перебирання правил — углибину чи вшир?

Пряме і зворотне висновування

У системах з прямим висновуванням за відомими фактами відшукується факт, який з них випливає (див. мал. 2). Якщо такий факт вдається знайти, то він записується в базу фактів. Пряме висновування називають також висновуванням, керованим даними, або висновуванням, керованим посилками правил.

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

Пошук вглиб та вшир

Пошук вшир
Пошук вглиб

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

Див. також: Пошук у глибину
Див. також: Пошук у ширину

Проблеми

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

If A then B; If B then C; If C then A.

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

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

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

Література

Див.також