ISHIGURO et al.: MULTI-CLASS BOOSTING FOR EARLY CLASSIFICATION

1Multi-class Boosting for Early Classification ofSequences
Katsuhiko Ishiguro
ishiguro@cslab.kecl.ntt.co.jp

Hiroshi Sawada
sawada@cslab.kecl.ntt.co.jp

NTT Communication Science
Laboratories,
NTT Corporation
Kyoto, 610-0237, Japan

Hitoshi Sakano
keen@cslab.kecl.ntt.co.jp

Abstract
We propose a new boosting algorithm for sequence classification, in particular one
that enables early classification of multiple classes. In many practical problems, wewould like to classify a sequence into one of K classes as quickly as possible, without
waiting for the end of the sequence. Recently, an early classification boosting algorithm
was proposed for binary classification that employs a weight propagation technique. In
this paper, we extend this model to a multi-class early classification. The derivation
is based on the loss function approach, and the developed model is quite simple andeﬀective. We validated the performance through experiments with real-world data, andconfirmed the superiority of our approach over the previous method.

1

Introduction

In this paper, we are interested in multi-class classification of sequence data. For example, consider the problem of driver behavior recognition from images captured by a camera
installed in a vehicle [11]. Recognition of driver behavior is crucial for driver assistancesystems that make driving comfortable and safe, and we would like to predict and classify
a behavior as quickly as possible: we don’t want to wait until the behavior is over. If we
detect a sign of dangerous movements such as mobile phone use while driving, we would
like to warn the driver quickly before the behavior causes any accidents. If the driver looks
into a side mirror frequently, the system may predict there will be a lane change. Thus theassistance system can suggest to the driver the best timing for changing lanes.
This kind of classification task is called “early classification (recognition),” and is important for many practical problems including on-line handwritten character recognition [1],and speech recognition systems [7].
We can apply either a generative model such as HMM [9] or a discriminative model such
as SVM [14], CRF [8] to general sequence recognition problems [3]. In general, generativemodels such as HMM are flexibly applicable to the recognition of (sub)sequence x1:t but aretrained to maximize the likelihood of the “total” sequence x1:T , not for early classificationof sequences. Discriminative models such as SVM and CRF are said to be superior in theclassification score to generative models. However, we need to fix the length of sequencesc 2010. The copyright of this document resides with its authors.
It may be distributed unchanged freely in print or electronic forms.

2

ISHIGURO et al.: MULTI-CLASS BOOSTING FOR EARLY CLASSIFICATIONa priori in typical applications. Thus we cannot compute the classification results if the test
sequence is shorter than the predefined length of sequences.
In this paper, we focus to another famous discriminative model, i.e. Adaboost [4, 5], because some researchers have proposed early classification extensions. Sochman and Matas [12]combined the idea of sequential decision making problem in order to balance the trade-oﬀ
between the precision and the quickness when the decision (recognition) should be made. [6]have also proposed a boosting scheme which is able to handle early classification and variable length sequence inputs. Uchida and Amamoto [13] proposed a new boosting algorithm
that we refer to “Earlyboost.” Earlyboost enables early classification of sequences by timeframe-wise weak classifiers and weight propagation technique which preferentially corrects
the classifiers to reduce misclassifications made by the previous time frames.
Unfortunately, in these three models the authors have studied only a binary classification(the number of classes is K = 2) problem. However many real-world applications including
the driver behavior recognition example require multi-class (K > 2) classification scheme.
The authors(K ) of [13] handled such cases by constructing 1 vs. 1 strong classifiers for all
possible 2 class pairs. Obviously, this approach is ineﬃcient with large K. Also the resultant strong classifier is not optimized for K-class classification problem because it is just acollection of independent binary classifiers.
To this end, we present a multi-class extension of Earlyboost, called Earlyboost.MH(Fig. 1). In our model, the number of weak classifiers to be trained is proportional to K. The
idea is to combine the weight propagation technique with existing multi-class Adaboost [10].
This combination is intuitively understandable and practically useful. Based on the exponential loss approach [5], we derive and validate the soundness of the model formulation. In thenext section, we briefly provide some background. In the third section, we present our newmodel, and we examine its performance through real-world sequence data in the fourth section. The last section concludes the paper.
start (t = 1)

