Minimizing Sparse High-Order Energies by Submodular Vertex-Cover
Delong, Andrew, Veksler, Olga, Osokin, Anton, Boykov, Yuri
–Neural Information Processing Systems
Inference on high-order graphical models has become increasingly important in recent years. We consider energies with simple 'sparse' high-order potentials. Previous work in this area uses either specialized message-passing or transforms each high-order potential to the pairwise case. We take a fundamentally different approach, transforming the entire original problem into a comparatively small instance of a submodular vertex-cover problem. These vertex-cover instances can then be attacked by standard pairwise methods, where they run much faster (4--15 times) and are often more effective than on the original problem. We evaluate our approach on synthetic data, and we show that our algorithm can be useful in a fast hierarchical clustering and model estimation framework.
Neural Information Processing Systems
Dec-31-2012