Journal of the ACM Bibliography

Abstract

Probabilistic reasoning suffers from NP-hard implementations. In particular, the amount of probabilistic information necessary to the computations is often overwhelming. For example, the size of conditional probability tables in Bayesian networks has long been a limiting factor in the general use of these networks.

We present a new approach for manipulating the probabilistic information given. This approach avoids being overwhelmed by essentially compressing the information using approximation functions called linear potential functions. We can potentially reduce the information from a combinatorial amount to roughly linear in the number of random variable assignments. Furthermore, we can compute these functions through closed form equations. As it turns out, our approximation method is quite general and may be applied to other data compression problems.

The abstract is also available as a LaTeX file, a DVI file, or a PostScript file.

Categories and Subject Descriptors: E.4 [Coding and Information Theory]; G.1.2 [Numerical Analysis]: Approximation; G.1.6 [Numerical Analysis]: Optimization; I.2.3 [Artificial Intelligence]: Deduction and Theorem Proving; I.5 [Pattern Recognition]

General Terms: Algorithms, Design, Experimentation, Theory

Additional Key Words and Phrases: Artificial intelligence, data compaction and compression, integer programming, least squares approximation, pattern recognition, probabilistic reasoning, uncertainty

Selected references

• Eugene Charniak and Robert Goldman. A logic for semantic interpretation. In Proceedings of the 26th Annual Meeting of the Association for Computational Linguistics, pages 87-94, 1988.

• Eugene Charniak and Eugene Santos, Jr. Dynamic map calculations for abduction. In Proceedings of the AAAI Conference, pages 552-557, 1992.

• Eugene Charniak and Solomon E. Shimony. Probabilistic semantics for cost based abduction. In Proceedings of the AAAI Conference, pages 106-111, 1990.

• Gregory F. Cooper. Probabilistic inference using belief networks is NP-hard. Technical Report KSL-87-27, Medical Computer Science Group, Stanford University, 1987.

• Paul Dagum and Michael Luby. Approximating probabilistic inference in Bayesian belief networks is NP-hard. Artificial Intelligence, 60 (1):141-153, 1993.

• R. Davis. Diagnostic reasoning based on structure and behavior. Artificial Intelligence, 24:347-410, 1984.

• Thomas Dean. Using goals to find plans with high expected utility. In Proceedings of the Second European Workshop on Planning, 1993.

• R. O. Duda, P. E. Hart, and N. J. Nilsson. Subjective bayesian methods for rule-based inference systems. In Proceedings of the National Computer Conference, 1976.

• Robert P. Goldman. A Probabilistic Approach to Language Understanding. PhD thesis, Department of Computer Science, Brown University, 1990.

• Robert P. Goldman and Eugene Charniak. Probabilistic text understanding. In Proceedings of the Third International Workshop on AI and Statistics, Fort Lauderdale, FL, 1991.

• Jerry R. Hobbs, Mark Stickel, Paul Martin, and Douglas Edwards. Interpretation as abduction. In Proceedings of the 26th Annual Meeting of the Association for Computational Linguistics, pages 95-103, 1988.

• Narendra Karmarkar and Richard M. Karp. An efficient approximation scheme for the one-dimensional bin-packing problem. In 23rd Annual Symposium on Foundations of Computer Science, pages 312-320, Chicago, Illinois, 3-5 November 1982. IEEE.

• Jak Kirman, Kenneth Basye, and Thomas Dean. Sensor abstractions for control of navigation. In Proceedings of the IEEE International Conference on Robotics and Automation, pages 2812-2817, 1991.

• Philip Klein, Serge A. Plotkin, C. Stein, and Eva Tardos. Faster approximation algorithms for the unit capacity concurrent flow problem with applications to routing and finding sparse cuts. Technical Report Technical Report 961, Schools of Operations Research and Industrial Engineering, Cornell University, 1991.

• H. Lehmann. Probabilistic diagnosis using a reformulation of the internist-1/qmr knowledge base: I. the probabilistic model and inference algorithms. Methods of Information in Medicine, 30:241-255, 1991.

• C. McMillan. Mathematical Programming. John-Wiley & Sons, Inc., 1975.

• George L. Nemhauser, A. H. G. Rinnooy Kan, and M. J. Todd, editors. Optimization: Handbooks in Operations Research and Management Science Volume 1, volume 1. North Holland, 1989.

• Judea Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, San Mateo, CA, 1988.

• Yun Peng and James A. Reggia. Abductive Inference Models for Diagnostic Problem-Solving. Springer-Verlag, 1990.

• Yun Peng and James A. Reggia. Plausibility of diagnostic hypothese: The nature of simplicity. In Proceedings of the AAAI Conference, pages 140-147, 1986.

• Serge A. Plotkin, David B. Shmoys, and Éva Tardos. Fast approximation algorithms for fractional packing and covering problems. In 32nd Annual Symposium on Foundations of Computer Science, pages 495-504, San Juan, Puerto Rico, 1-4 October 1991. IEEE.

• Prabhakar Raghavan. Probabilistic construction of deterministic algorithms: Approximating packing integer programs. Journal of Computer and System Sciences, 37(2):130-143, October 1988.

• Eugene Santos, Jr. On the generation of alternative explanations with implications for belief revision. In Proceedings of the Conference on Uncertainty in Artificial Intelligence, pages 337-347, 1991.

• Eugene Santos, Jr. A fast hill-climbing approach without an energy function for finding mpe. In Proceedings of the 5th IEEE International Conference on Tools with Artificial Intelligence, 1993.

• Eugene Santos, Jr. A linear constraint satisfaction approach to cost-based abduction. Artificial Intelligence, 65(1):1-28, 1994.

• Eugene Santos, Jr. and Solomon Eyal Shimony. Belief updating by enumerating high-probability independence-based assignments. In Proceedings of the Conference on Uncertainty in Artificial Intelligence, pages 506-513, 1994.

• A. Schrijver. Theory of Linear and Integer Programming. John Wiley & Sons Ltd., 1986.

• Murray Shanahan. Prediction is deduction but explanation is abduction. In Proceedings of the International Joint Conference on Artificial Intelligence, pages 1055-1060, 1989.

• Solomon E. Shimony. The role of relevance in explanation I: Irrelevance as statistical independence. International Journal of Approximate Reasoning, June 1993.

• Solomon E. Shimony and Eugene Charniak. A new algorithm for finding map assignments to belief networks. In Proceedings of the Conference on Uncertainty in Artificial Intelligence, 1990.

• Sampath Srinivas. A generalization of the noisy-or model. In Proceedings of the Conference on Uncertainty in Artificial Intelligence, pages 208-215, 1993.

• Bon K. Sy. Reasoning mpe to multiply connected belief networks using message passing. In Proceedings of the Tenth National Conference on Artificial Intelligence, 1992.

Shortcuts: