Convolution Kernels with Feature Selection for Natural Language Processing Tasks

Convolution Kernels with Feature Selection for Natural Language Processing Tasks Jun Suzuki, Hideki Isozaki and Eisaku Maeda NTT Communication Science Laboratories, NTT Corp. 2-4 Hikaridai, Seika-cho, Soraku-gun, Kyoto,619-0237 Japan {jun, isozaki, maeda}@cslab.kecl.ntt.co.jp Abstract Convolution kernels, such as sequence and tree ker- nels, are advantageous for both the concept and ac- curacy of many natural language processing (NLP) tasks. Experiments have, however, shown that the over-fitting problem often arises when these ker- nels are used in NLP tasks. This paper discusses this issue of convolution kernels, and then proposes a new approach based on statistical feature selec- tion that avoids this issue. To enable the proposed method to be executed efficiently, it is embedded into an original kernel calculation process by using sub-structure mining algorithms. Experiments are undertaken on real NLP tasks to confirm the prob- lem with a conventional method and to compare its performance with that of the proposed method. 1 Introduction Over the past few years, many machine learn- ing methods have been successfully applied to tasks in natural language processing (NLP). Espe- cially, state-of-the-art performance can be achieved with kernel methods, such as Support Vector Machine (Cortes and Vapnik, 1995). Exam- ples include text categorization (Joachims, 1998), chunking (Kudo and Matsumoto, 2002) and pars- ing (Collins and Duffy, 2001). Another feature of this kernel methodology is that it not only provides high accuracy but also allows us to design a kernel function suited to modeling the task at hand. Since natural language data take the form of sequences of words, and are generally ana- lyzed using discrete structures, such as trees (parsed trees) and graphs (relational graphs), discrete ker- nels, such as sequence kernels (Lodhi et al., 2002), tree kernels (Collins and Duffy, 2001), and graph kernels (Suzuki et al., 2003a), have been shown to offer excellent results. These discrete kernels are related to convolution kernels (Haussler, 1999), which provides the con- cept of kernels over discrete structures. Convolution kernels allow us to treat structural features without explicitly representing the feature vectors from the input object. That is, convolution kernels are well suited to NLP tasks in terms of both accuracy and concept. Unfortunately, experiments have shown that in some cases there is a critical issue with convolution kernels, especially in NLP tasks (Collins and Duffy, 2001; Cancedda et al., 2003; Suzuki et al., 2003b). That is, the over-fitting problem arises if large “sub- structures” are used in the kernel calculations. As a result, the machine learning approach can never be trained efficiently. To solve this issue, we generally eliminate large sub-structures from the set of features used. How- ever, the main reason for using convolution kernels is that we aim to use structural features easily and efficiently. If use is limited to only very small struc- tures, it negates the advantages of using convolution kernels. This paper discusses this issue of convolution kernels, and proposes a new method based on statis- tical feature selection. The proposed method deals only with those features that are statistically signif- …

Content truncated to 500 words