Skip to Main content Skip to Navigation
Conference papers

Recherche complète à voisinages variables guidée par la décomposition arborescente pour la minimisation d'énergie dans les modèles graphiques

Abstract : Graphical models factorize a global probability distribution/energy function as the product/sum of local functions. A major inference task, known as MAP in Markov Random Fields and MPE in Bayesian Networks, is to find a global assignment of all the variables with maximum probability/minimum energy. A usual distinction on MAP/MPE solving methods is complete/incomplete, i.e. the ability to prove optimality or not. Most complete methods rely on tree search, while incomplete methods rely on local search. Among them, we study Variable Neighborhood Search (VNS) for graphical models. In this paper, we propose an iterative approach above VNS which uses (partial) tree search inside its local neighborhood exploration. The resulting hybrid method offers a better compromise between completeness and anytime behavior than existing tree search methods while still being competitive for proving optimality. We further propose a parallel version of our method improving its anytime behavior on difficult instances coming from a large graphical model benchmark. Last we experiment on the challenging minimum energy problem found in Computational Protein Design, showing the practical benefit of our parallel version. Solver is available at https:/ / github.com/ toulbar2/ toulbar2.
Document type :
Conference papers
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download

https://hal.inrae.fr/hal-02733676
Contributor : Migration Prodinra <>
Submitted on : Tuesday, June 2, 2020 - 12:53:54 PM
Last modification on : Wednesday, May 12, 2021 - 8:14:09 AM
Long-term archiving on: : Wednesday, December 2, 2020 - 1:00:27 PM

File

JFRB_2018_paper_12ALLOUCHE_1.p...
Publisher files allowed on an open archive

Identifiers

Citation

Abdelkader Ouali, David Allouche, Simon de Givry, Samir Loudni, Yahia Lebbah, et al.. Recherche complète à voisinages variables guidée par la décomposition arborescente pour la minimisation d'énergie dans les modèles graphiques. 9e Journées Francophones sur les Réseaux Bayésiens et les Modèles Graphiques Probabilistes 2018 (JFRB 2018), May 2018, Toulouse, France. 114 p., ⟨10.3166/RIA.-.1-7⟩. ⟨hal-02733676⟩

Share

Metrics

Record views

110

Files downloads

31