Fast Methods for Kernel-based Text Analysis

Taku Kudo and Yuji Matsumoto
Graduate School of Information Science,
Nara Institute of Science and Technology{taku-ku,matsu}@is.aist-nara.ac.jp

Abstract
Kernel-based learning (e.g., Support Vector Machines) has been successfully applied to many hard problems in Natural
Language Processing (NLP). In NLP, although feature combinations are crucial to
improving performance, they are heuristically selected. Kernel methods change
this situation. The merit of the kernel
methods is that effective feature combination is implicitly expanded without lossof generality and increasing the computational costs. Kernel-based text analysis
shows an excellent performance in termsin accuracy; however, these methods areusually too slow to apply to large-scale
text analysis. In this paper, we extend
a Basket Mining algorithm to convert akernel-based classifier into a simple andfast linear classifier. Experimental results
on English BaseNP Chunking, JapaneseWord Segmentation and Japanese Dependency Parsing show that our new classifiers are about 30 to 300 times faster than
the standard kernel-based classifiers.

1

Introduction

Kernel methods (e.g., Support Vector Machines(Vapnik, 1995)) attract a great deal of attention recently. In the field of Natural Language Processing, many successes have been reported. Examples
include Part-of-Speech tagging (Nakagawa et al.,2002) Text Chunking (Kudo and Matsumoto, 2001),
Named Entity Recognition (Isozaki and Kazawa,
2002), and Japanese Dependency Parsing (Kudo andMatsumoto, 2000; Kudo and Matsumoto, 2002).
It is known in NLP that combination of featurescontributes to a significant improvement in accuracy.
For instance, in the task of dependency parsing, it
would be hard to confirm a correct dependency relation with only a single set of features from eithera head or its modifier. Rather, dependency relations
should be determined by at least information fromboth of two phrases. In previous research, feature
combination has been selected manually, and theperformance significantly depended on these selections. This is not the case with kernel-based methodology. For instance, if we use a polynomial kernel, all feature combinations are implicitly expanded
without loss of generality and increasing the computational costs. Although the mapped feature spaceis quite large, the maximal margin strategy (Vapnik,
1995) of SVMs gives us a good generalization performance compared to the previous manual feature
selection. This is the main reason why kernel-basedlearning has delivered great results to the field of
NLP.
Kernel-based text analysis shows an excellent performance in terms in accuracy; however, its inefficiency in actual analysis limits practical application. For example, an SVM-based NE-chunker runs
at a rate of only 85 byte/sec, while previous rulebased system can process several kilobytes per second (Isozaki and Kazawa, 2002). Such slow execution time is inadequate for Information Retrieval,
Question Answering, or Text Mining, where fast

analysis of large quantities of text is indispensable.
This paper presents two novel methods that makethe kernel-based text analyzers substantially faster.
These methods are applicable not only to the NLP
tasks but also to general machine learning tasks
where training and test examples are represented ina binary vector.
More specifically, we focus on a Polynomial Kernel of degree d, which can attain feature combinations that are crucial to improving the performanceof tasks in NLP. Second, we introduce two fast classification algorithms for this kernel. One is PKI(Polynomial Kernel Inverted), which is an extension of Inverted Index in Information Retrieval. The
other is PKE (Polynomial Kernel Expanded), where
all feature combinations are explicitly expanded. By
applying PKE, we can convert a kernel-based classifier into a simple and fast liner classifier. In orderto build PKE, we extend the PrefixSpan (Pei et al.,2001), an efficient Basket Mining algorithm, to enumerate effective feature combinations from a set of
support examples.
Experiments on English BaseNP Chunking,Japanese Word Segmentation and Japanese Dependency Parsing show that PKI and PKE perform respectively 2 to 13 times and 30 to 300 times fasterthan standard kernel-based systems, without a discernible change in accuracy.

2

Kernel Method and Support Vector
Machines

Suppose we have a set of training data for a binaryclassification problem:(x1 , y1 ), . . . , (xL , yL ) xj ∈ <N , yj ∈ {+1, −1},
where xj is a feature vector of the j-th training sample, and yj is the class label associated with thistraining sample. The decision function of SVMs isdefined by³X

y(x) = sgn´

yj αj φ(xj ) · φ(x) + b ,

(1)

j∈SV

