| Automating rule strengths in expert systems is a way to alleviate the knowledge acquisition bottleneck. It is assumed that rules are fixed, except for the values of their strengths, which are computed or adjusted from initial values given by experts.;A model of expert systems is proposed, in which rules have the form IF (P$sb1$ & P$sb2$ & dots & P) THEN C WITH ATTENUATION a, where P$sb1$, P$sb2$, dots, P$sb{rm n}$, and C are weighted propositions, i.e., statements with a certainty factor (CF), and a, the strength of the rule, is a number between 0 and 1. Certainty factors are numbers between 0 and 1. The premise of the rule has a CF that is computed by taking the MIN of the CFs of its component conjuncts. The CF of the premise is multiplied by the strength of the rule to obtain the CF of the conclusion, C. Many rules may conclude the same proposition; their CFs are merged by using the MAX or the probabilistic addition functions.;To compute rule attenuations, two problem settings are considered. In the first, an oracle is given, that can provide the CFs of the conclusions of the entire rule-based system, given any assignment of certainty factors to the premises of the entire system (complete case). In the second, a fixed set of cases is available (incomplete case).;A fast algorithm for synthesis in the complete case for simple rule bases is given both for MAX and probabilistic sum. It is shown that, when premises are shared among rules, a well-known result in the testing of Boolean circuits implies that determination of a rule strength is NP-Complete. However, a fast algorithm is given for the determination of input attenuations.;In the incomplete case, the synthesis of attenuations is shown to be NP-Complete, even for very shallow rule bases with only two propositions in the premise of each rule, both for MAX and probabilistic sum. The refinement of attenuations from expert-given estimates is shown to be NP-Hard, no matter how close to the correct value the estimates are and how small an improvement towards the correct value is desired.;The NP-Hardness proofs are exploited to define a strict condition under which a fast algorithm for the MAX case exists and to interpret several simple iterative algorithms. |
