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 $22^{nd}$ International Conference on Machine learning, ICML'05, New York, NY, USA.

Online Version

Online version

Summary

This paper presents an alternative approach to inference in conditional random fields using 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 method is able to take into account these constraints more efficiently.

Conditional Random Field

A standard CRF model is represented by:

$P_{\lambda }(y|x)={\frac {\exp(\lambda \cdot F(y,x)}{Z_{\lambda }(x)}}$

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

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

$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})]$

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 $G=(V,E)$, two distinct nodes $s,t\in V$, and a non-negative cost $c_{uv}$ of each edge $(u,v)\in E$, a minimum cost path from $s$ to $t$ is desired. For each edge $(u,v)\in E$, an indicator variable $x_{uv}$ is introduced. If $(u,v)$ is in the minimum cost (shortest) path, then $x_{uv}$ is set to 1; otherwise, it is 0. The cost function is, $\sum _{(u,v)\in E}c_{uv}\cdot x_{uv}$ .

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

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

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 $i$ to be 0:

$\sum _{0\leq y\leq m-1}x_{i,y_{0}}=1$

Example 2

There is no "duplication" of segments in a sequence:

where, the indicator variable $x_{i,ab}$ represents the antecedent.

Example 3

If label $a$ appears, then label $b$ must also appear:

for all $i$ such that, $0\leq i\leq n-1$.

Example 4

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

$v_{i,y}=\sum _{0\leq y^{\prime }\leq m-1}x_{i,y^{\prime }y}$ ,

$(q-p)v_{p,l}\leq \sum _{p+1\leq i\leq q}v_{i,l}$

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

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: