Timezone: »

Efficient Sampling for Bipartite Matching Problems
Maksims Volkovs · Richard Zemel

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

Bipartite matching problems characterize many situations, ranging from ranking in information retrieval to correspondence in vision. Exact inference in real-world applications of these problems is intractable, making efficient approximation methods essential for learning and inference. In this paper we propose a novel {\it sequential matching} sampler based on the generalization of the Plackett-Luce model, which can effectively make large moves in the space of matchings. This allows the sampler to match the difficult target distributions common in these problems: highly multimodal distributions with well separated modes. We present experimental results with bipartite matching problems - ranking and image correspondence - which show that the sequential matching sampler efficiently approximates the target distribution, significantly outperforming other sampling approaches.

Author Information

Maksims Volkovs (University of Toronto)
Richard Zemel (Vector Institute/University of Toronto)

More from the Same Authors