Polynomial to linear
Naoki Yoshinaga, Masaru Kitsuregawa · 2009
This paper proposes a method that speeds up a classifier trained with many conjunctive features: combinations of (primitive) features. The key idea is to precompute as partial results the weights of primitive feature vectors that appear frequently in the target NLP task. A trie compactly stores the primitive feature vectors with their weights, and it enables the classifier to find for a given feature vector its longest prefix feature vector whose weight has already been computed. Experimental results for a Japanese dependency 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.