Структура ПИЛОТ-программ и управление выводом

Пример разработки системы, основанной на знаниях

□ Продукционно-фреймовый ЯПЗ PIL0T/2

□ Психодиагностика - пример предметной области для построения экспертных систем

□ Разработка и реализация психодиагностической ЭС «Cattell»

7.1. Продукционно-фреймовый ЯПЗ PILOT/2

В любом языке программирования можно выделить три составляющие: декла­ративную (описания данных), процедурную (правила преобразования данных) и инференциальную (правила управления компонентами процедурной, а иногда и декларативной составляющих). Не исключение в этом смысле и языки представления знаний, но их специфика в том, что описания здесь в основном структурные, а данные могут быть активными за счет присоединенных процедур, обес­печивающих «вычисление» их значений; правила преобразования данных ориентированы скорее на то, чтобы явно специфицировать, что должно быть получено, не концентрируя без необходимости внимание программиста на том, как дости­гается результат. Но самое большое отличие ЯПЗ от других языков в инференциальной компоненте, которая реализует некоторую (чаще всего встроенную) стратегию поиска решения. Такой подход предполагает, что при выполнении

ЯПЗ-программ всегда существует «арбитр», функцией которого является оцен­ка «текущей ситуации» и выбор пути движения от нее к целевой.

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

В качестве примера развитых средств продукционно-фреймового программирования баз знаний ниже обсуждается ЯПЗ PILOT/2, разработанный в рамках проекта PiES WorkBench [Khoroshevsky, 1994b]. Его специфика в том, что здесь введены явно достаточно мощные средства программирования инференциальной составляющей и выразительные описания образцов, а также удобный и открытый для расширения набор операторов преобразования данных в основной и внешней памяти.

В общем случае PILOT-программа содержит две основные (декларативная и про­цедурная) и две вспомогательные (включение файлов и переопределение строк) компоненты. Декларативная часть состоит из элементов, специфицирующих пе­ременные, прототипы функций и/или процедур, а также необходимые базы зна­ний. Продукционная часть состоит из секций, которые, в свою очередь, содержат продукции. Инференциальная составляющая присутствует в ЯПЗ PILOT/2 не­явным образом в виде встроенного «арбитра», алгоритм работы которого описы­вается ниже, и, кроме того, определяется средствами настройки и перепрограмми­рования такого «арбитра».

Разбиение на секции и правила и специальные условия в виде секционных и правиловых разрешений необходимы для того, чтобы обеспечить многоуровневое управление выполнением PILOT-программ. Как известно [Форсайт, 1987], «ар­битр» продукционной системы функционирует следующим образом: сначала для всех продукций проверяются условия применимости и из тех продукций, для ко­торых эти условия истинны, формируется конфликтное множество. Из этого множества по определенному критерию выбирается исполняемая продукция; она реализуется (то есть отрабатывается ее правая часть), и цикл управления работой «арбитра» повторяется, пока конфликтное множество на некотором шаге не ста­нет пустым (тогда работа продукционной системы завершается естественным об­разом) или функционирование не будет прервано явным образом, например с помощью специального действия из правой части исполняемой продукции (в этом случае работа продукционной системы завершается принудительно).

Понятно, что работа такого «арбитра» имеет смысл лишь в тех случаях, когда про­дукций немного (десятки), а в конфликтном множестве продукций мало (едини­цы). В противном случае функционирование системы неэффективно и требуют­ся специальные алгоритмы, чтобы «арбитр» не тратил все время только на себя. К настоящему времени разработаны и опробованы на практике различные стра­тегии увеличения эффективности работы «арбитра» [de Kleer, 1989], которые используются и в данном случае. Но не менее важно иметь гибкие средства описа­ния этих стратегий с уровня входного языка. Тогда пользователь, в зависимости от требований его задачи, сможет отказаться от стандартных стратегий и описать свою собственную, которая адекватна его конкретному случаю.

Для описания стратегий управления выводом решений в ЯПЗ PILOT/2 служат секционное и правиловое разрешения. Каждое из них является последовательно­стью фильтров, с помощью которых формируется и/или изменяется конфликт­ное множество продукций. Для понимания того, как пользоваться этими фильтрами, необходимо знать стратегию встроенного «арбитра» PILOT/2. Поэтому ниже приводится алгоритм его работы, специфицирующий схему, представлен­ную на рис. 7.1.

