Integer Linear Programming for Natural Language Processing (Integer lineair programmeren voor natuurlijke taalverwerking)

The field of natural language processing has made great advances in thelast decades. Most of us have used Google translate, and have heard of Watson, the computer that won Jeopardy! Luckily, there are still many open problems in natural language processing, specifically with the machine learning algorithms behind it. A first problem is the training data. Most algorithms are supervised, and require annotated training data to learn from. This data has to be manually annotated, which is often an expensive and time consuming task. Therefore, there is a significant interest in weakly supervised and unsupervised methods, that learnwith less or no annotated data. A second problem is the computational complexity of the algorithms. Often approximate algorithms have to be used, leading to sub-optimal results. Especially methods that use little supervision tend to be very complex. In this thesis, we approach these two problems from an optimization point of view. By leveragingdecades of advances in the field of mathematical optimization, we are able to solve several natural language processing problems in an effective and efficient way. More specifically, we formulate the problems as constrained optimization problems, using integer linear programming. This allows us to find a globally optimal solution, and it allows us to encodeadditional knowledge through the use of constraints. We apply this strategy to several natural language processing problems, both on sentence level as on document level. On the sentence level we focus on sentence compression. We not only develop state-of-the-art methods, but also contribute by annotating data and comparing evaluation measures. On a document level we develop methods for rhetorical role classification, coreference resolution, and document simplification. Although these can all be solved as traditional classification problems, we develop methods that find a globally optimal solution. These methods are computationally more intensive, but we find efficient ways of solving them, by building on decades of research in the field of optimization theory. By efficiently finding a globally optimal solution we are able to outperform the current state of the art in many aspects.status: publishe