Kernel Slicing: Scalable Online Training with Conjunctive Features
Naoki Yoshinaga
Institute of Industrial Science,
the University of Tokyo

Masaru Kitsuregawa
Institute of Industrial Science,
the University of Tokyoynaga@tkl.iis.u-tokyo.ac.jp

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

Abstract
This paper proposes an efficient online
method that trains a classifier with many
conjunctive features. We employ kernel
computation called kernel slicing, which
explicitly considers conjunctions amongfrequent features in computing the polynomial kernel, to combine the merits oflinear and kernel-based training. To improve the scalability of this training, wereuse the temporal margins of partial feature vectors and terminate unnecessary
margin computations. Experiments on dependency parsing and hyponymy-relation
extraction demonstrated that our method
could train a classifier orders of magnitude faster than kernel-based online learning, while retaining its space efficiency.

1

Introduction

The past twenty years have witnessed a growing
use of machine-learning classifiers in the field of
NLP . Since the classification target of complex
NLP tasks (e.g., dependency parsing and relation
extraction) consists of more than one constituent(e.g., a head and a dependent in dependency parsing), we need to consider conjunctive features,i.e., conjunctions of primitive features that focus on the particular clues of each constituent, toachieve a high degree of accuracy in those tasks.
Training with conjunctive features involves aspace-time trade-off in the way conjunctive features are handled. Linear models, such as loglinear models, explicitly estimate the weights ofconjunctive features, and training thus requires a
great deal of memory when we take higher-orderconjunctive features into consideration. Kernelbased models such as support vector machines, on
the other hand, ensure space efficiency by using
the kernel trick to implicitly consider conjunctive
features. However, training takes quadratic timein the number of examples, even with online algorithms such as the (kernel) perceptron (Freund andSchapire, 1999), and we cannot fully exploit ample ‘labeled’ data obtained with semi-supervisedalgorithms (Ando and Zhang, 2005; Bellare et al.,2007; Liang et al., 2008; Daumé III, 2008).
We aim at resolving this dilemma in training with conjunctive features, and propose online
learning that combines the time efficiency of linear training and the space efficiency of kernelbased training. Following the work by Goldberg
and Elhadad (2008), we explicitly take conjunctive features into account that frequently appear in
the training data, and implicitly consider the otherconjunctive features by using the polynomial kernel. We then improve the scalability of this training by a method called kernel slicing, which allows us to reuse the temporal margins of partial
feature vectors and to terminate computations that
do not contribute to parameter updates.
We evaluate our method in two NLP tasks: dependency parsing and hyponymy-relation extraction. We demonstrate that our method is orders ofmagnitude faster than kernel-based online learning while retaining its space efficiency.
The remainder of this paper is organized as follows. Section 2 introduces preliminaries and notations. Section 3 proposes our training method.
Section 4 evaluates the proposed method. Section 5 discusses related studies. Section 6 concludes this paper and addresses future work.

Algorithm 1 BASE L EARNER : K ERNEL PA - I|T |INPUT: T = {(x, y)t }t=1 , k : Rn × Rn 7→ R, C ∈ R+
OUTPUT: (S|T | , α|T | )1: initialize: S0 ← ∅, α0 ← ∅2: for t = 1 to |T | do
3:
receive example (x, y)t : x ∈ XRn , y ∈ {−1, +1}
αi k(si , x)
4:compute margin: mt (x) =si ∈St−1

if `t = max {0,(x)} > 0 then 1 − ymtff`t6:τt ← min C,
kxk2
7:
αt ← αt−1 ∪ {τt y}, St ← St−1 ∪ {x}
8:
else
9:
αt ← αt−1 , St ← St−1
10:
end if
11: end for
12: return (S|T | , α|T | )5:2

Preliminaries

This section first introduces a passive-aggressivealgorithm (Crammer et al., 2006), which we use
as a base learner. We then explain fast methods ofcomputing the polynomial kernel.
Each example x in a classification problem isrepresented by a feature vector whose element xj
is a value of a feature function, fj ∈ F. Here, we
assume a binary feature function, fj (x) ∈ {0, 1},
which returns one if particular context data appear
in the example. We say that feature fj is active inexample x when xj = fj (x) = 1. We denote abinary feature vector, x, as a set of active featuresx = {fj | fj ∈ F, fj (x) = 1} for brevity; fj ∈ xmeans that fj is active in x, and |x| represents thenumber of active features in x.
2.1

Kernel Passive-Aggressive Algorithm

A passive-aggressive algorithm (PA) (Crammer etal., 2006) represents online learning that updates
parameters for given labeled example (x, y)t ∈T in each round t. We assume a binary label,y ∈ {−1, +1}, here for clarity. Algorithm 1
is a variant of PA (PA - I) that incorporates a kernel function, k. In round t, PA - I first computesa (signed) margin mt (x) of x by using the kernel function with support set St−1 and coefficientsαt−1 (Line 4). PA - I then suffers a hinge-loss,`t = max {0, 1 − ymt (x)} (Line 5). If `t > 0,
PA - I adds x to St−1 (Line 7). Hyperparameter C
controls the aggressiveness of parameter updates.
The kernel function computes a dot product in

RH space without mapping x ∈ Rn to φ(x) ∈RH (k(x, x0 ) = φ(x)T φ(x0 )). We can implicitly consider (weighted) d or less order conjunctions of primitive features by using polynomial
kernel function kd (s, x) = (sT x + 1)d . For example, given support vector s = (s1 , s2 )T and
input example x = (x1 , x2 )T , the second-orderpolynomial kernel returns k2 (s, x) = (s1 x1 +s2 x2 + 1)2 = 1 + 3s1 x1 + 3s2 x2 + 2s1 x1 s2 x2 (∵si , xi ∈ {0, 1}). Thisthus√
√ implies map√ function
ping φ2 (x) = (1, 3x1 , 3x2 , 2x1 x2 )T .
Although online learning is generally efficient,the kernel spoils its efficiency (Dekel et al., 2008).
This is because the kernel evaluation (Line 4)
takes O(|St−1 ||x|) time and |St−1 | increases as
training continues. The learner thus takes the mostamount of time in this margin computation.
2.2

Kernel Computation for Classification

This section explains fast, exact methods of computing the polynomial kernel, which are meant totest the trained model, (S, α), and involve substantial computational cost in preparation.
2.2.1

Kernel Inverted

Kudo and Matsumoto (2003) proposed polynomial kernel inverted (PKI), which builds inverted
indices h(fj ) ≡ {s | s ∈ S, fj ∈ s} from eachfeature fj to support vector s ∈ S to only consider support vector s relevant to given x suchthat sT x 6= 0. The time complexity of PKI is
1 P
O(B · |x| + |S|) where B ≡ |x|
fj ∈x |h(fj )|,which is smaller than O(|S||x|) if x has manyrare features fj such that |h(fj )|  |S|.
To the best of our knowledge, this is the only
exact method that has been used to speed up margin computation in the context of kernel-based online learning (Okanohara and Tsujii, 2007).
2.2.2

Kernel Expansion

Isozaki and Kazawa (2002) and Kudo and Matsumoto (2003) proposed kernel expansion, which
explicitly maps both support set S and given example x ∈ Rn into RH by mapping φd imposedby kd :
!Tm(x) =

Xsi ∈S

αi φd (si )φd (x) =Xfi ∈xdwi ,where xd ∈ {0, 1}H is a binary feature vector
in which xdi = 1 for (φd (x))i 6= 0, and w is aweight vector in the expanded feature space, F d .
The weight vector w is computed from S and α:
w=

X

αi

si ∈S

d
X

ckd Ik (sdi ),

(1)

k=0

where ckd is a squared coefficient of k-th order conjunctive features for d-th order polynomial kernel(e.g., c02 = 1, c12 = 3, and c22 = 2)1 and Ik (sdi ) is
sdi ∈ {0, 1}H whose dimensions other than thoseof k-th order conjunctive features are set to zero.
The time complexity of kernelis expansionPd , whichO(|xd |) where |xd | = dk=0 |x|∝|x|kcan be smaller than O(|S||x|) in usual NLP tasks(|x|  |S| and d ≤ 4).
2.2.3 Kernel Splitting
Since kernel expansion demands a huge memory volume to store
the weight vector, w, in RH
Pd|F |(H = k=0 k ), Goldberg and Elhadad (2008)
only explicitly considered conjunctions among
features fC ∈ FC that commonly appear in support set S, and handled the other conjunctive features relevant to rare features fR ∈ F \ FC byusing the polynomial kernel:
m(x) = m(x̃) + m(x) − m(x̃)=

Xfi ∈x̃dw̃i +X

αi kd0 (si , x, x̃), (2)si ∈SR

