The Leaf Path Projection View of Parse Trees: Exploring String Kernels for HPSG Parse Selection

The Leaf Projection Path View of Parse Trees: Exploring String Kernels for HPSG Parse Selection Kristina Toutanova CS Dept, Stanford University 353 Serra Mall Stanford 94305, CA USA, kristina@cs.stanford.edu Penka Markova EE Dept, Stanford University 350 Serra Mall Stanford 94305, CA, USA, penka@cs.stanford.edu Christopher Manning CS Dept, Stanford University 353 Serra Mall Stanford 94305, CA, USA, manning@cs.stanford.edu Abstract We present a novel representation of parse trees as lists of paths (leaf projection paths) from leaves to the top level of the tree. This representation allows us to achieve significantly higher accuracy in the task of HPSG parse selection than standard models, and makes the application of string kernels natural. We define tree kernels via string kernels on projec- tion paths and explore their performance in the con- text of parse disambiguation. We apply SVM rank- ing models and achieve an exact sentence accuracy of 85.40% on the Redwoods corpus. 1 Introduction In this work we are concerned with building sta- tistical models for parse disambiguation – choos- ing a correct analysis out of the possible analyses for a sentence. Many machine learning algorithms for classification and ranking require data to be rep- resented as real-valued vectors of fixed dimension- ality. Natural language parse trees are not readily representable in this form, and the choice of repre- sentation is extremely important for the success of machine learning algorithms. For a large class of machine learning algorithms, such an explicit representation is not necessary, and it suffices to devise a kernel function ����� � which measures the similarity between inputs � and � . In addition to achieving efficient computation in high dimensional representation spaces, the use of ker- nels allows for an alternative view on the mod- elling problem as defining a similarity between in- puts rather than a set of relevant features. In previous work on discriminative natural lan- guage parsing, one approach has been to define fea- tures centered around lexicalized local rules in the trees (Collins, 2000; Shen and Joshi, 2003), simi- lar to the features of the best performing lexicalized generative parsing models (Charniak, 2000; Collins, 1997). Additionally non-local features have been defined measuring e.g. parallelism and complexity of phrases in discriminative log-linear parse ranking models (Riezler et al., 2000). Another approach has been to define tree kernels: for example, in (Collins and Duffy, 2001), the all- subtrees representation of parse trees (Bod, 1998) is effectively utilized by the application of a fast dynamic programming algorithm for computing the number of common subtrees of two trees. Another tree kernel, more broadly applicable to Hierarchi- cal Directed Graphs, was proposed in (Suzuki et al., 2003). Many other interesting kernels have been de- vised for sequences and trees, with application to se- quence classification and parsing. A good overview of kernels for structured data can be found in (Gaert- ner et al., 2002). Here we propose a new representation of parse trees which (i) allows the localization of broader useful context, (ii) paves the way for exploring ker- nels, …

Content truncated to 500 words