Алгоритм Rete (Glikjnmb Rete)

Rete — эффективный алгоритм сопоставления с образцом для продукционных систем, экспертных систем и баз знаний, созданный Чарльзом Форги из Университета Карнеги — Меллона. Впервые был описан в рабочем документе 1974 года, затем в докторской диссертации 1979 года и в статье 1982 года (см. Ссылки). Rete стал основой многих популярных экспертных систем, включая CLIPS, Jess, Drools, BizTalk Rules Engine и Soar.

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

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

Описание

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

• Уменьшает или исключает избыточность условий за счет объединения узлов.
• Сохраняет частичные соответствия между фактами при слиянии разных типов фактов. Это позволяет избежать полного вычисления (англ. re-evaluation) всех фактов при любом изменении в рабочей памяти продукционной системы. Система работает только с самими изменениями (англ. deltas).
• Позволяет эффективно высвобождать память при удалении фактов.

Алгоритм Rete широко используется для реализации сопоставления с образцом в системах с циклом сопоставление-решение-действие (англ. match-resolve-act) для генерации и логического вывода.

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

Продукции (правила) обычно создаются аналитиками и программистами на некотором языке высокого уровня. Правила объединяются и транслируются, часто в рантайме, в выполнимую сеть Rete.

Когда факты актуализированы (англ. asserted), экспертная система создает записи (WME, англ. working memory elements) в оперативной памяти для каждого факта в виде кортежей разной длины. Каждая запись может содержать весь факт или наоборот, факт может быть системой записей фиксированной длины, обычно триплетов.

Все записи поступают в корневой узел сети. Узлы передают записи по дереву, где они сохраняются, либо достигают конечных вершин.

Альфа сеть

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

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

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

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

Бета сеть

Правая (бета) часть графа выполняет сборку записей. Она используется только при необходимости. Каждый узел имеет 2 входа и направляет результат в бета-память.

Бета-узлы работают с метками (tokens), обозначающими записи в альфа-памяти. Метка является единицей хранения и пересылки между узлами и памятью.

Бета-узел в качестве результата может создавать новые метки для списка записей или создавать списки меток.

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

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

Записи в конечных узлах бета-сети полностью соответствуют условию продукции и передаются в выходы Rete-сети, именуемые «п-узлы» от слова «продукция». При попадании записи в п-узел экземпляр правила продукции передается в «повестку дня», где они хранятся в очереди с приоритетом.

Бета-узлы объединяют списки записей бета-памяти и отдельных записей альфа-памяти. Каждый бета-узел связан с двумя входными блоками памяти. Альфа-память хранит записи и активирует бета-узлы ‘справа’ при поступлении каждой новой записи. Бета-память хранит списки записей и при поступлении записей активирует бета-узлы ‘слева’. При правой активации объединяющий узел сравнивает один или несколько атрибутов добавленной записи из входной альфа-памяти с соответствующими атрибутами каждой записи входной бета-памяти. При левой активации он просматривает добавленный список записей в бета-памяти, извлекает значения нужных атрибутов и сравнивает эти значения со значениями атрибутов каждой записи в альфа-памяти.

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

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

Для устранения избыточности узлов любая альфа- или бета-память может активировать множество бета-узлов. Как и с объединяющими узлами в бета-сети могут быть дополнительные типы узлов, некоторые из которых описаны ниже. Если Rete сеть не содержит бета-сети, альфа-узлы выдают метки, содержащие по одной записи, напрямую в п-узлы. В этом случае нет необходимости хранить записи в альфа-памяти.

Разрешение конфликтов

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

Разрешение конфликтов тесно связано с алгоритмом Rete, но не является его частью. Некоторые продукционные системы не выполняют разрешение конфликтов.

Выполнение продукций

После разрешения конфликтов система активирует экземпляры продукций и выполняет предписанные ими действия. Действия продукций в данным момент определены в представлениях записей.

По умолчанию система выполняет продукции по порядку пока они не закончатся. Каждая продукция выполняется в каждом цикле сопоставление-решение-действие только один раз. Это свойство называют «рефракцией». Однако выполнение продукций может быть прервано изменением в фактах. Действия продукций могут добавить, удалить или обновить факты. Каждый раз при таком изменении система входит в новый цикл сопоставление-решение-действие. Обновления представляются удалением старой и добавлением новой записи. Система распознает новые факты и меняет набор продукций в повестке дня, поэтому при выполнении любой продукции повестка дня может очиститься полностью и заполниться экземплярами других продукций.

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

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

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

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

Квантификация существования и всеобщности

По условиям можно выполнять выборку и слияние кортежей. Однако, используя дополнительные бета-узлы, сеть Rete может выявлять признаки в логике 1 порядка. Существование означает наличие хотя бы одного сопоставимого факта, всеобщность фиксирует выполнение некоторого условия всем множеством. Вариант квантификации всеобщности выделяет подмножество записей соответствующее условию. Так же можно проверять наличие конкретного количества соответствий.

Квантификация не обязательна для алгоритма Rete и известно несколько способов её использования. Существование часто описывается в документах как «отрицание». Отрицание существования требует специальных бета-узлов, проверяющих отсутствие соответствующих условию записей или списков. Узел передает список только если соответствия не найдено. Реализации этого квантора бывают разные. Например, узел на левом входе получает требуемое число записей, и сверяет его с числом записей в правом. Узел пропускает только списки в которых 0 списков соответствует условию. Или узлу добавляется память для записей с левого входа, подобная бета-памяти, собирающая списки с правого входа. Если в списке нет записей, узел отрицания активирует следующий бета-узел напрямую, не сохраняя списка в бета-память. Узел отрицания формализует немонотонное правило от противного.

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

Признак существования обычно строится как двойное отрицание «отсутствует факт отсутствия соответствия».

Индексация памяти

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

Удаление записей и списки записей

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

Обработка условия ИЛИ

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

Диаграмма

Данная диаграмма иллюстрирует базовую топологию сети Rete и демонстрирует ассоциации между разной памятью и узлами разных типов.

Пример сети Rete.

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

Более подробное и полное описание алгоритма Rete смотрите в главе 2 Doorenbos R. Production Matching for Large Learning Systems.

Дополнение

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

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

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

Оптимизация и производительность

Выявлены и описаны несколько способов оптимизации Rete. Некоторые только для специальных случаев и не относятся к системам общего назначения. Найдены альтернативные алгоритмы, такие как TREAT и LEAPS, обеспечивающие повышение эффективности, но примеров их реализации в коммерческих или open source проектах очень мало.

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

Rete II

В 1980-х Чарльз Форги создал новую версию алгоритма Rete II [1]. Детали алгоритма не разглашаются. По заявлениям Rete II демонстрирует повышенную эффективность (возможно на порядки) на сложных задачах ([2]). Он официально реализован в CLIPS/R2.

Rete II улучшен по двум параметрам: повышена общая производительность сети включая хешированную память для больших массивов данных, добавлен алгоритм обратного вывода, работающий на той же сети. Скорость обратного вывода по сравнению с Rete I повышена значительно.

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

Rete-NT

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

См. также

• Нормальный алгоритм
• en:Action selection mechanism
• Экспертная система
• Машина вывода
• Продукционная модель представления знаний

Ссылки

• Production Matching for Large Learning Systems — R Doorenbos Detailed and accessible description of Rete, also describes a variant named Rete/UL, optimised for large systems (PDF)
• According to the Rules (A short introduction from cut-the-knot)