7.3. Продукционные системы

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

Продукционное правило представляет собой выражение вида

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

Метод обработки информации с помощью продукционных правил не является формальным аналогом приемов,

применявмых в системах с использованием традиционных процедур (разд. 7.5). Впервые метод продукций был предложен Е. Постом (Post, 1936) и использован для определения языков и формальных грамматик (Chomsky 1963). С 1974 г. он находит широкое применение в многочисленных программах, которые получили уже знакомое нам название экспертных систем.

Рис. 7.3. Примеры вывода при движении по цепочке вперед.

Они применяются в специальных областях, где решение задач основано на логических выводах, но имеет исключительно познавательный аспект. В основе экспертных систем лежат продукционные правила, поддерживающие весь объем доступных знаний. Эти знания представлены -в модульном виде и могут быть легко модифицированы с учетом того, что их содержание не меняется при выполнении программ. На рис. 7.3 приведен пример вывода в такой системе.

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

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

7.3.1. Структура продукционной системы

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

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

Рис. 7.4. (см. скан) Элементарный цикл интерпретатора.

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

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

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

Рис. 7.5. Дерево вывода при движении по цепочке назад (те же данные, что и на рис. 7.3).

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

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

Движение к цели при работе системы происходит естественным образом (как при доказательстве теоремы) и может быть легко представлено с помощью И/ИЛИ (рис. 7.5).

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

Рис. 7.6. (см. скан) Общая схема современной продукционной системы.

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

Большую часть вычислительной работы в этом случае выполняет интерпретатор Лисп с помощью рекурсивных процедур. Общая схема системы приведена на рис. 7.6. Заметим, что хороший интерпретатор должен давать возможность проходить по цепочке правил вперед или назад в зависимости от практических потребностей.