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

Les modèles graphiques probabilistes unifient la théorie des probabilités et les modèles graphiques via des variables aléatoires reliées entre elles par une distribution de loi jointe décomposable. L’objectif étudié ici est connu sous le nom de Maximum A Posteriori dans les champs aléatoires de Markov et de Most Probable Explanation dans les réseaux bayésiens, consiste à trouver une affectation globale de toutes les variables ayant une probabilité maximale ou de manière équivalente une énergie minimale. Les méthodes de résolution MAP/MPE sont qualifiées habituellement de complète ou incomplète, selon leur capacité à prouver l’optimalité ou non. Alors que la plupart des méthodes complètes reposent sur la recherche arborescente, les méthodes incomplètes reposent, quant à elles, sur la recherche locale. Dans cet article, nous proposons une approche itérative potentiellement complète au-dessus d’une recherche à voisinages variables qui utilise la recherche arborescente partielle dans son exploration locale des voisinages. La méthode hybride qui en résulte a été evaluée sur un large éventail de benchmarks issus de l’analyse d’images, la reconnaissance de formes, l’allocation de ressources, la bio-informatique, la bio-physique. . . Les résultats montrent que comparée aux méthodes de recherche arborescente existantes, notre méthode offre un meilleur compromis entre le comportement anytime et la preuve d’optimalité. Enfin, l’expérimentation de notre version parallèle sur des instances difficiles issues de la conception de protéines a mis en évidence l’efficacité de la version parallèle pour trouver des bonnes solutions. Le solveur est librement téléchargeable sur https:/ / github.com/ toulbar2/ toulbar2.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