Exact and approximate inference in graphical models: variable elimination and beyond
FRANC, Alain
from patterns to models in computational biodiversity and biotechnology [PLEIADE]
Biodiversité, Gènes & Communautés [BioGeCo]
See more >
from patterns to models in computational biodiversity and biotechnology [PLEIADE]
Biodiversité, Gènes & Communautés [BioGeCo]
FRANC, Alain
from patterns to models in computational biodiversity and biotechnology [PLEIADE]
Biodiversité, Gènes & Communautés [BioGeCo]
< Reduce
from patterns to models in computational biodiversity and biotechnology [PLEIADE]
Biodiversité, Gènes & Communautés [BioGeCo]
Language
en
Document de travail - Pré-publication
This item was published in
2015
English Abstract
Probabilistic graphical models offer a powerful framework to account for the dependence structure between variables, which can be represented as a graph. The dependence between variables may render inference tasks such as ...Read more >
Probabilistic graphical models offer a powerful framework to account for the dependence structure between variables, which can be represented as a graph. The dependence between variables may render inference tasks such as computing normalizing constant, marginalization or optimization intractable. The objective of this paper is to review techniques exploiting the graph structure for exact inference borrowed from optimization and computer science. They are not yet standard in the statistician toolkit, and we specify under which conditions they are efficient in practice. They are built on the principle of variable elimination whose complexity is dictated in an intricate way by the order in which variables are eliminated in the graph. The so-called treewidth of the graph characterizes this algorithmic complexity: low-treewidth graphs can be processed efficiently. Algorithmic solutions derived from variable elimination and the notion of treewidth are illustrated on problems of treewidth computation and inference in challenging benchmarks from optimization competitions. We also review how efficient techniques for approximate inference such as loopy belief propagation and variational approaches can be linked to variable elimination and we illustrate them in the context of Expectation-Maximisation procedures for parameter estimation in coupled Hidden Markov Models.Read less <
English Keywords
treewidth
computational inference
graphical model
variational approximations
message passing
Origin
Hal imported