Ripple-down rules

Ripple-down rules (RDR) are a way of approaching knowledge acquisition. Knowledge acquisition refers to the transfer of knowledge from human experts to knowledge-based systems.

Introductory material

Ripple-down rules are an incremental approach to knowledge acquisition 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, based on Test Driven Development, 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 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' 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. 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 system 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 (which in this context is the first rule).

Implementations

Below is a list of known implementations of RDR:

The alpha version of RDR (MCRDR) Framework was developed by the University of New South Wales (UNSW) and University of Tasmania (UTAS) Research Team and funded by ARC.^{[definition needed]}
RDR (MCRDR) document classifier was developed by Dr. Yang Sok Kim, UNSW and AProf. Byeong Ho Kang, UTAS.
The Erudine Behaviour Engine is a commercial software product that employs RDRs as part of its methodology for knowledge capture and business process modelling. It is implemented in Java.
The Ballarat Incremental Knowledge Engine (BIKE) is a comprehensive open source implementation in C++. It includes plugins for single-classification and multiple-classification RDRs.
Pacific Knowledge Systems (PKS) uses a commercial product called RippleDown Expert that is based on multiple-classification ripple-down rules.
The Java data-mining software Weka has a version of Induct RDR called Ridor. It learns rules from a data set with the principal aim to predict a class within a test set.
RDRPOSTagger toolkit: Single-classification ripple-down rules for part-of-speech tagging
RDRsegmenter toolkit: Single-classification ripple-down rules for word segmentation

References

D.Q. Nguyen, D.Q. Nguyen and S.B. Pham (2017). "Ripple Down Rules for Question Answering." Semantic Web, vol. 8, no. 4, pages 511–532. [.pdf]
D.Q. Nguyen, D.Q. Nguyen, D.D. Pham and S.B. Pham (2016). "A Robust Transformation-Based Learning Approach Using Ripple Down Rules for Part-Of-Speech Tagging." AI Communications, vol. 29, no. 3, pages 409–422. [.pdf]
"BEST RDR (Best Expert System Technique Ripple Down Rules)". RDR systems and publications available. Retrieved February 15, 2013.
"The Ballarat Incremental Knowledge Engine". Introduction. Retrieved September 27, 2010.
R. Dazeley, P.Warner, S. Johnson and P. Vamplew (2010). "The Ballarat Incremental Knowledge Engine". 11th International Workshop on Knowledge Management and Acquisition for Smart Systems and Services (PKAW 2010). pp. 195–207. doi:10.1007/978-3-642-15037-1_17.{{cite conference}}: CS1 maint: multiple names: authors list (link)
D. Richards (2009). "Two Decades of RDR Research". Knowledge Engineering Review. 24 (2): 159–184. doi:10.1017/S0269888909000241. S2CID 6183087.
P. Compton & R. Jansen (1988). "Knowledge in Context: a strategy for expert system maintenance". Proc. Second Australian Joint Artificial Intelligence Conference. pp. 292–306.
P. Compton & R. Jansen (1990). "A philosophical basis for knowledge acquisition". Knowledge Acquisition. 2 (3): 241–257. CiteSeerX 10.1.1.31.7340. doi:10.1016/S1042-8143(05)80017-2.
K. Horn, L. Lazarus, P. Compton and J.R. Quinlan (1985). "An expert system for the interpretation of thyroid assays in a clinical laboratory". Aust Comp J. 17: 7–11.{{cite journal}}: CS1 maint: multiple names: authors list (link)

External links