Article
Full Access
On proof- and model-based techniques for reasoning with uncertainty
Flávio S. Corrěa da Silva,
Flávio S. Corrěa da Silva
Instituto de Matemática e Estatistica da Universidade de São Paulo—Cid. Universitária “ASO”—PO Box 20570—01498-070 São Paulo SP, Brazil
Search for more papers by this authorFlávio S. Corrěa da Silva,
Flávio S. Corrěa da Silva
Instituto de Matemática e Estatistica da Universidade de São Paulo—Cid. Universitária “ASO”—PO Box 20570—01498-070 São Paulo SP, Brazil
Search for more papers by this authorAbstract
In this article we compare two well-known techniques for reasoning with uncertainty—namely, Incidence Calculus and Fagin-Halpern's version of the Theory of Evidence—from a viewpoint not so frequently explored for such techniques. We argue that, despite the equivalence relations that these techniques have been proved to hold, they have intrinsically different rǒles as representations of uncertainty for automated reasoning, in the sense that the former represents approximations to uncertainty values due to impossibility to achieve exact results by proof-theoretic means, and the latter represents model-theoretic limits of definability of uncertainty values. © 1995 John Wiley & Sons, Inc.
Reference
- 1 D. A. Clark, Numerical and symbolic approaches to uncertainty management in AI, Artificial Intelligence Review, 4, 109–146 (1990).
- 2 P. R. Cohen, Numeric and symbolic reasoning in expert systems, in ECAI '86—Proceedings of the 7th European Conference on Artificial Intelligence, 1986.
- 3 F. S. Correa da Silva, D. S. Robertson, and J. Hesketh, “ Automated Reasoning with Uncertainties,” In Knowledge Representation and Uncertainty M. Masuch and L. Pawlos, Ed., Ch. 5 (LNAI 808). A preliminary version was presented at the APLOC—Applied Logic Conference (Logic at Work), 1992. Springer-Verlag, Berlin, 1993.
- 4
A. Saffiotti,
“An AI view of the treatment of uncertainty,”
Knowl. Eng. Rev.
2
(2),
75–97
(1987).
10.1017/S0269888900000795 Google Scholar
- 5 D. Dubois and H. Prade, An introduction to possibilistic and fuzzy logics, in Non-standard Logics for Automated Reasoning, P. Smets, A. Mamdani, D. Dubois, and H. Prade, Academic Press, London, 1988.
- 6 Léa Sombé, “Reasoning under incomplete information in artificial intelligence: a comparison of formalisms using a single example,” Int. J. Intel. Sys. 5 (1990).
- 7 M. Abadi and J. Y. Halpern, “Decidability and expressiveness for first-order logics of probability,” Technical Report RJ-7220, IBM Research Report, 1989.
- 8 F. Bacchus, Representing and Reasoning with Probabilistic Knowledge, MIT Press, Cambridge MA, 1990.
- 9 P. Cheeseman, “ In defense of probability,” In IJCAI '85—Proceedings of the 9th International Joint Conference on Artificial Intelligence, 1985.
- 10 F. S. Correa da Silva and A. Bundy, “ On some equivalence relations between Incidence Calculus and Dempster-Shafer theory of evidence,” In 6th Conference on Uncertainty in Artificial Intelligence, 1990.
- 11 H. E. Kyburg, Jr., “Bayesian and non-Bayesian Evidential Updating,” Artificial Intelligence, 31, 271–293 (1987).
- 12 J. Pearl, Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference, Morgan Kaufmann, San Mateo, 1988.
- 13 G. Shafer, Belief functions and possibility measures, in Analysis of Fuzzy Information, J. C. Bezdek, Ed., CRC Press, 1987.
- 14
A. Bundy.
“Incidence calculus: a mechanism for probabilistic reasoning,”
J. Auto. Reas.
1
(3),
263–284
(1985).
10.1007/BF00244272 Google Scholar
- 15 A. Bundy. “ Incidence Calculus,” Technical Report 497, University of Edinburgh, Department of Artificial Intelligence, 1990.
- 16 R. Fagin and J. Y. Halpern, “Uncertainty, Belief, and Probability,” Technical Report RJ-6191, IBM Research Report, 1989.
- 17 N. J. Nilsson, “Probabilistic Logic,” Artificial Intelligence, 28, 71–87 (1986).
- 18
G. Boole,
An Investigation of the Laws of Thought—on which are Founded the Mathematical Theories of Logic and Probabilities,
MacMillan, London,
1854.
10.5962/bhl.title.29413 Google Scholar
- 19 T. Hailperin, Boole's Logic and Probability (2nd ed). North-Holland, New York, 1986.
- 20
G. Shafer,
A Mathematical Theory of Evidence.
Princeton Univ. Press, Princeton NJ,
1976.
10.1515/9780691214696 Google Scholar
- 21 A. P. Dempster, “Upper and lower probabilities induced by a multivalued mapping,” Annals of Math. Stat. 38, 325–339 (1967).
- 22 A. P. Dempster, “A Generalisation of Bayesian Inference,” J. Royal Stat. Soc. 30, 205–247 (1968).
- 23
Z. Pawlak,
“Rough Sets,”
Int. J. Info. Computer Sci.
11, 145–172
(1982).
10.1007/BF01001956 Google Scholar
- 24 A. Bundy and W. Liu, “On Dempster's combination rule,” (submitted to the Artificial Intelligence Journal). University of Edinburgh, Department of Artificial Intelligence, 1993.
- 25 W. Liu and A. Bundy, “ Incidence Calculus and Generalized Incidence Calculus,” (internal communication), University of Edinburgh, Department of Artificial Intelligence, 1993.
- 26
E. Mendelson,
Introduction to Mathematical Logic, (3rd Ed),
Wadsworth & Brooks/ Cole, Monterey,
1987.
10.1007/978-1-4615-7288-6 Google Scholar
- 27 J. L. Bell and A. B. Slomson. Models and Ultraproducts: an Introduction, North-Holland, 1971.
- 28 A. Kolmogorov, Foundations of the Theory of Probability, Chelsea, New York, 1956.
- 29
A. Bundy,
Correctness criteria of some algorithms for uncertain reasoning using Incidence Calculus,
J. Auto. Reas.
2
(1),
109–126,
(1986).
10.1007/BF02432147 Google Scholar
- 30 R. A. Corlett and S. J. Todd, “ A Monte Carlo approach to uncertain inference,” In Artificial Intelligence and its Applications, A. G. Cohn and J. R. Thomas, Eds., John Wiley, New York, 1986.
- 31 R. G. McLean, Testing and Extending the Incidence Calculus, Msc thesis, Edinburgh University, 1992.
- 32 P. Smets, “ The transferable belief model and other interpretations of Dempster-Shafer's model,” In 6th Conference on Uncertainty in Artificial Intelligence, 1990.
- 33 R. Fagin, J. Y. Halpern, and N. Megiddo, “A logic for reasoning about probabilities,” Information and Computation, 87, 78–128 (1990).
- 34 R. Ng and V. S. Subrahmanian, “Probabilistic logic programming,” Information and Computation, to appear.
- 35 R. Ng and V. S. Subrahmanian, Stable Semantics for Probabilistic Deductive Databases, Technical Report 2573, University of Maryland, Department of Computer Science, 1990.
- 36 R. Ng and V. S. Subrahmanian, “A semantical framework for supporting subjective and conditional probabilities in deductive databases,” Technical Report 2563, University of Maryland, Department of Computer Science, 1990.
