DUBOIS PEYRARD, Nathalie; DE GIVRY, Simon; FRANC, Alain; ROBIN, Stephane; SABBADIN, Régis; SCHIEX, Thomas; VIGNES, Matthieu

Métadonnées

Licence d’utilisation du document

DUBOIS PEYRARD, Nathalie
Unité de Biométrie et Intelligence Artificielle (ancêtre de MIAT) [UBIA]

DE GIVRY, Simon
Unité de Biométrie et Intelligence Artificielle (ancêtre de MIAT) [UBIA]

FRANC, Alain
from patterns to models in computational biodiversity and biotechnology [PLEIADE]
Biodiversité, Gènes & Communautés [BioGeCo]

Langue

Document de travail - Pré-publication

Ce document a été publié dans

2015

Résumé en anglais

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.< Réduire

Mots clés en anglais

treewidth

computational inference

graphical model

variational approximations

message passing

Origine

Importé de hal

Unités de recherche

BioGeCo (Biodiversité Gènes & Communautés) - UMR 1202