Afficher la notice abrégée

Exact and approximate inference in graphical models: variable elimination and beyond

hal.structure.identifierUnité de Biométrie et Intelligence Artificielle (ancêtre de MIAT) [UBIA]
dc.contributor.authorDUBOIS PEYRARD, Nathalie
hal.structure.identifierUnité de Biométrie et Intelligence Artificielle (ancêtre de MIAT) [UBIA]
dc.contributor.authorDE GIVRY, Simon
hal.structure.identifierfrom patterns to models in computational biodiversity and biotechnology [PLEIADE]
hal.structure.identifierBiodiversité, Gènes & Communautés [BioGeCo]
dc.contributor.authorFRANC, Alain
hal.structure.identifierMathématiques et Informatique Appliquées [MIA-Paris]
dc.contributor.authorROBIN, Stephane
hal.structure.identifierUnité de Biométrie et Intelligence Artificielle (ancêtre de MIAT) [UBIA]
dc.contributor.authorSABBADIN, Régis
hal.structure.identifierUnité de Biométrie et Intelligence Artificielle (ancêtre de MIAT) [UBIA]
dc.contributor.authorSCHIEX, Thomas
hal.structure.identifierUnité de Biométrie et Intelligence Artificielle (ancêtre de MIAT) [UBIA]
dc.contributor.authorVIGNES, Matthieu
dc.date.created2015-06-30
dc.date.issued2015
dc.description.abstractEnProbabilistic 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.
dc.language.isoen
dc.subject.entreewidth
dc.subject.encomputational inference
dc.subject.engraphical model
dc.subject.envariational approximations
dc.subject.enmessage passing
dc.title.enExact and approximate inference in graphical models: variable elimination and beyond
dc.typeDocument de travail - Pré-publication
dc.typePrepublication/Preprint
dc.subject.halSciences du Vivant [q-bio]
dc.identifier.arxiv1506.08544
hal.identifierhal-01197655
hal.version1
hal.popularnon
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-01197655v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.date=2015&rft.au=DUBOIS%20PEYRARD,%20Nathalie&DE%20GIVRY,%20Simon&FRANC,%20Alain&ROBIN,%20Stephane&SABBADIN,%20R%C3%A9gis&rft.genre=preprint&unknown


Fichier(s) constituant ce document

FichiersTailleFormatVue

Il n'y a pas de fichiers associés à ce document.

Ce document figure dans la(les) collection(s) suivante(s)

Afficher la notice abrégée