Polynomial to Linear: Efficient Classification with Conjunctive Features
Naoki Yoshinaga
Institute of Industrial Science
University of Tokyo
4-6-1 Komaba, Meguro-ku, Tokyo

Masaru Kitsuregawa
Institute of Industrial Science
University of Tokyo
4-6-1 Komaba, Meguro-ku, Tokyoynaga@tkl.iis.u-tokyo.ac.jp

kitsure@tkl.iis.u-tokyo.ac.jp

Abstract
This paper proposes a method that speeds
up a classifier trained with many conjunctive features: combinations of (primitive) features. The key idea is to precompute as partial results the weights ofprimitive feature vectors that appear frequently in the target NLP task. A trie
compactly stores the primitive feature vectors with their weights, and it enables theclassifier to find for a given feature vector its longest prefix feature vector whose
weight has already been computed. Experimental results for a Japanese dependency parsing task show that our method
speeded up the SVM and LLM classifiersof the parsers, which achieved accuracy of
90.84/90.71%, by a factor of 10.7/11.6.

1

Introduction

Deep and accurate text analysis based on discriminative models is not yet efficient enough as a component of real-time applications, and it is inadequate to process Web-scale corpora for knowledge
acquisition (Pantel, 2007; Saeger et al., 2009) or
semi-supervised learning (McClosky et al., 2006;
Spoustová et al., 2009). One of the main reasonsfor this inefficiency is attributed to the inefficiency
of core classifiers trained with many feature combinations (e.g., word n-grams). Hereafter, we referto features that explicitly represent combinationsof features as conjunctive features and the otheratomic features as primitive features.
The feature combinations play an essential rolein obtaining a classifier with state-of-the-art accuracy for several NLP tasks; recent examples include dependency parsing (Koo et al., 2008), parsere-ranking (McClosky et al., 2006), pronoun resolution (Nguyen and Kim, 2008), and semantic rolelabeling (Liu and Sarkar, 2007). However, ‘explicit’ feature combinations significantly increase

the feature space, which slows down not only
training but also testing of the classifier.
Kernel-based methods such as support vector
machines (SVMs) consider feature combinations
space-efficiently by using a polynomial kernel
function (Cortes and Vapnik, 1995). The kernelbased classification is, however, known to be very
slow in NLP tasks, so efficient classifiers should
sum up the weights of the explicit conjunctive features (Isozaki and Kazawa, 2002; Kudo and Matsumoto, 2003; Goldberg and Elhadad, 2008).
`1 -regularized log-linear models (`1 - LLMs), on
the other hand, provide sparse solutions, in whichweights of irrelevant features are exactly zero, by
assuming a Laplacian prior on the weights (Tibshirani, 1996; Kazama and Tsujii, 2003; Goodman,
2004; Gao et al., 2007). However, as Kazama andTsujii (2005) have reported in a text categorization
task and we later confirm in a dependency parsing task, when most features regarded as irrelevant
during training `1 - LLMs appear rarely in the task,
we cannot greatly reduce the number of active features in each classification. In the end, when efficiency is a major concern, we must use exhaustive
feature selection (Wu et al., 2007; Okanohara andTsujii, 2009) or even restrict the order of conjunctive features at the expense of accuracy.
In this study, we provide a simple, but effective
solution to the inefficiency of classifiers trainedwith higher-order conjunctive features (or polynomial kernel), by exploiting the Zipfian nature oflanguage data. The key idea is to precompute theweights of primitive feature vectors and use themas partial results to compute the weight of a givenfeature vector. We use a trie called the feature
sequence trie to efficiently find for a given feature vector its longest prefix feature vector whose
weight has been computed. The trie is built fromfeature vectors generated by applying the classifierto actual data in the classification task. The timecomplexity of the classifier approaches time that

is linear with respect to the number of primitive
features when the retrieved feature vector covers
most of the features in the input feature vector.
We implemented our algorithm for SVM and
LLM classifiers and evaluated the performance ofthe resulting classifiers in a Japanese dependency
parsing task. Experimental results show that it
successfully speeded up classifiers trained withhigher-order conjunctive features by a factor of 10.
The rest of this paper is organized as follows.
Section 2 introduces LLMs and SVMs. Section 3
proposes our classification algorithm. Section 4
presents experimental results. Section 5 concludes
with a summary and addresses future directions.

2

where fi,y (x, y) is a feature function that returns
a non-zero value when fi (x) = 1 and the label isy, wi,y ∈PR is a P
weight associated with fi,y , andZ(x) = y exp i wi,y fi,y (x, y) is the partition
function. We can consider feature combinations in
LLM s by explicitly introducing a new conjunctive
feature fF 0 ,y (x, y) that is activated when a particular set of features F 0 ⊆ F to V
be combined is activated (namely, fF 0 ,y (x, y) = fi,y ∈F 0 fi,y (x, y)).
We then introduce an `1 -regularized LLM (`1 LLM ), in which the weight vector w is tuned so
as to maximize the logarithm of the a posteriori
probability of the training data:
L(w) =

Preliminaries

LX

log p(yi |xi ) − Ckwk1 .

(2)

i=1

In this paper, we focus on linear classifiers that calculate the probability (or score) by summing up
weights of individual features. Examples include
not only log-linear models but also support vector machines with kernel expansion (Isozaki and
Kazawa, 2002; Kudo and Matsumoto, 2003). Below, we introduce these two classifiers and theirways to consider feature combinations.
In classification-based NLP, the target task ismodeled as one or more classification steps. For
example in part-of-speech (POS) tagging, eachclassification decides whether to assign a particular label (POS tag) to a given sample (each word
in a given sentence). Each sample is then represented by a feature vector x, whose element xi isa value of a feature function fi ∈ F.
Here, we assume a binary feature functionfi (x) ∈ {0, 1}, in which a non-zero value meansthat particular context data appears in the sample.
We say that a feature fi is active in sample x whenxi = fi (x) = 1 and |x| represents the number ofactive features in x (|x| = |{fi |fi (x) = 1}|).
2.1

Log-Linear Models

The log-linear model (LLM), or also known as
maximum-entropy model (Berger et al., 1996), isa linear classifier widely used in the NLP literature.
Let the training data of LLMs be {hxi , yi i}L
i=1 ,nwhere xi ∈ {0, 1} is a feature vector and yi is aclass label associated with xi . We assume a binary
label yi ∈ {±1} here to simplify the argument.
The classifier provides conditional probabilityp(y|x) for a given feature vector x and a label y:p(y|x) =X
1
exp
wi,y fi,y (x, y), (1)Z(x)
iHyper-parameter C thereby controls the degree ofover-fitting (solution sparseness). Interested readers may refer to the cited literature (Andrew andGao, 2007) for the optimization procedures.
2.2

Support Vector Machines

A support vector machine (SVM) is a binary classifier (Cortes and Vapnik, 1995). Training withnsamples {hxi , yi i}L
i=1 where xi ∈ {0, 1} andyi ∈ {±1} yields the following decision function:y(x) = sgn(g(x) + b)
Xg(x) =
yj αj φ(xj )T φ(x),(3)

xj ∈SV

where b ∈ R, φ : Rn 7→ RH and support vectors xj ∈ SV (subset of training samples), eachof which is associated with weight αj ∈ R. We
hereafter call g(x) the weight function. Nonlinear
mapping function φ is chosen to make the training samples linearly separable in RH space. Kernel function k(xj , x) = φ(xj )T φ(x) is then introduced to compute the dot product in RH space
without mapping x to φ(x).
To consider combinations of primitive features
fj ∈ F, we use a polynomial kernel kd (xj , x) =d(xTj x + 1) . From Eq. 3, we obtain the weightfunction for the polynomial kernel as:
Xdg(x) =
yj αj (xT(4)
j x + 1) .
xj ∈SV

Since we assumed that xi is a binary value representing whether a (primitive) feature fi is activein the sample, the polynomial kernel of degree d
implies a mapping φd from x to φd (x) that hasP
H = dk=0 nk dimensions. Each dimension represents a (weighted) conjunction of d features in
the original sample x.1
Kernel Expansion (SVM - KE) The time complexity of Eq. 4 is O(|x| · |SV|). This cost is usually high for classifiers used in NLP tasks because
they often have many support vectors (|SV| >10, 000). Kernel expansion (KE) was proposedby Isozaki and Kazawa (2002) to convert Eq. 4
into the linear sum of the weights in the mappedfeature space as in LLM (p(y|x) in Eq. 1):
g(x) = wT xd =X

wi xdi ,(5)

iwhere xd is a binary feature vector whose element
xdi has a non-zero value when (φd (x))i > 0, w
is the weight vector for xd in the expanded feature space F d and is precalculated from the support vectors xj and their weights αj . Interested
readers may refer to Kudo and Matsumoto (2003)
for the detailed computation for obtaining w.
The time complexity of Eq. 5 (and Eq. 1) isO(|xd |), which is linear with respect to the number of active features in xd within the expandedfeature space F d .
Heuristic Kernel Expansion (SVM - HKE) To
make the weight vector sparse, Kudo and Matsumoto (2003) proposed a heuristic method thatfilters out less useful features whose absoluteweight values are less than a pre-defined threshold
σ.2 They reported that increased threshold value σ
resulted in a dramatically sparse feature space F d ,which had the side-effects of accuracy degradationand classifier speed-up.

3

Proposed Method

In this section, we propose a method that speeds
up a classifier trained with many conjunctive features. Below, we focus on a kernel-based classifier
trained with a polynomial kernel of degree d (here,
1
For example, given an input vector x = (x1 , x2 )T
and a support vector x0 = (x01 , x02 )T , the 2nd-orderpolynomial kernel returns k2 (x0 , x) = (x01 x1 + x02 x2 +1)2 = 3x01 x1 + 3x02 x2 + 2x01 x1 x02 x2 + 1 (∵ x0i , xi ∈{0, √1}). This
thus implies a mapping φ2 (x) =√ function√(1, 3x1 , 3x2 , 2x1 x2 )T . In the following argument, we
ignore the dimension of the constant in the mapped space andassume constant b is set to include it.
2
Precisely speaking, they set different thresholds to positive (αj > 0) and negative (αj < 0) support vectors, considering the proportion of positive and negative support vectors.

Figure 1: Efficient computation of g(x).
SVM s), but an analogous argument is possible forlinear classifiers (e.g., LLMs).3
We hereafter represent a binary feature vector x
as a set of active features {fi |fi (x) = 1}. x canthereby be represented as an element of the power
set 2F of the set of features F.
3.1

Idea

Let us remember that weight function g(x) in
Eq. 5 maps x ∈ 2F to W ∈ R. If we could calculate Wx = g(x) for all possible x in advance,
we could obtain g(x) by simply checking |x| elements, namely, in O(|x|) time. However, because|{x|x ∈ 2F }| = 2|F | and |F| is likely to be verylarge (often |F| > 10, 000 in NLP tasks), this calculation is impractical.
We then compute and store weight Wx0 =g(x0 ) for x0 ∈ Vc (⊂ 2F ), a certain subset ofthe possible value space, and compute g(x) forx ∈/ Vc by using precalculated weight Wxc forxc ⊆ 4 x in the following way:X
g(x) = Wxc +wi .
(6)
fi ∈xd −xdc

Intuitively speaking, starting from partial weightWxc , we add up remaining weights of primitive
features f ∈ F that are not active in xc but activein x and conjunctive features that combine f andthe other active features in x.
An example of this computation (d = 2) is depicted in Figure 1. We can efficiently computeg(x) for a vector x that has four active features
f1 , f2 , f3 , and f4 (and x2 has their six conjunctive features) using precalculated weight W{1,2,3} ;we should first check the three features f1 , f2 , andf3 to retrieve W{1,2,3} and next check the remaining four features related to f4 , namely f4 , f1,4 ,
f2,4 , and f3,4 , in order to add up the remaining
3

When a feature vector x includes (explicit) conjunctive
features f ∈ F d , we assume weight function g 0 (y|x0 ) =dg(y|x), where x0 is a projection of x (by φ−1
d : F → F ).
4
This means that all active features in xc are active in x.

weights, while the normal computation in Eq. 5
should check the four primitive and six conjunctive features to get the individual weights.
Expected time complexity Counting the number of features to be checked in the computation,
we obtain the time complexity f (x, d) of Eq. 6 as:
f (x, d) = O(|xc | + |xd | − |xdc |),

d 
X
|x|
d
where |x | =
k

(7)
(8)

k=1

2

3

(e.g., |x2 | = |x| 2+|x| and |x3 | = |x| +5|x|).5 Note
6that when |xc | becomes close to |x|, this timecomplexity actually approaches O(|x|).
Thus, to minimize this computational cost, xc
is to be chosen from Vc as follows:
xc = argmin (|x0 | + |xd | − |x0d |).
Construction of Feature Sequence Trie

There are two issues with speeding up the classifier by the computation shown in Eq. 6. First, since
we can store weights for only a small fraction of
possible feature vectors (namely, |Vc |  2|F | ), weshould choose Vc so as to maximize its impact on
the speed-up. Second, we should quickly find an
optimal xc from Vc for a given feature vector x.
The solution to the first problem is to enumerate partial feature vectors that frequently appear in
the target task. Note that typical linguistic features
used in NLP tasks usually consist of disjunctive
sets of features (e.g., word surface and POS), in
which each set is likely to follow Zipf’s law (Zipf,
1949) and correlate with each other. We can expect the distribution of feature vectors, the mixtureof Zipf distributions, to be Zipfian. This has been
confirmed for word n-grams (Egghe, 2000) anditemset support distribution (Chuang et al., 2008).
We can thereby expect that a small set of partial
feature vectors commonly appear in the task.
To solve the second problem, we introduce afeature sequence trie (fstrie), which represents ahierarchy of feature vectors, to enable the classifier to efficiently retrieve (sub-)optimal xc (inEq. 9) for a given feature vector x. We build an
fstrie in the following steps:
Step 1: Apply the target classifier to actual (raw)data in the task to enumerate possible feature
vectors (hereafter, source feature vectors).
5

Step 2: Sort the features in each source feature
vector according to their frequency in the
training data (in descending order).
Step 3: Build a trie from the source feature vectors by regarding feature indices as charactersand store weights of all prefix feature vectors.

(9)x0 ∈Vc ,x0 ⊆x

3.2

Figure 2: Feature sequence trie and completion ofprefix feature vector weights.

This is the maximum number of conjunctive features.

An fstrie built from six source feature vectors isshown in Figure 2. In fstries, a path from the root
to another node represents a feature vector. An
important point here is that the fstrie stores theweights of all prefix feature vectors of the source
feature vectors, and the trie structure enables us toretrieve for a given feature vector x the weight of
its longest prefix vector xc ⊆ x in O(|xc |) time.
To handle feature functions in P
LLM s (Eq. 1), westore partial weight Wxc ,y =i wi,y fi,y (xc , y)for each label y on the node that expresses xc .
Since we sort the features in the source feature vectors according to their frequency, the prefix feature vectors exclude less frequent featuresin the source feature vectors. Lexical features orfiner-grained features (e.g., POS-subcategory) areusually less frequent than coarse-grained features(e.g., POS), so they lie in the latter part of thefeature vectors. This sorting helps us to retrieve
longer feature vector xc for input feature vector xthat will have diverse infrequent features. It also
minimizes the size of fstrie by sharing the common frequent prefix (e.g., {f1 , f2 } in Figure 2).
Pruning nodes from fstrie We have so far described the way to construct an fstrie from thesource feature vectors. However, a naive enumeration of source feature vectors will result in the
explosion of the fstrie size, and we want to havea principled way to control the fstrie size rather
than reducing the processed data size. Below, we
present a method that prunes useless prefix feature
vectors (nodes) from the constructed fstrie to maximize its impact on the classifier efficiency.

Algorithm 1 P RUNE N ODES FROM F STRIE
Input: fstrie T , node_limit N ∈ N
Output: fstrie T
1: while # of nodes in T > N do2:
xc ← argmin u(x0 )x0 ∈leaf(T )3:remove xc , T

4: end while
5: return T

We adopt a greedy strategy that iteratively
prunes a leaf node (one prefix feature vector andits weight) from the fstrie built from all the source
feature vectors, according to a certain utility score
calculated for each node. In this study, we consider two metrics for each prefix feature vector xc
to calculate its utility score.
Probability p(xc ), which denotes how often thestored weight Wxc will be used in the target task. The maximum-likelihood estimation provides probability:Px0 ⊇x nx0,(10)p(xc ) = P c
x nx
where nx ∈ N is the frequency count of asource feature vector x in the processed data.
Computation reduction ∆d (xc ), which denotes
how much computation is reduced by Wxc to
calculate a weight of x ⊇ xc . This can be estimated by counting the number of conjunctive features we additionally have to checkwhen we remove xc . Since the fstrie storesthe weight of a prefix feature vector xc- ⊂ xc
such that |xc- | = |xc | − 1 (e.g., in Figure 2,
xc- = {f1 , f2 } for xc = {f1 , f2 , f4 }), we
can define the computation reduction as:∆d (xc ) = (|xdc | − |xdc- |) − (|xc | − |xc- |)
 X

d 
d 
X
|xc | − 1
|xc |
−
=
k
k
k=2

k=2

(∵ Eq. 8).
2∆2 (xc ) = |xc | − 1 and ∆3 (xc ) = |xc | 2−|xc | .
We calculate utility score of each node xc in the
fstrie as u(xc ) = p(xc ) · ∆d (xc ), which means
the expected computation reduction by xc in thetarget task, and prune the lowest-utility-score leaf
nodes from the fstrie one by one (Algorithm 1). If
several prefix vectors have the same utility score,
we eliminate them in numerical descending order.

Algorithm 2 C OMPUTE W EIGHT WITH F STRIEdInput: fstrie T , weight vector w ∈ R|F |feature vector x ∈ 2F
Output: weight W = g(x) ∈ R
1: x ← sort(x)2: hxc , Wxc i ← prefix_search(T , x)
3: W ← Wxc
4: for all feature fj ∈ xd − xdc do
5:
W ← W + wj
6: end for7: return W
3.3

Classification Algorithm

Our classification algorithm is shown in detail in
Algorithm 2. The classifier first sorts the active
features in input feature vector x according to theirfrequency in the training data. Then, for x, it retrieves the longest common prefix vector xc fromthe fstrie (line 2 in Algorithm 2). It then adds theweights of the remaining features to partial weightWxc (line 5 in Algorithm 2).
Note that the remaining features whose weights
we sum up (line 4 in Algorithm 2) are primitiveand conjunctive features that relate to f ∈ x − xc ,which appear less frequently than f 0 ∈ xc in the
training data. Thus, when we apply our algorithm
to classifiers with the sparse solution (e.g., SVM HKE s or `1 - LLM s), |xd |−|xdc | can be much smaller
than the theoretical expectation (Eq. 8). We confirmed this in the following experiments.

