Rete Algorithm
Charles L.Forge 가 1979년에 Carnegie-Mellon 대학에서 OPS(Official Production System) 에 관한 박사논문에서 Rete algorithm을 발표했다. 이것은 기존의 Markov algorithm을 발전시킨 것이다. 즉 Markov 에 의해서 rule 에 priority 를 부여하여 높은 우선순위의 rule 을 먼저 수행하는 control strategy 를 확립하여 expert system 의 기초가 되었다.
그러나 실 세계의 expert system을 위해서는 수백, 수천개의 rule을 사용하게 되므로 효율성의 문제가 대두되었다. 사용자가 response 를 얻는데 오랬동안 기다려야 한다면 시스템은 사용되지 않을 것이다. 따라서 모든 rule에 대해서 알고 있으며 각 rule을 순서적으로 적용해볼 필요없이도 어떤 rule을 수행시키는 algorithm을 필요로 하게 되었다
Rete algorithm 은 network 상에 rule 에 관한 정보를 저장함으로써 속도를 향상시키는 very fast pattern matcher 이다. 즉 모든 recognize-act cycle에서 모든 rule 에 대한 facts 를 match 시키는 것이 아니고, 변화된 facts 에 대해서만 match 시킨다. 각 cycle에서 변화가 없었던 static data 는 무시되기 때문에 antecedent 에 대한 facts 들의 matching 속도를 크게 향상시킨다. Rete 와 같은 fast pattern matching algorithm 들은 expert system 의 실제 응용을 위한 기초가 되었다. Forge 는 계속해서 OPS 를 발전시키었다
THE RETE MATCHING ALGORITHM : Dan W. Patterson : ..... 전형적인 지식 베이스는 수백 또는 수천가지 이상의 규칙을 포함하는데 각 규칙은 몇가지 (아마도 10여가지 이상의) 규칙들을 포함한다. 작업 메모리 역시 전형적으로 수백 가지 이상의 조항들을 포함한다. 결과적으로 작업메모리 (working memory) 에 대한 모든 규칙과 LHS (left hand side) 조건들을 소모적으로 매칭하는 데 수만번의 비교가 필요하다 ...... 이러한 시스템은 계산 시간의 90% 정도가 매칭연산과 관련되어질 수 있다 ........각 사이클마다 매칭연산이 수 천번 수행되어지는 것을 제거할 수 있다. 이에 효과적인 매치 알고리즘을 개발하게 되었는데 이를 RETE라고 부른다 (Forgy, 1982) .......
Rete Algorithm
The Rete algorithm is an efficient pattern matching algorithm for implementing rule-based ("expert") systems. The Rete algorithm was designed by Dr. Charles L. Forgy of Carnegie Mellon University in 1979. Rete has become the basis for many popular expert systems, including OPS5, CLIPS, JESS, and LISA.
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 (from the Latin 'rete' for net, or network) provides the basis for a more efficient implementation of an expert system. 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 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.
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.
[edit]
In the 1980s Charles L. Forgy developed successor of Rete algorithm named Rete II [1] (http://www.pst.com/rete2.htm). Unlike original Rete (which is public domain) this algorithm was not disclosed. Rete II claims better performance for more complex problems (even orders of magnitude (http://www.pst.com/benchcr2.htm)).
[edit]
[edit]
term :
지식 (Knowledge) 지식베이스 (Knowledge Base) 지식공학 (Knowledge Engineering) 지식공학자 (Knowledge Engineer) 지식획득 (Knowledge Acquisition) 지식 표현 (Knowledge Representation) 지식표현 (Knowledge Representation) 전문가시스템 (Expert System) 휴리스틱 (Heuristic) 컴퓨터 (Computer) 인공지능 (Artificial Intelligence)
paper :
THE RETE MATCHING ALGORITHM : Dan W. Patterson