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

Продукционная модель в силу своей простоты получила наи­более широкое распространение. В этой модели знания представ­ляются в виде совокупности правил типа «ЕСЛИ — ТО». Системы обработки знаний, использующие такое представление, получили название продукционных систем (ПС). В состав экспертной системы продукционного типа входят база правил, база фактических дан­ных (рабочая память) и интерпретатор правил, реализующий оп­ределенный механизм логического вывода. Любое продукцион­ное правило, содержащееся в БЗ, состоит из двух частей: антеце­дента и консеквента. Антецедент представляет собой посылку правила (условную часть) и состоит из элементарных предложе­ний, соединенных логическими связками И, ИЛИ. Консеквент (заключение) включает одно или несколько предложений, кото­рые выражают либо некоторый факт, либо указание на определен­ное действие, подлежащее исполнению. Продукционные правила принято записывать в виде АНТЕЦЕДЕНТ ® КОНСЕКВЕНТ.

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

Примеры продукционных правил:

ЕСЛИ «двигатель не заводится» И «стартер двигателя не рабо­тает», ТО «неполадки в системе электропитания стартера»;

ЕСЛИ «животное имеет перья», ТО «животное - птица».

Антецеденты и консеквенты правил формируются из атрибу­тов и значений, например:

Атрибут Значение

Двигатель Не заводится

Стартер двигателя Не работает

Животное Имеет перья

Животное Птица

Любое правило состоит из одной (или нескольких) пары ат­рибут — значение. В рабочей памяти продукционной системы хра­нятся пары атрибут — значение, истинность которых установлена в процессе решения конкретной задачи к некоторому текущему моменту времени. Содержимое рабочей памяти изменяется в процессе решения задачи. Это происходит по мере срабатывания правил. Правило срабатывает, если при сопоставлении фактов, содержащихся в рабочей памяти, с антецедентом анализируемого правила имеет место совпадение, при этом заключение сработав­шего правила заносится в рабочую память. Поэтому в процессе логического вывода объем фактов в рабочей памяти, как прави­ло, увеличивается (уменьшаться он может в том случае, если дей­ствие какого-нибудь правила состоит в удалении фактов из рабо­чей памяти). В процессе логического вывода каждое правило из базы правил может сработать только один раз.

При описании реальных знаний конкретной предметной об­ласти может оказаться недостаточным представление фактов с помощью пар атрибут—значение. Более широкие возможности имеет способ описания с помощью триплетов объект—атри­бут—значение. В этом случае отдельная сущность предметной об­ласти рассматривается как объект, а данные, хранящиеся в рабо­чей памяти, показывают значения, которые принимают атрибуты этого объекта. Одним из преимуществ такого представления знаний являет­ся уточнение контекста, в котором применяются правила. С введением триплетов правила из базы правил могут срабаты­вать более одного раза в процессе одного логического вывода, по­скольку одно правило может применяться к различным экземп­лярам объекта (но не более одного раза к каждому экземпляру).

ПС обеспечивает управление процессом решения задачи по образцу и состоит из набора продукционных правил, рабочей памяти и цикла управления «распознавание-действие».

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

Рассмотрим простой пример работы ПС, которая сортирует строку, состоящую из символов a, b и c. В этом примере продукция является допустимой, если ее условие соответствует части строки в рабочей памяти. При выполнении правила подстрока, которая соответствовала его условию, заменяется строкой из правой части правила. В таблице представлено решение этой задачи.

Набор продукций:

1. ba → ab

2. ca → ac

3. cb → bc

Итерация	Рабочая память	Конфликтное множество	Применение правила
	cbaca	1, 2, 3
	cabca
	acbca	2, 3
	acbac	1, 3
	acabc
	aacbc
	aabcc	Ø	останов

Рассмотрим пример использования продукционных систем для решения шахматной задачи хода конем в упрощенном варианте на доске размером 3×3. Требуется найти такую последовательность ходов конем, при которой он ставится на каждую клетку только один раз (рис. 3.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)

Рис. 3.1. Шахматная доска 3×3 для задачи хода конем