4

Evaluation

We applied our algorithm to SVM - KE, SVM - HKE,and `1 - LLM classifiers and evaluated the resultingclassifiers in a Japanese dependency parsing task.
To the best of our knowledge, there are no previous
reports of an exact weight calculation faster thanlinear summation (Eqs. 1 and 5). We also compared our SVM classifier with a classifier calledpolynomial kernel inverted (PKI: Kudo and Matsumoto (2003)), which uses the polynomial kernel(Eq. 4) and inverted indexing to support vectors.
4.1

Experimental Settings

A Japanese dependency parser inputs bunsetsusegmented sentences and outputs the correct head(bunsetsu) for each bunsetsu; here, a bunsetsu is
a grammatical unit in Japanese consisting of one
or more content words followed by zero or morefunction words. A parser generates a feature vec-

Modifier, head word (surface-form, POS, POS-subcategory,
modifiee inflection form), functional word (surface-form,
bunsetsu POS, POS-subcategory, inflection form), brackets,
quotation marks, punctuation marks, position insentence (beginning, end)
Between distance (1, 2–5, 6–), case-particles, brackets,bunsetsus quotation marks, punctuation marks

Table 1: Feature set used for experiments.
tor for a particular pair of bunsetsus (modifier andmodifiee candidates) by exploiting the head-final
and projective (Nivre, 2003) nature of dependency
relations in Japanese. The classifier then outputs
label y = ‘+1’ (dependent) or ‘−1’ (independent).
Since our classifier is independent of individual parsing algorithms, we targeted speeding up(a classifier in) the shift-reduce parser proposedby Sassano (2004), which has been reported to be
the most efficient for this task, with almost stateof-the-art accuracy (Iwatate et al., 2008). Thisparser decreases the number of classification steps
by using the fact that a bunsetsu is likely to modify
a bunsetsu close to itself. Due to space limitations,
we omit the details of the parsing algorithm.
We used the standard feature set tailored for thistask (Kudo and Matsumoto, 2002; Sassano, 2004;
Iwatate et al., 2008) (Table 1). Note that featureslisted in the ‘Between bunsetsus’ row represent
contexts between the target pair of bunsetsus andappear independently from other features, which
will become an obstacle to finding the longest prefix vector. This task is therefore a better measureof our method than simple sequential labeling suchas POS tagging or named-entity recognition.
For evaluation, we used Kyoto Text Corpus Version 4.0 (Kurohashi and Nagao, 2003), Mainichinews articles in 1995 that have been manually annotated with dependency relations.6 The training, development, and test sets included 24,283,
4833, and 9284 sentences, and 234,685, 47,571,
and 89,874 bunsetsus, respectively. The training
samples generated from the training set included
150,064 positive and 146,712 negative samples.
The following experiments were performed ona server with an Intel R XeonTM 3.20-GHz CPU.
We used TinySVM7 and a simple C ++ library for
maximum entropy classification8 to train SVMs
and `1 - LLMs, respectively. We used Darts-Clone,9
6

