Подання знань.
ПМ або системи продукції використовують для представлення знань два поняття:
"Об'єкт-атрибут-значення"
"Правило продукції"
За допомогою (1) описуються декларативні знання в базі. Таке подання дозволяє при формуванні БЗ порядок опис об'єктів, дотримуючись їх певну ієрархію. Якщо до таких впорядкованим об'єктах в процесі логічного виведення застосовувати правила, то можна організувати звернення окремо до об'єкта, окремо до атрибута і окремо до значення.
Правило продукції являє собою засіб опису процедурних знань у вигляді MG-> MD
MG описує певну ситуацію в предметній області
MD описує собою одну дію або соволкупность дій, які необхідно виконати в разі виявлення відповідної ситуації в предметній області
Применеие кожного поточного правила змінює ситуацію на об'єкті, тому потрібно в наступному циклі перевірити весь набір правил, поки не зустрінеться умова зупину. І ліва і права частина правила будується на основі знань у вигляді "об'єкт-атрибут-значення" або більш складних конструкцій, побудованих на їх базі.
Продукційні системи використовують модульний принцип організації знань (цим вони відрізняються від традиційних систем, тому що ті використовують модульний принцип організації алгоритмів)
У продукційних моделях передбачається повна незалежність правил один від одного, тобто на одному рівні ієрархії одне правило не може викликати інше.
Продукційні моделі володіють високим ступенем модифікованості значень, дають можливість чітко відокремити метазнанія від предметних знань, що дозволяє навіть врамках однієї системи використовувати різні стратегії виведення.
2. Особливості організації логічного висновку.
Механізм або апарат логічного висновку продукційної моделі грунтується на принципі розпізнавання образів. Цей механізм називають інтерпретатором, який циклічно виконує 4 послідовні етапи (вибірку, зіставлення, вирішення конфлікту, дія або їх сукупність)
На кожному з перерахованих етапів інтерпретатор працює з БЗ, робочої пам'яттю, пам'яттю станів інтерпретатора.
Схема одного циклу роботи інтерпретатора наступна:
Запит користувача
На етапі вибірки проводиться активізація тієї частини даних і знань, на підставі яких може бути реалізований запит користувача.
Активізація знань проводиться на основі закладених у системі стратегії виведення. Найбільш часто на цьому етапі використовується операції заміни, додавання, видалення, за допомогою яких поповнюються переліки активних знань і змінюється порядок активізації об'єктів.
На етапі зіставлення, вибраного на попередньому етапі безліч активних правил Рv приводиться у відповідність обраному безлічі елементів робочої пам'яті Fv і визначається конфліктний набір правил, тобто правил з Рv і даних з Fv, на яких ці правила визначені.
Конфліктний набір - упорядковані послідовності Рv і Fv, який називається означивание.
Етап зіставлення вимагає проведення значного обсягу операцій, тому що для конфліктного набору слід перевірити всі умови правил на всіх поєднаннях активних елементів робочої пам'яті.
У ході вирішення конфлікту інтерпретатор вибирає один або кілька означіваніе, кіт. д.б. виконані в поточному циклі. Система будується таким чином, що на цьому етапі передбачається обов'язкова її реакція на зміну навколишнього середовища, а також передбачене. можливість придбання нових значень у тих випадках, коли виникають нові аспекти навколишнього середовища. У ході вирішення конфлікту з'являється необхідність координації дій декількох правил, кіт. за визначенням д.б. незалежні. Залежно від обраної моделі знань, для вирішення конфлікту м.б. використані наступні керуючі структуриіначе порядок вибору правил:
1-а керуюча структура - упорядкування правил
2-а керуюча структура - керуюча структура спеціальних випадків
Третій керуюча структура - віку елемента
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}, які дозволяють домогтися високої ефективності за рахунок керуючої структури, де перевага віддається правилами з посиланням на самий останній згенерований елемент "об'єкт-атрибут-значення".