Scalable Online Training
with Conjunctive Features
Naoki Yoshinaga and Masaru Kitsuregawa
IIS, The University of Tokyo1

Proposal• Kernel slicing for online training with conjunctive features• explicitly consider conjunctions among frequent features,

while implicitly considering the others by polynomial kernel• reuse temporal margins of partial feature vectors

evaluation on two NLP tasks• Performance(dependency parsing and hyponymy relation extraction)• orders of magnitudes faster than kernel-based online training,
while retaining its space efficiency• model accuracy: comparable to batch SVM2

Overview• Research Backgrounds• Space-time trade-off in training with conjunctive features• Kernel splitting [Goldberg+ ’08] for testing• Methods• Online learning with kernel splitting• Online learning with kernel slicing• Experiments• Conclusion

3Conjunctive features in NLP
features play a key role to obtain a high• Conjunctive
degree of accuracy in NLP classification problems• dependency parsing [Koo+ ’08], pronoun resolution [Nguyen+, 08],
semantic role labeling [Liu+, ’07], relation extraction [Sumida+ ’08]
ex. | dependency parsing
Linear model[LLM, Perceptron, etc.]
y = sgn(wTd (x))

high-dimensional
weight vector

y=IsawaRRP VBD DTgirlNNwithIN+1 (dependent)
1 (independent)...

x = f1 , f2 , f3 , f4 active (primitive) features
2 (x) = f1 , f2 , f3 , f4 , f1 2 , f1 3 , . . . , f3 4
conjunctive features
fi j = 0 iff fi = 0 fj = 04

Conjunctive features in NLP
features play a key role to obtain a high• Conjunctive
degree of accuracy in NLP classification problems• dependency parsing [Koo+ ’08], pronoun resolution [Nguyen+, 08],
semantic role labeling [Liu+, ’07], relation extraction [Sumida+ ’08]

Linear model[LLM, Perceptron, etc.]
y = sgn(wTd (x))

polynomial kernel
Kernel-based model[SVM, Kernel perceptron, etc.] kd (s, x)
y = sgn(i kd (si , x))= (s)T (x)si S

high-dimensional
weight vectord= (sT x + 1)dsupport set(subset of training examples)5dSpace-time tradeoff
in training with conjunctive features• Training with conjunctive features involves space-timetradeoff in the way conjunctive features are handled

linear training(perceptron)

kernel-based training(kernel perceptron)w} initialize
for t = 1 to T docomputemt
wT d (xt )} margin
if yt mt < 0w
w + yt d (xt ) } update
endif needs huge memory
end

