Timezone: »

Minimizing Sparse High-Order Energies by Submodular Vertex-Cover
Andrew Delong · Olga Veksler · Anton Osokin · Yuri Boykov

Tue Dec 04 07:00 PM -- 12:00 AM (PST) @ Harrah’s Special Events Center 2nd Floor #None

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.

Author Information

Andrew Delong (Concordia University)
Olga Veksler (University of Western Ontario)
Anton Osokin (National Research University HSE, Moscow, Russia)
Yuri Boykov (University of Western Ontario)

More from the Same Authors