Об использовании общепринятых форм и обозначений

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

Вводя в предыдущей главе понятие продукции и специфицируя составляющую этого понятия, называемую условием, мы аккуратно отметили, что реализация условия, «как правило, определяется истинностью или ложностью логического выражения…» (см. п. 2.1.2). На самом деле, автору неизвестно ни одной реальной задачи, связанной с использованием продукционных правил, где бы условия продукционных правил (логические выражения) определялись формулами языка, более сложного, нежели язык исчисления предикатов первого порядка. Мы уверены, и практика эго показывает, что языка исчисления предикатов первого порядка достаточно для записи логических утверждений о реальных задачах (см. п. 4.1.3). Таким образом, использование в алгоритме Rete языка исчисления предикатов первого порядка не является сколь-нибудь значимым ограничением.

Забегая вперед (см. и. 4.1.4), отметим, что любая формула Fисчисления предикатов первого порядка может быть представлена, в частности, в виде F_x vF₂v…vF_k, где, в свою очередь, каждая подформула F_{ является конъюнкцией некоторых атомов F, = G,&G₂&…&G_w. Это так называемая дизъюнктивная форма, которая очень широко используется.

Опять же, используя материал гл. 4 («законы» эквивалентности), мы с легкостью выполним преобразование: -> Q = (-i(F_xvF₂v…vF^)vQ) =

= ((-)F₁&-iF₂&…&-F'_k)vQ) = ((^vQ^i^vQ^.M^Q)) — № -> Q)&№ -> —> Q)&…&(F_k —" Q). Последняя формула, с учетом соответствующих подстановок для Fj и соглашения о том, что конъюнкция импликаций эквивалентна списку продукционных правил, дает нам все основания использовать (а) терминологическую конструкцию «не умаляя общности» и (б) считать посылку (условие)р любой продукции конъюнкцией атомарных формул. Таким образом, все приводимые ниже рассуждения, соображения и примеры (как и алгоритм Rete в целом) корректны и применимы для любых продукционных систем.

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

Такое представление системы продукций является традиционным и согласуется с содержимым гл. 2 и предыдущих параграфов гл. 3. Следует, однако, сделать некоторые уточняющие замечания.

Прежде всего, важно понимать, что в приведенных формулах для переменных не допускается переименование (одинаковые имена денотируют один и тот же объект), и возможная подстановка [С^/х^ осуществляется строго согласованно для всех вхождений ХуВ правиле (как в условии, так и в действии). Это соображение определяет принцип построения и функционирования «решета фактов», которое в оригинальном описании алгоритма называется альфа-сетыо (далее используется запись а-сеть).

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

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

Итак, структура данных алгоритма Rete имеет две составляющих. Первая, альфа-сеть, осуществляет проверки фактов. Выходы этой сети содержат все факты, прошедшие подтверждение. Вторая часть, бета-сеть ([3-сеть), «собирает» конъюнкции и формирует конкретные наборы фактов, которые обращают условие р в истину. Продемонстрируем работу алгоритма Rete на простом примере «из мира кубиков»^[1], преследуя цель облегчить понимание работы алгоритма (рис. 3.6).

Рис. 3.6. Сцена из «мира кубиков».

В рассматриваемом примере участвуют четыре кубика, имеющие имена В_{, В₂у В₃, В₄, и стол, имеющий имя Table. Объекты могут обладать свойствами, в данном случае рассматривается одно свойство — цвет. Значениями этого свойства являются константы Black, White и т. д. Объекты могут находиться в некоторых отношениях, в данном случае рассматриваются отношения «стоять на» (On) и «быть слева от» (Left-of). Таким образом, вводится следующая система предикатов:

• • On (х, у) — объект х находится на объекте у
• • Left-of (х, у) — объект х находится левее объекта у
• • Color (х, z) — объект х имеет цвет 2.

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

Будем также считать, что предикатам из условия (0w (…), Left-of{…) и Color{…)) сопоставлены имена A_lf Л₂, Л₃, соответственно (А от антецедент). Другими словами, A_t = On (х, г/); Л₂ = Left-of (у, г); А₃ = Color (z, Black).

Пусть текущее состояние d е D сформировано фактами (см. рис. 3.6):

w{. Оп (В_{, В₂) w₂. On (B_v В₃) w₃: Color (B_{, Black)

w_A On (B₂, Table) w₅: Left-of (B₂, B₃) w₆: Color (B₂, White)

w₁: Left-of (B₃, B₄) w₈: On (B₃, Table) w₉: Color (B₃, Black).

Покажем, как алгоритм Rete выясняет, какой именно набор (или наборы) фактов удовлетворяет посылке рассматриваемого правила. Для рассматриваемого случая строится дерево (рис. 3.7). Это дерево относится к классу двудольных графов. Вершины первого сорта (белые прямоугольники) содержат списки (конъюнкции) фактов, вершины второго сорта (окружности) реализуют операцию согласования левого и правого узлов первого сорта (наборов конъюнктов). При этом «левые» прямоугольники (а-сеть^[2]) поставляются текущим состоянием окружения (набором фактов) d е Д, а «правые» прямоугольники (P-сеть) содержат (списки) невырожденных конъюнкций, полученных в процессе согласования всего антецедента продукции.

Рассмотрим, как идет процесс построения сети по шагам (см. рис. 3.7).

• 1. Первым предикатом является А_х = On (х, у). С ним согласуются факты w_lt w₂, w₄, w₈, подстановками соответствующих констант вместо переменных, что допустимо, поскольку все переменные пока свободны.
• 2. Вторым предикатом является А₂ = Left-of (г/, z). С ним согласуются факты w_3l w₁. При этом конъюнкцию А_х & А₂ согласуют конъюнкции фактов Wi&w$ с подстановкой [В_х/х, В₂/у, B₃/z и w₂&w₇ с подстановкой В_{/х, В₃/у, B₄/z]. Другие конъюнкции фактов, например, w_{&w₅, не являются согласующими, поскольку в подстановке [В_{/х_у 1/у, BJz] вместо у нужно подставить сразу В₂ и В₃, что невозможно.
• 3. Третьим предикатом является А₃ = Color (z, Black). Из трех фактов w_3j w₆y zc₉ с ним согласуются только факты zo₃, w₉. При этом конъюнкцию А_{&А₂&А₃ согласует только конъюнкция фактов w_t&w₅&w₉ с подстановкой [В_{/х, В₂/уу B₃/z. Другие конъюнкции фактов, например, zc^&zc₅&zo₃y не являются согласующими, поскольку в подстановке [В_{/х, В₂/у_у ?/z вместо z нужно подставить сразу В_{ и В_4у что невозможно.

Таким образом, в результате построения сети вычисляются все конъюнкции фактов, которые согласуют посылку рассматриваемого правила.

Рис. 3.7. Подбор фактов, согласующих антецедент одной продукции.

Заметим, что «процесс поставки фактов из d» требует очень небольших затрат. Дело в том, что база знаний (фактов) D организована так, что (в каждый фиксированный момент) с каждым предикатным символом связывается список конкретизаций — всех фактов, определяемых данным предикатным символом для различных комбинаций константных параметров.

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

Рис. 3.8. Фрагмент состояния d е D. Список фактов для предиката Color.

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

Еще одной полезной особенностью алгоритма Rete является то, что его структуры данных организованы так, что почти никогда не возникает необходимости повторного анализа информационной единицы. Все актуализированные факты из текущего состояния d с линейными затратами времени (но количеству фактов) попадают в соответствующие фрагменты a-сети, а все (допустимые!) составляющие конъюнкций для антецедентов по одному разу появляются в узлах р-сети.

Рассмотрим теперь (опять же, на модельном примере) работу алгоритма Rete для многих продукций (построение конфликтного множества). Пусть этими продукциями будут:

В данном случае нам даже не важно, какие именно предикаты входят в антецеденты правил, и не важно, каковы консеквенты q_Xi q₂, <73. Важно, что предикаты в антецедентах повторяются (это выделено цветом фона и рамочками), и алгоритм Rete позволяет учесть эти повторы и сэкономить усилия за счет избегания повторных вычислений. Пусть также зафиксировано некоторое состояние базы фактов d е D. Тогда структура данных алгоритма Rete будет выглядеть так, как это представлено на рис. 3.9. Обратите внимание, p-составляющая представляет собой ориентированное двоичное дерево, что серьезно упрощает работу со структурой данных, хотя и вызывает определенные проблемы при построении (неоднозначность).

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

При анализе механизма работы алгоритма Rete и выработке соображений о реализации его отдельных фрагментов весьма полезным может оказаться использование принципов организации реляционных баз данных¹. Текущее состояние окружения (набор фактов, формирующий d е D) в этом случае рассматривается как состояние БД^[3][4].

Рассмотрим конкретное продукционное правило г=р_]&…&р_т —> q. Каждому проинтерпретированному атомарному компоненту условия р_г входящему в антецедент, соответствует фрагмент a-сети. Это фрагмент можно трактовать как результат выполнения операции выборки из таблицы фактов, где условием выборки является равенство имени предикатного символа р_пате = «р» и равенство аргументов именам констант, если таковые заданы в р;. argj = «с^». Обозначим такую выборку Напомним, что все операции реляционной алгебры определены над отношениями и их же доставляют в качестве результата. Таким образом, результат операции выборки — это также отношение. Согласования (как уже сказано, их может быть несколько даже в случае одной продукции) для продукции г определяются результатом серии операций эквисоединения.

при этом если в атомах р_х и pj есть какие-то общие переменные, например, х на позиции k в предикате р_х и тот же х на позиции / в предикате р_г то для каждой такой переменной в условие эквисоединения добавляется s (Pi).mg_k = s (pj).argJ.

Результирующая таблица-отношение может оказаться и пустой, если для условия рассматриваемой продукции при данном состоянии базы фактов нет согласования. При этом промежуточные согласующие вершины в p-сети соответствуют «начальным» отрезкам общего эквисоединения s (p_{) •… • s (pj), где i < т. Таким образом, переход от некоторой р-вершины к другой, непосредственно с ней связанной, реализуется «единичной» операцией эквисоединения, которая каждый раз уменьшает ранг результирующей таблицы-отношения.

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

• [1] Условный «мир кубиков» — часто используемый иллюстративный пример в задачахискусственного интеллекта. В «мире кубиков» есть объекты — кубики, которые могут иметьсвойства (например, «цвет», «размер», …) и могут быть связаны отношениями (например,"стоять на", «левее»,…).
• [2] Мы не видим большого смысла в разбиении на a-сеть и p-сеть и оставляем эти обозначения по традиции. По существу, содержательным различием здесь является признак"поставляться из базы фактов" или «генерироваться в ходе анализа». Присутствует, разумеется, и эстетический момент — красивые греческие буквы. Па наш взгляд, более важныммоментом является двудольность графа.
• [3] Ульман Дж. Основы систем баз данных. М.: Финансы и статистика, 1983.
• [4] Возможные различные схемы реляционной БД, представляющей базу фактов. Можнопредположить для простоты, что БД состоит из единственного отношения. Каждый кортежэтого отношения — один факт. Пусть первым атрибутом является имя предиката р пате, а последующими атрибутами — arg_ 1, arg₂, … — имена аргументов, значениями которыхявляются имена констант.