Интернет магазин китайских планшетных компьютеров

Компьютеры - Алгоритм Rete - Описание

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

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

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

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

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

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

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

Альфа сеть

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

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

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

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

Бета сеть

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Признак Существования обычно строится как двойное отрицание ‘отсутствует факт отсутствия соответствия…’.

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

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

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

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

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

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

Диаграмма

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

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

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

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