end (t = T)

Input sequence1tObservation (feature)
sequencet-1

Hk (x) = Σt=1:L αt ht,k (xt)Classify
Misclassification
Information

Early classification of(sub)sequences

Add a weak classifier

ht,k (xt) Learninga new weak classifier
αtWeightPropagation

Figure 1: Overview of a concept of the multi-class early classification boosting. Finalstrong classifiers consists of time frame-wise weak classifiers. The weak classifiers are learnt
through weight propagation technique to achieve early classification of (sub)sequences.

ISHIGURO et al.: MULTI-CLASS BOOSTING FOR EARLY CLASSIFICATION

2

Background2.1

Adaboost

3

Let us first review the well-known Adaboost [4]. We have a training dataset D = {xi , yi } :
i = 1, 2, . . . , N where xi ∈ Rd is an observation and yi ∈ {1, −1} is its class label. The goal of
Adaboost learning is to construct a strong classifier H : Rd → {1, −1} using D as follows:
M

∑

H(x) = sign  αm hm (x) ,

(1)

m=1

where hm : Rd → {1, −1} is the m-th weak classifier, αm ∈ R is its importance weight and M isthe total number of weak classifiers. Let us denote the m-subset of the final strong classifier
as follows:
m

∑

m

H (x) = sign  αl hl (x) .
(2)
l=1

Therefore the final strong classifier H is equivalent with H M .
The empirical loss function J for H m is defined by the following equation [5]:J(H ) =
m

