Convolution Kernel over Packed Parse Forest

Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pages 875–885, Uppsala, Sweden, 11-16 July 2010. c⃝2010 Association for Computational Linguistics Convolution Kernel over Packed Parse Forest Min Zhang Hui Zhang Haizhou Li Institute for Infocomm Research A-STAR, Singapore {mzhang,vishz,hli}@i2r.a-star.edu.sg Abstract This paper proposes a convolution forest ker- nel to effectively explore rich structured fea- tures embedded in a packed parse forest. As opposed to the convolution tree kernel, the proposed forest kernel does not have to com- mit to a single best parse tree, is thus able to explore very large object spaces and much more structured features embedded in a forest. This makes the proposed kernel more robust against parsing errors and data sparseness is- sues than the convolution tree kernel. The pa- per presents the formal definition of convolu- tion forest kernel and also illustrates the com- puting algorithm to fast compute the proposed convolution forest kernel. Experimental results on two NLP applications, relation extraction and semantic role labeling, show that the pro- posed forest kernel significantly outperforms the baseline of the convolution tree kernel. 1 Introduction Parse tree and packed forest of parse trees are two widely used data structures to represent the syntactic structure information of sentences in natural language processing (NLP). The struc- tured features embedded in a parse tree have been well explored together with different ma- chine learning algorithms and proven very useful in many NLP applications (Collins and Duffy, 2002; Moschitti, 2004; Zhang et al., 2007). A forest (Tomita, 1987) compactly encodes an ex- ponential number of parse trees. In this paper, we study how to effectively explore structured fea- tures embedded in a forest using convolution kernel (Haussler, 1999). As we know, feature-based machine learning methods are less effective in modeling highly structured objects (Vapnik, 1998), such as parse tree or semantic graph in NLP. This is due to the fact that it is usually very hard to represent struc- tured objects using vectors of reasonable dimen- sions without losing too much information. For example, it is computationally infeasible to enu- merate all subtree features (using subtree a fea- ture) for a parse tree into a linear feature vector. Kernel-based machine learning method is a good way to overcome this problem. Kernel methods employ a kernel function, that must satisfy the properties of being symmetric and positive, to measure the similarity between two objects by computing implicitly the dot product of certain features of the input objects in high (or even in- finite) dimensional feature spaces without enu- merating all the features (Vapnik, 1998). Many learning algorithms, such as SVM (Vapnik, 1998), the Perceptron learning algo- rithm (Rosenblatt, 1962) and Voted Perceptron (Freund and Schapire, 1999), can work directly with kernels by replacing the dot product with a particular kernel function. This nice property of kernel methods, that implicitly calculates the dot product in a high-dimensional space over the original representations of objects, has made kernel methods an effective solution to modeling structured objects in NLP. In …

Content truncated to 500 words