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.

Back to the Colloquium Page