Transfer Learning through Greedy Subset Selection
Ilja Kuzborskij1 , Francesco Orabona2 , and Barbara Caputo3
1

Idiap Research Institute, Centre du Parc, Rue Marconi 19, 1920 Martigny, SwitzerlandÉcole Polytechnique Fédérale de Lausanne (EPFL), Switzerland
ilja.kuzborskij@idiap.ch
2
Yahoo Labs, 229 West 43rd Street, 10036 New York, NY, USA
francesco@orabona.com
3
University of Rome La Sapienza, Dept. of Computer, Control and Management Engineering,Rome, Italy
caputo@dis.uniroma1.it

Abstract. We study the binary transfer learning problem, focusing on how to
select sources from a large pool and how to combine them to yield a good performance on a target task. In particular, we consider the transfer learning setting
where one does not have direct access to the source data, but rather employs thesource hypotheses trained from them. Building on the literature on the best subset
selection problem, we propose an efficient algorithm that selects relevant source
hypotheses and feature dimensions simultaneously. On three computer visiondatasets we achieve state-of-the-art results, substantially outperforming transfer
learning and popular feature selection baselines in a small-sample setting. Also,
we theoretically prove that, under reasonable assumptions on the source hypotheses, our algorithm can learn effectively from few examples.

1

Introduction

It is a truth universally acknowledged that learning algorithms perform better whentrained on a lot of data. This is even more true when facing noisy or “hard” problems
such as large-scale visual recognition [7]. However, considering object detection tasks,
access to training data might be restricted. As noted in [23], the distribution of realworld objects is highly skewed, with few objects occurring very often, and many with
few instances. Moreover, learning systems are often not trained from scratch: usually
they can be build on previous knowledge acquired over time on related tasks [21]. The
scenario of learning from few examples by transferring from what is already known
to the learner is collectively known as Transfer Learning. The target domain usuallyindicates the task at hand and the source domain the prior knowledge of the learner.
Most of the transfer learning algorithms proposed in the recent years assume accessto the training data coming from both source and target domains [21]. While featuring
good practical performance [11], and well understood theoretical guarantees [2], theyoften demonstrate poor scalability w.r.t. number of sources. An alternative direction,
known as a Hypothesis Transfer Learning (HTL) [15, 3], consists in transfering from thesource hypotheses, that is classifiers trained from them. This framework is practicallyvery attractive [1, 24, 16], as it treats source hypotheses as black boxes without any
regard of their inner workings.

The goal of this paper is to develop an HTL algorithm able to deal effectively andefficiently with a large number of sources. To this end, we cast Hypothesis Transfer
Learning as a problem of efficient selection and combination of source hypotheses froma large pool. We pose it as a subset selection problem and build on results from the literature [6, 27]. We develop a greedy algorithm, GreedyTL, which attains the state ofart performance given a very limited amount of data from the target domain, while able
to scale well over the large number of sources. Our key contribution is a L2-regularizedvariant of the Forward Regression algorithm [13]. Since our algorithm can be viewed
both as feature selection and hypothesis transfer learning algorithm, we extensively
evaluate it against popular feature selection and transfer learning baselines. We empirically demonstrate that all baselines but GreedyTL, fail in most small-sample transfer
learning scenarios, thus proving the critical role of regularization in our formulation.
Experiments over three datasets show the power of our approach: we obtain state-ofthe-art results in tasks with up to 1000 classes, totalling 1.2 million examples, with only
11 to 20 training examples from the target domain. We back our experimental results
by proving generalization bounds showing that, under reasonable assumptions on thesource hypotheses, our algorithm is able to learn effectively with a very limited data.

2