where x̃ is x whose dimensions of rare featuresare set to zero, w̃ is a weight vector computedwith Eq. 1 for FCd , and kd0 (s, x, x̃) is defined as:
kd0 (s, x, x̃) ≡ kd (s, x) − kd (s, x̃).
We can space-efficiently compute the first termof Eq. 2 since |w̃|  |w|, while we canquickly compute the second term of Eq. 2 sinceT
kd0 (si , x, x̃) = 0 when sT
i x = si x̃; we only
need toSconsider a small subset of the support set,
SR = fR ∈x\x̃ h(fR ), that has at least one of therare features, fR , appearing in x\ x̃ (|SR |  |S|).
Counting the number of features examined, thetime complexity of Eq. 2 is O(|x̃d | + |SR ||x̃|).
1

Following
and Matsumoto(2003),` ´Lemma`Pk 1 in Kudo
` k ´´P
k−m
ckd = dl=k dl· ml m.
m=0 (−1)

3

Algorithm

This section first describes the way kernel splitting
is integrated into PA - I (Section 3.1). We then propose kernel slicing (Section 3.2), which enables
us to reuse the temporal margins computed in thepast rounds (Section 3.2.1) and to skip unnecessary margin computations (Section 3.2.2).
In what follows, we use PA - I as a base learner.
Note that an analogous argument can be applied
to other perceptron-like online learners with theadditive weight update (Line 7 in Algorithm 1).
3.1

Base Learner with Kernel Splitting

A problem in integrating kernel splitting into thebase learner presented in Algorithm 1 is how todetermine FC , features among which we explicitly consider conjunctions, without knowing thefinal support set, S|T | . We heuristically solve
this by ranking feature f according to their frequency in the training data and by using the topN frequent features in the training data as FC(= {f | f ∈ F, RANK(f ) ≤ N }).2 Since S|T |is a subset of the examples, this approximates theselection from S|T | . We empirically demonstrate
the validity of this approach in the experiments.
We then use FC to construct a base learner withkernel splitting; we replace the kernel computation (Line 4 in Algorithm 1) with Eq. 2 where(S, α) = (St−1 , αt−1 ). To compute mt (x̃) byusing kernel expansion, we need to additionally
maintain the weight vector w̃ for the conjunctionsof common features that appear in St−1 .
The additive parameter update of PA - I enables
us to keep w̃ to correspond to (St−1 , αt−1 ).
When we add x to support set St−1 (Line 7 in
Algorithm 1), we also update w̃ with Eq. 1:w̃ ← w̃ + τt ydX

ckd Ik (x̃d ).

k=0

Following (Kudo and Matsumoto, 2003), we
use a trie (hereafter, weight trie) to maintain conjunctive features. Each edge in the weight trie islabeled with a primitive feature, while each path2
The overhead of counting features is negligible compared to the total training time. If we want to run the learnerin a purely online manner, we can alternatively choose firstN features that appear in the processed examples as FC .

represents a conjunctive feature that combines all
the primitive features on the path. The weights
of conjunctive features are retrieved by traversing nodes in the trie. We carry out an analogous
traversal in updating the parameters of conjunctive features, while registering a new conjunctive
feature by adding an edge to the trie.
The base learner with kernel splitting combines
the virtues of linear training and kernel-based
training. It reduces to linear training when we increase N to |F|, while it reduces to kernel-based
training when we decrease N to 0. The output
is support set S|T | and coefficients α|T | (optionally, w̃), to which the efficient classification techniques discussed in Section 2.2 and the one proposed by Yoshinaga and Kitsuregawa (2009) canbe applied.
Note on weight trie construction The time andspace efficiency of this learner strongly depends
on the way the weight trie is constructed. We
need to address two practical issues that greatly
affect efficiency. First, we traverse the trie fromthe rarest feature that constitutes a conjunctive
feature. This rare-to-frequent mining helps us to
avoid enumerating higher-order conjunctive features that have not been registered in the trie, when
computing margin. Second, we use RANK(f )encoded into a dlog128 RANK(f )e-byte string byusing variable-byte coding (Williams and Zobel,
1999) as f ’s representation in the trie. This encoding reduces the trie size, since features withsmall RANK(f ) will appear frequently in the trie.
3.2

Base Learner with Kernel Slicing

Although a base learner with kernel splitting canenjoy the merits of linear and kernel-based training, it can simultaneously suffer from their demerits. Because the training takes polynomial timein the number of common features in x (|x̃d | =
Pd
|x̃|
d
k=0 k ∝ |x̃| ) at each round, we need to set
N to a smaller value when we take higher-orderconjunctive features into consideration. However,since the margin computation takes linear time in
the number of support vectors |SR | relevant to rarefeatures fR ∈ F \FC , we need to set N to a larger
value when we handle a larger number of training
examples. The training thereby slows down when

we train a classifier with high-order conjunctive
features and a large number of training examples.
We then attempt to improve the scalability ofthe training by exploiting a characteristic of labeled data in NLP. Because examples in NLP tasks
are likely to be redundant (Yoshinaga and Kitsuregawa, 2009), the learner computes margins of examples that have many features in common. If we
can reuse the ‘temporal’ margins of partial feature
vectors computed in past rounds, this will speed
up the computation of margins.
We propose kernel slicing, which generalizes
kernel splitting in a purely feature-wise mannerand enables us to reuse the temporal partial margins. Starting from the most frequent feature f1 inx (f1 = argminf ∈x RANK(f )), we incrementally
compute mt (x) by accumulating a partial margin, mjt (x) ≡ mt (xj ) − mt (xj−1 ), when we add
the j-th frequent feature fj in x:
mt (x) = m0t +|x|X

mjt (x),(3)

j=1

where m0t = si ∈St−1 αi kd (si , ∅) = i αi , andxj has the j most frequent features in x (x0 = ∅,F
xj = j−1
k=0 {argminf ∈x\xk RANK (f )}).
P

P

Partial margin mjt (x) can be computed by using the polynomial kernel:
mjt (x) =αi kd0 (si , xj , xj−1 ),X(4)si ∈St−1

or by using kernel expansion:
mjt (x) =

X

w̃i .

(5)

fi ∈xdj \xdj−1

Kernel splitting is a special case of kernel slicing,which uses Eq. 5 for fj ∈ FC and Eq. 4 for fj ∈F \ FC .
3.2.1 Reuse of Temporal Partial Margins
We can speed up both Eqs. 4 and 5 by reusing
a temporal partial margin, δtj0 = mjt0 (x) that had
been computed in past round t0 (< t):mjt (x) = δtj0 +X

αi kd0 (si , xj , xj−1 ), (6)si ∈Sjwhere Sj = {s | s ∈ St−1 \ St0 −1 , fj ∈ s}.

Algorithm 2 K ERNEL S LICINGFF

INPUT: x ∈ 2 , St−1 , αt−1 , FC ⊆ F, δ : 2 7→ N × R
OUTPUT: mt (x)1: initialize: x0 ← ∅, j ← 1, mt (x) ← m0t
2: repeat3:
xj ← xj−1 t {argminf ∈x\xj−1 RANK(f )}4:retrieve partial margin: (t0 , δtj0 ) ← δ(xj )5:
if fj ∈ F \ FC or Eq. 7 is true then6:
compute mjt (x) using Eq. 6 with δtj0
7:
else
8:
compute mjt (x) using Eq. 5
9:end if10:
update partial margin: δ(xj ) ← (t, mjt (x))
11:
mt (x) ← mt (x) + mjt (x)12: until xj 6= x
13: return mt (x)Eq. 6 is faster than Eq. 4,3 and can even befaster than Eq. 5.4 When RANK(fj ) is high, xj appears frequently in the training examples and |Sj |becomes small since t0 will be close to t. WhenRANK (fj ) is low, xj rarely appears in the training
examples but we can still expect |Sj | to be small
since the number of support vectors in St−1 \St0 −1that have rare feature fj will be small.
To compute Eq. 3, we now have the choice tochoose Eq. 5 or 6 for fj ∈ FC . Counting thenumber of features to be examined in computing
mjt (x), we have the following criteria to determine whether we can use Eq. 6 instead of Eq. 5:
1 + |Sj ||xj−1 | ≤ |xdj \ xdj−1 | =

d 
X
k=1



j−1
,
k−1

where the left- and right-hand sides indicate thenumber of features examined in Eq. 6 for the former and Eq. 5 for the latter. Expanding the righthand side for d = 2, 3 and dividing both sides with|xj−1 | = j − 1, we have:
1 (d = 2)|Sj | ≤.
(7)j(d = 3)
2
If this condition is met after retrieving the temporal partial margin, δtj0 , we can compute partial
margin mjt (x) with Eq. 6. This analysis reveals
3

When a margin of xj has not been computed, we regard
t = 0 and δtj0 = 0, which reduces Eq. 6 to Eq. 4.
4
We associate partial margins with partial feature sequences whose features are sorted by frequent-to-rare order,and store them in a trie (partial margin trie). This enables us
to retrieve partial margin δtj0 for given xj in O(1) time.
0that we can expect little speed-up for the secondorder polynomial kernel; we will only use Eq. 6
with third or higher-order polynomial kernel.
Algorithm 2 summarizes the margin computation with kernel slicing. It processes each feature
fj ∈ x in frequent-to-rare order, and accumulatespartial margin mjt (x) to have mt (x). Intuitively
speaking, when the algorithm uses the partial margin, it only considers support vectors on each feature that have been added since the last evaluationof the partial feature vector, to avoid the repetitionin kernel evaluation as much as possible.
3.2.2 Termination of Margin Computation
Kernel slicing enables another optimization that
exploits a characteristic of online learning. Because we need an exact margin, mt (x), only when
hinge-loss `t = 1−ymt (x) is positive, we can finish margin computation as soon as we find that thelower-bound of ymt (x) is larger than one.
When ymt (x) is larger than one after processing feature fj in Eq. 3, we quickly examine
whether this will hold even after we process theremaining features. We can compute a possible
range of partial margin mkt (x) with Eq. 4, having the upper- and lower-bounds, k̂d0 and ǩd0 , ofkd0 (si , xk , xk−1 ) (= kd (si , xk ) − kd (si , xk−1 )):mkt (x) ≤ k̂d0X