http://nlp.kuee.kyoto-u.ac.jp/nl-resource/corpus-e.html
http://chasen.org/˜taku/software/TinySVM/
8
http://www-tsujii.is.s.u-tokyo.ac.jp/˜tsuruoka/maxent/9
http://code.google.com/p/darts-clone/7

Model type
Model statistics
Dep. Sent.
Model
d ω/σ
|F d ||xd |acc. acc.
SVM - KE 1 039712
27.3 88.29 46.49
SVM - KE 2 01478109 380.6 90.76 53.83
SVM - KE 3 026194354 3286.7 90.93 54.43
13247675 2725.9 90.92 54.39
SVM - HKE 3 0.001
2514385 2238.1 90.91 54.32>
SVM - HKE 3 0.002
SVM - HKE 3 0.003
793195 1855.4 90.83 54.21
SVM - KE 4 0293416102 20395.4 90.91 54.69
SVM - HKE 4 0.0002
96522236 15282.1 90.93 54.53>
SVM - HKE 4 0.0004
19245076 11565.0 90.96 54.64
SVM - HKE 4 0.0006
7277592 8958.2 90.84 54.48>`1 - LLM 1 1.0
9268
26.5 88.22 46.06`1 - LLM 2 2.032575 309.8 90.62 53.46`1 - LLM 3 3.0
129503 2088.3 90.71 54.09>
85419 1803.0 90.61 53.79`1 - LLM 3 4.0`1 - LLM 3 5.063046 1699.5 90.59 53.55

Table 2: Specifications of LLMs and SVMs. The
accuracy marked with ‘’ or ‘>’ was significantly better than the d = 2 counterpart (p < 0.01
or 0.01 ≤ p < 0.05 by McNemar’s test).
a double-array trie (Aoe, 1989; Yata et al., 2008),
as a compact trie implementation. All these libraries and algorithms are implemented in C ++.
The code for building fstries occupies 100 lines,
while the code for the classifier occupies 20 lines(except those for kernel expansion).
4.2

Results

Specifications of SVMs and LLMs used here areshown in Table 2; |F d | is the number of active features, while |xd | is the average number of active
features in each classification for the test corpus.
Dependency accuracy is the ratio of dependency
relations correctly identified by the parser, while
sentence accuracy is the exact match accuracy ofcomplete dependency relations in a sentence.
For LLM training, we designed explicit conjunctive features for all the d or lower-order feature
combinations to make the results comparable tothose of SVMs. We could not train d = 4 LLMs
due to parameter explosion. We varied SVM softmargin parameter c from 0.1 to 0.000001 and LLM
width factor parameter ω,10 which controls the impact of the prior, from 1.0 to 5.0, and adjusted
the values to maximize dependency accuracy forthe development set: (d, c) = (1, 0.1), (2, 0.005),(3, 0.0001), (4, 0.000005) for SVMs and (d, ω) =(1, 1.0), (2, 2.0), (3, 4.0) for `1 - LLMs.
The accuracy of around 90.9% (SVM - KE, d =3, 4) is close to the performance of state-of-the10
The parameter C of `1 - LLM in Eq. 2 was set to ω/L(referred to in Kazama and Tsujii (2003) as ‘single width’).

Modeltyped
SVM - KE 1
SVM - KE 2
SVM - KE 3
SVM - KE 4

PKI

classify

Baseline
Mem. Time [ms/sent.]

Proposed w/ fstrieS
Mem. Time [ms/sent.]

Proposed w/ fstrieM
Mem. Time [ms/sent.]

Proposed w/ fstrieL
Mem. Time [ms/sent.](MB)[ms/sent.](MB)classify (total)(MB)

classify (total)(MB)

classify (total)

13.48010.31310.94512.6030.2 0.003 (0.015)
13.5 0.041 (0.054)
142.2 0.345 (0.361)
648.0 2.338 (2.363)

+0.6
+0.5
+0.5
+0.5

0.006 (0.018)
0.020 (0.032)
0.163 (0.178)
1.156 (1.178)

+20.2
+18.0
+18.2
+18.6

0.007 (0.018)
0.021 (0.034)
0.108 (0.123)
0.671 (0.690)

Speed
up

classify (total)+662.9 0.016 (0.029)+662.4 0.023 (0.036)+667.0 0.079 (0.093)+675.9 0.415 (0.432)

NA
2.1
4.4
5.6

art parsers (Iwatate et al., 2008), and the model
statistics are considered to be complex (or realistic) enough to evaluate our classifier’s utility. The number of support vectors of SVMs was
71, 766 ± 9.2%, which is twice as many as thoseused by Kudo and Matsumoto (2003) (34,996) intheir experiments on the same task.
We could clearly observe that the number of active features |xd | increased dramatically according
to the order d of feature combinations. The density of |xd | for SVMs was very high (e.g., |x3 | =3286.7, close to the maximum shown in Eq. 8:(27.33 + 5 × 27.3)/6 ' 3414.
For d ≥ 3 models, we attempted to control
the size of the feature space |F d | by changing
the model’s hyper-parameters: threshold σ for the
SVM - HKE and width factor ω for the `1 - LLM . Although we successfully reduced the size of the feature space |F d |, we could not dramatically reduce
the average number of active features |xd | in eachclassification while keeping the accuracy advantage. This confirms that the solution sparsenessdoes not suffice to obtain an efficient classifier.
We obtained source feature vectors to build
fstries by applying parsers with the target classifiers to a raw corpus in the target domain,
3,258,313 sentences of 1991–94 Mainichi news
articles that were morphologically analyzed by
JUMAN6 and segmented into bunsetsus by KNP.6
We first built fstrieL using all the source feature
vectors. We then attempted to reduce the numberof prefix feature vectors in fstrieL to 1/2n the sizeby Algorithm 1. We refer to fstries built from 1/32
and 1/1024 of the prefix feature vectors in fstrieL
as fstrieM and fstrieS in the following experiments.
Because we exploited Algorithm 2 to calculate the weights of the prefix feature vectors, it
took less than one hour (59 min. 29 sec.) on the
3.20-GHz server to build fstrieL (and calculate theutility score for all the nodes in it) for the slowest SVM - KE (d = 4) from the 40,409,190 source
feature vectors (62,654,549 prefix feature vectors)
generated by parsing the 3,258,313 sentences.

