Лекция 4. Продукционные модели знаний

Продукционные модели знаний.

Продукционные модели знаний занимают особое положение, т. к. они являются наиболее декларативным способом представления знаний. Продукционная модель представления знаний – это набор правил вила

ЕСЛИ <условие>, ТО <действие>,

где <условие> - образец для поиска в базе данных (утверждение о состоянии базы данных), <действие> - действие, выполняемое при успешном исходе поиска в базе (процедуры, которые могут изменять состояние базы данных). Действия могут быть промежуточными, выступающие далее как условия и целевыми, завершающими работу системы.

В продукционных моделях используются некоторые элементы логических моделей, что позволяет организовывать на них эффективные процедуры вывода, а с другой стороны, более наглядно отражают знания, чем классические логические модели. Правила вывода в этих моделях называются продукциями. Системы продукций – это набор правил, используемый как базы знаний, поэтому его называют еще базой правил. Продукции соответствуют навыкам в долгосрочной памяти человека. Подобно навыкам в долгосрочной памяти эти продукции не изменяются при работе системы. Они вызываются «по образцу» для решения данной проблемы. Рабочая память продукционной системы соответствует краткосрочной памяти, или текущей области внимания человека. Содержание рабочей области после решения задачи не сохраняется.

Примеры фактов и правил.

Факт 1. Зажженная плита – горячая.

Правило 1. Если положить руку на зажженную плиту, то можно обжечься.

В общем виде под продукцией понимается выражение следующего вида:

(I); Q; P; A => B; N,

здесь I – имя продукции, с помощью которого эта продукция выделяется из всего множества продукций. В качестве имени может выступать какое-либо словосочетание или порядковый номер продукции в их множестве, хранящемся в памяти системы.

. Q - характеризует сферу применения продукции. Примерами сфер применения могут быть «роботизированный участок», «приготовление пищи» и другие. Разделение знаний на отдельные сферы позволяет экономить время на поиск нужных знаний.

Основным элементом продукции является ее ядро: А => В. Интерпретация ядра продукции может быть различной, но чаще всего звучит так: ЕСЛИ А, ТО В, более сложные конструкции ядра допускают в правой части альтернативный выбор, например: ЕСЛИ А, ТО В1, ИНАЧЕ В2.

Элемент Р – условие применимости. Обычно Р представляет собой логическое выражение. Когда Р принимает значение «истина» ядро активизируется. Если Р «ложно», то ядро не может быть использовано.

Элемент N описывает постусловия продукции. Это действия, которые выполняются только в том случае, если ядро продукции реализовалось.

Если в памяти системы хранится некоторый набор продукций, то они образуют систему продукций. В системе продукций должны быть заданы специальные процедуры управления продукциями, с помощью которых происходит активизация продукций и выбор для выполнения той или иной продукции из числа активизированных. Продукционные системы имеют давнюю историю. Их ограничение – в применении к крупномасштабным задачам, т.к. большое число правил приводит к замедлению скорости вывода. Кроме того, продукционная модель не имеет механизма вывода из тупиковых состояний в процессе поиска. Она продолжает работать, пока не будут исчерпаны все допустимые продукции.

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

- простота и гибкость выделения знаний;

- отделение знаний от программы поиска;

- модульность продукционных правил (правила не могут вызывать другие правила);

- простота пополнения и модификации;

- возможность эвристического управления поиском;

- возможность трассировки «цепочки рассуждений»;

- простота механизма вывода;

- независимость от выбора языка программирования;

- для ПК это простой и точный механизм использования знаний с высокой однородностью, описанных по одному синтаксису;

- продукционные правила являются правдоподобной моделью решения задачи человеком.

Фрагмент управления транспортным роботом:

Правило 1: Если i-й накопитель пуст – перейти к i+1 накопителю.

Правило 2: Если в i-том накопителе есть детали И тележка робота не заполнена, то освободить накопитель и перейти к i+1 накопителю.

Правило 3: Если тележка робота заполнена, то отвезти детали на склад и вернуться к i-тому накопителю.

Продукционная система имеет три компонента. Это знания, представленные в виде системы продукций в базе правил (БП), образцы условий в рабочей памяти (РП) и механизм вывода (МВ) (рис. 6).

Рис.6. Машина (механизм) вывода.

Программа, управляющая перебором правил называется машиной вывода (интерпретатором правил). МВ выполняет две функции: а) просмотр существующих фактов из рабочей памяти (базы данных) и правил из базы знаний с добавлением (по мере возможности) в рабочую память новых фактов; б) определение порядка просмотра и применения правил.

