Afficher la notice abrégée

Exact or approximate inference in graphical models: why the choice is dictated by the treewidth, and how variable elimination can be exploited

hal.structure.identifierUnité de Mathématiques et Informatique Appliquées de Toulouse [MIAT INRA]
dc.contributor.authorPEYRARD, Nathalie
hal.structure.identifierUnité de Mathématiques et Informatique Appliquées de Toulouse [MIAT INRAE]
dc.contributor.authorCROS, Marie-Josée
hal.structure.identifierUnité de Mathématiques et Informatique Appliquées de Toulouse [MIAT INRA]
dc.contributor.authorDE GIVRY, Simon
hal.structure.identifierBiodiversité, Gènes & Communautés [BioGeCo]
hal.structure.identifierfrom patterns to models in computational biodiversity and biotechnology [PLEIADE]
dc.contributor.authorFRANC, Alain
hal.structure.identifierAgroParisTech
hal.structure.identifierMathématiques et Informatique Appliquées [MIA Paris-Saclay]
dc.contributor.authorROBIN, Stephane
hal.structure.identifierUnité de Mathématiques et Informatique Appliquées de Toulouse [MIAT INRA]
dc.contributor.authorSABBADIN, Régis
hal.structure.identifierUnité de Mathématiques et Informatique Appliquées de Toulouse [MIAT INRAE]
dc.contributor.authorSCHIEX, Thomas
hal.structure.identifierMassey University
dc.contributor.authorVIGNES, Matthieu
dc.date.issued2019-06-06
dc.identifier.issn1369-1473
dc.description.abstractEnProbabilistic graphical models offer a powerful framework to account for the dependence structure between variables, which is represented as a graph. However, the dependence between variables may render inference tasks intractable. In this paper, we review techniques exploiting the graph structure for exact inference, borrowed from optimisation and computer science. 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. The so‐called treewidth of the graph characterises this algorithmic complexity: low‐treewidth graphs can be processed efficiently. The first point that we illustrate is therefore the idea that for inference in graphical models, the number of variables is not the limiting factor, and it is worth checking the width of several tree decompositions of the graph before resorting to the approximate method. We show how algorithms providing an upper bound of the treewidth can be exploited to derive a ‘good' elimination order enabling to realise exact inference. The second point is that when the treewidth is too large, algorithms for approximate inference linked to the principle of variable elimination, such as loopy belief propagation and variational approaches, can lead to accurate results while being much less time consuming than Monte‐Carlo approaches. We illustrate the techniques reviewed in this article on benchmarks of inference problems in genetic linkage analysis and computer vision, as well as on hidden variables restoration in coupled Hidden Markov Models.
dc.description.sponsorshipDécomposition de Modèles Graphiques - ANR-16-CE40-0028
dc.language.isoen
dc.publisherWiley
dc.subject.enMarginalisation
dc.subject.enMode evaluation
dc.subject.enMessage passing
dc.subject.enComputational inference
dc.subject.enVariational approximations
dc.title.enExact or approximate inference in graphical models: why the choice is dictated by the treewidth, and how variable elimination can be exploited
dc.typeArticle de revue
dc.identifier.doi10.1111/anzs.12257
dc.subject.halMathématiques [math]/Statistiques [math.ST]
bordeaux.journalAustralian and New Zealand Journal of Statistics
bordeaux.page89-133
bordeaux.volume61
bordeaux.issue2
bordeaux.peerReviewedoui
hal.identifierhal-02433018
hal.version1
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-02433018v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=Australian%20and%20New%20Zealand%20Journal%20of%20Statistics&rft.date=2019-06-06&rft.volume=61&rft.issue=2&rft.spage=89-133&rft.epage=89-133&rft.eissn=1369-1473&rft.issn=1369-1473&rft.au=PEYRARD,%20Nathalie&CROS,%20Marie-Jos%C3%A9e&DE%20GIVRY,%20Simon&FRANC,%20Alain&ROBIN,%20Stephane&rft.genre=article


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