ПЕРЕЛІК ЗНАНЬ ТА НАВИЧОК
Після опанування теми студент має знати:
• які основні завдання покладаються на машину висновку;
• створення поточного контексту пов’язане з вибором правила висновку з множини альтернативних правил;
• два базові підходи до побудови маршруту висновку;
• алгоритм, що здійснює побудову шляху висновку;
• в якому режимі здійснення циклів працює машина логічного виведення;
• стратегії розв’язання конфліктів правил.
• метод МЕА та його п’ять кроків.
• інформаційну СППР «Super Finance» («SF 2»);
• семантичні мовні інструкції та функції інтерпретатора системи «SF 2»; має вміти:
• записати алгоритм, що здійснює побудову шляху висновку;
• застосувати логічні правила висновку для логічного виведення;
• пояснити систему підстановок та її алфавіт;
• пояснити метод роботи машини логічного виведення;
• розробити стратегії вирішення конфліктів правил;
• програмувати базу знань в інформаційній СППР «Super Finance».
ЗМІСТ ПИТАНЬ З ТЕМИ
13.1. Машина логічного виведення
Машина виведення є інтепретатором правил, який використовує факти БЗ для вирішення шляху висновку. На вході машина висновку одержує мету консультації.
На кожному кроці висновку машина будує (нарощує) контекст (шлях висновку) і намагається підібрати правило, застосовне до цього контексту.
Чиста продукційна модель не має механізму виходу з тупикових станів у процесі пошуку; вона просто продовжує працювати доти, поки не будуть вичерпані всі допустимі продукції. Багато практичних реалізацій продукційних систем містять механізми повернення в попередній стан робочої пам’яті.
Контекст — це математична структура, відповідного зразку, якому додатково додана мета висновку. При цьому мета висновку може також задаватися у вигляді зразка — мети.
На машину висновку покладаються такі основні завдання:
1. Побудова маршруту висновку.
2. Інтерпретація правил висновку та їх застосування до поточного контексту.
3. Підвищення ефективності пошуку.
Завдання побудови шляху висновку полягає у відображенні в пам’яті ЕОМ послідовності кроків висновку, вживаних правил і набуваючого значення змінних. Множина значень змінних, відомих на даному кроці висновку утворює контекст. Мета побудовишляху — можливість її перевизначення з деякого раніше породженого контексту.
Створення поточного контексту пов’язане з вибором правила висновку з множини альтернативних правил — друге завдання. Від такого вибору зрештою залежить ефективність системи (швидкодія ПСШІ), тому необхідні заходи щодо забезпечення достатньої ефективності машини висновку. Існує два базові підходи до побудови шляху висновку. Перший заснований на логіці рішення в напрямі «від того, що відоме,
— до того, що треба знайти»; другий підхід, навпаки, використовує рух у зворотному напрямі: «від того, що треба знайти, — до того, що відоме». Перший підхід характеризує системи з прямим висновком, другий — системи зі зворотним висновком. Зворотний висновок застосовується в тих випадках, коли цілі відомі та їх порівняно небагато.
Простий алгоритм, що здійснює побудову шляху висновку, полягає в такому:
1) визначити початковий контекст;
2) занести всі змінні початкового контексту в чергу змінних логічного висновку, а їх значення (якщо задані) — у список змінних;
3) проглянути список змінних і знайти ту змінну, ім’я якої стоїть на початку черги змінних логічного висновку. Якщо змінна знайдена, записати в покажчик змінних умови, номер правила і число 1. Якщо змінна не знайдена, перейти до п. 6;
4) привласнити значення неініціалізованим змінним умовної частини знайденого правила якщо такі є. Імена змінних містяться в списку змінних умови правила. Перевірити всі умови правила «якщо» і у разі їх істинності звернутися до частини «то» правила;
5) привласнити значення змінної, що входить у частину «то» правила, і помістити її в кінець черги змінних логічного висновку;
6) видалити змінну, що стоїть на початку черги змінних логічного висновку, якщо вона більше не трапляється в умовній частині якого-небудь правила;
7) закінчити процес міркувань, щойно спорожніє черга змінних, логічного висновку. Якщо в черзі є ще змінні, повернутися до п. 3.
У системах діагностики частіше застосовується прямий висновок, тоді як у системах планування ефективніший зворотний. Крім того, використовується і комбінований висновок, заснований на поєднанні прямого і зворотного пошуку. Комбінований висновок називається також циклічним.
Проблема організації шляху висновку безпосередньо пов’язана з підвищенням ефективності пошуку. Зараз формалізуємо завдання організації шляху висновку. Для цього введемо по
няття дерева рішення. Розглянемо п’ятірку <S
0 , S F , A, R A R S >, де S
0 — початковий стан системи (об’єкту, моделі); S F — кінцевий (шуканий) стан системи (об’єкту, моделі);
А — алгоритм відображення F A SS???
0 ; R A — список обмежень на реалізацію алгоритму А; R S — список обмежень на «SF 2» (критерій).
Стан досліджуваної системи (об’єкта) S j , що безпосередньо досягається з S k , назвемо наступником S k , а стан S k — попередником S j . Граф Г(S, ?) з безліччю вершин станів S j ? S і дуг, що пов’язують попередників і наступників, утворює дерево рішення з коренем S
1 і листом, якщо: µ-й ярус у Г утворюють ті наступники (µ – 1)-го ярусу (µ = 1,2...), які не входять у яруси (µ – 2), (µ – 3) і т. д.; листям у Г є стани, усі наступники яких містяться у верхніх ярусах (виняток, можливо, становить S F ).
Усі ці завдання так чи інакше торкаються проблеми відшукання маршруту М у Г(S, ?), що зв’язує S
0 і S F . Деяка (будь-яка) закінчена частина цього маршруту називається трасою висновку.
Очевидно, що ефективність стратегії висновку визначається передусім тим, наскільки «близько» вона тримається маршруту М, а по-друге, наскільки великі витрати (пам’яті й процесорного(µ = 1,2...), які не входять у яруси (µ – 2), (µ – 3) і т. д.; листям у Г є стани, усі наступники яких містяться у верхніх ярусах (виняток, можливо, становить S F ).
Усі ці завдання так чи інакше торкаються проблеми відшукання маршруту М у Г(S, ?), що зв’язує S
0 і S F . Деяка (будь-яка) закінчена частина цього маршруту називається трасою висновку.
Очевидно, що ефективність стратегії висновку визначається передусім тим, наскільки «близько» вона тримається маршруту М, а по-друге, наскільки великі витрати (пам’яті й процесорногоняття дерева рішення. Розглянемо п’ятірку <S
0 , S F , A, R A R S >, де S
0 — початковий стан системи (об’єкту, моделі); S F — кінцевий (шуканий) стан системи (об’єкту, моделі);
А — алгоритм відображення F A SS???
0 ; R A — список обмежень на реалізацію алгоритму А; R S — список обмежень на «SF 2» (критерій).
Стан досліджуваної системи (об’єкта) S j , що безпосередньо досягається з S k , назвемо наступником S k , а стан S k — попередником S j . Граф Г(S, ?) з безліччю вершин станів S j ? S і дуг, що пов’язують попередників і наступників, утворює дерево рішення з коренем S
1 і листом, якщо:
• µ-й ярус у Г утворюють ті наступники (µ – 1)-го ярусу (µ = 1,2...), які не входять у яруси (µ – 2), (µ – 3) і т. д.;
• листям у Г є стани, усі наступники яких містяться у верхніх ярусах (виняток, можливо, становить S F ).
Усі ці завдання так чи інакше торкаються проблеми відшукання маршруту М у Г(S, ?), що зв’язує S
0 і S F . Деяка (будь-яка) закінчена частина цього маршруту називається трасою висновку.
Очевидно, що ефективність стратегії висновку визначається передусім тим, наскільки «близько» вона тримається маршруту М, а по-друге, наскільки великі витрати (пам’яті й процесорного
Т — загальне число вершин, пройдених у пошуку мети в Г(S, ?).
Очевидно, що детермінована оптимальна стратегія забезпечує максимальну міру близькості Р, яка дорівнює 1. Підвищення ефективності пошуку по-різному досягається в існуючих системах висновку: використання евристичних функцій оцінки; використання пріоритетів для правил; використання метаправил (правил для правил).
Машина логічного виведення працює в режимі здійснення циклів «розпізнавання — дія» (цикл «вибирання — виконання», цикл «ситуація — відгук», цикл «ситуація — дія»): вона послідовно в
Рис. 4.7. Схема циклу роботи механізму виведення
Метод роботи машини логічного виведення містить такі кроки:
1. Ініціалізація: робоча пам’ять ініціалізується зразком — початковим описом задачі в робочій пам’яті.
2. Цикл «розпізнавання — дія».
2.1. Ідентифікація (зіставлення, узгодження, розпізнавання)
— порівняння умов з лівих частин продукцій з фактами робочої пам’яті, що призводить до конкретизації й активізації правил.
часу) для реалізації цієї стратегії висновку. Як одна з оцінок ефективності стратегії пошуку визначена оцінка міри близькості шляху висновку і маршруту М у вигляді: де L — довжина знайденого шляху до мети (довжина М);
Конкретизація правила — сукупність узагальненого формулювання правила і значень використовуваних у ньому змінних.
Активізоване (реалізоване) — правило, всі умови якого задоволено. Усі активізовані правила заносяться до робочого списку правил.
Конфлікти правил виникають у робочому списку останніх, якщо одночасно активізується кілька правил.
Конфліктний набір правил (конфліктна множина, conflict set)
— набір конкретизованих правил, які активізовані протягом одного циклу обчислень.
Допустимі продукції — продукції, що містяться в конфліктній множині.
2.2. Розв’язання конфліктів правил (conflict resolution) — вибір зі сформованого списку заявок (конфліктної множини) єдиного правила, яке має бути виконане в поточній ситуації. Не маючи механізму розв’язання конфліктів, продукційна система буде не в змозі ефективно справлятися з браком детермінізму в наборі правил, обробкою виключень і переключенням уваги на визначений стиль розмірковувань. Іншими словами, поданню бракуватиме евристичних здібностей, а керувати функціонуванням такої системи буде досить важко, навіть якщо знання подано цілком коректно.
2.3. Дія (запуск правил) — зміна вмісту робочої пам’яті за допомогою послідовного виконання дій, зазначених у правій частині активізованого правила, обраного з робочого списку правил. Після виконання дії, відповідне правило видаляється з робочого списку правил або виконується його релаксація.
Терміну запуск у нейрофізіології (науці про те, як працює нервова система) відповідає термін збудження. У результаті стимуляції окрема нервова клітина випускає електричний сигнал. Подальша стимуляція, наскільки сильною вона б не була, не може змусити нейрон знову збудитися, поки не пройде якийсь короткий період часу. Цей феномен називається релаксацією. Експертні системи, засновані на правилах, створюються з використанням релаксації з метою запобігання тривіальних циклів. Для забезпечення релаксації розроблено різні методи. Наприклад, кожному факту після його введення в робочу пам’ять присвоюється унікальний ідентифікатор, який називається часовою оцінкою (timetag). Після того, як деяке правило запускається під впливом деякого факту, машина логічного виведення не запускає його знову під впливом того самого факту, якщо з моменту застосування його часової оцінки пройшло занадто мало часу.
2.4. Перевірка умов зупинення. Якщо хоча б одна з умов зупинення задовольняється, тоді закінчити роботу і повернути рішення, якщо воно знайдено, у протилежному випадку — повторити кроки 2.1—2.4.
Виокремлюють такі умови зупинення:
— переривання роботи користувачем;
— вичерпання всіх правил із продукційної пам’яті;
— виконання деякої умови, якій задовольняє вміст робочої пам’яті (наприклад, поява в ній якогось факту);
— невідповідність вмісту робочої пам’яті жодним умовам.
Протягом кожного циклу можуть бути активізовані й поміщені в робочий список правил багато інших правил. Крім того, у робочому списку правил залишаються результати активізації правил від попередніх циклів, якщо не відбувається деактивізація цих правил у зв’язку з тим, що їхні ліві частини більше не виконуються. У такий спосіб у ході виконання програми кількість активізованих правил у робочому списку правил змінюється. Залежно від програми раніше активізовані правила можуть завжди залишатися в робочому списку правил, але ніколи не вибиратися для запуску. Аналогічно деякі правила можуть ніколи не ставати активізованими. У подібних випадках варто повторно перевіряти призначення цих правил, оскільки або такі правила взагалі не потрібні, або їхні антецеденти неправильно спроектовано.
Використання різних стратегій перебору наявних знань, як правило, досить істотно впливає на характеристики ефективності програми. Ці стратегії визначають, як програма відшукує розв’язання проблеми в деякому просторі альтернатив. Як правило, не буває так, щоб дані, які має програма роботи з БЗ, дозволяли точно визначити ту область у цьому просторі, де є сенс шукати відповідь. Оскільки стратегія вирішення конфліктів впливає на продуктивність системи в цілому, у більшості програмних систем передбачаються визначені опції для підстроювання цього механізму.
Виокремлюють такі стратегії розв’язання конфліктів правил:
— після активізації правила воно не може бути запущене знову, поки не зміняться елементи робочої пам’яті, що відповідають його умовам. Найпростіший варіант реалізації цього механізму — видаляти зі списку заявок застосоване раніше правило. Іноді використовується інший варіант: зі списку видаляється правило, активізоване в попередньому циклі, що запобігає зацикленню, але якщо бажано повторювати саме цю процедуру, то в розпорядження програміс-
• Розмаїтість (рефракція — refraction)
• Новизна (recency) — віддає перевагу правилам, умови яких відповідають фактам, доданим у робочу пам’ять останніми. Це дозволяє зосередити пошук на одній лінії суджень. Елементи в робочій пам’яті в таких системах позначаються спеціальним атрибутом часу породження. Це дозволяє системі ранжирувати елементи в списку заявок відповідно до того, як давно введені в робочу пам’ять дані, що використовувалися при зіставленні, а потім пріоритет віддається правилам, які реагують на більш свіжі дані. Ідея полягає в тому, щоб випливати за поточною хвилею і менше уваги приділяти тим даним, що були давно сформовані. До них можна буде повернутися надалі, якщо поточний ланцюжок міркувань наштовхнеться на яку-небудь перешкоду.
Новизна правил — найбільш нові правила, уведені в систему в останню чергу, здобувають за замовчуванням найвищий пріоритет.
• Старовина правил — найбільш старі правила, уведені в систему в першу чергу, здобувають за замовчуванням найвищий пріоритет.
• Стратегія глибини — утілення стратегії новизни даних стосовно правил, що мають однаковий клас опуклості. Правила, обрані в список заявок на підставі даних, що були включені в робочу пам’ять порівняно недавно, розташовуються в цьому списку раніше за правила, при виборі яких використані більш старі дані. Тож, перевага віддається принципу пошуку в глибину в просторі станів проблеми, тобто правила, що є наслідком більш пізніх змін стану системи, мають визначений пріоритет.
• Стратегія ширини — протилежна стратегії глибини і призначається для реалізації пошуку в ширину в просторі станів проблеми. Правила, обрані в список заявок на підставі даних, що були включені в робочу пам’ять порівняно давно, розташовуються в цьому списку раніше за правила, при виборі яких використані більш свіжі дані.
• Стратегія складності (специфічність — specifity, принцип найбільш довгої умови) — спирається на розуміння «здорового глузду», що частина правил, які належать до вузького класу ситуацій, є важливішими від загальних правил, що їх відносять до широкого класу ситуацій, оскільки ця частина правила враховуює більше інформації про ситуацію, ніж загальні, і полягають у виборі з фронту готових продукцій тієї, у якої складність більше. Складність правила визначається кількістю операцій перевірки,
та надається функція відновлення, що дозволяє тимчасово призупинити механізм, який діє за замовчуванням.
• Стратегія простоти — протилежна стратегії складності: більш вище знаходження (більший пріоритет) у списку заявок під час реалізації цієї стратегії віддається тим правилам, складність яких нижча.
• LEX-стратегія — припускає спочатку видалення зі списку заявок усіх правил, що вже були раніше використані. Правила, що залишилися з рівним значенням опуклості, потім упорядковуються за новизною використовуваних даних. Якщо виявиться, що два правила використовують дані однакової новизни, то перевага віддається тому правилу, що залучає до аналізу передумов більше даних. Метод LEX практично ідентичний методу МЕА за одним винятком — у ньому бракує кроку 2, а на кроці 3 порівнюються всі елементи умов конкретизованих правил і пов’язаних з ними елементів робочої пам’яті (перші елементи умов конкретизованих правил є, як правило, лексемами задач у робочій пам’яті).
• МЕА-стратегія (Mean-Ends Analysis) багато в чому аналогічна LEX-стратегії, але в аналізі новизни беруться до уваги тільки перші умови в передумовах правил. Якщо виявиться, що в списку заявок виявилися два претенденти з однаковими показниками, то для вибору між ними застосовується механізм LEX-стратегії. Метод МЕА охоплює п’ять кроків.
Крок 1. Виключити з конфліктної множини правил ті, що вже були застосовані в попередньому циклі. Якщо після цього множина стала порожньою, припинити процес.
Крок 2. Порівняти новизну елементів у робочій пам’яті, що відповідають першим елементам умов у конкретизованих правилах, які залишилися в конфліктній множині. Пріоритет віддається тим правилам, що звертаються до найновіших елементів робочої пам’яті, — ці правила домінують над іншими. Якщо існує єдине
які потрібно виконати під час аналізу умов даного правила. Одне правило є більш специфічним (складним, конкретним), ніж інше, якщо воно містить більше умов, і, відповідно, складніше задовольняється, а виявляється, відповідає меншій кількості правил у робочій пам’яті й має пріоритет перед більш загальними правилами. Цю стратегію можна ефективно використовувати у роботі з винятками із загальних правил, коли знання і самі продукції добре структуровані прив’язкою до типових ситуацій, на яких задано відношення типу «частинне — загальне». Труднощі використання такого принципу полягають у тому, що треба заздалегідь упорядкувати умови за входженням одна до одної за відношенням «частинне — загальне».
Крок 3. Упорядкувати конкретизовані правила за новизною інших елементів умов у правилах. Якщо домінує одне правило, воно застосовується і потім процес припиняється. Якщо ж домінують два чи кілька правил, то вони залишаються в конфліктуючій множині, а інші видаляються з неї. Потім виконується перехід до кроку 4.
Крок 4. Якщо за критерієм новизни елементів умов відібрано кілька правил з рівними показниками, то порівнюється інший показник правил — показник специфіки. Перевага віддається правилу, застосування якого вимагає перевірки найбільшої кількості умов у робочій пам’яті. Якщо претендентів виявиться кілька, інші видаляються з конфліктної множини і виконується перехід до кроку 5.
Крок 5. Застосовується правило, обране довільно з тих, що залишилися у конфліктній множині, і процес припиняється.
Отже, стратегія МЕА поєднує в одному методі аналіз таких показників, як повторюваність, новизна і специфіка.
• Принцип «стосу книг» (частотна перевага) — заснована на ідеї, що найбільш часто використовувана продукція є найбільш корисною. Готові продукції ніби утворять «стосу», у якій порядок визначається нагромадженою частотою використання продукцій у минулому. На самому верху «стосу» знаходиться продукція, що використовувалася найчастіше. Під час актуалізації деякого фронту готових продукцій для виконання вибирається та продукція (чи ті продукції за наявності рівнобіжних технічних пристроїв), у якої частота використання є максимальною. Подібний принцип є особливо прийнятним, коли частота виконання підраховується з урахуванням деякої ситуації, за якої раніше вироблялася продукція, і це виконання мало позитивну оцінку. За такого зворотного зв’язку метод стосу книг може перетворитися на процедуру, що навчається та адаптується до тих завдань, що виникають у зовнішньому середовищі. Принцип стосу книг доцільно застосовувати, якщо продукції є відносно незалежними одна від одної.
• Принцип метапродукцій — заснований на ідеї введення в систему продукцій спеціальних метапродукцій (метаправил), завданням яких є організація керування в системі продукцій за можливості неоднозначного вибору із фронту готових продукцій.
таке правило, то воно обирається для застосування, після чого процес слід припинити. У протилежному разі, якщо є кілька домінуючих правил з рівнозначним пріоритетом, вони зберігаються в конфліктній множині, а інші з неї видаляються. Далі виконується перехід до кроку 3.
• Керування за іменами — засновано на задаванні для імен продукцій, що входять у деяку систему, певної формальної граматики або іншої процедури, що забезпечує звуження фронту готових продукцій і вибір з нього чергової продукції для виконання.
• Упорядкування на основі цілей — правила упорядковуються, принаймні частково, залежно від того, наскільки швидко вони приводять до досягнення мети. Виконується пошук випадків, мета яких відповідає поточній ситуації.
• Принцип пріоритетного вибору — пов’язаний з уведенням статичних або динамічних пріоритетів на продукції. Статичні пріоритети можуть формуватися апріорі на підставі відомостей про важливість продукційних правил у даній ПРГ. Ці відомості, як правило, являють собою інформацію, що береться у експерта. Динамічні пріоритети виробляються в процесі функціонування системи продукцій і можуть відбивати, наприклад, такий параметр, як час перебування продукції у фронті готових продукцій. До цього типу керування належить задавання послідовності пріоритетів за допомогою спеціальної каузальної семантичної мережі. У цьому випадку задається певний каузальний сценарій, рух за яким визначається виникаючими ситуаціями, і в кожній вершині якого задана функція вибору чергової продукції із фронту готових продукцій.
• Модель дошки оголошень (модель класної дошки) — стратегія розв’язання складних системних задач із залученням різнорідних джерел знань, які взаємодіють через загальне інформаційне поле, — модель керування, що успішно застосовується для вирішення завдань, які вимагають координації різних процесів або джерел знання, що ґрунтується на ідеї спускових функцій (рис. 4.8).
Рис. 4.8. Архітектура дошки оголошень Marketing Definition
Метою розроблення моделі дошки оголошень було створення такої системи, що компенсує обмеженість монотонних виведень і може застосовуватися для розв’язання складних проблем за рахунок використання механізму поділу джерел знань та їх пого-
Дошка оголошень (класна дошка — blackboard)
— центральна глобальна БЗ, призначена для зв’язку незалежних асинхронних джерел знань.
Як правило, на дошці оголошень виділяють спеціальні поля для формування умов застосовності ядер продукцій, різні для різних сфер застосування продукцій, спеціальні поля для запису результатів опрацьовування продукцій і для запису постумов, якщо вони адресовані іншим продукціям.
Кожне джерело знань (knowledge source) є групою однотипних продукційних правил та одержує свої дані від дошки оголошень, обробляє їх і повертає результати дошці оголошень для подальшого використання іншими джерелами знань. Це ізольовані процеси, що діють відповідно до власних специфікацій (опису). Тому за рівнобіжної обробки інформації або мультипроцесорної системи ці системи беруть участь у розв’язанні єдиної задачі незалежно одна від одної. Це асинхронна система, оскільки кожне джерело знань починає свою роботу, коли знаходить відповідні вхідні дані на дошці оголошень. Закінчивши обробку даних, воно повертає свої результати й очікує нових вхідних даних.
Якщо джерело знань на одному рівні не може обробити (осмислити) передані йому дані, то воно робить запит до відповідного джерела про нові дані. Потім, одержавши нові дані, робить ще одну спробу обробки їх або приймає іншу гіпотезу стосовно спочатку отриманих даних. Усі процеси є асинхронними і керованими на основі даних. Вони запускаються з появою вхідних даних і продовжують роботу, поки не закінчать завдання, потім повертають свої результати і чекають наступного завдання.
Одне із джерел знань, яке називається планувальником, обробляє повідомлення про результати обробки інформації, передані між іншими джерелами знань. Планувальник ранжирує результати діяльності кожного джерела знань і за допомогою пріоритетної черги забезпечує деякий напрямок розв’язання задачі. Якщо жодне з джерел знань не є активним, планувальник вирішує, що завдання завершене, і припиняє свою роботу. Із принципом дошки оголошень може комбінуватися принцип керування за допомогою метапродукцій, оскільки він вимагає перевірки деяких умов, що фіксуються в робочому полі пам’яті, а також інші принципи керування.
джених дій у загальній робочій пам’яті зі збереженням при цьому такої переваги продукційної системи, як модульність знань.