Этот механизм управляет процессом консультации, сохраняя для пользователя информацию о полученных заключениях, и запрашивает у него информацию, когда для срабатывания очередного правила в РП оказывается недостаточно данных.

МВ представляет собой небольшую по объему программу и включает два компонента – один реализует вывод, второй управляет этим процессом.

Действие компонента вывода основано на применении правила, называемого modus ponens. «Если известно, что истинно утверждение А и существует правило ЕСЛИ А,ТО В, тогда утверждение В также истинно». Правила срабатывают, когда находятся факты, удовлетворяющие их левой части. «Если истинна посылка, то должно быть истинно и заключение». Компонент вывода должен функционировать даже при недостатке информации.

Управляющий компонент определяет порядок применения правил и выполняет четыре функции:

1. Сопоставление = образец правила сопоставляется с известным фактом.

2. Выбор – если в конкретной ситуации может быть применено сразу несколько правил, то из них выбирается одно, наиболее подходящее по заданному критерию (разрешение конфликтов).

3. Срабатывание – если образец правила при сопоставлении совпал с каким-либо фактом из РП, то правило срабатывает.

4. Действие – РП подвергается изменению путем добавления в нее заключения сработавшего правила. Если в правой части правила содержится указание на какое-либо действие, то оно выполняется.

Интерпретатор МВ) работает циклически. В каждом цикле он просматривает все правила, чтобы выявить те, которые совпадают с известными на данный момент фактами из РП. После выбора правило срабатывает, его заключение заносится в РП, и цикл повторяется снова. В одном цикле может сработать только одно правило.

Если несколько правил успешно сопоставлены с фактами, то МВ производит выбор по определенному критерию единственного правила, которое срабатывает в данном цикле.

Цикл работы МВ показан на рис.7.

Рис.7. Цикл работы механизма вывода.

Работа МВ зависит только от состояния РП и от состава базы знаний. На практике обычно учитывается история работы, т.е поведение МВ запоминается в памяти состояний, которая содержит протокол системы.

Пример:

П1. Если (отдых летом) И (человек активный)

ТО (ехать в горы)

П2. Если (любит солнце) ТО (отдых летом)

Предположим, что в систему поступили факты: человек активный и любит солнце.

1-проход.

Шаг 1. Пробуем П!, не работает (не хватает данных – отдых летом)

Шаг 2. Пробуем П2, работает, б базу поступает факт – отдых летом.

2-й проход.

Шаг 3. Пробуем П1, работает. Активизируется цель (ехать в горы), которая выступает как совет.

Стратегия управления выводом.

От метода поиска зависит порядок применения и срабатывания правил. Процедура выбора сводится к определению направления поиска и способа его осуществления.

Прямой и обратный вывод. В системах с прямым выводом по известным фактам отыскивается заключение, которое следует из этих фактов. Если такое заключение найдено, то оно заносится в РП. Такой вывод называют выводом, управляемым данными.

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

В системах с более сотен правил желательно использовать стратегию управления выводом, позволяющую минимизировать время поиска решения и тем самым повысить эффективность работы системы. К числу таких стратегий относятся поиск в глубину, поиск в ширину, разбиение на подзадачи и альфа-бета стратегия.

При поиске в глубину в качестве подцели выбирается та, которая соответствует следующему, более детальному уровню описания задачи.

При поиске в ширину анализируются все начальные варианты. Разбиение на подзадачи заключается в выделении подзадач, решение которых рассматривается как достижение промежуточных целей. Альфа-бета стратегия заключается в удалении ветвей, неперспективных для успешного поиска.

Работа продукционной системы инициируется начальным описанием (состоянием) задачи. Из продукционного множества правил выбираются правила, пригодные для применения на очередном шаге. Эти правила могут создавать так называемое конфликтное множество. Для выбора правил из конфликтного множества существуют стратегии разрешения конфликтов, которые могут быть достаточно простыми, например, выбор первого правила. Могут быть и сложными эвристическими правилами. Следует отметить, что конфликтные множества представляют собой простейшие базы целей.

Кроме базовой структуры продукционных систем необходимы дополнительные средства – управление данными, уточняющими смысл:

Триплет: объект – атрибут (необходимый признак) – значение;

Пример; робот – степень подвижности – 4.

Четверка: – атрибут (необходимый признак) – значение – степень достоверности.

Пример: сверло – материал Р!* - стойкость 25 мин. – достоверность 0,7.

