Paper: Expected Sequence Similarity Maximization

ACL ID N10-1139
Title Expected Sequence Similarity Maximization
Venue Human Language Technologies
Session Main Conference
Year 2010

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 approx...