Paper: Polynomial to Linear: Efficient Classification with Conjunctive Features

ACL ID D09-1160
Title Polynomial to Linear: Efficient Classification with Conjunctive Features
Venue Conference on Empirical Methods in Natural Language Processing
Session Main Conference
Year 2009
Authors

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.