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

Autor: Simon de Givry, Alain Franc, Nathalie Peyrard, Stéphane Robin, Régis Sabbadin, Matthieu Vignes, Marie-Josée Cros, Thomas Schiex
Přispěvatelé: Unité de Mathématiques et Informatique Appliquées de Toulouse (MIAT INRA), Institut National de la Recherche Agronomique (INRA), Biodiversité, Gènes & Communautés (BioGeCo), Université de Bordeaux (UB)-Institut National de la Recherche Agronomique (INRA), from patterns to models in computational biodiversity and biotechnology (PLEIADE), Université de Bordeaux (UB)-Institut National de la Recherche Agronomique (INRA)-Université de Bordeaux (UB)-Institut National de la Recherche Agronomique (INRA)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Bordelais de Recherche en Informatique (LaBRI), Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université Sciences et Technologies - Bordeaux 1-Université Bordeaux Segalen - Bordeaux 2-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université Sciences et Technologies - Bordeaux 1-Université Bordeaux Segalen - Bordeaux 2, AgroParisTech, Mathématiques et Informatique Appliquées (MIA-Paris), Institut National de la Recherche Agronomique (INRA)-AgroParisTech, Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS), Massey University, Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE), Institut National de la Recherche Agronomique (INRA)-Université de Bordeaux (UB), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Biodiversité, Gènes & Communautés (BioGeCo), Institut National de la Recherche Agronomique (INRA)-Université de Bordeaux (UB)-Institut National de la Recherche Agronomique (INRA), Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE)-AgroParisTech-Université Paris-Saclay, Unité de Mathématiques et Informatique Appliquées de Toulouse (MIAT INRAE), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest, Mathématiques et Informatique Appliquées (MIA Paris-Saclay), AgroParisTech-Université Paris-Saclay-Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE), ANR-16-CE40-0028,DE-MO-GRAPH,Décomposition de Modèles Graphiques(2016), AgroParisTech-Institut National de la Recherche Agronomique (INRA)
Jazyk: angličtina
Rok vydání: 2019
Předmět:
Zdroj: Australian and New Zealand Journal of Statistics
Australian and New Zealand Journal of Statistics, Wiley, 2019, 61 (2), pp.89-133. ⟨10.1111/anzs.12257⟩
Australian and New Zealand Journal of Statistics, 2019, 61 (2), pp.89-133. ⟨10.1111/anzs.12257⟩
ISSN: 1369-1473
1467-842X
DOI: 10.1111/anzs.12257⟩
Popis: to appear; International audience; Probabilistic 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.
Databáze: OpenAIRE
Externí odkaz: