Продукционная модель

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

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

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

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

В самом общем виде продукционное правило представляет собой набор (I, Q, P, A→B, N) следующих компонент:

I —имя продукции, с помощью которого данная продукция выделяется из всего множества продукций (имя может выражать суть продукции, смысл выполняемого ей действия).

Q —область применения продукции— часто система продукций может быть разделена на подсистемы, каждая из которых связана с решением определенного типа задачи в комплексе задач, что позволяет экономить время на поиск нужных знаний.

P —условие применимости ядра продукции. Обычно Р представляет собой логическое выражение (когда Р принимает значение «истина», ядро продукции активизируется, а если Р — «ложно», то ядро продукции не может быть использовано).

A→B — ядро продукции— основной элемент продукционной системы.

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

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

• детерминированные — при актуализации ядра и при выполнимости. "А" правая часть ядра выполняется обязательно, т.е. предложение реализуется с необходимостью;

• недетерминированные —при актуализации ядра и при выполнимости "А" правая часть ядра может выполняться или не выполняться, т.е. предложение реализуется с возможностью (интерпретация ядра в этом случае может, например, выглядеть так:«если А, то возможно В»). Возможность может определяться некоторыми оценками реализации ядра. Например, если задана вероятность выполнения В при актуализации А, то продукция может быть такой:«если А, то с вероятностью реализовать В».

Оценка реализации ядра может быть лингвистической, связанной с понятием, терм-множествалингвистической переменной, например:«если А, то с большей долей уверенности В». Возможны иные способы реализации ядра.

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

Особым типом являются прогнозирующие продукции, описывающие последствия, ожидаемые при актуализации А, например:«если А, то с вероятностью p можно ожидать В».

Основными элементами продукционных систем являются следующие:

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

Работа машины вывода

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

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

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

Компонент вывода действует на основании правила: «Если известно, что истинно утверждение А и существует правило вида “ЕСЛИ А, ТО В”, тогда утверждение В также истинно».

Правила срабатывают, когда находятся факты, удовлетворяющие их левой части: если истинна посылка, то должно быть истинно и заключение.

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

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

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

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

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

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

Стратегии управления выводом в продукционной системе

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

При разработке стратегии управления выводом важно определить два вопроса:

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

Существуют два метода осуществления поиска (способа вывода заключений):

• прямой вывод — путем построения прямой (от данных к цели поиска) цепочки рассуждений;
• обратный вывод — путем построения обратной (от цели, для ее подтверждения — к данным) цепочки рассуждений.

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

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

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

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

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

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

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

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

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

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

В ряде систем искусственного интеллекта используют комбинации сетевых (семантические сети) и продукционных моделей представления знаний. В таких моделях декларативные знания описываются в сетевом компоненте модели, а процедурные знания — в продукционном.

К достоинствам продукционной модели можно отнести: модульность структуры, естественность вывода (аналогия с рассуждениями человека-эксперта), простота модернизации и расширения (для внесения изменений в структуру, а, следовательно, и в процесс обработки, достаточно изменить правило).