Продукційні правила, продукційні системи
Методи реалізації продукційних правил
Методи реалізації продукційних правил пройшли еволюційний процес із середини ХХ ст. Оскільки спосіб подання знань на основі продукційних правил є класичним засобом створення експертних систем, їх розробникам необхідно мати системну інформацію щодо методичного змісту етапів розвитку концепції правил.
Продукційна система Поста
Продукційні системи були вперше використані в символічній логіці американським логіком Емілем Постом (Emil Post), тому ім'я цього вченого увійшло до назв зазначених систем. Основна ідея Посту полягала в тому, що на основі логічної та математичної систем можна представити набір правил, що встановлює порядок перетворення рядка символів на інший послідовний набір символів. Це означає, що продукційне правило, після отримання вхідного рядка (антецедента), здатне зробити новий рядок (консеквент), наприклад:
У цьому правилі стрілка означає, що один символьний рядок повинен бути перетворений на інший. Зазначене правило можна інтерпретувати за допомогою системи позначень IF-THEN наступним чином:
Слід зазначити, що маніпуляції з рядками ґрунтуються на синтаксисі, а не на семантиці. Іншими словами продукційна система Поста застосовується лише як спосіб перетворення одного рядка в інший, без розуміння значення слів: «постійний дохід» та «клієнт кредитоспроможний».
Продукційні правила також можуть мати кілька антецедентів, що поділяються зв'язкою AND, як показано в наступному прикладі:
Безумовно,Продукційні правила Посту були необхідні формування певної частини фундаменту експертних систем, але вони були достатніми для програмування товарів, мають практичну цінність. Основним обмеженням продукційних правил Посту, з погляду програмування, є відсутність стратегії управління, яка б регламентувати застосування правил. Зрозуміти це обмеження можна легко, представивши гіпотетичну ситуацію з візитом до бібліотеки. Якщо для пошуку потрібної книги не використовувати жодної системи управління процесом, можна витратити багато часу переглядаючи всі можливі варіанти.
Марківські алгоритми
p align="justify"> Наступним значним кроком у розробці методів застосування продукційних правил стало відкриття, зроблене Марковим, яке дозволило визначити структуру управління для виробничих систем.Марківський алгоритм - це впорядкована група продукцій, що застосовуються відповідно до пріоритетів до вхідного символьного рядка. Якщо правило з найвищим пріоритетом є непридатним, то використовується наступне правило з низьким пріоритетом і т.д. Марківський алгоритм завершує свою роботу після виявлення однієї з наступних умов: по-перше, остання продукція не була застосовна до рядка або, по-друге, була застосована продукція, яка закінчується крапкою.
Марківські алгоритми можуть застосовуватися до сегментів символьних рядків, починаючи зліва. Наприклад, продукційна система складається з одного правила:
Після її застосування, до вхідного рядка «ПРИВАННЯ» утворюється новий рядок «вилучити». Оскільки тепер продукція застосовується до нового рядка, остаточним результатом стає рядок видалити.
Марківські алгоритми використовують спеціальні символи. Зокрема, спеціальний символ позначає порожній рядок,що не містить символів. Наступна продукція видаляє всі входження символу А у вхідному рядку:
Інші спеціальні символи Марковського алгоритму можуть представляти інші набори символів та позначаються літерами а, b, c, …, y, z. Ці символи євідносимвольними змінними і є значною частиною сучасних мов експертних систем. Наприклад, наступне правило змінює місцями символи А і В рядку, якщо між ними є будь-який одиничний символ:
Як спеціальні знаки пунктуації в Марківському алгоритмі використовуються грецькі літери б, β і т.д. Грецькі літери застосовуються тому, що їх легко відрізнити від звичайних букв алфавіту.
Марківський алгоритм може застосовуватися як основа експертної системи, але він не є досить ефективним способом створення систем з великою кількістю правил. Такі системи вимагають алгоритму, який має повну інформацію про всі правила і може застосувати будь-яке з них, не роблячи спроби послідовно перевіряти кожне.
Rete-алгоритм
Вирішенням цієї проблеми єrete-алгоритм, розроблений Чарльзом Л. Форго (Charles L. Forgy) у 1979 році. Термін "rete-алгоритм" походить від латинського слова rete, що означає мережу. Відповідно до назви, rete-алгоритм функціонує як мережа, що призначена для зберігання великого обсягу знань. Він заснований на використанні динамічної структури даних, яка автоматично реорганізується з метою оптимізації пошуку аналогічно до дерева, який застосовується при індексації структур реляційних баз даних.
Rete-алгоритм є високошвидкісним засобом порівняння фактів із шаблонами, швидкодія якого досягається завдяки зберіганню в оперативній пам'яті інформації про правила, що знаходяться у мережі. У rete-алгоритмі втілено два емпіричні спостереження, на підставі яких було запропоновано структуру даних, покладених в основу:
- Тимчасова надмірність. Дія, що чиниться в результаті запуску одного з правил, зазвичай пов'язана з кількома фактами.
- Структурна подібність. Один і той же шаблон часто знаходиться в лівій частині більш ніж одного правила.
У rete-алгоритмі в циклах «розпізнавання-дія» контролюються лише зміни у погодженнях, тому в кожному циклі немає потреби узгоджувати факти з кожним правилом. Завдяки цьому суттєво підвищується швидкість узгодження фактів із антецедентами, оскільки статистичні дані, які не змінюються від циклу до циклу, можуть бути проігноровані.
Необхідною умовою практичної реалізації концепції продукційних правил використання формальної системи визначення продукцій. У загальному вигляді під формальною системою визначення розуміють систему позначень, яка виконує роль метамови для визначення синтаксису інших мов. Мови поділяються кілька типів: природні мови, логічні мови, мови математики, комп'ютерні мови тощо. Синтаксис мови визначає її форму, а семантика - значення її слів.
Однією з формальних систем позначень, використовуваних визначення продукцій, єнормальна форма Бекуса-Наура (Backus-Naur form — BNF). Для її детального розгляду скористаємося простим правилом граматики англійської мови, поданим у вигляді продукційного правила:
Відповідно до системи позначень форми Бекуса-Наура речення (sentence) складається з підлягає (subject) і присудка (verb), за якими слідує розділовий знак, що позначає кінець речення (end-mark). У цьому правилі кутові дужки(<>) і символ «:: = є символами метамови. Символ "::=" означає "визначений як". Він використовується замість символу "→", який застосовувався в Марківських алгоритмах продукційних правил.
Інтуїтивно певний вираз метамови, що є формальним ідентифікатором об'єкта, носить назвутерма. Терми, поміщені в кутові дужки, називається нетермінальними символами.Нетермінальний символ - це змінна, що представляє інший терм. У свою чергу, як такий інший терм може використовуватися нетермінальний або термінальний символ.
Термінальний символ не може бути замінений іншим символом і тому є константою. З його допомогою реалізується остання ланка ланцюга утворень. Наприклад, такі правила дозволяють розкривати значення нетермінальних символів, оскільки вони є термінальними символами, якими вони можуть бути замінені:
У цій метамові вертикальна характеристика означає «або».
Усі можливі пропозиції мови, тобто продукції, можуть бути створені шляхом послідовної заміни кожного нетермінального символу відповідними нетермінальними або термінальними символами, взятими з правої частини правил, доти, доки не будуть усунені всі нетермінальні символи. Як приклад застосування продукції даної мови можна навести такі пропозиції:
Гривня дорожчає. Долар дешевшає! Євро дешевшає?
Послідовність термінальних символів називається рядком символів мови. За умови, якщо рядок символів може бути отриманий із початкового символу шляхом заміни нетермінальних символів із застосуванням правил, які визначає, то це не називається дійсною пропозицією. В іншому випадку, рядок не вважається дійсним реченням, наприклад:
Повний набір продукційних правил, що однозначно визначає мову, називається її граматикою. Розглянуті в прикладі правила визначають деяку граматику, але вона дуже обмежена, оскільки забезпечує створення невеликої кількості можливої продукції. Складність граматики збільшується за рахунок різних доповнень, наприклад:
::= ::=на 1% на 5% на 10%
Проте, попри рівень досягнутої складності граматики, принцип системи визначення продукції залишається незмінним.