Polynomial to Linear: Efficient Classification with Conjunctive Features

Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing, pages 1542–1551, Singapore, 6-7 August 2009. c⃝2009 ACL and AFNLP Polynomial to Linear: Efficient Classification with Conjunctive Features Naoki Yoshinaga Institute of Industrial Science University of Tokyo 4-6-1 Komaba, Meguro-ku, Tokyo ynaga@tkl.iis.u-tokyo.ac.jp Masaru Kitsuregawa Institute of Industrial Science University of Tokyo 4-6-1 Komaba, Meguro-ku, Tokyo kitsure@tkl.iis.u-tokyo.ac.jp Abstract This paper proposes a method that speeds up a classifier trained with many con- junctive features: combinations of (prim- itive) features. The key idea is to pre- compute as partial results the weights of primitive feature vectors that appear fre- quently in the target NLP task. A trie compactly stores the primitive feature vec- tors with their weights, and it enables the classifier to find for a given feature vec- tor its longest prefix feature vector whose weight has already been computed. Ex- perimental results for a Japanese depen- dency parsing task show that our method speeded up the SVM and LLM classifiers of the parsers, which achieved accuracy of 90.84/90.71%, by a factor of 10.7/11.6. 1 Introduction Deep and accurate text analysis based on discrimi- native models is not yet efficient enough as a com- ponent of real-time applications, and it is inade- quate to process Web-scale corpora for knowledge acquisition (Pantel, 2007; Saeger et al., 2009) or semi-supervised learning (McClosky et al., 2006; Spoustová et al., 2009). One of the main reasons for this inefficiency is attributed to the inefficiency of core classifiers trained with many feature com- binations (e.g., word n-grams). Hereafter, we refer to features that explicitly represent combinations of features as conjunctive features and the other atomic features as primitive features. The feature combinations play an essential role in obtaining a classifier with state-of-the-art ac- curacy for several NLP tasks; recent examples in- clude dependency parsing (Koo et al., 2008), parse re-ranking (McClosky et al., 2006), pronoun reso- lution (Nguyen and Kim, 2008), and semantic role labeling (Liu and Sarkar, 2007). However, ‘ex- plicit’ feature combinations significantly increase the feature space, which slows down not only training but also testing of the classifier. Kernel-based methods such as support vector machines (SVMs) consider feature combinations space-efficiently by using a polynomial kernel function (Cortes and Vapnik, 1995). The kernel- based classification is, however, known to be very slow in NLP tasks, so efficient classifiers should sum up the weights of the explicit conjunctive fea- tures (Isozaki and Kazawa, 2002; Kudo and Mat- sumoto, 2003; Goldberg and Elhadad, 2008). ℓ1-regularized log-linear models (ℓ1-LLMs), on the other hand, provide sparse solutions, in which weights of irrelevant features are exactly zero, by assuming a Laplacian prior on the weights (Tibshi- rani, 1996; Kazama and Tsujii, 2003; Goodman, 2004; Gao et al., 2007). However, as Kazama and Tsujii (2005) have reported in a text categorization task and we later confirm in a dependency pars- ing task, when most features regarded as irrelevant during training ℓ1-LLMs appear rarely in the task, we cannot greatly reduce the number of active fea- tures in each …

Content truncated to 500 words