View source for Ristad and Yianilos 1997 Learning String Edit Distance

== Citation ==

Ristad, E.S. and Yianilos, P.N. Learning string-edit distance. IEEE Transactions on Pattern Analysis and Machine Intelligence, 20: 522--532, 1998.

== Online ==

* [http://pnylab.com/pny/papers/sed/main.html Paper web-site] by Yianilos.

* [http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=682181 Short PDF version].

* [http://pnylab.com/pny/papers/sed/sed.pdf Full research report].

== Summary ==

In this [[Category::paper]] the authors describe a stochastic [[UsesMethod::HMM | HMM]] model for learning a [[AddressesProblem::String Edit Distance]] function, as well as an efficient [[UsesMethod:: Expectation Maximization | EM]] variant for learning the edit costs. 

The [[AddressesProblem::String Edit Distance]] model is then used to provide a stochastic solution to the problem of [[AddressesProblem::String Classification]], in which the classification is based on the similarity of an observed string, <math>y^v</math> (string of length <math>v</math>), to an underlying prototype, <math>x^t</math> (string of length <math>t</math>), from a class, <math>w</math>. The paper describes an efficient algorithm for inducing a joint probability model, <math>p(w, y^v|L, \phi)</math> where <math>L</math> is a dictionary of prototype strings and <math>\phi</math> is the stochastic model, from a corpus of labeled strings, and this model is used to classify new strings. 

Finally, the authors address the problem of learning [[AddressesProblem::Word Pronunciation]] in conversational speech by reducing it to a classification problem and applying the [[AddressesProblem::String Edit Distance]] model. In this problem, the classes are the set of syntactic words in a language, and similarity is measured between the set of phonological segments of words (these are the prototype strings) and observed phonemes.

== A Stochastic Model for String Edit Distance ==
The distance between the strings <math>A^*</math> and <math>B^*</math> is modeled as a memoryless stochastic transduction (using a [[UsesMethod::Pair HMM | Pair HMM]]) of edit operations, including deletions, insertions, and substitutions (modeling letter-specific transitions for every alphabet letter). Using this model, two distance functions are defined: (1) The '''Viterbi edit distance''' is defined by most likely transduction between two strings, and (2) the '''stochastic edit distance''' is defined by aggregating all transductions between the strings. The paper describes variants of the ''Forward'' and ''Backward'' algorithms as well as an [[UsesMethod::Expectation_Maximization | EM]] variant for learning the parameters of the [[UsesMethod::HMM | HMM]] which represent the costs of the edit operations.

Three types of [[UsesMethod::HMM | HMM]]s are being considered:
* '''Tied''': The model is simplified to contain only four distinct edit costs for insertion, deletion, identity and substitution. Using these parameter equivalence classes is termed "parameter tying".
* '''Mixed''': A <math>k</math>-component mixed transducer is a linear combination of <math>k</math> [[UsesMethod::HMM | HMM]]s, each using a different model (e.g., each model may use a different degree of parameter tying).
* '''Memory''': This is a model using a higher order Markov chain, that is, the probability of future events depends on <math>m</math> past events for some <math>m</math>.

=== Baseline ===

The model is compared with the [http://en.wikipedia.org/wiki/Levenshtein_distance Levenshtein distance] which is the minimum number of edit operations required for the transduction between two strings. Effectively, this is a transformation process in which the cost of identity substitutions is zero and all other edit costs are one.

== Results ==
The experimental evaluations test the use of this approach with all of the suggested models (using '''Tied''', '''Untied''', and '''Mixed''' models, and setting the distance to either the '''Viterbi''' or the '''stochastic''' distance for each of the models). The error rates of the stochastic models are from one half to one sixth the error of using the baseline [http://en.wikipedia.org/wiki/Levenshtein_distance Levenshtein distance]. Over 87 percent of the unseen pronunciations are correctly recognized, which is within 4 percent of the maximum success rate by any classifier.