Алгоритм Рете

Алгоритм Rete ( / ˈ r iː t iː / REE -tee , / ˈ r eɪ t iː / RAY -tee , редко / ˈ r iː t / REET , / r ɛ ˈ t eɪ / reh- TAY ) представляет собой сопоставление с образцом Алгоритм реализации систем, основанных на правилах . Алгоритм был разработан для эффективного применения множества правил или шаблонов ко многим объектам или фактам в базе знаний . Он используется для определения того, какое из правил системы должно сработать, на основе хранилища данных и фактов. Алгоритм Rete был разработан Чарльзом Л. Форги из Университета Карнеги-Меллона , впервые опубликован в рабочем документе в 1974 году, а затем подробно описан в его докторской диссертации 1979 года. диссертация и статья 1982 года.

Обзор

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

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* или совпадение, ориентированное на коллекцию ).

Описание

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

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

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

• Он предоставляет средства для сопоставления «многие-многие», что является важной функцией, когда необходимо найти многие или все возможные решения в поисковой сети.

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

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

Когда факты «заносятся» в рабочую память, механизм создает элементы рабочей памяти (WME) для каждого факта. Факты представляют собой кортежи и поэтому могут содержать произвольное количество элементов данных. Каждый WME может содержать весь кортеж или, альтернативно, каждый факт может быть представлен набором WME, где каждый WME содержит кортеж фиксированной длины. В этом случае кортежи обычно представляют собой тройки (3-кортежи).

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

Альфа-сеть

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

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

Бета-сеть

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

В описаниях 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 в альфа-памяти.

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

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

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

Оформление производства

Выполнив разрешение конфликта, движок теперь «запускает» первый производственный экземпляр, выполняя список действий, связанных с производством. Действия действуют на данные, представленные списком WME производственного экземпляра.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Обработка условий ORed

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

Диаграмма

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

Иллюстрирует базовый Rete.

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

Более подробное и полное описание алгоритма Rete см. в главе 2 книги Роберта Дооренбоса «Производственное сопоставление для больших обучающихся систем» (см. ссылку ниже).

Альтернативы

Альфа Сеть

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

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

Бета-сеть

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

Бета-узлы обрабатывают токены. Токен — это единица хранения в памяти, а также единица обмена между памятью и узлами. Во многих реализациях токены вводятся в альфа-память, где они используются для хранения отдельных WME. Эти токены затем передаются в бета-сеть.

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

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

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

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

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

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

Несколько оптимизаций для Rete были идентифицированы и описаны в научной литературе. Однако некоторые из них применяются только в очень специфических сценариях и поэтому часто практически не применяются в механизме правил общего назначения. Кроме того, альтернативные алгоритмы, такие как TREAT, разработанный Дэниелом П. Миранкером, Были сформулированы LEAPS и Design Time Inferencing (DeTI), которые могут обеспечить дополнительное повышение производительности.

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

Производительность Rete также во многом зависит от выбора реализации (независимо от топологии сети), один из которых (использование хеш-таблиц) приводит к серьезным улучшениям.Большинство тестов производительности и сравнений, доступных в Интернете, так или иначе предвзяты. Упомянем лишь частую предвзятость и несправедливое сравнение:1) использование игрушечных задач, таких как примеры «Манеры» и «Вальс»; такие примеры полезны для оценки конкретных свойств реализации, но они могут не отражать реальную производительность сложных приложений;2) использование старой реализации; например, ссылки в следующих двух разделах (Rete II и Rete-NT) сравнивают некоторые коммерческие продукты с полностью устаревшими версиями CLIPS и утверждают, что коммерческие продукты могут быть на порядки быстрее, чем CLIPS; при этом забываем, что CLIPS 6.30 (с введением хеш-таблиц, как в Rete II) на порядки быстрее, чем версия, используемая для сравнений (CLIPS 6.04).

Варианты

Сеть II

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

Rete II можно охарактеризовать двумя областями улучшения; конкретные оптимизации, связанные с общей производительностью сети Rete (включая использование хэш-памяти для повышения производительности при работе с большими наборами данных), а также включение алгоритма обратной цепочки, предназначенного для работы поверх сети Rete. Только обратная цепочка может объяснить самые резкие изменения в тестах, касающихся Rete и Rete II. Rete II реализован в коммерческом продукте Advisor от FICO, ранее называвшемся Fair Isaac.

Джесс (по крайней мере, версии 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.

Сеть-НТ

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

Рете-ОО

Учитывая, что Rete стремится поддерживать логику первого порядка (в основном операторы if-then-else ), Rete-OO Целью является создание системы, основанной на правилах, которая поддерживает неопределенность (когда информация для принятия решения отсутствует или является неточной). По предложению автора, правило « если Опасность, то Тревога » будет улучшено до чего-то вроде « при наличии вероятности Опасности будет определенная вероятность услышать Тревогу » или даже « Чем больше Опасность, тем громче следует быть тревогой ». Для этого он расширяет язык Drools (который уже реализует алгоритм Rete), чтобы обеспечить поддержку вероятностной логики , такой как нечеткая логика и байесовские сети .

См. также

• Механизм выбора действия
• Механизм вывода

Внешние ссылки

• Объяснение алгоритма Rete Брюса Шнайера, Dr. Dobb's Journal
• Согласование производства для больших систем обучения – Р. Дооренбос Подробное и доступное описание Rete, а также описан вариант под названием Rete/UL, оптимизированный для больших систем (PDF)
• По правилам (краткое вступление от «разрубить узел» )