Variable neighborhood search for graphical model energy minimization - INRAE - Institut national de recherche pour l’agriculture, l’alimentation et l’environnement Accéder directement au contenu
Article Dans Une Revue Artificial Intelligence Année : 2020

Variable neighborhood search for graphical model energy minimization

Résumé

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 a posteriori probability/minimum energy. A usual distinction on MAP 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 that uses (partial) tree search inside its local neighborhood exploration. The proposed approach performs several neighborhood explorations of increasing search complexity, by controlling two parameters, the discrepancy limit and the neighborhood size. Thus, optimality of the obtained solutions can be proven when the neighborhood size is maximal and with unbounded tree search. 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. A solver is available at https:// github .com /toulbar2 /toulbar2.
Fichier principal
Vignette du fichier
S0004370218305927.pdf (860.7 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-02463467 , version 1 (21-12-2021)

Licence

Paternité - Pas d'utilisation commerciale

Identifiants

Citer

Abdelkader Ouali, David Allouche, Simon de Givry, Samir Loudni, Yahia Lebbah, et al.. Variable neighborhood search for graphical model energy minimization. Artificial Intelligence, 2020, 278, pp.103194. ⟨10.1016/j.artint.2019.103194⟩. ⟨hal-02463467⟩
136 Consultations
108 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More