Proceedings

On the Relations between Probabilistic Logic and p-CMS

Download BibTeX Cite

Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence. Automated Reasoning. Pages 56-62.

© 1999 International Joint Conferences on Artificial Intelligence

Abstract

We discuss the relationship between probabilistic logic and 1r-CMS. Given a set of logical sentences and their probabilities of being true, the outcome of a probabilistic logic system consists of lower and upper bounds on the probability of an additional sentence to be true . These bounds are computed using a linear programming formulation. In 1r-CMS systems, the outcome is defined by the probabilities of the support and the plausibility (with the assumptions being independent) after a first phase which consists of computing the prime implicants depending only on the variables of the assumptions. We propose to reformulate a 7rCMS system without independence conditions on the assumptions, using the linear programming framework of probabilistic logic, and show how to exploit its particular structure to solve it efficiently. When an independence condition is imposed on the assumptions the two systems give different results. Comparisons are made on small problems using the assumption-based evidential language program (ABEL) of [Anrig et al., 1998] and the PSAT program of [Jaumard et al., 1991].

  1. [Anrig et al., 1998] Bernhard Anrig, Roman Bissig, Rolf Haenni , Jiirg Kohlas, and Nobert Lehmann. Prob- abilistic Argumentation Systems: Introduction to Assumption-Based Modeling using ABEL. Techni- cal report, Institute of Informatics, University of Fri- bourg, September 1998.
  2. [Chvatal, 1983] Vasek Chvatal. Linear Programming. Freeman, New York, NY, 1983.
  3. [de Kleer and Williams, 1987] Johan de Kleer and Brian C. Williams. Diagnosing Multiple Faults. Artificial Intelligence, 32(1):97-130, 1987.
  4. [de Kleer, 1986] Johan de Kleer. An Assumption-based TMS . Artificial Intelligence, 28:127-162, 1986.
  5. [de Kleer, 1992] Johan de Kleer. An Improved Incre- mental Algorithm for Generating Prime Implicates. In Proc. of the 10th Nat. Conf. on Artificial Intelli- gence, pages 780-785, San Jose, California, July 1992.
  6. A A AI. [Fisher and Kedia, 1990]
  7. Marchall L. Fisher and Pradeep Kedia. Optimal Solution of Set Cover- ing/Partitioning Problems Using Dual Heuristics. Management Science, 36(6):674-688, June 1990.
  8. [Glover and Laguna, 1997] Fred Glover and Manuel La- guna. Tabu Search. Kluwer, 1997.
  9. [Hansen and Jaumard, 1990] Pierre Hansen and Brigitte Jaumard. Algorithms for the Maximum Satisfiability Problem. Computing, 44:279-303, 1990.
  10. [Hansen et al., 1995] Pierre Hansen, Brigitte Jaumard, and Marcus V. Poggi de Aragao. Boole's Conditions HANSEN. JAUMARD. AND PARREIRA of Possible Experience and Reasoning Under Uncer- tainty. Discrete Applied Mathematics, 60:181-193, 1995.
  11. Hansen et al., 1999) Pierre Hansen, Brigitte Jaumard, Anderson D. Parreira, and Marcus V. Poggi de Aragao. Difficulties of Conditioning and Con- ditional Independence in Probabilistic Satisfiabil- ity. Technical Report G-99-16, Cahiers du GERAD , February 1999.
  12. Jaumard et al., 1991)
  13. Brigitte Jaumard, Pierre Hansen, and Marcus V. Poggi de Aragao. Column Generation Methods for Probabilistic Logic. ORSA Journal on Computing, 3:135-148, 1991.
  14. Kohlas and Haenni, 1996) Jiirg Kohlas and Rolf Haenni. Assumption-based Reasoning and Proba- bilistic Argumentation Systems. In J. Kohlas and S. Moral, editors, Defeasible Reasoning and Uncertainty Management Systems: Algorithms. Oxford University Press, 1996.
  15. Lasdon, 1970)
  16. Leon S. Lasdon. Optimization Theory for Large Systems. MacMillan, New York, 1970.
  17. Liu et al., 1993) Weiru Liu, Alan Bundy, and Dave Robertson. On the Relations between Incidence Cal- culus and ATMS. In Symbolic and Quantitative Ap- proaches to Reasoning and Uncertainty (Granada, 1993 ), pages 249-256. Springer-Verlag, Berlin, 1993.
  18. Nilsson, 1986)
  19. Nils J. Nilsson. Probabilistic Logic. Ar- tificial Intelligence, 28:71-87, 1986.
  20. Reiter and de Kleer, 1987) Raymond Reiter and Jo- han de Kleer. Foundations of Assumption-Based Truth Maintenance Systems: Preliminary Report. In Proc. of the 6th Nat. Conf. on Artificial Intelligence, volume 1, pages 183-188, Seatle, Washington, July 1987.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards