×

Variable neighborhood search for graphical model energy minimization. (English) Zbl 1478.68329

Summary: 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.

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
62H22 Probabilistic graphical models
92D20 Protein sequences, DNA sequences
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Koller, D.; Friedman, N., Probabilistic Graphical Models: Principles and Techniques (2009), The MIT Press · Zbl 1183.68483
[2] Shimony, S., Finding MAPs for belief networks is NP-hard, AI Commun., 68, 399-410 (1994) · Zbl 0818.68097
[3] Marinescu, R.; Dechter, R., Memory intensive and/or search for combinatorial optimization in graphical models, AI Commun., 173, 16-17, 1492-1524 (2009) · Zbl 1185.68649
[4] Otten, L.; Dechter, R., Anytime AND/OR depth-first search for combinatorial optimization, AI Commun., 25, 3, 211-227 (2012) · Zbl 1250.90075
[5] Allouche, D.; de Givry, S.; Katsirelos, G.; Schiex, T.; Zytnicki, M., Anytime hybrid best-first search with tree decomposition for weighted CSP, (Proc. of CP (2015)), 12-28
[6] Kolmogorov, V., Convergent tree-reweighted message passing for energy minimization, IEEE Trans. Pattern Anal. Mach. Intell., 28, 10, 1568-1583 (2006)
[7] Wainwright, M.; Jordan, M., Graphical models, exponential families, and variational inference, Found. Trends Mach. Learn., 1, 1-2, 1-305 (2008) · Zbl 1193.62107
[8] Sontag, D.; Meltzer, T.; Globerson, A.; Jaakkola, T.; Weiss, Y., Tightening LP relaxations for MAP using message-passing, (Proc. of UAI (2008)), 503-510
[9] Sontag, D.; Choe, D.; Li, Y., Efficiently searching for frustrated cycles in MAP inference, (Proc. of UAI (2012)), 795-804
[10] Wang, H.; Koller, D., Subproblem-tree calibration: a unified approach to max-product message passing, (Proc. of ICML (2013)), 190-198
[11] Park, J., Using weighted MAX-SAT engines to solve MPE, (Proc. of AAAI (2002)), 682-687
[12] Hutter, F.; Hoos, H.; Stützle, T., Efficient stochastic local search for MPE solving, (Proc. of IJCAI (2005)), 169-174
[13] Mengshoel, O.; Wilkins, D.; Roth, D., Initialization and restart in stochastic local search: computing a most probable explanation in Bayesian networks, IEEE Trans. Knowl. Data Eng., 23, 2, 235-247 (2011)
[14] Marinescu, R.; Kask, K.; Dechter, R., Systematic vs. non-systematic algorithms for solving the MPE task, (Proc. of UAI (2003)), 394-402
[15] Shaw, P., Using constraint programming and local search methods to solve vehicle routing problems, (Proc. of CP (1998)), 417-431
[16] Perron, L.; Shaw, P.; Furnon, V., Propagation guided large neighborhood search, (Proc. of CP (2004)), 468-481 · Zbl 1152.68572
[17] Lombardi, M.; Schaus, P., Cost impact guided lns, (Proc. of Integration of AI and OR Techniques in Constraint Programming (2014)), 293-300
[18] Dekker, J. J.; de la Banda, M. G.; Schutt, A.; Stuckey, P. J.; Tack, G., Solver-independent large neighbourhood search, (Proc. of CP (2018)), 81-98
[19] Demirovic, E.; Chu, G.; Stuckey, P. J., Solution-based phase saving for CP: a value-selection heuristic to simulate local search behavior in complete solvers, (Proc. of CP (2018)), 99-108
[20] Mladenović, N.; Hansen, P., Variable neighborhood search, Comput. Oper. Res., 24, 11, 1097-1100 (1997) · Zbl 0889.90119
[21] Loudni, S.; Boizumault, P., Solving constraint optimization problems in anytime contexts, (Proc. of IJCAI (2003)), 251-256
[22] Harvey, W.; Ginsberg, M., Limited discrepancy search, (Proc. of IJCAI (1995)), 607-615
[23] Fontaine, M.; Loudni, S.; Boizumault, P., Exploiting tree decomposition for guiding neighborhoods exploration for VNS, RAIRO Oper. Res., 47, 2, 91-123 (2013) · Zbl 1267.68211
[24] Davidovic, T.; Crainic, T., MPI parallelization of variable neighborhood search, Electron. Notes Discrete Math., 39, 241-248 (2012) · Zbl 1268.68150
[25] Ouali, A.; Loudni, S.; Loukil, L.; Boizumault, P.; Lebbah, Y., Replicated parallel strategies for decomposition guided VNS, Electron. Notes Discrete Math., 47, 93-100 (2015)
[26] Simoncini, D.; Allouche, D.; de Givry, S.; Delmas, C.; Barbe, S.; Schiex, T., Guaranteed discrete energy optimization on large protein design problems, J. Chem. Theory Comput., 11, 12, 5980-5989 (2015)
[27] Meseguer, P.; Rossi, F.; Schiex, T., Soft constraints processing, (Handbook of Constraint Programming (2006), Elsevier), 279-326, Ch. 9
[28] Hurley, B.; O’Sullivan, B.; Allouche, D.; Katsirelos, G.; Schiex, T.; Zytnicki, M.; de Givry, S., Multi-language evaluation of exact solvers in graphical model discrete optimization, Constraints, 21, 3, 413-434 (2016) · Zbl 1368.90107
[29] Dechter, R.; Rish, I., Mini-buckets: a general scheme for bounded inference, J. ACM, 50, 2, 107-153 (2003) · Zbl 1326.68335
[30] Larrosa, J.; de Givry, S.; Heras, F.; Zytnicki, M., Existential arc consistency: getting closer to full arc consistency in weighted CSPs, (Proc. of IJCAI (2005)), 84-89
[31] Cooper, M.; de Givry, S.; Sanchez, M.; Schiex, T.; Zytnicki, M.; Werner, T., Soft arc consistency revisited, AI Commun., 174, 449-478 (2010) · Zbl 1213.68580
[32] Karoui, W.; Huguet, M.-J.; Lopez, P.; Naanaa, W., Yields: a yet improved limited discrepancy search for csps, (Proc. of Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (2007)), 99-111 · Zbl 1214.68358
[33] Prosser, P.; Unsworth, C., Limited discrepancy search revisited, ACM J. Exp. Algorithmics, 16, 1.6:1.1-1.6:1.18 (2011) · Zbl 1284.68722
[34] Bodlaender, H.; Koster, A., Treewidth computations I. Upper bounds, Inf. Comput., 208, 3, 259-275 (2010) · Zbl 1186.68328
[35] Bodlaender, H.; Koster, A.; Van den Eijkhof, F., Preprocessing rules for triangulation of probabilistic networks, Comput. Intell., 21, 3, 286-305 (2005)
[36] Arnborg, S., Complexity of finding embeddings in a k-tree, SIAM J. Algebraic Discrete Methods, 8, 277-284 (1987) · Zbl 0611.05022
[37] Kjærulff, U., Triangulation of Graphs - Algorithms Giving Small Total State Space (1990), Aalborg University, Tech. rep.
[38] Tarjan, R. E., Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs, SIAM J. Comput., 13, 3, 566-579 (1984) · Zbl 0545.68062
[39] Luby, M.; Sinclair, A.; Zuckerman, D., Optimal speedup of Las Vegas algorithms, (Proc. of TCS (1993)), 128-133 · Zbl 0797.68139
[40] Boussemart, F.; Hemery, F.; Lecoutre, C.; Sais, L., Boosting systematic search by weighting constraints, (Proc. of ECAI (2004)), 146-150
[41] Kappes, J.; Andres, B.; Hamprecht, F.; Schnörr, C.; Nowozin, S.; Batra, D.; Kim, S.; Kausler, B.; Kröger, T.; Lellmann, J.; Komodakis, N.; Savchynskyy, B.; Rother, C., A comparative study of modern inference techniques for structured discrete energy minimization problems, Int. J. Comput. Vis., 115, 2, 155-184 (2015)
[42] Favier, A.; Givry, S.; Legarra, A.; Schiex, T., Pairwise decomposition for combinatorial optim. in graphical models, (Proc. of IJCAI (2011)), 2126-2132
[43] de Givry, S.; Prestwich, S.; O’Sullivan, B., Dead-end elimination for weighted CSP, (Proc. of CP (2013)), 263-272
[44] Ihler, A.; Flerova, N.; Dechter, R.; Otten, L., Join-graph based cost-shifting schemes, (Proc. of UAI (2012)), 397-406
[45] Otten, L.; Ihler, A.; Kask, K.; Dechter, R., Winning the PASCAL 2011 MAP challenge with enhanced AND/OR branch-and-bound, (Proc. of NIPS Workshop DISCML (2012))
[46] Neveu, B.; Trombettoni, G.; Glover, F., ID walk: a candidate list strategy with a simple diversification device, (Proc. of CP (2004)), 423-437 · Zbl 1152.68568
[47] Mooij, J. M., libDAI: a free and open source C++ library for discrete approximate inference in graphical models, J. Mach. Learn. Res., 11, 2169-2173 (2010) · Zbl 1242.62004
[48] Otten, L.; Dechter, R., And/or branch-and-bound on a computational grid, J. Artif. Intell. Res., 59, 351-435 (2017) · Zbl 1418.68189
[49] Allouche, D.; Davies, J.; de Givry, S.; Katsirelos, G.; Schiex, T.; Traoré, S.; André, I.; Barbe, S.; Prestwich, S.; O’Sullivan, B., Computational protein design as an optimization problem, AI Commun., 212, 59-79 (2014) · Zbl 1407.92099
[50] Huang, P.-S.; Boyken, S. E.; Baker, D., The coming of age of de novo protein design, Nature, 537, 320-327 (2016)
[51] Lippow, S. M.; Tidor, B., Progress in computational protein design, Protein Technologies/Systems Biology. Protein Technologies/Systems Biology, Curr. Opin. Biorecovery, 18, 4, 305-311 (2007)
[52] Trudeau, D. L.; Tawfik, D. S., Protein engineers turned evolutionists—the quest for the optimal starting point, Pharmaceutical Biotechnology. Pharmaceutical Biotechnology, Curr. Opin. Biotechnol., 60, 46-52 (2019)
[53] Abseher, M.; Musliu, N.; Woltran, S., Improving the efficiency of dynamic programming on tree decompositions via machine learning, J. Artif. Intell. Res., 58, 829-858 (2017) · Zbl 1407.68386
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.