Алгоритм сопоставления с образцом Rete

Введение

Алгоритм сопоставления шаблонов

Алгоритм Rete (произносится как /ˈriːtiː/ РИти, /ˈreɪtiː/ РЕЙти, реже /ˈriːt/ РИТ, /ˈrɛteɪ/ реТЭЙ) — это алгоритм сопоставления шаблонов для реализации систем, основанных на правилах. Алгоритм был разработан для эффективного применения множества правил или шаблонов к множеству объектов или фактов в базе знаний. Он используется для определения, какие правила системы должны быть активированы на основе хранилища данных, её фактов. Алгоритм Rete был разработан Чарльзом Л. Форги из Университета Карнеги — Меллона, впервые опубликован в виде рабочей статьи в 1974 году, а затем подробно описан в его докторской диссертации 1979 года и статье 1982 года.

Обзор

Наивная реализация экспертной системы может проверять каждое правило на соответствие известным фактам в базе знаний, выполнять (активировать) это правило, если необходимо, а затем переходить к следующему правилу (и возвращаться к первому правилу по завершении). Даже для баз знаний умеренного размера, содержащих правила и факты, такой наивный подход работает слишком медленно. Алгоритм Rete предоставляет основу для более эффективной реализации. Экспертная система, основанная на Rete, строит сеть узлов, где каждый узел (за исключением корневого) соответствует шаблону, встречающемуся в левой части (условию) правила. Путь от корневого узла к листовому узлу определяет полную левую часть правила. Каждый узел хранит информацию о фактах, удовлетворяющих этому шаблону. Эта структура по сути является обобщенным деревом отбора (trie). При утверждении или изменении новых фактов они распространяются по сети, вызывая аннотацию узлов, когда факт соответствует шаблону. Когда факт или комбинация фактов приводит к удовлетворению всех шаблонов для данного правила, достигается листовой узел и соответствующее правило активируется. Rete впервые был использован в качестве основного движка языка производственных систем OPS5, который применялся для создания ранних систем, включая R1 для Digital Equipment Corporation. Rete стал основой для многих популярных движков правил и оболочек экспертных систем, включая CLIPS, Jess, Drools, IBM Operational Decision Management, BizTalk Rules Engine и Soar. Слово "Rete" в переводе с латыни означает "сеть" или "гребень". То же слово используется в современном итальянском языке для обозначения "сети". Чарльз Форги, как сообщается, выбрал термин "Rete" из-за его использования в анатомии для описания сети кровеносных сосудов и нервных волокон. Алгоритм Rete разработан таким образом, чтобы жертвовать памятью ради повышения скорости. В большинстве случаев увеличение скорости по сравнению с наивными реализациями составляет несколько порядков (поскольку производительность Rete теоретически не зависит от количества правил в системе). Однако в очень больших экспертных системах оригинальный алгоритм Rete часто сталкивается с проблемами, связанными с потреблением памяти и ресурсов сервера. С тех пор были разработаны другие алгоритмы, как новые, так и основанные на Rete, требующие меньше памяти (например, Rete* или Collection Oriented Match).

A naive implementation of an expert system might check each rule against known facts in a knowledge base, firing that rule if necessary, then moving on to the next rule (and looping back to the first rule when finished). For even moderate sized rules and facts knowledge bases, this naive approach performs far too slowly. The Rete algorithm provides the basis for a more efficient implementation. A Rete based expert system builds a network of nodes, where each node (except the root) corresponds to a pattern occurring in the left hand side (the condition part) of a rule. The path from the root node to a leaf node defines a complete rule left hand side. Each node has a memory of facts that satisfy that pattern. This structure is essentially a generalized trie. As new facts are asserted or modified, they propagate along the network, causing nodes to be annotated when that fact matches that pattern. When a fact or combination of facts causes all of the patterns for a given rule to be satisfied, a leaf node is reached and the corresponding rule is triggered. Rete was first used as the core engine of the OPS5 production system language, which was used to build early systems including R1 for Digital Equipment Corporation. Rete has become the basis for many popular rule engines and expert system shells, including CLIPS, Jess, Drools, IBM Operational Decision Management, BizTalk Rules Engine, and Soar. The word 'Rete' is Latin for 'net' or 'comb'. The same word is used in modern Italian to mean 'network'. Charles Forgy has reportedly stated that he adopted the term 'Rete' because of its use in anatomy to describe a network of blood vessels and nerve fibers. The Rete algorithm is designed to sacrifice memory for increased speed. In most cases, the speed increase over naïve implementations is several orders of magnitude (because Rete performance is theoretically independent of the number of rules in the system). In very large expert systems, however, the original Rete algorithm tends to run into memory and server consumption problems. Other algorithms, both novel and Rete based, have since been designed that require less memory (e. g. Rete* or Collection Oriented Match).

