Вертикальне вимірювання цієї схеми відповідає ієрархії знань (рівень абстракції), а горизонтальне — ієрархії метапродукцій. Ієрархічна організація модуля ПСП розширює можливості систем продукцій і має високопаралельну структуру — властивість, що викликає нині все більший інтерес з погляду паралельних обчислень. Поняття ПСП може бути розширено до паралельнопослідовного модуля, загальну схему якого подано на рис. 4.5.
Система має безліч баз знань: Продукції
1 , ..., Продукції n , кожна з яких функціонує незалежно від інших, використовуючи власну БЗ. Після припинення роботи локальних процесорів необхідна інформація переноситься в загальну БЗ.
Загальні продукції редагують загальну БЗ, інформація з якої стає доступною кожному локальному процесу. Тож, кожне джерело знань на проміжному кроці обчислень може використовувати як послідовну, так і паралельну інформацію. Загальну БЗ називають також дошкою оголошень (black-board).
Рис. 4.5. Структура паралельно-послідовного ПСП
Незважаючи на те, що більшість сучасних ПСП є нині послідовними, майбутні ПСП стануть паралельними, успішно реалізовуваними на багатопроцесорних ЕОМ.
Як уже наголошувалося, більшість досліджень зі ПСШІ зосереджено на виборі відповідних засобів для подання знань, які забезпечували б високу швидкість роботи в системах, які використовують великі обсяги знань. Нині помітна тенденція використовувати не суто продукційне подання знань, а деяке поєднання, що
Це викликано бажанням досягти максимально високого рівня опису знань, який би наближався до рівня проблемноорієнтованих мов. Як правило, у таких системах декларативні знання подаються у вигляді фреймів, а процедурні — у вигляді продукцій. Використання комбінованих підходів надає нові можливості для ширшого застосування систем продукцій.
Підводячи підсумки викладеному вище, наголосимо, що скрізь ми проводили відмінність тільки між типами компонентів ПСП, а не між типами розв’язуваних задач. У принципі одні й ті самі задачі можна розв’язувати різними способами, причому їх ефективність багато в чому залежатиме від специфіки використовуваних знань.
Ці знання умовно можна поділити на три групи:
• представлені в базі (знання про завдання);
• закладені в продукції (знання про ПРГ);
• керуючі — управляючи (знання про процеси, стратегії і структури, використовувані для розв’язання задач).
Загальна проблема під час проектування спеціалізованих ПСП полягає в тому, як краще організувати ці три компоненти знань, щоби звести до мінімуму витрати результативного обчислювального процесу.
12.4. Управління висновком в системах продукцій
При описуванні ПРГ традиційно виокремлюють два види знань: логічні, використовувані у розв’язанні задач, і знання, що управляють, котрі описують основні стратегії і методи розв’язання задач. На ранніх етапах конструювання СП ці види знань не відділялися один від одного, і звичайна схема висновку в СП не передбачала ніяких засобів управління: продукція могла застосовуватися тільки у разі, коли були істинні умови її застосовності.
Проте в багатьох ПРГ необхідні засоби представлення управляючої інформації оскільки розв’язання задачі часто потребує знань про плани і послідовність дій. Крім того, у разі значних обсягів знань розміри дерев пошуку розв’язання задач виявляються дуже великими, що робить обидві процедури систематичного перебору (у глибину і ширину) надзвичайно непривабливими.
складається з таких широковідомих засобів, як фрейми і семантичні мережі.
Експліцитний поділ знань дає, на думку багатьох авторів, дві основні переваги:
• логічні знання (без управляючих), будуть чітким, коректним і лаконічним описом ПРГ;
• знання, що управляють (управляючі знання), впливають на ефективність системи, у результаті відділяння від логічних простіше покращувати і оптимізувати.
Отже, вироблення адекватних способів подання управляючих знань, які не змінили б суть СП і зберігали такі їх найважливіші властивості, як розширюваність і здібність до саморедагування, є одним з основних завдань у розробленні технологічних комплексів.
Управління висновком в СП поділяють на два основні типи: управління продукціями і управління даними.
Мова управління застосуванням продукцій
Опис процедур розв’язання конфлікту зводиться зазвичай до задання порядку застосування продукцій, який іноді називають дисципліною застосування. При цьому порядок може бути або детермінованим, коли на кожному кроці задається одна продукція, або недетермінованим, коли перевіряються умови кількох продукцій, але їх число значно менше від загальної кількості правил у системі.
За способом завдання можна виділити вбудовані порядки застосування продукцій, що настроюються. До вбудованих відносять засоби, які безпосередньо запрограмовані в інтерпретаторі системи. Прикладом вбудованого порядку застосування правил може служити схема вибору правил у нормальних алгоритмах Маркова. На кожному кроці висновку перевіряються умови тільки одного правила (на першому кроці — першого), якщо воно не застосовно, то відбувається перехід до наступного.
Якщо правило застосувалося, то на наступному кроці знову перевіряються умови першого правила і т. д. У системі продукції можна упорядковувати за частотою використання або за щонайдовшими списками умов, за пріоритетом тощо.
Крім того, у різних системах широко використовувалося введення міток і тегів, спеціальних логічних символів усередині продукції для завдання послідовності вибору. Такі засоби управління порядком застосування продукцій активно використовувалися в початковий період конструювання СП, коли під кожну процедуру розв’язання конфлікту програмувався свій інтерпретатор.
Першою спробою в цьому напрямі було використання в системі HEARSAY-II розбиття правил на підсистеми так, щоб у кожен момент часу розглядалося лише їх прийнятне число. Іншим засобом завдання порядку є метапродукції, використані в комплексі систем MYCIN-TEIRESIAS. Проте послідовність управляючої інформації, неможливо описати одними метапродукціями (необхідне введення метаметапродукцій і т. д.). По суті, ідея введення метапродукцій полягає в спробі задати всю можливу інформацію в системі однорідним чином.
Ще одним засобом управління порядком застосування правил є використання мов управління. Опишемо формули, що неформально управляють, і їх використання для висновку.
Нехай Р r = {< q i r i >}, i = 1 ... n, п 0 — множина продукцій, d — поточний стан БЗ. Мовою управління порядком задається формула, що управляє, описується множина продукцій, для яких на поточному кроці виведення t перевіряються умови застосовності.
Нехай Р r = {< q i r i >}, i = 1 ... n, п ? 0 — множина продукцій, d — поточний стан БЗ. Мовою управління порядком задається формула, що управляє, описується множина продукцій, для яких на поточному кроці виведення t перевіряються умови застосовності.
Такі множини називатимемо безліччю активованих продукцій A r , A r ? Р r . має бути істинною після перевірки, тобто знайдеться підстановка ? така, що q? ? d;
Кожна продукція рr =< q,r > у множині, що задається, може бути в одному з трьох станів: рr+
— умова продукції рr, активованої на кроці виведення t,
• рr+
— умова продукції рr, активованої на кроці виведення t,
Кожна продукція рr =< q,r > у множині, що задається, може бути в одному з трьох станів:
• рr+
— умова продукції рr, активованої на кроці виведення t,
— умова продукції рr, активованої на кроці виведення t, має бути помилковою після перевірки, тобто не існує підстановки ? такої, що q? ? d;
• рr–
• rp ) — продукція має бути активована, а значення її умов (істинне або помилкове) не впливає на перехід до наступного кроку
Якщо, наприклад, ?+=
321 ,,prprrpA r ) , то перехід до A r+1 відбудеться в тому випадку, якщо умови рr
2 істинні, а рr
3 помилкові. Істинність умов pr i не впливає на перехід до A r+1 . Вимога помилковості умов рr
1 є одним із засобів завдання негативного контексту, якщо він необхідний для висновку.
321 r r+1будеться в тому випадку, якщо умови рr
2 істинні, а рr
3 помилкові. Істинність умов pr i не впливає на перехід до A r+1 . Вимога помилковості умов рr
1 є одним із засобів завдання негативного контексту, якщо він необхідний для висновку. ir+1 ковості умов рr
1 є одним із засобів завдання негативного контексту, якщо він необхідний для висновку. висновку.
Якщо, наприклад, {} ?+=
321 ,,prprrpA r ) , то перехід до A r+1 відбудеться в тому випадку, якщо умови рr
2 істинні, а рr
3 помилкові. Істинність умов pr i не впливає на перехід до A r+1 . Вимога помилковості умов рr
1 є одним із засобів завдання негативного контексту, якщо він необхідний для висновку.
Мова управління є множиною правильно побудованих формул {?} над станами продукцій і бінарними операціями між ними, серед яких виділені такі перевірки умов: послідовна (•), одночасна (,) і альтернативна (;). Такі формули називаються управляючими, а множина продукцій із заданою управляючою формулою — системою структурованих продукцій.
Опишемо неформально процес висновку в Р r із формулою ?, що управляє, на деякому кроці t. Для кожного кроку виведення t по ? формується множина А r , яка складається з ?+ ??= rrrr pppA де
• + r p — множина продукцій, позначених станом +, тобто продукцій, умови яких мають бути істинні на поточному кроці виведення r;
• ? r p — множина продукцій, позначених станом –, тобто продукцій, умови яких мають бути помилкові на кроці виведення r;
• r p — множина продукцій, для яких не вимагається однозначної відповіді на питання, чи істинні їх умови застосовності на поточному кроці висновку, проте на думку експерта, їх розумно включити в число правил, у яких слід перевірити умови застосовності, і якщо вони істинні, то застосувати правила.
Після перевірки умов A r розпадається на дві непересічні підмножини: ?+ ?= rrr AAA, =? ?+ rr AA? де + r A і ? r A — множина усіх активованих продукцій з дійсними і помилковими умовами застосовності відповідно.
Якщо виконано умову ??++ ??? rrrr ApAp, то застосовуються всі продукції з множини + r A і відбувається перехід до наступного кроку висновку. Висновок закінчується успішно, якщо чергове A r порожнє. Якщо вказана умова не виконана або A r містить спеціальний виділений символ ?, то висновок «зависає».
Як видно з неформального опису, введення засобів управління дозволяє скорочувати число правил, що активуються. Проте це покладає велику відповідальність на експерта, оскільки вибрана ним дисципліна застосування правил може виявитися невдалою.
Розглянемо приклад використання мови управління для вирішення завдання визначення мови, що породжується в системі такою формальною граматикою: ,:
1 ABCSp? ,:
5 aAp? ,:
2 aAAp? ,:
6 bBp? ,:
3 bBBp? ,:
7 cCp? ,:
4 cCCp? ^ ^
Наведена контекстно-вільна граматика породжує мову: {}1,1,1???nmlcba nml .
Уведемо над цією граматикою формулу, що управляє, та описується виразом: ()
765 *
4321 ppppppp, де ( ) * задає ітеративне застосуванняправил p
2 , p
3 p
4 .
Даний вираз може бути зображений мережею переходів на рис. 4.6
Рис. 4.6. Мережа переходів для мови управління
У результаті використання управляючої мови множина слів створює мову {a n b n c n
|n ? 1}, яка не є контекстно-вільною.
Як видно навіть із цього невеликого прикладу, мова управління з застосуванням правил дозволяє значно спрощувати основні продукції.
12.5. Динамічне управління даними в процесі висновку
Другим типом управління є управління даними, які динамічно змінюються в процесі висновку. У загальному випадку це управління полягає у виборі підстановки або порядку обробки даних, що може істотно впливати на результат висновку в системі.
Традиційним способом завдання стратегії обробки є фіксація типів даних і програмування «вручну» способу їх обробки. Таке управління даними називають вбудованим. Наприклад, у різних версіях лінгвістичних процесорів використовувалися різноманітні вбудовані порядки обробки рядків: зліва направо, справа налі-
Основний недолік вбудованої стратегії обробки даних полягає в тому, що користувач змушений настроювати свої наступному знання на задану стратегію пошуку, яка, як правило, не є єдино можливою і єдино виправданою.
Природнішим є такий спосіб опису ПРГ, за якого експерт, не зв’язаний жорсткою стратегією, формулює спочатку продукції і лише після цього — правила обходу структур даних, використовуючи за необхідності в різних фрагментах даних різні стратегії. Такий спосіб задання управління даними називають таким, що настроюється. Він задається у вигляді лаконічної специфікації мовою управління даними.
Неформально мова управління даними аналогічна мові управління застосування продукцій і полягає в наступному. Для кожного поточного стану бази фактів d r кроку виведення r задається підмножина фактів dd A r ?, на яких (і лише на них) у нинішній момент висновку перевіряються умови застосовності активованих продукцій. Такі A r d називатимемо активованими даними. Оскільки дані в процесі висновку змінюються (додаються нові і, можливо, виключаються старі факти), то статистичний опис множини A r d до початку висновку неможливий, у зв’язку з чим необхідні засоби динамічного задання множин A r d.
Визначатимемо управління даними за деяким виділеним відношенням f
0 ) ? d r , залежну від поточного стану d r і f
0 ?F над термами, котре задає структуру M(d r , f
0 . У цій структурі між елементами визначається як мінімальна довжина шляху між ними, пара (центр, радіус), де центр — довільний елемент структури, радіус — натуральне число, задає в цій структурі границю пошуку, що містить у собі всі елементи структури, відстань до яких від центру не більше радіуса границі. Множину активованих даних складають ті факти з поточного d r , в які входять терми, належні границі пошуку. Границю пошуку називають іноді «вікном активації».
Центр і радіус поточної границі можуть бути задані явно (точною вказівкою) або обчислюватися через центр і радіус границі, визначені над структурою попереднього кроку висновку. В ре
r+1виходить з d r додаванням або викреслюванням деяких фактів.зультаті застосування продукцій формується d r+1 стан бази, який виходить з d r додаванням або викреслюванням деяких фактів.
во, з поверненням на початок рядка, без повернення та їх комбінації. Якщо над оброблюваними даними зафіксовано відношення часткового порядку, то прикладом можуть служити перебори в глибину і завширшки.
Розглянемо висновок в границі на деякому довільному кроці t. Нехай d r — поточний стан бази фактів, ? r — границя пошуку кроку виведення r. Якщо границя не порожня, то в ній перевіряються умови застосовності активованих продукцій кроку виведення r. Продукції з дійсними умовами застосовуються, що приводить до стану d r+1 . Якщо d r+1 містить спеціальний виділений символ невдалого висновку ?, то висновок «зависає». Інакше, коли поточна границя пошуку порожня, відбувається формування ? r+1 границі пошуку, центр і радіус якої обчислюються через відповідні компоненти ? r , а активовані дані беруться з поточного d r+1 стану БЗ. Якщо ? r+1 містить спеціальний виділений символ зупинки, то відбувається зупинка, що означає кінець опису стратегії, а отриманий стан БЗ містить результат, що виводиться продукціями із заданого початкового стану за фіксованим порядком обробки даних.
Описані вище мови управління висновком призначені для двох основних цілей. З одного боку, вони є досить простим і лаконічним засобом визначення вимог і специфікації логіки поведінки систем продукцій, з другого — це точки настроювання в програмних реалізаціях, що дають основу для побудови технологічного пакета систем продукцій. У межах цього пакета кожна з точок настроювання інтерпретується відповідним механізмом (особливо на етапі налагодження системи), а дисципліни застосування продукцій і порядки обробки даних, що найбільш часто трапляються, вбудовуються в технологічний пакет у вигляді стандартних модулів. Специфікація відповідної формули викликає ці модулі та збирає необхідну конфігурацію.
Терміни та поняття до теми
• Продукція — це пара «умова-дія», «ситуація-дія», «причинаслідство», «умова-висновок» і т. ін., котра визначає одну порцію знань, необхідних для вирішення завдання.
• Умовна частина правила — це зразок (шаблон), який визначає, коли це правило може бути застосовано для вирішення якого-небудь етапу завдання.
• Продукційна система — це модель обчислень, що забезпечує управління процесом розв’язання задачі за зразком і складається з набору продукційних правил, робочої пам’яті і циклу управління «розпізнавання-дія».
1 ,...,e n ).
• Фактом є впорядкований список вигляду (f A ,e
• Ситуацією — кінцева кон’юнкція фактів.
• Сфера застосування — визначає, для яких випадків може бути застосована продукція, тобто задає множину елементів, для якої продукція є застосовною.
• Детерміновані продукції можуть бути однозначними і альтернативними.
• Робоча пам’ять містить опис поточного стану спокою в процесі міркувань.
• Якщо таких правил більше ніж одне, то вони утворюють конфліктну множину, а продукції, що містяться в конфліктній множині, називаються допустимими.
• Продукційна система (production system) складається з продукційної пам’яті (production memory) — БЗ у вигляді продукційних правил, машини логічного виведення, а також робочої пам’яті, що містить дані (факти).
• В архітектурі програмних систем продукцій традиційно виокремлюють три основні компоненти: базу знань — пам’ять для зберігання поточної інформації про розв’язувану задачу, базу правил — множина правил (продукцій) та інтерпретатор (модуль управління).
• БЗ складається з наступних п’яти основних частин: пам’яті, каркаса, управління, контролю несумісності, асоціативної надбудови.
Питання для самоконтролю
1. Поясніть відомі формальні моделі систем продукцій (СП).
2. Охарактеризуйте формальні реляційні моделі обчислень СП.
3. Надайте визначення продукційної системи, продукції, факту, ситуації, кон’юнкції фактів, сфери застосування продукції.
4. Поясніть ядро продукції та склад.
5. Охарактеризуйте архітектуру програмних систем продукцій ПСП.
6. Поясніть склад БЗ та основні частини.
7. Охарактеризуйте операції над БЗ.
8. Поясніть динамічне управління даними в процесі висновку.
Завдання для індивідуальної роботи, обов’язкові та додаткові практичні завдання
1. Поясніть принципи класифікації ядра продукцій.
2. Опишить приклад продукційної системи, яка складається з продукційної пам’яті — бази знань у вигляді продукційних правил, машини логічного виведення, а також робочої пам’яті, що містить факти.
3. Дайте пояснення компонентам, які входять до архітектури програмних систем продукцій.
4. Приведіть праклади продукційних правил.
5. Для яких випадків може бути застосована продукція?
Література для поглибленого вивчення матеріалу
1. Люгер Дж. Ф. Искусственный интеллект. — М. : Вильямс, 2005.
— 864 с.
2. Інформаційні системи в економіці : монографія / под ред. Устенко С. В. — К. : КНЕУ, 2011. — 424 с.
3. Іванченко Г. Ф. Системи штучного інтелекту : навч. посіб. — К. : КНЕУ, 2011. — 382 с.
