Лекция 7 Лекция 8

Продукционная модель предполагает такой способ организации вычислительного процесса, при котором программа преобразования некоторой информационной структуры задается в виде системы правил вида: условие -> действие, где "условие" специфицирует определенные требования к текущему состоянию структуры С, а "действие" содержит описание тех операций над С, которые надо выполнить, если С удовлетворяет этим требованиям [24].

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

Системы подстановок служат для обработки слов, заданных в некотором алфавите. К таким системам относятся системы продукций Поста [144] (именно работам Г.Поста мы обязяны появлением термина "системы продукций", который получил со временем более широкое употребление) и нормальные алгоритмы Маркова [54]. Формальные грамматики [106], служащие для описания синтаксиса и семантики различных языков, являются тем классом формальных систем, который в своем развитии привел к появлению современных систем продукций. Первым продукционным языком программирования был язык Флойда, основанный на грамматике и предназначавшийся для синтаксического анализа [124].

Рассмотрим программные системы продукций. Структурно программная система продукций [24] состоит из трех частей: базы, множества правил продукций и интерпретатора [120]. База представляет собой рабочую память, над которой работает множество правил. Организация рабочей памяти может быть различной - от простой памяти в виде совокупности именованных переменных до семантических сетей и фреймов. Правила также могут иметь произвольную сложность, сохраняя при этом вид: условие Ґ действие. Работу интерпретатора можно рассматривать как поисковый процесс, состоящий по крайней мере из двух фаз: выбора продукции и ее применения. Ситемы продукций могут отличаться как организацией рабочей памяти, так и видом правил, но существенным различием для них является различие в интерпретаторе, т.е. способе выбора и применения продукций.

Проблема выбора интерпретатором продукций сводится к двум подзадачам: (1) максимально ограничить число продукций, условия применимости которых могут проверяться и (2) из полученного множества продукций выбрать одну с истинным условием применимости. Первая задача чаще всего решается не путем ограничения множества продукций, а путем активации какого либо его подмножества. Вторая задача возникает в связи с тем, что в выделенном подмножестве могут оказаться истинными условия более чем одной продукции. Совокупность таких продукций называется конфликтным множеством, а процедура выбора продукции из этого множества - процедурой разрешения конфликта [120]. Перечислим основные способы выбора продукций из конфликтного множества, приведенные в [62]:

- случайный выбор;

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

- выбор по критерию, формируемому динамически по ходу процесса, например, приписыванием правилам и/или компонентам базы адинамически вычисляемых весов - приоритетов.

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

В зависимости от отношения к проблеме активации продукций системы продукций делятся на два класса: простые системы продукций и управляемые системы продукций.

В простых системах продукций активными считаются все продукции. Обычно такой способ активации продукций применяется в системах продукций небольших по объему, а также в системах продукций, характеризующихся тем, что структуризация множества продукций и принудительная активация противоречит положенной в их основе идеологии или используемой ими стратегии выбора продукций. Это относится, например, к семейству языков OPS [126], использующих специальный алгоритм быстрого сопоставления образцов [127], Rete и языку Пролог [160], в основе которого лежит бектрекинг и обратный вывод.

В управляемых системах продукций предусмотрены средства управления активацией продукций. Выделяется 4 вида управляемых систем продукций:

- с независимым управляющим языком,

- с метапродукциями,

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

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

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

Другой способ управления активацией продукций состоит в использовании метапродукций, т.е. продукций, содержащих информацию о других продукциях и активирующих (дезактивирующих) на основе этих знаний и анализа текущей ситуации определенное подмножество продукций. Системы продукций могут включать несколько уровней метапродукций. Такие системы называются иерархическими [121], [142]. Т.о. аппарат метапродукций позволяет организовать довольно гибкое динамическое управление активацией продукций.

В последовательных системах продукций множество продукций разбивается на несколько подмножеств, каждое из которых представляет собой автономный модуль обработки данных (продукционный модуль). При этом фиксируется следующий порядок применения правил: сначала применяются правила из 1 подмножества, затем из 2 и т.п.. Такая организация продукций может использоваться в системах, в которых возникает необходимость многоуровневого представления знаний, причем эти уровни могут быть четко разделены. Например, в лингвистических процессорах семейства ЗАПСИБ [60], [61], обрабатывающих запросы к реляционной базе данных на естественном языке, каждому уровню знаний соответствует определенный продукционный модуль. Аналогичный подход использован в системах понимания речи HEARSAY-I [146] и HEARSAY-II [121].

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

Рассмотрим способы применения продукций [24]. Имеют место две стратегии применения продукций: прямая и обратная. В системах продукций, работающих в прямом направлении, образцом для поиска служит левая часть продукции (условие). Продукции, которые применяются к текущему состоянию, порождают новые состояния. При использовании обратной стратегии задача решается в обратном направлении - от цели (если она известна) к начальному состоянию. При этом продукции должны иметь вид подстановок и применяться в обратном направлении (условия применения и действие меняются местами). Обратная стратегия обычно применяется для решения задач с четко заданным целевым состоянием. Прямую стратегию можно успешно применять и в тех случаях, когда целевое состояние не задано или задано неточно. В некоторых системах, например, в системе доказательства теорем Нильсона [143], в языке Плэннэр [77], одновременно используются обе стратегии.

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

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

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