Описание

Алгоритм Rete предоставляет обобщенное логическое описание реализации функциональности, отвечающей за сопоставление кортежей данных ("фактов") с продукциями ("правилами") в системе продукционного сопоставления с образцом (категория движка правил). Продукция состоит из одного или нескольких условий и набора действий, которые могут быть выполнены для каждого полного набора фактов, удовлетворяющих условиям. Условия проверяют атрибуты фактов, включая спецификаторы/идентификаторы типа фактов. Алгоритм Rete обладает следующими основными характеристиками:

Он снижает или устраняет определенные типы избыточности за счет совместного использования узлов. Он хранит частичные совпадения при выполнении соединений между различными типами фактов. Это, в свою очередь, позволяет продукционным системам избегать полной переоценки всех фактов при каждом изменении рабочей памяти продукционной системы. Вместо этого продукционной системе необходимо оценивать только изменения (дельты) в рабочей памяти. Он обеспечивает эффективное удаление элементов памяти при извлечении фактов из рабочей памяти. Алгоритм Rete широко используется для реализации функциональности сопоставления в механизмах сопоставления с образцом, использующих цикл "сопоставление-разрешение" для поддержки прямого цепочечного вывода. Он предоставляет возможность сопоставления "многие ко многим", что является важной особенностью, когда необходимо найти множество или все возможные решения в сети поиска. Сети Rete – это направленные ациклические графы, представляющие наборы правил более высокого уровня. Обычно они представлены во время выполнения с использованием сети объектов в памяти. Эти сети сопоставляют условия правил (образцы) с фактами (реляционные кортежи данных). Сети Rete действуют как тип реляционного процессора запросов, выполняющего проекции, отборы и соединения условно на произвольном количестве кортежей данных. Продукции (правила) обычно формулируются и определяются аналитиками и разработчиками с использованием языка правил высокого уровня. Они собираются в наборы правил, которые затем переводятся, часто во время выполнения, в исполняемый Rete. Когда факты "утверждаются" в рабочей памяти, движок создает элементы рабочей памяти (WME) для каждого факта. Факты являются кортежами и поэтому могут содержать произвольное количество элементов данных. Каждый WME может содержать целый кортеж, или, альтернативно, каждый факт может быть представлен набором WME, где каждый WME содержит кортеж фиксированной длины. В этом случае обычно используются тройки (3 кортежа). Каждый WME входит в сеть Rete через единственный корневой узел. Корневой узел передает каждый WME своим дочерним узлам, и каждый WME затем может распространяться по сети, возможно, сохраняясь во временных хранилищах, пока не достигнет терминального узла.

