| dbpprop:abstract
|
- The Rete algorithm is an efficient pattern matching algorithm for implementing production rule systems. The Rete algorithm was designed by Dr Charles L. Forgy of Carnegie Mellon University, first published in a working paper in 1974, and later elaborated in his 1979 Ph.D. thesis and a 1982 paper. Rete has become the basis for many popular expert system shells, including CLIPS, Jess, Drools, BizTalk Rules Engine and Soar. The word 'Rete' is taken from the Latin for 'net'. The same word is used in modern Italian to mean . Rete is generally pronounced /ˈriːtiː/ -tee, but a common academic pronunciation is /ˈreɪtiː/ -tee, which is closer to modern Italian pronunciation. Other variant pronunciations include /ˈriːt/ reet and, rarely, /rɛˈteɪ/ re-tay. A naïve implementation of an expert system might check each rule against the known facts in the 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 naïve 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 which 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. 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 consumption problems. Other algorithms, both novel and Rete-based, have since been designed which require less memory.
- Der Rete-Algorithmus (rete, lat. für Netz oder Netzwerk) ist ein Algorithmus und Expertensystem zur Mustererkennung und zur Abbildung von Systemprozessen über Regeln. Es wurde vom US-amerikanischen Informatiker Charles Forgy im Rahmen seiner Doktorarbeit entwickelt bzw. die ihn 1979 zum Titel führen sollte. Der Algorithmus ist frei, da das amerikanische Verteidigungsministerium bei seiner Erstellung hinreichend mit beteiligt war. Der Algorithmus war bei seiner Entwicklung den bestehenden Systemen um den Faktor 3000 überlegen. Der Algorithmus hat bislang zwei Nachkömmlinge, Rete II und Rete III. Beide sind ca. 50 mal schneller als der ursprüngliche Ansatz. Rete III umfasst ein paar Erweiterungen, die seine Effizienz nochmals leicht erhöhen. Die Entwicklung war eng an die Plattform DEC XCON angelehnt und fand ihre Implementierung zunächst in OPS-Systemen, speziell in OPS2 bzw. später in OPS5. Einsparungen in Millionenhöhe wurden benannt. Das implementierte Regelwerk hatte im Endausbau ca. 10.000 Elemente.
- El algoritmo Rete es un algoritmo de reconocimiento de patrones eficiente para implementar sistema de producción de reglas. Fue creado por el Dr. Charles L. Forgy en la Carnegie Mellon University, su primera referencia escrita data de 1974, y apareció de forma más detallada en su tesis doctoral y en un artículo científico de 1982. Rete es hoy en día la base de muchos sistemas expertos muy famosos, incluyendo CLIPS, Jess, JBoss Rules, y Soar. Una implementación simple de un sistema experto comprobaría cada regla con los hechos de la base de conocimiento activando la regla si corresponde, y pasando a evaluar la siguiente (volviendo a la primera al final). Este algoritmo, incluso para un número bajo de reglas y hecho, tiene un tiempo de ejecución muy alto (haciéndolo inadecuado para sistemas en producción reales). El algoritmo Rete (cuya pronunciación suele ser 'REET', 'REE-tee' o, en Europa, 're-tay' que viene de su pronunciación en Latín, dado que 'rete' significa red en Latín) es la base de diversas implementaciones más eficientes de sistemas expertos. Un sistema experto basado en Rete construye una red de nodos, donde cada uno de ellos (excepto el nodo raíz) representa un patrón que aparece en la parte izquierda (el condicional) de una regla. Por lo tanto, el camino desde el nodo raíz a una hoja define la parte condicional entera de una regla. Cada nodo tiene un memoria de hechos que satisfacen su patrón. Esta estructure es, básicamente, un Trie. A medida que se añaden o modifican hechos, se propagan los cambios por la red, haciendo que los nodos que se activan con el patrón se activen. Cuando un hecho o un conjunto de ellos hace que todos los patrones de una regla se satisfagan, se llega a un nodo hoja y la regla es activada. Básicamente, el algoritmo Rete sacrifica memoria para incrementar velocidad de procesamiento. En la mayoría de los casos el incremento de velocidad comparado con la implementación simple es de varios órdenes de magnitud (porque teóricamente el rendimiento de Rete es independiente del número de reglas del sistema). En sistemas expertos muy grandes, sin embargo, Rete suele presentar problemas por su gran cantidad de consumo memoria. Existen otros algoritmos tanto basados en él como independientes, que necesitan menos memoria.
- L'algorithme de Rete est un algorithme performant de filtrage par motif (« pattern matching ») intervenant dans l'implémentation de systèmes de règles de production. L'algorithme a été conçu par le Dr Charles L. Forgy de l'Université Carnegie Mellon, tout d'abord publié comme une note de travail en 1974, puis plus tard élaboré dans sa thèse PhD de 1979 et dans une publication de 1982. Rete est devenu la base de nombreux systèmes experts tels que Clips, Jess, JBoss Rules, et Soar. Une implémentation naïve d'un système expert pourrait vérifier chaque règle en la confrontant aux faits de la base de connaissance, éliminant les règles au fur et à mesure, puis passant à la règle suivante (et rebouclant à la première règle une fois terminé). Même pour des règles et des bases de connaissance de taille réduite, cette approche naïve est bien trop longue. L'algorithme de Rete (habituellement prononcé « REET », « REE-tee » ou, en Europe, « re-tay » d'après la prononciation latine, du latin « rete » pour réseau) fournit la base pour une exécution plus efficace d'un système expert. Un système expert basé sur Rete établit un réseau des nœuds, où chaque nœud (excepté la racine) correspond à un modèle se produisant dans le « côté gauche » d'une règle. Le chemin du nœud racine à un nœud externe (leaf node) définit un « côté gauche » complet de règle. Chaque nœud a une mémoire des faits qui satisfont ce modèle. Cette structure est essentiellement un Trie généralisé. Lorsque de nouveaux faits sont affirmés ou modifiés, ils se propagent le long du réseau, annotant les nœuds quand les faits correspondent au modèle. Quand un fait ou une combinaison des faits satisfait tous les modèles d'une règle donnée, un nœud externe (leaf node) est atteint et la règle correspondante est déclenchée. L'algorithme de Rete est conçu pour sacrifier la mémoire au profit de la vitesse. Dans la plupart des cas, l'augmentation de la vitesse par rapport à une implémentation naïve est de plusieurs ordres de grandeur (parce que l'exécution de Rete est théoriquement indépendante du nombre de règles dans le système). Dans les systèmes experts très grands, cependant, l'algorithme de Rete original tend à rencontrer des problèmes de consommation de mémoire. On a depuis conçu d'autres algorithmes, basés sur Novel d'une part et Rete d'autre part, qui exigent moins de mémoire.
- L'Algoritmo rete è un efficiente algoritmo di pattern matching per l'implementazione di sistemi di produzione a regole. L'Algoritmo Rete è stato creato dal Dr. Charles Forgy della Carnegie Mellon University, la prima pubblicazione dell'algoritmo risale al 1974 e dopo rielaborato nel 1979 per la sua tesi di dottorato. L'algoritmo Rete è alla base di alcuni tra i più popolari sistemi esperti come ad esempio: Blaze Advisor JRules OPS5 CLIPS Jess LISA Un'implementazione 'naïve' di un sistema esperto dovrebbe verificare ogni regola rispetto ai fatti conosciuti presenti nella base di conoscenza attivando la regola necessaria e poi passando a controllare le altre regole applicabili. Questo approccio 'naïve' anche per piccoli sistemi con un numero prefissato di regole e fatti, si rivela molto inefficiente. L'algoritmo Rete fornisce una efficiente base per l'implementazione di un sistema esperto. Un sistema esperto rete-based costruisce un network di nodi, dove ogni nodo (ad eccezione del nodo radice) corrisponde ad un pattern presente nella parte sinistra di una regola. Il cammino che collega il nodo radice al nodo foglia definisce una completa parte sinistra di una regola. Ogni nodo ha una memoria di fatti che soddisfano quel pattern. Questa struttura è genericamente riconducibile ad un Trie
- Reteアルゴリズムとは、プロダクションシステム実装のための効率的なパターンマッチングアルゴリズムである。カーネギーメロン大学のチャールズ・フォーギーが設計したもので、1974年の論文で最初に公表し、1979年の学位論文や1982年の論文でさらに洗練された（参考文献参照）。数々のエキスパートシステムの基盤として使われており、JRules、OPS5、CLIPS、Jess、Drools、Soar、LISA、Microsoft BizTalk Server におけるビジネスルールエンジン、TIBCO BusinessEvents などがある。Rete とは、ラテン語の 'rete'（網、ネットワーク）が語源である。 素朴なエキスパートシステムの実装では、知識ベース内の既知の事実と規則（ルール）群を順次照合し、適合するルールを実行していく。ルール群や知識ベースがそれほど大きくなくても、この素朴な方法では性能は期待できない。 Reteアルゴリズムはより効率的なエキスパートシステムを実装する基盤を提供する。Reteに基づいたエキスパートシステムでは、ルールやデータの依存関係がノードのネットワークから構成される内部表現に置き換えられる。各ノードはルート（根）となるノード以外はルールの左辺部（Left Hand Side、LHS）に現われるパターンに対応している。ルートノードから末端ノードまでの経路が1つのルールの左辺全体を表す。各ノードにはそのパターンに適合した事実が記憶される。この構造は基本的にトライ木の応用である。 新たな事実が表明されたり、事実が更新されると、それがネットワーク上を伝播していき、あるノードでパターンマッチする。1つまたは複数の事実によってルールの左辺のパターン全てにマッチした場合、その規則を表す経路の末端ノードに到達し、そのルールの右辺部（Right Hand Side、RHS）が起動される。 Reteアルゴリズムは高速化のためにメモリを消費する設計となっている。Reteの性能は理論的にはシステム内のルール数に依存し、非常に大規模なエキスパートシステムではReteアルゴリズムによるメモリ枯渇問題が発生しやすい。これを解決すべく、Reteアルゴリズムの改良版や他のアルゴリズムが考案されてきた。
- Het rete-algoritme is een algoritme voor patroonmatching, gebruikt bij regelgebaseerde productiesystemen. Het werd in 1979 ontwikkeld door Dr. Charles L. Forgy van de Carnegie-Mellon Universiteit. Het rete-algoritme wordt toegepast in veelgebruikte expertsystemen zoals OPS5, CLIPS, JESS en LISA. Een eenvoudige implementatie van een expertsysteem zou elke productieregel kunnen vergelijken met alle feiten in de feitenverzameling van het expertsysteem, en deze proberen uit te voeren wanneer aan de condities van de productieregel voldaan zijn. Zelfs voor kleine feitenverzamelingen en kennisbanken is deze benadering veel te traag. Het rete-algoritme (van het Latijnse rete, dat net, netwerk betekent) ligt aan de basis van een meer efficiënte implementatie: het algoritme bouwt een graaf op waarbij elke knoop overeenkomt met een bepaald patroon in de condities van de productieregel. Het pad van de wortel tot een terminale knoop definieert een dergelijke (conjunctie van) condities. Elke knoop houdt in het geheugen de lijst van feiten bij die aan het patroon horend bij de knoop voldoen.
- Rete - эффективный алгоритм сопоставления с образцом для продукционных систем, экспертных систем и баз знаний, созданный Чарльзом Форги из Университета Карнеги Меллона. Впервые был описан в рабочем документе 1974 года, затем в докторской диссертации 1979 и в статье 1982 года. Rete стал основой многих популярных экспертных систем, включая CLIPS, Jess, Drools, BizTalk Rules Engine and Soar. Слово 'rete' на латыни означает 'сеть', а в современном итальянском 'связи'. Произносится как 'рити', в академической среде 'рейти', что ближе к современному итальянскому произношению. Другие варианты 'рит' и, редко, 'ретэ'. При буквальной реализации экспертная система проверяет применимость каждого правила вывода к каждому факту базы знаний, при необходимости выполняет его и переходит к следующему правилу, возвращаясь в начало при исчерпании всех правил. Даже для небольшого набора правил и фактов такой метод работает неприемлемо медленно. Алгоритм Rete обеспечивает более высокую эффективность. При использовании Rete экспертная система строит специальный граф или префиксное дерево, узлам которого соответствуют части условий правил. Путь от корня до листа образует полное условие некоторой продукции. В процессе работы каждый узел хранит список фактов соответствующих условию. При добавлении или модификации факта он прогоняется по сети, при этом отмечаются узлы, условиям которых данный факт соответствует. При выполнении полного условия правила, когда система достигает листа графа, правило выполняется. Алгоритм Rete жертвует объемом памяти ради скорости. В большинстве случаев скорость возрастает на порядки (т. к. эффективность теоретически не зависит от числа правил в системе). В экспертных системах с большим числом правил классический Rete требует слишком много памяти, но появились новые алгоритмы, в том числе основанные на Rete, ограничивающиеся разумным объемом.
|
| rdfs:comment
|
- The Rete algorithm is an efficient pattern matching algorithm for implementing production rule systems. The Rete algorithm was designed by Dr Charles L. Forgy of Carnegie Mellon University, first published in a working paper in 1974, and later elaborated in his 1979 Ph.D. thesis and a 1982 paper. Rete has become the basis for many popular expert system shells, including CLIPS, Jess, Drools, BizTalk Rules Engine and Soar. The word 'Rete' is taken from the Latin for 'net'.
- Der Rete-Algorithmus (rete, lat. für Netz oder Netzwerk) ist ein Algorithmus und Expertensystem zur Mustererkennung und zur Abbildung von Systemprozessen über Regeln. Es wurde vom US-amerikanischen Informatiker Charles Forgy im Rahmen seiner Doktorarbeit entwickelt bzw. die ihn 1979 zum Titel führen sollte. Der Algorithmus ist frei, da das amerikanische Verteidigungsministerium bei seiner Erstellung hinreichend mit beteiligt war.
- El algoritmo Rete es un algoritmo de reconocimiento de patrones eficiente para implementar sistema de producción de reglas. Fue creado por el Dr. Charles L. Forgy en la Carnegie Mellon University, su primera referencia escrita data de 1974, y apareció de forma más detallada en su tesis doctoral y en un artículo científico de 1982. Rete es hoy en día la base de muchos sistemas expertos muy famosos, incluyendo CLIPS, Jess, JBoss Rules, y Soar.
- L'algorithme de Rete est un algorithme performant de filtrage par motif (« pattern matching ») intervenant dans l'implémentation de systèmes de règles de production. L'algorithme a été conçu par le Dr Charles L. Forgy de l'Université Carnegie Mellon, tout d'abord publié comme une note de travail en 1974, puis plus tard élaboré dans sa thèse PhD de 1979 et dans une publication de 1982. Rete est devenu la base de nombreux systèmes experts tels que Clips, Jess, JBoss Rules, et Soar.
- L'Algoritmo rete è un efficiente algoritmo di pattern matching per l'implementazione di sistemi di produzione a regole. L'Algoritmo Rete è stato creato dal Dr. Charles Forgy della Carnegie Mellon University, la prima pubblicazione dell'algoritmo risale al 1974 e dopo rielaborato nel 1979 per la sua tesi di dottorato.
- Het rete-algoritme is een algoritme voor patroonmatching, gebruikt bij regelgebaseerde productiesystemen. Het werd in 1979 ontwikkeld door Dr. Charles L. Forgy van de Carnegie-Mellon Universiteit. Het rete-algoritme wordt toegepast in veelgebruikte expertsystemen zoals OPS5, CLIPS, JESS en LISA.
- Rete - эффективный алгоритм сопоставления с образцом для продукционных систем, экспертных систем и баз знаний, созданный Чарльзом Форги из Университета Карнеги Меллона. Впервые был описан в рабочем документе 1974 года, затем в докторской диссертации 1979 и в статье 1982 года.
|
![[RDF Data]](/statics/sw-cube.png)
