A Discriminative Model of Stochastic Edit Distance in the form of a Conditional Transducer

Abstract : Many real-world applications such as spell-checking or DNA analysis use the Levenshtein edit-distance to compute similarities between strings. In practice, the costs of the primitive edit operations (insertion, deletion and substitution of symbols) are generally hand-tuned. In this paper, we propose an algorithm to learn these costs. The underlying model is a probabilitic transducer, computed by using grammatical inference techniques, that allows us to learn both the structure and the probabilities of the model. Beyond the fact that the learned transducers are neither deterministic nor stochastic in the standard terminology, they are conditional, thus independant from the distributions of the input strings. Finally, we show through experiments that our method allows us to design cost functions that depend on the string context where the edit operations are used. In other words, we get kinds of \textit{context-sensitive} edit distances.
Document type :
Conference papers
Complete list of metadatas

Cited literature [12 references]  Display  Hide  Download

https://hal-ujm.archives-ouvertes.fr/ujm-00109698
Contributor : Marc Bernard <>
Submitted on : Friday, November 17, 2006 - 8:55:35 AM
Last modification on : Wednesday, July 25, 2018 - 2:05:30 PM
Long-term archiving on : Saturday, May 14, 2011 - 12:24:08 AM

Identifiers

  • HAL Id : ujm-00109698, version 1

Collections

Citation

Marc Bernard, Jean-Christophe Janodet, Marc Sebban. A Discriminative Model of Stochastic Edit Distance in the form of a Conditional Transducer. 8th International Colloquium on Grammatical Inference, Sep 2006, Tokyo, Japan. pp.240-252. ⟨ujm-00109698⟩

Share

Metrics

Record views

226

Files downloads

294