The computational complexity of probabilistic inference using Bayesian belief networks. (English) Zbl 0717.68080
Summary: Bayesian belief networks provide a natural, efficient method for representing probabilistic dependencies among a set of variables. For these reasons, numerous researchers are exploring the use of belief networks as a knowledge representation in artificial intelligence. Algorithms have been developed previously for efficient probabilistic inference using special classes of belief networks. More general classes of belief networks, however, have eluded efforts to develop efficient inference algorithms. We show that probabilistic inference using belief networks is NP-hard. Therefore, it seems unlikely that an exact algorithm can be developed to perform probabilistic inference efficiently over all classes of belief networks. This result suggests that research should be directed away from the search for a general, efficient probabilistic inference algorithm, and toward the design of efficient special-case, average-case, and approximation algorithms.
Software:
NESTORReferences:
| [1] | Agogino, A. M.; Rege, A., IDES: Influence diagram based expert system, Math. Modelling, 8, 227-233 (1987) |
| [2] | Andreassen, S.; Woldbye, M.; Falck, B.; Andersen, S. K., MUNIN: A causal probabilistic network for interpretation of electromyographic findings, (Proceedings IJCAI-87. Proceedings IJCAI-87, Milan, Italy (1987)) |
| [3] | Chavez, R. M.; Cooper, G. F., KNET: Integrating hypermedia and normative Bayesian modeling, (Proceedings Workshop on Uncertainty in Artificial Intelligence. Proceedings Workshop on Uncertainty in Artificial Intelligence, Minneapolis, MN (1988)) |
| [4] | Chin, H. L.; Cooper, G. F., Bayesian belief network inference using simulation, (Kanal, L. N.; Levitt, T. S.; Lemmer, J. F., Uncertainty in Artificial Intelligence, 3 (1989), North-Holland: North-Holland Amsterdam), 129-147 |
| [5] | Cook, S. A., The complexity of theorem-proving procedures, (Proceedings Third Annual ACM Symposium on Theory of Computing. Proceedings Third Annual ACM Symposium on Theory of Computing, New York (1971)), 151-158 · Zbl 0363.68125 |
| [6] | Cooper, G. F., NESTOR: A computer-based medical diagnostic aid that integrates causal and probabilistic knowledge, (Ph.D. Dissertation (1984), Stanford University: Stanford University Stanford, CA) |
| [7] | Cooper, G. F., The computational complexity of probabilistic inference using belief networks, (Rept. KSL-87-27 (1987), Medical Computer Science Group, Stanford University: Medical Computer Science Group, Stanford University Stanford, CA) · Zbl 0717.68080 |
| [8] | Cooper, G. F., An algorithm for computing probabilistic propositions, (Kanal, L. N.; Levitt, T. S.; Lemmer, J. F., Uncertainty in Artificial Intelligence, 3 (1989), North-Holland: North-Holland Amsterdam), 3-14 |
| [9] | Duda, R. O.; Hart, P. E.; Nilsson, N. J., Subjective Bayesian methods for rule-based inference systems, (Proceedings 1976 National Computer Conference (1976)) |
| [10] | Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman New York · Zbl 0411.68039 |
| [11] | Good, I. J., A causal calculus I, British J. Philos. Sci., 11, 305-318 (1961) |
| [12] | Good, I. J., A causal calculus II, British J. Philos. Sci., 12, 43-51 (1962) |
| [13] | Henrion, M., Propagating uncertainty by logic sampling in Bayes’ networks, (Kanal, L. N.; Lemmer, J. F., Uncertainty in Artificial Intelligence, 2 (1988), North-Holland: North-Holland Amsterdam) · Zbl 0649.68095 |
| [14] | Henrion, M., Towards efficient probabilistic diagnosis in multiply-connected belief networks, (Proceedings Conference on Influence Diagrams. Proceedings Conference on Influence Diagrams, Berkeley, CA (1988)) |
| [15] | Henrion, M.; Cooley, D. R., An experimental comparison of knowledge engineering for expert systems and for decision analysis, (Proceedings AAAI-87. Proceedings AAAI-87, Seattle, WA (1987)) |
| [16] | Holtzman, S., Intelligent Decision Systems (1989), Addison-Wesley: Addison-Wesley Reading, MA |
| [17] | Lauritzen, S. L.; Spiegelhalter, D. J., Local computations with probabilities on graphical structures and their application to expert systems, J. Roy. Stat. Soc., B 50, 157-224 (1988) · Zbl 0684.68106 |
| [18] | Lichtenstein, D., Planar formulae and their uses, SIAM J. Comput., 11, 329-343 (1982) · Zbl 0478.68043 |
| [19] | Nilsson, N. J., Probabilistic logic, Artificial Intelligence, 28, 71-87 (1986) · Zbl 0589.03007 |
| [20] | Pearl, J., Fusion, propagation, and structuring in belief networks, Artificial Intelligence, 29, 241-288 (1986) · Zbl 0624.68081 |
| [21] | Pearl, J., Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference (1988), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA |
| [22] | Pearl, J.; Verma, T. S., The logic of representing dependencies by directed graphs, (Proceedings AAAI-87. Proceedings AAAI-87, Seattle, WA (1987)) |
| [23] | Y. Peng and J. Reggia, A comfort measure for diagnostic problem-solving, Inf. Sci.; Y. Peng and J. Reggia, A comfort measure for diagnostic problem-solving, Inf. Sci. · Zbl 0635.68112 |
| [24] | Pople, H. E., Heuristic methods for imposing structure on ill-structured problems: The structuring of medical diagnostics, (Szolovits, P., Artificial Intelligence in Medicine (1982), Westview Press: Westview Press Boulder, CO), 119-190 |
| [25] | Provan, J. S.; Ball, M. O., The complexity of counting cuts and of computing the probability that a graph is connected, SIAM J. Comput., 12, 777-788 (1983) · Zbl 0524.68041 |
| [26] | Rosenthal, A., A computer scientist looks at reliability computations, (Barlow, R. E.; Fussell, J. B.; Singpurwalla, N. D., Reliability and Fault Tree Analysis (1975), SIAM: SIAM Philadelphia, PA), 133-152 |
| [27] | Rosenthal, A., Computing the reliability of complex networks, SIAM J. Appl. Math., 32, 384-393 (1977) · Zbl 0379.90048 |
| [28] | Rousseau, W. F., A method for computing probabilities in complex situations, (Rept. 6252-2 (1968), Center for Systems Research, Stanford University: Center for Systems Research, Stanford University Stanford, CA) |
| [29] | Shachter, R. D., Intelligent probabilistic inference, (Kanal, L. N.; Lemmer, J. F., Uncertainty in Artificial Intelligence (1986), North-Holland: North-Holland Amsterdam), 371-382 · Zbl 0605.68094 |
| [30] | Weiss, J. M.; Kulikowski, C. A.; Amarel, S.; Safir, A., A model-based method for computeraided medical decision-making, Artificial Intelligence, 11, 145-172 (1978) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