It reduces or eliminates certain types of redundancy through the use of node sharing. It stores partial matches when performing joins between different fact types. This, in turn, allows production systems to avoid complete re evaluation of all facts each time changes are made to the production system's working memory. Instead, the production system needs only to evaluate the changes (deltas) to working memory. It allows for efficient removal of memory elements when facts are retracted from working memory. The Rete algorithm is widely used to implement matching functionality within pattern matching engines that exploit a match resolve act cycle to support forward chaining and inferencing. It provides a means for many–many matching, an important feature when many or all possible solutions in a search network must be found. Retes are directed acyclic graphs that represent higher level rule sets. They are generally represented at run time using a network of in memory objects. These networks match rule conditions (patterns) to facts (relational data tuples). Rete networks act as a type of relational query processor, performing projections, selections and joins conditionally on arbitrary numbers of data tuples. Productions (rules) are typically captured and defined by analysts and developers using some high level rules language. They are collected into rule sets that are then translated, often at run time, into an executable Rete. When facts are "asserted" to working memory, the engine creates working memory elements (WMEs) for each fact. Facts are tuples, and may therefore contain an arbitrary number of data items. Each WME may hold an entire tuple, or, alternatively, each fact may be represented by a set of WMEs where each WME contains a fixed length tuple. In this case, tuples are typically triplets (3 tuples). Each WME enters the Rete network at a single root node. The root node passes each WME on to its child nodes, and each WME may then be propagated through the network, possibly being stored in intermediate memories, until it arrives at a terminal node.

Сеть Альфа

"Левая" (альфа) сторона графа узлов формирует сеть дискриминации, отвечающую за выбор отдельных WME на основе простых условных проверок, сопоставляющих атрибуты WME с константными значениями. Узлы в сети дискриминации могут также выполнять проверки, сравнивающие два или более атрибутов одного и того же WME. Если WME успешно соответствует условиям, представленным узлом, он передается следующему узлу. В большинстве движков непосредственные дочерние узлы корневого узла используются для проверки идентификатора сущности или типа факта каждого WME. Таким образом, все WME, представляющие один и тот же тип сущности, обычно проходят по данной ветви узлов в сети дискриминации. Внутри сети дискриминации каждая ветвь альфа-узлов (также называемых узлами с одним входом) заканчивается в памяти, называемой альфа-памятью. Эти памяти хранят наборы WME, соответствующих каждому условию в каждом узле данной ветви. WME, не соответствующие хотя бы одному условию в ветви, не сохраняются в соответствующей альфа-памяти. Ветви альфа-узлов могут разветвляться для минимизации избыточности условий.

Бета-сеть

"Правая" (бета) сторона графа в основном выполняет соединения между различными WME. Это необязательно и включается только при необходимости. Она состоит из 2 входных узлов, где каждый узел имеет "левый" и "правый" вход. Каждый бета-узел отправляет свой выход в бета-память. В описаниях Rete обычно упоминается передача токенов внутри бета-сети. Однако в этой статье мы опишем распространение данных с точки зрения списков WME, а не токенов, учитывая различные варианты реализации и основное назначение и использование токенов. По мере прохождения любого списка WME через бета-сеть к нему могут добавляться новые WME, и список может быть сохранен в бета-памяти. Список WME в бета-памяти представляет собой частичное соответствие условиям в данном продукционном правиле. Списки WME, достигающие конца ветви бета-узлов, представляют собой полное соответствие для одного продукционного правила и передаются в терминальные узлы. Эти узлы иногда называют p-узлами, где "p" означает "продукционное правило". Каждый терминальный узел представляет собой одно продукционное правило, и каждый список WME, поступающий в терминальный узел, представляет собой полный набор соответствующих WME для условий этого правила. Для каждого полученного списка WME продукционный узел "активирует" новый экземпляр продукционного правила в "повестке дня". Повестки дня обычно реализуются в виде приоритетных очередей. Бета-узлы обычно выполняют соединения между списками WME, хранящимися в бета-памяти, и отдельными WME, хранящимися в альфа-памяти. Каждый бета-узел связан с двумя входными памятью. Альфа-память содержит WM и выполняет "правые" активации бета-узла каждый раз, когда сохраняет новый WME. Бета-память содержит списки WME и выполняет "левые" активации бета-узла каждый раз, когда сохраняет новый список WME. Когда узел соединения получает правую активацию, он сравнивает один или несколько атрибутов недавно сохраненного WME из его входной альфа-памяти с соответствующими атрибутами конкретных WME в каждом списке WME, содержащемся во входной бета-памяти. Когда узел соединения получает левую активацию, он просматривает один недавно сохраненный список WME в бета-памяти, извлекая конкретные значения атрибутов данных WME. Он сравнивает эти значения со значениями атрибутов каждого WME в альфа-памяти. Каждый бета-узел выдает списки WME, которые либо сохраняются в бета-памяти, либо отправляются непосредственно в терминальный узел. Списки WME сохраняются в бета-памяти, когда движок будет выполнять дополнительные левые активации на последующих бета-узлах. Логически, бета-узел в начале ветви бета-узлов является особым случаем, поскольку он не принимает вход от какой-либо бета-памяти выше в сети. Разные движки решают эту проблему по-разному. Некоторые движки используют специализированные адаптерные узлы для подключения альфа-памяти к левому входу бета-узлов. Другие движки позволяют бета-узлам принимать вход непосредственно из двух альфа-памятей, рассматривая одну как "левый" вход, а другую как "правый" вход. В обоих случаях "начальные" бета-узлы получают входные данные из двух альфа-памятей. Для устранения избыточности узлов любая альфа- или бета-память может использоваться для выполнения активаций на нескольких бета-узлах. Помимо узлов соединения, бета-сеть может содержать дополнительные типы узлов, некоторые из которых описаны ниже. Если Rete не содержит бета-сети, альфа-узлы передают токены, каждый из которых содержит один WME, непосредственно в p-узлы. В этом случае может не быть необходимости хранить WME в альфа-памяти.

The "right" (beta) side of the graph chiefly performs joins between different WMEs. It is optional, and is only included if required. It consists of 2 input nodes where each node has a "left" and a "right" input. Each beta node sends its output to a beta memory. In descriptions of Rete, it is common to refer to token passing within the beta network. In this article, however, we will describe data propagation in terms of WME lists, rather than tokens, in recognition of different implementation options and the underlying purpose and use of tokens. As any one WME list passes through the beta network, new WMEs may be added to it, and the list may be stored in beta memories. A WME list in a beta memory represents a partial match for the conditions in a given production. WME lists that reach the end of a branch of beta nodes represent a complete match for a single production, and are passed to terminal nodes. These nodes are sometimes called p nodes, where "p" stands for production. Each terminal node represents a single production, and each WME list that arrives at a terminal node represents a complete set of matching WMEs for the conditions in that production. For each WME list it receives, a production node will "activate" a new production instance on the "agenda". Agendas are typically implemented as prioritised queues. Beta nodes typically perform joins between WME lists stored in beta memories and individual WMEs stored in alpha memories. Each beta node is associated with two input memories. An alpha memory holds WM and performs "right" activations on the beta node each time it stores a new WME. A beta memory holds WME lists and performs "left" activations on the beta node each time it stores a new WME list. When a join node is right activated, it compares one or more attributes of the newly stored WME from its input alpha memory against given attributes of specific WMEs in each WME list contained in the input beta memory. When a join node is left activated it traverses a single newly stored WME list in the beta memory, retrieving specific attribute values of given WMEs. It compares these values with attribute values of each WME in the alpha memory. Each beta node outputs WME lists that are either stored in a beta memory or sent directly to a terminal node. WME lists are stored in beta memories whenever the engine will perform additional left activations on subsequent beta nodes. Logically, a beta node at the head of a branch of beta nodes is a special case because it takes no input from any beta memory higher in the network. Different engines handle this issue in different ways. Some engines use specialised adapter nodes to connect alpha memories to the left input of beta nodes. Other engines allow beta nodes to take input directly from two alpha memories, treating one as a "left" input and the other as a "right" input. In both cases, "head" beta nodes take their input from two alpha memories. In order to eliminate node redundancies, any one alpha or beta memory may be used to perform activations on multiple beta nodes. As well as join nodes, the beta network may contain additional node types, some of which are described below. If a Rete contains no beta network, alpha nodes feed tokens, each containing a single WME, directly to p nodes. In this case, there may be no need to store WMEs in alpha memories.

Решение конфликтов

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

Производственное исполнение

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

