![]() |
|||
![]()
|
![]() |
![]() |
![]() |
4. CERTAINTY FACTORSThe certainty factor (CF) approach has appeal because it is computationally simple, and therefore understandable, to a non-mathematician. It also provides a means of estimating belief that is more appealing and more natural to an expert. Probability statements that have varying boundaries are particularly nonintuitive. The certainty approach allows the expert to ignore prior probabilities that are decidedly difficult to estimate. They are essentially assumed away by observing that in the absence of knowledge in a large hypothesis space, they can be considered uniformly small (Buchanan and Shortliffe, 1984,p. 211). The detailed motivation to consider uncertainty in expert- or knowledge-based systems is discussed in detail in Buchanan and Shortliffe (1984) and Shortliffe (1976). Buchanan and Shortliffe (1984) also discuss the uncertainty model in detail. This is an excellent starting place if you are interested in this approach. The most notable early use of certainty factors was in the MYCIN project. 5. THE MYCIN APPROACHA CF can vary in value from -1 to +1. A CF of 0 indicates no evidence for the hypothesis (H) in question. As the CF varies toward +1, evidence increasingly supports the hypothesis. As the CF moves toward -1, evidence increasingly disfavors the H. CFs are associated with rules -- rules in the usual expert system sense. The starting rules would be those whose left-hand side represent starting assumptions or premises. Associated with each rule is a CF indicating its contribution to the certainty of whatever hypothesis or subhypothesis is represented on the right-hand side of the rule. A simple abstract rule base modeled after Heckerman (1990, p. 171) illustrates the idea:
The first rule says that if evidence A is a fact, then assert C but only with a certainty of +0.6. Notice that C is also used as evidence in Rule 3 for the hypothesis D which, in turn, is confirming evidence for hypothesis F. The rule base can be thought of as representing an inference chain with CF propagating down the inference chain with the degree of belief either increasing, remaining the same, or decreasing as the inference process continues. This is shown in Figure 1. Combination rules are needed for propagating the CF values when there are multiple sources of support. For example, both rules 1 and 2 support hypothesis C. The rules for parallel combination are: The parallel combination rules are based on the sign of the arguments. In our example, both A and B are positive so we would use the rule x + y - xy The next question is: how do we propagate changes in belief? The rule for this is called the strength rule. It is as follows: A - (x) > B - (y) A > , CF(D) = y Max(0,CF(B)) Since C has CF 0.72 and by Rule 3 C implies D, C (x = 0.72) D (y = 0.7), means that: CF(D) = 0.7 Max(0, 0.72) = 0.504 Finally, we note that the left-hand sides of rules can be complex with a variety of boolean combinations. We restrict ourselves to combinations using simple and/or Boolean combinations. The rules for Boolean combination are: That is, if the LHS predicates are anded, propagate the lowest value. If the LHS predicates are ored, propagate the maximum value. The CF for each case would be:
Figure 2 shows the rule base with propagated CF values. As noted, CF has the advantage that estimating CFs is considerably less difficult than estimating prior and conditional probabilities. Further, CFs assume conditional independence and the combination methods insure locality, detachment, and modularity (Stefik, 1995, p. 474). What this means is that combinations can be computed whenever a rule's LHS is satisfied, and changed whenever a condition changes. The effects will propagate correctly. We can view the problem a rule at a time. This means that adding or deleting rules does not require rebuilding the entire certainty model. This is described in detail in Stefik (1995) and also in Heckerman (1990), and the reader is directed to these references for details. This approach has proved useful in medical diagnosis. With tuning of CFs, it has performed in the MYCIN studies as well as expert physicians. It can be considered a practical and useful approach for diagnostic problems. It has the advantage that CFs are much easier for an expert to understand than prior and conditional probabilities. It should be noted that this approach has limitations. First, there is a serious problem that is a function of the number of parallel rules supporting a hypothesis. It has been shown that as the number of parallel rules supporting a hypothesis increases, CF approaches 1 even for small values of CF. Also, there is no mechanism for adjusting CFs if evidence that has been used in a computation is later retracted. A conclusion once made, cannot be retracted. That is, the CF process is monotonic. Additional discussion of limitations and the relationship between certainty factors and probability models is discussed in Heckerman (1990). This is an excellent article that details the issues. If you are interested in how a MYCIN-like certainty factor approach is implemented, see Norvig (1992); Chapter 16 details the implementation of expert systems using certainty. The accompanying online code that implements a MYCIN-like system with CFs can be accessed from Norvig's Web page.
|
![]() |
|
Use of this site is subject certain Terms & Conditions. Copyright (c) 1996-1999 EarthWeb, Inc.. All rights reserved. Reproduction in whole or in part in any form or medium without express written permission of EarthWeb is prohibited. Please read our privacy policy for details. |