αi + ǩd0

X
si ∈Sk+

αi

(8)

αi ,

(9)

si ∈Sk−si ∈Sk+mkt (x) ≥ ǩd0X

αi + k̂d0

X
si ∈Sk−where Sk+ = {si | si ∈ St−1 , fk ∈ si , αi > 0},Sk− = {si | si ∈ St−1 , fk ∈ si , αi < 0}, k̂d0 =(k + 1)d − k d and ǩd0 = 2d − 1 (∵ 0 ≤ sT
i xk−1 ≤Tx|xk−1 | = k − 1, sTx=s+
1 for allkk−1iisi ∈ Sk+ ∪ Sk− ).
We accumulate Eqs. 8 and 9 from rare to frequent features, and use the intermediate results
to estimate the possible range of mt (x) before
Line 3 in Algorithm 2. If the lower bound of
ymt (x) turns out to be larger than one, we terminate the computation of mt (x).
As training continues, the model becomes discriminative and given x is likely to have a larger
margin. The impact of this termination will increase as the amount of training data expands.

4

We evaluated the proposed method in two NLPtasks: dependency parsing (Sassano, 2004) andhyponymy-relation extraction (Sumida et al.,2008). We used labeled data included in opensource softwares to promote the reproducibility of
our results.5 All the experiments were conducted
on a server with an Intel R XeonTM 3.2 GHz CPU.
We used a double-array trie (Aoe, 1989; Yata etal., 2009) as an implementation of the weight trie
and the partial margin trie.
4.1