N
∑
(
i=1




N
m
 ∑

)) ∑ 
exp −yi
exp −yi H (xi ) =αl hl (xi ) .
(

m

i=1

(3)

l=1

In the learning phase, we find hm and αm which minimizes the loss J(H m−1 + αm hm ) iteratively, incrementing m ← m + 1. As a result, we obtain the following equations:hm = arg min m ,h()
1
1 − mαm = log
,
2
m
∑
m =
Dm (i).

(4)
(5)
(6)

i:yi ,h(xi )Dm (i) ∈ R is a sample weight of xi at m-th training, defined recursively as follows:
Dm (i) ∝ Dm−1 (i) exp (−αm−1 yi hm−1 (xi )) .

(7)

Intuitively, Eq. (7) will be large if the classification by the weak classifier hm−1 and the truelabel are inconsistent, and will be small otherwise.

2.2“Earlyboost”

A novel attempt to use the boosting scheme for early sequence classification was proposedby Uchida and Amamoto [13]. We call this method “Earlyboost” for convenience, though
the authors of [13] did not specify a name for their model.
Let us denote that i-th sequence x i has a number of time frame elements xi,t : i.e. x i ={xi,t ∈ Rd }, t = 1, 2, . . . , T . The number of sequences is N: thus i ∈ {1, 2, . . . , N}. T is the length

4

ISHIGURO et al.: MULTI-CLASS BOOSTING FOR EARLY CLASSIFICATION

of time sequences, and t ∈ {1, 2, . . . , T } is the time index. The objective of Earlyboost is tolearn the strong classifier H from the training data D = {xxi , yi }:
 T

∑

(
)
H(xxi ) = sign  αt ht xi,t (8)t=1

where ht : Rd → {1, −1} is the t-th frame-wise weak classifier that only accepts the samples
on the t-th time frame {xi,t }i=1,2,...,N . At each t, we find ht and αt by the following equations:ht = arg min t ,h()
1 − t1,αt = log
2
t
∑
t =
Dt (i).

(9)
(10)
(11)

i:yi ,h(xi,t )The contribution of [13] is the definition of Dt (i) based on the weight propagation technique. Since ht−1 and ht are learned on diﬀerent sets of samples, we need to devise a way toconnect them. The authors put weights over sequences i, not samples xi,t and propagate theweights over time frames t − 1 and t:()
Dt (i) ∝ Dt−1 (i) exp −αt−1 yi ht−1 (xi,t−1 ) .
(12)
In the classification phase, a test (sub)sequence x j = {x j,t , t = 1, 2, . . . , L} will be classified
as follows:
 L

∑
( )
( )
(13)y j = H x j = sign  αt ht x j,t t=1

Eq. (12) implies that each weak classifier ht learns the classification boundary at time t tominimize the classification error induced by the information up to time t − 1. Thus the resulting strong classifier will be good for early classification of sequences, even if the sequenceis short (L ≤ T ).
We can validate the formulation of Earlyboost by using the loss function approach, which
has not been examined in the original paper [13]. First we define the t-subset of the final
strong classifier H like Eq. (2):

 t
∑
( )t(14)
H (xxi ) = sign  α s h s xi,s  .
s=1

Then we define the exponential loss function as follows:


t
∑(

 ∑
(
)) ∑
t
t

α s h s (xi,s ) .
J(H ) =
exp −yi H (xxi ) =exp −yi
i

i

(15)

s=1

Then Eqs.(9-12) are derived by seeking for αt and ht which minimizes the loss below:()
αt , ht = arg min J H t−1 + αt ht .
(16)
α,h

Thus Earlyboost iteratively augments the strong classifier H which minimizes the loss above
w.r.t. αt and ht , those who are dependent only on the t-th frame observations. The derivationis almost the same with Adaboost [5]. Please find details in the supplemental material.

ISHIGURO et al.: MULTI-CLASS BOOSTING FOR EARLY CLASSIFICATION

3

Proposed: Earlyboost.MH

3.1

Algorithm

5

The problem with Earlyboost is that it is only a binary classifier. We propose an eﬃcient multi-class Earlyboost that we refer to Earlyboost.MH. Our model is inspired by Adaboost.MH [10], which is a standard multi-class Adaboost. The Earlyboost.MH is derived
by applying the idea of weight propagation to Adaboost.MH.
We have a set of training data D = {xxi , yi }. Because of multi-class classification, classlabels range in K values: yi ∈ {1, 2, . . . , K} which makes contrast to Adaboost and Earlyboost.
A weak classifier ht,k (x) : Rd → {1, −1} only accepts the samples on the t-th time frames.
ht,k (x) returns 1 if x belongs to class k, and returns −1 otherwise. We also define gk (y) :{1, 2, . . . , K} → {1, −1} returns 1 if y = k, and returns −1 otherwise.
The strong classifier of Earlyboost.MH consists of K classifiers Hk , namely H = {Hk }.
Hk is a one vs. all type classifier which computes the likelihood of the sequence being themember of class k, described as follows:
Hk (xxi ) =T∑αt ht,k (xi,t ).

(17)

α s h s,k (xi,s ).

(18)

t=1

We also define the t-subset of Hk as:
Hkt (xxi ) =

t
∑
s=1

We define an empirical loss function for Earlyboost.MH as follows:


t
N ∑
K (
N ∑
K
∑
∑


(
)) ∑
t
t

α s h s,k (xi,s ) .
J(H ) =
exp −gk (yi )Hk (xxi ) =exp −gk (yi )i=1 k=1i=1 k=1(19)

s=1

We can readily obtain above by plugging Eq. (15) to the loss of Adaboost.MH [5, 10].
In the learning phase, we seek for {ht,k , αt } which minimizes the loss given Hkt−1 :αt , ht,k = arg min
α,h

N ∑
K
∑

[
(
)]
exp −gk (yi ) Hkt−1 (xxi ) + αt ht,k (xi,t ) .

(20)

i=1 k=1

Note that the predicate of exp is expanded by αt and ht,k that are to be estimated.
We solve Eq. (20) w.r.t. ht,k and αt to find the minimum. After simple calculations, we
obtain the following equations Eqs.(21-24). For the details of the derivation, please find the
supplemental material. An optimal ht,k is computed as follows:
ht,k = arg max rt,k ,hrt,k =N∑

gk (yi )ht,k (xi,t )Dt (i, k).

(21)
(22)

i=1

rt,k is a class- and frame-wise classification score which only depends on the observation at
the t-th frame. The score rt,k will be large if the estimated label by a weak classifier and gk

6

ISHIGURO et al.: MULTI-CLASS BOOSTING FOR EARLY CLASSIFICATION

match correctly, and will be small otherwise. Dt (i, k) ∈ R is a weight of a sequence x i for thek-th classifier at t-th frame, propagated from the time t − 1:()
Dt (i, k) ∝ Dt−1 (i, k) exp −αt−1 gk (yi )ht−1,k (xi,t−1 ) .
(23)
The importance weight αt is computed as follows given maximized rt,k :)(∑1 + k rt,k1∑.
αt = log
2
1 − k rt,k(24)

In the classification phase, we estimate the label y j of a test (sub)sequence x j whose
length is L < T as follows:
y j = arg max Hk (xx j ) = arg max
k=1,2,...,K

k=1,2,...,KL∑

αt ht,k (x j,t ).

(25)

t=1

The resulting strong classifier tries best to distinguish K classes given shorter L samples
thanks to the early classification property brought by Eq. (23).

3.2 Short remarks
Our Earlyboost.MH has two advantages over the original Earlyboost. At first, Earlyboost.MH
optimizes the loss Eq. (20), which equally evaluates all K classes. Thus the learnt model is
optimal (for) K class classification problem. On the other hand, the original Earlyboost [13]trains a K2 set of strong binary classifiers which discern between the class k and k0 . Thesestrong classifiers are optimized for each binary classification, thus the performance in K classclassification will degrade.
Also, our Earlyboost.MH only requires training of KT weak classifiers for K class classification problems. It eﬀectively reduces( ) the number of weak classifiers compared to theoriginal Earlyboost, which requires T K2 weak classifiers. Some practical tasks such as Chinese character recognition and large-vocabulary speech recognition have large cardinality ofclasses (K > 100, 1000, . . . ). In such cases, this computational advantage of( Earlyboost.MH)
may be essential to develop the system since learning, installing and using K2 strong classifier becomes inhibitory.
In our model, we construct a time frame-wise weak classifier ht,k , which only considers sample distribution at time t. We can naturally adapt the classifier to the dynamics ofsequence by setting T weak classifiers for T length sequence as in Eq. (21). We can extend the weak classifiers to take care of multiple frames easily, but this does not change thedescription of the model.

4 Experiments
We conduct two experiments to validate the performance of Earlyboost.MH. One is the online handwritten digits recognition, and another is the behavior recognition of drivers (Fig. 2).

4.1 Datasets
The same dataset used in [13] is tested in online handwritten digits recognition task (Fig. 2(A)).
The dataset is called Ethem Alpaydim Digit, which is a collection of digit (“0”-”9”) writing

ISHIGURO et al.: MULTI-CLASS BOOSTING FOR EARLY CLASSIFICATION

7

Pressure sensitive tablet

Stylus pen

Sampling points (w,h)(A)

Three joints, tracked by optical flow (no markers)(B)

Figure 2: Dataset used in the experiments. (A) On-line handwritten digits recognition task isconducted using Ethem Alpaydim Digit dataset. Trajectories are collected through a pressure
sensitive tablet and a wireless stylus pen. (B) For driver behavior recognition tasks, sevensubjects are recorded their driving simulations by a consumer video camera. Three joints aretracked by optical flow, without any markers or special attachments.
trajectories. Following [13], we align the lengths of all sequences to T = 50 by simple linear
interpolations. Observed features xi,t consists of i) 2D coordinates of a stylus pen tip calculated by a pressure sensitive tablet and ii) 2D velocity of the pen tip computed by frame
diﬀerence. These d = 4 dimensional data are whitened in prepossessing.
This task is a K = 10 class classification problem. Each sequence corresponds to a writing
trajectory of one digit. We have approximately N = 11000 sequences in total. We employedkNN classifiers (k = 5) for a weak learner, where the samples are resampled based on theweights Dt (i, k). Learning and classification is conducted in 6 fold cross validation.
Our second task is driver behavior recognition (Fig. 2(B)). A video camera was installed
in a real-scale driving simulator and recorded the driving behaviors of seven people. Each
person drove 30 times. The movies were recorded in 60 FPS. We tracked several of thedrivers’ joints using optical flows, and finally obtained joint coordinate’ sequences of theleft wrist, right wrist and left elbow on the 2D images [11]. Thus, the observation data is asequence of d = 6(= 3 × 2) dimensional vectors. Sequence lengths were not normalized.
The number of behavioral classes (patterns) is K = 12, which includes “manipulating
A/C,” “adjusting the rear-view mirror,” and so forth. All time frames were manually labeled,
and were segmented into a series of behavior motion sequences. Every sequence starts fromthe home position: the driver holds the steering wheels by both hands. This is a natural
assumption because a driver holds the steering wheel in the most part of driving. The numberof sequences N was diﬀerent for each person, but roughly N = 660 sequences were collected
for each person. We chose a decision stump [2] for a weak classifier. Classification precision
was computed via 6-fold cross validation for each person.

