Abstract

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.