Ave. classification time [ms/sent.]

Table 3: Parsing results for test corpus: SVM - KE classifiers with dense feature space.
2.5

SVM - KE (d = 1)
SVM - KE (d = 2)
SVM - KE (d = 3)
SVM - KE (d = 4)

2
1.5
1
0.5
0
0

100

200

300
400
500
Size of fstrie [MB]

600

700

Figure 3: Average classification time per sentenceplotted against size of fstrie: SVM - KE.
Results for SVM - KE with dense feature space
The performances of parsers having SVM - KE classifiers with and without the fstrie are given in Table 3. The ‘speed-up’ column shows the speed-up
factor of the most efficient classifier (bold) versus the baseline classifier without fstries. Since
each classifier solved a slightly different number of classification steps (112, 853 ± 0.15%), weshow the (average) cumulative classification time
for a sentence. The Mem. columns show the sizeof weight vectors for SVM - KE classifiers and thesize of fstriesS , fstriesM , and fstriesL , respectively.
The fstries successfully speeded up SVM - KEclassifiers with the dense feature space.11 The
SVM - KE classifiers without fstries were still fasterthan PKI, but as expected from a large |xd | value,
the classifiers with higher conjunctive features
were much slower than the classifier with onlyprimitive features by factors of 13 (d = 2), 109(d = 3) and 738 (d = 4) and the classification
time accounted for most of the parsing time.
The average classification time of our classifiersplotted against fstrie size is shown in Figure 3.
Surprisingly, we obtained a significant speed-up
even with tiny fstrie sizes of < 1 MB. Furthermore, we naively controlled the fstrie size by sim11

