Rule-Based Systems and Identification Trees
By ai-depot | November 23, 2002
Methods of Rule-Based Systems
Methods of Rule-Based Systems
Forward-Chaining
Rule-based systems, as defined above, are adaptable to a variety of problems. In some problems, information is provided with the rules and the AI follows them to see where they lead. An example of this is a medical diagnosis in which the problem is to diagnose the underlying disease based on a set of symptoms (the working memory). A problem of this nature is solved using a forward-chaining, data-driven, system that compares data in the working memory against the conditions (IF parts) of the rules and determines which rules to fire.
For an example of forward-chaining, see Appendix A.
Backward-Chaining
In other problems, a goal is specified and the AI must find a way to achieve that specified goal. For example, if there is an epidemic of a certain disease, this AI could presume a given individual had the disease and attempt to determine if its diagnosis is correct based on available information. A backward-chaining, goal-driven, system accomplishes this. To do this, the system looks for the action in the THEN clause of the rules that matches the specified goal. In other words, it looks for the rules that can produce this goal. If a rule is found and fired, it takes each of that rule�s conditions as goals and continues until either the available data satisfies all of the goals or there are no more rules that match.
For an example of backward-chaining, see Appendix B.
Which method to use?
Of the two methods available, forward- or backward-chaining, the one to use is determined by the problem itself. A comparison of conditions to actions in the rule base can help determine which chaining method is preferred. If the �average� rule has more conditions than conclusions, that is the typical hypothesis or goal (the conclusions) can lead to many more questions (the conditions), forward-chaining is favored. If the opposite holds true and the average rule has more conclusions than conditions such that each fact may fan out into a large number of new facts or actions, backward-chaining is ideal.
If neither is dominant, the number of facts in the working memory may help the decision. If all (relevant) facts are already known, and the purpose of the system is to find where that information leads, forward-chaining should be selected. If, on the other hand, few or no facts are known and the goal is to find if one of many possible conclusions is true, use backward-chaining.
Improving Efficiency of Forward Chaining
Forward-chaining systems, as powerful as they can be if well designed, can become cumbersome if the problem is too large. As the rule-base and working memory grow, the brute-force method of checking every rule condition against every assertion in the working memory can become quite computationally expensive. Specifically, the computational complexity if the order of RA^C, where R is the number of rules, C is the approximate number of conditions per rule, and A is the number of assertions in working memory. With this exponential complexity, for a rule-base with any real rules, the system will perform quite slowly.
There are ways to reduce this complexity, thus making a system of this nature far more feasible for use with real problems. The most effective such solution to this is the Rete algorithm. The Rete algorithm reduces the complexity by reducing the number of comparisons between rule conditions and assertions in the working memory. To accomplish this, the algorithm stores a list of rules matched or partially matched by the current working memory. Thus, it avoids unnecessary computations in re-checking the already matched rules (they are already activated) or un-matched rules (their conditions cannot be satisfied under the existing assertions in the working memory). Only when the working memory changes does it re-check the rules, and then only against the assertions added or removed from working memory. All told, this method drops the complexity to O(RAC), linear rather than exponential.
The Rete algorithm, however, requires additional memory to store the state of the system from cycle to cycle. The additional memory can be considerable, but may be justified for the increased speed efficiency. For large problems in which speed is a factor, the Rete method is justified. For small problems, or those in which speed is not an issue but memory is, the Rete method may not be the best option. Another unfortunate shortcoming of the Rete method is that it only works with forward-chaining.
Tags: none
Category: tutorial |
April 11th, 2008 at 7:12 am
I see it has been a while since this one has been post, but i wonder if the images are still somewhere on the net?
April 11th, 2008 at 8:52 am
Got in another article here at the AI-depot..
http://ai-depot.com/Tutorial/RuleBased-Methods.html