с допустимыми ходами

Записанные на рис.3.1 предикаты move (x, y) составляют базу знаний (базу фактов) для задачи хода конем. Продукционные правила – это факты перемещений move, первый параметр которых определяет условие, а второй параметр определяет действие (сделать ход в поле, в которое конь может перейти). Продукционное множество правил для такой задачи приведено ниже.

P1: If (конь в поле 1) then (ход конем в поле 8)

P2: If (конь в поле 1) then (ход конем в поле 6)
P3: If (конь в поле 2) then (ход конем в поле 9)

P4: If (конь в поле 2) then (ход конем в поле 7)

P5: If (конь в поле 3) then (ход конем в поле 4)

P6: If (конь в поле 3) then (ход конем в поле 8)

P7: If (конь в поле 4) then (ход конем в поле 9)

P8: If (конь в поле 4) then (ход конем в поле 3)

P9: If (конь в поле 6) then (ход конем в поле 1)

P10: If (конь в поле 6) then (ход конем в поле 7)

P11: If (конь в поле 7) then (ход конем в поле 2)

P12: If (конь в поле 7) then (ход конем в поле 6)

P13: If (конь в поле 8) then (ход конем в поле 3)

P14: If (конь в поле 8) then (ход конем в поле 1)

P15: If (конь в поле 9) then (ход конем в поле 2)

P16: If (конь в поле 9) then (ход конем в поле 4)

Допустим, необходимо из исходного состояния (поле1) перейти в целевое состояние (поле 2). Итерации ПС для этого случая игры показаны в табл. 3.2.

Таблица 3.2

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

ПС могут порождать бесконечные циклы при поиске решения. В ПС эти циклы особенно трудно определить, потому что правила могут активизироваться в любом порядке. Например, если в 4-й итерации выбрать правило 8, то попадем в поле 3 и произойдет зацикливание. Самая простая стратегия разрешения конфликтов сводится к тому, чтобы выбирать первое соответствующее перемещение, которое ведет в еще не посещаемое состояние. Отметим, что конфликтное множество есть простейшая база целей.

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

Основные достоинства продукционных систем связаны с простотой представления знаний и организации логического вывода. Перечислим основные преимущества ПС:

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

2. Естественное соответствие поиску в пространстве состояний. Компоненты ПС естественно отображаются в логическую структуру поиска в пространстве состояний. Последовательные состояния рабочей памяти составляют вершины графа пространства состояний. Правила вывода – набор возможных переходов между состояниями. Разрешение конфликтов обеспечивает выбор перехода (ветви) в пространстве состояний. Эти правила упрощают выполнение, отладку и документирование алгоритмов поиска.

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

4. Управление на основе образцов. Задачи, решаемые с помощью программ ИИ, требуют особой гибкости при выполнении программы. Это вызвано еще и тем фактором, что правила в ПС могут запускаться в любой последовательности. Описание задачи, представляющее текущее состояние, определяет конфликтное множество и, следовательно, конкретный путь поиска и решения.

5. Возможности эвристического управления поиском.

6. Трассировка и трактовка. Модульность правил и итерационный характер их выполнения облегчает контроль за работой ПС. На каждой стадии «распознание-действие» рассматривается некоторое правило. Поскольку каждое правило соответствует отдельной «порции» знаний о методах решения задач, содержание правила должно давать ясную интерпретацию текущего состояния системы и действия. Более того, цепочка правил, используемых в процессе решения, отражает как путь на графе, так и цепочку рассуждений, приводящую к решению задачи человека-эксперта.

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

8. Правдоподобная модель решения задачи человеком.

К недостаткам систем продукций можно отнести следующие:

• отличие от структур знаний, свойственных человеку;

• неясность взаимных отношений правил;

• сложность оценки целостного образа знаний;

• низкая эффективность обработки знаний.

При разработке небольших систем (десятки правил) проявля­ются в основном положительные стороны систем продукций, од­нако при увеличении объема знаний более заметными становят­ся слабые стороны.

Дата добавления: 2015-07-10