where: (A) φ is a non-liner mapping function from<N to <H (N ¿ H). (B) αj , b ∈ <, αj ≥ 0.
The mapping function φ should be designed suchthat all training examples are linearly separable in<H space. Since H is much larger than N , it requires heavy computation to evaluate the dot products φ(xi ) · φ(x) in an explicit form. This problem
can be overcome by noticing that both constructionof optimal parameter αi (we will omit the detailsof this construction here) and the calculation of thedecision function only require the evaluation of dot
products φ(xi ) · φ(x). This is critical, since, in somecases, the dot products can be evaluated by a simple
Kernel Function: K(x1 , x2 ) = φ(x1 ) · φ(x2 ). Substituting kernel function into (1), we have the following decision function.
³X

y(x) = sgn´

yj αj K(xj , x) + b

(2)

j∈SV

One of the advantages of kernels is that they are notlimited to vectorial object x, but that they are applicable to any kind of object representation, just given
the dot products.

3 Polynomial Kernel of degree d
For many tasks in NLP, the training and test examples are represented in binary vectors; or sets,
since examples in NLP are usually represented in socalled Feature Structures. Here, we focus on suchcases 1 .
Suppose a feature set F = {1, 2, . . . , N } andtraining examples Xj (j = 1, 2, . . . , L), all ofwhich are subsets of F (i.e., Xj ⊆ F ). In thiscase, Xj can be regarded as a binary vector xj =(xj1 , xj2 , . . . , xjN ) where xji = 1 if i ∈ Xj ,xji = 0 otherwise. The dot product of x1 and x2
is given by x1 · x2 = |X1 ∩ X2 |.
Definition 1 Polynomial Kernel of degree dGiven sets X and Y , corresponding to binary feature vectors x and y, Polynomial Kernel of degree d
Kd (X, Y ) is given by
Kd (x, y) = Kd (X, Y ) = (1 + |X ∩ Y |)d ,(3)

where d = 1, 2, 3, . . ..
In this paper, (3) will be referred to as an implicit
form of the Polynomial Kernel.
1

In the Maximum Entropy model widely applied in NLP, weusually suppose binary feature functions fi (Xj ) ∈ {0, 1}. This
formalization is exactly same as representing an example Xj ina set {k|fk (Xj ) = 1}.

It is known in NLP that a combination of features,a subset of feature set F in general, contributes tooverall accuracy. In previous research, feature combination has been selected manually. The use ofa polynomial kernel allows such feature expansion
without loss of generality or an increase in computational costs, since the Polynomial Kernel of degree
d implicitly maps the original feature space F into
F d space. (i.e., φ : F → F d ). This property is
critical and some reports say that, in NLP, the polynomial kernel outperforms the simple linear kernel(Kudo and Matsumoto, 2000; Isozaki and Kazawa,
2002).
Here, we will give an explicit form of the Polynomial Kernel to show the mapping function φ(·).
Lemma 1 Explicit form of Polynomial Kernel.
The Polynomial Kernel of degree d can be rewrittenas
Kd (X, Y ) =dX

cd (r) · |Pr (X ∩ Y )|,

(4)

r=0

where
• Pr (X) is a set of all subsets of X with exactlyr elements in it,• cd (r) =

Pd

l=r

¡d¢³Prl¡ ¢r−m · ml r
m=0 (−1)m´.

Proof See Appendix A.
cd (r) will be referred as a subset weight of the Polynomial Kernel of degree d. This function gives aprior weight to the subset s, where |s| = r.
Example 1 Quadratic and Cubic Kernel
Given sets X = {a, b, c, d} and Y = {a, b, d, e},
the Quadratic Kernel K2 (X, Y ) and the Cubic Kernel K3 (X, Y ) can be calculated in an implicit formas:
K2 (X, Y ) = (1 + |X ∩ Y |)2 = (1 + 3)2 = 16,
K3 (X, Y ) = (1 + |X ∩ Y |)3 = (1 + 3)3 = 64.
Using Lemma 1, the subset weights of the
Quadratic Kernel and the Cubic Kernel can be calculated as c2 (0) = 1, c2 (1) = 3, c2 (2) = 2 andc3 (0) = 1, c3 (1) = 7, c3 (2) = 12, c3 (3) = 6.
In addition, subsets Pr (X ∩ Y ) (r = 0, 1, 2, 3)
are given as follows:
P0 (X ∩ Y )={φ}, P1 (X ∩Y ) = {{a}, {b}, {d}}, P2 (X ∩Y ) ={{a, b}, {a, d}, {b, d}}, P3 (X ∩ Y ) = {{a, b, d}}.
K2 (X, Y ) and K3 (X, Y ) can similarly be calculated in an explicit form as:function PKI classify (X)r = 0 # an array, initialized as 0
foreach i ∈ X
foreach j ∈ h(i)rj = rj + 1
end
end
result = 0
foreach j ∈ SV
result = result + yj αj · (1 + rj )dend
return sgn(result + b)
end

Figure 1: Pseudo code for PKI
K2 (X, Y ) = 1 · 1 + 3 · 3 + 2 · 3 = 16,
K3 (X, Y ) = 1 · 1 + 7 · 3 + 12 · 3 + 6 · 1 = 64.

4

Fast Classifiers for Polynomial Kernel

In this section, we introduce two fast classification
algorithms for the Polynomial Kernel of degree d.
Before describing them, we give the baseline classifier (PKB):³X

y(X) = sgn´

yj αj · (1 + |Xj ∩ X|)d + b . (5)j∈SV

The complexity of PKB is O(|X| · |SV |), since ittakes O(|X|) to calculate (1 + |Xj ∩ X|)d and there
are a total of |SV | support examples.
4.1

PKI (Inverted Representation)

Given an item i ∈ F , if we know in advance theset of support examples which contain item i ∈ F ,we do not need to calculate |Xj ∩ X| for all support
examples. This is a naive extension of Inverted Indexing in Information Retrieval. Figure 1 shows thepseudo code of the algorithm PKI. The function h(i)is a pre-compiled table and returns a set of support
examples which contain item i.
The complexity of the PKI is O(|X| · B + |SV |),where B is an average of |h(i)| over all item i ∈ F .
The PKI can make the classification speed drastically faster when B is small, in other words, whenfeature space is relatively sparse (i.e., B ¿ |SV |).
The feature space is often sparse in many tasks in
NLP, since lexical entries are used as features.
The algorithm PKI does not change the final accuracy of the classification.

4.2 PKE (Expanded Representation)
4.2.1 Basic Idea of PKE
Using Lemma 1, we can represent the decisionfunction (5) in an explicit form:y(X) = sgn³X

yj α j

j∈SV

d
¡X

¢

´

cd (r) · |Pr (Xj ∩ X)| + b .

The algorithm PKE is an approximation of the
PKB, and changes the final accuracy according to
the selection of thresholds σpos and σneg . The calculation of w0 is formulated as the following mining
problem:

r=0

If we, in advance, calculatew(s) =

Xyj αj cd (|s|)I(s ∈ P|s| (Xj ))j∈SV(where I(t) is an indicator function 2 ) for all subsetsSs ∈ dr=0 Pr (F ), (6) can be written as the following
simple linear form:³ X

y(X) = sgn´

w(s) + b .

(7)s∈Γd (X)S

where Γd (X) = dr=0 Pr (X).
The classification algorithm given by (7) will bereferred to as PKE. The complexity of PKE isO(|Γd (X)|) = O(|X|d ), independent on the number of support examples |SV |.
4.2.2 Mining Approach to PKE
To apply the PKE, we first calculate |Γd (F )| degree of vectors
w = (w(s1 ), w(s2 ), . . . , w(s|Γd (F )| )).
This calculation is trivial only when we use a
Quadratic Kernel, since we just project the original feature space F into F × F space, which issmall enough to be calculated by a naive exhaustive
method. However, if we, for instance, use a polynomial kernel of degree 3 or higher, this calculation
becomes not trivial, since the size of feature space
exponentially increases. Here we take the following
strategy:
1. Instead of using the original vector w, we use
w0 , an approximation of w.
2. We apply the Subset Mining algorithm to calculate w0 efficiently.
2

I(t) returns 1 if t is true,returns 0 otherwise.

(6)

Definition 2 w0 : An approximation of w
An approximation of w is given by w0 =(w0 (s1 ), w0 (s2 ), . . . , w0 (s|Γd (F )| )), where w0 (s) is
set to 0 if w(s) is trivially close to 0. (i.e., σneg <w(s) < σpos (σneg < 0, σpos > 0), where σpos andσneg are predefined thresholds).

