Управление функционированием интерпретатора

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

(1) Сопоставить образцы в предпосылках правил и элементы данных в рабочей памяти.

(2) Если окажется, что можно активизировать более одного правила, выбрать одно из них; этот шаг называется разрешением конфликта.

(3) Применить выбранное правило. Результатом, скорее всего, будет добавление нового элемента данных в рабочую память и/или удаление какого-либо существующего элемента из рабочей памяти. Затем перейти к шагу 1.

Обычно перед началом этого циклического процесса в рабочую память вводится элемент, соответствующий исходному состоянию проблемы. На языке CLIPS такой элемент является вектором (initial-fact). Процесс останавливается, если будет обнаружен цикл, в котором ни одно из правил не может быть активизировано, или если активизированное правило явно содержит команду прекращения работы⁵. На шаге 2 система располагает набором пар, состоящих из правил и подстановок переменных, которые сформированы при сопоставлении образцов. Такие пары называются означиваниями (instantiations). Механизм разрешения конфликтов специфичен для каждой системы, т.е. для каждого интерпретатора правил. Можно, конечно, сформулировать и такой набор правил, что в любой ситуации только одно из них будет удовлетворяться (он называется детерминированным). Но в экспертных системах обычно используются недетерминированные наборы правил, поскольку в реальной жизни очень часто встречаются ситуации, которые позволяют использовать более одного правила.

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

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

Разрешение конфликтов

Как мы видели, в алгоритме функционирования продукционной системы введен специальный шаг принятия решения между шагами анализа ситуации и применения правила. В результате анализа соответствия текущих данных и предпосылок различных правил в имеющемся наборе можно сформировать список правил, которые могут быть применимы в данной ситуации. Такой набор иногда называют конфликтующий множеством (conflict set). В терминологии языка CLIPS этот список называется agenda — список заявок.

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

При выработке стратегии разрешения конфликтов обычно используется комбинация разных базовых механизмов, каждый из которых обладает свойственными только ему характеристиками. Производительность экспертной системы зависит от таких ключевых характеристик режима управления, как чувствительность и стабильность. Чувствительность характеризует, как быстро система будет реагировать на изменение среды, которое отражается в рабочей памяти, а стабильность характеризует степень консерватизма в поведении системы ([McDermott andForgy, 1978], [Brownston et al., 1985, Chapter 7]).

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

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

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

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

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

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

Разрешение конфликтов в CUPS

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

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

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

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