Integer Programming for NLP
Speaker: James Clarke
Institution: University of Edinburgh
Abstract:
Many natural language processing tasks, such as machine translation, parsing and generation; require a decoding algorithm to find the best solution for a given input and probabilistic model. The decoding problem is also referred to as the inference or search problem. Ideally during decoding we should find the optimal solution in an efficient manner. However, many decoding algorithms find sub-optimal solutions or force us to make strong assumptions of conditional independence between variables. Formulating decoding as an integer program allows us to infer globally optimal solutions and enforce global constraints.
In this talk we give an introduction to the concepts, formulation and solving of integer programs. We demonstrate how integer programming can be used for decoding in two applications: sentence compression and dependency parsing. Our approach can yield state-of-the-art or better performance by introducing linguistically motivated constraints that allow us to model the global properties observed in language.