Rete algorithm

The Rete algorithm ( , , rarely , ) is a pattern matching algorithm for implementing rule-based systems. The algorithm was developed to efficiently apply many rules or patterns to many objects, or facts, in a knowledge base. It is used to determine which of the system's rules should fire based on its data store, its facts. The Rete algorithm was designed by 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.

The Rete algorithm ( , , rarely , ) is a pattern matching algorithm for implementing rule-based systems. The algorithm was developed to efficiently apply many rules or patterns to many objects, or facts, in a knowledge base. It is used to determine which of the system's rules should fire based on its data store, its facts. The Rete algorithm was designed by 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. ==Overview== 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, Soar, and Evrete. 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 ). === Production execution=== 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. ==Variants== ===Rete II=== In the 1980s, Charles Forgy developed a successor to the Rete algorithm named Rete II. Unlike the original Rete (which is public domain) this algorithm was not disclosed. Rete II claims better performance for more complex problems (even orders of magnitude ), and is officially implemented in CLIPS/R2, a C/++ implementation and in OPSJ, a Java implementation in 1998. Rete II gives about a 100 to 1 order of magnitude performance improvement in more complex problems as shown by KnowledgeBased Systems Corporation benchmarks. Rete II can be characterized by two areas of improvement; specific optimizations relating to the general performance of the Rete network (including the use of hashed memories in order to increase performance with larger sets of data), and the inclusion of a backward chaining algorithm tailored to run on top of the Rete network. Backward chaining alone can account for the most extreme changes in benchmarks relating to Rete vs. Rete II. Rete II is implemented in the commercial product Advisor from FICO, formerly called Fair Isaac Jess (at least versions 5.0 and later) also adds a commercial backward chaining algorithm on top of the Rete network, but it cannot be said to fully implement Rete II, in part due to the fact that no full specification is publicly available. ===Rete-III=== In the early 2000s, the Rete III engine was developed by Charles Forgy in cooperation with FICO engineers. The Rete III algorithm, which is not Rete-NT, is the FICO trademark for Rete II and is implemented as part of the FICO Advisor engine. It is basically the Rete II engine with an API that allows access to the Advisor engine because the Advisor engine can access other FICO products. ===Rete-NT=== In 2010, Forgy developed a new generation of the Rete algorithm. In an InfoWorld benchmark, the algorithm was deemed 500 times faster than the original Rete algorithm and 10 times faster than its predecessor, Rete II. This algorithm is now licensed to Sparkling Logic, the company that Forgy joined as investor and strategic advisor, as the inference engine of the SMARTS product. ===Rete-OO=== Considering that Rete aims to support first-order logic (basically if-then-else statements), Rete-OO aims to provide a rule-based system that supports uncertainty (where the information to make a decision is missing or is inaccurate). According to the author's proposal, the rule "if Danger then Alarm" would be improved to something such as "given the probability of Danger, there will be a certain probability of hearing an Alarm" or even "the greater the Danger, the louder should be Alarm". For this it extends the Drools language (which already implements the Rete algorithm) to make it support probabilistic logic, like fuzzy logic and Bayesian networks.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1374898096 under CC BY-SA 4.0; modifications have been made.