Продукційна модель (ПМ) знань і її використання в ЕС.

Представлення знань.

ПМ або системи продукції використовують для представлення знань два поняття:

"об'єкт-атрибут-значення"

"правило продукції "

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

Правило продукції являє собою засіб опису процедурних знань у вигляді MG-> MD

MG описує певну ситуацію в предметної області

MD описує собою одну дію або соволкупность дій, які необхідно виконати в разі виявлення відповідної ситуації в предметної області

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

Продукційні системи використовують модульний принцип організації знань (цим вони відрізняються від традиційних систем, тому що ті використовують модульний принцип організації алгоритмів)

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

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

2. Особливості організації логічного висновку.

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

На кожному з перерахованих етапів інтерпретатор працює з БЗ, робочої пам'яттю, пам'яттю станів інтерпретатора.

Схема одного циклу роботи інтерпретатора наступна:

Запит користувача

На етапі вибірки проводиться активізація тієї частини даних і знань, на підставі яких може бути реалізований запит користувача.

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

На етапі зіставлення, обраний на попередньому етапі безліч активних правил Рv приводиться у відповідність обраному безлічі елементів робочої пам'яті Fv і визначається конфліктний набір правил, тобто правил з Рv і даних з Fv, на яких ці правила визначені.

Конфліктний набір - впорядковані послідовності Рv і Fv, який називається означіваніе.

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

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

1-а керуюча структура - упорядкування правил

2-а керуюча структура - керуюча структура спеціальних випадків

3-я керуюча структура - віку елемента

4-а керуюча структура - відмінностей (подібності)

5-а керуюча структура - випадкові стратегії

(1) -- використовується як критерій вибору означіваній пріоритети або оцінки, кіт. приписуються відповідними правилами. У цьому випадку вводиться поняття пам'яті правила.

Оцінний показник вибирається довільно, частіше за все виходячи з наступних критеріїв:

1 -- динамічний пріоритет правила в залежності від його внеску в досягнення цілей.

2 -- динамічний пріоритет в залежності від важливості використовуваних фактів.

(2) - ісп. в як критерій зарание певного відносини двох правил, таке що якщо перше правило є спеціальним випадком, то воно вважається кращим

(3) - ісп. в як критерій часу перебування елемента в робочій пам'яті. Зазвичай вік визначається числом циклів роботи инт-ра або числом дій, кіт. виконувалися після створення елемента

(4) - ісп. в як критерій відмінності або подібності означіваній з поточного набору тим означіваніям, кот. були виконані в межах циклу

(5) - явл. небажаною, до них доводиться вдаватися в тих випадках, коли після застосування інших стратегій не відбувається вибору ніодного правила. К (5) можна віднести і вичерпний перебір правил. Він допустимо в невеликих за розміром БЗ в тих випадках, коли необхідно провести аналіз всіх можливих висновків і комбінацій.

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

У продукційних системах можна виділити два підходи, исп. при виведенні рішень:

1 -- безповоротний

2 - пробний

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

3. Організація пошуку рішень у простих та складних ЕС.

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

1 - розмір предметної області

2 -- змінність предметної області в часі іпространстве

3 - повнота моделі, описів предметної області

4 -- визначеність даних про розв'язуваної задачі

Вимоги користувача в системі може опису. Наст. параметрами:

1 - к-ть потрібних рішень (одне застосовне, декілька, або всі допустимі)

2 - обмеження на результат і спосіб його одержання.

Описані з помощбю зазначених пар в ЕС підрозділ-ся на прості (мала статична предметна область, повнота і визначеність даних) і складні. Для простих і складних ЕС повинні использ-ся різні процедури пошуку рішень.

процедури пошуку рішення значно відрізняються один від одного в простих і складних ЕС. Для простих ЕС найчастіше використовують пошук в просторі станів: метод редукції, евристичний пошук.

Метод пошук в просторі станів можна описати таким чином: нехай задана трійка (S0, F, SТ), де

S0-безліч початкових станів системи (запит)

F-безліч операторів, що відображають одні стану в інші.

ST-безліч кінцевих цільових станів системи

Обробити завдання (запит) - визначити таку послідовність операторів, кот. дозволить преобразовазовать початковий стан системи в кінцеве. Процес рішення представляється у вигляді графа

сигма = (x, y), де

x = (x0, x1 ... xТ) безліч нескінченних вершин графа, кожна з яких пов'язана з певними станами.