Having performed conflict resolution, the engine now "fires" the first production instance, executing a list of actions associated with the production. The actions act on the data represented by the production instance's WME list. By default, the engine will continue to fire each production instance in order until all production instances have been fired. Each production instance will fire only once, at most, during any one match resolve act cycle. This characteristic is termed refraction. However, the sequence of production instance firings may be interrupted at any stage by performing changes to the working memory. Rule actions can contain instructions to assert or retract WMEs from the working memory of the engine. Each time any single production instance performs one or more such changes, the engine immediately enters a new match resolve act cycle. This includes "updates" to WMEs currently in the working memory. Updates are represented by retracting and then re asserting the WME. The engine undertakes matching of the changed data which, in turn, may result in changes to the list of production instances on the agenda. Hence, after the actions for any one specific production instance have been executed, previously activated instances may have been de activated and removed from the agenda, and new instances may have been activated. As part of the new match resolve act cycle, the engine performs conflict resolution on the agenda and then executes the current first instance. The engine continues to fire production instances, and to enter new match resolve act cycles, until no further production instances exist on the agenda. At this point the rule engine is deemed to have completed its work, and halts. Some engines support advanced refraction strategies in which certain production instances executed in a previous cycle are not re executed in the new cycle, even though they may still exist on the agenda. It is possible for the engine to enter into never ending loops in which the agenda never reaches the empty state. For this reason, most engines support explicit "halt" verbs that can be invoked from production action lists. They may also provide automatic loop detection in which never ending loops are automatically halted after a given number of iterations. Some engines support a model in which, instead of halting when the agenda is empty, the engine enters a wait state until new facts are asserted externally. As for conflict resolution, the firing of activated production instances is not a feature of the Rete algorithm. However, it is a central feature of engines that use Rete networks. Some of the optimisations offered by Rete networks are only useful in scenarios where the engine performs multiple match resolve act cycles.

Экзистенциальные и универсальные количественные определения

Условные тесты чаще всего используются для выполнения выборок и соединений для отдельных кортежей. Однако, реализуя дополнительные типы бета-узлов, сети Rete могут выполнять квантификацию. Экзистенциальная квантификация включает в себя проверку существования хотя бы одного набора соответствующих WME в рабочей памяти. Универсальная квантификация включает в себя проверку того, что весь набор WME в рабочей памяти соответствует заданному условию. Вариация универсальной квантификации может проверять, соответствует ли заданное количество WME, выбранных из набора WME, заданным критериям. Это может быть проверка либо точного количества, либо минимального количества совпадений. Квантификация не реализована повсеместно в Rete-движках, и, где она поддерживается, существует несколько вариаций. Вариант экзистенциальной квантификации, называемый отрицанием, широко, хотя и не повсеместно, поддерживается и описан в основополагающих документах. Экзистенциально отрицаемые условия и конъюнкции включают использование специализированных бета-узлов, которые проверяют отсутствие соответствующих WME или наборов WME. Эти узлы распространяют списки WME только в случае, если совпадение не найдено. Точная реализация отрицания варьируется. В одном подходе узел поддерживает простой счетчик для каждого списка WME, получаемого с левого входа. Счетчик указывает количество совпадений, найденных с WME, полученными с правого входа. Узел распространяет только списки WME, счетчик которых равен нулю. В другом подходе узел поддерживает дополнительную память для каждого списка WME, получаемого с левого входа. Эта память является формой бета-памяти и хранит списки WME для каждого совпадения с WME, полученными с правого входа. Если в памяти списка WME нет списков WME, он распространяется по сети. В этом подходе отрицающие узлы обычно активируют другие бета-узлы напрямую, а не сохраняют свой вывод в дополнительной бета-памяти. Отрицающие узлы обеспечивают форму «отрицания как отказа». При внесении изменений в рабочую память список WME, который ранее не соответствовал никаким WME, теперь может соответствовать вновь добавленным WME. В этом случае распространенный список WME и все его расширенные копии должны быть отозваны из бета-памяти ниже по сети. Второй описанный выше подход часто используется для поддержки эффективных механизмов удаления списков WME. При удалении списков WME соответствующие экземпляры продукции деактивируются и удаляются из повестки дня. Экзистенциальную квантификацию можно выполнить, объединив два отрицающих бета-узла. Это представляет семантику двойного отрицания (например, «Если НЕ НЕ соответствующие WME, то»). Это распространенный подход, используемый несколькими системами продукций.

