Expected Sequence Similarity Maximization

Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the ACL, pages 957–965, Los Angeles, California, June 2010. c⃝2010 Association for Computational Linguistics Expected Sequence Similarity Maximization Cyril Allauzen1, Shankar Kumar1, Wolfgang Macherey1, Mehryar Mohri2,1 and Michael Riley1 1Google Research, 76 Ninth Avenue, New York, NY 10011 2Courant Institute of Mathematical Sciences, 251 Mercer Street, New York, NY 10012 Abstract This paper presents efficient algorithms for expected similarity maximization, which co- incides with minimum Bayes decoding for a similarity-based loss function. Our algorithms are designed for similarity functions that are sequence kernels in a general class of posi- tive definite symmetric kernels. We discuss both a general algorithm and a more efficient algorithm applicable in a common unambigu- ous scenario. We also describe the applica- tion of our algorithms to machine translation and report the results of experiments with sev- eral translation data sets which demonstrate a substantial speed-up. In particular, our results show a speed-up by two orders of magnitude with respect to the original method of Tromble et al. (2008) and by a factor of 3 or more even with respect to an approximate algorithm specifically designed for that task. These re- sults open the path for the exploration of more appropriate or optimal kernels for the specific tasks considered. 1 Introduction The output of many complex natural language pro- cessing systems such as information extraction, speech recognition, or machine translation systems is a probabilistic automaton. Exploiting the full in- formation provided by this probabilistic automaton can lead to more accurate results than just using the one-best sequence. Different techniques have been explored in the past to take advantage of the full lattice, some based on the use of a more complex model applied to the automaton as in rescoring, others using addi- tional data or information for reranking the hypothe- ses represented by the automaton. One method for using these probabilistic automata that has been suc- cessful in large-vocabulary speech recognition (Goel and Byrne, 2000) and machine translation (Kumar and Byrne, 2004; Tromble et al., 2008) applications and that requires no additional data or other com- plex models is the minimum Bayes risk (MBR) de- coding technique. This returns that sequence of the automaton having the minimum expected loss with respect to all sequences accepted by the automaton (Bickel and Doksum, 2001). Often, minimizing the loss function L can be equivalently viewed as max- imizing a similarity function K between sequences, which corresponds to a kernel function when it is positive definite symmetric (Berg et al., 1984). The technique can then be thought of as an expected se- quence similarity maximization. This paper considers this expected similarity max- imization view. Since different similarity functions can be used within this framework, one may wish to select the one that is the most appropriate or relevant to the task considered. However, a crucial require- ment for this choice to be realistic is to ensure that for the family of similarity functions considered the expected similarity …

Content truncated to 500 words