Consistent Structured Estimation for Weighted Bipartite Matching
author:James Petterson, National ICT Australia
author:Julian McAuley, National ICT Australia
published: Dec. 20, 2008, recorded: December 2008, views: 113
Slides
Related content
24:34
106 views - Eun Yong Kang, 2008
54:09
194 views - Steve Hanneke, 2008
33:19
72 views - Aiden Roger Doherty, 2008
12:00
499 views - Davide Albanese, 2008
18:36
125 views - Aapo Hyvärinen, Kun Zhang, Patrik Hoyer, 2008
19:42
96 views - Brian Tanner, 2008
05:39:24
547 views - Tibério Caetano, 2008
23:01
56 views - Sebastian J. Schultheiss, 2008
19:59
148 views - Joaquin Vanschoren, 2008
24:59
1734 views - Kaspar Riesen, 2007
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.
See Also:
Download slides:
aml08_caetano_csewbm_01.pdf (1.7 MB)
Launch in a standalone WM Player
Switch to Windows Media Player
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: