Economics Dictionary of Arguments

Home Screenshot Tabelle Begriffe

 
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


Send Link
> Counter arguments against Russell
> Counter arguments in relation to Variable Elimination

Authors A   B   C   D   E   F   G   H   I   J   K   L   M   N   O   P   Q   R   S   T   U   V   W   Z  


Concepts A   B   C   D   E   F   G   H   I   J   K   L   M   N   O   P   Q   R   S   T   U   V   W   Z