Consistent Structured Estimation for Weighted Bipartite Matching
author: Tibério Caetano,
National ICT Australia
author: James Petterson, National ICT Australia
author: Julian McAuley, Department of Computer Science and Engineering, UC San Diego
published: Dec. 20, 2008, recorded: December 2008, views: 5689
author: James Petterson, National ICT Australia
author: Julian McAuley, Department of Computer Science and Engineering, UC San Diego
published: Dec. 20, 2008, recorded: December 2008, views: 5689
Slides
Related content
Report a problem or upload files
If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Description
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.
Link this page
Would you like to put a link to this lecture on your homepage?Go ahead! Copy the HTML snippet !
Write your own review or comment: