📄 Fast Methods for Kernel-Based Text Analysis

Summary

SVMs with polynomial kernels work well for NLP classification because they implicitly consider conjunctions of features, so nobody has to hand-pick them. The drawback is speed. Each decision sums kernel values over every support example, which makes these analyzers far too slow for large text collections. Kudo and Matsumoto restrict attention to binary (set-valued) feature vectors and propose two faster classifiers for the kernel (1 + |X ∩ Y|)^d.

• PKI builds an inverted index from each feature to the support examples that contain it. It gives exactly the same output as the baseline.
• PKE rewrites the kernel in an explicit form with closed-form weights for subsets of each size. This turns the SVM into a linear model over feature combinations. Combinations whose weights are nearly zero are discarded, and the remaining ones are found with an adapted version of the PrefixSpan pattern-mining algorithm.

Tested on three tasks, namely Japanese dependency parsing, English BaseNP chunking and Japanese word segmentation, PKI delivers roughly 2–13× speedups and PKE roughly 30–300×, while accuracy stays practically the same. This makes kernel-quality models usable in high-throughput settings.

Key points

• The baseline classifier (PKB) costs O(|X|·|SV|). PKI reduces this to O(|X|·B + |SV|), where B is the average number of support examples per feature. PKE costs O(|X|^d) and does not depend on the number of support vectors.

• Experimental setup:

  Task	Training examples	Support vectors
  EBC	135,692	11,690
  JWS	265,413	57,672
  JDP	110,355	34,996

  EBC is a multi-class task, so it uses pairwise classifiers combined by majority voting.

• EBC results: PKE is about 97–105× faster than PKB, with F1 between 93.79 and 93.85 (PKB: 93.84). PKI is 8.3× faster.

• JWS results: PKE is up to 358× faster, with accuracy of 97.93–97.95% (PKB: 97.94%).

• JDP results: PKE is 32–67× faster, with accuracy of 88.91–89.29% (PKB: 89.29%). PKI is 12.6× faster.

• Pruning by feature frequency affects the two Japanese tasks differently:

  • JWS: it shrinks the model but costs accuracy (down to 97.83%).
  • JDP: it cuts the expanded model from about 8.3M to 2.45M combinations without losing accuracy.

• The method generalizes Isozaki & Kazawa's XQK, which handles only quadratic kernels and expands combinations exhaustively.

Interesting ideas

• I1. Compile a trained kernel model into a linear one. Precomputing one weight per feature conjunction moves the cost from prediction time to training time. This pays off for any deployed model with many support vectors and sparse binary inputs.
• I2. Use an inverted index over support vectors. The idea is borrowed from information retrieval and needs no approximation. It is a cheap first speedup whenever features are sparse, such as lexical features.
• I3. Treat weight enumeration as frequent-pattern mining. Sorting a set turns it into a sequence, so a sequence miner like PrefixSpan can enumerate useful combinations without a blind exhaustive search. Other pattern-mining tools could be repurposed for model compression in the same way.
• I4. Prune by weight magnitude and report the full trade-off. Dropping near-zero weights via the σ thresholds gives a tunable size/speed/accuracy knob. Reporting speed, model size and accuracy at several thresholds is a good evaluation template for any approximation method.
• I5. Extend the approach to structured kernels. The authors suggest the same expansion could apply to string and tree kernels by pairing them with sub-tree mining.