A Sequence Alignment Model Based on the Averaged Perceptron

Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pp. 238–247, Prague, June 2007. c⃝2007 Association for Computational Linguistics A Sequence Alignment Model Based on the Averaged Perceptron Dayne Freitag Fair Isaac Corporation 3661 Valley Centre Drive San Diego, CA 92130, USA DayneFreitag@fairisaac.com Shahram Khadivi Lehrstuhl f¨ur Informatik 6 Computer Science Department RWTH Aachen University D-52056 Aachen, Germany khadivi@cs.rwth-aachen.de Abstract We describe a discriminatively trained se- quence alignment model based on the av- eraged perceptron. In common with other approaches to sequence modeling using per- ceptrons, and in contrast with comparable generative models, this model permits and transparently exploits arbitrary features of input strings. The simplicity of perceptron training lends more versatility than compa- rable approaches, allowing the model to be applied to a variety of problem types for which a learned edit model might be useful. We enumerate some of these problem types, describe a training procedure for each, and evaluate the model’s performance on sev- eral problems. We show that the proposed model performs at least as well as an ap- proach based on statistical machine transla- tion on two problems of name translitera- tion, and provide evidence that the combina- tion of the two approaches promises further improvement. 1 Introduction Sequence alignment is a problem that crops up in many forms, both in computational linguistics (CL) and in other endeavors. The ability to find an op- timal alignment between two sequences has found application in a number of areas of CL, includ- ing phonetic modeling (Ristad and Yianilos, 1998), name transcription (Huang et al., 2004), and dupli- cate detection or information integration (Bilenko and Mooney, 2003; McCallum et al., 2005). Se- quence alignment is a member of a broader class of problems which we might call sequence transduc- tion, to which one of the core CL challenges, ma- chine translation, belongs. Under the assumption that one string (the target) is produced through a series of local edits to another string (the source), and given an edit cost matrix, the optimal sequence of edits can be efficiently com- puted through dynamic programming (Needleman and Wunsch, 1970). While the cost matrix tradition- ally has been set by hand, several recent papers have proposed determining edit costs empirically. These proposals arise from a variety of learning paradigms, including generative models (Ristad and Yianilos, 1998; Bilenko and Mooney, 2003), conditional ran- dom fields (McCallum et al., 2005), maximum- margin methods (Joachims, 2003), and gradient boosting (Parker et al., 2006). While approaches based on generative models support only limited fea- ture engineering, discriminative approaches share the advantage of allowing arbitrary features of the input sequences. We describe a new sequence alignment model based on the averaged perceptron (Collins, 2002), which shares with the above approaches the ability to exploit arbitrary features of the input sequences, but is distinguished from them by its relative sim- plicity and the incremental character of its training procedure. The fact that it is an online algorithm makes it …

Content truncated to 500 words