TY - GEN
T1 - Proteins, particles, and pseudo-max-marginals
T2 - 32nd International Conference on Machine Learning, ICML 2015
AU - Pacheco, Jason L.
AU - Sudderth, Erik B.
N1 - Publisher Copyright:
© Copyright 2015 by International Machine Learning Society (IMLS). All rights reserved.
PY - 2015
Y1 - 2015
N2 - Variants of max-product (MP) belief propagation effectively find modes of many complex graphical models, but are limited to discrete distributions. Diverse particle max-product (D-PMP) robustly approximates max-product updates in continuous MRFs using stochastically sampled particles, but previous work was specialized to tree-structured models. Motivated by the challenging problem of protein side chain prediction, we extend D-PMP in several key ways to create a generic MAP inference algorithm for loopy models. We define a modified diverse particle selection objective that is provably submodular, leading 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 recovery 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 further demonstrate superior side chain prediction accuracy compared to baseline algorithms from the state-of-the-art Rosetta package.
AB - Variants of max-product (MP) belief propagation effectively find modes of many complex graphical models, but are limited to discrete distributions. Diverse particle max-product (D-PMP) robustly approximates max-product updates in continuous MRFs using stochastically sampled particles, but previous work was specialized to tree-structured models. Motivated by the challenging problem of protein side chain prediction, we extend D-PMP in several key ways to create a generic MAP inference algorithm for loopy models. We define a modified diverse particle selection objective that is provably submodular, leading 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 recovery 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 further demonstrate superior side chain prediction accuracy compared to baseline algorithms from the state-of-the-art Rosetta package.
UR - http://www.scopus.com/inward/record.url?scp=84969922888&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84969922888&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84969922888
T3 - 32nd International Conference on Machine Learning, ICML 2015
SP - 2190
EP - 2198
BT - 32nd International Conference on Machine Learning, ICML 2015
A2 - Bach, Francis
A2 - Blei, David
PB - International Machine Learning Society (IMLS)
Y2 - 6 July 2015 through 11 July 2015
ER -