nips nips2003 nips2003-99 nips2003-99-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Jun Suzuki, Yutaka Sasaki, Eisaku Maeda
Abstract: This paper devises a novel kernel function for structured natural language data. In the field of Natural Language Processing, feature extraction consists of the following two steps: (1) syntactically and semantically analyzing raw data, i.e., character strings, then representing the results as discrete structures, such as parse trees and dependency graphs with part-of-speech tags; (2) creating (possibly high-dimensional) numerical feature vectors from the discrete structures. The new kernels, called Hierarchical Directed Acyclic Graph (HDAG) kernels, directly accept DAGs whose nodes can contain DAGs. HDAG data structures are needed to fully reflect the syntactic and semantic structures that natural language data inherently have. In this paper, we define the kernel function and show how it permits efficient calculation. Experiments demonstrate that the proposed kernels are superior to existing kernel functions, e.g., sequence kernels, tree kernels, and bag-of-words kernels. 1
[1] M. Collins and N. Duffy. Convolution Kernels for Natural Language. In Proc. of Neural Information Processing Systems (NIPS’2001), 2001.
[2] M. Collins and N. Duffy. Parsing with a Single Neuron: Convolution Kernels for Natural Language Problems. In Technical Report UCS-CRL-01-10. UC Santa Cruz, 2001.
[3] C. Fellbaum. WordNet: An Electronic Lexical Database. MIT Press, 1998.
[4] D. Haussler. Convolution Kernels on Discrete Structures. In Technical Report UCS-CRL-99-10. UC Santa Cruz, 1999.
[5] S. Ikehara, M. Miyazaki, S. Shirai, A. Yokoo, H. Nakaiwa, K. Ogura, Y. Oyama, and Y. Hayashi, editors. The Semantic Attribute System, Goi-Taikei — A Japanese Lexicon, volume 1. Iwanami Publishing, 1997. (in Japanese).
[6] T. Joachims. Text Categorization with Support Vector Machines: Learning with Many Relevant Features. In Proc. of European Conference on Machine Learning(ECML ’98), pages 137–142, 1998.
[7] X. Li and D. Roth. Learning Question Classifiers. In Proc. of the 19th International Conference on Computational Linguistics (COLING 2002), pages 556–562, 2002.
[8] H. Lodhi, C. Saunders, J. Shawe-Taylor, N. Cristianini, and C. Watkins. Text Classification Using String Kernel. Journal of Machine Learning Research, 2:419–444, 2002.
[9] N. Cancedda and E. Gaussier and C. Goutte and J.-M. Renders. Word-Sequence Kernels. Journal of Machine Learning Research, 3:1059–1082, 2003.
[10] J. Suzuki, H. Taira, Y. Sasaki, and E. Maeda. Question Classification using HDAG Kernel. In Workshop on Multilingual Summarization and Question Answering (2003), pages 61–68, 2003.
[11] V. N. Vapnik. The Nature of Statistical Learning Theory. Springer, 1995.
[12] C. Watkins. Dynamic Alignment Kernels. In Technical Report CSD-TR-98-11. Royal Holloway, University of London Computer Science Department, 1999.