Hierarchical Directed Acyclic Graph Kernel: Methods for Structured Natural Language Data

Hierarchical Directed Acyclic Graph Kernel: Methods for Structured Natural Language Data Jun Suzuki, Tsutomu Hirao, Yutaka Sasaki, and Eisaku Maeda NTT Communication Science Laboratories, NTT Corp. 2-4 Hikaridai, Seika-cho, Soraku-gun, Kyoto, 619-0237 Japan � jun, hirao, sasaki, maeda � @cslab.kecl.ntt.co.jp Abstract This paper proposes the “Hierarchical Di- rected Acyclic Graph (HDAG) Kernel” for structured natural language data. The HDAG Kernel directly accepts several lev- els of both chunks and their relations, and then efficiently computes the weighed sum of the number of common attribute sequences of the HDAGs. We applied the proposed method to question classifica- tion and sentence alignment tasks to eval- uate its performance as a similarity mea- sure and a kernel function. The results of the experiments demonstrate that the HDAG Kernel is superior to other kernel functions and baseline methods. 1 Introduction As it has become easy to get structured corpora such as annotated texts, many researchers have applied statistical and machine learning techniques to NLP tasks, thus the accuracies of basic NLP tools, such as POS taggers, NP chunkers, named entities tag- gers and dependency analyzers, have been improved to the point that they can realize practical applica- tions in NLP. The motivation of this paper is to identify and use richer information within texts that will improve the performance of NLP applications; this is in con- trast to using feature vectors constructed by a bag- of-words (Salton et al., 1975). We now are focusing on the methods that use nu- merical feature vectors to represent the features of natural language data. In this case, since the orig- inal natural language data is symbolic, researchers convert the symbolic data into numeric data. This process, feature extraction, is ad-hoc in nature and differs with each NLP task; there has been no neat formulation for generating feature vectors from the semantic and grammatical structures inside texts. Kernel methods (Vapnik, 1995; Cristianini and Shawe-Taylor, 2000) suitable for NLP have recently been devised. Convolution Kernels (Haussler, 1999) demonstrate how to build kernels over discrete struc- tures such as strings, trees, and graphs. One of the most remarkable properties of this kernel method- ology is that it retains the original representation of objects and algorithms manipulate the objects simply by computing kernel functions from the in- ner products between pairs of objects. This means that we do not have to map texts to the feature vectors by explicitly representing them, as long as an efficient calculation for the inner products be- tween a pair of texts is defined. The kernel method is widely adopted in Machine Learning methods, such as the Support Vector Machine (SVM) (Vap- nik, 1995). In addition, kernel function ���� � has been described as a similarity function that satisfies certain properties (Cristianini and Shawe- Taylor, 2000). The similarity measure between texts is one of the most important factors for some tasks in the application areas of NLP such as Machine Trans- lation, Text Categorization, Information Retrieval, and Question Answering. This paper proposes the Hierarchical Directed Acyclic …

Content truncated to 500 words