7.3.3. Варианты, используемые в концепции продукционной системы

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

Содержимое базы экспертизы

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

“Эстроген развал молекулы ((14-15), (13-17)) и передача водорода (1,12)”.

Такая условная запись позволяет выразить правило сжато и эффективно.

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

Структура управления

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

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

• Исчерпывающий перебор.

• Выбор правила с помощью оценки.

• Управление с помощью метаправил.

Исчерпывающий перебор. Данный тип управления используется в системе MYCIN. Эта стратегия удобна в тех случаях,

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

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

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

1) динамическая оценка приоритета правил в зависимости от их вклада в достижение цели;

2) приоритет правил устанавливается в зависимости от важности используемых фактов;

3) критерий специализации: выбирается наиболее специфичное правило (критерий, используемый в интерпретаторе Лисп);

4) выбор, определяемый графом, устанавливающим связь частичного порядка с правилом (DENDRAL) или осуществляемый с помощью программы (Gascuel, 1981);

5) выбор последнего использованного правила;

6) выбор правила, в котором упоминается последний использованный факт.

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

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

Эффективность продукционной системы

Время вычислений и получения выводов растет вместе с произведением числа правил на число записей в базе фактов. Наиболее важным фактором является число безуспешных попыток, предпринятых для выполнения правил. Можно построить различные фильтры, которые перед унификацией исключают бесполезные правила и факты. Дермотт (Dermott, 1978) предлагает четыре таких фильтра и приводит соответствующие формулы оценки времени их работы. Решение, принимаемое многими авторами, состоит в выполнении данного правила и последующем переносе выведенных фактов с реактивацией только таких правил, в которых эти факты упоминаются как посылки. Кроме того, в некоторых интерпретаторах предусматривается оценка выражений, общих для нескольких правил, только один раз за цикл и даже сохранение результатов вычислений при переходе от одного цикла к другому, когда соответствующие факты не изменяются (Gascuel, 1981), (Ghallab, 1981), (Forgy, 1981). Простые и доступные эвристические факты используются здесь с полной отдачей: при минимальных затратах времени они упрощают поиск соответствия между правилами и фактами.

Другим средством уменьшения числа попыток является автоматическая организация элементарных фактов в более сложные структуры для получения представления более высокого уровня. При этом с увеличением разнообразия рассматриваемых объектов уменьшается вероятность успеха унификации и одновременно уменьшается число бесполезных попыток. В работе (Minsky, 1975) была предложена структура прототипов типичных ситуаций (фреймов), использовавшаяся во многих системах (разд. 7.5).

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

Теперь перейдем к обзору существующих экспертных систем.