The inefficiency of the classifier (d = 1) results from thecost of the additional sort function (line 1 in Algorithm 2) andCPU cache failure due to random accesses to the huge fstries.

Modeld σ/ω

type

Baseline
Mem. Time [ms/sent.]

Proposed w/ fstrieS
Mem. Time [ms/sent.]

Proposed w/ fstrieM
Mem. Time [ms/sent.]

Proposed w/ fstrieL
Mem. Time [ms/sent.]

classify (total)(MB)

classify (total)(MB)

classify (total)(MB)64.6 0.348 (0.363)
13.9 0.332 (0.346)
4.2 0.314 (0.328)
235.0 2.258 (2.280)
82.8 2.038 (2.058)
32.2 1.802 (1.820)
0.1 0.004 (0.016)
0.4 0.043 (0.055)
1.0 0.314 (0.326)
0.7 0.300 (0.313)
0.5 0.290 (0.302)

+0.5
+0.5
+0.4
+0.5
+0.5
+0.4
+0.8
+0.6
+0.5
+0.5
+0.5

0.151 (0.166)
0.123 (0.137)
0.102 (0.115)
1.022 (1.042)
0.816 (0.835)
0.646 (0.662)
0.006 (0.018)
0.016 (0.028)
0.091 (0.103)
0.082 (0.094)
0.076 (0.088)

+17.6
+17.0
+14.7
+17.7
+16.8
+15.7
+25.0
+20.5
+17.8
+16.3
+15.1

