Predict, Price and Cut: Column and Row Generation for Structured Prediction

Add to your list(s) Download to your calendar using vCal

• Sebastian Riedel, University College London
• Friday 16 November 2012, 12:00-13:00
• FW26, Computer Laboratory.

If you have a question about this talk, please contact Ekaterina Kochmar.

Many problems in NLP , and structured prediction in general, can be cast as finding high-scoring structures based on a large set of candidate parts. For example, in second order tagging, we have to select high-scoring transitions between tags in a globally consistent fashion. In second order graph-based dependency parsing we have to choose a quadratic number of first order and a cubic number of second order edges such that the graph is both high-scoring and a tree. What makes such problems challenging is the large number of possible parts to consider. This number not only affects the cost of search or optimization but also slows down the process of scoring parts before they enter the optimisation problem, and extracting features.

In this talk I present an approach that can solve problems with large sets of candidate parts without considering all of these parts in either optimization or scoring. In contrast to most pruning heuristics, our algorithm can give certificates of optimality before having optimized over, or even scored, all parts. It does so without the need of auxiliary models or tuning of threshold parameters. This is achieved by a delayed column and row generation algorithm that iteratively solves an LP relaxation over a small subset of current candidate parts, and then finds new candidates with high scores that can be inserted into the current optimal solution without removing high scoring existing structure. The latter step subtracts from the cost of a part the price of resources the part requires, and is often referred as pricing. Sometimes parts may score highly after pricing, but are necessary in order to make the current solution feasible. We add such parts in a step that roughly amounts to violated cuts to the LP.

We evaluate our approach on two applications: second order dependency parsing and first order tagging with large domains. In both cases we dramatically reduce the number of parts considered, and observe about an order of magnitude speed-up. This is possible without loss of optimality guarantees, and hence accuracy.

This talk is part of the NLIP Seminar Series series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge Centre for Data-Driven Discovery (C2D3)
• Cambridge Forum of Science and Humanities
• Cambridge Language Sciences
• Cambridge talks
• Chris Davis' list
• Department of Computer Science and Technology talks and seminars
• FW26, Computer Laboratory
• Graduate-Seminars
• Guy Emerson's list
• Interested Talks
• Language Sciences for Graduate Students
• NLIP Seminar Series
• PMRFPS's
• Simon Baker's List
• Trust & Technology Initiative - interesting events
• bld31
• ndk22's list
• ob366-ai4er
• rp587

Note that ex-directory lists are not shown.