---
title: "Fast Methods for Kernel-Based Text Analysis — Kudo 2003"
description: "PKI builds an inverted index from each feature to the support examples that contain it. 14 references, cited by 64 papers here."
authors: ["Taku Kudo", "Yuji Matsumoto"]
year: 2003
venue: "Proceedings of the 41st Annual Meeting of the Association for Computational Linguistics"
source: "https://aclanthology.org/P03-1004/"
doi: "10.3115/1075096.1075100"
licence: "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)"
licence_url: "https://creativecommons.org/licenses/by-nc-sa/3.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/kudo-2003-fast-methods-kernel-based-text/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/kudo-2003-fast-methods-kernel-based-text/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2003](https://md.research.elamur.ai/free/en/papers/2003/) / Fast Methods for Kernel-Based Text Analysis

# Fast Methods for Kernel-Based Text Analysis

**Authors:** [Taku Kudo](https://md.research.elamur.ai/free/en/authors/taku-kudo/) and [Yuji Matsumoto](https://md.research.elamur.ai/free/en/authors/yuji-matsumoto/) · **Year:** 2003 · **Venue:** [Proceedings of the 41st Annual Meeting of the Association for Computational Linguistics](https://md.research.elamur.ai/free/en/venues/acl/) ([ACL 2003](https://md.research.elamur.ai/free/en/venues/acl/2003/)) · **Publisher:** [Association for Computational Linguistics](https://md.research.elamur.ai/free/en/publishers/association-for-computational-linguistics/) · **Licence:** [CC BY-NC-SA 3.0 (ACL Anthology, before 2016)](https://creativecommons.org/licenses/by-nc-sa/3.0/)

**Links:** [Publisher's page](https://aclanthology.org/P03-1004/) · [PDF](https://aclanthology.org/P03-1004.pdf) · [DOI 10.3115/1075096.1075100](https://doi.org/10.3115/1075096.1075100) · [OpenAlex](https://openalex.org/W2159859968)

**Citations:** 202 citations (OpenAlex, 2026-10-14) · [64](https://md.research.elamur.ai/free/en/papers/kudo-2003-fast-methods-kernel-based-text/cited-by/) in our library, of the 141,840 papers whose bibliographies we read

## 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
- **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.
- **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.
- **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.
- **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.
- **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.

*Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.*

## Institutions

- [Nara Institute of Science and Technology](https://md.research.elamur.ai/free/en/universities/nara-institute-of-science-and-technology/) — University, Ikoma, Japan · 34 works · 4,419 citations

📚 Shelves (4): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 9,085 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 8,888 works · [🎭 Arts and Humanities](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/) · 9,296 works · [🗣️ Language and Linguistics](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/language-and-linguistics/) · 9,206 works

## Cite

Cite as: Taku Kudo and Yuji Matsumoto. 2003. Fast Methods for Kernel-Based Text Analysis. Proceedings of the 41st Annual Meeting of the Association for Computational Linguistics.

The paper itself, not this page. BibTeX from the library's record of the work.

```bibtex
@inproceedings{kudo2003fast,
  title = {{Fast Methods for Kernel-Based Text Analysis}},
  author = {Taku Kudo and Yuji Matsumoto},
  booktitle = {Proceedings of the 41st Annual Meeting of the Association for Computational Linguistics},
  year = {2003},
  doi = {10.3115/1075096.1075100},
  url = {https://doi.org/10.3115/1075096.1075100}
}
```

- [← previous Graph-Based Generation of Referring Expressions](https://md.research.elamur.ai/free/en/papers/krahmer-2003-graph-based-generation-referring-expressions/)
- [next → Transliteration of Proper Names in Cross-Lingual Information Retrieval](https://md.research.elamur.ai/free/en/papers/virga-2003-transliteration-proper-names-cross-lingual/)
- [↑ back to papers of 2003](https://md.research.elamur.ai/free/en/papers/2003/)

## References

14 references, 2 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. Junichi Aoe. 1989. An efficient digital search algorithm by using a double-array structure. IEEE Transactions on Software Engineering, 15(9). [find](https://scholar.google.com/scholar?q=Junichi+Aoe%2E+1989%2E+An+efficient+digital+search+algorithm+by+using+a+double%2Darray+structure%2E+IEEE+Transactions+on+Software+Engineering%2C+15%289%29%2E)
2. Michael Collins and Nigel Duffy. 2001. Convolution kernels for natural language. In Advances in Neural Information Processing Systems 14, Vol.1 (NIPS 2001), pages 625–632. [find](https://scholar.google.com/scholar?q=Michael+Collins+and+Nigel+Duffy%2E+2001%2E+Convolution+kernels+for+natural+language%2E+In+Advances+in+Neural+Information+Processing+Systems+14%2C+Vol%2E1+%28NIPS+2001%29%2C+pages+625%E2%80%93632%2E)
3. Hideki Isozaki and Hideto Kazawa. 2002. Efficient support vector classifiers for named entity recognition. In Proceedings of the COLING-2002, pages 390–396. [find](https://scholar.google.com/scholar?q=Hideki+Isozaki+and+Hideto+Kazawa%2E+2002%2E+Efficient+support+vector+classifiers+for+named+entity+recognition%2E+In+Proceedings+of+the+COLING%2D2002%2C+pages+390%E2%80%93396%2E)
4. Hisashi Kashima and Teruo Koyanagi. 2002. Svm kernels for semi-structured data. In Proceedings of the ICML-2002, pages 291–298. [find](https://scholar.google.com/scholar?q=Hisashi+Kashima+and+Teruo+Koyanagi%2E+2002%2E+Svm+kernels+for+semi%2Dstructured+data%2E+In+Proceedings+of+the+ICML%2D2002%2C+pages+291%E2%80%93298%2E)
5. Taku Kudo and Yuji Matsumoto. 2000. Japanese Dependency Structure Analysis based on Support Vector Machines. In Proceedings of the EMNLP/VLC-2000, pages 18–25. [find](https://scholar.google.com/scholar?q=Taku+Kudo+and+Yuji+Matsumoto%2E+2000%2E+Japanese+Dependency+Structure+Analysis+based+on+Support+Vector+Machines%2E+In+Proceedings+of+the+EMNLP%2FVLC%2D2000%2C+pages+18%E2%80%9325%2E)
6. Taku Kudo and Yuji Matsumoto. 2001. [Chunking with support vector machines](https://md.research.elamur.ai/free/en/papers/kudo-2001-chunking-support-vector-machines/). In Proceedings of the the NAACL, pages 192–199.
7. Taku Kudo and Yuji Matsumoto. 2002. Japanese dependency analyisis using cascaded chunking. In Proceedings of the CoNLL-2002, pages 63–69. [find](https://scholar.google.com/scholar?q=Taku+Kudo+and+Yuji+Matsumoto%2E+2002%2E+Japanese+dependency+analyisis+using+cascaded+chunking%2E+In+Proceedings+of+the+CoNLL%2D2002%2C+pages+63%E2%80%9369%2E)
8. Sadao Kurohashi and Makoto Nagao. 1997. Kyoto University text corpus project. In Proceedings of the ANLP-1997, pages 115–118. [find](https://scholar.google.com/scholar?q=Sadao+Kurohashi+and+Makoto+Nagao%2E+1997%2E+Kyoto+University+text+corpus+project%2E+In+Proceedings+of+the+ANLP%2D1997%2C+pages+115%E2%80%93118%2E)
9. Huma Lodhi, Craig Saunders, John Shawe-Taylor, Nello Cristianini, and Chris Watkins. 2002. Text classification using string kernels. Journal of Machine Learning Research, 2. [find](https://scholar.google.com/scholar?q=Huma+Lodhi%2C+Craig+Saunders%2C+John+Shawe%2DTaylor%2C+Nello+Cristianini%2C+and+Chris+Watkins%2E+2002%2E+Text+classification+using+string+kernels%2E+Journal+of+Machine+Learning+Research%2C+2%2E)
10. Tetsuji Nakagawa, Taku Kudo, and Yuji Matsumoto. 2002. Revision learning and its application to part-of-speech tagging. In Proceedings of the ACL 2002, pages 497–504. [find](https://scholar.google.com/scholar?q=Tetsuji+Nakagawa%2C+Taku+Kudo%2C+and+Yuji+Matsumoto%2E+2002%2E+Revision+learning+and+its+application+to+part%2Dof%2Dspeech+tagging%2E+In+Proceedings+of+the+ACL+2002%2C+pages+497%E2%80%93504%2E)
11. Jian Pei, Jiawei Han, and et al. 2001. Prefixspan: Mining sequential patterns by prefix-projected growth. In Proc. of International Conference of Data Engineering, pages 215– 224. [find](https://scholar.google.com/scholar?q=Jian+Pei%2C+Jiawei+Han%2C+and+et+al%2E+2001%2E+Prefixspan%3A+Mining+sequential+patterns+by+prefix%2Dprojected+growth%2E+In+Proc%2E+of+International+Conference+of+Data+Engineering%2C+pages+215%E2%80%93+224%2E)
12. Lance A. Ramshaw and Mitchell P. Marcus. 1995. [Text chunking using transformation-based learning](https://md.research.elamur.ai/free/en/papers/ramshaw-1995-text-chunking-transformation-based-learning/). In Proceedings of the VLC, pages 88–94.
13. Vladimir N. Vapnik. 1995. The Nature of Statistical Learning Theory. Springer. [find](https://scholar.google.com/scholar?q=Vladimir+N%2E+Vapnik%2E+1995%2E+The+Nature+of+Statistical+Learning+Theory%2E+Springer%2E)
14. Mohammed Zaki. 2002. Efficiently mining frequent trees in a forest. In Proceedings of the 8th International Conference on Knowledge Discovery and Data Mining KDD, pages 71– 80. [find](https://scholar.google.com/scholar?q=Mohammed+Zaki%2E+2002%2E+Efficiently+mining+frequent+trees+in+a+forest%2E+In+Proceedings+of+the+8th+International+Conference+on+Knowledge+Discovery+and+Data+Mining+KDD%2C+pages+71%E2%80%93+80%2E)

*Updated 24 October 2026*