Economics Dictionary of ArgumentsHome | |||
| |||
Variable elimination: Variable elimination is a method used in probabilistic graphical models to compute probabilities efficiently by eliminating irrelevant variables. It simplifies computations by eliminating variables that are not needed to answer specific queries, reducing computational complexity while retaining accuracy in probabilistic inference._____________Annotation: The above characterizations of concepts are neither definitions nor exhausting presentations of problems related to them. Instead, they are intended to give a short introduction to the contributions below. – Lexicon of Arguments. | |||
Author | Concept | Summary/Quotes | Sources |
---|---|---|---|
Stuart J. Russell 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, 83–158. 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 [Concept/Author], [Author1]Vs[Author2] or [Author]Vs[term] resp. "problem:"/"solution:", "old:"/"new:" and "thesis:" is an addition from the Dictionary of Arguments. If a German edition is specified, the page numbers refer to this edition. |
Russell I B. Russell/A.N. Whitehead Principia Mathematica Frankfurt 1986 Russell II B. Russell The ABC of Relativity, London 1958, 1969 German Edition: Das ABC der Relativitätstheorie Frankfurt 1989 Russell IV B. Russell The Problems of Philosophy, Oxford 1912 German Edition: Probleme der Philosophie Frankfurt 1967 Russell VI B. Russell "The Philosophy of Logical Atomism", in: B. Russell, Logic and KNowledge, ed. R. Ch. Marsh, London 1956, pp. 200-202 German Edition: Die Philosophie des logischen Atomismus In Eigennamen, U. Wolf (Hg), Frankfurt 1993 Russell VII B. Russell On the Nature of Truth and Falsehood, in: B. Russell, The Problems of Philosophy, Oxford 1912 - Dt. "Wahrheit und Falschheit" In Wahrheitstheorien, G. Skirbekk (Hg), Frankfurt 1996 Norvig I Peter Norvig Stuart J. Russell Artificial Intelligence: A Modern Approach Upper Saddle River, NJ 2010 |