Power set kernel for feature combination: data mining approach for its fast classifiers

摘要

The kernel method (e.g., Support Vector Machines) attracts a great deal of attention recently. The merit of the kernel method is that the effective feature combination, which has been manually selected in the previous approaches, is implicitly expanded without loss of generality and computational cost. However, the kernel-based approach is usually too slow to classify large-scale test data. In this paper, we fist formulate a Power Set Kernel which gives a dot product of two sets. Then, we extend the Basket Mining algorithm to convert a kernel-based classifier into a simple and fast linear classifier. Experimental results on Japanese Word Segmentation and Japanese Dependency Parsing show that our new classifier is about 30-280 times faster than the standard kernel-based classifier.