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

Можно предложить несколько определений систем продукций (или продукционных систем, или систем, основанных на правилах)', рассматривая^[1]

их с различных точек зрения. В конечном счете различные определения ведут к одному и тому же объекту, хотя и подходят с разных сторон и различаются в некоторых деталях. Мы рассмотрим три определения:

• 1) системы продукций с точки зрения их структуры;
• 2) системы продукций с алгоритмической точки зрения;
• 3) системы продукций как логические исчисления.

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

Терминологические соглашения и содержательная интерпретация

В заголовке присутствует слово «содержательная», которое обозначает сознательное отступление автора с позиций «строгости» и «алгоритмичности» в представлении материала, но это отступление временное. Объясняется отступление желанием автора подчеркнуть существующую в обсуждаемой области «неразбериху» в терминах, представлениях и обоснованиях, что, в свою очередь, является почти необходимым признаком «молодости» направления исследований и интенсивности его развития. Разнобой в терминологии только кажущийся: на самом деле в данном случае разными словами обозначают одно и то же, и одновременно разные слова используют для обозначения сходных вещей. При этом разные термины почти не обозначают различий по существу: это просто дань культурным традициям, воспитанию и научным школам. Мы пользуемся одной конкретной системой терминов (принятой в нашей научной школе), но одновременно перечисляем и другие, стараясь учесть все существенные. Наша терминология не противоречит одной из самых популярных энциклопедий по искусственному интеллекту^[2].

Содержательно (с позиций здравого смысла и естественного языка) с термином «продукция» чаще всего ассоциируют сложноподчиненное предложение ^{[3][4] условного вида «Если посылка, то}

заключение

". Не вдаваясь в детали, зафиксируем пока именно эти термины: посылка и

заключение

.

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

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

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

Продукции естественным образом можно разбить на два непересекающихся класса: однородные и неоднородные. Это разбиение определяется способом задания интерпретации посылки и заключения продукции. В первом случае р и q получают «схожий» смысл (слова в некотором общем алфавите, числовые значения, логические выражения и т. п.). Ко второму виду мы отнесем продукции, в которых посылка и заключение интерпретируются по-разному (условие — действие, состояние среды — переход, стимул — реакция, другие сочетания).

Напомним еще один важный момент: все механизмы и приемы, составляющие содержание этой книги, предназначены для описания и анализа изменений в некоторой конкретной предметной области. Фиксированную ситуацию в предметной области мы, как правило, называем текущим состоянием (окружения или окружающей среды). Множество всех возможных состояний мы всегда (если явно не оговаривается иное) обозначаем буквой D, а отдельные состояния из этого множества — буквой d (с индексами, если нужно) и полагаем, что это состояние описывается набором конкретных значений (утверждений) чего-либо (о чем-либо). Способ хранения (организации) текущего состояния d не принципиален (список, массив, набор таблиц). Механизм хранения текущего состояния мы также обозначаем буквой D (всегда легко отличить по контексту, о чем идет речь — о множестве состояний или о механизме представления множества в программе) и называем «база фактов» (реже — «база данных», а иногда «пространство поиска»).

Множество всех возможных состояний базы фактов D называется пространством поиска (search space).

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

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

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

Таблица 2.1

Примеры систем продукций

• 1 ^{В парадигме (логических) формальных теорий (см. п. 4.1.1) понятие вывода вводится несколько другим способом, не подразумевающим явной связи с интерпретацией.}
• ^{2 Переходы состояний также называют шагами, а последовательности переходов — путями.}
• ^{3 Ахо А._} Ульман Дж. Теория синтаксического анализа перевода и компиляции. В 2 т. М.: Мир, 1978.}
• ^{4 Бухбергер Б. Компьютерная алгебра. Символьные и алгебраические вычисления / Б. Бухбергер [и др.]. М.: Мир, 1986.}

^{э Чень И., Ли Р. Математическая логика и автоматическое доказательство теорем. М.: Наука, 1983.}

⁶ Поликарпова II. И., Шалыто А. А. Автоматное программирование. 2-е изд. СПб.: Питер, 2011.

Мы видим, что для неоднородных систем в большинстве случаев нет общепринятого математического базиса. В лучшем случае, обоснованием систем второго класса могут выступить охраняемые команды Дейкстры¹, которые, впрочем, так и не стали строгой формальной теорией. Машины состояний, упомянутые в случае дискретных систем управления, фактически далеко ушли от математических конечных автоматов в сторону систем программирования.

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

• [1] Не только в русском языке системы продукций обозначаются многими, почти синонимичными, но все-таки различными способами. В английском языке также применяют О
• [2] 2^{множество} различных, хотя и похожих словосочетаний. Например, в выражении «[production] [rules] [based] [inference] systems» почти любая пара или даже тройка слов, стоящихв квадратных скобках, может быть допустимым термином, имеющим прямое отношениек системам продукций. Поэтому при поиске информации на эту тему в Интернете мы рекомендуем провести поиск по нескольким различным словосочетаниям.
• [3] Рассел С., Норвиг П. Искусственный интеллект: современный подход (AIMА) = ArtificialIntelligence: A Modern Approach (AIMA). 2-с изд. М.: Вильямс, 2007.
• [4] Сложноподчиненное предложение — это сложное предложение, части которого связаныподчинительным союзом или относительным словом и подчинительной связью. Условноесложноподчиненное предложение указывает на условие, при котором совершается действие, описанное в главном предложении. К главному предложению подчиненное присоединяетсяс помощью союзов если, когда, коли и т. д. и отвечает на вопрос при каком условии? Например:"Я тебе дам эту книгу, если ты пообещаешь вернуть ее через неделю". — Шпаргалка по русскому языку [http://shkola.lv/].