Task Descriptions

Japanese Dependency Parsing A parser inputs
a sentence segmented by a bunsetsu (base phrase
in Japanese), and selects a particular pair of bunsetsus (dependent and head candidates); the classifier then outputs label y = +1 (dependent) or−1 (independent) for the pair. The features consist of the surface form, POS, POS-subcategory
and the inflection form of each bunsetsu, and surrounding contexts such as the positional distance,
punctuations and brackets. See (Yoshinaga andKitsuregawa, 2009) for details on the features.
Hyponymy-Relation Extraction A hyponymy
relation extractor (Sumida et al., 2008) first extracts a pair of entities from hierarchical listing
structures in Wikipedia articles (hypernym andhyponym candidates); a classifier then outputs label y = +1 (correct) or −1 (incorrect) for the
pair. The features include a surface form, morphemes, POS and the listing type for each entity,and surrounding contexts such as the hierarchicaldistance between the entities. See (Sumida et al.,2008) for details on the features.
4.2

DATA SET

Evaluation

Settings

Table 1 summarizes the training data for the twotasks. The examples for the Japanese dependency
parsing task were generated for a transition-basedparser (Sassano, 2004) from a standard data set.6
We used the dependency accuracy of the parser
5
The labeled data for dependency parsing is available
from: http://www.tkl.iis.u-tokyo.ac.jp/˜ynaga/pecco/, andthe labeled data for hyponymy-relation extraction is available from: http://nlpwww.nict.go.jp/hyponymy/.
6
Kyoto Text Corpus Version 4.0:
http://nlp.kuee.kyoto-u.ac.jp/nl-resource/corpus-e.html.

|T |(y = +1)(y = −1)
Ave. of |x|
Ave. of |x2 |Ave. of |x3 ||F ||F 2 ||F 3 |

DEP

REL

296,776
150,064
146,71227.6
396.1
3558.364,493
3,093,768
58,361,669

201,664
152,199
49,465
15.4
136.9
798.7
306,036
6,688,886
64,249,234

