Fast Methods for Kernel-Based Text Analysis

Fast Methods for Kernel-based Text Analysis Taku Kudo and Yuji Matsumoto Graduate School of Information Science, Nara Institute of Science and Technology {taku-ku,matsu}@is.aist-nara.ac.jp Abstract Kernel-based learning (e.g., Support Vec- tor Machines) has been successfully ap- plied to many hard problems in Natural Language Processing (NLP). In NLP, al- though feature combinations are crucial to improving performance, they are heuris- tically selected. Kernel methods change this situation. The merit of the kernel methods is that effective feature combina- tion is implicitly expanded without loss of generality and increasing the compu- tational costs. Kernel-based text analysis shows an excellent performance in terms in accuracy; however, these methods are usually too slow to apply to large-scale text analysis. In this paper, we extend a Basket Mining algorithm to convert a kernel-based classifier into a simple and fast linear classifier. Experimental results on English BaseNP Chunking, Japanese Word Segmentation and Japanese Depen- dency Parsing show that our new classi- fiers are about 30 to 300 times faster than the standard kernel-based classifiers. 1 Introduction Kernel methods (e.g., Support Vector Machines (Vapnik, 1995)) attract a great deal of attention re- cently. In the field of Natural Language Process- ing, many successes have been reported. Examples include Part-of-Speech tagging (Nakagawa et al., 2002) Text Chunking (Kudo and Matsumoto, 2001), Named Entity Recognition (Isozaki and Kazawa, 2002), and Japanese Dependency Parsing (Kudo and Matsumoto, 2000; Kudo and Matsumoto, 2002). It is known in NLP that combination of features contributes to a significant improvement in accuracy. For instance, in the task of dependency parsing, it would be hard to confirm a correct dependency re- lation with only a single set of features from either a head or its modifier. Rather, dependency relations should be determined by at least information from both of two phrases. In previous research, feature combination has been selected manually, and the performance significantly depended on these selec- tions. This is not the case with kernel-based method- ology. For instance, if we use a polynomial ker- nel, all feature combinations are implicitly expanded without loss of generality and increasing the compu- tational costs. Although the mapped feature space is quite large, the maximal margin strategy (Vapnik, 1995) of SVMs gives us a good generalization per- formance compared to the previous manual feature selection. This is the main reason why kernel-based learning has delivered great results to the field of NLP. Kernel-based text analysis shows an excellent per- formance in terms in accuracy; however, its inef- ficiency in actual analysis limits practical applica- tion. For example, an SVM-based NE-chunker runs at a rate of only 85 byte/sec, while previous rule- based system can process several kilobytes per sec- ond (Isozaki and Kazawa, 2002). Such slow exe- cution time is inadequate for Information Retrieval, Question Answering, or Text Mining, where fast analysis of large quantities of text is indispensable. This paper presents two novel methods that make the kernel-based text analyzers substantially faster. These methods are applicable not only to the NLP tasks but also to general …

Content truncated to 500 words