АЛГОРИТМІЧНІ МЕТОДИ ПРИСКОРЕННЯ ПОШУКУ

Алгоритми RETEі TREAT

Найбільш відомим методом прискорення резолюції правил є алгоритм RETE , створений Чарльзом Фордж в 1982 р [1] і використовується в експертних системах CLIPS, JESS, SOAR і ін.

В основу алгоритму покладено префіксне дерево, вузлами якого є умови правил. У кожному вузлі префіксного дерева створюється список фактів з бази знань, які задовольняють умовам правила. Коли факти додаються в робочу пам'ять, створюються елементи робочої пам'яті (WME - working memory elements). Кожен елемент робочої пам'яті може містити один кортеж, або кожен факт може бути представлений набором елементів робочої пам'яті, де кожен елемент містить кортеж фіксованою довжини, зазвичай триплет.

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

Мал. 3.1 ілюструє альфа- і бета-мережі для простої бази знань, яка описує розміщення на столі чотирьох ящиків 51, 52, 53 і 54. Розміщення ящиків на столі описується дев'ятьма фактами w 1 - Ш9.

Правило виглядає наступним чином:

Р : <х>, <у> - це стопка з двох ящиків, що стоїть зліва від червоного ящика, якщо (<х> на <г />) і (<г /> зліва від <г>) і (колір <г >-червоний).

Умови правила:

З 1: (<х> на <у> );

С2: (<у > зліва від <г>); СЗ: (колір - червоний).

Елемент альфа-пам'яті для умови С1 включає в себе факти w 1, w2, w4, w8, що встановлюють відносини «стоїть на». Другій умові С2 правила 51 відповідають факти гс5, wl , а третій умові - факти w 3 і w9 (ящик має червоний колір).

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

Вузьким місцем алгоритму Кеті є необхідність корекції префіксного дерева при зміні, додаванні або видаленні фактів бази знань. При кожній модифікації бази фактів префіксне дерево повинно будуватися заново або модифікуватися. Більшість модифікацій алгоритму RETE, наприклад Modify- in-place, Scaffolding, Decision Tree, націлені саме на зміну префіксного дерева [2] . Тим часом модифікація безлічі фактів відбувається в системах ШІ постійно, оскільки кожне правило дає в якості результату нові факти, які повинні відразу ж використовуватися в ході резолюції.

Альфа- і бета-дерева алгоритму RETE

Мал. 3.1. Альфа- і бета-дерева алгоритму RETE [ :

- альфа-пам'ять; - бета-пам'ять; - бета-вузли об'єднання

1 Doorenbos R. В. Production Matching for Large Learning Systems. PhD Theses. California: University of South California, 1995.

Експериментальні дослідження швидкодії алгоритму RETE показують прискорення приблизно на три порядки в порівнянні з наївним логічним висновком 1 .

Іптрепретатор в продукційних системах повторює в циклі наступні операції.

  • 1. Зіставлення. Умови кожного правила порівнюються з поточної робочої пам'яттю, в якій зберігаються факти. Кожна підмножина елементів робочої пам'яті, що задовольняє умовам правила, називається екземпляром ( instantiation ). Всі екземпляри об'єднуються в конфліктний набір {conflict, set).
  • 2. Відбір. З конфліктного набору вибирається підмножина екземплярів, які відповідають певному попередньо заданому критерію. На практиці одиночний екземпляр витягується з конфліктного набору на основі новизни фактів в робочій пам'яті.
  • 3. Дія. Виконання дії відповідно до результуючої частиною правила.

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

Алгоритм TREAT , запропонований Даніелем Міранкером в 1987 р [3] [4] , ґрунтується на наступних двох спостереженнях. Припустимо, що в продукционной системі немає умов з запереченням. Якщо єдина дія в результуючої частини правила - додавання нового факту в робочу пам'ять, то конфліктний набір залишається незмінним за винятком додавання нових екземплярів, що містять цей новий факт. Друге спостереження: якщо єдина дія правила полягає у видаленні елемента робочої пам'яті, то нові правила не створюються, а існуючі екземпляри, які містять віддалені факти, стають недійсними.

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

Даний малюнок ілюструє процеси додавання і видалення фактів в алгоритмі TREAT. На рис. 3.2я показано початковий стан робочої пам'яті для одного правила до умов Л, В, С, де А = ос >, В = <х, у >, С = >. Конфліктний набір для наявних фактів <Л1, В 12, 523, 534, СЗ, С2> утворюється об'єднанням кортежів:

Додавання нового факту Л2 зачіпає всі умови Л, 5, С, в результаті об'єднання фактів робочої пам'яті для цих умов конфліктний набір поповнюється новим кортежем {Л2, 523, СЗ}. При видаленні факту Л2 необхідно тільки видалення цього кортежу {Л2, 523, СЗ}, створеного раніше при додаванні факту Л2. Якщо відбувається зміна існуючого факту, то це може бути реалізовано через послідовне видалення існуючого і додавання зміненого факту.

Дослідження швидкодії алгоритму TREAT , проведені в роботі Міранкера [5] , демонструють подвоєну швидкість в порівнянні з RETE на операціях додавання і видалення фактів. Тим часом ілюстрації роботи алгоритмів RETE і TREAT наочно демонструють, що по суті обидва цих алгоритму припускають зберігання готових наборів, які залишається тільки підставити в умови правила.

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

Алгоритм TREAT  при додаванні і видаленні фактів

Мал. 3.2. Алгоритм TREAT при додаванні і видаленні фактів:

а - вихідний стан; б - цикл додавання; в - цикл видалення

  • [1] Forgy С. RETE: A Fast Algorithm for the Many Pattern / Many Object PatternMatch Problem // Artificial Intelligence. 1982. № 19.
  • [2] Див .: Doorenbos R. В. Production Matching for Large Learning Systems.; Tambe M., Kalp D., Rosenbloom PS An Efficient Algorithm for Production Systemswith Linear -Time Match // Proceedings of the Fourth IEEE International Conferenceon Tools with Artificial Intelligence. Одна тисяча дев'ятсот дев'яносто дві.
  • [3] Див .: Безсмертний І. А. Інтелектуальні системи на продукціонноймоделі знань. Проблеми практичної реалізації. Saarbriicken: LambertAcademic Publishing, 2012.
  • [4] Miranker DP TREAT: A Better Match Algorithm for Production Systems // Proceedings of the 6th National Conference on Artificial Intelligence . Seattle: AAAI, 1987. URL: http://www.aaai.org/Papers/AAAI/1987/AAAI87-008.pdf
  • [5] Див .: MimnkerD. Р. TREAT: A Better Match Algorithm for Production Systems.
 
Переглянути оригінал
< Попер   ЗМІСТ   ОРИГІНАЛ   Наст >