4.2

Compared method

We compare the proposed method with the original Earlyboost [13]. We need to take care( )of multi-class situation because Earlyboost is a binary classifier. Instead of constructing K2“one vs. one (k vs. k0 )” classifiers as in [13], we took another approach for a fair comparisonin terms of the computational cost.
We have implemented “one vs. all” type binary classifiers for K classes by Earlyboost.
Each binary strong classifier Hk estimates whether the test sequence x j “belongs to class k

8

ISHIGURO et al.: MULTI-CLASS BOOSTING FOR EARLY CLASSIFICATION(y = 1)”, or “belongs to the other classes (y = −1)”. The diﬀerence is that K strong binaryclassifiers are learnt independently in our implementation of Earlyboost. For classification,
we compute the sum of weak classifiers’ output scores and classify the sequence to the classof arg max as in Eq. (25). We can expect that the comparison is fair since the number of
weak classifiers and computational costs for learning and classifications become almost thesame with Earlyboost.MH in this setup. Please remember that all classifiers for K classes
are optimized simultaneously in the proposed Earlyboost.MH.

4.3 Results
First, we show the results of online handwritten digits recognition task. Fig. 3 presents
the averaged classification precision score for K = 10 class. The vertical axis denotes theprecision, and the horizontal axis the length L of the input test (sub)sequence (Eq. (25)). The
thick blue line is the averaged precision of propose Earlyboost.MH, and the thin red line isthat of Earlyboost.
Earlyboost.MH is superior to the previous Earlyboost in many frames. Especially, Earlyboost.MH marked relatively good scores around 40 ∼ 45 frames. However we also admit the
proposed method is little inferior to Earlyboost in the first 15 frames, which is not pleasingfor early classification. Yet we think that we can assume the proposed multi-class boosting
approach is good, at least comparable, in early sequence classification of handwritten digits.
Evolution of precision (handwritten digits)
1
0.9Classification precision

