Timezone: »
We present a method for learning max-weight matching predictors in bipartite graphs. The method consists of performing maximum a posteriori estimation in exponential families with sufficient statistics that encode permutations and data features. Although inference is in general hard, we show that for one very relevant application - document ranking - exact inference is efficient. For general model instances, an appropriate sampler is readily available. Contrary to existing max-margin matching models, our approach is statistically consistent and, in addition, experiments with increasing sample sizes indicate superior improvement over such models. We apply the method to graph matching in computer vision as well as to a standard benchmark dataset for learning document ranking, in which we obtain state-of-the-art results, in particular improving on max-margin variants. The drawback of this method with respect to max-margin alternatives is its runtime for large graphs, which is high comparatively.
Author Information
James Petterson (NICTA)
Tiberio Caetano (NICTA Canberra)
Julian J McAuley (Stanford)
Jin Yu
More from the Same Authors
-
2014 Poster: (Almost) No Label No Cry »
Giorgio Patrini · Richard Nock · Tiberio Caetano · Paul Rivera -
2014 Spotlight: (Almost) No Label No Cry »
Giorgio Patrini · Richard Nock · Tiberio Caetano · Paul Rivera -
2012 Poster: Learning to Discover Social Circles in Ego Networks »
Julian J McAuley · Jure Leskovec -
2012 Poster: Learning as MAP Inference in Discrete Graphical Models »
Tiberio Caetano · Xianghang Liu · James Petterson -
2012 Poster: A Convex Formulation for Learning Scale-Free Networks via Submodular Relaxation »
Aaron Defazio · Tiberio Caetano -
2012 Session: Oral Session 8 »
Tiberio Caetano -
2012 Spotlight: A Convex Formulation for Learning Scale-Free Networks via Submodular Relaxation »
Aaron Defazio · Tiberio Caetano -
2011 Workshop: Philosophy and Machine Learning »
Marcello Pelillo · Joachim M Buhmann · Tiberio Caetano · Bernhard Schölkopf · Larry Wasserman -
2011 Poster: Submodular Multi-Label Learning »
James Petterson · Tiberio Caetano -
2010 Poster: Word Features for Latent Dirichlet Allocation »
James Petterson · Alexander Smola · Tiberio Caetano · Wray L Buntine · Shravan M Narayanamurthy -
2010 Poster: Reverse Multi-Label Learning »
James Petterson · Tiberio Caetano -
2010 Poster: Multitask Learning without Label Correspondences »
Novi Quadrianto · Alexander Smola · Tiberio Caetano · S.V.N. Vishwanathan · James Petterson -
2009 Workshop: Learning with Orderings »
Tiberio Caetano · Carlos Guestrin · Jonathan Huang · Risi Kondor · Guy Lebanon · Marina Meila -
2009 Poster: Convex Relaxation of Mixture Regression with Efficient Algorithms »
Novi Quadrianto · Tiberio Caetano · John Lim · Dale Schuurmans -
2009 Poster: Distribution Matching for Transduction »
Novi Quadrianto · James Petterson · Alexander Smola -
2008 Poster: Robust Near-Isometric Matching via Structured Learning of Graphical Models »
Julian J McAuley · Tiberio Caetano · Alexander Smola