Related WorkIn the literature there are several transfer learning settings [21, 2, 22, 11]. We focus on
the Hypothesis Transfer Learning framework (HTL, [15, 3]). There, it is required tohave access only to source hypotheses, that is classifiers or regressors trained on thesource domains. No assumptions are made on how these source hypotheses are trained,
or about their inner workings: they are treated as “black boxes”, in spirit similar toclassifier-generated visual descriptors such as Classemes [4] or Object-Bank [17]. Several works proposed HTL for visual learning [1, 24, 20], some exploiting more explicitly the connection with classemes-like approaches [14], demonstrating an intriguing
potential. Although offering scalability, HTL-based approaches proposed so far havebeen tested on problems with less than a few hundred of sources [24], already showing
some difficulties in selecting informative sources.
Recently, the growing need to deal with large data collections [7, 5] has started tochange the focus and challenges of research in transfer learning. Scalability with respect
to the amount of data and the ability to identify and separate informative sources fromthose carrying noise for the task at hand have become critical issues. Some attempts
have been made in this direction [18, 25]. However, all these approaches assume accessto all source training data. Moreover, in many of these works the use of richer sources of
information has been supported by an increase in the information available in the target
domain as well. From an intuitive point of view, this corresponds to having more data
points than dimensions. Of course, this makes the learning and selection process easier,but in many applications it is not a reasonable hypothesis. Also, none of the proposed
algorithms has a theoretical backing. On the other hand, HTL-based approaches proposed so far have been tested only on problems with less than a few hundred of sources[24], already showing some difficulties in selecting informative sources.

3

Transfer Learning through Subset Selection

