Self-Adaptive Classifier for Efficient Text-stream Processing
Naoki Yoshinaga (Univ. Tokyo) and Masaru Kitsuregawa (NII; Univ. Tokyo)# tweets/min. on the day 3.11 Earthquake in JapanIntroduction

Mw 9.0@14:46

A social text stream (e.g., twitter) mirrors the state of real world, soanalyzing a real-time text stream is beneficial for reducing natural
disasters, monitoring sentiment, predicting stock market etc.

Mw 6.3@03:59
Mw 5.6@04:31

Challenge: The content and volume of flow changes dramaticallyin a text stream, reflecting a change in the real worldWe dynamize a linear classifier based on feature sequence trie [Yoshinaga & Kitsuregawa ‘09]
so that it adaptively speeds up classification while processing a text stream

ProposalClassification based on feature sequence trie
[Yoshinaga & Kitsuregawa, EMNLP ‘09]

Self-adaptive classification for text stream[this paper]

Use of conjunctive features (e.g., n-grams) improves
accuracy but slows down processing time in NLP tasks

Keep updating a set of common classification
problems while processing text:

Then, solve common classification problems in advanceto quickly solve new problems as their instances• Use global statistics to select common problems• Store problems in a feature sequence trie for fast retrieval?
NNS IN NNP
men in Corkm(x) =A prefix search returns amargin of a problem similar
to input without processing
conjunctive features

text

0.5
INA

wii (x)=1

input

NNS IN NNP
beers in Dublin...

Issue:

1

enumerate

NNS IN NNP , NNS IN NNP ,beers in Dublin D songs by Enya E, IN NNP , . . .
, for Irish Gsolution:\03\0\00416836 9+gap-based key\0\02\050\07\0841 3
6 9+reducing value nodes

Reducing # nodes to quickly update a trie(candidate) common classification problems
BCDABCEAUse cache algorithms
to keep only k problems
when k=3, LRU (Least Recently Used) keeps E, C, B,while LFU (Least Frequently Used) keeps A, B, C

Experiments

root

59variable-byte ID coding
AProblem: it cannot effectively speed up when a burstoccurs and the topic (content) shifts in a text streamroot
42

How to quickly
update the trie?

...

root

-20.5
, IN NNP F

updateroot

How to select usefulclassification problems?

1.5
IN NNP B

10.5
NNS IN NNP C

10.5
1.5,,.
.
.
NNSIN
NNP
IN NNP

0.5 ,IN

retrieve

0\0B

FG

...

Stop enumeration as soon as
the label (sign of margin) is fixed
use upper-/lower-bounds after
adding the rest feature weights

Impact of the number of common classification problems, k• Data: Tweet stream on 3.11 Earthquake (9M posts in Japanese)• Tasks: base-phrase chunking / dependency parsing• Models: pointwise chunker / shift-reduce parser [Sassano ‘04]
• Base classifier: PA-I with 3rd-order poly kernel
Overall classification performance for tweets on 3.11 Earthquake
ChunkingParsing
MethodSpeed
SpaceSpeed
Space［ms/sent.］ [MiB] ［ms/sent.］

Baseline [Kudo & Matsumoto ‘03]
[Yoshinaga & Kitsuregawa ‘09]
This paper （LFU, k=220）（LFU, k=224）（LRU, k=220）（LRU, k=224）(candidate) common classification problems

?

root

Pre-compute a margin bysumming up feature weights

input

1. build/enumerate common classification problems
Idea:by adding frequent features in input one by one
2. get a margin if exists, o/w compute/store a margin

0.02210.01180.00880.00810.00770.0070

12.0
30.5
90.7
463.0
85.9
399.2

0.11870.07380.02930.02220.02830.0208

[MiB]

31.5
99.9
113.4
904.3
108.9
840.9

Yoshinaga & Kitsuregawa ‘09
Least Frequently Used(LFU)
Least Recently Used
Parsing(LRU)

Speed-up against baseline in processing one-min. tweets
LRU, k=224
LRU, k=220

Parsing

Environment: Intel Core i7-3720QM 2.6GHz CPU server with 16GB RAM

All the codes are available as open-source softwares at http://www.tkl.iis.u-tokyo.ac.jp/~ynaga/

LRU, k=216
Y&K ‘09