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

• Paper web-site by Yianilos.

• Short PDF version.

• Full research report.

Summary

In this paper the authors describe a stochastic model (HMM) for learning a String Edit Distance function, as well as an efficient EM variant for learning edit costs. The authors then present a stochastic solution to String Classification, in which the classification is based on the similarity of an observed string, $y^{v}$, to an underlying prototype, $x^{t}$, from a class, $w$. The paper describes an efficient algorithm for inducing a joint probability model $p(w,y^{v}|L,\phi )$ from a corpus, and this model is used to classify new strings. Finally, the described techniques are applied to the problem of learning Word Pronunciation in conversational speech.