BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Predict\, Price and Cut: Column and Row Generation for Structured 
 Prediction -  Sebastian Riedel\, University College London
DTSTART:20121116T120000Z
DTEND:20121116T130000Z
UID:TALK40798@talks.cam.ac.uk
CONTACT:Ekaterina Kochmar
DESCRIPTION:Many problems in NLP\, and structured prediction in general\, 
 can be cast as\nfinding high-scoring structures based on a large set of ca
 ndidate parts.\nFor example\, in second order tagging\, we have to select 
 high-scoring\ntransitions between tags in a globally consistent fashion. I
 n second order\ngraph-based dependency parsing we have to choose a quadrat
 ic number of\nfirst order and a cubic number of second order edges such th
 at the graph is\nboth high-scoring and a tree. What makes such problems ch
 allenging is the\nlarge number of possible parts to consider. This number 
 not only affects\nthe cost of search or optimization but also slows down t
 he process of\nscoring parts before they enter the optimisation problem\, 
 and extracting\nfeatures.\n\nIn this talk I present an approach that can s
 olve problems with large sets\nof candidate parts without considering all 
 of these parts in either\noptimization or scoring. In contrast to most pru
 ning heuristics\, our\nalgorithm can give certificates of optimality befor
 e having optimized over\,\nor even scored\, all parts. It does so without 
 the need of auxiliary models\nor tuning of threshold parameters. This is a
 chieved by a delayed column and\nrow generation algorithm that iteratively
  solves an LP relaxation over a\nsmall subset of current candidate parts\,
  and then finds new candidates with\nhigh scores that can be inserted into
  the current optimal solution without\nremoving high scoring existing stru
 cture. The latter step subtracts from\nthe cost of a part the price of res
 ources the part requires\, and is often\nreferred as pricing. Sometimes pa
 rts may score highly after pricing\, but\nare necessary in order to make t
 he current solution feasible. We add such\nparts in a step that roughly am
 ounts to violated cuts to the LP.\n\nWe evaluate our approach on two appli
 cations: second order dependency\nparsing and first order tagging with lar
 ge domains. In both cases we\ndramatically reduce the number of parts cons
 idered\, and observe about an\norder of magnitude speed-up. This is possib
 le without loss of optimality\nguarantees\, and hence accuracy.
LOCATION:FW26\, Computer Laboratory
END:VEVENT
END:VCALENDAR