y - безліч пар (xi, xj), приналежності. множ. X

Якщо кожна пара (Xi; Xj) не впорядкована, то її називають ребром графа, а граф неорієнтовані.

Якщо для кожної пари (Xi; Xj) задано порядок, то її називають дугою, а граф орієнтованим.

Найчастіше метод використовується для орієнтованого графа.

У цьому випадку рішення задачі являє собою шлях на орієнтованому графі, де пари (Xij-1; Xij) належать Y, який призводить з початкового стану до цільового. На практиці дуг графа приписують вагові характеристики, які відображають їх пріоритетність в процесі обробки запиту. У цьому випадку вибір шляху зводиться до мінімізації або максимізації суми вагових характеристик дуг, які складають цей шлях. Таким чином граф j задає простір можливих станів предметної області. Побудова простору здійснюється за допомогою такої процедури: береться деяка вершина з безлічі початкових станів і до неї застосовуються всі можливі оператори, що породжують дочірні вершини. Цей процес інакше називається "Розкриттям вершин". Він продовжується до тих пір, поки не буде знайдена вершина, відповідна одному з цільових станів.

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

Метод II -- редукція.

При пошуку методом редукції рішення завдання зводиться до вирішення утворюють її підзадач. Процес повторюється для кожної наступної підзадачі до тих пір, поки не буде знайдено очевидне рішення для всієї їх сукупності. Процес розбиття задач на підзадачі представляється у вигляді орієнтованого графа j, який називається "І/або-граф". Кожна вершина "і/або-графа" представляє собою завдання або підзадачі і може бути кон'юнктівной ( "і"-вершиною) або діз'юнктівной ( "Або"-вершиною). Кон'юнктівние вершини разом зі своїми дочірніми вершинами інтерпретуються наступним чином: рішення завдання зводиться до вирішення всіх її подзадач, відповідних дочірнім вершин кон'юнктівной вершини.

Діз'юнктівние вершини можна інтерпретувати наступним чином: рішення завдання зводиться до рішення "з її подзадач, відповідних дочірнім вершин діз'юнктівной вершини. Пошук на "і/або-графі" зводиться до знаходження вирішального графа для "Початкової вершини.

З метою скорочення часу пошуку рішень використовуються евристичні методи пошуку.

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

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

Для складних ЕС застосовуються процедури пошуку, які призначені для роботи з тими видами складності, які притаманні системі. Тільки для ЕС з великим розміром простору пошуку доцільно розділити його на підпростори іншого рівня ієрархії. При цьому можуть виділятися підпростори, що описують конкретні групи явищ предметної області, а також абстрактні простору для опису будь-яких сутностей. Для останнього випадку характерно використання неповних описів, для яких в просторі більш низького рівня дається певна конкретизація.

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

І т.д. (дуже багато методів).

4. Приклади використання ПМ.

MYCIN - система для діагностики та лікування інфекційних захворювань.

Був розроблений кістковий мову, інакше - оболонка ЕС. Декларативні знання системи MYCIN описуються у вигляді "об'єкт-атрибут-значення" і кожній трійці приписується коефіцієнт впевненості, що визначає ступінь надійності знань. Процедурні знання описані у вигляді класичного правила продукції. Механізм логічного виведення заснований на зворотному ланцюжку міркувань. Пошук проводиться в ієрархічно упорядкованому просторі станів.

У системі EMYCIN (оболонка) посилена предметної області стосовно MYCIN функція редагування БЗ, доведена до високого рівня система пояснення ходу рішення завдання, а також апарат навчання системи. Написаний на ФОРТРАНе.

OPS-5. Універсальна мова інженерії знань, призначений для розробки ЕС, що використовуються в комерційних додатках. Розробник - університет Корнегі-Меллон. Декларативні знання в системі описані у вигляді "Об'єкт-атрибут-значення". Процедурні знання описані у вигляді класичних правил продукції. У механізмі логічного висновку використовується стратегія прямої ланцюжка міркувань, реалізується метод застосування одного і того ж правила в різних контекстах; для формування конфлікту набору та вирішення конфлікту використовуються спеціальні методи (RETELEX), які дозволяють домогтися високої ефективності за рахунок керуючої структури, де перевага віддається правилами з посиланням на самий останній згенерований елемент "об'єкт-атрибут-значення".

Список літератури

Для підготовки даної роботи були використані матеріали з сайту http://www.parny.by.ru/