Table 1: Training data for dependency parsing(DEP) and hyponymy-relation extraction (REL).
as model accuracy in this task. In the hyponymyrelation extraction task, we randomly chosen two
sets of 10,000 examples from the labeled data fordevelopment and testing, and used the remaining
examples for training. Note that the number ofactive features, |F d |, dramatically grows when we
consider higher-order conjunctive features.
We compared the proposed method, PA - I SL
(Algorithm 1 with Algorithm 2), to PA - I KER NEL (Algorithm 1 with PKI ; Okanohara and Tsujii (2007)), PA - I KE (Algorithm 1 with kernel expansion; viz., kernel splitting with N = |F|),SVM (batch training of support vector machines),7and `1 -LLM (stochastic gradient descent trainingof the `1 -regularized log-linear model: Tsuruoka
et al. (2009)). We refer to PA - I SL that does notreuse temporal partial margins as PA - I SL∗ . To
demonstrate the impact of conjunctive features onmodel accuracy, we also trained PA - I without conjunctive features. The number of iterations in PA - I
was set to 20, and the parameters of PA - I were averaged in an efficient manner (Daumé III, 2006).
We explicitly considered conjunctions among topN (N = 125 × 2n ; n ≥ 0) features in PA - I SL
and PA - I SL∗ . The hyperparameters were tuned tomaximize accuracy on the development set.
4.3

Results

Tables 2 and 3 list the experimental results forthe two tasks (due to space limitations, Tables 2
and 3 list PA - I SL with parameter N that achieved
the fastest speed). The accuracy of the models
trained with the proposed method was better than
`1 -LLMs and was comparable to SVMs. The infe7

http://chasen.org/˜taku/software/TinySVM/

METHOD
PA - I`1 -LLM
SVM
PA - I KERNELPA - I KE∗
PA - I SL N =4000`1 -LLM
SVM
PA - I KERNELPA - I KE
PA - I SL N =250

d
1
2
2
2
2
2
3
3
3
3
3

ACC .
88.56%
90.55%
90.76%
90.68%
90.67%
90.71%
90.76%
90.93%
90.90%
90.90%
90.89%TIMEMEMORYMETHOD

3s
340s
29863s
8361s
41s
33s
4057s
25912s
8704s
465s
262s

55MB
1656MB
245MB
84MB
155MB
95MB
21,499MB
243MB
83MB
993MB
175MB

PA - I`1 -LLM
SVM
PA - I KERNELPA - I KE∗
PA - I SL N =8000`1 -LLM
SVM
PA - I KERNELPA - I KE
PA - I SL N =125

Table 2: Training time for classifiers used in dependency parsing task.

150

PA - I SP
PA - I SL∗
PA - I SL

1200
900
600
300
0
102

103

104

105

N: # of expanded primitive features

Figure 1: Training time for PA - I variants as a function of the number of expanded primitive featuresin dependency parsing task (d = 3).
rior accuracy of PA - I (d = 1) confirmed the necessity of conjunctive features in these tasks. The
minor difference among the model accuracy of thethree PA - I variants was due to rounding errors.
PA - I SL was the fastest of the training methods with the same feature set, and its space efficiency was comparable to the kernel-based learners. PA - I SL could reduce the memory footprint
from 993MB8 to 175MB for d = 3 in the dependency parsing task, while speeding up training.
Although linear training (`1 -LLM and PA - I KE)
dramatically slowed down when we took higherorder conjunctive features into account, kernel
slicing alleviated deterioration in speed. Especially in the hyponymy-relation extraction task,
PA - I SL took almost the same time regardless ofthe order of conjunctive features.
8

ACC .
91.75%
92.67%
92.85%
92.91%
92.96%
92.88%
92.86%
93.09%
93.14%
93.11%
93.05%`1 -LLM took much more memory than PA - I KE mainly
because `1 -LLM expands conjunctive features in the examples prior to training, while PA - I KE expands conjunctive features in each example on the fly during training. Interested
readers may refer to (Chang et al., 2010) for this issue.

TIME

MEMORY2s
136s
12306s
1251s
27s
17s
779s
17354s
1074s
103s
17s

28MB
1683MB
139MB
54MB
143MB
77MB
14,089MB
140MB
49MB
751MB
131MB

Table 3: Training time for classifiers used inhyponymy-relation extraction task.

Training time [s]Training time [s]

1500

d
1
2
2
2
2
2
3
3
3
3
3

PA - I SP
PA - I SL∗
PA - I SL

120
90
60
30
0
102

103

104

105

106

N: # of expanded primitive features

Figure 2: Training time for PA - I variants as a function of the number of expanded primitive featuresin hyponymy-relation extraction task (d = 3).

