Kernel Slicing: Scalable Online Training with Conjunctive Features

Proceedings of the 23rd International Conference on Computational Linguistics (Coling 2010), pages 1245–1253, Beijing, August 2010 Kernel Slicing: Scalable Online Training with Conjunctive Features Naoki Yoshinaga Institute of Industrial Science, the University of Tokyo ynaga@tkl.iis.u-tokyo.ac.jp Masaru Kitsuregawa Institute of Industrial Science, the University of Tokyo kitsure@tkl.iis.u-tokyo.ac.jp Abstract This paper proposes an efficient online method that trains a classifier with many conjunctive features. We employ kernel computation called kernel slicing, which explicitly considers conjunctions among frequent features in computing the poly- nomial kernel, to combine the merits of linear and kernel-based training. To im- prove the scalability of this training, we reuse the temporal margins of partial fea- ture vectors and terminate unnecessary margin computations. Experiments on de- pendency parsing and hyponymy-relation extraction demonstrated that our method could train a classifier orders of magni- tude faster than kernel-based online learn- ing, while retaining its space efficiency. 1 Introduction The past twenty years have witnessed a growing use of machine-learning classifiers in the field of NLP. Since the classification target of complex NLP tasks (e.g., dependency parsing and relation extraction) consists of more than one constituent (e.g., a head and a dependent in dependency pars- ing), we need to consider conjunctive features, i.e., conjunctions of primitive features that fo- cus on the particular clues of each constituent, to achieve a high degree of accuracy in those tasks. Training with conjunctive features involves a space-time trade-off in the way conjunctive fea- tures are handled. Linear models, such as log- linear models, explicitly estimate the weights of conjunctive features, and training thus requires a great deal of memory when we take higher-order conjunctive features into consideration. Kernel- based models such as support vector machines, on the other hand, ensure space efficiency by using the kernel trick to implicitly consider conjunctive features. However, training takes quadratic time in the number of examples, even with online algo- rithms such as the (kernel) perceptron (Freund and Schapire, 1999), and we cannot fully exploit am- ple ‘labeled’ data obtained with semi-supervised algorithms (Ando and Zhang, 2005; Bellare et al., 2007; Liang et al., 2008; Daum´e III, 2008). We aim at resolving this dilemma in train- ing with conjunctive features, and propose online learning that combines the time efficiency of lin- ear training and the space efficiency of kernel- based training. Following the work by Goldberg and Elhadad (2008), we explicitly take conjunc- tive features into account that frequently appear in the training data, and implicitly consider the other conjunctive features by using the polynomial ker- nel. We then improve the scalability of this train- ing by a method called kernel slicing, which al- lows us to reuse the temporal margins of partial feature vectors and to terminate computations that do not contribute to parameter updates. We evaluate our method in two NLP tasks: de- pendency parsing and hyponymy-relation extrac- tion. We demonstrate that our method is orders of magnitude faster than kernel-based online learn- ing while retaining its space efficiency. The remainder of this paper is organized as …

Content truncated to 500 words