Learning string-edit distance
Eric Sven Ristad, P.N. Yianilos · IEEE Transactions on Pattern Analysis and Machine Intelligence · 1998
In many applications, it is necessary to determine the similarity of two strings. A widely-used notion of string similarity is the edit distance: the minimum number of insertions, deletions, and substitutions required to transform one string into the other. In this report, we provide a stochastic model for string-edit distance. Our stochastic model allows us to learn a string-edit distance function from a corpus of examples. We illustrate the utility of our approach by applying it to the difficult problem of learning the pronunciation of words in conversational speech. In this application, we learn a string-edit distance with nearly one-fifth the error rate of the untrained Levenshtein distance. Our approach is applicable to any string classification problem that may be solved using a similarity function against a database of labeled prototypes.
Cited by 859 works. doi:10.1109/34.682181
Authors
References
- Maximum Likelihood from Incomplete Data Via the EM Algorithm
- Error bounds for convolutional codes and an asymptotically optimum decoding algorithm
- The viterbi algorithm
- Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison
- A Maximization Technique Occurring in the Statistical Analysis of Probabilistic Functions of Markov Chains
- The String-to-String Correction Problem
- An inequality with applications to statistical estimation for probabilistic functions of Markov processes and to a model for ecology
- Binary codes capable of correcting deletions, insertions and reversals
- Interpolated estimation of Markov source parameters from sparse data
- Mixture Densities, Maximum Likelihood and the EM Algorithm