A Dynamic Bayesian Framework to Model Context and Memory in Edit Distance Learning: An Application to Pronunciation Classification

Proceedings of the 43rd Annual Meeting of the ACL, pages 338–345, Ann Arbor, June 2005. c⃝2005 Association for Computational Linguistics A Dynamic Bayesian Framework to Model Context and Memory in Edit Distance Learning: An Application to Pronunciation Classification Karim Filali and Jeff Bilmes∗ Departments of Computer Science & Engineering and Electrical Engineering University of Washington Seattle, WA 98195, USA {karim@cs,bilmes@ee}.washington.edu Abstract Sitting at the intersection between statis- tics and machine learning, Dynamic Bayesian Networks have been applied with much success in many domains, such as speech recognition, vision, and compu- tational biology. While Natural Language Processing increasingly relies on statisti- cal methods, we think they have yet to use Graphical Models to their full poten- tial. In this paper, we report on experi- ments in learning edit distance costs using Dynamic Bayesian Networks and present results on a pronunciation classification task. By exploiting the ability within the DBN framework to rapidly explore a large model space, we obtain a 40% reduc- tion in error rate compared to a previous transducer-based method of learning edit distance. 1 Introduction Edit distance (ED) is a common measure of the sim- ilarity between two strings. It has a wide range of applications in classification, natural language processing, computational biology, and many other fields. It has been extended in various ways; for example, to handle simple (Lowrance and Wagner, 1975) or (constrained) block transpositions (Leusch et al., 2003), and other types of block opera- tions (Shapira and Storer, 2003); and to measure similarity between graphs (Myers et al., 2000; Klein, 1998) or automata (Mohri, 2002). ∗This material was supported by NSF under Grant No. ISS- 0326276. Another important development has been the use of data-driven methods for the automatic learning of edit costs, such as in (Ristad and Yianilos, 1998) in the case of string edit distance and in (Neuhaus and Bunke, 2004) for graph edit distance. In this paper we revisit the problem of learn- ing string edit distance costs within the Graphi- cal Models framework. We apply our method to a pronunciation classification task and show sig- nificant improvements over the standard Leven- shtein distance (Levenshtein, 1966) and a previous transducer-based learning algorithm. In section 2, we review a stochastic extension of the classic string edit distance. We present our DBN- based edit distance models in section 3 and show re- sults on a pronunciation classification task in sec- tion 4. In section 5, we discuss the computational aspects of using our models. We end with our con- 2clusions and future work in section 6. Stochastic Models of Edit Distance Let sm 1 = s1s2...sm be a source string over a source alphabet A, and m the length of the string. sj i is the substring si...sj and sj i is equal to the empty string, ϵ, when i > j. Likewise, tn 1 denotes a target string over a target alphabet B, and n the length of tn 1. A source string can be transformed into a target string through a sequence …

Content truncated to 500 words