Условная часть может состоять из одного или нескольких условий, соединенных связкой И. Заключительная часть показывает данные, которыми следует пополнить РП при выполнении условной части. На практике при необходимости расширяют эти правила. Например, используют связку ИЛИ. В условной части, вводят условную часть с вычислениями на основании содержимого РП, либо вводят заключительную часть с пометкой – не дополнять содержимое РП.

Визуально такое отношение можно представить в виде графа с древовидной структурой (рис. 8).

Рис. 8. Граф древовидной структуры.

Если существует множество правил, из которых выводится одно и то же заключение, то выполняется процедура ИЛИ над всеми заключениями из этих правил. Таким образом всю систему продукций можно представить в виде одного графа И/ИЛИ (рис. 9).

Рис.9. Граф и/или.

Система, реализующая прямую цепочку рассуждений, на основании имеющихся условий делает возможным логические выводы. Система, реализующая обратную цепочку рассуждений по имеющимся выводам, ищет необходимые для них условия.

По такому графу обратный вывод – это поиск пути на графе. Управление последовательностью поиска осуществляется механизмом вывода. Могут быть использованы различные стратегии поиска. Используются также системы с двунаправленными выводами, где сначала оценивается небольшой объем полученных данных и выбирается гипотеза (прямой вывод), а затем запрашиваются данные для принятия решения о пригодности данной гипотезы.

Для повышения эффективности функционирования ИС в проблемной области с увеличением числа правил используются методы группирования, упорядочения информации в РП, предварительной компиляции правил в виде графа.

Пример работы продукционной системы. Рассматривается роботизированный участок.

Правило 1: ЕСЛИ (станок без заготовки) (1)

И (заготовка на накопителе) (2)

ТО (робот подает заготовку на станок) (3)

Правило 2: ЕСЛИ (накопитель подал заготовку в загрузочную позицию) (4)

ТО (заготовка в загрузочной позиции)

Действия:

1. Допустим, в РП вносятся 1 и 4 образцы и рассматривается возможность применения правил. Сначала МВ сопоставляет образцы из условной части правил с образцами в РП.

2. Если все образцы имеются в РП, то условная часть считается истинной, в противном случае – ложной. Т.к. в условной части (2) отсутствует, то условная часть правила 1 считается ложной. Но правило 2 выполняется, т.к. посылка (4) верна, поэтому МВ выполняет его заключительную часть, и образец (2) заносится в РП.

3. Вторично применяется правило 1, т.к. правило 2 уже было применено и выбыло из числа кандидатов. Т.к. (1) истина и (2) истина, то (3) – вывод. В итоге правил, которые можно было бы применить не остается и система останавливается.

4. Для описания задач часто используют дерево решений.

В общем виде цепочки рассуждений при решении задач в продукционных системах можно представить в виде алгоритмов:

Прямая цепочка рассуждений:

1. Определить исходную переменную, запомнить ее значение;

2. Установить признак продолжения цикла в значение ложь;

3. Сделать первое правило текущим;

4. Если текущее правило простое -, то перейти к шагу 6;

5. Если в условной части правила один факт F1 истинен и содержится другой факт F2, в котором содержится неопределенная переменная, то запросить значение переменной из факта F2 у пользователя;

6. Если условная часть правила истинна и переменная из заключительной части не определена, то присвоить значение переменной, исключить правило из дальнейшего рассмотрения и установить признак продолжения цикла в значение истина;

7. Если не достигнуто последнее правило в БЗ, то сделать правило текущим и вернуться к шагу 4;

8. Если все переменные определены, то перейти к шагу 10;

9. Если признак продолжения цикла имеет значение истина, то вернуться к шагу 2;

10. Сообщить пользователю окончательный вывод;

11. Конец алгоритма.

Алгоритм прекращает работу, если выполняется одно из трех условий:

- все значения переменных определены;

- при переборе правил в БЗ ни одно из правил не было исключено из рассмотрения;

- все правила исключены из рассмотрения.

Обратная цепочка рассуждений:

1. Определить переменную логического вывода.

2. Найти правило, заключительная часть которого содержит переменную вывода.

3, Если такое правило не найдено, то сообщить пользователю, что вывод невозможен, и перейти к шагу 14, иначе поместить правило в стек.

4. Если переменная, соответствующая номеру условия правила в вершине стека, определена, то увеличить номер условия на 1 и перейти к шагу 8.

5. Найти правило, в заключительной части которого встречается переменная, соответствующая номеру условия.

