Rete-алгоритм

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

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

Рішенням проблеми є rete-алгоритм, відкритий Ч. Форгі в університеті Карнегі-Меллона в 1979 році при розробці експертної системи ОРS.

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

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

Недолік алгоритму - великі потреби в пам'яті.

В основу rete-алгоритма покладена структура даних, запропонована на підставі двох емпіричних спостережень:

§ Часова надмірність. Кожне з правил, звичайно змінює лише кілька фактів, а кожна з цих змін впливає тільки на кілька правил.

§ Структурна подоба. Однаковий шаблон часто виявляється в лівій частині більше чим одного правила.

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

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

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

Основні недоліки систем продукцій:

§ труднощі складання продукційного правила, адекватного елементу знання, тому що важко виразити складні правила;

§ неможливий виклик одного правила з іншого (зв'язок між правилами тільки через дані);

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

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

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

Дата добавления: 2014-01-07