McCallum Bellare and Pereira 2005 A Conditional Random Field for Discriminatively-Trained Finite-State String Edit Distance

Citation

Andrew McCallum, Kedar Bellare and Fernando Pereira. A Conditional Random Field for Discriminatively-Trained Finite-State String Edit Distance. Conference on Uncertainty in AI (UAI'05), 2005.

Online

• PDF version.

Summary

This paper presents a discriminative string edit CRF. The authors show that conditional random fields outperform generative models for string edit distance prediction (such as the HMM and Pair HMM based methods described in Ristad and Yianilos and Bilenko and Mooney) since they are able to use complex, arbitrary features over the input strings. As in the case of the generative models, this method does not require to specify the edit sequence (alignment) of the training strings, however, it does require negative input instances.

The results show that the CRF approach outperforms the generative models on all but one of the estimated classes.

Method

The model

The CRF presented in this paper is based on a finite state machine (FSM) model with a single start state and two sets of disjoint states, $S_{1}$ and $S_{0}$, representing 'matching' and 'non-matching' string pairs, respectively.

An alignment under this model is a four-tuple

$a=\langle e,ix,jy,q\rangle$

where,

• $e=e_{1},\dots ,e_{k}$. These indicate the sequence of edit-operations for this alignment.

Each edit operation $e_{p}$ consumes a portion of either one or both of the input strings, up to position $i_{p}$ or $j_{p}$.

• $ix=i_{1},\dots ,i_{k}$. These are non-decreasing positions in the input string x, associated with the edit operations in $e$.
• $jy=j_{1},\dots ,j_{k}$. These are non-decreasing positions in the input string y, associated with the edit operations in $e$.
• $q=q_{1},\dots ,q_{k}$. This is the set of states in the FSM model of this alignment. By construction, either $q\subseteq S_{1}$ (indicating a sequence of match states), or $q\subseteq S_{0}$ (indicating a sequence of non-match states).

Let $a_{p}=\langle e_{p},i_{p},j_{p},q_{p}\rangle$, be the $p$-th position in the alignment.

Given the strings x, and y, the probability of an alignment a is given by

$p(\mathbf {a} |\mathbf {x} ,\mathbf {y} )={\frac {1}{Z_{x,y}}}\prod _{i=1}^{|a|}\Phi (a_{i-1},a_{i},\mathbf {x} ,\mathbf {y} )$

where $Z_{x,y}$ is a normalizer and $\Phi$ is the following potential function, parametrized as an exponential of a linear scoring function

$\Phi (a_{i-1},a_{i},\mathbf {x} ,\mathbf {y} )=\exp \Lambda \cdot \mathbf {f} (a_{i-1},a_{i},\mathbf {x} ,\mathbf {y} )$

where f is a vector of feature functions over its arguments.

Inference

The probability of a match (or mismatch) is given by marginalizing over the alignments with states in the corresponding state set ($S_{1}$ or $S_{0}$)

$p(z|\mathbf {x} ,\mathbf {y} )=\sum _{a.q\subseteq S_{z}}{\frac {1}{Z_{x,y}}}\prod _{i=1}^{|a|}\Phi (a_{i-1},a_{i},\mathbf {x} ,\mathbf {y} )$

This is calculated with dynamic programming, to give a Forward-Backward-like match-estimate. Alternatively, a Viterbi estimate can be given by calculating the max-product.

Learning

The training data consists of string pairs $\langle x^{(j)},y^{(j)}\rangle$ with corresponding labels $z^{(j)}\in {1,0}$, indicating a 'match' or 'mismatch' label.

The model parameters are estimated using maximum likelihood with penalization in the form of a zero-mean Gaussian prior: $\Sigma _{k}\lambda _{k}^{2}/\sigma ^{2}$

The penalized log likelihood is given by

${\mathcal {L}}_{C}=\sum _{j}\sum _{a}\log(p(z^{(j)}|a,x^{(j)},y^{(j)})p(a|x^{(j)},y^{(j)}))$

This is maximized using EM , and the M-step uses BFGS for optimization.

The initial model parameters are manually-tuned in order to avoid local-maxima.

Results

The results of this work are compared with the results of Bilenko and Mooney over six data sets. The CRF outperforms the previously used generative model in 5 out of 6 cases. Additionally, in all but one of the datasets, using the Forward-Backward alignment score has been shown to outperform the Viterbi alignment score.