Göm menyn
Files: Description Format
Fulltext PDF (requires Acrobat Reader)
Fulltext part 1 PostScript (requires a PostScript Reader)
  Fulltext part 2 PostScript (requires a PostScript Reader)
Author: Adnan Darwiche
Article title: On the Role of Partial Differentiation in Probabilistic Inference
Publ. type: Article
Volume: 5
Article No: 28
Language: English
Abstract [en]: 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.

Publisher: LINKÖPING University Electronic Press
Year: 2000
Available: 2000-12-21
No. of pages: 9
Series: LINKÖPING Electronic Articles in Computer and Information Science
ISSN: 1401-9841
Note: First posting 1999-04-06 in ETAI Newsletter and Decision and Reasoning under Uncertainty

Responsible for this page: Peter Berkesand
Last updated: 2017-02-21