Definition 3 Feature Combination Mining
Given a set of support examples and subset weight
cd (r), extract all subsets s and their weights w(s) if
w(s) holds w(s) ≥ σpos or w(s) ≤ σneg .
In this paper, we apply a Sub-Structure Mining
algorithm to the feature combination mining problem. Generally speaking, sub-structures mining algorithms efficiently extract frequent sub-structures(e.g., subsets, sub-sequences, sub-trees, or subgraphs) from a large database (set of transactions).
In this context, frequent means that there are no lessthan ξ transactions which contain a sub-structure.
The parameter ξ is usually referred to as the Minimum Support. Since we must enumerate all subsetsof F , we can apply subset mining algorithm, in sometimes called as Basket Mining algorithm, to our task.
There are many subset mining algorithms proposed, however, we will focus on the PrefixSpan algorithm, which is an efficient algorithm for sequential pattern mining, originally proposed by (Pei etal., 2001). The PrefixSpan was originally designed
to extract frequent sub-sequence (not subset) patterns, however, it is a trivial difference since a set
can be seen as a special case of sequences (i.e., bysorting items in a set by lexicographic order, the set
becomes a sequence). The basic idea of the PrefixSpan is to divide the database by frequent sub-patterns(prefix) and to grow the prefix-spanning pattern in a
depth-first search fashion.
We now modify the PrefixSpan to suit to our feature combination mining.
• size constraint
We only enumerate up to subsets of size d.
when we plan to apply the Polynomial Kernelof degree d.

• Subset weight cd (r)In the original PrefixSpan, the frequency ofeach subset does not change by its size. However, in our mining task, it changes (i.e., thefrequency of subset s is weighted by cd (|s|)).
Here, we process the mining algorithm byassuming that each transaction (support example Xj ) has its frequency Cd yj αj , where
Cd = max(cd (1), cd (2), . . . , cd (d)). The
weight w(s) is calculated by w(s) = ω(s) ×
cd (|s|)/Cd , where ω(s) is a frequency of s,
given by the original PrefixSpan.
• Positive/Negative support examples
We first divide the support examples into positive (yi > 0) and negative (yi < 0) examples,and process mining independently. The result
can be obtained by merging these two results.
• Minimum Supports σpos , σneg
In the original PrefixSpan, minimum support isan integer. In our mining task, we can give areal number to minimum support, since eachtransaction (support example Xj ) has possibly
non-integer frequency Cd yj αj . Minimum supports σpos and σneg control the rate of approximation. For the sake of convenience, we justgive one parameter σ, and calculate σpos andσneg as follows

σneg³ #of positive examples ´,#of support examples³ #of negative examples ´= −σ ·.
#of support examples

σpos = σ ·After the process of mining, a set of tuples Ω ={hs, w(s)i} is obtained, where s is a frequent subset
and w(s) is its weight. We use a TRIE to efficiently
store the set Ω. The example of such TRIE compression is shown in Figure 2. Although there are many
implementations for TRIE, we use a Double-Array(Aoe, 1989) in our task. The actual classification of
PKE can be examined by traversing the TRIE for all
subsets s ∈ Γd (X).

5

Experiments

To demonstrate performances of PKI and PKE, we
examined three NLP tasks: English BaseNP Chunking (EBC), Japanese Word Segmentation (JWS) and

1

s



 
          


 
 
 
 

!#"$"&%
'(#) *


'+,'-+


. '-+






. '0





. '-(#) *

. +-/

. '-+

Figure 2: Ω in TRIE representation

Japanese Dependency Parsing (JDP). A more detailed description of each task, training and test data,
the system parameters, and feature sets are presented
in the following subsections. Table 1 summarizes
the detail information of support examples (e.g., sizeof SVs, size of feature set etc.).
Our preliminary experiments show that a
Quadratic Kernel performs the best in EBC, and a
Cubic Kernel performs the best in JWS and JDP.
The experiments using a Cubic Kernel are suitableto evaluate the effectiveness of the basket mining
approach applied in the PKE, since a Cubic Kernel
projects the original feature space F into F 3 space,which is too large to be handled only using a naive
exhaustive method.
All experiments were conducted under Linux using XEON 2.4 Ghz dual processors and 3.5 Gbyte ofmain memory. All systems are implemented in C++.
5.1

English BaseNP Chunking (EBC)

Text Chunking is a fundamental task in NLP – dividing sentences into non-overlapping phrases. BaseNP
chunking deals with a part of this task and recognizes the chunks that form noun phrases. Here is an
example sentence:[He] reckons [the current account deficit]
will narrow to [only $ 1.8 billion] .

