Продукционные модели

Д. Л. Поспелов

Основные определения

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

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

(0; Q; Р; А=>В; N.

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

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

Основным элементом продукции является ее ядро: А=$~В. Интерпретация ядра продукций может быть различной и зависит от того, что стоит слева и справа от знака секвенции =ф». Обычное прочтение ядра продукции выглядит так: ЕСЛИ А, ТО В, более сложные конструкции ядра допускают в правой ча­сти альтернативный выбор, например, ЕСЛИ А, ТО В\, ИНАЧЕ В₂. Секвенция может истолковываться в обычном логическом смысле как знак логического следования В из истинного А (если А не является истинным выражением, то о В ничего сказать нельзя). Возможны и другие интерпретации ядра продук­ции, например А описывает некоторое условие, необходимое для того, чтобы можно было совершить действие В.

Элемент Р есть условие применимости ядра продукции. Обычно Р пред­ставляет собой логическое выражение (как правило, предикат). Когда Р при­нимает значение «истина», ядро продукции активизируется. Если Р ложно, то ядро продукции не может быть использовано. Например, если в продукции «НАЛИЧИЕ ДЕНЕГ; ЕСЛИ ХОЧЕШЬ КУПИТЬ ВЕЩЬ X, ТО ЗАПЛАТИ В КАССУ ЕЕ СТОИМОСТЬ И ОТДАЙ ЧЕК ПРОДАВЦУ» условие примени­мости ядра продукции ложно, т. е. денег нет, то применить ядро продукции невозможно.

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

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

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

В ряде ИС используются комбинации сетевых и продукционных моделей представления знаний. В таких моделях декларативные знания описываются в сетевом компоненте модели, а процедурные знания —в продукционном. В этом случае говорят о работе продукционной системы над семантической сетью ГНариньяни и др., 1984].

Классификация ядер продукции

Ядра продукций можно классифицировать по различным основаниям. Прежде всего все ядра делятся на два больших типа: детерминированные и недетерминированные. В детерминированных ядрах при актуализации ядра и при выполнимости А правая часть ядра выполняется обязательно; в недетер­минированных ядрах В может выполняться и не выполняться. Таким образом, секвенция =*■ в детерминированных ядрах реализуется с необходимостью, а в недетерминированных — с возможностью. Интерпретация ядра в этом слу­чае может, например, выглядеть так: ЕСЛИ А, ТО ВОЗМОЖНО В.

Возможность может определяться некоторыми оценками реализации ядра. Например, если задана вероятность выполнения В при актуализации А, то продукция (в простейшем случае продукция состоит лишь из ядра) может быть такой: ЕСЛИ А, ТО С ВЕРОЯТНОСТЬЮ р РЕАЛИЗОВАТЬ В. Оценка реализации ядра может быть лингвистической, связанной с понятием терм-мно­жества лингвистической переменной, например: ЕСЛИ А, ТО С БОЛЬШОЙ ДОЛЕЙ УВЕРЕННОСТИ В. Возможны иные способы задания оценки реали­зации ядра.

Детерминированные продукции могут быть однозначными и альтернатив­ными. Во втором случае в правой части ядра указываются альтернативные возможности выбора, которые.оцениваются специальными весами выбора. В качестве таких весов могут использоваться вероятностные оценки, лингви­стические оценки, экспертные оценки и т. п. (например, ЕСЛИ А, ТО ЧАЩЕ ВСЕГО НАДО ДЕЛАТЬ В_и РЕЖЕ В,).

Особым типом являются прогнозирующие продукции, в которых описыва­ются последствия, ожидаемые при актуализации А, например- ЕСЛИ А ТО С ВЕРОЯТНОСТЬЮ р МОЖНО ОЖИДАТЬ В.

Дальнейшую классификацию ядер продукций можно провести опираясь на типовую схему ИС (рис. 1.15). Если х и у обозначают любой из блоков рисунка (О, Д, 3, Л), то ядро А_Х=>В_У означает, что информация об А берется из блока х, а результат срабатывания продукции В посылается в блок у. Ком­бинации х и у, осмысленные с точки зрения ИС, отмечены в табл. 1.8 зна­ком «+>.

ешняя среда

Рис. 1.15

Рассмотрим часто встречающийся тип продукции Аз=$-Вз. В этом случае Аз и Въ представляют собой некоторые фрагменты информации, хранящейся в базе знаний. При сетевом представлении это могут быть фрагменты семан­тической сети, при логических моделях — формулы того или иного исчисления. Тогда смысл продукции Аз=>В₃ состоит в замене одного фрагмента базы зна­ний другим. Для актуализации этой продукции необходимо, чтобы в базе зна­ний существовал фрагмент, совпадающий с А. При поиске в базе знаний А играет роль образца, а процедура такого поиска называется поиском по об­разцу.

Для иллюстрации поиска по образцу предположим, что в базе знаний для представления знаний используется семантическая сеть (рис. 1.16,а) и продук­ция (рис. 1.16,6). Поиск А в базе знаний организуется различными способами. Можно, например, сначала искать вершину а. Если в базе знаний такой вер­шины нет, то поиск по образцу заканчивается неудачей. Если вершина а най­дена, то ищутся все выходящие из нее дуги, помеченные отношением /?₃, так как в образце справа от этой дуги стоит вершина х, на месте которой в базе знаний может находиться любая вершина. Если из а не выходит ни одной дуги, помеченной отношением Яз, то поиск по образцу заканчивается неудачей. Но если такие дуги есть, то происходит переход во все вершины, с которыми вершину а связывает отношение /?з, т. е. возникает параллельный процесс по­иска. В примере произойдет переход от вершины а к вершинам Ъ и /, из ко­торых начнется поиск выходящих из них дуг, помеченных отношением Ru ведущих в любую вершину, так как в образце далее стоит вершина, которой соответствует свободная переменная у. Далее процесс продолжается аналогич­ным образам. Ц примере поиск по образцу оказывается успешным. После на­хождения А в семантической сети происходит замена, которая определяется правой частью образца. В результате возникает трансформированная сеть (рис. 1.16,0).

Продукция Лд =? В₃ может соответствовать процедуре нахождения зако­номерностей по эмпирическим данным. Логический блок на основании просмот­ра и анализа данных выдвигает гипотезы о наличии закономерностей и, убе­дившись в их приемлемости и достаточной обоснованности, записывает их в базу знаний. Аналогично можно интерпретировать и иные типы продукций из табл. 1.8.

а)

6)

в)

РИС. 1.16

Краткая история

Термин «продукция» принадлежит американскому логику Э. Посту [Posf, 1943]. В понимании Поста в качестве продукции выступала только та ее часть, которую теперь называют ядром. Запись «ЕСЛИ А, ТО В» трактовалась как оператор замены цепочки А цепочкой В в некотором входном слове, т. е. про­дукции были тем, что позже стали называть подстановками и использовать при описании различных уточнений понятия алгоритма. Например, подстанов­ки являются основным оператором в нормальных алгорифмах Маркова. По­этому в языке программирования Рефал, основанном на идее такой модели уточнения понятия алгоритма, оператор подстановки играет основную роль. Идея продукций используется в языках логического программирования, нашед-

Ъ2

ших применение в ИС. Среди языков подобного типа наиболее известен Про­лог. Продукционный подход стал стилем нового этапа программирования.

Системы продукций широко распространены в экспертных системах [Алек­сеева и др., 1984; Микулич, 1985].

Популярность продукционных моделей определяется несколькими факто­рами.

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

2. Системы продукций являются модульными. За небольшим исключением
удаление или добавление продукций не приводит к изменениям в остальных
продукциях.

3. При необходимости системы продукций могут реализовать любые алго­
ритмы и, следовательно, способны отражать любое процедурное знание, до­
ступное ЭВМ.

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

5. При объединении систем продукций и сетевых представлений получают­
ся средства, обладающие большой вычислительной мощностью (см. § 1.3).

6. Естественный параллелизм в системе продукций, асинхронность их реа­
лизации делают продукционные системы удобной моделью вычислений для
ЭВМ новой архитектуры, в которой идея параллельности и асинхронности яв­
ляется центральной.

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

Управление системой продукций

При выполнении условия применимости ядер продукции для группы про­дукций возникает дилем^ма выбора той продукции, которая в данной ситуации будет активизирована. Решение этой задачи возлагается на систему управле­ния оистемой продукций. Если, например, ИС реализована на ЭВМ с парал* дельной архитектурой, то из фронта готовых продукций может выбираться не одна продукция, а столько, сколько параллельных ветвей может одновременно в данной ситуации выполнять ЭВМ. Но независимо от количества актуализи­рованных продукций задача альтернативного выбора остается.