Алгоритм работы встроенного «арбитра» ЯПЗ PILOT/2

while (уровень-0!= NULL) {

«выбрать из «повестки-дня» секцию для выполнения»;

«сформировать на уровне-1 мн-во правил этой секции»;

«выполнить фильтрацию мн-ва правил на уровне-1 по флагу активна/ неактивна»;

«выполнить фильтрацию мн-ва оставшихся правил на основании вычисления истинности секционного разрешения»;

«сформировать на уровне-2 множество активных правил»;

for (каждого правила на уровне-2) {

«вычислить значение истинности левой части»;

if (значение истинности правила == TRUE)

«добавить правило в конфл. мн-во на уровне-3»;

}

«выполнить фильтрацию мн-ва оставшихся на уровне-3 правил на основании вычисления истинности правиловых разрешений»;

«сформировать на уровне-4 множество готовых к выполнению правил»;

if (на уровне-4 осталось одно правило)

«выполнить данное правило»;

else {

«выполнить случайный выбор исполняемого правила из множества правил на уровне-4»;

«выполнить данное правило»;

}

}

Приведенный алгоритм прозрачен и не нуждается в особых комментариях. Заме­тим лишь, что фильтр «активна/неактивна» реализован как встроенная проверка флагов активности продукций текущей секции. Первоначально (при запуске сек­ции) «арбитр» считает, что все продукции секции активны, но в процессе вы­полнения их состояние может измениться за счет применения соответствующих действий. Фильтр секционного разрешения тоже программируется с уровня входного языка. В результате применения этих двух фильтров формируется мно­жество продукций, которые принципиально могут войти в конфликтное множе­ство. Этап фильтрации продукций по истинности левых частей – традиционный, в результате получается традиционное конфликтное множество (правда, уже усе­ченное за счет предыдущих двух фильтров). На этом множестве в ЯПЗ PILOT/2 может быть организовано дополнительное управление за счет программируемых правиловых разрешений. Если все усечения не привели к однозначному выбору исполняемой продукции, она выбирается случайным образом и цикл работы «ар­битра» повторяется.

Рис. 7.1. Встроенный «арбитр» PILOT/2

Точек «влияния» на работу «арбитра» PILOT/2 всего четыре: активность/неак­тивность продукций; секционное разрешение; истинность левых частей продук­ций; правиловое разрешение. Существует и пятая точка - алгоритм случайного выбора, но она инженеру по знаниям недоступна.

Секционные и правиловые разрешения суть последовательность операторов if-then-else и действий разрешения. При этом сами условия секционного и правилового разрешений - логические формулы в базисе И-ИЛИ-НЕ с общепри­нятым старшинством операций. А специфика ЯПЗ PILOT/2 состоит в том, как определяются элементарные разрешения. Семантика действий разрешений (при условии, что через КМ обозначено конфликтное множество) - следующая:

set (Rl, R2,..., Rk) KM - Rl,R2,..., Rk

insert (Rl, R2,..., Rk)KM_н - KM_C + Rl + R2 +... + Rk

remove (Rl, R2,..., Rk)KM_н - KM_C - Rl - R2 -... - Rk

removeall KM = пустое множество

break Прерывает выполнение оставшихся элементов

секционного или правилового разрешения

Семантика элементарных секционных (продукционных) разрешений - опреде­ляется правилами вида:

1. Элементарное секционное разрешение active (Rl,R2,...,Rk)истинно, если все продукции Rl, R2,..., Rk имеют включенные флаги активности.

2. Элементарное секционное (продукционное) разрешение used (Rl,R2,...,Rk)ис­тинно, если все продукции Rl, R2,..., Rk применялись ранее.

3. Элементарное продукционное разрешение ready (Rl,R2,...,Rk) истинно, если все продукции Rl, R2,..., Rk готовы к выполнению, что, в свою очередь, спра­ведливо, если их левые части (условия) истинны.

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

Вместе с тем в ЯПЗ PILOT/2 инженеру по знаниям предоставлена возможность управления работой продукционной системы и на основе анализа базы знаний. Нужно лишь понимать, что это управление «дорогое», так что пользоваться им следует лишь в тех случаях, когда соответствующие условия невозможно (или нецелесообразно) проверять в левых частях продукций.

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