0.097 (0.111)
0.074 (0.088)
0.057 (0.070)
0.558 (0.575)
0.414 (0.430)
0.311 (0.326)
0.007 (0.019)
0.015 (0.027)
0.041 (0.054)
0.036 (0.049)
0.032 (0.045)(MB)SVM - HKE 3 0.001
SVM - HKE 3 0.002
SVM - HKE 3 0.003
SVM - HKE 4 0.0002
SVM - HKE 4 0.0004
SVM - HKE 4 0.0006`1 - LLM 1 1.0`1 - LLM 2 2.0`1 - LLM 3 3.0`1 - LLM 3 4.0`1 - LLM 3 5.0

Speed
up

classify (total)+638.0 0.070 (0.084)+612.2 0.053 (0.067)+526.2 0.041 (0.054)+637.1 0.330 (0.346)+601.7 0.234 (0.249)+558.9 0.168 (0.183)+787.7 0.016 (0.029)+698.0 0.018 (0.030)+601.0 0.027 (0.040)+550.1 0.024 (0.037)+510.7 0.022 (0.035)

5.0
6.2
7.8
6.8
8.7
10.7
NA
2.9
11.6
12.4
13.3

Ave. classification time [ms/sent.]

2.5

naive
utility score

2
1.5
1

0.680 ms/sent.
(67.1 MB)

0.5

0.671 ms/sent.
(18.6 MB)

0
0

10

20

30
40
50
Size of fstrie [MB]

60

70

0.4

Figure 4: Fstrie reduction: utility score vs. processed sentence reduction for SVM - KE (d = 4).
ply reducing the number of sentences processed to
1/2n . The impact on the speed-up of the resulting
fstries (naive) and the fstries constructed by ourutility score (utility-score) on SVM - KE (d = 4)
is shown in Figure 4. The Zipfian nature of language data let us obtain a substantial speed-up
even when we naively reduced the fstrie size, andthe utility score further decreased the fstrie size
required to obtain the same speed-up. We needed
less than 1/3 size fstries to achieve the same speedup: 0.671 ms./sent. (18.6 MB) (utility-score) vs.
0.680 ms./sent. (67.1 MB) (naive).
Results for SVM - HKE and `1 - LLM classifierswith sparse feature space The performances ofparsers having SVM - HKE and `1 - LLM classifierswith and without the fstrie are given in Table 4.
The fstries successfully speeded up the SVM - HKEand `1 - LLM classifiers by factors of 10.7 (SVM HKE , d = 4, σ = 0.0006) and 11.6 (`1 - LLM ,d = 3, ω = 3.0). We obtained more speedup when we used fstries for classifiers with moresparse feature space F d (Figures 5 and 6). The
parsing speed with d = 3 models are now comparable to the parsing speed with d = 2 models.

SVM - KE (d = 3)
SVM - HKE (d = 3, σ = 0.001)
SVM - HKE (d = 3, σ = 0.002)
SVM - HKE (d = 3, σ = 0.003)

0.35
0.3
0.25
0.2
0.15
0.1
0.05
0
0

80

100

200

300
400
500
Size of fstrie [MB]

600

700

Figure 5: Average classification time per sentenceplotted against size of fstrie: SVM - HKE (d = 3).
Ave. classification time [ms/sent.]

Ave. classification time [ms/sent.]

Table 4: Parsing results for test corpus: SVM - HKE and `1 - LLM classifiers with sparse feature space.

0.4ℓ1 - LLM (d = 3, ω = 3.0)
ℓ1 - LLM (d = 3, ω = 4.0)
ℓ1 - LLM (d = 3, ω = 5.0)

0.35
0.3
0.25
0.2
0.15
0.1
0.05
0
0

100

200

300
400
500
Size of fstrie [MB]

600

700

Figure 6: Average classification time per sentenceplotted against size of fstrie: `1 - LLM (d = 3).

Without fstries, little speed-up of SVM - HKEclassifiers versus the SVM - KE classifiers (in Table 3) was obtained due to the mild reduction in
the average number of active features |xd | in theclassification. This result conforms to the results
reported in (Kudo and Matsumoto, 2003).
The parsing speed reached 14,937 sentences
per second with accuracy of 90.91% (SVM - HKE,
d = 3, σ = 0.002). We used this parser to process 1,005,918 sentences (5,934,184 bunsetsus)
randomly extracted from Japanese weblog feedsupdated in November 2008, to see how much theimpact of fstries lessens when the test data andthe data processed to build fstries mismatch. The
parsing time was 156.4 sec. without fstrieL , while
it was just 35.9 sec. with fstrieL . The speed-up
factor of 4.4 on weblog feeds was slightly worse
than that on news articles (0.346/0.067 = 5.2)
but still evident. This implies that sorting featuresin building fstries yielded prefix features vectorsthat commonly appear in this task, by excludingdomain-specific features such as lexical features.
In summary, our algorithm successfully minimized the efficiency gap among classifiers withdifferent degrees of feature combinations andmade accurate classifiers trained with higher-orderfeature combinations practical.

5Conclusion and Future Work

Our simple method speeds up a classifier trainedwith many conjunctive features by using precalculated weights of (partial) feature vectors stored
in a feature sequence trie (fstrie). We experimentally demonstrated that it speeded up SVM and
LLM classifiers for a Japanese dependency parsing task by a factor of 10. We also confirmed thatthe sparse feature space provided by `1 - LLMs andSVM - HKE s contributed much to size reduction of
the fstrie required to achieve the same speed-up.
The implementations of the proposed algorithm
for LLMs and SVMs (with a polynomial kernel) andthe Japanese dependency parser will be available
at http://www.tkl.iis.u-tokyo.ac.jp/˜ynaga/.
We plan to apply our method to wider range ofclassifiers used in various NLP tasks. To speed upclassifiers used in a real-time application, we canbuild fstries incrementally by using feature vectors generated from user inputs. When we run ourclassifiers on resource-tight environments such ascell-phones, we can use a random feature mixing technique (Ganchev and Dredze, 2008) or amemory-efficient trie implementation based on a
succinct data structure (Jacobson, 1989; Delprattet al., 2006) to reduce required memory usage.
We will combine our method with other techniques that provide sparse solutions, for example,
kernel methods on a budget (Dekel and Singer,
2007; Dekel et al., 2008; Orabona et al., 2008) or
kernel approximation (surveyed in Kashima et al.
(2009)). It is also easy to combine our methodwith SVMs with partial kernel expansion (Goldberg and Elhadad, 2008), which will yield slower

but more space-efficient classifiers. We will in
the future consider an issue of speeding up decoding with structured models (Lafferty et al., 2001;
Miyao and Tsujii, 2002; Sutton et al., 2004).
Acknowledgment The authors wish to thankSusumu Yata and Yoshimasa Tsuruoka for letting
the authors to use their pre-release libraries. The
authors also thank Nobuhiro Kaji and the anonymous reviewers for their valuable comments.

References
Galen Andrew and Jianfeng Gao. 2007. Scalable training of L1 -regularized log-linear models. In Proc.
ICML 2007, pages 33–40.
Jun’ichi Aoe. 1989. An efficient digital search algorithm by using a double-array structure. IEEE
Transactions on Software Engineering, 15(9):1066–
1077, September.
Adam Berger, Stephen Della Pietra, and Vincent Della
Pietra. 1996. A maximum entropy approach to natural language processing. Computational Linguistics, 22(1):39–71, March.
Kun-Ta Chuang, Jiun-Long Huang, and Ming-Syan
Chen.
2008.
Power-law relationship andself-similarity in the itemset support distribution:
analysis and applications. The VLDB Journal,
17(5):1121–1141, August.
Corinna Cortes and Vladimir Vapnik. 1995. Supportvector networks. Machine Learning, 20(3):273–
297, September.
Ofer Dekel and Yoram Singer. 2007. Support vector machines on a budget. In Bernhard Schölkopf,
John Platt, and Thomas Hofmann, editors, Advancesin Neural Information Processing Systems 19, pages
345–352. The MIT Press.
Ofer Dekel, Shai Shalev-Shwartz, and Yoram Singer.
2008. The forgetron: A kernel-based perceptron ona budget. SIAM Journal on Computing, 37(5):1342–
1372, January.
O’Neil Delpratt, Naila Rahman, and Rajeev Raman.
2006. Engineering the LOUDS succinct tree representation. In Proc. WEA 2006, pages 134–145.
Leo Egghe. 2000. The distribution of n-grams. Scientometrics, 47(2):237–252, February.
Kuzman Ganchev and Mark Dredze. 2008. Small statistical models by random feature mixing. In Proc.
ACL 2008 Workshop on Mobile Language Processing, pages 19–20.
Jianfeng Gao, Galen Andrew, Mark Johnson, andKristina Toutanova. 2007. A comparative study

of parameter estimation methods for statistical natural language processing. In Proc. ACL 2007, pages
824–831.

David McClosky, Eugene Charniak, and Mark Johnson. 2006. Effective self-training for parsing. In
Proc. HLT-NAACL 2006, pages 152–159.

Yoav Goldberg and Michael Elhadad.
2008.
splitSVM: Fast, space-efficient, non-heuristic, polynomial kernel computation for NLP applications. In
Proc. ACL 2008, Short Papers, pages 237–240.

Yusuke Miyao and Jun’ichi Tsujii. 2002. Maximum
entropy estimation for feature forests. In Proc. HLT
2002, pages 292–297.

Joshua Goodman. 2004. Exponential priors for maximum entropy models. In Proc. HLT-NAACL 2004,
pages 305–311.

Ngan L.T. Nguyen and Jin-Dong Kim. 2008. Exploring domain differences for the design of a pronoun
resolution system for biomedical texts. In Proc.
COLING 2008, pages 625–632.

Hideki Isozaki and Hideto Kazawa. 2002. Efficient
support vector classifiers for named entity recognition. In Proc. COLING 2002, pages 1–7.

Joakim Nivre. 2003. An efficient algorithm for projective dependency parsing. In Proc. IWPT 2003,
pages 149–160.

Masakazu Iwatate, Masayuki Asahara, and Yuji Matsumoto. 2008. Japanese dependency parsing using
a tournament model. In Proc. COLING 2008, pages
361–368.

Daisuke Okanohara and Jun’ichi Tsujii. 2009. Learning combination features with L1 regularization. In
Proc. HLT-NAACL 2009, Short Papers, pages 97–
100.

Guy Jacobson. 1989. Space-efficient static trees andgraphs. In Proc. FOCS 1989, pages 549–554.

Francesco Orabona, Joseph Keshet, and Barbara Caputo. 2008. The projectron: a bounded kernel-based
perceptron. In Proc. ICML 2008, pages 720–727.

Hisashi Kashima, Tsuyoshi Idé, Tsuyoshi Kato, andMasashi Sugiyama. 2009. Recent advances andtrends in large-scale kernel methods. IEICE Transactions on on Information and Systems, E92-D. toappear.

Patrick Pantel. 2007. Data catalysis: Facilitating largescale natural language data processing. In Proc.
ISUC, pages 201–204.

Jun’ichi Kazama and Jun’ichi Tsujii. 2003. Evaluationand extension of maximum entropy models with inequality constraints. In Proc. EMNLP 2003, pages
137–144.
Jun’ichi Kazama and Jun’ichi Tsujii. 2005. Maximum entropy models with inequality constraints: A
case study on text categorization. Machine Learning, 60(1-3):159–194.
Terry Koo, Xavier Carreras, and Michael Collins.
2008. Simple semi-supervised dependency parsing.
In Proc. ACL 2008, pages 595–603.

Stijn De Saeger, Kentaro Torisawa, and Jun’ichi
Kazama. 2009. Mining web-scale treebanks. In
Proc. NLP 2009, pages 837–840.
Manabu Sassano. 2004. Linear-time dependency analysis for Japanese. In Proc. COLING 2004, pages
8–14.
Drahomíra “Johanka” Spoustová, Jan Hajič, Jan Raab,and Miroslav Spousta. 2009. Semi-supervised
training for the averaged perceptron POS tagger. In
Proc. EACL 2009, pages 763–771.

Taku Kudo and Yuji Matsumoto. 2002. Japanese
dependency analysis using cascaded chunking. In
Proc. CoNLL 2002, pages 1–7.

Charles Sutton, Khashayar Rohanimanesh, and Andrew McCallum. 2004. Dynamic conditional random fields: factorized probabilistic models for labeling and segmenting sequence data. In Proc. ICML
2004, pages 783–790.

Taku Kudo and Yuji Matsumoto. 2003. Fast methods
for kernel-based text analysis. In Proc. ACL 2003,
pages 24–31.

Robert Tibshirani. 1996. Regression shrinkage and selection via the lasso. Journal of the Royal StatisticalSociety. Series B, 58(1):267–288, April.

Sadao Kurohashi and Makoto Nagao. 2003. Building a Japanese parsed corpus. In Anne Abeillé, editor, Treebank: Building and Using Parsed Corpora,pages 249–260. Kluwer Academic Publishers.

Yu-Chieh Wu, Jie-Chi Yang, and Yue-Shi Lee. 2007.
An approximate approach for training polynomial
kernel SVMs in linear time. In Proc. ACL 2007
Poster and Demo Sessions, pages 65–68.

John D. Lafferty, Andrew McCallum, and Fernando
C. N. Pereira. 2001. Conditional random fields:
Probabilistic models for segmenting and labeling sequence data. In Proc. ICML 2001, pages 282–289.

Susumu Yata, Kazuhiro Morita, Masao Fuketa, andJun’ichi Aoe. 2008. Fast string matching withspace-efficient word graphs. In Proc. Innovationsin Information Technology 2008, pages 79–83.

Yudong Liu and Anoop Sarkar. 2007. Experimental
evaluation of LTAG-based features for semantic rolelabeling. In Proc. EMNLP 2007, pages 590–599.

George K. Zipf. 1949. Human Behavior and the Principle of Least-Effort. Addison-Wesley.