МПЗиО_9_17_ПродукцМодель (Лекции)

ПРЕДСТАВЛЕНИЕЗНАНИЙ:ПРОДУКЦИОННАЯМОДЕЛЬСОДЕРЖАНИЕ1. Продукционная модель ПЗ● правила продукции и продукционные2.3.4.5.6.системы (ПС)Основные компоненты и особенности ПСВывод в ПС● прямой и обратный● управление выводом● цикл работы ПСПродукционные языкиДостоинства и недостатки ПСЗаключение2ПОНЯТИЕ ПРОДУКЦИИ Продукция – это правило (выражение) вида:ситуация (условие)  действиеили(пред)посылка  заключениеp  qp – левая часть, q – правая часть Правила продукции удобны для представленияповерхностных процедурных знаний, в частности, дляэмпирических/эвристических знаний ПО:медицинаЕсли у вас t° > 38°С , то надо принять парацетамолбытовая химия:Если PH жидкости < 6, то разлившееся вещество –кислотаЕсли жидкость – кислота и пахнет уксусом, то этоуксусная кислота3СЕМАНТИКА ПРОДУКЦИИЕсли текущая ситуация – данные о решаемойзадаче (факты) согласуются с левой,условной частью правила продукции, товыполняется правая часть, задающая: Получение определённого заключения о задаче:добавление к текущему состоянию решаемойзадачи нового факта или гипотезы Внешнее воздействие: например, ввод/выводинформации Правила продукции часто используются вэкспертных системах (ЭС) ЭС– специальный класс систем ИИ, основанных назнаниях экспертов4ПРОДУКЦИОННАЯ МОДЕЛЬ ПЗ Единица знаний – правило продукции Последовательное применение правила продукцийк текущему состоянию задачи – порождение такназываемой цепочки выводаS1 r1 S2 r2 … ri Siгде Si – набор фактов, описывающих текущеесостояние решаемой задачи Процесс решения задачи (вывод) – поискрешающей цепочки правил продукций для решенияопределённой задачи исходя из заданных фактов Продукционная система (ПС) – специальныйвычислительный формализм5ОСНОВНЫЕ КОМПОНЕНТЫ ПСРабочая память:База фактовБаза знаний:База правилУправляющаястратегия(Системауправления)• предназначена для описания решаемойзадачи• в начальный момент – исходная информация• набор правил продукций, выражающих всовокупности знания в некоторой ПО• стратегия выбора и применения продукцийпри поиске решения задачи(т.е.

решающей цепочки продукций)УС последовательно определяет правило, используемое втекущий момент, и прекращает вычисления в нужный момент.Исполнение правил реализует интерпретатор продукций6ОСОБЕННОСТИ ПС● При любом способе вычислений, в любомалгоритме можно выделить стандартныевычислительные компоненты:данные, операции, управлениеПС основаны на полном и чётком разделении(независимости) этих компонент.РП + БЗ + управляющие знания● Модульность БЗ (набора продукций) – возможностьопределять правила независимо● «Недетерминированность»: выбор очереднойпродукции реализует УС, а не программист● ПС – продукционная парадигма программирования:rule-based programming7ВИДЫ УПРАВЛЯЮЩИХ СТРАТЕГИЙКлассификация по различным признакам:● возможность возврата в точках выбора применяемойпродукции● направление построения решающей цепочкипродукций:прямой или обратный вывод Прямой вывод в ПС: поиск решения – в прямомнаправлении от исходного (начального) состояния кцелевому состоянию (управляемый данными) Обратный вывод в ПС: формирование пробныхгипотез и проверка их на соответствие текущимфактам (управляемый целями, целевое состояние –начальная гипотеза)Пролог: режим возвратов (бэктрекинг) + обратный вывод8ПРИМЕР ПРЯМОГО ВЫВОДАРассмотрим различие двух видов УС на примереПусть БЗF&BZ(1)C&DF(2)AD(3)Начальное состояние РП – факты {A, B, C, E, G, H}Целевое состояние РП – наличие факта Z (условие останова)Тогда последовательные состояния РП:A, B,C, E,G, H3A, B, C,D, E,G, H2A, B, C,D, E, F,G, H1A, B, C,D, E, F,G, H, ZПод стрелками стоит номер применённого правила продукцийПодчеркнут новый, добавляемый факт9ПРИМЕР ОБРАТНОГО ВЫВОДАТа же самая БЗ:F&BZC&DFAD(1)(2)(3)Начальное состояние РП – факты {A, B, C, E, G, H}Целевое состояние РП – наличие факта Z (условие останова)Тогда:A, B, CZ? 1 F? 2 D? 3t!E, G, H● Последовательный поиск правила, которое приводит кустановлению нужного факта● По окончании: инверсия найденной цепочки правил● Изменяемая часть: Z, F, D10ПРЯМОЙ И ОБРАТНЫЙ ВЫВОД:СРАВНЕНИЕ● Наиболее эффективное направление поискарешения определяется структурой задачи● Если цели известны и их немного, то лучше обратныйвывод● Если цели неизвестны или их много, а исходных данныхмало, то лучше прямой вывод● В диагностических ЭС чаще применяется прямой вывод,а в ЭС планирования более эффективным оказываетсяобратный вывод● Иногда эффективен (если возможен) двусторонний поиск:движение в прямом и обратном направленииодновременно● При реализации ПС с прямым выводом обратный выводможет быть использован для её настройки/отладки11ПРЯМОЙ И ОБРАТНЫЙ ВЫВОД:ЗАМЕЧАНИЕН.