Conditional tests are most commonly used to perform selections and joins on individual tuples. However, by implementing additional beta node types, it is possible for Rete networks to perform quantifications. Existential quantification involves testing for the existence of at least one set of matching WMEs in working memory. Universal quantification involves testing that an entire set of WMEs in working memory meets a given condition. A variation of universal quantification might test that a given number of WMEs, drawn from a set of WMEs, meets given criteria. This might be in terms of testing for either an exact number or a minimum number of matches. Quantification is not universally implemented in Rete engines, and, where it is supported, several variations exist. A variant of existential quantification referred to as negation is widely, though not universally, supported, and is described in seminal documents. Existentially negated conditions and conjunctions involve the use of specialised beta nodes that test for non existence of matching WMEs or sets of WMEs. These nodes propagate WME lists only when no match is found. The exact implementation of negation varies. In one approach, the node maintains a simple count on each WME list it receives from its left input. The count specifies the number of matches found with WMEs received from the right input. The node only propagates WME lists whose count is zero. In another approach, the node maintains an additional memory on each WME list received from the left input. These memories are a form of beta memory, and store WME lists for each match with WMEs received on the right input. If a WME list does not have any WME lists in its memory, it is propagated down the network. In this approach, negation nodes generally activate further beta nodes directly, rather than storing their output in an additional beta memory. Negation nodes provide a form of 'negation as failure'. When changes are made to working memory, a WME list that previously matched no WMEs may now match newly asserted WMEs. In this case, the propagated WME list and all its extended copies need to be retracted from beta memories further down the network. The second approach described above is often used to support efficient mechanisms for removal of WME lists. When WME lists are removed, any corresponding production instances are de activated and removed from the agenda. Existential quantification can be performed by combining two negation beta nodes. This represents the semantics of double negation (e. g., "If NOT NOT any matching WMEs, then "). This is a common approach taken by several production systems.

Индексирование памяти

Алгоритм Rete не предписывает какого-либо конкретного подхода к индексации рабочей памяти. Однако большинство современных продукционных систем предоставляют механизмы индексации. В некоторых случаях индексируются только бета-памяти, а в других – и альфа-, и бета-памяти. Эффективная стратегия индексации является ключевым фактором, определяющим общую производительность продукционной системы, особенно при выполнении наборов правил, приводящих к высококомбинаторному сопоставлению с образцом (то есть к интенсивному использованию бета-соединений), или, для некоторых движков, при выполнении наборов правил, которые выполняют значительное количество отмен WME в ходе нескольких циклов разрешения конфликтов. Памяти часто реализуются с использованием комбинаций хеш-таблиц, а хеш-значения используются для выполнения условных соединений на подмножествах списков WME и самих WME, а не на всем содержимом памяти. Это, в свою очередь, часто значительно уменьшает количество вычислений, выполняемых сетью Rete.

Удаление WME и списков WME

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

Обработка ОРЕД условия

При определении продукций в наборе правил часто допускается группировка условий с помощью логического ИЛИ. Во многих системах продукций это реализуется путем интерпретации одной продукции, содержащей несколько шаблонов, соединенных ИЛИ, как эквивалента нескольких продукций. Получающаяся сеть Rete содержит наборы терминальных узлов, которые вместе представляют собой отдельные продукции. Такой подход не допускает никакого сокращения вычисления условий, соединенных ИЛИ. Кроме того, в некоторых случаях это может привести к активации дублирующих экземпляров продукций в повестке дня, когда один и тот же набор WME соответствует нескольким внутренним продукциям. Некоторые движки предоставляют механизм дедупликации повестки дня для решения этой проблемы.

Диаграмма