Definitions. We will denote with small and capital bold letters respectively column vectors and matrices, e.g. α = [α1 , α2 , . . . , αd ]T ∈ Rd and A ∈ Rd1 ×d2 . The subvectorof a with rows indexed by set S is aS , while the square submatrix of A with rows andcolumns indexed by set S is AS . For x ∈ Rd , the support of x is supp(x) = {i : xi 6=0, i ∈ {1, . . . , d}}. Denoting by X and Y respectively the input and output space ofthe learning problem, the training set is {(xi , yi )}m
i=1 , drawn i.i.d. from the probability
distribution p defined over X × Y. We will focus on the binary classification problem
so Y = {−1, 1}, and, without loss of generality, X = {x : kxk2 ≤ 1, x ∈ Rd }.
To measure the accuracy of a learning algorithm, we have a non-negative loss function `(h(x), y), which measures the cost incurred predicting h(x) instead of y. In particular, we will focus on the square loss, `(h(x), y) = (h(x) − y)2 , for its appealing
computational properties. The risk of a hypothesis h, with respect to the probability
distribution p, is then defined as R(h) := E(x,y)∼p [`(h(x), y)], while the empiricalPm
1risk given a training set {(xi , yi )}m
i=1 is R̂(h) := mi=1 `(h(xi ), yi ). Whenever the
hypothesis is a linear predictor, that is, hw (x) = w> x, we will also use risk notationas R(w) = R(hw ) and R̂(w) = R̂(hw ).
nSource Selection. Assume, that we are given a finite source hypothesis set {hsrci }i=1m
and the training set {(xi , yi )}i=1 . As in previous works [19, 24, 14], we consider thetarget hypothesis to be of the form>
htrg
w,β (x) = w x +nXβi hsrc
i (x),(1)i=1where w and β are found by the learning procedure. The essential parameter here is β,that is the one controlling the influence of each source hypothesis. Previous works intransfer learning have focused on finding β such that minimizes the error on the training
set, subject to some condition on β. In particular, [24] have proposed to minimize theleave-one-out error w.r.t. β, subject to kβk2 ≤ τ , which is known to improve generalization for the right choice of τ [15]. A slightly different approach is to use kβk1 ≤ τregularization for this purpose [24], which is known to prefer β with the most coefficients equal to 0, thus assuming that the optimal β is sparse. Nonetheless, it is not clear
whether transfer learning tasks are always truly sparse in practice.
In this work we embrace a weaker assumption, namely, there exist up to k sourcesthat collectively improve the generalization on the target domain. Thus, we pose theproblem of the Source Selection as a minimization of the regularized empirical risk on
the target training set, while constraining the number of selected source hypotheses.
 m

src
src
>
k-Source Selection. Given the training set [x>i , h1 (xi ), . . . , hn (xi )] , yi
i=1
we have the optimal target hypothesis htrg
w? ,β ? by solving,no2
2(w? , β ? ) = arg min R̂(htrgw,β ) + λkwk2 + λkβk2 ,w,βs.t kwk0 + kβk0 ≤ k.

(2)

Notably, the problem (2) is a special case of the Subset Selection problem [6]:choose a subset of size k from the n observation variables, which collectively givethe best prediction on the variable of interest. However, the Subset Selection problem is
NP-hard [6]. In practice we can resort to algorithms generating approximate solutions,for many of which we have approximation guarantees. Hence, due to the extensive practical and theoretical results, we will treat the k-Source Selection as a Subset Selection
problem, building atop of existing guarantees.
We note that our formulation, (2), differs from the classical subset selection for
the fact that it is L2-regularized. This technical difference practically and theoreticallymakes an essential difference and it is the crucial part of our algorithm. First, L2 regularization is known to improve the generalization ability of empirical risk minimization.
Second, we show that regularization also improves the quality of the approximate solution in situations when the sources, or features, are correlated. At the same time, theexperimental evaluation corroborates our theoretical findings: Our formulation substantially outperforms standard subset selection, feature selection algorithms, and transfer
learning baselines.

4

Greedy Algorithm for k-Source Selection

In this section we state the algorithm proposed in this work, GreedyTL4 .
nGreedyTL. Let X ∈ Rm×d and y ∈ Rm be the standardized training set, {hsrci }i=1 ,source hypothesis set, and k andh λ, regularization parameters.
Then, denote C = Z > Zi
hsrc
1 (x1 ) · · ·hsrc
n (x1 )········
and b = Z > y, where Z = X hsrc·(x) · · · hsrc (x )1mn

, and select set S of size k asmfollows: (I) Initialize S ← ∅ and U ← {1, . . . , n + d}. (II) Keep populating S with−1 >i ∈ U , that maximize b>
S ((C + λI)S ) bS , as long as |S| ≤ k and U is non-empty.
Derivation of the Algorithm. We derive GreedyTL by extending the well known
Forward Regression (FR) algorithm [6], which gives an approximation to the subset
selection problem, the problem of our interest. FR is known to find good approximation
as far as features are uncorrelated [6]. In the following, we build upon FR by introducing
a Tikhonov (L2) regularization into the formulation. The purpose of regularization is
twofold: first, it improves the generalization ability of the empirical risk minimization,and second, it makes the algorithm more robust to the feature correlations, thus opting
to find better approximate solution.
First, we briefly formalize the subset selection problem. In a subset selection problem one tries to achieve a good prediction accuracy on the predictor random variable
Y , given a linear combination of a subset of the observation random variables {Xi }ni=1 .
The least squares subset selection then reads as
"
#
X
2
min
E (Y −
wi Xi ) .
|S|=k,w∈Rk

4i∈S

Source code is available at http://idiap.ch/∼ikuzbor/Now denote the covariance matrix of zero-mean unit-variance observation random variables by C, and the covariances between Y and {Xi }m
i=1 as b. By virtue of the analytic
solution to least-squares and using the introduced notation, we can also state the equiva−1 >lent Subset Selection problem: max|S|=k b>
S (C S ) bS . However, our goal is to obtainthe solution to (2), or a L2-regularized subset selection. Similarly to the unregularized subset selection, it is easy to get that (2) is equivalent to max|S|=k b>
S ((C S +λI)−1 )> bS . As said above, the Subset Selection problem is NP-hard, however, there
are number ways to approximate it in practice [13]. We choose FR for this task forits simplicity, appealing computational properties and provably good approximation
guarantees. Now, to apply FR to our problem, all we have to do is to provide it withnormalized (C + λI)−1 instead of C −1 .
In the basic formulation, FR requires to invert the covariance matrix at each iteration of a greedy search. Clearly, this naive approach gets prohibitive with the growth ofboth the number of variables and desired subset size, since its computational complexity would be in O(k(d + n)4 ). However, we note that in transfer learning one typicallyassumes that training set is much smaller than sources and feature dimension. For thisreason we apply rank-one updates w.r.t. the dual solution of regularized subset selection,
so that the size of the inverted matrix does not change. The computational complexity
then improves to O(km2 (d + n)2 ).
Theoretical Guarantees. We now focus on the analysis of the generalization propertiesof GreedyTL for solving k-Source Selection problem (2). ThroughoutPnthis paragraph>src
we will consider a truncated target predictor htrg
(x)
:=
T
w
x
+
i=1 βi hi (x) ,w,βwith T(a) := min{max{a, −1}, 1}. First we state the bound on the risk of an approximate solution returned by GreedyTL. 5
Theorem 1. Let GreedyTL generate the solution (ŵ, β̂), given the training set (X, y),
src 2
n
src
source hypotheses {hsrci }i=1 with τ∞ := maxi {khi k∞ }, hyperparameters λ and k.
Then with high probability,R1
where R̂src := m

htrg
ŵ,β̂

Pm





− R̂ htrg
≤ Õ
ŵ,β̂

i=1 `

src
1 + kτ∞
+
λm

r

src
1 + kτ∞
R̂src
λm

!
,



P
src
.
yi , Tj∈supp(β̂) β̂i hj (xi )This results in a generalization bound which tells us how close the performance of
the algorithm on the test set will be to the one on the training set. The key quantity
here is R̂src , which captures the quality of the sources selected by the algorithm. To
understand its impact, assume that λ = O(1). The boundq has two terms, a fast oneof the order of Õ(k/m) and a slow one of the order Õ( R̂src k/m). When m goes toinfinity and R̂src 6=q0 the slow term will dominate the convergence rate, giving us a rateof the order of Õ( R̂src k/m). If R̂src = 0 the slow term completely disappears, giving

us a so called fast rate of convergence of Õ(k/m). On the other hand, for any finite m
5

Proofs for theorems can be found in the supplementary material.

if R̂src is small enough, in particular of the order of Õ(k/m), we still have a rate of theorder of Õ(k/m). Hence, the quantity R̂src will govern the finite sample and asymptotic
behavior of the algorithm, predicting a faster convergence in both regimes when it issmall. In other words, when the source and target tasks are similar, TL facilitates afaster convergence of the empirical risk to the risk. A similar behavior was alreadyobserved in [15, 3].
However, one might ask what happens when the selected sources are providing bad
predictions? Since R̂src p≤ 1, due to truncation, the empirical risk converges to the risk
at the standard rate Õ( k/m), the same one we would have without any transferingfrom the sources classifiers.
We now present another result that upper bounds the difference between the risk ofsolution of the algorithm and the empirical risk of the optimal solution to the k-Source
Selection problem.
Theorem 2. In addition to conditions of Theorem 1, let (w? , β ? ) be the optimal solution to (2). Given a sample covariance matrix Ĉ, assume that Ĉi,j6=i ≤ γ < 1+λ6k , and2γ := 16(k+1). Then with high probability,
1+λsrc
1 + kτ∞
+
λm





trg
R hŵ,β̂ − R̂ htrg
≤ (1 + )R̂λsrc + Õw? ,β ?

where R̂λsrc := min|S|≤k

n

1
λ
+ |S|
|S|

src
i∈S R̂(hi )

P

o

r

src
1 + kτ∞R̂λsrcλm!
,.

To analyze the implications of Theorem 2, let us consider few interesting cases.
Similarly as done before, the quantity R̂λsrc captures how well the source hypotheses
are aligned with the target task and governs the asymptotic and finite sample regime.
In fact, assume for any finite m thatp there is at least one sourcep hypothesis with small
empirical risk, in particular, inÕ( k/m),
and
set
λ
=
Õ(
k/m). Then we have that

p
trg
trg
k/m , that is we get the generalization bound as if
R(hŵ,β̂ ) − R̂(hw? ,β? ) = Õ
we are able to solve the original NP-hard problem in (2). In other words, if there areuseful source hypotheses, we expect our algorithm to perform similarly to the one that
identifies the optimal subset. This might seem surprising, but it is important to note that
we do not actually care about identifying the correct subset of source hypotheses. We
only care about how well the returned solution is able to generalize. On the other hand,
if not even one source hypothesis has low risk, selecting the best subset of k sources
becomes meaningless. In this scenario, we expect the selection of any subset to performin the same way. Thus the approximation guarantee does not matter anymore.
We now state the approximation guarantees of GreedyTL used to prove Theorem 2. In the following Corollary we show how far the optimal solution to the regularized subset selection is from the approximate one found by GreedyTL.
onCorollary 1. Let λ ∈ R+ and k ≤ n. Denote OPT := minkwk0 =k R̂(w) + λkwk22 .
Assume that Ĉ and b̂ are normalized, and Ĉi,j6=i ≤ γ < 1+λ
6k . Then, FR algorithm
generates an approximate solution
ŵ
to
the
regularized
subsetselection problem that
16(k+1)2 γ
16(k+1)2 γλ2satisfies R̂(ŵ) + λkŵk2 ≤ 1 + 1+λOPT − (1+λ)2 .

Apart from being instrumental in the proof of Theorem 2, this statement also points
to the secondary role of regularization parameter λ: unlike in FR, we can control thequality of approximate solution even if the features are correlated.

5

Experiments

In this section we present experiments comparing GreedyTL to several transfer learning and feature selection algorithms. As done previously, we considered the object detection task and, for all datasets, we left out one class considering it as the target class,while the remaining classes were treated as sources [24]. We repeated this procedure
for every class and for every dataset at hand, and averaged the performance scores.
In the following, we refer to this procedure as leave-one-class-out. We performed theevaluation for every class, reporting averaged class-balanced recognition scores.
We used subsets of Caltech-256 [12], Imagenet [7] and SUN09 [5]. The largest
setting considered involves 1000 classes, totaling in 1.2M examples, where the numberof training examples of the target domain varies from 11 to 20. Our experiments aimed
at verifying two claims: (I) the importance of regularization when using greedy feature
selection as a transfer learning scheme; (II) in a small-sample regime GreedyTL is
more robust than alternative feature selection approaches, such as L1-regularization.
Datasets and features. We used the whole Caltech-256, a public subset of Imagenet containing 103 classes and all the classes of SUN09 that have more than 1 example, which amounts to 819 classes. For Caltech-256 and Imagenet, we used as features
the publicly-available 1000-dimensional SIFT-BOW descriptors, while for SUN09 we
extracted 3400-dimensional PHOG descriptors.
We composed a negative class by merging 100 held-out classes (surrogate negativeclass). We did so for each dataset, and we further split it into the source negative andthe target negative class as 90% + 10% respectively, for training sources and the target.
The training sets for the target task were composed by {2, 5, 10} positive examples, and10 negative ones. Following [24], the testing set contained 50 positive and 50 negative
examples for Caltech-256 and Imagenet. For the skewed SUN09 dataset we took one
positive and 10 negative training examples, with the rest left for testing. We drew eachtarget training and testing set randomly 10 times, averaging the results over them.
Algorithms. We chose a linear SVM to train the source classifiers [10]. This allows us to compare fairly with relevant baselines (like Lasso) and is in line with recent
trends in large scale visual recognition and transfer learning [8]. The source classifiers
were trained for each class in the dataset, combining all the positive examples of thatclass and the source negatives. On average, each source classifier was trained using
104 examples for the Caltech-256, 105 for Imagenet and 103 for the SUN09 dataset.
The models were selected by 5-fold cross-validation having regularization parameterC ∈ {10−4 , 10−3 , · · · , 104 }. In addition to trained source classifiers, for the Caltech256, we also evaluated transfer from Classemes [4] and Object Bank [17], which arevery similar in spirit to source classifiers. At the same time, for Imagenet, we evaluatedtransfer from DeCAF convolutional neural network [8].
We divided the baselines into two groups - the linear transfer learning baselinesthat do not require access to the source data, and the feature selection baselines. We

included the second group of baselines due to GreedyTL’s resemblance to a feature
selection algorithm. We focus on the linear baselines, since we are essentially interested
in the feature selection in high-dimensional spaces from few examples. In that scope,most feature selection algorithms, such as Lasso, are linear. In particular, amongst TL
baselines we chose: No transfer: Regularized Least Squares (RLS) algorithm trained
solely on the target data; Best source: indicates the performance of the best sourceclassifier selected by its score on the testing set. This is a pseudo-indicator of what an
HTL can achieve; AverageKT: obtained by averaging the predictions of all the sourceclassifiers; RLS src+feat: RLS trained on the concatenation of feature descriptors andsource classifier predictions; MultiKT k · k2 : HTL algorithm by [24] selecting β in (1)by minimizing the leave-one-out error subject to kβk2 ≤ τ ; MultiKT k · k1 : similar
to previous, but applying the constraint kβk1 ≤ τ ; DAM: An HTL algorithm by [9],that can handle selection from multiple source hypotheses. It was shown to performbetter than a well known and similar ASVM [26] algorithm. For the feature selection
baselines we selected well-established algorithms involving sparsity assumption: L1Logistic: Logistic regression with L1 penalty [13]; Elastic-Net: Logistic regression with
mixture of L1 and L2 penalties [13]; Forward-Reg: Forward regression – a classicalgreedy feature selection algorithm.
Results. Figure 1 shows the leave-one-class-out performance w.r.t. all considereddatasets. In addition, Figures 1b, 1c, 1f show the performance when transferring from
off-the-shelf classemes, object-bank feature descriptors, and DeCAF neural network
activations. Whenever any baseline algorithm has hyperparameters to tune, we chosethe ones that minimize the leave-one-out error on the training set. In particular, weselected the regularization parameter λ ∈ {10−4 , 10−3 , . . . , 104 }. MultiKT and DAM
have an additional hyperparameter that we call τ with τ ∈ {10−3 , . . . , 103 }. Kernelizedalgorithms were supplied with a linear kernel. Model selection for GreedyTL involves
two hyperparameters, that is k and λ. Instead of fixing k, we let GreedyTL selectfeatures as long as the regularized error between two consecutive steps is larger than δ.
In particular, we set δ = 10−4 , as in preliminary experiments we have not observed any
gain in performance past that point. The λ is fixed to 1. Even better performance could
be obtained tuning it.
We see that GreedyTL dominates TL and feature selection baselines throughout
the benchmark, rarely appearing on-par, especially in the small-sample regime. In addition, on two datasets out of three, it manages to identify the source classifier subsetthat performs comparably or better than the Best source, that is the single best classifier
selected by its performance on the testing set. The significantly stronger performanceachieved by GreedyTL w.r.t. FR, on all databases and in all settings, confirms theimportance of the regularization in our formulation.
Notably, GreedyTL outperforms RLS src+feat, which is equivalent to GreedyTL
selecting all the sources and features. This observation points to the fact that GreedyTL
successfully manages to discard irrelevant feature dimensions and sources. To investigate this important point further, we artificially add 10, 100 and 1000 dimensions ofpure noise sampled from a standard distribution. Figure 2 compares feature selection
methods to GreedyTL in robustness to noise. Clearly, in the small-sample setting,
GreedyTL is tolerant to large amount of noise, while L1 and L1/L2 regularization

k

k
2

·k

2

o
fe
r

ns

o

N

so
ur
ce
tra
ns
fe
r

Be
st

k
·
ul
tiK k2
T
k
·
Av
er k1
ag
eK
L1
T
-L
og
is
tic
El
as
tic
-N
Fo
et
rw
ar
dR
eg
M

L
sr
c+
fe
at
DA
M

o

N

so
ur
ce
tra
ns
fe
r

Be
st

k
·k
ul
2
tiK
T
k
·k
Av
1
er
ag
eK
L1
T
-L
og
is
tic
El
as
tic
-N
Fo
et
rw
ar
dR
eg
M

ul
tiK
T

LS

M

R

Balanced Accuracy (%)
90

tra

e

90

N

rc

st
so
u

L
sr
c+
fe
a
DA t
M

ul
tiK
T

LS

M

R

(c) Caltech256 (Object Bank)

Be

T
k
·k
Av
1
er
ag
eK
L1
T
-L
og
is
tic
El
as
tic
N
Fo
et
rw
ar
dR
eg

tiK

·k

50

M
ul

60

k

2 positive
5 positive
10 positiveT(e) Imagenet (1000 classes)

tiK

70
ed
yT

(a) Caltech-256

M
ul

100

L

50

fe
a
DA t
M

2 positive
5 positive
10 positive

c+

100

sr

60
re

G

so
ur
ce
tra
ns
fe
r

50

LS

70

ed
yT

80

Balanced Accuracy (%)

o

N

Be
st

60

re

G

ce

fe
r

tra
ns

so
ur

70

R

80

Balanced Accuracy (%)

o

N

Be
st

k
·k
ul
2
tiK
T
k
·k
Av
1
er
ag
eK
L1
T
-L
og
is
tic
El
as
tic
-N
Fo
et
rw
ar
dR
eg
M

ul
tiK
T

L
sr
c+
fe
a
DA t
M

Balanced Accuracy (%)
80

ed
yT

2

·k

k
·k
Av
1
er
ag
eK
T
L1
-L
og
is
tic
Fo
rw
ar
dR
eg

ul
tiK
T

k

LS

M

R

ed
yT

re

G

2 positive
5 positive
10 positive

re

ul
tiK
T

M

L

sr
c+
fe
at
DA
M

Balanced Accuracy (%)
100

G

fe
r

ns

e

90

tra

LS

M

R

ed
yT

re

G

90

o

rc

st
so
u

Balanced Accuracy (%)
90

N

Be

·k
Av
1
er
ag
eK
L1
T
-L
og
is
tic
El
as
tic
-N
Fo
et
rw
ar
dR
eg

T

tiK

T

L

fe
a
DA t
M

c+

sr

tiK

M
ul

M
ul

LS

R

ed
yT

re

G

Fig. 1: Performance on the Caltech-256, subsets of Imagenet (1000 classes) and SUN09(819 classes). Averaged class-balanced accuracies in the leave-one-class-out setting.

100(b) Caltech-256 (Classemes)
2 positive
5 positive
10 positive

80

70

60

50

90

(d) SUN0985
1 positive

80

75

70

65

60

55

50

100

(f) Imagenet (DeCAF, 1000 classes)

2 positive
5 positive
10 positive

80

70

60

50

Fig. 2: Baselines and number of additional noise dimensions sampled from a standard
distribution. Averaged class-balanced recognition accuracies in the leave-one-class-out
setting.
(a) Caltech-256(b) Imagenet

100

100
2 positive
5 positive
10 positive

Balanced Accuracy (%)

80

70

60

70

60

10 3

10 2
L1

-L

og

is

tic

10 1
-L

og

is

tic

10 3

tic
is
og
-L

L1

L1

10 2
as
El

tic

-N

et

10 1
as
El

tic

-N

et
-N
as

El

tic

et

10 3

10 2
G

re

ed
yT

L

10 1

L
ed
yT
re

G

re

ed
yT

L

10 3

10 2
L1

-L

og

is

tic

10 1
L1

-L

og

is

tic
is
og
-L

L1

tic

10 3

10 2
as
El

tic

-N

et

10 1
as
El

tic

-N

et
-N
as

El

tic

et

10 3

10 2

L

G

re

ed
yT

L

L

ed
yT
re
G

ed
yT
re
G

80

50
10 1

50

2 positive
5 positive
10 positive

90

G

Balanced Accuracy (%)

90

suffer a considerable loss in performance. We also draw attention to the failure of L1based feature selection methods and MultiKT with L1 regularization to match the performance of GreedyTL.

6

Conclusions

In this work we studied the transfer learning problem involving hundreds of sources.
The kind of transfer learning scenario we consider assumes no access to the source data
directly, but through the use of the source hypotheses induced from them. In particular,
we focused on the efficient source hypothesis selection and combination, improving theperformance on the target task. We proposed a greedy algorithm, GreedyTL, capable of selecting relevant sources and feature dimensions at the same time. We verified
these claims by obtaining the best results among the competing feature selection and
TL algorithms, on the Imagenet, SUN09 and Caltech-256 datasets. At the same time,comparison against the non-regularized version of the algorithm clearly show the powerof our intuition. We support our empirical findings by showing theoretically that underreasonable assumptions on the sources, the algorithm can learn effectively from few
target examples.

Acknowledgments
I.K. is supported by the Swiss National Science Foundation Sinergia project Ninapro
and Idiap Research Institute.

References
1. Aytar, Y., Zisserman, A.: Tabula rasa: Model transfer for object category detection. In: ICCV(2011)
2. Ben-David, S., Blitzer, J., Crammer, K., Kulesza, A., Pereira, F., Vaughan, J.: A theory oflearning from different domains. Machine Learning (2010)

3. Ben-David, S., Urner, R.: Domain adaptation as learning with auxiliary information. In: New
Directions in Transfer and Multi-Task - Workshop @ NIPS (2013)
4. Bergamo, A., Torresani, L.: Classemes and other classifier-based features for efficient object
categorization. Pattern Analysis and Machine Intelligence, IEEE Transactions on (2014)
5. Choi, M.J., Lim, J.J., Torralba, A., Willsky, A.S.: Exploiting hierarchical context on a large
database of object categories. In: CVPR (2010)
6. Das, A., Kempe, D.: Algorithms for subset selection in linear regression. In: STOC (2008)
7. Deng, J., Dong, W., Socher, R., Li, L.J., Li, K., Fei-Fei, L.: Imagenet: A large-scale hierarchical image database. In: CVPR (2009)
8. Donahue, J., Jia, Y., Vinyals, O., Hoffman, J., Zhang, N., Tzeng, E., Darrell, T.: Decaf: A
deep convolutional activation feature for generic visual recognition. In: ICML (2014)
9. Duan, L., Tsang, I.W., Xu, D., Chua, T.S.: Domain adaptation from multiple sources via
auxiliary classifiers. In: ICML (2009)
10. Fan, R.E., Chang, K.W., Hsieh, C.J., Wang, X.R., Lin, C.J.: Liblinear: A library for large
linear classification. Journal of Machine Learning Research (2008)
11. Gong, B., Shi, Y., Sha, F., Grauman, K.: Geodesic flow kernel for unsupervised domain
adaptation. In: CVPR (2012)
12. Griffin, G., Holub, A., Perona, P.: Caltech-256 object category dataset. Tech. rep., Caltech(2007)
13. Hastie, T., Tibshirani, R., Friedman, J.: The Elements Of Statistical Learning. Springer(2009)
14. Jie, L., Tommasi, T., Caputo, B.: Multiclass transfer learning from unconstrained priors. In:
ICCV (2011)
15. Kuzborskij, I., Orabona, F.: Stability and hypothesis transfer learning. In: ICML (2013)
16. Kuzborskij, I., Orabona, F., Caputo, B.: From N to N+1: Multiclass Transfer Incremental
Learning. In: CVPR (2013)
17. Li, L., Su, H., Xing, E., Fei-Fei, L.: Object bank: A high-level image representation for scene
classification & semantic feature sparsification. In: NIPS (2010)
18. Lim, J.J., Torralba, A., Salakhutdinov, R.: Transfer learning by borrowing examples for multiclass object detection. In: NIPS (2011)
19. Mansour, Y., Mohri, M., Rostamizadeh, A.: Domain Adaptation with Multiple Sources. In:
NIPS (2009)
20. Oquab, M., Bottou, L., Laptev, I., Sivic, J.: Learning and transferring mid-level image representations using convolutional neural networks. In: CVPR (2014)
21. Pan, S.J., Yang, Q.: A survey on transfer learning. Knowledge and Data Engineering, IEEE
Transactions on (2010)
22. Saenko, K., Kulis, B., Fritz, M., Darrell, T.: Adapting visual category models to new domains. In: ECCV (2010)23. Salakhutdinov, R., Torralba, A., Tenenbaum, J.: Learning to share visual appearance for multiclass object detection. In: CVPR (2011)
24. Tommasi, T., Orabona, F., Caputo, B.: Learning categories from few examples with multimodel knowledge transfer. IEEE Transactions on Pattern Analysis and Machine Intelligence(2013)
25. Vezhnevets, A., Ferrari, V.: Associative embeddings for large-scale knowledge transfer with
self-assessment. In: CVPR (2014)
26. Yang, J., Yan, R., Hauptmann, A.: Cross-Domain Video Concept Detection Using Adaptive
SVMs. In: ACMM (2007)
27. Zhang, T.: Adaptive forward-backward greedy algorithm for sparse learning with linear models. In: NIPS (2008)