Title: | On the Role of Partial Differentiation in Probabilistic Inference |

Authors: | Adnan Darwiche |

Series: | Linköping Electronic Articles
in Computer and Information ScienceISSN 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 exp(w)) 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 exp(w)) Finally, we show that second partial derivatives can all be computed
simultaneously in exp(w)) 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".*