Chapter 6 Ripple Down Rules

Ripple Down Rules

Ripple Down Rules looks similar to some other methods. It is a rules based method, with a difference. In a traditional production rules system rules are a long list of individual chunks of knowledge. In a ripple down rule knowledge base the rules are stored in a tree. Section 6.1 will look at this tree structure. Section 6.2 will look at the process of adding rules to the knowledge base. Section 6.3 will discuss performance and efficiency issues.

6.1 Knowledge Base Structure

Each node of the tree is a rule. In the simplest version of ripple down rules, each node has only two child-branches. One branch is for the case that the conditions specified in the rule are satisfied, the other branch for when they are not. Each node also has a conclusion that should be adopted if the conditions are satisfied.

The case in question starts at the root node and traverses the tree until it runs out of branches. At the end of the trip the conclusion is taken from the last rule that was satisfied.

In Figure 6.1 we see a knowledge base in the process of refinement. The thick lines show the path of the case in question. The conditions at rule 1 were satisfied, so the next rule to be applied was rule 2. Rule 2 was not satisfied, so the case went on to rule 3 and so on. The last rule it satisfied was rule 9, so the conclusion of rule 9 was given. It turns out that this was not the desired conclusion, so an extra rule is to be added. This is the new rule 11. The case in question satisfies the conditions of rule 11 so it will take on the conclusion that we write in rule 11.

Figure 6.1: The structure of a ripple down rule knowledge base. [Compton, 2000]

6.2 Adding Rules

Ripple Down Rules!adding rules The beauty of this simple system is that you do not need to analyse the whole system before adding a new rule. Rules are only ever added to the ends of the tree, so they only affect the outcome of the rule above. In Figure 6.1 rule 11 affects the cases that are classified by rule 9 so we need to know the difference between the these two rules.

To know the difference between two rules it is easier to work from the cases they classify. Part of the ripple down rules system is a database of `cornerstone cases'. Each time a new refinement is made, the case in question is added to the cornerstone cases for later reference. In the case of Figure 6.1 the cornerstone case for rule 9 will be compared to the case in question. The differences will be presented and it is up to the operator to select which differences are to be used in the rule. This is called difference selection.

The operator does not even need to see the actual rules, just the cases.

The difference with other systems is that here there is only one cornerstone case relevant to the addition of a rule. In other systems all of the cornerstone cases must be run through to check for any unexpected effects.

6.2.1 Freedom of expression

It is up to the domain expert, the actual operator, to decide what is important in the system. It is best to have just one person assigned to updating the knowledge base since that way inconsistency should be minimised.

Over time there may be changes in the way the problems that arise are tackled. Some new technological or social change may affect the way the problem in question is seen. If this is the case, gradual changes in the rules base will bring the system up to date.

When a new person is assigned to taking care of the updates, it has been found that the knowledge base often undergoes subtle changes that reflect the thinking of the new domain expert. In this way the person in charge is kept happy with the system. This would be difficult to accommodate with conventional rules bases.

6.3 Tree Growth

It would appear that adding rules as needed could create the problem of a huge, disorganised tree. In the area of telecommunications this is important. A large tree to search through would use up valuable processing time. Real time performance would be unattainable and the system would not be practical.

The size would be more problematic if there was a lot of repetition in the database. The constraints placed on the addition of rules may make it necessary to add several rules to fix a problem, since the new rule may need to cover different areas.

For example, looking at Figure 6.2 there are basically three independent rules that should be fired regardless of the outcome of any of the others. The 6 conclusions are combinations of just 3, and to complete the picture there needs to be 1 more rule added. This is the main drawback in single classification ripple-down rules.

Figure 6.2: Repetition in a single conclusion ripple down rules tree

This particular problem is solved by using a multiple conclusion tree [Kang and Compton, 1992] as in Figure 6.3. Before any new rule is added, there is a search to look at the corner stone cases further up the tree to find the best place to add a new case. Once the node is selected, the case in question is added to this node as an additional cornerstone case.

As you can see with multiple paths, each path ends in a conclusion. It may be the case that too many conclusions may be drawn, if, for example, the same conclusion was reached on two different paths. It may also be the case that a path ends inconclusively. Where the appropriate conclusion is 'No Conclusion' then a stopping rule can be added.

Figure 6.3: Multiple conclusion ripple down rules eliminating repetition

6.3.1 Evaluating the knowledge base

One way to measure the efficiency of the tree is to compare it to trees constructed in different ways. Machine learning techniques can be used to make optimised trees from large sets of data. Induct [Gaines and Compton, 1992] and C4.5 [Quinlan, 1993] are two algorithms for making decision trees from sets of data. Induct has been used to make RDR trees too.

It was found that the incremental addition of knowledge is close to optimal efficiency anyway[Compton etal., 1994]. The test done involved simulating the expert's decision in choosing the relevant conditions to distinguish new cases. An optimised decision tree was induced from the training set to help the process then three levels of expertise were simulated.

Dumb expert: who chose all the conditions that were different as distinguishing features
Smart expert: who chose only one condition from the difference list, referring to the optimised decision tree
Smartest expert: who chose up to four conditions, referring to the optimised decision tree

The tests showed that the RDR system produces knowledge bases of comparable size to the induction algorithms. This challenges the assumption that more energy should be put into optimisation algorithms.

Garvan-ES1 An RDR tree is also useful for generating the data needed for rule induction. The Garvan-ES1 system based on RDR was started with 200 rules. After 11 weeks the base had grown to 600 rules[Compton etal., 1991]. After a year there were 1200 rules[Gaines and Compton, 1992]. Each of these rules had a corner stone case which forms a very useful database that should cover a large majority of the acquired knowledge. Induct managed to cover 9551 cases from the Garvan data set with only 174 rules, where the handmade RDR rules took 547 rules[Gaines and Compton, 1992].

6.4 Summary

Ripple-Down Rules seems to have all the answers. The structure of the rules frees the user from tedious programming-style debugging cycles to add rules with confidence. The updates can be done by a domain expert, rather than by a separate computer programmer.

The rules base can be kept working just as the domain expert likes, without having to wait for major changes to be necessary.

The rules base is quite efficient. Human operators tend to choose conditions for rules well. The number of rules made by incrementally adding rules is comparable to that achieved by optimisation algorithms.