Efficient Classification with Conjunctive Features
Naoki Yoshinaga and Masaru Kitsuregawa / Institute of Industrial Science, University of Tokyo

Efficiency-accuracy dilemmain feature-based classifiers

Efficient classifier with feature sequence trie

Evaluation: dependency parsing

We speed up a classifier trained with many conjunctive features.

Results of Japanese dependency parsing

Pre-compute weight Wc for some feature vector xc
and use it to obtain weight W of x  xc

Conjunctive features (e.g., n-grams)
play an important role in obtaining
accurate classifiers in many NLP tasks.

Idea:Ex) Log-linear model (LLM) w/ binary featuresex) x { f1 , f 2 , f 3 , f 4 } ( x 2w4

W{1, 2,3} w3 w3,4

 fi F f i ( x, y): conjunctive feature

w2 w2,3 w2, 4

w1 w1, 2 w1,3 w1, 4

But if we use many conjunctive features,the classification becomes very slow.
O(| x |)  O(| x |) d (or less) conjunctions

actual datain the task

Current approaches
There are two ways to speeding up theclassification with conjunctive features.

References

w1  w2  w1, 2
 w3  w2,3  w1,3 w4  w3, 4  w2, 4  w1, 4# features
checked10

W{1, 2,3}  w4  w3, 4
 w2, 4  w1, 4

W>

7 (= 3 + 4)

source featurevectors

feature sequence trie (fstrie)root{ f1 , f 3 }frequentff (coarse){ f1 , f 2 }{ f1 , f 3 , f 4 }{ f1 , f 3 , f 5 }{ f2 , f6}

W{1,3}

1

f2
f4

2

f3

f6
f5

rare
(fine)

Obtain source feature vectors from actual data,
sort features in them by frequency, and store
solution: weights of the prefix feature vectors into a trie.

[1] Kudo and Matsumoto: Fast method
for kernel-based text analysis. ACL ‘ .

Time complexity: O(| xc | | x |  | x |) remaining weights (sparse)
ddc[2] Gao et al. A comparative study of parameter estimation
methods for statistical natural language processing. ACL ‘

9 Kyoto Corpus; Sassano’s Shift/reduce parser
9 3,258,313 sentences (news article) were parsed
to build fstrie (weight calculation took 1 hour)Classification time as a function of fstrie size
Classification time [ms/sent.]of primitive features in x

9 L1-reguralized LLM shrinks thefeature space [2], but frequentfeatures are likely to survive.

W

w/ pre-computed
weight W{1,2,3}

9 Which xc should we pre-compute weight for?
Issue: 9 How to find an optimal xc for input x?

d9 Polynomial kernel implicitly
expresses conjunctive features, but
its computation is heavy in practiceO(|SV||x|); |SV| >> |x| [1].

weight computation

Classifyf F ( x, y)weight vector{ f1 , f 2 , f 3}

[ms./sent.]p ( y | x)1
exp ¦ wi f i ( x, y ), wi  Z ( x)iWeight{ f1 , f 2 , f 3 , f 4 , f1, 2 , f1,3 , f1, 4 , f 2,3 , f 2, 4 , f 3, 4 }), xc

Model
SVM
L1-LLM
Conj. degree
1313| F d | # feat.(u103 )39.7 26194.4
9.3 129.5| x d | ave. # feat.
27.3 3286.7 26.5 2088.3
Dep. Acc. (%)
88.29
90.93 88.22 90.71
kernel13.480 10.945
NANA
baseline
0.003
0.345 0.004 0.314
w/ fstrie
NA0.079
NA 0.027
Parse [ms./sent.]
0.0150.093 0.016 0.040

Feature vectors are likely
to follow Zipf’ law (cf. [3])Size of fstrie [MB]* The nodes in fstrie are pruned according to theirprobability and impact on computation reduction

What s ne t
9 Evaluation in other tasks (try the code at
http://www.tkl.iis.u-tokyo.ac.jp/~ynaga/)
9 Application to structured prediction (CRF)[3] Chuang et al. Power-law relationship and self-similarity in the itemset
support distribution: analysis and applications. The VLDB Journal.