A BaseNP chunk is represented as sequence ofwords between square brackets. BaseNP chunking
task is usually formulated as a simple tagging task,
where we represent chunks with three types of tags:
B: beginning of a chunk. I: non-initial word. O:
outside of the chunk. In our experiments, we used
the same settings as (Kudo and Matsumoto, 2002).
We use a standard data set (Ramshaw and Marcus,
1995) consisting of sections 15-19 of the WSJ corpus as training and section 20 as testing.

5.2 Japanese Word Segmentation (JWS)

5.4

Results

Tables 2, 3 and 4 show the execution time, accuracy4 , and |Ω| (size of extracted subsets), by changing σ from 0.01 to 0.0005.
The PKI leads to about 2 to 12 times improvements over the PKB. In JDP, the improvement is significant. This is because B, the average of h(i) overLet s = c1 c2 · · · cm be a sequence of Japanese all items i ∈ F , is relatively small in JDP. The imcharacters, t = t1 t2 · · · tm be a sequence of Japanese provement significantly depends on the sparsity ofcharacter types 3 associated with each character, the given support examples.
and yi ∈ {+1, −1}, (i = (1, 2, . . . , m − 1)) be a
The improvements of the PKE are more signifiboundary marker. If there is a boundary between ci cant than the PKI. The running time of the PKE isand ci+1 , yi = 1, otherwise yi = −1. The feature 30 to 300 times faster than the PKB, when we set an
set of example xi is given by all characters as well appropriate σ, (e.g., σ = 0.005 for EBC and JWS,
as character types in some constant window (e.g., 5): σ = 0.0005 for JDP). In these settings, we could{ci−2 , ci−1 , · · · , ci+2 , ci+3 , ti−2 , ti−1 , · · · , ti+2 , ti+3 }. preserve the final accuracies for test data.
Note that we distinguish the relative position ofeach character and character type. We use the Kyoto 5.5 Frequency-based Pruning
University Corpus (Kurohashi and Nagao, 1997), The PKE with a Cubic Kernel tends to make Ω large
7,958 sentences in the articles on January 1st to (e.g., |Ω| = 2.32 million for JWS, |Ω| = 8.26 milJanuary 7th are used as training data, and 1,246 lion for JDP).
sentences in the articles on January 9th are used as
To reduce the size of Ω, we examined simthe test data.
ple frequency-based pruning experiments. Our extension is to simply give a prior threshold ξ(=
1, 2, 3, 4 . . .), and erase all subsets which occur in
5.3 Japanese Dependency Parsing (JDP)
less than ξ support examples. The calculation of frequency can be similarly conducted by the PrefixSThe task of Japanese dependency parsing is to idenpan algorithm. Tables 5 and 6 show the results oftify a correct dependency of each Bunsetsu (basefrequency-based pruning, when we fix σ=0.005 forphrase in Japanese). In previous research, we preJWS, and σ=0.0005 for JDP.
sented a state-of-the-art SVMs-based Japanese deIn JDP, we can make the size of set Ω about one
pendency parser (Kudo and Matsumoto, 2002). We
thirdof the original size. This reduction gives us
combined SVMs into an efficient parsing algorithm,
notonly
a slight speed increase but an improvement
Cascaded Chunking Model, which parses a sentence
deterministically only by deciding whether the cur- of accuracy (89.29%→89.34%). Frequency-based
rent chunk modifies the chunk on its immediate right pruning allows us to remove subsets that have large
hand side. The input for this algorithm consists of weight and small frequency. Such subsets may be
a set of the linguistic features related to the head generated from errors or special outliers in the trainand modifier (e.g., word, part-of-speech, and inflec- ing examples, which sometimes cause an overfitting
tions), and the output from the algorithm is either of in training.
In JWS, the frequency-based pruning does not
the value +1 (dependent) or -1 (independent). We
use a standard data set, which is the same corpus de- work well. Although we can reduce the sizeof Ω by half, the accuracy is also reduced
scribed in the Japanese Word Segmentation.
(97.94%→97.83%). It implies that, in JWS, featureseven with frequency of one contribute to the final de3
Usually, in Japanese, word boundaries are highly concision hyperplane.
Since there are no explicit spaces between words inJapanese sentences, we must first identify the wordboundaries before analyzing deep structure of a sentence. Japanese word segmentation is formalized asa simple classification task.

strained by character types, such as hiragana and katakana(both are phonetic characters in Japanese), Chinese characters,
English alphabets and numbers.

