Constrained conditional model

Making decisions in many domains (such as natural language processing and computer vision problems) often involves assigning values to sets of interdependent variables where the expressive dependency structure can influence, or even dictate, what assignments are possible. These settings are applicable not only to Structured Learning problems such as semantic role labeling, but also for cases that require making use of multiple pre-learned components, such as summarization, 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.

Constrained conditional models form a learning and inference framework that augments the learning of conditional (probabilistic or discriminative) models with declarative constraints (written, for example, using a first-order representation) as a way to support decisions in an expressive output space while maintaining modularity and tractability of training and inference. These constraints can express either hard restrictions, completely prohibiting some assignments, or soft restrictions, penalizing unlikely assignments. In most applications of this framework in NLP, following,[1] Integer Linear Programming (ILP) was used as the inference framework, although other algorithms can be used for that purpose.

Given a set of feature functions ${\displaystyle \{\phi _{i}(x,y)\}}$ and a set of constraints ${\displaystyle \{C_{i}(x,y)\}}$, defined over an input structure ${\displaystyle x\in X}$ and an output structure ${\displaystyle y\in Y}$, a constraint conditional model is characterized by two weight vectors, w and ${\displaystyle \rho }$, and is defined as the solution to the following optimization problem:

${\displaystyle argmax_{y}\sum _{i}w_{i}\phi _{i}(x,y)-\sum \rho _{i}C_{i}(x,y)}$.

Each constraint ${\displaystyle C_{i}\in C}$ is a boolean mapping indicating if the joint assignment ${\displaystyle (x,y)}$ violates a constraint, and ${\displaystyle \rho }$ is the penalty incurred for violating the constraints. Constraints assigned an infinite penalty are known as hard constraints, and represent unfeasible assignments to the optimization problem.

The advantages of the CCM declarative formulation and the availability of off-the-shelf solvers have led to a large variety of natural language processing tasks being formulated within the framework, including semantic role labeling,[7] syntactic parsing,[8] coreference resolution,[9] summarization,[10][11][12] transliteration,[13] natural language generation[14] and joint information extraction.[15][16]

Most of these works use an integer linear programming (ILP) solver to solve the decision problem. Although theoretically solving an Integer Linear Program is exponential in the size of the decision problem, in practice using state-of-the-art solvers and approximate inference techniques [17] large scale problems can be solved efficiently.

The key advantage of using an ILP solver for solving the optimization problem defined by a constrained conditional model is the declarative formulation used as input for the ILP solver, consisting of a linear objective function and a set of linear constraints.

• CCM Tutorial Predicting Structures in NLP: Constrained Conditional Models and Integer Linear Programming in NLP

• University of Illinois Cognitive Computation Group
• Workshop on Integer Linear Programming for Natural Language Processing, NAACL-2009