6. Если правило не найдено или предыдущий вывод неверен (см. шаг 9), то запросить значение переменной у пользователя, увеличить номер условия на 1 и перейти к шагу 8.

7. Поместить найденное правило в стек и вернуться к правилу 4.

8. Если номер условия меньше или равен числу фактов в условной части правила, то вернуться к правилу 4.

9. Если условная часть истинна, то присвоить значение переменной из заключительной части правила, иначе предыдущий вывод неверен.

10. Удалить правило из стека.

11. Если переменная вывода определена, то перейти к шагу 13.

12. Если стек пуст, то вернуться к шагу 2.

13. Сообщить пользователю окончательный вывод.

14. Конец алгоритма.

Алгоритм прекращает работу, если выполняется одно из двух условий:

- значение переменной вывода определено;

- при полученных значениях переменных значение переменной вывода получить невозможно.

Пример 1.

Прямая цепочка рассуждений:

Пр.1. ЕСЛИ двигатель перегрелся, ТО мотор заклинит и заглохнет

Пр.2. ЕСЛИ мотор заклинит и заглохнет, ТО это приведет к денежным затратам.

Отправная точка – перегрев двигателя. Затем срабатывает условная часть первого правила. Так как ситуация удовлетворяет содержавшемуся в нем условию, согласно части ТО вводится новая ситуация – мотор заглохнет. Цепочка рассуждений продолжается.

Условие в части ЕСИ второго правила выполняется, следовательно вывод из части ТО приведет к решению задачи.

Обратная цепочка:

Автомобиль не заводится.

Пр.1. Если автомобиль не заводится И сел аккумулятор, ТО не подается ток в стартер.

Пр.2. Если в стартер не подается ток, ТО автомобиль не тронется места.

Обратная цепочка всегда начинается со следствия (ТО второго правила). Причина – если в стартер не подается ток. Почему не подается? Вывод – сел аккумулятор и автомобиль не заводится.

Система, реализующая прямую цепочку рассуждений. на основании имеющихся условий, делает возможные логические выводы; при реализации обратной цепочки рассуждений по имеющимся выводам система ищет необходимые для них условия.

Пример 2:

Имеется шахматная доска 3х3. Найти последовательность ходов конем, чтобы он ставился на каждую клетку только один раз. Начало движения с поля 1.

Возможные состояния:

Р1: Если(конь в поле 1, То (ход конем в поле 8;

Р2: Если(конь в поле 1, То (ход конем в поле 6;

Р3: Если(конь в поле 2, То (ход конем в поле 9;

Р4: Если(конь в поле 2, То (ход конем в поле 7;

Р5: Если(конь в поле 3, То (ход конем в поле 4;

Р6: Если(конь в поле 3, То (ход конем в поле 8;

Р7: Если(конь в поле 4, То (ход конем в поле 9;

Р8: Если(конь в поле 4, То (ход конем в поле 3;

Р9: Если(конь в поле 6, То (ход конем в поле 1;

Р10: Если(конь в поле 6, То (ход конем в поле 7;

Р11: Если(конь в поле 7, То (ход конем в поле 2;

Р12: Если(конь в поле 7, То (ход конем в поле 6;

Р13: Если(конь в поле 8, То (ход конем в поле 3;

Р14: Если(конь в поле 8, То (ход конем в поле 1;

Р15: Если(конь в поле 9, То (ход конем в поле 2;

Р16: Если(конь в поле 9, То (ход конем в поле 4.

Допустим, что необходимо переместить коня в поле 2 из поля 1. Вышеуказанное условие можно представить в виде операторов:

Move (1,8) Move (6,1)

Move (1,6) Move (6,7)

Move (2,9) Move (7,2)

Move (2,7) Move (7,6)

Move (3,4) Move (8,3)

Move (3,8) Move (8,1)

Move (4,9) Move (9,2)

Move (4,3) Move (9,4)

Это база знаний (база факторов).

Итерации для задачи:

№ итерации	Текущее поле	Целевое поле	Конфликтное множество	Активация правила
			1,2
			13,14
			5,6
			7,8
			15,16
				Выход

В итерациях 3 и 5 возникает конфликтное множество. Наиболее простой способ разрешения – выбор первого соответствующего перемещения, которое ведет в еще не посещаемое состояние.. Конфликтное множество – это простейшая база целей. Таким образом, если конь имеет систему движений, то последовательность движений 1-8-3-4=9=2.

Конфликтное множество – это список всех правил, имеющих удовлетворенные условия при некотором, текущем состоянии фактов и объектов и которые еще не выполнены.

Дата добавления: 2014-01-11