Figures 1 and 2 plot the trade-off between thenumber of expanded primitive features and training time with PA - I variants (d = 3) in the twotasks. Here, PA - I SP is PA - I with kernel slicing
without the techniques described in Sections 3.2.1
and 3.2.2, viz., kernel splitting. The early termination of margin computation reduces the training time when N is large. The reuse of temporal
margins makes the training time stable regardlessof parameter N . This suggests a simple, effective strategy for calibrating N ; we start the training with N = |F|, and when the learner reaches
the allowed memory size, we shrink N to N/2
by pruning sub-trees rooted by rarer features withRANK (f ) > N/2 in the weight trie.
Figures 3 and 4 plot training time with PA - I
variants (d = 3) for the two tasks as a functionof the training data size. PA - I SP inherited the demerit of PA - I KERNEL which takes quadratic timein the number of examples, while PA - I SL took almost linear time in the number of examples.

200

PA - I KERNELPA - I SPN =250
PA - I SLN =250

500

Training time [s]Training time [s]

600

400
300
200

PA - I KERNELPA - I SPN =125
PA - I SLN =125

150
100
50

100
0

0
0

50000

1000001500002000002500000300000

50000

100000150000200000|T |: # of training examples|T |: # of training examples

Figure 3: Training time for PA - I variants as a function of the number of training examples in dependency parsing task (d = 3).

Figure 4: Training time for PA - I variants as afunction of the number of training examples inhyponymy-relation extraction task (d = 3).

5

racy. Their method, however, requires O(|St−1 |2 )time in updating the parameters in round t, which
disables efficient training. We have proposed anorthogonal approach that exploits the data redundancy in evaluating the kernel to train the samemodel as the base learner.

Related Work

There are several methods that learn ‘simpler’models with fewer variables (features or support
vectors), to ensure scalability in training.
Researchers have employed feature selection
to assure space-efficiency in linear training. Wu
et al. (2007) used frequent-pattern mining to select effective conjunctive features prior to training. Okanohara and Tsujii (2009) revised grafting for `1 -LLM (Perkins et al., 2003) to prune useless conjunctive features during training. Iwakura
and Okamoto (2008) proposed a boosting-based
method that repeats the learning of rules represented by feature conjunctions. These methods,
however, require us to tune the hyperparameter totrade model accuracy and the number of conjunctive features (memory footprint and training time);
note that an accurate model may need many conjunctive features (in the hyponymy-relation extraction task, `1 -LLM needed 15,828,122 features
to obtain the best accuracy, 92.86%). Our method,on the other hand, takes all conjunctive features
into consideration regardless of parameter N .
Dekel et al. (2008) and Cavallanti et al. (2007)
improved the scalability of the (kernel) perceptron, by exploiting redundancy in the training data
to bound the size of the support set to given threshold B (≥ |St |). However, Orabona et al. (2009)
reported that the models trained with these methods were just as accurate as a naive method thatceases training when |St | reaches the same threshold, B. They then proposed budget online learning based on PA - I, and it reduced the size of the
support set to a tenth with a tolerable loss of accu-

6Conclusion

