Title: On the Role of Partial Differentiation in Probabilistic Inference
Authors: Adnan Darwiche
Series: Linköping Electronic Articles in Computer and Information Science
ISSN 1401-9841
Issue: Vol. 5 (2000), No. 028
URL: http://www.ep.liu.se/ea/cis/2000/028/

Abstract: We present in this paper one of the simplest, yet most comprehensive frameworks for inference in Bayesian networks. According to this framework, one compiles a Bayesian network into a polynomial -- in which variables correspond to potential evidence and network parameters -- and then computes the partial derivatives of this polynomial with respect to each variable. Once such derivatives are made available, one can compute in constant-time answers to a large class of probabilistic queries, which are central to classical inference, parameter estimation, model validation and sensitivity analysis. We show a number of key results relating to this framework.

First, given a Bayesian network of size n and an elimination order of width w, we present an elimination algorithm for compiling the polynomial in  O(n exp(w))  time and space.

Next, given some evidence and parameter setting, we show that the compiled polynomial can be evaluated, and all its first partial derivatives computed simultaneously, in  O(n exp(w))  time and space. Once these derivatives are made available, we show that one can compute in constant-time: the posterior marginal of any network variable or family, the probability of evidence after having retracted the value of any evidence variable, and the sensitivity of evidence probability to change in any network parameter.

Finally, we show that second partial derivatives can all be computed simultaneously in  O(n2 exp(w))  time and space. Moreover, once such derivatives are made available, one can compute in constant-time a variety of sophisticated queries, such as context-specific independence between any pair of variables, and the amount of change to some network parameter which is needed to ensure a particular ranking on some hypotheses.

The proposed framework provides new insights into the role of partial differentiation in probabilistic inference. Moreover, its combined simplicity, comprehensiveness and computational complexity appear to be unique among existing frameworks for inference in Bayesian networks.


First posting
1999-04-06
In ETAI Newsletter and Decision and Reasoning under Uncertainty
Original publication
2000-12-21
Postscript part I -- Checksum
Checksum (old) Information about recalculation of checksum
Postscript part II -- Checksum II
Checksum II (old) Information about recalculation of checksum

This article was first posted on the Internet as specified under "First posting", and appeared on the E-press server on the date specified under "Original publication".