Proteins, Particles, and Pseudo-Max-Marginals: A Submodular Approach
Jason Pacheco, Erik B. Sudderth · 2015
Variants of max-product (MP) belief propagation effectively find modes of many complex graph-ical models, but are limited to discrete distribu-tions. Diverse particle max-product (D-PMP) ro-bustly approximates max-product updates in con-tinuous MRFs using stochastically sampled par-ticles, but previous work was specialized to tree-structured models. Motivated by the challeng-ing problem of protein side chain prediction, we extend D-PMP in several key ways to create a generic MAP inference algorithm for loopy mod-els. We define a modified diverse particle selec-tion objective that is provably submodular, lead-ing to an efficient greedy algorithm with rigorous optimality guarantees, and corresponding max-marginal error bounds. We further incorporate tree-reweighted variants of the MP algorithm to allow provable verification of global MAP re-covery in many models. Our general-purpose MATLAB library is applicable to a wide range of pairwise graphical models, and we validate our approach using optical flow benchmarks. We fur-ther demonstrate superior side chain prediction accuracy compared to baseline algorithms from the state-of-the-art Rosetta package. 1.