Задача управления характерна не только для систем продукций, но и для всех систем, где необходимо выполнение параллельных процессов с учетом имеющегося технического ресурса [Поспелов Д., 1972; Варшавский и др., 1984]. Возможны два пути ее решения: централизованный и децентрализован-ный. При централизованном управлении выполнением продукций решение об актуализации принимается специальной системой управления, а при децентра­лизованном определяется складывающейся в этот момент ситуацией. Еслр порядок выполнения продукций произволен, то решение определяется текущей ситуацией или оистемой управления; если порядок важен, то в продукциях должна содержаться информация о требованиях к этому порядку. Если в пост­условиях продукций указывается имя продукции, которая должна выполнять­ся после данной, система продукций превращается в обычную программу для ЭВМ, т. е. реализует некоторый алгоритм.

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

1. Принцип «стопки книг». Основан на идее, что наиболее часто используе­
мая продукция является наиболее полезной. Готовые продукции как бы об­
разуют «стопку», в которой порядок определяется накопленной частотой ис­
пользования продукций в прошлом. На самом верху «стопки» находится про­
дукция, которая использовалась чаще всех. При актуализации некоторого
фронта готовых продукций для исполнения выбирается та продукция (или те
продукция при наличии параллельных технических устройств), у которой ча­
стота использования максимальна. Подобный принцип управления особенно
хорош, когда частота исполнения подсчитывается с учетом некоторой ситуа­
ции, в которой ранее исполнялась продукция, и это исполнение имело положи­
тельную оценку. При такой обратной связи метод стопки книг может прев­
ратиться в обучающуюся процедуру, адаптирующуюся к тем задачам, которые
возникают во внешней среде (см. гл. 6 и 7). Управление по принципу стопки
книг целесообразно применять, если продукции относительно независимы
друг от друга, яэлример, когда каждая из них есть правило вида «ситуа­
ция (Л)=*-действие (5)>. Именно такой случай имеет место в планирующих
системах для роботов (см. § 7.1).

2. Принцип наиболее длинного условия. Заключается в выборе из фронта
готовых продукций той, у которой стало истинным наиболее «длинное» условие
выполнимости ядра. Этот принцип опирается на соображение «здравого смыс­
ла», что частные правила, относящиеся к узкому классу ситуаций, важнее
общих правил, относящихся к широкому классу ситуаций, так как первые учи­
тывают больше информации о ситуации, чем вторые. Трудность использования
данного принцида состоит в том, что надо заранее упорядочить условия по
вхождению друг в друга по отношению «частное — общее». Исследование си­
стем продукций, <в которых продукции упорядочены подобным образом, при­
вело к появлению понятия К-систем, оказавшихся более богатой моделью про­
цессов, чем классические алгоритмические модели [Кузнецов, I986J, однако не
гарантирующих однозначного результата, получаемого за конечное число ша­
гав, который является обязательным для алгоритмических систем. Управление
по принципу наиболее длинного условия в продукциях, образующих фронт го­
товых продукций, целесообразно применять в тех случаях, когда знания и
сами продукции хорошо структурированы привязкой к типовым ситуациям, на
которых задано отношение типа «частное — общее>.

3. Принцип метапродукций. Основан на идее ввода в систему продукций
специальных метапродукций, задачей которых является организация управления
в системе продукций при возможности неоднозначного выбора из фронта го­
товых продукций. Приведем пример использования метапродукций, заимствован­
ный из американской экспертной системы MYCIN-TEIRESTAS, предназначен­
ной для диагностики инфекционных заболеваний.

ЕСЛИ инфекция" есть pelvic-abcess и имеются продукции, входящие в со-

став фронта, в которых в условии А упоминается grampos-rods

ТО продукции, у которых в А имеется enterobacteriaceae, следует ак-

тивизировать раньше, чем продукции, содержащие в A grampos-rods

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

4. Принцип «классной доски». Основан на идее спусковых функций [По­
спелов Д., 1972]. При реализации принципа «классной доски» в ИС выделяется
специальное рабочее поле памяти — аналог классной доски, на которой мелом
пишут объявления и стирают их при необходимости тряпкой. На этой «доске»
параллельно выполняющиеся процессы находят информацию, инициирующую их
запуск, на нее же они и выносят информацию о своей работе, которая может
оказаться полезной для других процессов.

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

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

5. Принцип приоритетного выбора. Связан с введением статических или ди­
намических приоритетов на продукции. Статические приоритеты могут форми­
роваться априори на основании сведений о важности продукционных правил
в данной проблемной области. Эти сведения, как правило, представляют собой
информацию, извлекаемую из эксперта (см. § 2.1). Динамические приоритеты
вырабатываются в процессе функционирования системы продукций и могут
отражать, например, такой параметр, как время нахождения продукции во
фронте готовых продукций. К данному типу управления относится задание
последовательности приоритетов с помощью специальной каузальной семанти­
ческой сети [Feigenbaum et a]., 1971]. В этом случае задается некоторый кау­
зальный сценарий (си. § 1.5), движение по которому определяется складываю­
щимися ситуациями и в каждой вершине которого задана функция выбора
очередной продукции из фронта готовых продукций.

