A differential approach to inference in Bayesian networks

ABSTRACT

We present a new approach to inference in Bayesian networks, which is based on representing the network using a polynomial and then retrieving answers to probabilistic queries by evaluating and differentiating the polynomial. The network polynomial itself is exponential in size, but we show how it can be computed efficiently using an arithmetic circuit that can be evaluated and differentiated in time and space linear in the circuit size. The proposed framework for inference subsumes one of the most influential methods for inference in Bayesian networks, known as the tree-clustering or jointree method, which provides a deeper understanding of this classical method and lifts its desirable characteristics to a much more general setting. We discuss some theoretical and practical implications of this subsumption.

REFERENCES

• 1: Bodlaender, H. L. 1993. A tourist guide through treewidth. Acta Cybernetica 11, 1-2, 1--22.
• 2: Hans L. Bodlaender, A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth, SIAM Journal on Computing, v.25 n.6, p.1305-1317, Dec. 1996 [doi>10.1137/S0097539793251219]
• 3: Randal E. Bryant, Graph-based algorithms for Boolean function manipulation, IEEE Transactions on Computers, v.35 n.8, p.677-691, Aug. 1986 [doi>10.1109/TC.1986.1676819]
• 4: Castillo, E., Gutiérrez, J. M., and Hadi, A. S. 1996. Goal oriented symbolic propagation in Bayesian networks. In Proceedings of the AAAI National Conference. pp. 1263--1268.
• 5: Castillo, E., Gutiérrez, J. M., and Hadi, A. S. 1997. Sensitivity analysis in discrete Bayesian networks. IEEE Trans. Syst. Man, and Cybernetics 27, 412--423.
• 6: Chan, H., and Darwiche, A. 2002. When do numbers really matter? J. Artif. Intel. Res. 17, 265--287.
• 7: Robert G. Cowell , Steffen L. Lauritzen , A. Philip David , David J. Spiegelhalter , V. Nair , J. Lawless , M. Jordan , David J. Spiegelhater, Probabilistic Networks and Expert Systems, Springer-Verlag New York, Inc., Secaucus, NJ, 1999
• 8: Adnan Darwiche, Recursive conditioning, Artificial Intelligence, v.126 n.1-2, p.5-41, Feb., 2001 [doi>10.1016/S0004-3702(00)00069-2 ]
• 9: Adnan Darwiche, A compiler for deterministic, decomposable negation normal form, Eighteenth national conference on Artificial intelligence, p.627-634, July 28-August 01, 2002, Edmonton, Alberta, Canada
• 10: Darwiche, A. 2002b. A logical approach to factoring belief networks. In Proceedings of KR. pp. 409--420.
• 11: Darwiche, A., and Marquis, P. 2002. A knowlege compilation map. J. Artif. Intel. Res. 17, 229--264.
• 12: Dechter, R. 1996. Bucket elimination: A unifying framework for probabilistic inference. In Proceedings of the 12th Conference on Uncertainty in Artificial Intelligence (UAI). pp. 211--219.
• 13: Huang, C., and Darwiche, A. 1996. Inference in belief networks: A procedural guide. Int. J. Approx. Reason. 15, 3, 225--263.
• 14: Iri, M. 1984. Simultaneous computation of functions, partial derivatives and estimates of rounding error. Japan J. Appl. Math. 1, 223--252.
• 15: Jensen, F., and Andersen, S. K. 1990. Approximations in Bayesian belief universes for knowledge based systems. In Proceedings of the 6th Conference on Uncertainty in Artificial Intelligence (UAI) (Cambridge, Mass, July). pp. 162--169.
• 16: Finn Verner Jensen, Gradient Descent Training of Bayesian Networks, Proceedings of the European Conference on Symbolic and Quantitative Approaches to Reasoning and Uncertainty, p.190-200, July 05-09, 1999
• 17: Jensen, F. V., Lauritzen, S., and Olesen, K. 1990. Bayesian updating in recursive graphical models by local computation. Computat. Stat. Quart. 4, 269--282.
• 18: Uffe Kjærulff , Linda C. van der Gaag, Making Sensitivity Analysis Computationally Efficient, Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence, p.317-325, June 30-July 03, 2000
• 19: Steffen L. Lauritzen, The EM algorithm for graphical association models with missing data, Computational Statistics & Data Analysis, v.19 n.2, p.191-201, Feb. 1995 [doi>10.1016/0167-9473(93)E0056-A ]
• 20: Park, J. 2002. MAP complexity results and approximation methods. In Proceedings of the 18th Conference on Uncertainty in Artificial Intelligence (UAI) (San Francisco, Calif.). Morgan Kaufmann, San Mateo, Calif., pp. 388--396.
• 21: James D. Park , Adnan Darwiche, Approximating MAP using Local Search, Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, p.403-410, August 02-05, 2001
• 22: Park, J., and Darwiche, A. 2002. A differential semantics for jointree algorithms. In Proceedings of the Symposium on Advances in Neural Information Processing Systems 15. MIT Press, Cambridge, Mass., pp. 299--307.
• 23: Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 24: N. Robertson , P. D. Seymour, Graph minors. IV. Tree-width and well-quasi-ordering, Journal of Combinatorial Theory Series B, v.48 n.2, p.227-254, Apr. 1990 [doi>10.1016/0095-8956(90)90120-O]
• 25: Russell, S., Binder, J., Koller, D., and Kanazawa, K. 1995. Local learning in probabilistic networks with hidden variables. In Proceedings of the 11th Conference on Uncertainty in Artificial Intelligence (UAI) (1995). pp. 1146--1152.
• 26: Sawyer, J. W. 1984. First partial differentiation by computer with an application to categorical data analysis. Amer. Stat. 38, 4, 300--308.
• 27: Shachter, R., D'Ambrosio, B., and del Favero, B. 1990. Symbolic Probabilistic Inference in Belief Networks. In Proceedings of the Conference on Uncertainty in AI. pp. 126--131.
• 28: Shenoy, P. P., and Shafer, G. 1986. Propagating belief functions with local computations. IEEE Expert 1, 3, 43--52.
• 29: Joachim von zur Gathen, Algebraic complexity theory, Annual review of computer science: vol. 3, 1988, Annual Reviews Inc., Palo Alto, CA, 1988
• 30: Zhang, N. L., and Poole, D. 1996. Exploiting causal independence in Bayesian network inference. J. Artif. Intel. Res. 5, 301--328.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
  G.3 PROBABILITY AND STATISTICS

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION

General Terms:
Algorithms, Theory

Keywords:
Bayesian networks, Probabilistic reasoning, circuit complexity, compiling probabilistic models