0.8
0.7
0.6
0.5
0.4
0.3
0.2

earlyboost.MH
earlyboost

0.1
0

0

5

10

15

20

25

30

35

40

45

50

Time frames

Figure 3: Time evolution of averaged classification precision in handwritten digits recognition task. The horizontal axis denotes the length of the input, the vertical axis denotes theprecision. The thick red lines is the results of Earlyboost.MH, and the thin blue line is theresults of Earlyboost.
Next, we show the temporal evolution of the classification precision score of the driver
behavior recognition task in Fig. 4. In this figure, we present the average of seven drivers
results. It is clear that the proposed Earlyboost.MH (denoted by the thick red line) again
outperforms Earlyboost (the thin blue line) for the sequence early classification.
However, there is a notable gap in achieved improvements of classification precision
between two tasks. We think this is due to the characteristics of the task (and the dataset).
In the case of online handwritten digits recognition, we expect that the trajectories of each

ISHIGURO et al.: MULTI-CLASS BOOSTING FOR EARLY CLASSIFICATION

9digit class have “uniqueness” or independence between classes. For example, digits “1” and“5” are very diﬀerent in not only the start position of writing, but also in the curvature of
the trajectories. Therefore, we achieve relatively good scores by Earlyboost which does notincorporate the correlations between classes.
On the other hand, the data of driver behavior recognition is characterized by the factthat all sequences start from the “home position” (holding the steering wheel by both hands)
because of expected applications. We also note that some behaviors such as “manipulate
A/C” and “using car navigation system” will have very similar trajectories from the first
frame to the last frame. These implies that all trajectories are indistinguishable in the earlyframes, and the distributions of the sequence samples are highly correlated between someclasses. Therefore, if we neglect the dependency between classes like Earlyboost, we are
not able to obtain a good classification score. We conclude that the proposed method is
especially useful for the multi-class dataset where some classes are highly correlated.
Evolution of precision (driver behavior)
1
0.9Classification precision

