TY - JOUR
T1 - Interval-type and affine arithmetic-type techniques for handling uncertainty in expert systems
AU - Ceberio, Martine
AU - Kreinovich, Vladik
AU - Chopra, Sanjeev
AU - Longpré, Luc
AU - Nguyen, Hung T.
AU - Ludäscher, Bertram
AU - Baral, Chitta
N1 - Funding Information:
This work was supported in part by NASA under cooperative agreement NCC5-209, by NSF Grants EAR-0112968, EAR-0225670, and EIA-0321328, by Army Research Laboratories Grant DATM-05-02-C-0046, by NIH Grant 3T34GM008048-20S1, and by Applied Biomathematics.
PY - 2007/2/15
Y1 - 2007/2/15
N2 - Expert knowledge consists of statements Sj (facts and rules). The facts and rules are often only true with some probability. For example, if we are interested in oil, we should look at seismic data. If in 90% of the cases, the seismic data were indeed helpful in locating oil, then we can say that if we are interested in oil, then with probability 90% it is helpful to look at the seismic data. In more formal terms, we can say that the implication "if oil then seismic" holds with probability 90%. Another example: a bank A trusts a client B, so if we trust the bank A, we should trust B too; if statistically this trust was justified in 99% of the cases, we can conclude that the corresponding implication holds with probability 99%. If a query Q is deducible from facts and rules, what is the resulting probability p (Q) in Q? We can describe the truth of Q as a propositional formula F in terms of Sj, i.e., as a combination of statements Sj linked by operators like &, ∨, and ¬; 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: similar to affine arithmetic, besides P (Fj), we also compute P (Fj & Fi) (or P (Fj1 & & Fjd)), 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.
AB - Expert knowledge consists of statements Sj (facts and rules). The facts and rules are often only true with some probability. For example, if we are interested in oil, we should look at seismic data. If in 90% of the cases, the seismic data were indeed helpful in locating oil, then we can say that if we are interested in oil, then with probability 90% it is helpful to look at the seismic data. In more formal terms, we can say that the implication "if oil then seismic" holds with probability 90%. Another example: a bank A trusts a client B, so if we trust the bank A, we should trust B too; if statistically this trust was justified in 99% of the cases, we can conclude that the corresponding implication holds with probability 99%. If a query Q is deducible from facts and rules, what is the resulting probability p (Q) in Q? We can describe the truth of Q as a propositional formula F in terms of Sj, i.e., as a combination of statements Sj linked by operators like &, ∨, and ¬; 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: similar to affine arithmetic, besides P (Fj), we also compute P (Fj & Fi) (or P (Fj1 & & Fjd)), 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.
KW - Affine arithmetic
KW - Computer security
KW - Expert systems
KW - Fuzzy logic
KW - Geoinformatics
KW - Interval computations
UR - http://www.scopus.com/inward/record.url?scp=33750198108&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33750198108&partnerID=8YFLogxK
U2 - 10.1016/j.cam.2005.08.030
DO - 10.1016/j.cam.2005.08.030
M3 - Article
AN - SCOPUS:33750198108
SN - 0377-0427
VL - 199
SP - 403
EP - 410
JO - Journal of Computational and Applied Mathematics
JF - Journal of Computational and Applied Mathematics
IS - 2
ER -