Ripple down rules
Encyclopedia
Ripple Down Rules is a way of approaching knowledge acquisition
. Knowledge acquisition refers to the transfer knowledge from human experts to knowledge based systems.
and covers a family of techniques. RDR were proposed by Compton and Jansen based on experience maintaining the expert system GARVAN-ES1 (Compton and Jansen 1988). The original GARVAN-ES1 (Horn et al. 1985) employed a knowledge acquisition process where new cases, that were poorly classified by the system, were added to a data base and then used to incrementally refine the knowledge base. The added cases, whose conclusions conflicted with the advice of the system were termed "cornerstone cases". Consequently the data base grew iteratively with each refinement to the knowledge. The data base could then be used to test changes to the knowledge. Knowledge acquisition tools, similar to those provided by Teiresias were developed to find and help modify the conflicting rules. The tools would display the rules fired by each case and suggestions to "edit" the knowledge to remove the conflicts.
In the RDR framework, the human expert’s knowledge is acquired based on the current context and is added incrementally. Compton and Jansen argued that the expert's knowledge is to some extent 'made up' to justify why she was right, not to explain how she reached this right interpretation (or conclusion). The justification is based on features that are identified from the current case. The expert creates a rule for classifying cases corresponding to a particular context. This rule is unlikely to classify all cases belonging to the class. Compton and Jansen asserted that it is not possible to create a single elegant context free rule as the knowledge we communicate is a justification in a context. This implies that there is no absolute knowledge that acts as foundation of other knowledge, since knowledge is only true in a context (Compton and Jansen 1990).
The process of transferring human experts's knowledge to Knowledge Based Systems in RDR is explained in Knowledge Acquisition Scenario.
The data structure is similar to a decision tree
. Each node has a rule, the format of this rule is IF cond1 AND cond2 AND ... AND condN THEN conclusion. Cond1 is a condition (boolean evaluation), for example A=1, isGreater(A,5) and average(A,">",average(B)). Each node has exactly two successor nodes, these successor nodes are connected to predecessor node by "ELSE" or "EXCEPT".
An example of SCRDR tree (defined recursively) is shown below:
IF (OutLook = "SUNNY" AND Temperature = "COOL") THEN PLAY="TENNIS"
EXCEPT Child-1
ELSE Child-2
where Child-1 and Child-2 are also SCRDR trees. For example Child-1 is:
IF (Wind = "WINDY" AND Humidity = "HIGH") THEN Play="SQUASH"
EXCEPT NoChild
ELSE NoChild
[OutLook="SUNNY", Temperature="COOL", Wind="WINDY", Humidity="HIGH", ForeCast="STORM", Play="SQUASH"]. This case is misclassified as Play="TENNIS".
When a rule is constructed by the human experts, the conditions of this rule should be satisfied by the misclassified case and also they should NOT be satisfied by any previous cases classified correctly by the parent rule (in this context is the first rule).
Knowledge acquisition
Knowledge acquisition is a method of learning, first proposed by Aristotle in his seminal work "Organon". Aristotle proposed that the mind at birth is a blank slate, or tabula rasa...
. Knowledge acquisition refers to the transfer knowledge from human experts to knowledge based systems.
Introductory material
Ripple Down Rules (RDR) is an incremental approach to knowledge acquisitionKnowledge acquisition
Knowledge acquisition is a method of learning, first proposed by Aristotle in his seminal work "Organon". Aristotle proposed that the mind at birth is a blank slate, or tabula rasa...
and covers a family of techniques. RDR were proposed by Compton and Jansen based on experience maintaining the expert system GARVAN-ES1 (Compton and Jansen 1988). The original GARVAN-ES1 (Horn et al. 1985) employed a knowledge acquisition process where new cases, that were poorly classified by the system, were added to a data base and then used to incrementally refine the knowledge base. The added cases, whose conclusions conflicted with the advice of the system were termed "cornerstone cases". Consequently the data base grew iteratively with each refinement to the knowledge. The data base could then be used to test changes to the knowledge. Knowledge acquisition tools, similar to those provided by Teiresias were developed to find and help modify the conflicting rules. The tools would display the rules fired by each case and suggestions to "edit" the knowledge to remove the conflicts.
In the RDR framework, the human expert’s knowledge is acquired based on the current context and is added incrementally. Compton and Jansen argued that the expert's knowledge is to some extent 'made up' to justify why she was right, not to explain how she reached this right interpretation (or conclusion). The justification is based on features that are identified from the current case. The expert creates a rule for classifying cases corresponding to a particular context. This rule is unlikely to classify all cases belonging to the class. Compton and Jansen asserted that it is not possible to create a single elegant context free rule as the knowledge we communicate is a justification in a context. This implies that there is no absolute knowledge that acts as foundation of other knowledge, since knowledge is only true in a context (Compton and Jansen 1990).
Methodology
Ripple Down Rules (RDR) consist of a data structure and knowledge acquisition scenarios. Human experts' knowledge is stored in the data structure. The knowledge is coded as a set of rules.The process of transferring human experts's knowledge to Knowledge Based Systems in RDR is explained in Knowledge Acquisition Scenario.
Data Structure
There are various structures of Ripple Down Rules, for example Single Classification Ripple Down Rules (SCRDR), Multiple Classification Ripple Down Rules (MCRDR), Nested Ripple Down Rules (NRDR) and Repeat Inference Multiple Classification Ripple Down Rules (RIMCRDR). The data structure of RDR described here is SCRDR, which is the simplest structure.The data structure is similar to a decision tree
Decision tree
A decision tree is a decision support tool that uses a tree-like graph or model of decisions and their possible consequences, including chance event outcomes, resource costs, and utility. It is one way to display an algorithm. Decision trees are commonly used in operations research, specifically...
. Each node has a rule, the format of this rule is IF cond1 AND cond2 AND ... AND condN THEN conclusion. Cond1 is a condition (boolean evaluation), for example A=1, isGreater(A,5) and average(A,">",average(B)). Each node has exactly two successor nodes, these successor nodes are connected to predecessor node by "ELSE" or "EXCEPT".
An example of SCRDR tree (defined recursively) is shown below:
IF (OutLook = "SUNNY" AND Temperature = "COOL") THEN PLAY="TENNIS"
EXCEPT Child-1
ELSE Child-2
where Child-1 and Child-2 are also SCRDR trees. For example Child-1 is:
IF (Wind = "WINDY" AND Humidity = "HIGH") THEN Play="SQUASH"
EXCEPT NoChild
ELSE NoChild
Knowledge Acquisition Scenario
Human experts provide a case to the systems and they add a new rule to correct the classification of a misclassified case. For example rule Child-1 is added to correct classification of case[OutLook="SUNNY", Temperature="COOL", Wind="WINDY", Humidity="HIGH", ForeCast="STORM", Play="SQUASH"]. This case is misclassified as Play="TENNIS".
When a rule is constructed by the human experts, the conditions of this rule should be satisfied by the misclassified case and also they should NOT be satisfied by any previous cases classified correctly by the parent rule (in this context is the first rule).
Implementations
Below is a list of known implementations of RDR- The Ballarat Incremental Knowledge Engine (BIKE) is a comprehensive open source implementation in C++. Includes plugins for Single Classification and Multiple Classification RDRs.
- Pacific Knowledge Systems (PKS) uses a commercial product called LabWizard that is based on Multiple Classification Ripple Down Rules
- WEKA has a version of Induct RDR called Ridor.