In this paper, we proposed online learning withkernel slicing, aiming at resolving the space-timetrade-off in training a classifier with many conjunctive features. The kernel slicing generalizes
kernel splitting (Goldberg and Elhadad, 2008) ina purely feature-wise manner, to truly combine themerits of linear and kernel-based training. To improve the scalability of the training with redundantdata in NLP, we reuse the temporal partial margins
computed in past rounds and terminate unnecessary margin computations. Experiments on dependency parsing and hyponymy-relation extraction demonstrated that our method could train aclassifier orders of magnitude faster than kernelbased learners, while retaining its space efficiency.
We will evaluate our method with ample labeled data obtained by the semi-supervised methods. The implementation of the proposed algorithm for kernel-based online learners is available
from http://www.tkl.iis.u-tokyo.ac.jp/˜ynaga/.
Acknowledgment We thank Susumu Yata forproviding us practical lessons on the double-arraytrie, and thank Yoshimasa Tsuruoka for making
his `1 -LLM code available to us. We are also indebted to Nobuhiro Kaji and the anonymous reviewers for their valuable comments.

References
Ando, Rie Kubota and Tong Zhang. 2005. A framework for learning predictive structures from multiple tasks and unlabeled data. Journal of Machine
Learning Research, 6:1817–1853.
Aoe, Jun’ichi. 1989. An efficient digital search algorithm by using a double-array structure. IEEE
Transactions on Software Engineering, 15(9):1066–
1077.
Bellare, Kedar, Partha Pratim Talukdar, Giridhar Kumaran, Fernando Pereira, Mark Liberman, Andrew
McCallum, and Mark Dredze. 2007. Lightlysupervised attribute extraction. In Proc. NIPS 2007
Workshop on Machine Learning for Web Search.
Cavallanti, Giovanni, Nicolò Cesa-Bianchi, and Claudio Gentile. 2007. Tracking the best hyperplanewith a simple budget perceptron. Machine Learning, 69(2-3):143–167.
Chang, Yin-Wen, Cho-Jui Hsieh, Kai-Wei Chang,Michael Ringgaard, and Chih-Jen Lin. 2010. Training and testing low-degree polynomial data mappings via linear SVM. Journal of Machine Learning
Research, 11:1471–1490.
Crammer, Koby, Ofer Dekel, Joseph Keshet, Shai
Shalev-Shwartz, and Yoram Singer. 2006. Online
passive-aggressive algorithms. Journal of Machine
Learning Research, 7:551–585.
Daumé III, Hal. 2006. Practical Structured Learning Techniques for Natural Language Processing.
Ph.D. thesis, University of Southern California.

Kudo, Taku and Yuji Matsumoto. 2003. Fast methods
for kernel-based text analysis. In Proc. ACL 2003,
pages 24–31.
Liang, Percy, Hal Daumé III, and Dan Klein. 2008.
Structure compilation: trading structure for features. In Proc. ICML 2008, pages 592–599.
Okanohara, Daisuke and Jun’ichi Tsujii. 2007. A discriminative language model with pseudo-negative
samples. In Proc. ACL 2007, pages 73–80.
Okanohara, Daisuke and Jun’ichi Tsujii. 2009. Learning combination features with L1 regularization. In
Proc. NAACL HLT 2009, Short Papers, pages 97–
100.
Orabona, Francesco, Joseph Keshet, and Barbara Caputo. 2009. Bounded kernel-based online learning.
Journal of Machine Learning Research, 10:2643–
2666.
Perkins, Simon, Kevin Lacker, and James Theiler.
2003. Grafting: fast, incremental feature selection
by gradient descent in function space. Journal of
Machine Learning Research, 3:1333–1356.
Sassano, Manabu. 2004. Linear-time dependency
analysis for Japanese. In Proc. COLING 2004,
pages 8–14.
Sumida, Asuka, Naoki Yoshinaga, and Kentaro Torisawa. 2008. Boosting precision and recall of hyponymy relation acquisition from hierarchical layouts in Wikipedia. In Proc. LREC 2008, pages
2462–2469.

Daumé III, Hal. 2008. Cross-task knowledgeconstrained self training. In Proc. EMNLP 2008,
pages 680–688.

Tsuruoka, Yoshimasa, Jun’ichi Tsujii, and Sophia
Ananiadou. 2009. Stochastic gradient descenttraining for L1-regularized log-linear models withcumulative penalty. In Proc. ACL-IJCNLP 2009,
pages 477–485.

Dekel, Ofer, Shai Shalev-Shwartz, and Yoram Singer.
2008. The forgetron: A kernel-based perceptron on a budget. SIAM Journal on Computing,37(5):1342–1372.

Williams, Hugh E. and Justin Zobel. 1999. Compressing integers for fast file access. The Computer Journal, 42(3):193–201.

Freund, Yoav and Robert E. Schapire. 1999. Largemargin classification using the perceptron algorithm. Machine Learning, 37(3):277–296.

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

Goldberg, Yoav and Michael Elhadad.
2008.
splitSVM: fast, space-efficient, non-heuristic, polynomial kernel computation for NLP applications. In
Proc. ACL-08: HLT, Short Papers, pages 237–240.
Isozaki, Hideki and Hideto Kazawa. 2002. Efficient
support vector classifiers for named entity recognition. In Proc. COLING 2002, pages 1–7.
Iwakura, Tomoya and Seishi Okamoto. 2008. A fast
boosting-based learner for feature-rich tagging andchunking. In Proc. CoNLL 2008, pages 17–24.

Yata, Susumu, Masahiro Tamura, Kazuhiro Morita,
Masao Fuketa, and Jun’ichi Aoe. 2009. Sequential
insertions and performance evaluations for doublearrays. In Proc. the 71st National Convention of
IPSJ, pages 1263–1264. (In Japanese).
Yoshinaga, Naoki and Masaru Kitsuregawa. 2009.
Polynomial to linear: efficient classification withconjunctive features. In Proc. EMNLP 2009, pages
1542–1551.