A Discriminative Candidate Generator for String Transformations

Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing, pages 447–456, Honolulu, October 2008. c⃝2008 Association for Computational Linguistics A Discriminative Candidate Generator for String Transformations Naoaki Okazaki† okazaki@is.s.u-tokyo.ac.jp Yoshimasa Tsuruoka‡ yoshimasa.tsuruoka@manchester.ac.uk Sophia Ananiadou‡ sophia.ananiadou@manchester.ac.uk Jun’ichi Tsujii†‡ tsujii@is.s.u-tokyo.ac.jp †Graduate School of Information Science and Technology University of Tokyo 7-3-1 Hongo, Bunkyo-ku Tokyo 113-8656, Japan ‡School of Computer Science, University of Manchester National Centre for Text Mining (NaCTeM) Manchester Interdisciplinary Biocentre 131 Princess Street, Manchester M1 7DN, UK Abstract String transformation, which maps a source string s into its desirable form t∗, is related to various applications including stemming, lemmatization, and spelling correction. The essential and important step for string trans- formation is to generate candidates to which the given string s is likely to be transformed. This paper presents a discriminative approach for generating candidate strings. We use sub- string substitution rules as features and score them using an L1-regularized logistic regres- sion model. We also propose a procedure to generate negative instances that affect the de- cision boundary of the model. The advantage of this approach is that candidate strings can be enumerated by an efficient algorithm be- cause the processes of string transformation are tractable in the model. We demonstrate the remarkable performance of the proposed method in normalizing inflected words and spelling variations. 1 Introduction String transformation maps a source string s into its destination string t∗. In the broad sense, string trans- formation can include labeling tasks such as part- of-speech tagging and shallow parsing (Brill, 1995). However, this study addresses string transformation in its narrow sense, in which a part of a source string is rewritten with a substring. Typical applications of this task include stemming, lemmatization, spelling correction (Brill and Moore, 2000; Wilbur et al., 2006; Carlson and Fette, 2007), OCR error correc- tion (Kolak and Resnik, 2002), approximate string matching (Navarro, 2001), and duplicate record de- tection (Bilenko and Mooney, 2003). Recent studies have formalized the task in the dis- criminative framework (Ahmad and Kondrak, 2005; Li et al., 2006; Chen et al., 2007), t∗ = argmax t∈gen(s) P(t|s). (1) Here, the candidate generator gen(s) enumerates candidates of destination (correct) strings, and the scorer P(t|s) denotes the conditional probability of the string t for the given s. The scorer was modeled by a noisy-channel model (Shannon, 1948; Brill and Moore, 2000; Ahmad and Kondrak, 2005) and max- imum entropy framework (Berger et al., 1996; Li et al., 2006; Chen et al., 2007). The candidate generator gen(s) also affects the accuracy of the string transformation. Previous stud- ies of spelling correction mostly defined gen(s), gen(s) = {t | dist(s, t) < δ}. (2) Here, the function dist(s, t) denotes the weighted Levenshtein distance (Levenshtein, 1966) between strings s and t. Furthermore, the threshold δ requires the distance between the source string s and a can- didate string t to be less than δ. The choice of dist(s, t) and δ involves a tradeoff between the precision, recall, and training/tagging speed of …

Content truncated to 500 words