{ S0,
⇥ linearly increase as
for i = 1 to T do training proceeds{ mtsi St 1 i kd (si , xt )if yt mt < 0{yt , St = St 1 ⇥ {xt }tendifend

Linear training: polynomial space in the number of primitive features
Kernel-based training: quadratic time in the number of examples
6

Kernel splitting [Goldberg+ 2008](for testing)• Split features into common ones FC and rare ones F \ FCand divide margin computation:••according to frequency in S

explicitly consider conjunctions among common features
implicitly consider remaining conjunctions by kernel

i kd (si , x)i kd (si , xC ) +

=

si S

=

si Sx

TwC

d (xC ) +i {kd (si , x)

kd (si , xC )}FC si Si {kd (si , x)
si SR

7kd (si , xC )}Kernel splitting [Goldberg+ 2008](for testing)• Split features into common ones FC and rare ones F \ FCand divide margin computation:••according to frequency in S

explicitly consider conjunctions among common features
implicitly consider remaining conjunctions by kernel

i kd (si , x)i kd (si , xC ) +

=

si S

=

si SxTwC

d (xC ) +i
sj S

d (sikd (si , xC )}FC si Si {kd (si , x)si SR
explicit weights for common|w|
conjunctive features |wC |wC =i {kd (si , x)FC )space-efficient linear classification
8kd (si , xC )}Kernel splitting [Goldberg+ 2008](for testing)• Split features into common ones FC and rare ones F \ FCand divide margin computation:••according to frequency in S

explicitly consider conjunctions among common features
implicitly consider remaining conjunctions by kernel

i kd (si , x)i kd (si , xC ) +=

si S

=

si Sx

TwC

d (xC ) +i {kd (si , x)FC si S

TT= 0 when sj x = sj xC

i {kd (si , x)
si SRkd (si , xC )}kd (si , xC )}consider a few support vectors |SR ||S|
that have rare feature fR xR = x \ xC

space-efficient linear classification + efficient kernel-based testing9

Online learning with kernel splitting• Replace margin computation part in kernel-based online
learning with kernel splitting
Kernel perceptron
S0

⇥,

⇥,

for t = 1 to T do
mt

si St

if yt mtt

1i kd (si , xt )0yt , St = St 1 ⇤ {xt }

endif
end
10

replace this withkernel splitting

Online learning with kernel splitting• Replace margin computation part in kernel-based online
learning with kernel splitting
Kernel perceptron
S0kernel splitting⇥,⇥,

for t = 1 to T do
Q. 1: how to determine FC ?
xCxt ⌅ FC
mtwC ⇥d (xC ) Q. 2: how to maintain wC ?
+ si SR i {kd (si , xt ) kd (si , xC )}if yt mt 0yt , St = St 1 ⇤ {xt }tendifend
11

Online learning with kernel splitting• Replace margin computation part in kernel-based online
learning with kernel splitting

Kernel perceptron with kernel splitting
A. 1: Choose top-N
frequent features in the
training examples asFCS0⇥,⇥,FC{f | rank(f) N}, wC⇥for t = 1 to T do
Q. 1: how to determine FC ?
xCxt ⌅ FCkernel splitting
mtwC ⇥d (xC ) Q. 2: how to maintain wC ?
+ si SR i {kd (si , xt ) kd (si , xC )}if yt mt 0
A.2 Online-update w
yt , St = St 1 ⇤ {xt }tCto correspond withwCwC + yt ⇥d (xC )St , t ⇥endif
end12

Online learning with kernel splitting• Replace margin computation part in kernel-based online
learning with kernel splitting

Kernel perceptron with kernel splitting

Assumption:
additive updates⇥t > t⇤ t , St ⌅⇤t , St ⌅S0⇥,⇥,
FC{f | rank(f) N}, wC⇥
for t = 1 to T doxCxt ⌅ FCmt
wC ⇥d (xC )+ si SR i {kd (si , xt ) kd (si , xC )}if yt mt 0
yt , St = St 1 ⇤ {xt }twCwC + yt ⇥d (xC )
endif
end13

Intricacy in setting Parameter N
splitting can control space-time trade-off in training• Kernel
with conjunctive features, but it does not resolve itxCmtxt FCwC ⇥d (xC ) +si SR

i {kd (si , xt )kd (si , xC )}Time complexity : O(|xC |d + |SR ||xC |)N (= |F |) should be smaller for higher-order• conjunctivefeatures (to keep |x | and |F | small)
CCdCdN (= |F |) should be larger when we handle a larger• numbertraining examples (to keepsmall)
C|SR |14

Kernel slicing | basic idea
• Examples in real-world data are redundant [Yoshinaga+ ’09]
•Online learner will repeatedly compute margins of common
partial feature vectors

kernel perceptron
S0,⇥
for i = 1 to T do
mtsi St 1 i kd (si , xt )if yt mt < 0yt , St = St 1 ⇥ {xt }
t
endif
end

sequence of examples

i...

parameters

features sortedt2

xt 2 = f1 , f3 , f7 , f19 ⇥St 2 ,t 2⇥

t1

xt 1 = f1 , f3 , f9 , f21 ⇥St 1 ,t 1⇥

xt = f1 , f3 , f7 , f25 ⇥St ,t⇥

St |f25s}t...
mt =reusing partial margins reduces
support vectors to be considered
15+{xt 1 }+ mt{xt 2 }{sKernel slicing | feature-wise splitting
slicing: incrementally compute a partial margin of xt• Kernelwhen adding features to x0 (= ) from frequent to raret|xt |

margin change when we add j-th frequent featurejtemporal
mjt =kd (s, xjt 1 ))i (kd (s, xt )partial margin
si St

mjt

mt = m0t +j=1•

retrieve / update partial margins (with time indext ) in a trie
mjt = mjt +partial margin computedjfor xt at past round t (< t)i {kd (si , xj )si Sj

kd (si , xj 1 )}Sj = {s St \ St |fj s}
jnewly added support vectors since we finally see xt• when common feature fj

FC is added and the retrieved
margin was too old, use wC to compute the partial margin|d (xj )d (xj 1 )| < |Sj ||xj 1 |T
mjt = wC{16jd (xt )(xjt 1 )}Experiments
online passive aggressive I (PA-I) [Crammer+ ’06]
• Implementwith kernel slicing• Compare our learner with•••

Support vector machine (SVM) [TinySVM by T. Kudo]
kernel-based PA-I with inverted indices [Okanohara+ ’07]
SGD-training of 1 - reguralized log-linear model [Tsuruoka, ’09]

on two NLP tasks:• Evaluate
Japanese dependency parsing and hyponymy relation extraction

17

Task settings• Japanese dependency parsing• Classifier judges whether a given head/dependent candidate

has a dependency relation (in shift-reduce parser [Sassano, ’04])• Features: POS(-subcategory), inflection form of head /dependent, and surrounding contexts (distance etc.)• Hyponymy relation extraction•Classifier judges whether a given pair of entities extracted
from Wikipedia articles forms a hyponymy relation [Sumida+ ’08]

• Features: POS, surface string, morpheme, listing type of each
entity, and surrounding contexts (distance etc.)

We considered third-order conjunctive features in training
18

Example / Feature Statistics• Feature conjunctions dramatically increase• the average number of active features• the feature spacedata set
T (# examples)
Ave. of |x|
Ave. of | 3 (x)||F| (# features)|F 3 | (# conj. features)

dependency
parsing296,77627.6
x1303558.364,493x900
58,361,669

hyponymy
extraction
201,66415.4
798.7
306,036
64,249,234

x50
x210

Labeled examples are available from: http://www.tkl.iis.u-tokyo.ac.jp/~ynaga/pecco/
http://nlpwww.nict.go.jp/hyponymy/
19

Results | dependency parsing
with kernel slicing was the fastest, while retaining• PA-I
space-efficiency of kernel-based training•kernel-based
training

linear training

hyper-parameters are tuned to maximize model accuracy on
development set{{methodsvm (batch)
pa-i | kernel
pa-i | splitting
pa-i | slicing
pa-i | linear
1 -llm (sgd)acc.
90.93%
90.90%
90.90%
90.89%
90.90%
90.76%
20

time memory
25912s
243MB
8704s x30 83MB
351s
149MB
262s
175MB
465s
993MB
4057s 21499MB

1/6

Results | hyponymy extraction
with kernel slicing was the fastest, while retaining• PA-I
space-efficiency of kernel-based training•

hyper-parameters are tuned to maximize model accuracy on
development set

methodkernel-based svm (batch)
pa-i | kerneltraining
pa-i | splitting
pa-i | slicing
pa-i | linear
linear training
1 -llm (sgd)

{{

acc.
93.09%
93.14%
93.10%
93.05%
93.11%
92.86%
21

time17354s
1074s
68s
17s
103s
779s

memory140MB
x70 49MB
108MB
131MB
751MB
14089MB

1/6

Splitting vs. Slicing | Parameter N• Training time as a function of parameter N [mem. usage]• kernel splitting: parameter-sensitive• kernel slicing: parameter-insensitive
dependency parsing

1200
1000

~1000MB800= lineartraining

600

splitting400
200

slicing~180MB

0100

Training time [s]Training time [s]

1400

1000

10000

100000N (logscale)160
hyponymy extraction
140
120
100
splitting~750MB80= linear60
training
40~130MB
20
slicing
0100
1000
10000
100000N (logscale)

You don’t need to tune N (it doesn’t change the model, anyway)22

Splitting vs. Slicing | # examples, T• Training time as a function of the number of examples

Training time [s]600kernel500

kernel splitting: in between linear and quadratic
kernel slicing: almost linear
dependency parsing
N=250 (fixed)

400

splitting300
200

slicing

100
0150

100000200000300000splitting

1005000

hyponymy extraction
kernel
N=125 (fixed)

200

Training time [s]••slicing
050000100000150000

T : # of examples

T : # of examples

Reusing temporal margins

more scalable training
23200000Related Work
selection in linear training [Wu+ ’07, Okanohara+, ’09]
• Feature(limit the number of conjunctive features)• Simpler modelx17 but 94.19%
x37 but 89.52%

faster, more space-efficient, less accurate
93.71% (named entity recognition [Wu+ ’07]),
89.03% (dependency parsing [Okanohara+ ’09])

Kernel-based training [Dekel+ ’06; Cavallanti+ ’07]
• Bounded(limit the number of support vectors)•These lightweight algorithms could not bound the number ofsupport vectors, while retaining model accuracy [Orabona+ ’09]

Our method exploits the data redundancy in evaluating
the kernel to train the same model as the base learner24Conclusion• Scalable online training method with kernel slicing• Kernel slicing generalizes kernel splitting [Goldberg+ ’08], to reuse
temporal partial margins for common partial feature vectors• orders of magnitude faster than kernel-based online training,while retaining its space efficiency• Things I didn’t mention in this talk (see our paper):• Efficient management of feature weights and partial margins(packed training examples) with a double-array trie [Yata+ ’09]

• Termination of margin computations that will never contributeto parameter updates (safely skipping rare features)
25

Future work
C++ implementation and dataset: done.
• Release
http://www.tkl.iis.u-tokyo.ac.jp/~ynaga/opal/• Fast testing? - you may want to try pecco [Yoshinaga+, EMNLP ‘09]
http://www.tkl.iis.u-tokyo.ac.jp/~ynaga/pecco/• Implement kernel slicing for other online algorithms• Generalize kernel slicing to accommodate other kernels

26

Thank you27

28