Broad Area Colloquium For AI-Geometry-Graphics-Robotics-Vision
(CS 528)

Polynomials, Circuits and Bayesian Network Inference

Adnan Darwiche
Computer Science Department
Monday, April 12, 2004, 4:15PM
TCSeq 200


Bayesian networks (and probabilistic graphical models) have become standard tools for modeling and reasoning under uncertainty in many AI applications. One of the central computational questions surrounding these models is that of inference: computing the probability of various events with respect to the distributions encoded by these models.

I will present in this talk a non-classical formulation of the inference problem in Bayesian networks and discuss its practical and theoretical implications. According to this formulation, each Bayesian network is interpreted as a multivariate polynomial (with an exponential number of terms), and probabilistic inference is reduced to a process of evaluating the partial derivatives of this polynomial. The central computational question is then that of finding a compact representation of the network polynomial. I will propose arithmetic circuits for this purpose, together with a specific algorithm for finding small arithmetic circuits that compute network polynomials. I will show how this approach for inference subsumes (and provides new insights on) the standard one, based on jointrees, which has dominated the inference literature for more than a decade. I will also show how the new approach allows one to exploit both network connectivity (global structure) and its parameterization (local structure). Finally, I will illustrate its performance on very difficult networks, including those synthesized from relational probabilistic models. These networks are rich with local structure, yet are too connected to be within the reach of standard inference methods based on jointrees.

About the Speaker

Dr. Adnan Darwiche is an Associate Professor of Computer Science at UCLA. His main research interests are in probabilistic and symbolic automated reasoning and their various applications, especially to system analysis and diagnosis. Dr. Darwiche was a program co-chair of the Eighteenth Conference on Uncertainty in AI (UAI'02), the Eleventh International Workshop on Principles of Diagnosis (DX'00), and the general chair of the Nineteenth Conference on Uncertainty in AI (UAI'03). He is currently an Associate Editor for the Journal of Artificial Intelligence Research (JAIR) and has served on the program committees of many conferences, including the International Joint Conference on AI (IJCAI), the National Conference on AI (AAAI), and the Conference on Uncertainty in AI (UAI). Dr. Darwiche has published more than 50 papers in leading journals and conferences relating to automated reasoning, diagnosis and AI, and was the recipient of the OKAWA Foundation Award for research in 2000. Prior to joining UCLA, Dr. Darwiche was a senior scientist and manager of the department of diagnostics and modeling at Rockwell Science Center. Dr. Darwiche received his Ph.D. and M.S. degrees in computer science from Stanford University in 1993 and 1989, respectively.


Back to the Colloquium Page