Integer Linear Programming formulations in Natural Language Processing
Tutorial: Integer Linear Programming formulations in Natural Language Processing
Presenters: Dan Roth and Vivek Srikumar
Making decisions in natural language processing problems often involves assigning values to sets of interdependent variables where the expressive dependency structure can influence, or even dictate what assignments are possible. This setting includes a broad range of structured prediction problems such as semantic role labeling, named entity and relation recognition, co-reference resolution, dependency parsing and semantic parsing. The setting is also appropriate for cases that may require making global decisions that involve multiple components, possibly pre-designed or pre-learned, as in event recognition and analysis, summarization, paraphrasing, textual entailment and question answering. In all these cases, it is natural to formulate the decision problem as a constrained optimization problem, with an objective function that is composed of learned models, subject to domain or problem specific constraints.
Over the last few years, starting with a couple of papers written by (Roth & Yih, 2004, 2005), dozens of papers have been using the Integer linear programming (ILP) formulation developed there, including several award-winning papers (e.g., (Martins, Smith, & Xing, 2009; Koo, Rush, Collins, Jaakkola, & Sontag., 2010; Berant, Dagan, & Goldberger, 2011)).
This tutorial will present the key ingredients of ILP formulations of natural language processing problems, aiming at guiding readers through the key modeling steps, explaining the learning and inference paradigms and exemplifying these by providing examples from the literature. We will cover a range of topics, from the theoretical foundations of learning and inference with ILP models, to practical modeling guides, to software packages and applications.
The goal of this tutorial is to introduce the computational framework to broader ACL community, motivate it as a generic framework for learning and inference in global NLP decision problems, present some of the key theoretical and practical issues involved and survey some of the existing applications of it as a way to promote further development of the framework and additional applications. We will also make connections with some of the “hot” topics in current NLP research and show how they can be used within the general framework proposed here. The tutorial will thus be useful for many of the senior and junior researchers that have interest in global decision problems in NLP, providing a concise overview of recent perspectives and research results.
After briefly motivating and introducing the general framework, the main part of the tutorial is a methodological presentation of some of the key computational issues studied in this area, that we will present by looking at case studies published in the NLP literature.
We will begin by introducing structured prediction with various NLP examples. We will motivate the framework of Constrained Conditional Models using examples from sequential inference, sentence compression and semantic role labeling.
- Applications of ILP Formulations in Natural Language Processing
Examples will be used to explain several of the key properties the framework offers. In particular, we will discuss several ways in which expressive constraints can be introduced into an application.
- Co-reference resolution
- Sentence compression
- Information extraction
- Modeling: Inference methods and Constraints
- Modeling problems as structured prediction problems
- The use of hard and soft constraints to represent prior knowledge.
- Augmenting Probabilistic Models with declarative constraints.
- Inference Algorithms
- Lagrangian Relaxation
- Existing Packages
- Training Paradigms
- Structured learning
- Decomposed learning
- Constraints Driven Learning
- Semi-supervised Learning with Constraints
- Constrained Expectation Maximization
- Learning with Indirect Supervision
- Developing ILP based Applications
- A “template-based” approach” for developing applications with ILP formulations
- Future work
- ILP Formulations in the NN era.
Computer Science Department, University of Illinois at Urbana-Champaign, IL, 61801
Dan Roth is the Founder Professor of Engineering in the Department of Computer Science at the University of Illinois at Urbana-Champaign and the Beckman Institute of Advanced Science and Technology (UIUC). He is a fellow of the AAAS, ACM, AAAI and the ACL. Roth has published broadly in machine learning, natural language processing, knowledge representation and reasoning and received several paper, teaching and research awards. He has developed several machine learning based natural language processing systems that are widely used in the computational linguistics community and in industry and was the program chair for a number of major conferences, including ACL and AAAI. Roth is currently the Editor-in-Chief of the Journal of Artificial Intelligence Research (JAIR). Roth has given tutorials on these and other topics in all NLP and AI major conferences.
School of Computing, University of Utah
50 Central Campus Dr, Salt Lake City, UT 84112
Vivek Srikumar is an Assistant Professor in the School of Computing at the University of Utah. His research interests are in the areas of machine learning and natural language processing, particularly in the context of structured learning and prediction. Recently, he has been working on problems related to predicting semantic representations of text, structured learning from limited supervision and scaling inference. He has given multiple tutorials in major conferences such as AAAI and NAACL on predicting NLP structures.