Если продукции работают над семантической сетью, приоритеты могут формироваться не в системе продукций, а в сети [Вильсон, 1985].

Как и при логическом выводе (см. § 2.5), существуют два типа выполне­ния систем продукций: прямой и обратный. В первом случае поиск идет от ле­вых частей продукций, т. е. проверяются условия А и актуализируются те про­дукции, для которых А имеет место; во втором —от изначально заданных В, по которым определяются необходимые для В значения А, которые, в свою очередь, отождествляются с правыми частями ядер продукций в системе. Два этих метода часто называют восходящим и нисходящим методами реалнзациу системы продукций.

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

Например, пусть система продукций представлена четырьмя простейшими продукциями, состоящими лишь из ядерных частей: (а) А=>В; (б) B&D=>A; (в) A\/B=>D; (г) D=>C. В таком виде система продукций явно недетермини-рованна. Если выполняется Л, то фронт готовых продукций включает продук­ции с именами (а) и (в), а если выполняются В и D, то три последние про­дукции, Для устранения подобной недетерминированности может быть введена некоторая грамматика для имен продукций: (а)=>-(б); (в)=*-(б); (а)=>(г). Тог­да если в некоторый момент была выполнена продукция с именем (б), то но­вые продукции выполняться не будут. Если же в некоторый момент выполни­лась продукция с именем (а), то после нее смогут выполняться продукции с именем (б) или (г). Но левые части ядер в этих продукциях таковы, что неоднозначность возникнет лишь в случае, когда В и D одновременно выпол­нены. С помощью грамматики для имен продукций можно задать однозначный алгоритмический процесс.

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

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

Следует ожидать, что теория продукционных систем появится не ранее, чем будут созданы эффективные теории параллельных информационных процессов [Карпов, 1987J. Но некоторые результаты можно получить на основе сущест­вующих методов оптимального управления [Поспелов И. и др., 1987], введя ряд ограничений на понимание продукций и систем продукций.

Другая проблема практического применения продукционных моделей — пе­реход от статических систем к динамическим, меняющим состав продукций в си­стеме или перестраивающих алгоритм управления выбором продукций из фронта готовых продукций в зависимости от текущих ситуации. Такие системы продук­ций называются адаптивными, или системами продукций реаль­ного времени. Во многих приложениях быстрота срабатывания продукций си­стем имеет решающее значение [Clema et al., 1985; Stefic, 1985]. Достичь этого можно только за счет гибкого набора стратегий управления, среди которых должны быть стратегии различного уровня сложности и быстроты срабатывания [Sorrels, 1985]. Ряд авторов считает, что прототипом такого управления может стать управление, которое было использовано в программе игры в шашки [Sa­muel, 1959, 1967]. Ее идеи были реализованы в проекте CONSIM {моделирова­ние конфликтов), который ставил своей целью разработку системы продукцион­ных правил для принятия решений при управлении воздушным боем. Для этого проекта была создана система EMULAR, реализующая ряд функций динамиче­ской продукционной системы. Для повышения скорости работы таких систем разрабатывались специальные средства аппаратной поддержки [Stolfo et al., 1982; Masnio et al., 1983; Shaw, 1985].

Поиск по сайту: