T. TOMMASI ET AL.: LEVERAGING PRIOR KNOWLEDGE FOR ONLINE LEARNING

1

Leveraging over prior knowledge for online
learning of visual categories
Tatiana Tommasi121

Idiap Research Institute,
Martigny, CH

2

École Polytechnique Fédérale EPFL
Lausanne, CH

3

Toyota Technological Institute
Chicago, USA

ttommasi@idiap.ch

Francesco Orabona3
francesco@orabona.com

Mohsen Kaboli1
mkaboli@idiap.ch

Barbara Caputo1
bcaputo@idiap.ch

Abstract
Open ended learning is a dynamic process based on the continuous analysis of newdata, guided by past experience. On one side it is helpful to take advantage of priorknowledge when only few information on a new task is available (transfer learning). On
the other, it is important to continuously update an existing model so to exploit the newincoming data, especially if their informative content is very different from what is already known (online learning). Until today these two aspects of the learning process
have been tackled separately. In this paper we propose an algorithm that takes the best ofboth worlds: we consider a sequential learning setting, and we exploit the potentiality ofknowledge transfer with a computationally cheap solution. At the same time, by relying
on past experience we boost online learning to predict reliably on future problems. A
theoretical analysis, coupled with extensive experiments, show that our approach performs well in terms of the online number of training mistakes, as well as in terms of
performance on separate test sets.

1

Introduction

The underlying main goal of all research in visual recognition is to enable vision-based artificial systems to operate autonomously in the real world. However, even the best system wecan currently engineer is bound to fail whenever the setting is not heavily constrained. This isbecause the real world is generally too nuanced, too complicated and too unpredictable to besummarized within a limited set of specifications. There will be inevitably novel situations
and the system will always have gaps, conflicts or ambiguities in its own knowledge andcapabilities. This calls for algorithms able to support open ended learning of visual classes.
The open ended learning issue, i.e. the ability to learn a new detected class continuously
over time, has been typically addressed in a fragmented fashion in the literature. A firstcomponent is that of transfer learning, i.e. the ability to leverage over prior knowledge whenlearning a new class, especially in presence of few training data [10, 11, 15, 17, 18]. A
second component is that of updating continuously the learned visual class, as new samples
c 2012. The copyright of this document resides with its authors.
It may be distributed unchanged freely in print or electronic forms.

2

T. TOMMASI ET AL.: LEVERAGING PRIOR KNOWLEDGE FOR ONLINE LEARNING

arrive sequentially. The dominant approach in the literature here is that of online learning:
predictions are made on the fly and the model is progressively updated at each step, on thebasis of the given true label. An attractive feature of this family of algorithms is that they
aim at minimizing the number of total mistakes on the incoming samples (mistake-bound).
In this paper we propose to merge together these two components, using the prior knowledge sources for initializing the online learning process on a new target task through transfer
learning. This has two main advantages: (1) by using a principled transfer learning process
we can study the relation between the old sources and the new target. Within this framework, few samples might be sufficient to indicate in which part of the original space thecorrect solution (the best in term of generalization capacity) should be sought. (2) we show
theoretically that a good initialization for the online learning process produces a tighter mistake bound compared to previous work [18], while empirically improving the recognition
performance on an unseen test set. Globally an expensive transfer learning approach is used
only at the beginning, therefore limiting the computational burden. Then, a fast and efficientonline approach is applied. We choose the Passive Aggressive online learning algorithm[4], and we show how to initialize it in two different fashions with a state of the art transfer
learning method [17]. For each of the two versions of the algorithm, we derive the relative
mistake bound, which provide us with a deeper understanding of the methods. Experimentson the object categorization domain show the potential of our approach.
The paper is organized as follows: after a brief review of related works in this section,
we outline the Passive Aggressive method (section 2.1), and describe two existent batchand online transfer learning algorithms (sections 2.2 and 2.3) on which we build. The newderived algorithms, together with their theoretical analysis are introduced in section 2.4.
Section 3 reports our findings and comments the implications of the results. We conclude
with an overall discussion.
Related Work To our knowledge, the most similar approach to ours presented in the literature is Online Transfer Learning (OTL) [18]. Based on ensemble learning, it builds onlinea prediction function on the data of the target domain, and mix it with the old prediction
function learned on the source domain. The weights for the combination are adjusted dynamically on the basis of a loss function which evaluates the difference among the current
prediction and the correct label of any new incoming sample. This method does not consider
the case of transfer from multiple sources: for a single prior knowledge model a theoreticalanalysis demonstrates the existence of a mistake bound for OTL.
It has been shown that for recommender problems [1] and robotics applications [5] learning online on a new task with a good initialization based on source knowledge can be very
helpful. [13, 14] present active learning techniques which, by leveraging over different but
related source domains, get advantage on a new target, querying experts for more labeleddata only when necessary. Recently [9] introduced an online approach based on Gaussian
process regression for rapidly adapting pre-trained classifiers to a new test domain improving
the performance in face detection problems.

2

The Learning Approach

In this section we introduce formally the notation and we briefly recap the techniques on
which we build before presenting our learning algorithm.
We consider the case in which each instance is represented by a vector x ∈ Rd associatedto a unique label y ∈ {−1, 1} and the prediction mechanism is based on a hyperplane which

T. TOMMASI ET AL.: LEVERAGING PRIOR KNOWLEDGE FOR ONLINE LEARNING

3

divides the instance space into two parts. This hyperplane is defined by its orthogonal vector
w· x ). We will also assume without loss ofw ∈ Rd and the predicted label is given by sign(wgenerality that kxxt k ≤ 1. We also define the hinge loss with margin 1 of a classifier w overan instance/label pair (xx, y) as
w· x , y) = max{0, 1 − yw
w· x } .
`H (w

2.1

(1)

Online Learning

In the online learning framework a learner is presented with a sequence of instances xt , t =1, . . . , T . After each instance xt it generates the corresponding prediction. Then, the truelabel yt is given to the learner, that uses this feedback to update its hypothesis for future
trials. The aim of an online algorithm is to minimize its cumulative loss on the sequence of
data, measured using an arbitrary loss function. For a thorough introduction to the online
learning theory we refer the reader to [3].
In the linear setting defined above, at each step we estimate the hyperplane wt and predict
wt · xt ), while the quantity wt · xt , that corresponds to the distance between thewith sign(winstance and the hyperplane, can be roughly seen as the confidence on the prediction.
We focus here on the Passive Aggressive algorithm (PA) [4]. It learns an online classifier
which is updated at each step minimizing an objective function that trades off the maximum
closeness to the current classifier and the hinge loss on the most recent example1 . Startingfrom an arbitrary hypothesis, w 1 , at the t−th round PA is updated solving the following
optimization problem
1
wt+1 = argmin kw
w − wt k2 +Cξ
2
w

s.t.

w· xt , yt ) ≤ ξ
`H (w

and

ξ ≥0,

(2)

that results in a simple closed form
wt+1 = wt + γt yt xt
wt · xt , yt )`H (wwhere γt = min C,,
kxxt k2(3)

where C is the aggressiveness parameter that trades off the two quantities in (2). Hence thehypothesis is updated each time there is a prediction error, or the prediction is correct but themagnitude of the prediction is too low, i.e. the algorithm is not confident enough. When PA
is implemented in dual variables [4], each update requires the computation of γt which costs
O(t) where t indicates the number of samples seen till that moment. Considering a full set
of T instances, the total computational complexity of PA is O(T 2 ).

2.2

Transfer Learning

Among the existing transfer learning approaches we consider the Multi-KT algorithm [17].
Its main advantage is that it proposes a principled solution to evaluate automatically the
relatedness among multiple sources and the new target task. A discriminative model for thetarget task is then learned with the condition of closeness to a weighted combination of priorknowledge models.
More formally, we suppose to have k binary source tasks each containing Nk samples(xxi , yi ) i = 1, . . . , Nk . A discriminative model is learned for each task in terms of a linear
1 We consider the Passive Aggressive version defined as PA-I in [4] that for simplicity we denote by PA.

4

T. TOMMASI ET AL.: LEVERAGING PRIOR KNOWLEDGE FOR ONLINE LEARNING

w j · x for j = 1, . . . , k . For a novel target problem with T available training
function h j (xx) = ŵsamples living in the same data space of the sources (xxt , yt ) t = 1, . . . , T , Multi-KT solves
the following optimization problem [17]:2k1
w − ∑ β j ŵwj
minw ,b 2
j=1+

C T∑ (yi − w · xt − b)2 .
2 t=1

(4)

This problem has the same objective function of LS-SVM [16] where the second term is thesquare loss, while the regularizer has been modified to impose closeness between the newtarget model and a linear combination of source models. Here the weights β j assigned toT
β k2 ≤ 1, where
each prior knowledge are found by minimizing ∑t=1
`H (ỹt , yt ) subject to kβỹt is the leave-one-out prediction for the t−th sample, and β = (β1 , . . . , βk ) . With thisformulation the final prediction function on the target task is!
kf (xx) = w · x + b =T∑ β j ŵw j + ∑ αt xt

j=1·x +b ,

(5)t=1

where αt are the coefficients of the support vectors for the new target problem. From thecomputational point of view the runtime for Multi-KT is O(T 3 + k T 2 ) where the first termis related to solving the problem in (4) while the second term is the cost of calculating yt ỹt .
We are not taking into consideration the learning process on the source tasks, supposing thatthe prior knowledge models are given as input to the Multi-KT algorithm.

2.3

OTL: Online Transfer Learning

The OTL algorithm proposed in [18] is a two stages online learning approach which combines a source classifier h(xx) with a prediction function f (xx) learned online on the target
domain. Specifically f is learned from a sequence of samples (xxt , yt ) t = 1, . . . , T . At thet−trial the learner receives an instance xt and the prediction function ft is updated to ft+1
according to the PA rule (3) with ft (xxt ) = wt · xt . In addition, the corresponding class label
is predicted by the following ensamble function [18]:1ŷt = sign σt Π(h(xxt )) + τt Π( ft (xxt )) −,(6)2
where Π(x) = max{0, min{1, x+12 }} is a normalization function. The weights are initialized
as σ1 = τ1 = 12 and at each step they are adjusted dynamically according to [18]σt+1 =

σt st (h),σt st (h) + τt st ( ft )

τt+1 =

τt st ( ft ),σt st (h) + τt st ( ft )(7)

where st (g) = exp{− 12 `S (Π(g(xxt )), Π(yt )))} and `S (z, y) = (z − y)2 is the loss function.
The proposed method originally supposes the existence of one unique source domain. In
case of multiple source tasks we suggest the naïve solution of averaging all the prior knowledge models and use the mean classifier as h(xx). A different solution consists in assigning
one weight to each source knowledge. In this case we start from σ1 = ∑kj=1 σ j,1 = τ1 = 21
1
for j = 1, . . . , k and then we update the weights with
with σ j,1 = 2k
σ j,t+1 =σ j,t st (h j ),k∑ j=1 σ j,t st (h j ) + τt st ( ft )

τt+1 =

τt st ( ft ).
k
∑ j=1 σ j,t st (h j ) + τt st ( ft )(8)

T. TOMMASI ET AL.: LEVERAGING PRIOR KNOWLEDGE FOR ONLINE LEARNING

5

If we neglect the prior knowledge learning process as before, the total computational complexity of OTL matches the one of the online learning method used, since the cost of (7) (and(8)) is O(1) . Thus we have O(T 2 ) as for PA.
Theoretical Analysis In the particular case of one single source task, for the OTL algorithm is possible to prove a bound on the number of mistakes M made during the online
learning process (see Theorem 1 and its proof in [18]):

M ≤ 4 min Σh , Σ f + 8 ln 2 ,(9)TT
where Σh = ∑t=1
`S (Π(h(xxt )), Π(yt ))) and Σ f = ∑t=1
`S (Π( ft (xxt )), Π(yt ))) . Note that thefirst stage in OTL is based on the PA algorithm, that uses the hinge loss, while the second
stage uses the square loss. Hence in [18] the Authors observe that, if we denote by Mh and M f
the mistake bound of the model h and ft respectively, and we assume `S (Π(h(xxt )), Π(yt ))) ≈1
1Sx
4 Mh and ` (Π( ft (x t )), Π(yt ))) ≈ 4 M f , then M ≤ min{Mh , M f } + 8 ln 2.

2.4

TROL: TRansfer initializes Online Learning

The main issue faced by OTL is how to combine online the source and the target knowledge
that are learned independently in an initial stage. On the other hand Multi-KT provides amodel for the new target problem on the basis of very few training samples exploiting a
reliable combination of prior models. This is a batch approach directly meant to minimize
the generalization error of the obtained target model. Since Multi-KT operates in the small
setting scenario, we can use it to define an hybrid batch-online learning approach different
from OTL. It is based on two phases: at the beginning n target training samples are given
as input to Multi-KT which outputs the corresponding target model, and as second step, thismodel is used to initialize the online learning process. Using PA, the updated solution will
be at each step close to the previous one: this helps keeping the advantage given by MultiKT together with the proper introduction of new information when necessary. We name thisalgorithm TROL: TRansfer initializes Online Learning.
Formally, training Multi-KT on n target samples consists in solving the optimization
w j + ∑ni=1 αi x i ) is then introduced inproblem in (4). The obtained model w 1 = (∑kj=1 β j ŵ(2) as initialization when learning from the (n + 1)−th training sample on. The Multi-KT
algorithm is applied on n (typically n ≤ 10) training samples and k prior knowledge sources,
before starting the online learning process. Hence the final cost is O(T 2 + n3 + kn2 ), thatfor enough samples T is dominated by the complexity of PA. In other words the addedcomplexity of using Multi-KT on n samples is negligible.
Theoretical Analysis With respect to PA, a good initialization model can improve themistake bound. In fact it is easy to generalize the mistake bound in [4] to the case of usinga w 1 different from the null vector. In this case we have that the number M of prediction
mistakes satisfies
!


T
1
1
2
H
kuu − w 1 k +C ∑ ` (uu· xt , yt ) .
(10)
M ≤ 2 max 1,
C2
t=1
From this bound we have that it is possible to improve the performance of the algorithm, atleast in the worst case scenario, by initializing it with a classifier that is close to the optimal
one.

6

T. TOMMASI ET AL.: LEVERAGING PRIOR KNOWLEDGE FOR ONLINE LEARNING

2.4.1

Update the transfer weights

The learning solution described above to integrate old and new knowledge is based on aproper initialization of the online process. Still, the old knowledge is not directly reweighted
during the learning process. We show here that it is possible to use a simple feature augmentation trick to have the same starting condition of TROL together with a progressive updateof the source and the target knowledge weights in time. We call this algorithm TROL+.
Given the model w 1 , we can evaluate its prediction on each new training samples as
w 1 · xt . Cropping the obtained value between -1 and 1, similarly to OTL, to limit the norm of
the added dimension, we use this prediction as the (d + 1)-th element in the feature vector
descriptor of xt . So we define
xt0 = (xxt , νt ) ∈ Rd+1

where νt = max{−1, min{1, w 1 · xt }} .

The samples with such a modified representation enter the PA algorithm initialized now with
w01 · x 01 ) = sign(ν1 ) while for any t
w 01 = (0, . . . , 0, 1) ∈ Rd+1 . At t = 1 PA predicts with sign(wthe updating rule in (3) results in
wt0 · xt0 , yt )
`H (w
0
wt+1
= wt0 + γt yt xt0 where γt = min C,,(11)
kxxt0 k2
and the predictions are
t−1

wt0 · xt0 = ∑ γi yi (xxi · xt + νi νt ) .

(12)

i=1

Hence the hyperplane wt0 can be thought as composed by two parts, one for the old knowledge
and one for the knowledge coming from the new instances. Of course this approach can begeneralized to allow the use of k different prior models w 1j j = 1, . . . , k , expanding the input
vectors with k new dimensions
xt0 = (xxt , ν1,t , . . . , νk,t ) ∈ Rd+k

where

ν j,t = max{−1, min{1, w 1j · xt }} .

(13)

Theoretical Analysis A theoretical support to TROL+ is given by the following theorem
Theorem 1 Let (xxt0 , yt ), t = 1, . . . , T be a sequence of transformed instances as in (13),yt ∈ {+1, −1} and kxxt k ≤ 1 for all t. Then, for any vector u ∈ Rd+k the number of prediction
mistakes made by TROL+ on this sequence of examples is bounded from above by
!


T
1
1
0 2
H
0
M ≤ 2 max (1 + k),
kuu − w 1 k +C ∑ ` (uu· xt , yt ) ,C2
t=1
where C is the aggressiveness parameter provided to TROL+.
The proof follows immediately by considering the bound in (10) and the increased dimensionality of the instances. To compare this bound to the one of OTL, let us set C = 1
and use only one prior knowledge, i.e. k = 1. Given that the bound in (10) holds for any u ,we can worsen the bound by setting u to be the optimalalone or one for the new knowledgeT
the prior knowledge alone, to have that M ≤ 4 min Σh , Σ f , where Σh = ∑t=1
`H (vt , yt ) ≤TT`H (w1 · xt , yt ), and Σ f = minu 12 kuuk2 + ∑t=1
`H (uu· xt , yt ). Hence, as in OTL, the perfor∑t=1
mance of TROL+ is always close to the best between the performance of the prior and the

T. TOMMASI ET AL.: LEVERAGING PRIOR KNOWLEDGE FOR ONLINE LEARNING

7

performance of the best batch classifier over the new knowledge. However here we have thehinge loss `H and not the square loss `S as in OTL. It is known that the first one approximates
the real 0/1 loss better than the second [2, 12]. Moreover, as discussed in section 2.3, theOTL bound does not directly link the performance to the two stages of the algorithm, while
in TROL+ there is only one layer so we do not have this problem. Another difference withOTL is that TROL+ will make only a finite number of mistakes if there is an hyperplane uthat correctly classifies all the samples. In the next section we will show that this theoreticaladvantage is also evident in the empirical experiments.

3

Experiments

We ran experiments on the Caltech-256 dataset [8], following the setting chosen in [17].
Besides considering the full database, we focused on some selected classes to show theperformance of transfer learning in case of different level of relatedness between the source
and target tasks and to evaluate the eventual negative transfer (decrease in performance w.r.t
learning from scratch [11]). Feature-wise, we used the publicly available SIFT descriptors of[7]. The training (test) set for each class consisted of 60 (100) samples. Each set contains anequal number of positive (object class) and negative (background) examples. We considered
10 random orderings of the samples for each class and we present the average results on theseten splits both in terms of the average error rate for the online methods and of the recognition
rate produced by the current training solution on the test set. The training set are organizedsuch that any positive sample is always followed by a negative one and vice-versa. For
all experiments we used the Gaussian kernel K(xx, x 0 ) = exp(− δ1 kxx − x 0 k2 ), fixing δ to themean of the pairwise distances among the samples. For the particular feature augmentation
technique used in TROL+, we considered the linear combination of two kernels (K1 + K2 )where the first is Gaussian and deals with the SIFT feature descriptor, while the second is alinear kernel applied on the extra feature elements obtained by the prediction of the priors.
We benchmarked TROL and TROL+ against PA trained on the target samples, Multi-KT
and OTL, where in case of multiple priors we considered the average of all the available
models as source classifier. We also defined other three baselines:
NOTR This is a batch strategy corresponding to learn using only the target samples (notransfer). It uses LS-SVM on the available set of training samples at each step.
M-OTL This is our modified version of OTL able to assign a different weight to each priorknowledge in case of multiple sources, with the update rule defined in (8).
TR-OTL This method considers as source knowledge for OTL the same Multi-KT output
that we use as initialization in TROL.
All the online techniques initialized with Multi-KT use its output model learned overn = 6 training images, corresponding to three positive and three negative samples. All thesource models have been learned with LS-SVM. The value of the C parameter is chosen bycross validation on the sources and we used the same for the batch methods (Multi-KT and
NOTR) applied on the new task. The C value for all the online methods is instead fixed to 1.
Single source This is the setting in which OTL was originally presented and evaluated. We
ran experiments on different couple of classes, chosen inside the macro categories defined by
the dataset taxonomy (e.g. related objects in food-containers) or extracted randomly. For all
the couples we consider one of the classes as target task and the other as source knowledge,
repeating the experiments twice switching the role of the two classes. Three representative
results are reported in Figure 1. For the unrelated couple fireworks-treadmill (left column),

8

T. TOMMASI ET AL.: LEVERAGING PRIOR KNOWLEDGE FOR ONLINE LEARNING
schoolbus−dog

0.9

0.85

0.85

0.85
0.8
0.75
NOTR
Multi−KT [17]PA
OTL [18]
TR−OTL
TROL
TROL+

0.7

0

10

20
30
40
50
Number of Training Samples

0.8
0.75
NOTR
Multi−KT [17]PA
OTL [18]
TR−OTL
TROL
TROL+

0.7
0.65
0.6
0.55
0

60

10

fireworks−treadmill, online mistakes

0.6
0.55
0

60

0.32
0.3
0.28
0.26

10

20
30
40
50
Number of Training Samples

60

coffee mug−beer mug, online mistakes
0.25

OTL [18]
TR−OTL
TROL
TROL+

0.3
Average Error Rate

0.34

NOTR
Multi−KT [17]PA
OTL [18]
TR−OTL
TROL
TROL+

0.7

schoolbus−dog, online mistakes
0.35

OTL [18]
TR−OTL
TROL
TROL+

0.36

0.8
0.75

0.65

Average Error Rate

0.38

20
30
40
50
Number of Training Samples

Recognition Rate

0.95

0.9

0.65

Average Error Ratecoffee mug−beer mug

0.95

0.9
Recognition Rate

Recognition Rate

fireworks−treadmill
0.95

0.25

0.2

OTL [18]
TR−OTL
TROL
TROL+

0.2

0.15

0.1

0.15
0.24
0.22
0

10

20
30
40
50
Number of Training Samples

60

0.1
0

10

20
30
40
50
Number of Training Samples

60

0.05
0

10

20
30
40
50
Number of Training Samples

60

Figure 1: Single source experiments: couples of classes with increasing relatedness fromleft to right, as empirically shown by the growing advantage of Multi-KT over NOTR. Top
line: recognition rate results on the test set as a function of the number of training samples.
Bottom line: corresponding rate of mistakes for the online learning methods.
TROL and TROL+ matches the recognition performance of the corresponding no transfer
online learning method PA, while OTL and TR-OTL suffer for negative transfer. The caseschoolbus-dog (middle column) represents an intermediate condition, where transfer learning can be helpful. Here TROL and TROL+ present a small advantage over TR-OTL interms of recognition on the test set, while TROL+ and TR-OTL show the best performanceon the mistake rate. Finally for coffee-mugs and beer-mugs (right column) all the transfer
learning methods perform much better than learning from scratch with a particular advantageof TROL+ in terms of online mistake rate.
Multiple sources We focus here on the case where multiple priors are available. Figure
2 shows the results on a group of four unrelated classes (originally used in [6]). Each ofthem is considered in turn as target task while the remaining ones define three source knowledges. Despite the difference among the object categories, Multi-KT is able to define a goodcombination of priors and exploit it when learning on the target, obtaining extremely goodresults in classification. All the online methods initialized with Multi-KT (TROL, TROL+,
TR-OTL) matches its recognition performance after 10 training samples. OTL considering
the average source knowledge shows instead negative transfer. M-OTL, based on different
weights for each source classifier, does not have any advantage w.r.t learning from scratch(PA), but at least it is not worse. TROL, TROL+ and TR-OTL have the best performancewith respect to all the other baselines in terms of average rate of mistakes. A special remark is necessary here for the method named “TROL+ (priors)”. This refers to the case inwhich each prior knowledge model is considered as a separate source, so we are augmenting the feature space with k = 3 new elements. This method outperforms OTL and M-OTL
both in terms of mistake rate and recognition on the test set, roughly matching the batch
performances of Multi-KT after 20 training samples.
The four plots on the right in Figure 2 show how the weights given to source and target
knowledge change in the OTL-related methods. The information obtained as output from
Multi-KT, used as source in TR-OTL, maintains a high weight in time. This demonstrates

9

T. TOMMASI ET AL.: LEVERAGING PRIOR KNOWLEDGE FOR ONLINE LEARNING
airplanes

∗

faces

1

TROL
TROL+
TROL+ (priors)
OTL [18]
M−OTL
TR−OTL

0.4

NOTR
Multi−KT [17]
PA
TROL
TROL+
TROL+ (priors)
OTL [18]
M−OTL
TR−OTL

0.8
0.75
0.7
0.65
0

10

20
30
40
50
Number of Training Samples

60

0.4

0
0

0.25

0.6
0.4
0.2

10

20

30

40

50

0
0

60

Number of Training Samples

0.2

leopards

∗

1

1

0.1

0.8

0.8

0
0

10

20
30
40
50
Number of Training Samples

60

0.6
0.4
0.2
0
0

20

30

40

motorbikes

0.15

0.05

10

50

∗

0.6
0.4
0.2

10

20

30

40

50

Number of Training Samples

60

0
0

10

20

30

40

50

Number of Training Samples

Figure 2: Four unrelated classes: airplanes, motorbike, faces, leopards. Left: recognition rate
results on the test set as a function of the number of training samples. Middle: corresponding
rate of mistakes for the online learning methods. Right: value of the weights given to source(S) and target (T) knowledge by the OTL-related methods for one split. The line “M-OTL(S)” corresponds to the sum of all the weights separately given to the sources. The stars
indicate the weight given to each of the source classes by Multi-KT and used in the input
model to TR-OTL.
256 classes, online mistakes

256 classes
0.95

0.26

0.9

0.24

NOTR
Multi−KT [17]
PA
TROL
TROL+
TROL+ (priors)
OTL [18]
M−OTL
TR−OTL

0.7
0.65
0.6
10

20
30
40
50
Number of Training Samples

60

Average Error Rate

Recognition Rate

0.8
0.75

0.55
0

TROL
TROL+
TROL+ (priors)
OTL [18]
M−OTL
TR−OTL

0.22

0.85

0.2
0.18
0.16
0.14
0.12
0.1
0.08
0

10

20
30
40
50
Number of Training Samples

60

Figure 3: Recognition rate results on the test set as a function of the number of training
samples and corresponding average error rate for the online methods on the whole Caltech256 dataset. All the results are obtained as average over each of the classes considered astarget task with the remaining 255 used as sources.
its usefulness for the learning process. On the other hand, the source knowledge looses its
importance when the number of training samples increase, or show a small weight, for OTL
and M-OTL.
Figure 3 presents the results for the full Caltech-256 dataset. Here the online method
TROL performs as the batch algorithm Multi-KT and shows the best results w.r.t. all theother baselines in terms of mistake rate. Both OTL and TR-OTL do not seem able to use
properly the new information given by the incoming training samples, showing almost aflat performance on the test set. We see again the good results of “TROL+ (priors)” that
directly using and reweighting multiple prior knowledges outperforms OTL and M-OTL,
and matches TR-OTL in terms of average error rate with 60 training samples.
In summary, over all the experiments TROL and TROL+ are better or at least as good as
PA, never showing negative transfer, and can match the batch performance of Multi-KT on
the test set. In terms of online mistakes, they outperform all the other baselines.

460

Number of Training Samples

Weights

0.85

0.3

0.6

0.8

0.2

Weights

0.9

Average Error Rate

Recognition Rate

0.35

Weights

0.45

1
0.95

∗

1

OTL (S)OTL (T)M−OTL (S)M−OTL (T)TR−OTL (S)
TR−OTL (T)0.8

Weights

4 classes unrelated, online mistakes

4 classes unrelated

Conclusions

In this paper we addressed the issue of open ended learning of visual categories, casting astate of the art transfer learning method, Multi-KT [17], into the online learning framework.

60

10

T. TOMMASI ET AL.: LEVERAGING PRIOR KNOWLEDGE FOR ONLINE LEARNING

This results into an algorithm where the available priors are used in a principled manner
to initialize the online learning process. This allows us to exploit the potentiality of thetransfer method without paying the computational cost of a batch approach, possibly limited
to an initial budget. We call our algorithm TRansfer initialized Online Learning (TROL).
We presented two different version of the approach, for each deriving the relative mistakebound, and we showed with extensive experiments on the visual categorization problem thevalue of our method.
Acknowledgments This work was supported by the EMMA project thanks to the Hasler
foundation (www.haslerstiftung.ch).

References[1] D. Agarwal, B.C. Chen, and P. Elango. Fast online learning through offline initialization for time-sensitive recommendation. In Proceedings of the International conferenceon Knowledge discovery and data mining (KDD), 2010.
[2] C. M. Bishop. Pattern Recognition and Machine Learning (Information Science andStatistics). Springer-Verlag New York, Inc., Secaucus, NJ, USA, 2006.
[3] N. Cesa-Bianchi and G. Lugosi. Prediction, learning, and games. Cambridge University Press, 2006.
[4] K. Crammer, O. Dekel, J. Keshet, S. Shalev-Shwartz, and Y. Singer. Online passiveaggressive algorithms. Journal of Machine Learning Research, 7:551–585, 2006.
[5] J. S. de la Cruz, D. Kulić, and W. Owen. Online incremental learning of inverse dynamics incorporating prior knowledge. In Proceedings of the International conference
on Autonomous and intelligent systems (AIS), 2011.
[6] Li Fei-Fei, R. Fergus, and P. Perona. A bayesian approach to unsupervised one-shotlearning of object categories. In Proceedings of the International Conference on Computer Vision (ICCV), 2003.
[7] P. Gehler and S. Nowozin. Let the kernel figure it out: Principled learning of preprocessing for kernel classifiers. In Proceedings of the IEEE Conference on Computer
Vision and Pattern Recognition (CVPR), 2009.
[8] G. Griffin, A. Holub, and P. Perona. Caltech 256 object category dataset. Technical
Report UCB/CSD-04-1366, California Institue of Technology, 2007.
[9] V. Jain and E. Learned-Miller. Online domain adaptation of a pre-trained cascade ofclassifiers. In Proceedings of the IEEE Conference on Computer Vision and Pattern
Recognition (CVPR), 2011.
[10] F. Orabona, C. Castellini, B. Caputo, E. Fiorilla, and G. Sandini. Model adaptation
with least-squares SVM for hand prosthetics. In Proceedings of ICRA - International
Conference on Robotics and Automation, pages 2897–2903, 2009.
[11] S. J. Pan and Q. Yang. A survey on transfer learning. IEEE Transactions on Knowledge
and Data Engineering, 22(10):1345–1359, October 2010.

T. TOMMASI ET AL.: LEVERAGING PRIOR KNOWLEDGE FOR ONLINE LEARNING

11[12] L. Rosasco, E. De Vito, A. Caponnetto, M. Piana, and A. Verri. Are loss functions all
the same? Neural Computation, 16(5):1063–1076, 2004.
[13] A. Saha, P. Rai, H. Daumé, S. Venkatasubramanian, and S. L. DuVall. Active supervised domain adaptation. In Proceedings of the European conference on Machinelearning and knowledge discovery in databases (ECML PKDD), 2011.
[14] X. Shi, W. Fan, and J. Ren. Actively transfer domain knowledge. In Proceedings of theEuropean conference on Machine Learning and Knowledge Discovery in Databases(ECML PKDD), 2008.
[15] E. Soria, J. Martin, R. Magdalena, M. Martinez, and A. Serrano. Handbook of Research on Machine Learning Applications, chapter L. Torrey and J. Shavlik, Transfer
Learning. IGI Global, 2009.
[16] J.A.K. Suykens, T. Van Gestel, J. De Brabanter, B. De Moor, and J. Vanderwalle. Least
Squares Support Vector Machines. World Scientific, 2002.
[17] T. Tommasi, F. Orabona, and B. Caputo. Safety in numbers: Learning categories fromfew examples with multi model knowledge transfer. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2010.
[18] P. Zhao and S. C. H. Hoi. OTL: A Framework of Online Transfer Learning. In Proceedings of the International Conference on Machine Learning (ICML), 2010.