Peter Norvig on Variable Elimination - Dictionary of Arguments
Norvig I 545
Variable Elimination/Norvig/Russell: The basic idea of variable elimination—that repeated computations within the overall sum-of-products expression can be avoided by caching—appeared in the symbolic probabilistic inference (SPI) algorithm (Shachter et al., 1990)(1). Cf. the elimination algorithm (…) developed by Zhang and Poole (1994)(2). Criteria for pruning irrelevant variables were developed by Geiger et al. (1990)(3) and by Lauritzen et al. (1990)(4) (…). Dechter (1999)(5) shows how the variable elimination idea is essentially identical to nonserial dynamic programming (Bertele and Brioschi, 1972)(6), an algorithmic approach that can be applied to solve a range of inference problems in Bayesian networks - for example, finding the most likely explanation for a set of observations.
This connects Bayesian network algorithms to related methods for solving CSPs (>Constraint satisfaction problems) and gives a direct measure of the complexity of exact inference in terms of the tree width of the network. Wexler and Meek (2009)(7) describe a method of preventing exponential growth in the size of factors computed in variable elimination; their algorithm breaks down large factors into products of smaller factors and simultaneously computes an error bound for the resulting approximation. >Bayesian networks/Norvig, >Uncertainty/AI research.
1. Shachter, R. D., D’Ambrosio, B., and Del Favero, B. A. (1990). Symbolic probabilistic inference in belief networks. In AAAI-90, pp. 126–131.
2. Zhang, N. L., Qi, R., and Poole, D. (1994). A computational theory of decision networks. IJAR, 11,
3. Geiger, D., Verma, T., and Pearl, J. (1990). Identifying independence in Bayesian networks. Networks, 20(5), 507–534.
4. Lauritzen, S., Dawid, A. P., Larsen, B., and Leimer, H. (1990). Independence properties of directed
Markov fields. Networks, 20(5), 491–505
5. Dechter, R. (1999). Bucket elimination: A unifying framework for reasoning. AIJ, 113, 41–85.
6. Bertele, U. and Brioschi, F. (1972). Nonserial dynamic programming. Academic Press.
7. Wexler, Y. and Meek, C. (2009). MAS: A multiplicative approximation scheme for probabilistic inference. In NIPS 21._____________Explanation of symbols: Roman numerals indicate the source, arabic numerals indicate the page number. The corresponding books are indicated on the right hand side. ((s)…): Comment by the sender of the contribution. Translations: Dictionary of Arguments The note [Author1]Vs[Author2] or [Author]Vs[term] is an addition from the Dictionary of Arguments. If a German edition is specified, the page numbers refer to this edition.
Stuart J. Russell
Artificial Intelligence: A Modern Approach Upper Saddle River, NJ 2010