Interval-Type and Affine Arithmetic-Type Techniques for Handling Uncertainty in Expert Systems, with Applications to Geoinformatics and Computer Security

摘要

Expert knowledge consists of statements Sj (facts and rules). The expertu27s degree of confidence in each statement Sj can be described as a (subjective) probability (some probabilities are known to be independent). Examples: if we are interested in oil, we should look at seismic data (confidence 90%); a bank A trusts a client B, so if we trust A, we should trust B too (confidence 99%). If a query Q is deducible from facts and rules, what is our confidence p(Q) in Q? We can describe Q as a propositional formula F in terms of Sj; computing p(Q) exactly is NP-hard, so heuristics are needed.Traditionally, expert systems use technique similar to straightforward interval computations: we parse F and replace each computation step with corresponding probability operation. Problem: at each step, we ignore the dependence between the intermediate results Fj; hence intervals are too wide. Example: the estimate for P(A/~A) is not 1. Solution: similarly to affine arithmetic, besides P(Fj), we also compute P(Fj u26 Fi) (or P(Fj u26 ... u26 Fk)), and on each step, use all combinations of l such probabilities to get new estimates. Results: e.g., P(A/~A) is estimated as 1.