0.8
0.7
0.6
0.5
0.4
0.3
Earlyboost.MH
Earlyboost

0.2
0.1
0

20

40

60

80

100

120

140

160

180

Time frames

Figure 4: Time evolution of averaged classification precision in driver behavior recognition
task. The horizontal axis denotes the length of the input, the vertical axis denotes the precision. The thick red lines is the results of Earlyboost.MH, and the thin blue line is the resultsof Earlyboost. Averaged results for seven drivers are presented.

5Conclusion

We presented a new boosting algorithm for early classification of multi-class sequences. We
incorporated the idea of weight propagation proposed by [13] into a standard multi-class
Adaboost [10], and derived Earlyboost.MH model based on the standard exponential loss
approach [5]. The complexity of the model grows only linearly proportional to the numberof classes, and the resultant model showed comparable of much better results in experiments
on multi-class classification of handwritten digits and driver behaviors.
We will study the capability and the limitation of the model for several types of computer vision tasks, which includes large class (K > 100) classification problem such as character recognition. Also studying other types of loss function for multi-class early classification [15] is highly interesting and beneficial for many applications.

10

ISHIGURO et al.: MULTI-CLASS BOOSTING FOR EARLY CLASSIFICATION

References[1] C. Bahlmann and H. Burkhardt. The writer independent online handwriting recognition
system frog on hand and cluster generative statistical dynamic time warping. IEEE
Trans. PAMI, 26(3):299–310, Mar. 2004.
[2] C. M. Bishop. Pattern Recognition and Machine Learning. Springer-Verlag New York,2006.
[3] T. G. Dietterich. Machine learning for sequential data: A review. In T. Caelli, editor,
Proc. SSSPR, pages 15–30. Springer-Verlag., 2002.
[4] Y. Freund and R. E. Schapire. A decision-theoretic generalization of on-line learningand an application to boosting. Journal of Computing Systems and Science, 55(1):119–139, 1997.
[5] J. Friedman, T. Hastie, and R. Tibshirani. Additive logistic regression: A statisticalview of boosting (with discussion). Annals of Statistics, 28(2):337–407, 2000.
[6] C. J. A. Gonzalez, G. Juan, and J. J. R. Diez. Boosting interval-based literals: Variable
length and early classification. In Proc. ECAI’02 Workshop on Knowledge Discovery
from (Spatio-) Temporal Data, 2002.
[7] T. Hori, C. Hori, and Y. Minami. Fast on-the-fly composition for weighted finite-statetransducers in 1.8 million-word vocabulary continuous speech recognition. In Proc.
Interspeech, volume 1, pages 289–292, 2004.
[8] J. Laﬀerty, A. McCallum, and F. Pereira. Conditional random field: Probabilistic models for segmenting and labeling sequence data. In Proc. ICML, pages 282–289, 2001.
[9] L. R. Rabiner. A tutorial on hidden Markov models and selected applications in speech
recognition. Proceedings of the IEEE, 77(2):257–286, 1989.
[10] R. Schapire and Y. Singer. Improved boosting algorithms using confidence-rated predictions. Machine Learning, 37(3):297–336, 1999.
[11] Y. A. Sheikh, A. Datta, and T. Kanade. On the sustained tracking of human motion. In
Proc. FG, 2008.
[12] J. Sochman and J. Matas. Waldboost ― learning for time constrained sequential detection. In Proc. CVPR, volume 2, pages 150–156, 2005.
[13] S. Uchida and K. Amamoto. Early recognition of sequential patterns by classifier combination. In Proc. ICPR, 2008.
[14] V. N. Vapnik. The Nature of Statistical Learning Theory. Springer, 1995.
[15] H. Zou, J. Zhu, and T. Hastie. New multicategory boosting algorithms based on multicategory Fisher-consistent losses. The Annals of Applied Statistics, 2(4):1290–1306,
2008.