4

In EBC, accuracy is evaluated using F measure, harmonicmean between precision and recall.

Table 1: Details of Data Set
EBC
JWS
JDP
# of examples
135,692 265,413 110,355|SV| # of SVs
11,69057,672
34,996# of positive SVs
5,637
28,44017,528# of negative SVs
6,053
29,232
17,468|F | (size of feature)
17,47011,64328,157
Avg. of |Xj |
11.90
11.73
17.63
B (Avg. of |h(i)|))
7.74
58.13
21.92
Data Set

PKE
σ
0.01
0.005
0.001
0.0005PKI
PKB

Table 2: Results of EBC
Time
SpeedupF1(sec./sent.)
Ratio
0.0016105.2 93.79
0.0016101.3 93.85
0.001797.7
93.84
0.0017
96.8
93.84
0.020
8.3
93.84
0.164
1.0
93.84

|Ω|
(× 1000)

518
668
858
889

(Note: In EBC, to handle K-class problems, we use a pairwiseclassification; building K×(K−1)/2 classifiers considering allpairs of classes, and final class decision was given by majority
voting. The values in this column are averages over all pairwiseclassifiers.)

6

Discussion

There have been several studies for efficient classification of SVMs. Isozaki et al. propose an XQK(eXpand the Quadratic Kernel) which can make theirNamed-Entity recognizer drastically fast (Isozaki
and Kazawa, 2002). XQK can be subsumed into
PKE. Both XQK and PKE share the basic idea; allfeature combinations are explicitly expanded and weconvert the kernel-based classifier into a simple linear classifier.
The explicit difference between XQK and PKE isthat XQK is designed only for Quadratic Kernel. It
implies that XQK can only deal with feature combination of size up to two. On the other hand, PKE
is more general and can also be applied not only to
the Quadratic Kernel but also to the general-style ofpolynomial kernels (1 + |X ∩ Y |)d . In PKE, there
are no theoretical constrains to limit the size of combinations.
In addition, Isozaki et al. did not mention how to
expand the feature combinations. They seem to use
a naive exhaustive method to expand them, which is
not always scalable and efficient for extracting threeor more feature combinations. PKE takes a basket
mining approach to enumerating effective feature
combinations more efficiently than their exhaustive
method.

7

Conclusion and Future Works

We focused on a Polynomial Kernel of degree d,which has been widely applied in many tasks in NLP

PKE
σ
0.01
0.005
0.001
0.0005
PKI
PKB

PKE
σ
0.01
0.005
0.001
0.0005PKI
PKB

Table 3: Results of JWS
Time
Speedup Acc.(%)(sec./sent.)
Ratio
0.0024358.2
97.93
0.0028300.1
97.95
0.0034242.6
97.94
0.0035238.8
97.94
0.49891.7
97.94
0.8535
1.0
97.94
Table 4: Results of JDP
Time
Speedup Acc.(%)(sec./sent.)
Ratio
0.004266.8
88.91
0.006047.8
89.05
0.008633.3
89.26
0.009031.8
89.29
0.022612.6
89.29
0.2848
1.0
89.29

|Ω|
(× 1000)

1,228
2,327
4,392
4,820

|Ω|
(× 1000)

73
1,924
6,686
8,262

Table 5: Frequency-based pruning (JWS)
PKE
time
Speedup Acc.(%)|Ω|ξ (sec./sent.)
Ratio(× 1000)
1
0.0028
300.1
97.95
2,327
2
0.0025
337.3
97.83
954
3
0.0023
367.0
97.83
591
PKB
0.8535
1.0
97.94
Table 6: Frequency-based pruning (JDP)
PKE
time
Speedup Acc.(%)|Ω|ξ (sec./sent.)
Ratio(× 1000)1
0.0090
31.8
89.29
8,262
2
0.0072
39.3
89.34
2,450
3
0.0068
41.8
89.31
1,360
PKB
0.28481.0
89.29

and can attain feature combination that is crucial to
improving the performance of tasks in NLP. Then,
we introduced two fast classification algorithms forthis kernel. One is PKI (Polynomial Kernel Inverted), which is an extension of Inverted Index. The
other is PKE (Polynomial Kernel Expanded), where
all feature combinations are explicitly expanded.
The concept in PKE can also be applicable to kernels for discrete data structures, such as String Kernel (Lodhi et al., 2002) and Tree Kernel (Kashima
and Koyanagi, 2002; Collins and Duffy, 2001).
For instance, Tree Kernel gives a dot product ofan ordered-tree, and maps the original ordered-tree
onto its all sub-tree space. To apply the PKE, wemust efficiently enumerate the effective sub-trees
from a set of support examples. We can similarly
apply a sub-tree mining algorithm (Zaki, 2002) tothis problem.

