Difference between revisions of "McCallum Bellare and Pereira 2005 A Conditional Random Field for Discriminatively-Trained Finite-State String Edit Distance"

From Cohen Courses
Jump to navigationJump to search
Line 57: Line 57:
 
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.
 
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 ===
 
=== Learning ===
 +
The training data consists of string pairs <math> \langle x^{(j)}, y^{(j)}  \rangle </math> with corresponding labels <math>  z^{(j)} \in {1,0}</math>, 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: <math> \Sigma_k \lambda_k^2/\sigma^2</math>
 +
 +
The penalized log likelihood is given by
 +
 +
<math>
 +
\mathcal{L}_C = \sum_j \sum_a \log(p(z^{(j)}|a,x^{(j)},y^{(j)})p(a|x^{(j)},y^{(j)}))
 +
</math>
 +
 +
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

Revision as of 20:09, 29 November 2011

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

Summary

This paper presents a discriminative string edit CRF. Conditional random fields outperform generative models for string edit distance prediction (such as those used in the work of 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 (FST) model with a single start state and two sets of disjoint states, and , representing 'matching' and 'non-matching' string pairs, respectively.

An alignment under this model is a four-tuple

where,

  • . These indicate the sequence of edit-operations for this alignment.

Each edit operation consumes a portion of either one or both of the input strings, up to position or .

  • . This is the non-decreasing positions in the input string x, associated with the edit operations in .
  • . This is the non-decreasing positions in the input string y, associated with the edit operations in .
  • . This is the set of states in the FST models of this alignment. By construction, either (indicating a sequence of match states), or (indicating a sequence of non-match states).


Let , be the -th position in the alignment.


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

where is a normalizer and is the following potential function, parametrized as an exponential of a linear scoring function

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 ( or )

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 with corresponding labels , 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:

The penalized log likelihood is given by

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