Sequence and Tree Kernels with Statistical Feature Mining

Published 5 December 2005

Jun Suzuki, Hideki Isozaki

Citations35

TL;DR

This paper discusses the issue of convolution kernels and proposes a statistical feature selection that enable us to use larger sub-structures effectively and compares the performance of a conventional method to that of the proposed method.

Abstract

This paper proposes a new approach to feature selection based on a statistical feature mining technique for sequence and tree kernels. Since natural language data take discrete structures, convolution kernels, such as sequence and tree kernels, are advantageous for both the concept and accuracy of many natural language processing tasks. However, experiments have shown that the best results can only be achieved when limited small sub-structures are dealt with by these kernels. This paper discusses this issue of convolution kernels and then proposes a statistical feature selection that enable us to use larger sub-structures effectively. The proposed method, in order to execute efficiently, can be embedded into an original kernel calculation process by using sub-structure mining algorithms. Experiments on real NLP tasks confirm the problem in the conventional method and compare the performance of a conventional method to that of the proposed method. 1

Keywords

Computer Science

Lecture notes in computer scienceText categorization with Support Vector Machines: Learning with many relevant features

7,925 Citations1998Thorsten Joachims

SVMs achieve substantial improvements over the currently best performing methods and behave robustly over a variety of di-erent learning tasks, eliminating the need for manual parameter tuning.

PrefixSpan,: mining sequential patterns efficiently by prefix-projected pattern growth

1,791 Citations2005Jian Pei, Jiawei Han +5 more

This work proposes a novel sequential pattern mining method, called Prefixspan (i.e., Prefix-projected - Ettern_ mining), which explores prejxprojection in sequential pattern Mining, and shows that Pre fixspan outperforms both the Apriori-based GSP algorithm and another recently proposed method; Frees pan, in mining large sequence data bases.

Learning question classifiers

1,276 Citations2002Xin Li, Dan Roth

A hierarchical classifier is learned that is guided by a layered semantic hierarchy of answer types, and eventually classifies questions into fine-grained classes.

Convolution kernels on discrete structures

1,089 Citations1999David Haussler

A new method of constructing kernels on sets whose elements are discrete structures like strings, trees and graphs is introduced, which can be applied iteratively to build a kernel on a innnite set from kernels involving generators of the set.

The MIT Press eBooksConvolution Kernels for Natural Language

812 Citations2002Michael J. Collins, Nigel Duffy

It is shown how a kernel over trees can be applied to parsing using the voted perceptron algorithm, and experimental results on the ATIS corpus of parse trees are given.

Applied Physics Letters10.1162/153244302760200687

534 Citations2000

An approximation technique is introduced that is shown to deliver good approximations efficiently for large datasets and is shown to deliver good approximations efficiently for large datasets.

View PDF

Efficiently mining frequent trees in a forest

467 Citations2002Mohammed J. Zaki

This work presents TREEMinER, a novel algorithm to discover all frequent subtrees in a forest, using a new data structure called scope-list, and finds that TREEMINER outperforms the pattern matching approach by a factor of 4 to 20, and has good scaleup properties.

The MIT Press eBooksDynamic Alignment Kernels

242 Citations2000Chris Watkins

This paper shows that the scores produced by certain dynamic align ment algorithms for sequences are in fact valid kernel functions, proved by expressing the alignment scores explicitly as dot products.

Transversing itemset lattices with statistical metric pruning

200 Citations2000Shinichi Morishita, Jun Sese

A method of estimating a tight upper bound on the statistical metric associated with any superset of an itemset, as well as the novel use of the resulting information of upper bounds to prune unproductive supersets while traversing itemset lattices is presented.

Word sequence kernels

191 Citations2003Nicola Cancedda, Éric Gaussier +2 more

This article proposes the use of string kernels, a novel way of computing document similarity based of matching non-consecutive subsequences of characters with sequences of words rather than characters, and presents some extensions to sequence kernels dealing with symbol-dependent and match-dependent decay factors.