Structured Output Learning with Polynomial Kernel

International Conference RANLP 2009 - Borovets, Bulgaria, pages 281–286 Structured Output Learning with Polynomial Kernel Hajime Morita Department of Computational Intelligence and Systems Science, Tokyo Institute of Technology morita@lr.pi.titech.ac.jp Hiroya Takamura Precision and Intelligence Laboratory, Tokyo Institute of Technology takamura@pi.titech.ac.jp Manabu Okumura Precision and Intelligence Laboratory, Tokyo Institute of Technology oku@pi.titech.ac.jp Abstract We propose a new method which enables the training of a kernelized structured output model. The struc- tured output learning can flexibly represent a problem, and thus is gaining popularity in natural language pro- cessing. Meanwhile the polynomial kernel method is effective in many natural language processing tasks, since it takes into account the combination of features. However, it is computationally difficult to simultane- ously use both the structured output learning and the kernel method. Our method avoids this difficulty by transforming the kernel function, and enables the ker- nelized structured output learning. We theoretically discuss the computational complexity of the proposed method and also empirically show its high efficiency and effectiveness through experiments in the task of identifying agreement and disagreement relations be- tween utterances in meetings. Identifying agreement and disagreement relations consists of two mutually- correlated problems: identification of the utterance which each utterance is intended for, and classification of each utterance into approval, disapproval or others. We simultaneously use both of the structured output learning and the kernel method in order to take into account this correlation of the two problems. Keywords Structured Output Learning, Machine Learning, Passive-Aggressive Al- gorithm, Kernel, Meeting Records, Dialog Act, Adjacency-Pairs. 1 Introduction Structured output learning is a method that learns a model in order to predict the structured label of an instance. Typ- ically, the structure is complex, and the set of possible la- bels is very large. Examples of structured labels are graphs, trees and sequences. Recently, for the algorithms of struc- tured output learning, Support Vector Machine (Thochan- taridis, 04) and Passive Aggressive Algorithm (Crammer, 06) were expanded. Structured output learning plays an important role in natural language processing (NLP), in- cluding parsing and sequential role labeling. In NLP, the polynomial kernel has proven effective be- cause it can take into account the interaction between fea- tures. For example, for complicated tasks like dependency structure analysis, we need to consider a combination of features (Kudo, 00). The use of a kernel is necessary for non-linear classification, as well as for improvement of per- formance. However, structured output learning is hardly ever used with a kernel, mainly because evaluation of all possible labels by kernels would be necessary, and is com- putationally prohibitive. We construct a kernelized clas- sifier that identifies agreement/disagreement relations be- tween utterances in dialogue. Identifying agreement and disagreement relations consists of two mutually-correlated problems: identification of the utterance which each utter- ance is intended for, and classification of each utterance into approval, disapproval or others. This problem can be seen as the problem of finding edges between pairs of nodes, where the number of nodes is fixed, and it is equiva- lent to restricting …

Content truncated to 500 words