Машина виведення

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Компоненти машини виведення[ред.ред. код]

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

Машина виведення є однією із складових експертної системи.

Машина виведення складається з двох компонентів:

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

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

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

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

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

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

Стратегії керування виведенням[ред.ред. код]

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

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

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

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

Пряме і зворотне виведення[ред.ред. код]

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

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

Пошук вглиб та вшир[ред.ред. код]

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

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

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

Проблеми[ред.ред. код]

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

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

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

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

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

Література[ред.ред. код]

Див.також[ред.ред. код]