The shortage of labeled data is a fundamental problem in machine learning applications. While huge amounts of unlabeled data is generated and made available in many domains, the cost of acquiring data labels remains high. Domain adaptation addresses this problem by leveraging labeled data in one or more related domains, often referred as "source" domains, when learning a classifier for unseen data in a "target" domain. The domains are assumed to be related but not identical.
This situation occurs in domains where machine learning components are intensively deployed, such as event detection in videos, entity recognition across different text corpora, object recognition in images acquired in different conditions (see [21] for a survey of domain adaptation methods and [24] for a survey on the related field of transfer learning).
Domain adaptation has also received a significant attention in computer vision applications [17,18,19,20,22,26,27], Different aspects have been addressed and various approaches to the domain adaptation have been proposed [7,25]; this clearly indicates how complex and multi-faceted the problem is.
Current research in domain adaptation focuses on a scenario where (a) the prior domain (source) consists of one or maximum two databases (b) the labels between the source and the target domain are the same, and (c) the number of annotated training data for the target domain are limited. The goal of this challenge is to push the state of the art towards more realistic settings, relaxing these assumptions1 .
Indeed researchers and teams participating in the ImageCLEF DA 2014 challenge were asked to build recognition systems for the target classes by leveraging the knowledge from four source domains. Both source and target data are provided by exploiting existing available resources.
Specifically, the participants were provided with image features2 extracted by the organizers from 600 randomly selected images collected from five different image collections: Caltech-256 [2], ImageNet12 [3], PASCAL-VOC12 [4], Bing [1] and SUN [5]. The organizers selected 12 common classes from each datasets, namely, aeroplane, bike, bird, boat, bottle, bus, car, dog,horse, monitor, motorbike, people. (see Figure 1 for example images for each class and in all collection, showing the variability of classes between the collections). The first four collections from the list are proposed as source domains for which the image features and all the labels were provided. The SUN dataset served as the target domain, with 60 annotated and 600 non-annotated instances. The task was to provide predictions for the non-annotated target data.
We started by analyzing the domain adaptation task and the available features for the different collections. Three key elements of our analysis are the following:
1. Original images are not available neither for target nor for sources domains; the participants dispose feature sets only. It makes impossible to leverage the intermediate knowledge generated during the feature extraction process, such as the choice of low or high level features or the vocabulary for bags of visual words. 2. Source and target domains are semantically related, however they are different feature-wise. Figure 2.left compares the PCA projection of four source and target domains made available at phase 1 of the challenge3 . A similar relationship (see Figure 2.middle) can be found between PCA projections for the source and target domain data at phase 2. Worse, as shown in Figure 2.right, the target feature distribution has been changed between phases 1 and 2. This change is likely due to parameter changes in the feature extraction process hidden from the participants. Consequently, it made impossible any deployment of models learned at phase 1. 3. According to our experiments made with the features released in phase 1, none of existing domain adaptation methods for the visual classification appeared as a perfect match for the challenge task [7,25].
Putting all these elements together, we decided to proceed in two steps. First, we undertook a number of conceptually uncorrelated approaches to domain adaptation. Second, we used ensemble techniques to aggregate individual predictions using different majority voting methods. More precisely, in the first step we tested methods of the following classes:
Brute force : Cross validation on available training data to identify best combinations of source domains for transferring to the target domain, with the optimal set of parameter values and kernel functions. Instance weighting : Boosting-based instance-transfer domain adaptation to identify different instances in one or more source domains allowing to boost the learning in the target domain. Space transformation : Metric learning-based domain adaptation where the idea is to transform the feature space and bring instances from the same class close to each other, independently if they are from source or target domains.
The remainder of this working note is organized as follows. In Section 3 we describe three individual domain adaptation methods. Section 4 describes the ensemble methods over heterogeneous classifiers. Section 5 reports evaluation results including the ten submissions to the challenge. We analyze the results and the impact of different components on the overall performance. Finally we outline future work and conclude in Section 6.
There are two main cases in domain adaptation, they depend on available data in the target domain. In the unsupervised case, no labeled target instances are available. In the semi-supervised case, a few target instances are labeled. In ImageCLEF DA challenge, 60 labeled target instances are available, this positions the challenge into the second case.
We suppose that the labeled target dataset T l is drawn from the same distribution as the unlabeled target set T u and hence it will play an important role in building the classification model. However the size of T l is too small to adequately train a good classifier for the test data T u .
The training data from source domains are more abundant, but the classifiers learned from these data cannot classify the test data well due to different data distributions. Let S 1 , . . . , S N S denote the source domains, where N S ≥ 1 is the number of sources. Let X s k be an instance space of S k (e.g. a subset of S k used for training). We denote by X t the instance space of the target domain (that can take elements from T l , T u or both). Further, we denote by Y = {c 1 , c 2 , . . . , c Nc } the set of category labels common to all domains.
We start off with the brute force approach which uses available annotated data to assess the relatedness between source domains and the target domain and to test a straightforward domain adaptation scenario. For the N S = 4 different source domains we consider N SC = 2 N S − 1 = 15 source combinations SC i , i = 1, . . . , N SC which are generated by an exhaustive enumeration of all possible subsets of source domains, e.g. SC 1 = {S 1 }, SC 6 = {S 1 , S 3 } and SC 15 = {S 1 , S 2 , S 3 , S 4 }. For each source combination SC j , we concatenate the target train set T l with the selected sources SC j and train the SVM models in a cross validation mode to find out the optimal parameter values and kernel functions. Two versions have been implemented, the multi-task SVM and one-against-all binary SVMs, as follows:
Multi-class SVM: We first used the multi-class LIBSVM package 4 for the multi-class classification in the target domain. In the cross validation with k = 10 folds, we tested different values of SVM parameters µ, ν, C, the standard kernels available with the package and different source combinations SC i we found as the best source combination CS 13 = {S 1 , S 2 , S 4 } with the linear ν-SVM and the parameters ν = 0.12 and C = 0.01. This classifier denoted by f mcsvm allows a gain of 3% compared to the baseline multi-class SVM f bf 0 with no source domains and cross validated parameters. Binarised SVM: We additionally consider the multi-class classification by a composition of one-against-all classifiers running again the LIBSVM package and cross validate to determine the optimal parameters for each of N c = 12 classes in the datasets. Unlike the multi-class SVM above where the optimal parameter values, kernel and the source combination are common for all classes, in the binarized version we identify the best classifier for each class c j ∈ Y which comes with a specific set of parameter values, kernels and source combinations for each class c i . Hence, the multi-class classifier f bsvm is composed of N c binary classifiers f cj bsvm , j = 1, . . . , N c . For an unseen sample x i , it proceeds by applying all classifiers and predicting the label ŷbsvm = c j for which the corresponding classifier reports the highest confidence score:
In a probabilistic setting, all class confidence scores are converted into probabilities P (y i = c|f bsvm (x i )).
We extended the Transfer AdaBoost learning algorithm (TrAdaboost) [12], an extension of the AdaBoost [15] for transfer learning by assuming that there is abundant source training data to learn a classifier, but the target domain is different from the source. Hence this approach is can be easily adopted for the domain adaptation.
AdaBoost aims to boost the accuracy of a weak learner by carefully adjusting the weights of training instances and to learn a classifier accordingly. In TrAdaboost, source and target instances have opposite roles. Target training instances are weighted similarly as in AdaBoost, but when source training instances are wrongly predicted by the learned model due to distribution changes, it is assumed that they could be those that are the most dissimilar to the target instances and therefore TrAdaboost tries to decrease the weights of these instances in order to weaken their impact.
Algorithm 1 Transfer Adaptive Boosting with one source domain. 1: Initialize the initial source and target weight vectors, w 1 T = (w 1 t 1 , . . . , w 1 t N t ), w 1 S = (w 1 s 1 , . . . , w 1 s Ns ), 2: Set w = (wT , wS), β = 1/(1 + 2 ln Nt/M ) and T = (Tt, Ts). 3: for r = 1, . . . , M do 4:
Normalize w r = w r /|w r |.
Call Learner on the training set T with the distribution w r to find a hypothesis fr : X → Y which minimizes error for (T, w r ).
Calculate the error of hr on Tt : r = min 1 2 ,
Update the weight vectors:
10: end for 11: Output the aggregated estimate ftra(x) = M r=1 β r fr(x) . In a probabilistic setting, these scores are converted into probabilities P (yi = c|ftra(xi)).
A formal description of the framework is given in Algorithm 1 for the case of using one source domain, N S = 1, but the extension to multiple sources is straightforward. The main idea is that at each iteration round, if a source training instance is mistakenly predicted, the instance may likely conflict with the target training data. Therefore, we decrease its training weight to reduce its effect through multiplying its weight by a strictly positive factor exp(
] is the Iverson brackets denoting the indicator function that equals one if its argument is true and zero otherwise. We further add Γ r term inspired by [6] to address some drawbacks of the initial TrAdaboost [12]. Due to this, in the next round, the mis-classified source training instances, which are dissimilar to the target ones, will affect the learning process less than in the current round. After several iterations, the source training instances that fit the target ones better will have larger training weights, while the source training instances that are dissimilar to the target ones will have much lower weights. These instances with large training weights tend to help the learning algorithm to train better classifiers.
As in the previous section, we consider N SC =15 different compositions of available sources to be used as one. We use Algorithm 1 on different combinations by simply concatenating the sources to form the source training set X s . Note the existence of an extension of TrAdaboost to cope with multiple source domains [29]. This extension probes at each iteration instances from different sources, in order to identify a source which reduces the error the most. In the context of the ImageClef DA challenge, our experience of using TrAdaboost with multiple sources has not been convincing. Concatenating sources was more beneficial that keeping them separately. This phenomenon can be explained by the closeness between the source instances proposed for the challenge (see Figure 2). In the cases where source domains have very different distributions, keeping them separately might be a better strategy.
Another class of domain adaptation methods tries to jointly transform the source and target domains, either by trying to align domains using PCA projections [18,16,14] or by learning a metric which can bridge the two domains. For the challenge we experimented with two type of metric learning approaches. On one hand we extended a metric learning technique that optimizes KNN objectives [13,28] that we will denote by KNN ML. On the other hand, we adopted for domain adaptation the Nearest Class Mean (NCM) and Nearest Class Multiple Centroids (NCMC) classifiers from [23].
Metric learning with KNN objectives. The aim of these approaches is to find a linear transformation W such that, in the new space, distances between examples from the same class are decreased and distances between images from different classes are increased. This is done generally by optimizing the sum of the losses on the training set5 :
where (x q , x p , x n ) are triplets such as the image x p is from the same class as x q while x n is from a different class, d W (x q , x i ) = W x q − W x i 2 2 is the Euclidean distance between image x q and image x i in the transformed space and [a] + denotes max(0, a).
We consider only projections into a lower dimensional space, i.e. the dimension of the projected vector W x is lower than the dimension of x (in our experiments we used target dimensions of 64 and 128). One advantage of this is to have less parameters to estimate, which is especially important when only relatively small amount of training examples are available; also it generally leads to better performances.
As optimizing the sum of losses over all possible triplets is typically unfeasible, we approximate the solution through stochastic gradient descent (SGD) [8] method, where at each step a set of random triplets are selected and W is updated with a fix learning rate and the sub-gradients:
where X qnp = x q (x n − x p ) . If instead of updating only by a single triplet, for each x q we select a set of random positives-negative pair {(x pi , x ni ), i = 1..m}, we have the same updating formula but X qnp = X q X np , where X np is the matrix concatenating the (x ni − x pi ) vectors, and X q is the matrix concatenating m times the x q vector.
Metric Learning for Nearest Class Mean. The nearest class mean NCM classifier assigns a document to the class c * ∈ Y with the closest mean:
where d W (x, µ c ) is the Euclidean distance between an image x and the class mean µ c in the transformed space.
The main idea behind the metric learning for Nearest Class Mean (MLNCM) is to learn a linear projection matrix W such that, in this new space, the instances of the same class are closer to each other, and hence to the correct class mean than to the class centers of the other classes. To optimize such NCM performance objective in the projected space, Mensink et al. [23] proposed to formulate the NCM classifier as a multi-class soft-max regression problem using a probabilistic model where the probability for a class c given a feature vector x i is defined as:
Then, to learn the projection matrix W , the log-likelihood of the correct predictions are optimized over the training set using the stochastic gradient descend (SGD) algorithms [8]. At each step, W is updated with a fixed learning rate in the direction given by the gradient:
where N is the number of training examples. At each iteration we are using only a random subset of the training data to update W . In [23], Mensink et al. proposed an extension to this method, the Nearest Class Multiple Centroids (NCMC) classifier that allows more flexible class representations by considering multiple cluster means (centroids) for each class. In their case, NCMC represents each class by a set of centroids instead of a single class mean. In our multiple domain case, instead of cluster means, we consider domain specific class means µ d c (averaging over instances from the same class c and same domain d) and we assign a test instance to a given class based on a weighted soft-max distance to these domain specific class means:
where N d is the number of domains and
) is the normalizer. Adding domain specific weights w d in Eq. 6 allows giving different importance to each domain (in our experiments we used w t = 2 for the target domain T l and w s k = 1 for the source domains).
To learn the projection matrix W , we maximize the log-likelihood of correct classification in Eq. 6, for which the gradient w.r.t. W is given by:
where
. Again, we use Stochastic Gradient Descent [8] with fixed learning rate where at each iteration we sample a random subset from the training set (2 * N C was used in the experiments). We denote this learning method by NCMC ML.
Learning strategies. Let us now suppose that we have the labeled target dataset T l , the unlabeled target data set T u , and the source training set (that can contain one or several source domains S 1 , . . . , S Ns ). We experimented with the above mentioned metric learning approaches using 3 different strategies and different source configurations SC i .
1. In the first case we simply merged the source combination SC i with the target training data T l and directly optimized the loss in Eq. 2, Eq. 5 or Eq. 7 using all training examples. The rationale behind this is the following. By decreasing interclass distances independently from the domains, allows to exploit more efficiently labeled images from source domains in the projected space to classify target examples and hence it yield to increased performance of distance based classifiers. The methods from this first strategy are denoted by KNN ML, MLNCM ML respectively MLNCMC ML. 2. As we have much less labeled target examples than source ones, their presence is much rearer in the above mentioned random sampling processes. Hence in the iterative approaches they will have less influence in the learning process than the much larger amount of source images. Therefore as a second strategy, we propose to refine W obtained with the first strategy such that we impose at each iteration to have in the sample examples from T l . In the case of KNN, this is done by considering at each step x t q ∈ T l and sampling randomly a set of randomly sampled positive/negative image pairs from the source and then updating W using the triplet sets (x t q , x rj , x nj ), j = 1..N c . In the case of NCM and NCMC we simply ensure that at least one target image from T l is present in the selected batch. The methods corresponding to this second strategy are denoted KNN MLt, NCM MLt and NCMC MLt respectively. 3. Finally, inspired by the adaptive learning proposed in [27], we consider an iterative learning strategy where we further adjust the learned metric with the second strategy. To do this, at each step and for each class we add target instances from the unlabeled set T u and remove source instances as follows. For each class c we add the target instance x t i for which P (y i = c * i |x t i ) − P (y i = c ‡ i |x t i ) according to Eq. 4 is the largest difference, where c * i = c is the predicted label of x t i and c ‡ i is the second predicted label of x t i . Also, for each class c we remove the source image x s j from SC i for which c * j = c and P (y j = c * j |x s j ) − P (y j = c ‡ j |x s j ) is the lowest difference. Then we refine W using the updated training set. We do several rounds until the stopping criteria is reached6 . The methods corresponding to the third strategies are denoted by KNN MLDA, NCM MLDA and NCMC MLDA respectively.
Classification strategies. In the projected space we have different options to predict the class labels of the target images. As we learned a metric, we can use any distance based classifiers such as KNN, NCM or NCMC based classifications as they do not require further parameter tuning. The only parameter k of the KNN can be fixed (e.g. we used 3 in all experiments) or cross validated. NCM has no parameter and the parameters of the NCMD are the weights w d that can be fixed or tuned. In our experiments we used fixed weights. Note that we experimented also with training Multi-Class SVM in the projected space, but the performance was similar to or below the results obtained in the original space. As our experiments on the dataset provided in phase 1 7 have shown that NCMC in general performs better than KNN and NCM (up to 3-5%) we only retained the NCMC classifier to compute the class probabilities (using Eq. 6) independently which metric learning method or strategy was used to compute W . Furthermore, from our experiments in phase 1 it was not clear which source combinations are better when we evaluated the NCMC performance in the projected space. Furthermore, the combinations that yielded best accuracies in the original space (using SVM classifiers) were not always the ones that proved to be the best after projection. Therefore, for each of the above described methods, we learned a metric using each source combination SC i individually and computed class predictions P (y i = c * |f SCi ml (x t i )) for the test set T u in the corresponding projected space. Then we computed the late fusion of class predictions over all source combination to get final predictions given a metric learning method. These classifiers denoted by f ml , were used in two modes. Two runs have been used in submission to predict directly the labels, namely, MLNCM MLDA 128 it200 e0.1 p025 and MLNCMC ML 128 it200 e0.1 p025. Also they were used by ensemble methods in combination with other models to generate the combin * runs.
The combination of the decisions of several classifiers has been proposed as a means of improving the accuracy achieved by any of them. The reasons for combining the outputs of multiple classifiers are compelling, because different classifiers may implicitly represent different useful aspects of a problem, or of the input data, while none of them represents all useful aspects. In the context of instance classification, the idea of combining the decisions of several classifiers has been well explored.
In contrast to approaches which combine models derived from multiple versions of the same learning method, the specific focus of this paper is on ensemble methods that are able to combine the decisions of multiple classifiers of different types, so-called heterogeneous sets of classifiers.
Previous sections described three domain adaptation methods which generate one or more classifiers for target instances, namely, obtained by the brute force (f mcsvm and f bsvm ), transfer adaptive boosting (f tra ) and metric learning (f ml ). They form a pool F of several classifiers from each group F = {f 1 , . . . , f N f } where any classifier's output is class scores or class probabilities. We will denote by g(f k , x t i ) the predicted label of f k for x t i and by p(y i = c|f k (x t i )) the class probability scores. When the classifier does not provide such score we can define p(y i = c|f k (x t i )) = 1 when c = g(f k , x t i ) and zero otherwise.
The first method we tested was the (unweighted) majority voting that combines decisions of individual classifiers, so the global ensemble prediction for target instance x t is:
In the probabilistic setting, we sum up class probabilities and report the class with the highest probability:
The majority voting method is based solely on the output label or probabilities computed by each classifier. In the case of weighting majority voting, classifiers' opinions may be taken differently, depending on how accurate they have been in the past. Below we establish weights proportional to each classifier's accuracy, so each classifier's output is considered according to its past performance.
In the probabilistic setting, the fact that instance x t i belongs to class c given that classifier f k output label c for x, i.e. g(f k , x t i ) = c , has an uncertainty which can be expressed as the conditional probability p(y i = c|g(f k , x t i ) = c ). We may use the confusion matrices to approximate the conditional probabilities for all classes c ∈ Y given a classifier f k ∈ F .
Making assumption of the classifier independence, we use the Bayesian rule to estimate the posterior probability of the class c for the target instance x i from the output of classifiers f k ∈ F :
Finally, the class c * = argmax c∈Y P (y i = c|x t i ) (with the highest probability) is assigned as the weighted majority vote to instance x i .
Both individual and ensemble methods have been tuned by XRCE team during the phase 1 to select best strategies of the challenge and applied to the submission data (phase 2). Among multiple evaluation runs, ten most promising results have been selected for the submission, they all are reported in Table 1. For each submission, the table reports the accuracy, score, divergence and a comment on the method used.
The divergence has been proposed to measure the deviation of the submitted prediction vector from a vector with equi-weighted classes:
where N is the number of test images, N c the number of classes, {i|g(f, x t i ) = c} is the set of target instances for which the classifier f predicts class c, Card(A) is the cardinality of the set A and |a| is the absolute value of a. Under the assumption on the equal class distribution in the submission dataset, it may make sense to choose a run whose prediction tends to minimize the divergence. Analyzing the ten submissions made (as well as the non-submitted runs), allowed us to make the following conclusions on the selected strategy and performance of different components of the image classification system we have built for the challenge:
1. Among individual domain adaptation methods, the brute force performed poorly as expected. It did not merit any individual submission, but participated in various ensembles of classifiers. 2. TrAdaboost (TrA) with SVM as a week learner and the Metric Learning (ML) performed reasonably well, each merited two individual submissions. 3. Ensembles of heterogeneous classifiers has turned to be a right strategy to boost the overall performance. 4. Unweighted majority vote (UMV) on a small selection of classifiers performed the best; these selections include 3 to 6 top performing classifiers from each group of classifiers.
5. Weighted majority vote (WMV) works well on large sets of classifiers but underperformed against the manual classifier selection8 with unweighted majority vote. 6. Divergence minimization did not play any important role; making hypotheses on the class distribution and incorporating this prior knowledge in the classification system should be done in a more systematic way.
The strategy of using heterogeneous methods for domain adaptation turned to be a right one. It has allowed our team to build a image classification system in the target domain with an important knowledge transfer from available source domains. Ensembles of heterogeneous classifiers aggregated with different majority voting scenarios has allowed to get high accuracy in the submission runs and to eventually win the ImageCLEF Domain Adaptation competition. The thoughtful analysis of obtained results has also allowed to identify new directions in domain adaptation for image classification.