На следующей диаграмме показана базовая топология Rete и продемонстрированы связи между различными типами узлов и памятью. В большинстве реализаций узлы типов используются для выполнения первого уровня отбора элементов рабочей памяти. Узлы типов можно рассматривать как специализированные узлы отбора. Они различают различные типы отношений между кортежами. На диаграмме не показано использование специализированных типов узлов, таких как узлы отрицательной конъюнкции. Некоторые движки реализуют несколько различных специализаций узлов для расширения функциональности и достижения максимальной оптимизации. Диаграмма представляет собой логическое представление Rete. Реализации могут отличаться в деталях физической организации. В частности, на диаграмме показаны фиктивные входные данные, обеспечивающие правую активацию в начале ветвей бета-узлов. Движки могут использовать и другие подходы, например, адаптеры, позволяющие альфа-памяти выполнять правую активацию напрямую. Диаграмма не иллюстрирует все возможные варианты совместного использования узлов. Более подробное и полное описание алгоритма Rete можно найти в главе 2 книги Роберта Дуренбоса «Production Matching for Large Learning Systems» (см. ссылку ниже).

Сеть Альфа

Возможным вариантом является добавление дополнительных ячеек памяти для каждого промежуточного узла в сети дискриминации. Это увеличивает нагрузку на Rete, но может быть полезно в ситуациях, когда правила динамически добавляются или удаляются из Rete, что упрощает динамическое изменение топологии сети дискриминации. Альтернативная реализация описана Дооренбосом. В этом случае сеть дискриминации заменяется набором ячеек памяти и индексом. Индекс может быть реализован с использованием хеш-таблицы. Каждая ячейка памяти хранит WME, соответствующие одному условному шаблону, а индекс используется для обращения к ячейкам памяти по их шаблону. Этот подход целесообразен только тогда, когда WME представлены кортежами фиксированной длины, и длина каждого кортежа невелика (например, 3 кортежа). Кроме того, подход применим только к условным шаблонам, выполняющим проверку на равенство с константными значениями. Когда WME поступает в Rete, индекс используется для поиска набора ячеек памяти, условный шаблон которых соответствует атрибутам WME, и WME затем добавляется непосредственно в каждую из этих ячеек памяти. Сама по себе эта реализация не содержит входных узлов с одним входом. Однако для реализации проверок на неравенство Rete может содержать дополнительные сети с входными узлами с одним входом, через которые WME проходят перед помещением в ячейку памяти. В качестве альтернативы, проверки на неравенство могут быть выполнены в бета-сети, описанной ниже.

Бета-сеть

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

Различные соображения

Хотя алгоритм Rete и не определяет этого, некоторые движки предоставляют расширенную функциональность для обеспечения большего контроля над поддержанием истинности. Например, обнаружение совпадения для одного правила может привести к утверждению новых WME, которые, в свою очередь, соответствуют условиям другого правила. Если последующее изменение рабочей памяти делает первое совпадение недействительным, это может означать, что и второе совпадение также недействительно. Алгоритм Rete не определяет никаких механизмов для автоматического определения и обработки этих логических зависимостей в отношении истинности. Однако некоторые движки поддерживают дополнительную функциональность, позволяющую автоматически поддерживать эти зависимости. В этом случае отмена одного WME может привести к автоматической отмене дополнительных WME для поддержания логических утверждений об истинности. Алгоритм Rete также не определяет подхода к обоснованию. Обоснование относится к механизмам, обычно необходимым в экспертных и системах принятия решений, когда система, в простейшем случае, сообщает о каждом внутреннем решении, использованном для достижения конечного вывода. Например, экспертная система может обосновать вывод о том, что животное является слоном, указав, что оно большое, серое, имеет большие уши, хобот и бивни. Некоторые движки предоставляют встроенные системы обоснования в сочетании со своей реализацией алгоритма Rete. Данная статья не содержит исчерпывающего описания всех возможных вариаций или расширений алгоритма Rete. Существуют и другие аспекты и инновации. Например, движки могут предоставлять специализированную поддержку внутри сети Rete для применения обработки правил сопоставления с образцом к конкретным типам данных и источникам, таким как программные объекты, данные XML или таблицы реляционных баз данных. Другой пример касается дополнительных возможностей временной маркировки, предоставляемых многими движками для каждого WME, входящего в сеть Rete, и использования этих временных меток в сочетании со стратегиями разрешения конфликтов. Движки значительно различаются по способу обеспечения программного доступа к движку и его рабочей памяти и могут расширять базовую модель Rete для поддержки форм параллельной и распределенной обработки.