Appendix A.: Lemma 1 and its proof
cd (r) =d µ ¶³ r
X
X
d

l

l=r

(−1)r−m · ml

µ ¶´

m=0

r
m

.

Proof.
Let X, Y be subsets of F = {1, 2, . . . , N }. In this case, |X ∩Y | is same as the dot product of vector x, y, wherex = {x1 , x2 , . . . , xN }, y = {y1 , y2 , . . . , yN }(xj , yj ∈ {0, 1})
xj = 1 if j ∈ X, xj = 0 otherwise.
(1 + |X ∩ Y |)d = (1 + x · y)d can be expanded as follows(1 + x · y)d=d µ ¶³X
N
X
d

l

l=0

=

d µ ¶
X
d

l

l=0

´l
x j yjk1 +...+kN =l

X

kn ≥0

· τ (l)l!
(x1 y1 )k1 . . . (xN yN )kN .
k1 ! . . . kN !

Note that xj j is binary (i.e., xj j ∈ {0, 1}), the number of r-size subsets can be given by a coefficient of(x1 y1 x2 y2 . . . xr yr ). Thus,

cd (r)=d µ ¶µ k1 +...+kX
X r =ldl=rlkn ≥1,n=1,2,...,rl!
k1 ! . . . kr !

=

l

r
r −
(r−1) +(r−2)l − . . .
12

d µ ¶³ X
r
X
d
l=r

l

(−1)r−m · ml

m=0

µ ¶´
r
m

. 2

References
Junichi Aoe. 1989. An efficient digital search algorithm by using a double-array structure. IEEE Transactions on Software
Engineering, 15(9).
Michael Collins and Nigel Duffy. 2001. Convolution kernels
for natural language. In Advances in Neural Information
Processing Systems 14, Vol.1 (NIPS 2001), pages 625–632.
Hideki Isozaki and Hideto Kazawa. 2002. Efficient support
vector classifiers for named entity recognition. In Proceedings of the COLING-2002, pages 390–396.
Hisashi Kashima and Teruo Koyanagi. 2002. Svm kernels
for semi-structured data. In Proceedings of the ICML-2002,
pages 291–298.
Taku Kudo and Yuji Matsumoto. 2000. Japanese Dependency
Structure Analysis based on Support Vector Machines. In
Proceedings of the EMNLP/VLC-2000, pages 18–25.
Taku Kudo and Yuji Matsumoto. 2001. Chunking with support
vector machines. In Proceedings of the the NAACL, pages
192–199.
Taku Kudo and Yuji Matsumoto. 2002. Japanese dependency
analyisis using cascaded chunking. In Proceedings of the
CoNLL-2002, pages 63–69.
Sadao Kurohashi and Makoto Nagao. 1997. Kyoto University
text corpus project. In Proceedings of the ANLP-1997, pages
115–118.
Huma Lodhi, Craig Saunders, John Shawe-Taylor, Nello Cristianini, and Chris Watkins. 2002. Text classification using
string kernels. Journal of Machine Learning Research, 2.

Jian Pei, Jiawei Han, and et al. 2001. Prefixspan: Mining
sequential patterns by prefix-projected growth. In Proc. ofInternational Conference of Data Engineering, pages 215–
224.

k

k

l=r

µ ¶

l

Tetsuji Nakagawa, Taku Kudo, and Yuji Matsumoto. 2002. Revision learning and its application to part-of-speech tagging.
In Proceedings of the ACL 2002, pages 497–504.

j=1

where
τ (l) ==µ ¶d µ ¶µXdrl¶

Lance A. Ramshaw and Mitchell P. Marcus. 1995. Text chunking using transformation-based learning. In Proceedings of
the VLC, pages 88–94.
Vladimir N. Vapnik. 1995. The Nature of Statistical Learning
Theory. Springer.
Mohammed Zaki. 2002. Efficiently mining frequent trees in aforest. In Proceedings of the 8th International Conferenceon Knowledge Discovery and Data Mining KDD, pages 71–
80.

¶