Noah Smith, Carnegie Mellon University
Approximate Inference in Natural Language Processing
I'll start out by presenting an idealized version of the natural
language processing problem of parsing. I will brazenly suggest that
most of NLP is reducible to variations on parsing problems. I'll show
how dynamic programming solves the idealized version of the problem,
both for calculating modes and marginals over parse trees, exploiting
some key independence assumptions about the structure of natural
language sentences.
I will then discuss two approximate inference methods that let us build more powerful models of parsing. Neither comes with strong theoretical guarantees, but both are demonstrated to perform strongly in experiments on real NLP data. The first method builds on the dynamic programming representation, combining max-product and sum-product methods to produce, approximately, the k-best parses and a residual sum over the rest of the parses, useful when incorporating features that violate the usual independence assumptions. Experiments validate the approach with a discriminative model for machine translation.
The second method turns a parsing problem instance into a concise
integer linear program. Approximate inference is then accomplished
using well-known linear program relaxation. This is embedded in a
new online learning algorithm that tries to penalize uninterpretable
fractional solutions (and therefore inference cost at evaluation
time). We show that this approach leads to state-of-the-art parsing
performance on seven languages, with improved speed for both exact and
approximate inference and no significant performance loss.
This talk includes joint work with Kevin Gimpel, Andre Martins, and Eric Xing.