Although not defined by the Rete algorithm, some engines provide extended functionality to support greater control of truth maintenance. For example, when a match is found for one production, this may result in the assertion of new WMEs which, in turn, match the conditions for another production. If a subsequent change to working memory causes the first match to become invalid, it may be that this implies that the second match is also invalid. The Rete algorithm does not define any mechanism to define and handle these logical truth dependencies automatically. Some engines, however, support additional functionality in which truth dependencies can be automatically maintained. In this case, the retraction of one WME may lead to the automatic retraction of additional WMEs in order to maintain logical truth assertions. The Rete algorithm does not define any approach to justification. Justification refers to mechanisms commonly required in expert and decision systems in which, at its simplest, the system reports each of the inner decisions used to reach some final conclusion. For example, an expert system might justify a conclusion that an animal is an elephant by reporting that it is large, grey, has big ears, a trunk and tusks. Some engines provide built in justification systems in conjunction with their implementation of the Rete algorithm. This article does not provide an exhaustive description of every possible variation or extension of the Rete algorithm. Other considerations and innovations exist. For example, engines may provide specialised support within the Rete network in order to apply pattern matching rule processing to specific data types and sources such as programmatic objects, XML data or relational data tables. Another example concerns additional time stamping facilities provided by many engines for each WME entering a Rete network, and the use of these time stamps in conjunction with conflict resolution strategies. Engines exhibit significant variation in the way they allow programmatic access to the engine and its working memory, and may extend the basic Rete model to support forms of parallel and distributed processing.

Рете II

В 1980-х годах Чарльз Форги разработал преемника алгоритма Rete, названного Rete II. В отличие от оригинального Rete (который находится в общественном достоянии), этот алгоритм не был опубликован. Rete II заявляет о более высокой производительности для более сложных задач (вплоть до нескольких порядков величины) и официально реализован в CLIPS/R2 – реализации на C/++, а также в OPSJ – реализации на Java, появившейся в 1998 году. По результатам тестов KnowledgeBased Systems Corporation, Rete II обеспечивает улучшение производительности в сложных задачах примерно в 100–1000 раз. Rete II характеризуется двумя основными улучшениями: специфическими оптимизациями, касающимися общей производительности сети Rete (включая использование хеш-памяти для повышения производительности при работе с большими объемами данных), и включением алгоритма обратного прохода, разработанного для работы поверх сети Rete. Именно обратный проход может объяснить наиболее значительные различия в результатах тестов Rete и Rete II. Rete II реализован в коммерческом продукте Advisor от FICO, ранее известном как Fair Isaac.

Jess (по крайней мере, версии 5.0 и более поздние) также добавляет коммерческий алгоритм обратного прохода поверх сети Rete, однако нельзя утверждать, что он полностью реализует Rete II, частично из-за отсутствия публично доступной полной спецификации.

Рете-III

В начале 2000-х годов движок Rete III был разработан Чарльзом Форги в сотрудничестве с инженерами FICO. Алгоритм Rete III, отличный от Rete NT, является зарегистрированной торговой маркой FICO для Rete II и реализован как часть движка FICO Advisor. По сути, это движок Rete II с API, обеспечивающим доступ к движку Advisor, поскольку движок Advisor может взаимодействовать с другими продуктами FICO.

Rete-NT

В 2010 году Форги разработал новое поколение алгоритма Rete. В тесте InfoWorld алгоритм был признан в 500 раз быстрее оригинального алгоритма Rete и в 10 раз быстрее его предшественника, Rete II. В настоящее время этот алгоритм лицензирован компании Sparkling Logic, в которую Форги вошел в качестве инвестора и стратегического советника, и используется в качестве логического движка продукта SMARTS.

Рети-ОО

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