Нильсон: с формальной точки зрения между ПСс прямым и обратным выводом различия нет,но есть содержательное различие: В ПС с прямым выводом РП содержит описаниясостояний(заключения, сделанные по известным фактам),а продукции преобразуют состояния в состояния(точнее, в их описания)В ПС с обратным выводом РП содержит описаниецелей/подцелей (гипотез, которые надо подтвердить),а продукции преобразуют цели в подцели(точнее, в их описания)12МОНОТОННЫЙ И НЕМОНОТОННЫЙВЫВОДСравним вывод в ПС с выводом в логическихсистемах:● В логических системах – монотонный вывод, всёдоказанное остаётся истинным, множестводоказанных фактов монотонно возрастает● Чистый Пролог – монотонный вывод● В ПС в общем случае реализуем немонотонныйи монотонный вывод – из-за возможностиудаления фактов из РП● В рассмотренных на предыдущем слайдепримерах оба вывода (прямой и обратный) –монотонные (в правилах есть только добавлениеновых фактов, удаление фактов отсутствует)13ЦИКЛ РАБОТЫ ПСС ПРЯМЫМ ВЫВОДОМ1.

Сопоставление левых частей правил с фактами РП:поиск применимых правил продукций2. Разрешение конфликта: выбор одного правила согласноуправляющей стратегии3. Выполнение выбранного правила, при этом возможны: изменение РП (множества фактов) изменение БЗ изменение управляющей стратегииПовторение этого цикла, пока есть применимые правила Левая часть правил продукций обычно играет роль образцаданных, поэтому поиск часто называетсяпоиском по образцу Конфликтное множество – это множество найденныхправил, применимых в данный момент14СХЕМА РАБОТЫ ПС1КонфликтноемножествоправилСопоставление2РабочаяпамятьБазаправилКритерийвыбораправил (УС)РазрешениеконфликтаВыполняемоеправило3Действия изправой частиправила15УПРАВЛЕНИЕ ВЫВОДОМ В ПСУспешность вывода в ПС зависит отпроцедуры разрешения конфликтаВозможные принципы/стратегии:● Упорядочение элементов данных в РП: использование «возраста»– времени записи данных, тогда выбирается продукция,левая часть которой удовлетворяется на самых «свежих» данных,т.е.

записанных последними● Упорядочение продукций в конфликтном наборе● Применение метаправил, организующих управление выборомНапример: мета-правило может быть таким (ЭС MYCIN)► Если «инфекция» есть pelvic_abcess(условие на РП)► и в конфликтном наборе есть продукции, в левой части которыхупоминается grampos_rods (условие на левую часть продукции)► То продукции, в левой части которых используетсяenterobacteriaceal имеют больший приоритет16РАЗРЕШЕНИЕ КОНФЛИКТА:УПОРЯДОЧЕНИЕ ПРОДУКЦИЙ● По степени используемости (частоте): выбираетсяпродукция с максимальной частотой использования(принцип «стопки книг» – наиболее часто используемаяпродукция считается наиболее полезной)● По времени последнего использования: выбираетсяпродукция, которая была использована последней● По длине («жёсткости») условной части продукции:выбирается продукция с наиболее «длинным» условием(т.е.

выражающая специальные, частные случаи)● Посредством введения приоритета правил: Статический приоритет задается априори, на основаниисведений о важности продукции Динамический приоритет формируется в процессефункционирования ПС (может учитывать времянахождения продукции в конфликтном множестве)17ПРОДУКЦИОННЫЕ ЯЗЫКИ● ПС: определённая парадигма программирования,способ организации вычислений –rule-based programming,ситуационное, продукционное программирование● OPS-5 и CLIPS – продукционные языки, в обоих:● безвозвратный прямой вывод● немонотонный вывод● 2 вида фактов:● факты с упорядоченными атрибутами● факты с неупорядоченными именованнымиатрибутами CLIPS – больше встроенных средств и возможностей18ПРОДУКЦИОННЫЙ ЯЗЫК OPS-5● Реализован как надстройка над Лиспом (конец 70 гг.)● Запись фактов с упорядоченными атрибутами:(age Mike 27)(children Bob Liz Sam)● Запись фактов с неупорядоченными именованнымиатрибутами:(вещество ^класс кислота ^имя HCl^цвет бесцветное)● Правила продукций:Левая часть состоит из нужных фактов и/или их отрицанийПравая часть – последовательность действий:● make – создание факта● modify – изменение факта● remove – удаление факта● read – ввод данных● write – вывод данных19OPS-5: ПРИМЕРЫ ПРАВИЛПО – музыкальные инструменты:(p струнный? (инструмент ^струны да) ->(modify 1 ^тип струнный))(p контрабас? (инструмент ^тип смычковый^размер большой) –> (modify 1 ^имя контрабас))ПО – химия:(p реакция (вещество ^класс кислота)(вещество ^класс щелочь) -> (remove 1) (remove 2)(make (вещество ^класс соль))(р опр_хлорида (вещество ^имя AgNO3)(вещество ^цвет бесцветный ^класс соль^вид хлорид) -> (remove 1)(remove 2)(make (вещество ^класс соль ^имя AgCl^цвет белый ^осадок да)(make (вещество ^класс соль ^вид нитрат^цвет бесцветный))20ДОСТОИНСТВАПОДУКЦИОННОЙ МОДЕЛИ ПЗ● Простота создания и понимания правил продукций,выражающих самостоятельные фрагменты знаний● Удобство и простота пополнения и модификацииБЗ, т.е.