Route kernels for trees

ABSTRACT

Almost all tree kernels proposed in the literature match substructures without taking into account their relative positioning with respect to one another. In this paper, we propose a novel family of kernels which explicitly focus on this type of information. Specifically, after defining a family of tree kernels based on routes between nodes, we present an efficient implementation for a member of this family. Experimental results on four different datasets show that our method is able to reach state of the art performances, obtaining in some cases performances better than computationally more demanding tree kernels.

REFERENCES

• 1: Stephan Bloehdorn , Alessandro Moschitti, Structure and semantics for expressive text kernels, Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, November 06-10, 2007, Lisbon, Portugal [doi>10.1145/1321440.1321561]
• 2: Michael Collins , Nigel Duffy, New ranking algorithms for parsing and tagging: kernels over discrete structures, and the voted perceptron, Proceedings of the 40th Annual Meeting on Association for Computational Linguistics, July 07-12, 2002, Philadelphia, Pennsylvania [doi>10.3115/1073083.1073128]
• 3: Ludovic Denoyer , Patrick Gallinari, Report on the XML mining track at INEX 2005 and INEX 2006: categorization and clustering of XML documents, ACM SIGIR Forum, v.41 n.1, p.79-90, June 2007 [doi>10.1145/1273221.1273230]
• 4: Michelangelo Diligenti , Paolo Frasconi , Marco Gori, Hidden Tree Markov Models for Document Image Classification, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.4, p.519-523, April 2003
• 5: Haussler, D. (1999). Convolution kernels on discrete structures (Technical Report UCSC-CRL-99-10). University of California, Santa Cruz.
• 6: Tommi S. Jaakkola , David Haussler, Exploiting generative models in discriminative classifiers, Proceedings of the 1998 conference on Advances in neural information processing systems II, p.487-493, July 1999
• 7: Hisashi Kashima , Teruo Koyanagi, Kernels for Semi-Structured Data, Proceedings of the Nineteenth International Conference on Machine Learning, p.291-298, July 08-12, 2002
• 8: Kingsbury, P., & Palmer, M. (2002). From Treebank to PropBank. Proceedings of the 3rd International Conference on Language Resources and Evaluation (pp. 1989--1993). Las Palmas, Spain.
• 9: Kuboyama, T., Hirata, K., Kashima, H., Aoki-Kinoshita, K. F., & Yasuda, H. (2007). A spectrum tree kernel. Information and Media Technologies, 2, 292--299.
• 10: Moschitti, A. (2006). Efficient convolution kernels for dependency and constituent syntactic trees. Proc. of the European Conference on Machine Learning (pp. 318--329).
• 11: Nicotra, L., Micheli, A., & Starita, A. (2004). Tree fisher kernel. Proceedings. 2004 IEEE International Joint Conference on Neural Networks (pp. 1917--1922).
• 12: Rieck, K., Brefeld, U., & Krger, T. (2008). Approximate kernels for trees (Technical Report). Fraunhofer Publica {http://publica.fraunhofer.de/oai.har} (Germany).
• 13: Kilho Shin , Tetsuji Kuboyama, A generalization of Haussler's convolution kernel: mapping kernel, Proceedings of the 25th international conference on Machine learning, p.944-951, July 05-09, 2008, Helsinki, Finland [doi>10.1145/1390156.1390275]
• 14: Suzuki, J., & Isozaki, H. (2006). Sequence and tree kernels with statistical feature mining. In Y. Weiss, B. Schöölkopf and J. Platt (Eds.), Advances in neural information processing systems 18, 1321--1328. Cambridge, MA: MIT Press.
• 15: Vishwanathan, S., & Smola, A. J. (2002). Fast kernels on strings and trees. Proceedings of Neural Information Processing Systems 2002 (pp. 569--576).
• 16: Zhang, M., Che, W., Aw, A., Tan, C. L., Zhou, G., Liu, T., & Li, S. (2007). A grammar-driven convolution tree kernel for semantic role classification. Proc. of the 45th Annual Meeting of the Association for Computational Linguistics (pp. 200--2007).

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Experimental design

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Graph and tree search strategies
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Experimentation, Performance