Consistent Structured Estimation for Weighted Bipartite Matching
author:
Tibério Caetano,
National ICT Australia
author: James Petterson, National ICT Australia
author: Julian McAuley, National ICT Australia
author: James Petterson, National ICT Australia
author: Julian McAuley, National ICT Australia
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.
You might be experiencing some problems with Your Video player.
| Slides | |
| 0:00 | Exponential Family Bipartite Matching |
| 0:13 | Outline |
| 0:37 | The Problem |
| 0:41 | Overview (1) |
| 0:54 | Overview (2) |
| 1:02 | Assumptions |
| 1:25 | Applications (1) |
| 1:45 | Applications (2) |
| 1:59 | Formulation (1) |
| 2:54 | Formulation (2) |
| 4:25 | The Model |
| 4:34 | Our Contribution |
| 5:31 | Maximum-Likelihood Marriage Estimator (1) |
| 7:20 | Maximum-Likelihood Marriage Estimator (2) |
| 8:31 | Maximum-Likelihood Marriage Estimation (1) |
| 9:37 | Maximum-Likelihood Marriage Estimation (2) |
| 10:27 | Model Estimation |
| 10:34 | Maximum-Likelihood Marriage Estimation (1) |
| 12:20 | General Idea of Sampler (1) |
| 13:41 | General Idea of Sampler (2) |
| 14:39 | The Sampler |
| 16:22 | The Upper Bound |
| 16:33 | Monte Carlo |
| 16:45 | Optimization |
| 16:56 | Experiments |
| 17:34 | Matching with vs without learning (1) |
| 17:54 | Matching with vs without learning (2) |
| 18:03 | Matching with vs without learning (3) |
| 18:09 | Ranking (1) |
| 18:23 | Ranking (2) |
| 18:46 | Ranking (3) |
| 19:27 | Ranking (4) |
| 20:12 | Ranking (5) |
| 21:45 | Ranking (6) |
| 22:58 | Ranking (7) |
| 23:29 | Ranking (8) |
| 23:42 | Final remarks |
| 24:50 | Questions |
| 27:10 | - Questions |
Lecture rating
| People found this lecture: | ||
| Worth seeing | ||
| because it is: | ||
| Valuable and informative | ||
| Well presented | ||
| Easily understandable | ||
| Acceptably recorded | ||
| You need to login to cast your vote. | ||
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.
Related content
Visitors who watched this lecture also watched...
Link this page
Would you like to put a link to this lecture on your homepage?Go ahead! Copy the HTML snippet !





