Интерпретатор правил и управление выводом

При использовании продукционной модели представления знаний БЗ состоит из набора правил, а программа, управляющая перебором правил, называется интерпретатором правил, или машиной вывода. Интерпретатор правил – это программа, имитирующая логический вывод эксперта, пользующегося продукционной БЗ для интерпретации поступивших в систему данных [8].

Обычно он выполняет две функции:

1. Просмотр существующих данных из БД и правил из БЗ и добавление в БД новых фактов.

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

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

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

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

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

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

4. Действие – БД подвергается изменению путем добавления в нее заключения сработавшего правила.

Интерпретатор правил работает циклически (рис.4.1).

Рис. 4.1. Цикл работы интерпретатора правил

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

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

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

- исходная точка в пространстве состояний. От выбора этой точки зависит метод осуществления поиска – в прямом или обратном направлении;

- метод и стратегия перебора – в глубину, в ширину, по подзадачам.

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

Пример 4.1. Пусть имеется фрагмент БЗ из двух правил:

П1: Если «отдых летом» и «человек активный», то «ехать в горы».

П2: Если «любит солнце», то «отдых летом».

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

Прямой вывод

Первый проход БЗ:

Шаг 1. П1 не работает, поскольку не хватает данных «отдых летом».

Шаг 2. П2 срабатывает, в БД поступает факт «отдых летом».

Второй проход БЗ:

Шаг 3. П1 срабатывает, активизируя цель «ехать в горы», которая выступает как совет, который дает ЭС.

Обратный вывод

Первый проход БЗ:

Шаг 1. Цель – «ехать в горы»: пробуем П1-данных «отдых
летом» – нет. Они становятся новой целью, и ищется правило, где она находится в правой части.

Шаг 2. Цель «отдых летом»: правило П2 подтверждает цель и активизирует ее.

Второй проход БЗ:

Шаг 3. Правило П1 подтверждает искомую цель.

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

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

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

Семантические сети – это общее название методов описания, использующих сети, ими же называют один из способов представления знаний. На основе сетей осуществляются выводы, однако для этого необходимы специальные алгоритмы. Поскольку семантические сети являются собирательным названием систем представления, использующих сети, нет смысла определять для них специфические алгоритмы выводов. Для каждого конкретного формализма определяются собственные правила вывода, поэтому усиливается элемент произвольности, вносимый человеком. Выводы, которые достаточно тщательно не проверены, таят в себе угрозу создания противоречий. Следовательно, в семантических сетях необходимо больше, чем в продукционных системах, уделять внимания таким обстоятельствам, как устранение противоречий. Сама система такими возможностями не обладает, и потому во многих случаях эта функция возлагается на человека. Просматривая все знания, человек способен управлять их непротиворечивостью, однако, если объем знаний будет увеличиваться, то их представление резко усложнится, чем ограничит круг решаемых проблем сравнительно небольшими проблемами [11].