View source for Roth and Yih, ICML 2005. Integer Linear Programming Inference for Conditional Random Fields

== Citation ==
Dan Roth and Wen-tau Yih. 2005. Integer Linear Programming Inference for Conditional Random Fields. In ''Proceedings of the <math> 22^{nd} </math> International Conference on Machine learning'', ICML'05, New York, NY, USA.

== Online Version ==
[http://research.microsoft.com/pubs/73694/RothYi05.pdf Online version]

== Summary ==
This [[Category::paper]] presents an alternative approach to inference in [[UsesMethod::Conditional Random Fields | conditional random fields]] using [[UsesMethod::Integer Linear Programming  | integer linear programming]] (ILP). The standard Viterbi algorithm based on dynamic programming, in general, cannot efficiently incorporate non-local and non-sequential constraints over the output sequence. The authors propose an ILP-based method to inference procedure. and extend CRF models to naturally and efficiently support general constraint structures. For sequential constraints, this procedure reduces to simple linear programming as the inference process.

== Method ==
The efficiency of the CRF approach heavily depends on its Markov property – given the observation, the label of a token is assumed to depend only on the labels of its adjacent tokens. It is difficult to explicitly model and exploit more general constraints such as long distance dependencies keeping in mind the Markovian assumption. This is a problem not only for training CRFs but also for incorporating additional constraints during inference. Viterbi algorithm can handle some of these constraints, but cannot handle more generic constraints. This [[UsesMethod::Integer Linear Programming | method]] is able to take into account these constraints more efficiently.

=== Conditional Random Field ===
A standard [[UsesMethod:: Conditional Random Fields | CRF]] model is represented by:

<math>
P_{\lambda}(y|x) = \frac {\exp (\lambda \cdot F(y,x)} {Z_{\lambda}(x)}
</math>


where <math> F(y,x) </math> is the global feature vector, <math> \lambda </math> is weight vector, and <math> Z_{\lambda}(x) = \sum(\lambda \cdot F(y,x)) </math> is a normalization factor.


A CRF is trained by maximizing the conditional log-likelihood of a given training set 
<math>
T = \{ (x_{k}, y_{k}) \}^{N}_{k=1}
</math> :

<math>
L_{\lambda} = \sum_{k} \log (p_{\lambda} (y_k | x_k)) = \sum_{k} [\lambda \cdot F(y_k,x_k) - \log Z_{\lambda}(x_k)]
</math>


=== Inference Using ILP ===
Inference in CRFs is usually performed by the Viterbi algorithm which takes into account the shortest path from start to the end. The weights on the edges of the path determine the global path of the cost. This weight or ''log score'' is obtained from a linear combination of feature functions and the weight vector.

This approach is represented in ILP as follows:

Given a directed graph <math> G = (V,E) </math>, two distinct nodes <math> s, t \in V </math>, and a non-negative cost <math> c_{uv} </math> of each edge <math> (u,v) \in E </math>, a minimum ''cost'' path from <math> s </math> to <math> t </math> is desired. For each edge <math> (u,v) \in E </math>, an indicator variable <math> x_{uv} </math> is introduced. If <math> (u,v) </math> is in the minimum cost (shortest) path, then <math> x_{uv} </math> is set to 1; otherwise, it is 0. The cost function is, <math> \sum_{(u,v) \in E} c_{uv} \cdot x_{uv} </math> .

The following figure depicts ILP-based representation of CRFs subject to a set of constraints:

[[File:CRF-ILP.jpg]]


where, <math> - \log M_i(y,y^{\prime}) </math> is the cost function. Hence, <math> min </math> changes to <math> max </math> . The start and end nodes are denoted by <math> -1 </math> and <math> n </math> respectively, and <math> n, m </math> represent the sequence length and number of possible labels. Variable <math> x_{i,yy^{\prime}} </math> represents the edge from <math> y </math> to <math> y^{\prime} </math>.

=== Constraint Representation Using ILP ===

The set of constraints in the output space can be expressed using a set of Boolean functions. The authors lay down some example constraints in their model:

==== Example 1 ====
To force the output of label <math> i </math> to be 0:

<math> \sum_{0 \leq y \leq m-1} x_{i,y_0} = 1 </math>

==== Example 2 ====
There is no "duplication" of segments in a sequence:

[[File:CRF-ILP-Example-2.jpg]]


where, the indicator variable <math> x_{i,ab} </math> represents the antecedent.

==== Example 3 ====
If label <math> a </math> appears, then label <math> b </math> must also appear:

[[File:CRF-ILP-Example-3.jpg]]

for all <math> i </math> such that, 
<math>
0 \leq i \leq n-1
</math>.

==== Example 4 ====

When a segment \mathcal{A} of tokens share the same label. So, for every such segment from <math> p </math> to <math> q </math>:

<math>
v_{i,y} = \sum_{0 \leq y^{\prime} \leq m-1 } x_{i,y^{\prime}y}
</math> , 

<math>
(q - p)v_{p,l} \leq \sum_{p+1 \leq i \leq q} v_{i,l}
</math>


for all <math> l </math> such that, <math> 0 \leq l \leq m-1 </math> . <math> v_{i,y} </math> is a binary variable that indicates whether token <math> i </math> is assigned label <math> y </math>.

==== Example 5 ====
If each sequence has at least one segment of interest, i.e., some label other than "O" in BIO representation must be present:

[[File:CRF-ILP-Example-5.jpg]]


All constraints except example 1 have long distance dependencies and cannot be captured by the Viterbi algorithm during inference time. But ILP techniques can represent these constraints efficiently.

== Experiments and Results ==

This approach was tested on the important NLP task of [[AddressesProblem::semantic role labeling]] (SRL). The authors used the following constraints in their model to perform the task:

* No duplicate argument labels in a sentence.
* Argument-level i.e., chunk-level candidate information.
* At least one argument for a verb in a sentence.
* Known verb position.
* Disallowing certain arguments in the structure based on verb frames.

In this framework only the last two constraints can be incorporated in the Viterbi algorithm used for decoding.

=== Dataset ===
* The method was trained on 15-18 sections of the [[UsesDataset::PropBank]] and tested on section 20.
* The authors included Arg0,...,Arg5 in their evaluation.

=== Results ===
Results were reported using two SRL systems using CRF models. The first system was trained using the maximum log-likelihood approach (Quasi-Newton optimization algorithm, [[UsesMethod::L-BFGS | LBFGS]]; with Gaussian prior <math> \sigma^{2} </math> = 0.01). The second CRF-based system was trained using the discriminative method based on voted perceptron, suggested by [[RelatedPaper::Sha 2003 Shallow Parsing with Conditional Random Fields | Sha and Pereira, 2003]].


[[File:results1.jpg]]


Table 1 shows the performance in recall, precision and F-measure. It can be observed from the table that these general constraints improve the results with statistically significant gains for both CRF training algorithms.

== Related Papers ==
1. Kristjannson, T., Culotta, A., Viola, P., & McCallum, A. 2004. Interactive information extraction with constrained conditional random fields. In ''Proceedings of AAAI-2004''

[[RelatedPaper::Lafferty 2001 Conditional Random Fields | 2. Lafferty, J., McCallum, A., & Pereira, F. 2001. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In ''Proceedings of ICML-2001'']]

3. Punyakanok, V., Roth, D., Yih, W., & Zimak, D. 2004. Semantic role labeling via integer linear programming inference. In ''Proceedings of COLING-2004''