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

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

Представление знаний.

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

«объект-атрибут-значение».

«правило продукции».

С помощью (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}, які дозволяють домогтися високої ефективності з допомогою керуючої структури, де перевагу надають правилам із посиланням останній сгенерированный елемент «объект-атрибут-значение».

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

Для підготовки даної праці були використані матеріали із російського сайту internet.