| What is Multiple Classification Ripple Down Rule (MCRDR)? |
|
| 2. Knowledge Acquisition |
|
 |
|
Figure 2. Knowledge Structure and Inference |
|
| When a case has been classified incorrectly or missing classification, knowledge acquisition is required and can be divided into three parts. Firstly, the system acquires the correct classification from the expert. Secondly, the system decides on the new rules¡¯ location. Thirdly, the system acquires new rules from the expert and adds them to correct the knowledge base. It is likely that experts may found the system more natural if the order of steps two and three are reversed, thereby better hiding the implicit knowledge engineering that is going on. However, the order is not crucial in terms of the algorithm.
|
| Acquiring New Classifications
|
| Acquiring new classifications is trivial, the expert simply needs to state them. For example, if the system produces classification class2, class5, class for a given problem, the expert may decide that class 6 does not need to be changed but class 2 and class 5 should be deleted and class 7 and class 9 added.
|
| Locating Rules
|
| The system should find the locations for the new rules that will provide these classifications. It cannot be assumed that the correct location for a new rule is as a refinement for one of the rules giving one of the wrong classifications. It may be a quite independent classification and the wrong classification is simply wrong. The possibilities are shown in Table 1. Note the idea of stopping rules, rules that make no conclusion, or rather give a null classification. Stopping rules play a major role in MCRDR in preventing wrong classifications being given for a case.
|
| As well as attempting to decide whether a classification is best seen as a refinement or an independent classification, we note that in some ways it does not matter - both are workable solutions for any classification. The key effect of the rule location is to affect the evolution and maintenance of the knowledge base. If there is a strategy that tends to add rules at the top level, the knowledge base will cover the domain more rapidly but with a greater likelihood of error. If the strategy tends to add new rules at the end of paths, domain coverage will be slower but with lesser errors from the new rules, simply because they see lesser cases. This is shown in Fig 3. A rule can also be placed at appropriate intermediate levels. One can also change these strategies as the system develops. These decisions are a new type of knowledge engineering consideration - the issue is what type of development is appropriate for a particular domain, rather than the structure of the knowledge.
|
| Wrong classifications |
To correct the KB |
| Wrong classification to be stopped |
Add a rule (stopping rule) at the end of path to prevent the classification |
| Wrong classification replaced by new classification |
Add a rule at a higher level to give the new classification |
| A new independent classification |
Add a rule at a higher level to give the new classification |
|
| Table 1. The three ways in which new rules correct a knowledge base. |
|
| Decisions about the evolution of the knowledge base do not have to be knowledge engineering decisions that override any preferences of the expert. Rather, the expert can be free to make any type of decision, but the interface can be designed so that the expert is more likely to add rules towards the top or the bottom. For example, two alternative strategies might be to ask the expert to select the important data used in reaching the conclusion or to delete the irrelevant data. If selected data satisfies a pathway the rule is placed at the bottom of the pathway or at whatever level the conditions selected reach down to. One may expect that the expert's behaviour will be conservative, he or she will either select few conditions or remove few conditions. The method used here is for the (simulated) expert to select important data in the case. We call the selected conditions a "mini-case". Other strategies may include asking the expert to make the normal difference list selection (see below) and then asking the expert to select from a list which includes all the conditions for all the possible pathways where the rule may go. Again the expert's behaviour can probably be biased by asking for conditions to be removed or alternatively selected. |
| Acquiring Rule Conditions : Rule Validation
|
| Verification and validation are concerned with ensuring that a KBS system performs as it is meant to. Verification research is normally concerned with ensuring the internal consistency of a knowledge base. The normal approach in verification is to attempt to reduce the KB to pathways from data to conclusions and then look at the relationships between these pathways, the data they use, the intermediate conclusion they establish etc. (Preece, Shinghal et al. 1992). Validation, in terms of maintenance or incremental acquisition, is concerned with testing whether other cases previously correctly classified will be misclassified by a new rule, as well as ensuring the new rule covers the new case. We are mainly interested in validation, in particular in validating a KBS by testing it on cases. |
| A standard technique is to use a database (Buchanan, Barstow et al. 1983) of standard cases. In this situation one depends on the cases being representative of the cases the system is meant to cover. With RDR, a case is associated with a rule because the rule is added to deal with that particular case. A new rule must distinguish between the case that caused its creation and the case associated with the rule that gave the previous incorrect classification. With MCRDR, a number of cases (cornerstone cases) can reach a new rule and the higher in the tree the more cases can reach the rule. The new rule should distinguish between the new case and all of these cornerstone cases. That is, MCRDR has multiple cornerstone cases for a rule, compared to RDR where there is a one per rule. |
| A rule at some level can be hit by all the cases associated with its siblings at the same level and their children lower in the system. So, the rule has to be made sufficiently specific so that none of these other cases satisfy the rule. However, it does not matter if other cases which include the same classification reach this particular rule. If a rule is added at a level below the top level, only cases which satisfy the parent rule above need to be considered as cornerstone cases. Note that as the system develops, cases may arise which correctly satisfy a rule, but may be added to the system because a rule is needed elsewhere to add a further classification. Such a case will become a cornerstone case for new rules below the rule it satisfies and for which the classification is correct. As the tree develops, the rules lower down will naturally have less cornerstone cases associated with them. |
| The aim then is make a new rule sufficiently precise so that it satisfies only the case it is being added for and no other stored cases, except that it does not matter if it happens to satisfy cases which include the same classification. The algorithm for selecting conditions to make the rule sufficiently precise is very simple and some discussion is needed why a more sophisticated approach was not chosen. Consider a new case A and two cornerstone cases B and C. In creating a new rule, one may imagine that expert should choose at least one of conditions from (Case A - (Case B ? Case C)) or negated conditions from the ((Case B?Case C) - Case A) |
 |
|
Figure 3. Difference Lists |
|
| However, as seen in Fig 3, these may be empty - leading to the situation where no rule conditions can be found. Alternatively the difference list may contain only trivial conditions that are irrelevant. In other words there are no common conditions that distinguish the presented case from all the cornerstone cases, but a number of different conditions distinguish different cases and these conditions must all be included in the new rules. |
| The algorithm we use is as follows. First, the system can form a cornerstone case list which can reach the new rule and should be distinguished from the presented case. The expert is asked to select from a difference list between the presented case and one of the cornerstone cases in the list of cornerstone cases to be considered. The system then tests all cornerstone cases in the list against the conditions selected and deletes cornerstone cases from the list that do not satisfy the condition selected. The expert is then asked to choose conditions from a difference list between the current case and one of remaining cornerstone cases in the list. The conditions selected are added as a conjunction to the rule. The system repeats this process until there is no cornerstone case in the list which satisfies the rule. |
|
|
