Bilenko and Mooney 2003 Adaptive duplicate detection using learnable string similarity measures

... Under construction by Dana Movshovitz-Attias

Citation

Bilenko, M. and Mooney, R.J., Adaptive duplicate detection using learnable string similarity measures.Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pp.39--48, 2003.

Online

• PDF version.

Summary

This paper addresses the problem of Duplicate Document Detection by using string similarity measures. In contrast to previous methods that used generic or manually tuned distance metrics, in this paper, the authors suggest using learnable (trainable) text distance functions and training a specific function for different data fields. Such specialized function can capture a unique notion of similarity as is relevant for the specific data represented by a specific field.

Two similarity metrics are suggested:

1. The first extends the String Edit Distance as suggested by Ristad and Yianilos to include affine gaps.
2. The second metric measures similarity based on unordered bags of words, using an SVM for training.

Methods used

String edit distance with affine gap

The first method extends the String Edit Distance measure suggested by Ristad and Yianilos with an affine gap model, inspired by Needleman and Wunsch. In the affine model:

$cost(g)=s+e*l$

where $s$ is the cost of opening a gap, $e$ is the cost of extending the gap and $l$ is the gap length.

The formulation follows directly from Ristad and Yianilos, modeling the string edit distance as an alignment problem. The affine-gap alignment is modeled as a stochastic transducer with four states: (1) $M$, represents a match (or substitution between characters), (2) $D$, represents a deletion, (3) $I$, represents an insertion, and (4) $\#$, represents the end of the alignment.

This model successfully represents pairs of short strings with minor local variations, but is not as useful for longer strings.

Vector space similarity

The second measure attempts to capture the relative importance of tokens and so to capture more global variations between long strings. In this model, a pair of strings, $x$ and $y$ is represented by a vector, $p$, of unordered bags of words with TF-IDF based weights.

$p_{i}^{(x,y)}={\frac {x_{i}y_{i}}{||x||\cdot ||y||}}$