Proceedings

Fast Linearization of Tree Kernels over Large-Scale Data

Download BibTeX Cite

Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 2162-2167.

© 2013 International Joint Conferences on Artificial Intelligence

Abstract

Convolution tree kernels have been successfully applied to many language processing tasks for achieving state-of-the-art accuracy. Unfortunately, higher computational complexity of learning with kernels w.r.t. using explicit feature vectors makes them less attractive for large-scale data.In this paper, we study the latest approaches to solve such problems ranging from feature hashing to reverse kernel engineering and approximate cutting plane training with model compression. We derive a novel method that relies on reverse-kernel engineering together with an efficient kernel learning method. The approach gives the advantage of using tree kernels to automatically generate rich structured feature spaces and working in the linear space where learning and testing is fast. We experimented with training sets up to 4 million examples from Semantic Role Labeling. The results show that (i) the choice of correct structural features is essential and (ii) we can speed-up training from weeks to less than 20 minutes.

  1. [Carreras and Màrquez, 2005] Xavier Carreras and Lluís Màrquez. Introduction to the CoNLL-2005 Shared Task: Semantic Role Labeling. In CoNLL, 2005.
  2. [Chapelle, 2007] Olivier Chapelle. Training a support vector machine in the primal. Neural Comput., 19(5):1155-1178, May 2007.
  3. [Charniak, 2000] Eugene Charniak. A maximum-entropy- inspired parser. In ANLP, pages 132-139, 2000.
  4. [Collins and Duffy, 2002a] M. Collins and N. Duffy. New ranking algorithms for parsing and tagging: Kernels over discrete structures, and the voted perceptron. In ACL, Philadelphia, PA, USA, 2002.
  5. [Collins and Duffy, 2002b] Michael Collins and Nigel Duffy. New Ranking Algorithms for Parsing and Tag- ging: Kernels over Discrete Structures, and the Voted Perceptron. In ACL, 2002.
  6. [Cumby and Roth, 2003] Chad Cumby and Dan Roth. Ker- nel Methods for Relational Learning. In ICML, 2003.
  7. [Daumé III and Marcu, 2004] Hal Daumé III and Daniel Marcu. A tree-position kernel for document compression. In DUC, 2004.
  8. [Fan et al., 2008] Rong-En Fan, Kai-Wei Chang, Cho-Jui Hsieh, Xiang-Rui Wang, and Chih-Jen Lin. Liblinear: A library for large linear classification. JMLR, 9:1871-1874, June 2008.
  9. [Franc and Sonnenburg, 2008] Vojtech Franc and Sören Sonnenburg. Optimized cutting plane algorithm for sup- port vector machines. In ICML, pages 320-327, 2008.
  10. [Ganchev and Dredze, 2008] Kuzman Ganchev and Mark Dredze. Small statistical models by random feature mix- ing. In In workshop on Mobile NLP at ACL, 2008.
  11. [Gildea and Jurafsky, 2002] Daniel Gildea and Daniel Juraf- sky. Automatic labeling of semantic roles. Computational Linguistics, 28:245-288, 2002.
  12. [Graf et al., 2004] Hans Peter Graf, Eric Cosatto, Leon Bot- tou, Igor Durdanovic, and Vladimir Vapnik. Parallel sup- port vector machines: The cascade svm. In NIPS, 2004.
  13. [Guyon and Elisseeff, 2003] Isabelle Guyon and André Elis- seeff. An introduction to variable and feature selec- tion. Journal of Machine Learning Research, 3:1157- 1182, 2003.
  14. [Haussler, 1999] David Haussler. Convolution kernels on discrete structures. Technical report, Dept. of Computer Science, University of California at Santa Cruz, 1999.
  15. [Joachims, 1999] T. Joachims. Making large-scale SVM learning practical. In Advances in Kernel Methods -Sup- port Vector Learning, chapter 11, pages 169-184. MIT Press, Cambridge, MA, 1999.
  16. [Joachims, 2006] T. Joachims. Training linear SVMs in lin- ear time. In KDD, 2006.
  17. [Kate and Mooney, 2006] Rohit J. Kate and Raymond J. Mooney. Using string-kernels for learning semantic parsers. In ACL, July 2006. [Kazama and Torisawa, 2005] Jun'ichi Kazama and Kentaro Torisawa. Speeding up training with tree kernels for node relation labeling. In EMNLP, 2005.
  18. [Kudo and Matsumoto, 2003] Taku Kudo and Yuji Mat- sumoto. Fast methods for kernel-based text analysis. In ACL, 2003.
  19. [Kudo et al., 2005] Taku Kudo, Jun Suzuki, and Hideki Isozaki. Boosting-based parse reranking with subtree fea- tures. In ACL, 2005.
  20. [Marcus et al., 1993] Mitchell P. Marcus, Beatrice Santorini, and Mary Ann Marcinkiewicz. Building a large annotated corpus of English: the Penn Treebank. Computational Lin- guistics, 19(2):313-330, 1993.
  21. [Moschitti, 2006] Alessandro Moschitti. Making tree kernels practical for natural language learning. In EACL, Trento, Italy, 2006.
  22. [Palmer et al., 2005] Martha Palmer, Paul Kingsbury, and Daniel Gildea. The proposition bank: An annotated corpus of semantic roles. Computational Linguistics, 31(1):71- 106, 2005.
  23. [Pei et al., 2001] J. Pei, J. Han, Mortazavi B. Asl, H. Pinto, Q. Chen, U. Dayal, and M. C. Hsu. PrefixSpan Mining Sequential Patterns Efficiently by Prefix Projected Pattern Growth. In ICDE, 2001.
  24. [Pighin and Moschitti, 2009] Daniele Pighin and Alessandro Moschitti. Efficient linearization of tree kernel functions. In CONLL. ACL, 2009.
  25. [Severyn and Moschitti, 2011] A. Severyn and A. Moschitti. Fast support vector machines for structural kernels. In ECML/PKDD, 2011.
  26. [Shi et al., 2009] Qinfeng Shi, James Petterson, Gideon Dror, John Langford, Alex Smola, and S.V.N. Vish- wanathan. Hash kernels for structured data. Journal of Ma- chine Learning Research, 10:2615-2637, December 2009.
  27. [Suzuki and Isozaki, 2005] Jun Suzuki and Hideki Isozaki. Sequence and Tree Kernels with Statistical Feature Min- ing. In NIPS, 2005.
  28. [Yu and Joachims, 2008] Chun-Nam John Yu and T. Joachims. Training structural svms with kernels using sampled cuts. In KDD, 2008.
  29. [Zaki, 2002] Mohammed J. Zaki. Efficiently mining fre- quent trees in a forest. In SIGKDD, 2002.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards