Material Detail

Consistent Structured Estimation for Weighted Bipartite Matching

Consistent Structured Estimation for Weighted Bipartite Matching

This video was recorded at NIPS Workshop on Algebraic and Combinatorial Methods in Machine Learning, Whistler 2008. Given a weighted bipartite graph, the assignment problem consists of finding the heaviest perfect match. This is a classical problem in combinatorial optimization, which is solvable exactly and efficiently by standard methods such as the Hungarian algorithm, and is widely applicable in real-world scenarios. We give an exponential family model for the assignment problem. Edge weights are obtained from a suitable composition of edge features and a parameter vector, which is learned so as to maximize the likelihood of a sample consisting of training graphs and their labeled matches. The resulting consistent estimator contrasts with existing max-margin structured estimators, which are inconsistent for this problem.


  • User Rating
  • Comments
  • Learning Exercises
  • Bookmark Collections
  • Course ePortfolios
  • Accessibility Info

More about this material


Log in to participate in the discussions or sign up if you are not already a MERLOT member.