Emilie Morvant
email: emilie.morvant@lif.univ-mrs.fr

Amaury Habrard
email: amaury.habrard@univ-st-etienne.fr

Stéphane Ayache
email: stephane.ayache@lif.univ-mrs.fr

Parsimonious Unsupervised and Semi-Supervised Domain Adaptation with Good Similarity Functions

Keywords: Machine Learning, Transfer Learning, Domain Adaptation, Good Similarity Functions. Learning Sample From P Model Learning Supervised Classification

In this paper, we address the problem of domain adaptation for binary classification. This problem arises when the distributions generating the source learning data and target test data are somewhat different. From a theoretical standpoint, a classifier has better generalization guarantees when the two domain marginal distributions of the input space are close. Classical approaches try mainly to build new projection spaces or to reweight the source data with the objective of moving closer the two distributions. We study an original direction based on a recent framework introduced by Balcan et al. enabling one to learn linear classifiers in an explicit projection space based on a similarity function, not necessarily symmetric nor positive semi-definite. We propose a well founded general method for learning a low-error classifier on target data which is effective with the help of an iterative procedure compatible with Balcan et al.'s framework. A reweighting scheme of the similarity function is then introduced in order to move closer the distributions in a new projection space. The hyperparameters and the reweighting quality are controlled by a reverse validation procedure. Our approach is based on a linear programming formulation and shows good adaptation performances with very sparse models. We first consider the challenging unsupervised case where no target label is accessible, which can be helpful when no manual annotation is possible. We also propose a generalisation to the semi-supervised case allowing us to consider some few target labels when available. Finally, we evaluate our method on a synthetic problem and on a real image annotation task.

Introduction

In applications requiring automatic classification of new data, a usual method is to learn a classifier by using some machine learning technique. In general, most of the approaches for learning classifiers are built under the assumption that the learning data are representative of the test data. In other words, all train and test data are supposed to be drawn from the same (usually unknown) distribution. While this assumption can be relevant for some tasks, it is not always true in every applications. For example, in spam filtering problems, the training data associated to one user can be very different from emails received by another target user [START_REF] Junejo | Robust personalizable spam filtering via local and global discrimination modeling[END_REF]. A similar issue can also happen in some image annotation tasks where training data can be restricted to particular instances (due to the tricky and costly manual labeling of examples) like images crawled from particular web sites. Such training data are not representative of future test data that can come from images extracted from movies or videos. To overcome this drawback, some transfer learning methods [START_REF] Bahadori | Learning with minimum supervision: A general framework for transductive transfer learning[END_REF][START_REF] Guerra | From bias to opinion: a transfer-learning approach to real-time sentiment analysis[END_REF][START_REF] Junejo | Robust personalizable spam filtering via local and global discrimination modeling[END_REF][START_REF] Pan | A survey on transfer learning[END_REF][START_REF] Wang | Query-dependent cross-domain ranking in heterogeneous network[END_REF] have been proposed to adapt a model from a source domain to a target domain. In this paper, we address a particular transfer learning task named domain adaptation (DA) where test data are supposed to be drawn according to a distribution -the target domain -different from the one used for generating learning data -the source domain - [START_REF] Jiang | A literature survey on domain adaptation of statistical classifiers[END_REF][START_REF] Quionero-Candela | Dataset Shift in Machine Learning[END_REF]. DA is thus an important issue for the efficient application of machine learning methods leading to the development of many approaches in the literature.

Under the assumption that the two domains are somehow related, theoretical DA results state that if the source and the target marginal distributions over the input space are relatively close, then a classifier only learned from the labeled source data can perform well on the target domain [START_REF] Ben-David | Analysis of representations for domain adaptation[END_REF]Ben-David et al., 2010a;[START_REF] Mansour | Domain adaptation: Learning bounds and algorithms[END_REF]. This suggests a natural approach for a successful DA: Moving closer the source and the target distributions while keeping a low-error classifier on the source domain. In this context, [START_REF] Ben-David | Analysis of representations for domain adaptation[END_REF]2010a) have theoretically analyzed the importance of data representation for DA tasks by deriving a generalization bound of the target error for binary classifiers. [START_REF] Mansour | Domain adaptation: Learning bounds and algorithms[END_REF] have extended this approach to real valued classifiers with more general results and other generalization bounds.

In a DA scenario, two settings are generally considered (see Figure 1): One where labeled data are only available in the source learning sample. This setting is often called unsupervised domain adaptation as it works in an unsupervised way over the target domain. In the second, a few labeled data are also available in the target sample that corresponds to the semi-supervised domain adaptation setting. In this context, it is generally assumed that the number of target labeled data is significantly smaller than that of source labeled instances and not sufficiently large enough to learn a performing model only from the target labeled examples.

The unsupervised case is clearly more challenging. Some methods, based on different hypotheses or discrepancy measures, have been explored for reweighting the learning source data in order to move them closer to target data [START_REF] Huang | Correcting sample selection bias by unlabeled data[END_REF][START_REF] Jiang | Instance weighting for domain adaptation in nlp[END_REF][START_REF] Mansour | Domain adaptation: Learning bounds and algorithms[END_REF][START_REF] Sugiyama | Direct importance estimation with model selection and its application to covariate shift adaptation[END_REF]. In another context, [START_REF] Bruzzone | Domain adaptation problems: A DASVM classification technique and a circular validation strategy[END_REF] have designed a SVM-based procedure that iteratively replaces source labeled instances by self-labeled target points in the learning sample. Another idea consists in finding a common relevant feature space where the two distributions are close [START_REF] Bahadori | Learning with minimum supervision: A general framework for transductive transfer learning[END_REF][START_REF] Ben-David | Analysis of representations for domain adaptation[END_REF]Ben-David et al., 2010a;[START_REF] Blitzer | Domain adaptation with coupled subspaces[END_REF][START_REF] Xue | Topic-bridged plsa for cross-domain text classification[END_REF], but this often relies on ad hoc heuristics specific to particular tasks. We can also cite some approaches based on cotraining [START_REF] Chen | Co-training for domain adaptation[END_REF] or regression [START_REF] Cortes | Domain adaptation in regression[END_REF] that can enter in this unsupervised setting. In general, all these previous methods have some natural extensions to the semi-supervised case in order to exploit target labeled information for improving the classifier induction. In this latter setting, some specific approaches have been proposed for statistical classifiers by using an extended linear projection space [START_REF] Daumé | Frustratingly easy domain adaptation[END_REF][START_REF] Daumé | Co-regularization based semi-supervised domain adaptation[END_REF]. Some other techniques, using a com-Fig. 1. The intuition behind the difference between a classical machine learning setting and a classical domain adaptation setting. P S is the distribution generating the source data, P T is the distribution generating the target data. Note that to simplify the presentation, we use an abuse of notation for distributions generating the samples: unlabeled data of the test and target samples are not exactly drawn from the same distribution used to generate the labeled learning data, see Section 2 for a more formal description. bination of source and target labeled instances, have also been studied according to various frameworks (Ben-David et al., 2010a;[START_REF] Bergamo | Exploiting weakly-labeled web images to improve object classification: a domain adaptation approach[END_REF][START_REF] Daumé | Co-regularization based semi-supervised domain adaptation[END_REF][START_REF] Schweikert | An empirical analysis of domain adaptation algorithms for genomic sequence analysis[END_REF].

Many of the previously cited methods are often based on either heuristics, a source reweighting scheme only, the presence target labels or kernel methods requiring the use of symmetric and positive semi-definite (PSD) similarity functions.

In this article, we propose a new domain adaptation approach based on the novel theory introduced in (Balcan et al., 2008a;Balcan et al., 2008b) for binary classification. This framework allows one to learn in an explicit projection space defined by a good similarity function that may be not symmetric nor PSD. In other words, it generalizes kernel functions of SVM-based methods and is thus more flexible in some sense. The authors show that it is possible to learn a low-error linear classifier in that space, defined by similarities to some relevant landmark examples. We claim that these landmarks offer a natural set of features to transfer. Our idea consists in automatically modifying this projection space for moving closer source and target points. For this purpose, we propose a general method based on the optimization of a regularized convex objective function where the regularization term plays a crucial role. Indeed, this term focuses on landmark points close to both source and target examples. Our optimization problem is in fact formulated in a 1-norm regularized linear program leading naturally to very sparse models. We also propose an iterative process, based on a reweighting of similarities, to improve the tractability of the method. The key point of our approach relies on the use of general similarities (i.e. neither symmetric nor PSD) to find a relevant projection space for domain adaptation allowing us to move closer source and target distributions. This explains, why we propose to stand in the framework of Balcan et al's to design our DA method.

Our contribution is twofold. First, we define a method for the challenging unsupervised case where no target label is available. It provides then a solution to compensate the lack of target labeled data when manual labeling is impossible. It can also be useful, for example, to design a "cold start" strategy in an active learning process to label the very first examples [START_REF] Ayache | Video corpus annotation using active learning[END_REF]. In this unsupervised setting, a crucial point is to find a reliable method for assessing the various hyperparameters of our approach. To solve this problem, we propose to make use of approaches based on the notion of reverse validation [START_REF] Bruzzone | Domain adaptation problems: A DASVM classification technique and a circular validation strategy[END_REF][START_REF] Zhong | Cross validation framework to choose[END_REF]. We exploit this notion to propose a stopping criterion for our iterative procedure. We also present a theoretical analysis of our models in terms of sparsity and generalization guarantees. We derive a new error bound based on the notion of algorithmic robustness [START_REF] Xu | Robustness and generalization[END_REF]. Our second contribution takes the form of a generalization of our first approach to the semi-supervised case in order to take into account some existing target labels. It is inspired by Ben-David et al. (2010a) and based on the optimization of a linear combination of the source and target empirical errors. We also provide some theoretical justifications specific to this semi-supervised case. Our two methods are evaluated on a synthetic problem and on real image annotation corpora.

The paper is organized as follows. Section 2 introduces the domain adaptation framework of (Ben-David et al., 2010a). Section 3 deals with the theory of learning with good similarity functions (Balcan et al., 2008a). Our unsupervised approach is presented in Section 4 and its iterative enhancement in Section 5. Our semi-supervised method using a few target labels is formulated in Section 6. The different approaches are experimentally evaluated in Section 7. Finally, we conclude and discuss some future work in Section 8.

Domain Adaptation

Let X ⊆ R d be the input space of dimension d and Y = {-1, +1} the label set. A domain is defined as a probability distribution over X ×Y . In a DA framework (Ben-David et al., 2010a;[START_REF] Mansour | Domain adaptation: Learning bounds and algorithms[END_REF], we have a source domain represented by a distribution P S over X × Y and a target domain represented by a somewhat different distribution P T , D S and D T being the respective marginal distributions over X.

In the unsupervised case, a learning algorithm is provided with a Labeled Source sample LS = {(x i , y i )} d l i=1 drawn i.i.d. from P S and an unlabeled Target Sample T S = {x i } dt i =1 drawn i.i.d. from D T . We also denote by

LS |X = {(x i )/(x i , y i ) ∈ LS} d l i=1
the sample constituted of all the instances of LS without their label. Let h : X → Y be an hypothesis function in the form of a binary classifier. The expected errors of h over the source domain P S and the target domain P T are the probabilities that h commits an error on P S and P T respectively,

err S (h) = E (x,y)∼P S L 01 h, (x, y) , err T (h) = E (x,y)∼P T L 01 h, (x, y) ,
where L 01 (h, (x, y)) = 1 if h(x) = y and zero otherwise, corresponding to the 0-1 loss function. We denote by ê rr S (h) and ê rr T (h) the respective empirical errors. A hypothesis class H is a set of hypotheses from X to Y . For a DA task, the objective is then to learn a classifier h ∈ H with a low generalization error err T (h) over the target domain (see Figure 1(b)).

We now review the theoretical framework1 of DA based on (Ben-David et al., 2010a), where the authors give an upper bound for err T (h).

Theorem 1 (Ben-David et al. (2010a)). Let H be a hypothesis class, ∀h ∈ H, This bound depends on three terms:

err T (h) ≤ err S (h) + 1 2 d H∆H (D S , D T ) + ν, where d H∆H (D S , D T ) = 2 sup h,h ∈H∆H |P r D S (h(x) = h (x)) -P r D T (h(x) = h (x))| is + +++ + + + + + + + + - - --- - - - --- (
(A) The source domain expected error err S (h) which can be minimized by a learning algorithm based on the ERM principle. (B) The H∆H-distance between the two marginal distributions which is related to H by measuring a maximum variation divergence over the set of points on which an hypothesis can commit errors. (C) The last term ν is related to the ideal joint hypothesis h * over the domains and can be seen as a quality measure of H for the considered DA task. If h * performs poorly, then it seems to be hard to find a low-error hypothesis on the target domain.

Theorem 1 suggests that if the H∆H-distance is low, i.e. if the two marginal distributions are close, then a low-error classifier over the source domain might be a good model over the target one. The intuition behind this idea is given on Figure 2. An interesting point, described by the following Lemma, is that when the VC-dimension of H is finite (measuring the capacity of H), d H∆H (D S , D T ) can be estimated from finite samples.

Lemma 1 (Ben-David et al. (2010a)). Let H be an hypothesis class with finite VCdimension v. Let S and T be unlabeled samples of size m i.i.d. from D S and D T respectively. Let dH∆H (S, T ) be the empirical H∆H-distance. Then for any δ > 0 with probability at least 1 -δ,

d H∆H (D S , D T ) ≤ dH∆H (S, T ) + 4 2v log(2m) + log 2 δ m .
Lemma 1 means that the empirical distance dH∆H (S, T ) converges thus to the real one d H∆H (D S , D T ) with the size m of the samples. Consider a labeled sample made of S ∪ T where each instance of S is labeled as positive and each one of T as negative, we can directly estimate dH∆H (S, T ) (∈ [0, 2]) by looking for the best classifier able to separate S from T ,

dH∆H (S, T ) = 2 1 -min h∈H∆H ê rr S∪T (h) , (1)
with ê rr

S∪T (h) = 1 m    x∈S∪T : h(x)=-1 1 x∈S + x∈S∪T : h(x)=1 1 x∈T    , where 1 x∈A = 1 if x ∈ A, 0 otherwise.
Finding the optimal hyperplane is an NP-hard problem in general. However, an estimation of dH∆H (S, T ), and thus of d H∆H (D S , D T ), allows us to have an insight of the distribution distance and thus of the difficulty of the DA task for the class H. Note that [START_REF] Mansour | Domain adaptation: Learning bounds and algorithms[END_REF] have extended the H∆H-distance to real valued functions and have provided Rademacher generalization bounds.

Following Theorem 1, one solution for a DA algorithm is to look for a data projection space where both the H∆H-distance (B) and the source domain expected error of a classifier (A) are low (see Figure 2). According to (Ben-David et al., 2010b), minimizing these two terms is necessary to ensure a good adaptation in general.

As a consequence, we need to define a projection space to work on in order to move closer the two distributions. Rather than working in the original input space, we propose to consider a projection space defined by similarity scores to particular points where a good predictor exists. This brings us to the framework of Balcan et al. making use of a notion of good similarity function and introduced in the next section.

Learning with Good Similarity Functions

In this section, we present the framework of similarity-based binary linear classifiers introduced by (Balcan et al., 2008a;Balcan et al., 2008b). Recall that a similarity function over X is any pairwise function K : X × X → [-1, 1]. Many algorithms use similarity functions, like support vector machines where the similarity needs to be a kernel (i.e. symmetric and positive semi-definite (PSD)) to ensure learning and convergence in an implicit high dimensional Hilbert space. However, due to the PSD requirement, considering kernels can be a strong limitation and defining a relevant kernel is a tricky task in general (see [START_REF] Abbasnejad | A survey of the state of the art in learning the kernels[END_REF] for a survey on kernel learning).

The recent learning framework proposed by Balcan et al. (2008a) considers a rather intuitive definition of a good similarity function that overcomes some of these limitations.

Definition 1 (Balcan et al. (2008a)). A similarity function K is an ( ,γ,τ )-good similarity function for a learning problem P if there exists a (random) indicator function R(x) defining a (probabilistic) set of reasonable points such that the following conditions hold:

(i) A 1 -probability mass of examples (x, y) satisfy E (x ,y )∼P yy K(x, x )|R(x ) = 1 ≥ γ, (ii) P r x [R(x ) = 1] ≥ τ .
This definition means that a large proportion of examples must be on average γ more similar to the reasonable points of the same class than to the reasonable points of the opposite class (condition (i)). Moreover, at least a proportion τ of the examples should be reasonable (condition (ii)). Definition 1 includes all valid kernels as well as some non-PSD similarity functions and is thus quite general (Balcan et al., 2008a;Balcan et al., 2008b). The reasonable points are usually unknown a priori. Therefore, in the x E K(., )

x B K(., )

x A E F G H D C A B (b)
The projection of the data in the φ R -space and the linear separator in gray. following, we denote by R = {x j } du j=1 a set of potential reasonable points called landmarks. Given K an ( ,γ,τ )-good similarity function, the conditions of Balcan et al. (2008a) are sufficient to learn a good linear classifier in a φ R -space defined by the mapping function φ R , which projects a point in the explicit space of the similarities to the landmarks such that,

φ R : X → R du x → K(x, x 1 ), . . . , K(x, x du ) . (2)
The following theorem justifies the existence of a good linear classifier in the φ R -space.

Theorem 2 (Balcan et al. (2008a)). Let K be an ( ,γ,τ )-good similarity function for a learning problem P . Let R = {x 1 , . . . , x du } be a (potentially unlabeled) sample of landmarks drawn i.i.d. from P such that d u = 2 τ log(2/δ) + 8 log(2/δ) γ 2

. Consider the mapping φ R defined in Equation (2). Then, with probability at least 1 -δ over the random sample R, the induced distribution φ R (P ) in R du has a separator of error at most + δ to L 1 -margin at least γ/2.

Thus, given an ( ,γ,τ )-good similarity function for a learning problem and -enoughlandmarks, there exists with high probability a low-error linear separator in the explicit φ R -space.

We now provide a little toy example in order to illustrate the notion of ( ,γ,τ )-good similarity function introduced by Definition 1. We consider a problem with only height labeled examples in [0, 1]×[0, 1] represented on Figure 3 x F = (.10, .05), -1 , x G = (.15, .05), -1 and x H = (.10, .00), -1 . We can note here that because of x E , there exists no linear classifier that can achieve a null classification error in this original instance space. We now consider a similarity function K(x, x ) = 1-2 x-x 2 with x-x 2 the classical Euclidean distance. We take the opposite of the distance to obtain a similarity and the renormalization ensures that K(x, x ) ∈ [-1, 1]. We suppose that three out of the height examples are reasonable points: x A , x B and x E ; τ can thus be estimated as 3 8 . We can then evaluate the goodness of K according to these reasonable points from the formula given in Definition 1. The corresponding values are shown in Table 1. If Table 1. Example of the goodness of a similarity function. The table provides for each example the similarity scores to every reasonable points and its associated goodness. we take a margin γ = 0.002, we can remark that the goodness of each example is larger than γ which makes the similarity (0, 0.002, 3/8)-good. Now, with γ = 0.02, the similarity is (0.25, 0.02, 3/8)-good since two examples out of the height do not achieve a goodness larger than 0.02. Finally, in the explicit projection space defined by the similarities to the three rea-

K(•, x A ) K(•, x B ) K(•, x E ) Goodness (x, y) = E[yy K(x, x )|R(x ) = 1] x A 1 0.
sonable points φ R (•) =< K(•, x A ), K(•, x B ), K(•, x E )
> there exists a linear classifier sign g(•) that has a null error, where g is of the form g(

•) = α A K(•, x A ) + α B K(•, x B ) + α C K(•, x E ) (see Figure 3(b), a possible admissible solution is obtained with α A = α B = 1 and α E = -1).
The criterion given by Definition 1 requires to minimize the number of margin violations which is a NP-hard problem generally difficult to approximate. To overcome this problem, the authors have then proposed to consider an adaptation of Definition 1 with the hinge loss formalized as follows.

Definition 2 (Balcan et al. (2008a)). A similarity function K is an ( ,γ,τ )-good similarity function in hinge loss for a learning problem P if there exists a (random) indicator function R(x) defining a (probabilistic) set of reasonable points such that the following conditions hold:

(i) E (x,y)∼P [1-yg(x)/γ] + ≤ , where g(x) = E (x ,y )∼P [y K(x, x )|R(x )] and [1 -z] + = max(0, 1 -z) is the hinge loss, (ii) P r x [R(x )] ≥ τ .
Using the same φ R -space than Theorem 2, the authors have proved a similar theorem for this definition with the hinge loss.

Theorem 3 (Balcan et al. (2008a)). Let K be an ( ,γ,τ )-good similarity function in hinge-loss for a learning problem P . For any 1 > 0 and 0

< δ < γ 1 4 , let R = {x 1 , . . . , x du } be a sample of d u = 2 τ log(2/δ) + 16 log(2/δ) (γ 1 ) 2
landmarks drawn i.i.d.

from P . Consider the mapping φ R defined in Equation (2). Then, with probability at least 1 -δ over the random sample R, the induced distribution φ R (P ) in R du has a separator achieving hinge loss of error at most of + 1 at margin γ.

Finally, given LS a set of d l labeled points, and d u landmark examples, one can effi-ciently find a separator α ∈ R du by solving a linear program where the objective is to minimize the number of margin violations with the hinge loss. We give here an equivalent formulation of the L1-constrained problem presented by Balcan et al. (2008a), called SF opt , which is based on the hinge loss.

           min α 1 d l d l i=1 L g, (x i , y i ) + λ α 1 , with L g, (x i , y i ) = 1-y i g(x i ) + and g(x i ) = du j=1 α j K(x i , x j ), (SF opt )
where g(.) is the learned model. The L1-regularization over α produces an automatic selection of the reasonable points from the landmarks because of the sparsity property of the L1-norm. This leads to a natural two steps algorithm for learning the classifier:

(1) Select a random set of potential landmarks and then (2) learn a binary classifier h(x) = sign[g(x)], in the space induced by the selected landmarks, i.e. those with α j = 0. In practise, the landmarks are chosen from the learning sample. Note that once a φ R -space (of dimension d ) has been defined after this learning step, then the class H φ R of linear classifiers learnable in this space has a finite VC-dimension (d + 1). Thus, according to Lemma 1, we can assess the distribution divergence in the φ R -space by the empirical estimate dH φ R ∆H φ R (D S , D T ).

In the following, a linear classifier learned in this framework by solving (SF opt ) is called a SF-classifier. For sake of simplicity, we will denote H φ R by H.

Finally, by considering the minimization of the DA bound of Theorem 1, we remark that (SF opt ) can be seen both as an empirical minimization of the error on the source domain P S = P and as a method for building a relevant φ R -space. Our idea for DA is then to constrain the φ R -space to minimize the H∆H-distance.

Unsupervised Domain Adaptation with Similarity Functions

We now present our unsupervised DA method which consists in learning a classifier from ( ,γ,τ )-good similarity functions. Recall that following Theorem 1, the expected target domain error is bounded by three terms: (A) the source domain error, (B) the divergence between the marginal distributions and (C) the smallest joint error over the domains. Our idea is to minimize the expected target error by decreasing this bound.

According to (Balcan et al., 2008a;Balcan et al., 2008b), solving Problem (SF opt ), only on the source domain, involves to learn a relevant linear classifier in the explicit φ R -space (Equation (2)) of similarities to a landmark set. Then, it implies a natural decreasing of (A). For minimizing (B), we want to induce a new projection space allowing one to move closer the two domain marginal distributions by selecting landmarks that are both similar to the source and target examples. To achieve this goal, we propose to learn a classifier thanks to an additional regularization term on the weights α. Due to the lack of information on the target domain, the last term (C) is hard to decrease. However, we propose to use a reverse validation approach to try to control it.

Optimization Problem

By solving Problem (SF opt ) for learning SF-classifiers, we not only minimize the expected source error but we also define a relevant projection space for the source domain. Indeed, irrelevant landmarks, i.e. those associated with a null weight in the solution α, will not be considered. According to the notion of H∆H-distance (Equation ( 1)), we propose a new additional regularizer that forces the model to provide similar outputs for pairs of source and target points. This will tend to decrease the H∆H-distance between the marginal distributions. To define our regularizer, we have investigated the framework of algorithmic robustness proposed by [START_REF] Xu | Robustness and generalization[END_REF] (see Definition 3 in Section 4.2). Their underlying idea is based on the fact that "if a testing sample is similar to a training sample then the testing error is close to the training error". To ensure generalization guarantees, this framework requires that for a test point close to a training point of the same label, the deviation between the losses of each point has to be low. Note that this result assumes the test and training data to be generated from the same distribution, that is thus not valid in a DA scenario. Despite this drawback, we propose to follow this principle by defining an heuristic to move closer source and target samples. By considering the hinge loss of the Problem (SF opt ), for any learned model g and any pair (x s , x t ) of source and target examples of class y we have,

L g, (x s , y) -L g, (x t , y) = 1 -y du j=1 α j K(x s , x j ) + -1 -y du j=1 α j K(x t , x j ) + . The hinge loss is 1-lipschitz (|[X] + -[Y ] + | ≤ |X -Y |) then, L g, (x s , y) -L g, (x t , y) ≤ du j=1 α j K(x s , x j ) -K(x s , x j ) ≤ du j=1 α j K(x s , x j ) -K(x t , x j ) ≤ ( t φ R (x s ) -t φ R (x t )) diag(α) 1 , (3)
where t φ R (•) is the transposed vector of φ R (•) and diag(α) is the diagonal matrix with α as main diagonal.

Minimizing the term of line (3) amounts to reducing the deviation between source and target instances x s and x t of the same class. This would lead to select landmarks that move closer x s and x t and consequently reducing the domain divergence.

At this point, we assume that the pairs (x s , x t ) are known and let C ST ⊂ LS |X ×T S be the pair set. We propose to add the new regularization term of line (3) for each pair of C ST , weighted by a regularization parameter β to tune. Let R be a set of d u candidate landmarks and LS a source sample of d l source labeled examples. Our global optimization Problem (DASF opt ) corresponds to Problem (SF opt ) with the addition of Parsimonious Unsupervised and Semi-Supervised Domain Adaptation with Good Similarity Functions 11 our regularizer and can be easily formulated as a linear program.

                     min α F (α) = 1 d l d l i=1 L g, (x i , y i ) + λ α 1 +β (xs,xt)∈C ST t φ R (x s ) -t φ R (x t ) diag(α) 1 , with L g, (x i , y i ) = 1-y i g(x i ) + and g(x i ) = du j=1 α j K(x i , x j ). (DASF opt )
This linear problem is a convex program. It can be solved by using d l slack variables for expressing the hinge loss that leads to a program with

O(d l + d u ) variables with O(d l × d u ) constraints.

Theoretical Aspects

In this section, we provide a theoretical sparsity analysis of our optimization Problem (DASF opt ) and derive a generalization error bound.

We first need the following hypothesis about the pair set C ST . Concretely, since our additional regularizer is based on C ST and contributes to find a relevant projection space, C ST has to contain relevant information. We thus suppose a restriction on the coordinates in the φ R -space of the points of C ST ,

∀x j ∈ R, max (xs,xt)∈C ST K(x s , x j ) -K(x t , x j ) > 0. (4)
This means that for each coordinate x j in the φ R -space, there is at least one pair of points that brings some diversity with different coordinate values. This is actually not a too strong restriction, since if the two domains are far from each other, then the assumption (4) occurs with high probability.

Sparsity Analysis

As said before, in Balcan et al.'s Problem (SF opt ), the 1-norm regularizer α 1 on the learned vector α implies a natural sparsity of the induced SF-classifier. Our Problem (DASF opt ) keeps this feature but analyzing its sparsity requires to also consider the additional regularization term over α. We provide here an analysis of the sparsity according to all the different hyperparameters.

Lemma 2. For any hyperparameters λ > 0 and β > 0, and for any set of pairs C ST , let B R = min

x j ∈R max (xs,xt)∈C ST |K(x s , x j ) -K(x t , x j )| . If α * denotes the optimal solution of our Problem (DASF opt ), then we have, α * 1 ≤ 1 βB R + λ .
Proof. Recall F (.) refers to Problem (DASF opt ). For any solution α,

(xs,xt)∈C ST ( t φ R (x s ) -t φ R (x t )) diag(α) 1 = (xs,xt)∈C ST du j=1 α j K(x s , x j ) -K(x t , x j ) = du j=1   |α j |   (xs,xt)∈C ST |K(x s , x j ) -K(x t , x j )|     ≥ du j=1 |α j | max (xs,xt)∈C ST |K(x s , x j ) -K(x t , x j )| .
From Hypothesis (4) and the definition of B R we have,

B R = min x j ∈R max (xs,xt)∈C ST |K(x s , x j ) -K(x t , x j )| > 0.
Thus,

(xs,xt)∈C ST ( t φ R (x s ) -t φ R (x t )) diag(α) 1 ≥ α 1 B R . Then, α * 1 (λ + βB R ) + 1 d l d l i=1   1 -y i du j=1 α * j K(x i , x j )   + ≤ F (α * ).
Since α * is optimal, we have F (α * ) ≤ F (0) = 1, where 0 is the null vector.

Finally, we directly obtain α * 1 ≤

1 βB R + λ .
According to this lemma, the sparsity of the model depends on the hyperparameters λ, β and on the quantity B R . This last term is in fact related to the distance between the points in the pair set C ST . In the projection space, it is the minimum of the maximum deviation between the coordinates of the pair's points belonging to C ST . Thus, when the two marginal distributions are far from each other, i.e. the DA task is potentially hard, B R tends to be high that can imply an increase of the sparsity. Indeed, with sparser models, the projection space defined is smaller (i.e. with less features) that tends to make closer source and target instances more easily with less constraints to take into account.

Generalization Ability

Algorithmic Robustness

We recall now the definition of robustness and its associated theorem about the generalization ability of robust algorithms (proposed by [START_REF] Xu | Robustness and generalization[END_REF]). Considering this framework for our method reveals two advantages. On the one hand, it allows us to take into account the regularizers in the generalization bound. On the other hand, the algorithmic robustness tolerates to handle non-standard learning setups like DA. We begin with the definition of a robust algorithm which stands in a standard setup where the learning sample and the test sample are drawn from the same distribution P .

Definition 3 [START_REF] Xu | Robustness and generalization[END_REF]). Given a Learning Sample LS of d l examples drawn i.i.d from a distribution P , an algorithm A is (M, (LS)) robust on P, for Parsimonious Unsupervised and Semi-Supervised Domain Adaptation with Good Similarity Functions 13

M ∈ N and (.) : (X × Y ) d l → R, if X × Y can be partitioned into M disjoint sets, denoted as {C i } M i=1 , such that for every example s belonging to LS, s, u ∈ C i ⇒ L(A LS , s) -L(A LS , u) ≤ (LS), (5)
with A LS the model learned from LS with A and L(•, •) the loss function of A.

Given a learning sample LS, the robustness of an algorithm, measured by the values of M and (LS), depends thus on the learning sample. Note that this definition has to be verified for every learning example. The authors have nevertheless relaxed it with the property of pseudo-robustness, where the condition is only required for a subset of the learning sample [START_REF] Xu | Robustness and generalization[END_REF].

From Definition 3, the authors have proved the following generalization bound over the expected error on the distribution P .

Theorem 4 [START_REF] Xu | Robustness and generalization[END_REF]). If a learning sample LS = {(x i , y i )} d l i=1 is drawn i.i.d. from a distribution P and if an algorithm A is (M, (LS)) robust, then for any δ > 0, with probability at least 1 -δ,

err P (A LS ) ≤ ê rr P (A LS ) + (LS) + L U P 2M ln 2 + 2 ln 1 δ d l ,
where err P (A LS ) and ê rr P (A LS ) are respectively the generalization and the empirical errors over P of the model A LS learned from LS, L(•, •) being upper bounded by L U P . This bound is not proved in a DA scenario but the authors have argued that such a bound could be defined by adding a term depending on a domain divergence measure.

Generalization Bound

Following the previous idea, we propose to derive a bound for the target domain using the H∆H-distance which is appropriate to the context our approach. First, we prove that our optimization problem (DASF opt ) is robust on the source domain and then deduce a generalization bound for the target domain.

Theorem 5. Suppose that (X, ρ) is a compact metric space and K is a good similarity function continuous in its first argument. If the source Learning Sample LS is drawn i.i.d. from the source domain P S , then given the hyperparameters β > 0, λ > 0, the landmark set R and a fixed pair set

C ST with B R > 0, our Problem (DASF opt ) is 2M η , Nη βB R +λ
robust on the source domain P S , where η > 0, M η being the ηcovering number2 of X and

N η = max xa,x b ∼D S ρ(xa,x b )≤η t φ R (x a ) -t φ R (x b ) ∞ .
Proof. Let (X, ρ) a compact metric space. Let η > 0, since X is compact, by the definition of the covering number, we can partition X in M η subsets (M η finite), such that for x 1 , x 2 belonging to the same subset we have ρ(x 1 , x 2 ) ≤ η. With Y divided in 2 subsets {-1}, {+1} and following the proof principle of [START_REF] Xu | Robustness and generalization[END_REF], we can partition X × Y in 2M η subsets such that the points belonging to the same subset are of the same class. Given a good similarity function K continuous in its first argument, a source learning set LS = {(x i , y i )} d l i=1 drawn i.i.d. from P S , a landmark set R = {x j } du j=1 , the hyperparameters λ > 0, β > 0 and a fixed pair set C ST , let α * be the optimal solution of Problem (DASF opt ). For any s 1 = (x 1 , y 1 ) ∈ LS, any s 2 = (x 2 , y 2 ) such that s 1 and s 2 belong to the same subset, thus y 1 = y 2 and ρ(x 1 , x 2 ) ≤ η. Then,

L (g, (x 1 , y)) -L (g, (x 2 , y)) = 1 -y 1 du j=1 α * j K(x 1 , x j ) + -1 -y 1 du j=1 α * j K(x 2 , x j ) + .
By the 1-lipschitz property of the hinge loss, the successive application of Holder inequality 3 and Lemma 2, we obtain,

L (g, (x 1 , y)) -L (g, (x 2 , y)) ≤ α * 1 t φ R (x 1 ) -t φ R (x 2 ) ∞ ≤ α * 1 max xa,x b ∼D S ρ(xa,x b )≤η t φ R (x a ) -t φ R (x b ) ∞ ≤ N η βB R + λ , with N η = max xa,x b ∼D S ρ(xa,x b )≤η t φ R (x a ) -t φ R (x b )
∞ which is finite by the continuity of K in its first argument and the definition of covering number. Then, the algorithm associated with Problem (DASF opt ) is 2M η , Nη βB R +λ robust on P S .

In our case, the hinge loss 1 -y du j=1 α j K(., x j )

+ is upper bounded by a constant L U P and to lighten the notations we suppose L U P = 1 (which is not true in general but can be easily obtained by a normalization step). Then, we directly derive the following generalization bound over the expected source error from Theorem 4.

Theorem 6. With the same notations of Theorem 5, for every h in the hypothesis class H of SF-classifiers and for any δ > 0, with probability at least 1 -δ,

err S (h) ≤ ê rr S (h) + N η βB R + λ + 4M η ln 2 + 2 ln 1 δ d l .
Proof. From Theorem 5, Problem (DASF opt ) is 2M η , Nη βB R +λ robust on the source domain P S , the result is then obtained from Theorem 4.

From this result, we can now derive a generalization bound for our unsupervised domain adaptation approach based on good similarity functions.

Theorem 7. If LS = {(x i , y i )} d l
i=1 is drawn i.i.d. from the source domain P S , for every h in the hypothesis class H of SF-classifiers, for any δ > 0, with probability at least 1-δ,

err T (h) ≤ ê rr S (h) + N η βB R + λ + 4M η ln 2 + 2 ln 1 δ d l + 1 2 d H∆H (D S , D T ) + ν,
3 Holder inequality: uv 1 ≤ u p v q , with 1 ≤ p, q ≤ ∞ and 1/p + 1/q = 1.

Parsimonious Unsupervised and Semi-Supervised Domain Adaptation with Good Similarity Functions 15

where ν is the joint error over the domains, d H∆H (D S , D T ) is the H∆H-distance between the marginal distributions.

Proof. It comes directly from the application of Theorems 1 and 6.

In this bound, d H∆H measures the domain divergence and ν the adaptation capability of the hypothesis class. The constant Nη βB R +λ clearly depends on the regularizers and on the value N η that can be as small as wished, by choosing a small η and by continuity of the similarity function K(., .) in its first argument, implying then an increase of M η . The term with M η converges in O(1/ √ d l ) and ê rr S is the empirical error over the source sample. We can remark that with small values for β and λ, or B R (indicating far domains), the process will need more examples to be reliable. In our method, the terms d H∆H and ê rr S are actually decreased by solving our Problem (DASF opt ). In the next part, we present how to select the regularization parameters to keep these two terms low and we also introduce an heuristic aiming at decreasing an estimate of ν.

Reverse Classifier and Validation

A crucial point is the choice of the different hyperparameters λ, β, C ST of our method. In a transfer learning context, [START_REF] Zhong | Cross validation framework to choose[END_REF] have proposed a Transfer Cross-Validation method for selecting the best parameters. This principle uses a reverse validation approach based on a so-called reverse classifier evaluated on the source domain. We propose to follow a similar reverse validation procedure.

Given k-folds on the source labeled sample and a learning algorithm, k -1 labeled folds are used as labeled examples for learning a classifier h . Then, using the same algorithm, a reverse classifier h r is learned from a sample constituted by the union of the target sample {(x, h (x))} x∈T S self-labeled by h and a given target labeled set. Finally, the reverse classifier h r is evaluated on the last k th fold of the source labeled sample. Note that in its original definition, this method relies on a projection space defined by a kernel and uses some few target labels.

Since, we may consider non-PSD, non-symmetric similarity functions and no label on the target domain, we then make a little adaptation: We perform the reverse validation directly in the projection space φ R and we learn the reverse classifier only with the self-labeled target sample (see Figure 4). The justification of this choice comes from the fact that if the domains are sufficiently close and related, then such a reverse classifier must be also efficient for the source task [START_REF] Bruzzone | Domain adaptation problems: A DASVM classification technique and a circular validation strategy[END_REF]. In other words, in the projection space, it is possible to pass from one problem to another. Recall that we do not have any information on the target labels. We then define our reverse classifier h r as the best SF-classifier learned with SF opt -in the current φ R -spacefrom the target sample {(x, h(x))} x∈T S , self-labeled by the classifier h learned with our Problem (DASF opt ).

In summary, given k-folds on the source labeled sample (LS = ∪ k i=1 LS i ), a classifier h is learned from k -1 labeled folds and the unlabeled target sample by solving Problem (DASF opt ) and we evaluate the associated reverse classifier h r on the last k th fold. Its empirical source error corresponds to the mean of the error over the k-folds,

ê rr S (h r ) = 1 k k i=1 ê rr LSi (h r ).
In Section 2, Theorem 1 suggests that one solution for DA is to minimize the three terms of the DA bound4 , which are also present in our generalization bound in Theorem 7. Our Problem (DASF opt ) aims at minimizing the first two terms but does not consider at the moment the last term ν corresponding to the ideal joint classifier error and defined by ν = err S (h * ) + err T (h * ) with h * = argmin h∈H (err S (h) + err T (h)). This hypothesis, unknown in general, measures the adaptation ability of the classifier. We propose then to use an estimation of ν for selecting the relevant hyperparameters. However, due to the absence of target labels, we are not able to compute or estimate this ideal hypothesis. Since h * is clearly related to the capability to pass from one domain to another, we estimate it by the reverse classifier h r . For this purpose, at each cross-validation step, we divide the self-labeled target sample {(x, h(x))} x∈T S into two parts: one is used to learn h r and then h r is evaluated on the second to give an estimate of the target error, the evaluation of h r on the current source fold giving an estimation of the source error. Then, ê rr S (h r ) (resp. ê rr T (h r )) corresponds to the mean over the k-folds of the estimation of the source error (resp. the target error) of h r . We then consider the empirical estimation of ν defined by,

+ + + + + h h
ν = ê rr S (h r ) + ê rr T (h r ), (6)
where ê rr T (h r ) is evaluated over the self-labeled target sample. Motivated by the minimization of the DA bound, we finally select the parameters leading to the minimal ν.

An Iterative Reweighting: a Way to Lighten the Search of the Projection Space

The constitution of the set C ST is difficult a priori since we have no information on the target labels. Moreover, the set of relevant pairs allowing a good adaptation is generally Parsimonious Unsupervised and Semi-Supervised Domain Adaptation with Good Similarity Functions 17 dependent on the task at hand and testing all the possible pair sets is clearly intractable5 .

In order to tackle this problem, we present an iterative approach based both on a selection of a limited number of pairs and on a reweighting scheme of the similarities keeping the distributions close. We finally present a stopping criterion using the empirical estimation of the ideal joint error.

Selecting the Pairs of C ST

We propose to construct pairs from two subsets of the two samples provided to the algorithm U S ⊆ LS |X and U T ⊆ T S of equal size. We select them, at a given iteration l, according to the reverse model g r l-1 associated with the reverse classifier h r l-1 computed in the previous iteration. They correspond to the examples on which this model is highly or weakly confident on the labels. Let δ H S , δ H T , δ L S , δ L T be a set of positive parameters, U S and U T are defined as follows such that

|U S | = |U T | ≤ N , U S = x ∈ LS |X : |g r l (x)| > δ H S OR |g r l (x)| < δ L S , U T = x ∈ T S : |g r l (x)| > δ H T OR |g r l (x)| < δ L T .
In practice, we use these two sets for building the matching C ST ⊂ U S ×U T from U S and U T . We look for a bipartite matching minimizing the Euclidean distance in the new projection φ R l -space associated with an iteration l in the iterative process (described in the next Section 5.2). This can be done by solving the following problem. Note that in the particular case of bipartite matching, it can be achieved in polynomial time by linear programming for example.

                     min χst 1≤s≤|U S | 1≤t≤|U T | (xs,xt)∈U S ×U T χ st φ R l (x s ) -φ R l (x t ) 2 2 s.t.: ∀(x s , x t ) ∈ U S × U T , χ st ∈ [0, 1], ∀x s ∈ U S , xt∈U T χ st = 1, ∀x t ∈ U T , xs∈U S χ st ≤ 1. (7)
Then C ST corresponds to the pairs of U S × U T such that χ st = 1.

In our experiments, we limit the size of the subsets U S and U T to small6 N to build efficiently this bipartite matching, since it has to be done many times according to the different iterations and cross-validation. This is not a too restrictive heuristic since the notion of pseudo-robustness of [START_REF] Xu | Robustness and generalization[END_REF] does not require to consider all the points. In this case, the values δ H S , δ H T , δ L S , δ L T correspond to the ones allowing us to select the first N elements of each type.

A New Projection Space by Iterative Reweighting

The landmarks selected 7 by solving Problem (DASF opt ) define a projection space where the two distributions tend to be close. We propose to re-use their weights α j to force the new projection space to move closer the distributions. Indeed, we reweight the similarity function according to α. Suppose at a given iteration l, with a similarity function K l , we obtain new weights α l . Then, we propose to define K l+1 by reweighting8 K l conditionally to each landmark of R such that,

∀x j ∈ R, K l+1 (x, x j ) = α l j K l (x, x j ).
It can be seen as a kind of contraction of the space to keep the empirical H∆H-distance between the marginal distributions low. Indeed, in this new φ R l+1 -space defined by K l+1 , the points of each pair of C ST are naturally close since, by construction, our regularizer used at iteration l corresponds exactly to minimize their L 1 -distance in the φ R l+1 -space. Indeed, we have,

∀(x s , x t ) ∈ C ST , t φ R l+1 (x s ) -t φ R l+1 (x t ) 1 = t (φ R l (x s ) -t φ R l (x t )) diag(α l )
1 . An illustration of this procedure is provided on Figure 5. We then iterate the process at iteration l + 1 in the new φ R l+1 -space. The possible reweightings are related to the different hyperparameters δ H/L S/T (linked to C ST ) and λ, β of Problem (DASF opt ) that are selected according to reverse validation. Recall that, since we are not interested in using valid kernels, we do not have to keep any notion of symmetry or positive semi-definiteness for K l+1 . However, our normalization remains valid only if the new similarity function is still good on the source domain. We can empirically estimate this goodness by evaluating , γ and τ of Definition 1 on LS. In practice, the empirical τ corresponds to the number of landmarks selected by the algorithm. Therefore, we evaluate the best empirical (ˆ ,γ,τ )guarantee by

γ =      γ max if argmax γmax>0 ∀(x i , y i ) ∈ LS, y i d u du j=1 K(x i , x j ) ≥ γ max exists, 0 otherwise. ˆ =          0 if γ > 0, (x i , y i ) ∈ LS : y i d u du j=1 K(x i , x j ) < 0 |LS| otherwise.
In fact, we pay attention to keep only those that offer the best (ˆ ,γ, τ )-guarantee ensuring a sufficiently good similarity. Concretely, the higher γ and the lower ˆ , the better the guarantee. Note that a bad similarity would lead to a dramatic increase of the expected source error and thus would not be selected by the reverse validation process.

Stopping Criterion

We consider here the estimated joint error ν (6) related to the adaptation capability in the current space. Controlling the decreasing of this term during the iterative process can provide a nice way to stop the algorithm. Following Section 4. l, this term is defined by νl = ê rr S (h r l )+ ê rr T (h r l ), where h r l is the reverse classifier associated with h l learned at iteration l. An increasing of νl between two iterations means that the new projection space is no longer relevant and the current one must be preferred.

Then, our process stops at iteration l when the next νl+1 has reached a convergence point or has increased significantly. This criterion allows us to ensure the algorithm stops since the joint error is positive and bounded by 0. The global iterative algorithm (named DASF) is described in Algorithm 1.

Algorithm 1 DASF: Domain Adaptation with Similarity Function input similarity function K, landmark set R, source sample LS and target sample T S output classifier h DASF h 0 (•) ← sign 1

|R| |R| j=1 K(•, x j ) K 1 ← K l ← 1 while The stopping criterion is not verified do Select U S ⊆ LS |X , U T ⊆ T S with h r l-1 C ST ← Solve Problem (7) α l ← Solve Problem (DASF opt ) with K l and C ST K l+1 ← Update K l according to α l Update R l + + end while return h DASF (•) = sign x j ∈R α l j K l (•, x j )

Complexity

In practice, hyperparameters are selected according to a grid search, which has to be done at each iteration. It is thus very heavy and it is a clear disadvantage of our method.

The global complexity at each iteration corresponds to solving three different linear programs: Problem (DASF opt ), the building of the pair set C ST (Problem (7)) and computing the reverse classifier (with Problem (SF opt )) for each parameter set. Solving a linear program is in general costly ∼ O(n 3.5 L) [START_REF] Freund | Polynomial-time algorithms for linear programming based only on primal scaling and projected gradients of a potential function[END_REF] (or ∼ O(n 3 L) with approximated solutions [START_REF] Ye | An O(n 3 L) potential reduction algorithm for linear programming[END_REF])) for a system with n variables that can be encoded in L bits. However, the optimization problems we consider are a bit sparse in the sense that all the constraints do not involve all the variables at the same time that makes the problem faster to solve. Moreover, it is important to notice that the iteration process combined with the reverse validation allows us to lighten the search of the parameters.

6. Considering a Few Target Labels: Semi-Supervised DASF

So far, we have not considered any target label data. However, for some real applications it is reasonable to assume that a few target labels are available, notably in multimedia indexing tasks. This complimentary information can be very useful for constraining the search of the classifier as we will see in the experimental section.

We propose to extend our approach to take into account the target labels by following the principle proposed in (Ben-David et al., 2010a). It considers a linear combination of source and target labeled learning data. In this case, the learning Labeled Sample LS = (LS P S , LS P T ) is composed of a sample

LS P S = {(x i S , y i S )} d S l i S =1 of d S l labeled source examples i.i.d. from P S and a sample LS P T = {(x i T , y i T )} d T l i T =1 of d T l labeled target instances i.i.d. from P T . Let θ ∈ [0, 1] such that d T l = θd l and d S l = (1 -θ)d l ensuring LS has d l = d T l + d S l labeled instances.
Recall that we aim at minimizing the target expected error err T with d T l small regarding to d S l , i.e. with few target labels. In this context, as mentioned in (Ben-David et al., 2010a), minimizing directly the target empirical error ê rr T from LS P T does not seem to be the best solution since this sample is not sufficiently representative of the target distribution.

Thus, following Ben-David et al. (2010a), we minimize a convex combination of the source and target empirical errors,

ê rr κ (h) = κ ê rr T (h) + (1 -κ) ê rr S (h), (8)
for some κ ∈ [0, 1], err κ (h) = κ err T (h) + (1 -κ) err S (h) being the associated weighted expected error. This leads us to an adaption of our previous optimization Problem (DASF opt ), with some target labels. Given LS = (LS P S , LS P T ) a sample of d l instances, C ST ⊂ LS P S |X × T S a pair set and κ ∈ [0, 1], we propose the following minimization Problem (SSDASF opt ). The global iterative algorithm (named SSDASF) is described in Algorithm 2.

                     min α (1 -κ) 1 d S l d S l i S =1 L g, (x i S , y i S ) + κ 1 d T l d T l i T =1 L g, (x i T , y i T ) + λ α 1 + (1 -κ) β (xs,xt)∈C ST t φ R (x s ) -t φ R (x t ) diag(α) 1 , with L g, (x i , y i ) = 1-y i g(x i ) + and g(x i ) = du j=1 α j K(x i , x j ).
(SSDASF opt )

h 0 (•) ← sign 1 |R| |R| j=1 K(•, x j ) K 1 ← K l ← 1 while The stopping criterion is not verified do Select U S ⊆ LS P S |X , U T ⊆ T S with h r l-1 C ST ← Solve (7) α l ← Solve (SSDASF opt ) with K l and C ST K l+1 ← Update K l according to α l Update R l + + end while return h SSDASF (•) = sign x j ∈R α l j K l (•, x j )
Whereas our previous Problem (DASF opt ) focuses only on the minimization of the source empirical error, this optimization problem minimizes the convex combination of the source and target empirical errors (Equation ( 8)). We can in fact make some connections showing that (SSDASF opt ) can be seen as a generalization of some previous problems. Firstly, when κ = 0, no target labeled data is used and we move back to our standard DASF algorithm with Problem (DASF opt ). Secondly, when κ = 1 we stand in a usual supervised framework where the learning and test samples are drawn according to the target domain P T . Then, Theorem 4 of [START_REF] Xu | Robustness and generalization[END_REF] about robustness can be proved on P T .

We can also derive for our new Problem (SSDASF opt ) a generalization bound. First, we adapt the preceding result on sparsity analysis. Lemma 3. For any hyperparameters λ > 0 and β > 0, κ ∈ [0, 1] and for any pair set C ST , let B R = min

x j ∈R max (xs,xt)∈C ST |K(x s , x j ) -K(x t , x j )| . If α * denotes the optimal solution of our Problem (SSDASF opt ), then we have, α * 1 ≤ 1 (1 -κ)βB R + λ .
Proof. We use the same proof process as in Lemma 2.

This result suggests that when some additional target labels are used, i.e. (1 -κ) < 1, the induced model is less sparse than the approach with no target label. From this result, we can now provide our generalization bound combining source and target labels. then with probability at least 1 -δ,

Theorem 8. Let θ ∈ [0, 1], κ ∈ [0, 1],
err T (h) ≤ err T (h * ) + κ 2 θ + (1-κ) 2 1-θ ln 4 δ 2d l + κ(N T η -N S η ) + N S η (1-κ)βB R + λ + 2M ln 2 + 2 ln 4 δ d l κ √ θ + 1-κ √ 1-θ + 2(1-κ) 1 2 d H∆H (D S , D T )+ν , (9)
where B R = min

x j ∈R max (xs,xt)∈C ST |K(x s , x j ) -K(x t , x j )| , and
N S η = max xa,x b ∼D S ρ(xa,x b )≤η t φ R (x a ) -t φ R (x b ) ∞ , N T η = max xa,x b ∼D T ρ(xa,x b )≤η t φ R (x a ) -t φ R (x b ) ∞ .
Proof. Deferred to "Appendix".

Note that, when κ = 0, i.e. when we ignore target data, the bound is similar to that of Theorem 7. On the other hand, when κ = 1, i.e. we do not use source information, the bound becomes a classical standard learning bound with robustness in a supervised setting with only target data.

In order to illustrate some properties of that bound, we provide an analysis of its behavior, following the same principle as in (Ben-David et al., 2010a). In its present form, the bound is a bit difficult to analyze and in order to simplify our study, we make some little assumptions. First, we assume κ ∈ [0, a], where a is a positive number tending to 1 such that a < 1. This allows us to bound the following term

κ(N T η -N S η ) + N S η (1 -κ)βB R + λ < κ(N T η -N S η ) + N S η (1 -a)βB R + λ .
Then, we define

A = 1 2 d H∆H (D S , D T ) + ν, B = (1 -a)βB R + λ, C = 2M ln 2 + 2 ln 4 δ d l 1 √ θ - 1 √ 1 -θ + (N T η -N S η ) B -2A,
and D as the remaining constant terms. The bound (9) can then be rewritten as,

f (κ) = κ 2 θ + (1 -κ) 2 1 -θ ln 4 δ 2d l + Cκ + D.
With d T l = θd l and d S l = (1 -θ)d l , the general form of the highest root r of the derivative is

r = θ   1 + 1 -θ 2 ln 4 δ d l C 2 -θ(1 -θ)   = d T l d S l + d T l   1 + d S l 2 ln 4 δ (d S l +d T l ) C 2 -d S l d T l   .
To simplify the analysis, we assume (1-θ)2A 2 for r to be valid. Thus the optimal value is defined as follows,

N T η = N S η -B 2M ln 2+2 ln 4 δ d l 1 √ θ -1 √ 1-θ > 0 which can
κ =        a if d T l ≥ ln 4 δ (1 -θ)2A 2 , min{a, r} if d T l < ln 4 δ (1 -θ)2A 2 .
An interesting remark is that when A = 0, the bound suggests κ = θ, i.e. when the two domains are indistinguishable κ has to follow the repartition defined by the training sample. If we have no target label (i.e. d T l = 0) the bound suggests κ = 0. If we have only target labels (d S l = 0) or if d T l is large, κ must be chosen as 1, which is consistent with our framework. When the domains are very different, i.e. A is maximum, the bound says that κ tends to be 1, i.e. it is better to rely only on target labeled points. With other values of N T η /N S η , this tendency is also confirmed with our value B R . Indeed, when it is high, i.e. domains are far in the current representation, it seems better to put more weights on labeled target points. We can also see from B that when our hyperparameters are small, i.e. when we give a small importance to the decreasing of the distance or when we allow complex models, we should rather focus on target points with κ high, while a smaller value of κ can be better in the opposite case. As a conclusion, this analysis is close to the one provided in (Ben-David et al., 2010a) but has the advantage to take into account our regularizers for explaining the behavior of the approach.

Experiments

In this section, we evaluate our approach DASF, and its semi-supervised extension SS-DASF, on a synthetic toy problem and on a real image annotation task. We first present in Section 7.1 the similarity function used. More precisely, we propose an heuristic procedure to modify a priori the projection space for obtaining a relevant similarity, which is non-symmetric and non-PSD, for domain adaptation. Then in Section 7.2, we introduce the general setup for all our experiments. The results for the synthetic datasets are given in Section 7.3 and those for the image classification problems are presented in Section 7.4.

Similarity Function

We propose here to introduce an intuitive pre-process to design a similarity function potentially non-PSD, non-symmetric. According to the theoretical result of DA of Ben-David et al. (2010a) (Theorem 1) the learned classifier should perform well on the target domain and also on the source one. Thus, we aim at facilitating the adaptation to the target domain in order to link the source and target domains by considering information from both of them. Concretely, we build our new similarity function K ST by renormalizing a given similarity function K relatively to the unlabeled sample ST = LS |X ∪T S. Our choice is clearly heuristic and our aim is just to evaluate the interest of renormalizing a similarity for DA problems. Recall that, from Definition 1, a similarity must be good relatively to a set of reasonable points R. We actually propose to renormalize the similarities to these points: We perform a specific normalization for each instance x j ∈ R. The idea is to apply a scaling to mean zero and standard deviation one for the similarities of the instances of ST to each x j . Given a similarity function K which verifies the Definition 1 our normalized similarity function K ST is defined by,

∀x j ∈ R, K ST (., x j ) =                    K(., x j ) -µ x j σ x j if -1 ≤ K(., x j ) -μx j σx j ≤ 1 , -1 if K(., x j ) -μx j σx j ≤ -1 , 1 if 1 ≤ K(., x j ) -μx j σx j , ( 10
)
where μx j is the empirical mean of similarities to x j over ST ,

∀x j ∈ R, μx j = 1 |ST | x∈ST K(x, x j ),
and σx j is the empirical unbiased estimate of the standard deviation associated to μx j ,

∀x j ∈ R, σx j = 1 |ST | -1 x∈ST K(x, x j ) -μx j 2 .
By construction, the similarity K ST is then non-symmetric and non-PSD.

For all experiments, we take as similarity function K a Gaussian kernel,

K(x, x ) = exp - x -x 2 2 D 2 . ( 11
)
However, depending on the samples, the non-symmetric, non-PSD similarity K ST does not always offer better( ,γ,τ )-good guarantees than the Gaussian kernel. In the following, we only indicate the similarity which leads to the best results. Those obtained with K ST are pointed out with a * , as we will see they correspond generally to harder tasks.

General Experimental Setup

We compare our algorithm DASF with a classical SVM learned only from the source domain, the semi-supervised Transductive SVM [START_REF] Vapnik | Statistical Learning Theory[END_REF] (TSVM) and the DA method DASVM [START_REF] Bruzzone | Domain adaptation problems: A DASVM classification technique and a circular validation strategy[END_REF]. We take a classical Gaussian kernel (11) for these three methods to facilitate the comparison. We use the SVM-light library [START_REF] Joachims | Transductive inference for text classification using support vector machines[END_REF] with parameters tuned by cross-validation on the source data for SVM and TSVM. DASVM is implemented with the LibSVM library [START_REF] Chang | LIBSVM: a library for support vector machines[END_REF]. The parameters of DASVM and DASF are tuned according to a grid search by reverse validation. We also measure the behavior of a SF-classifier trained only from the source domain. For DASF and SF, the landmarks are taken from the labeled source sample. Following Equation ( 1), we assess an estimation of the H∆H-distance dH∆H between the two marginal distributions by learning a SF-classifier to separate source from target samples: A small value -near 0 -indicates close distributions while a larger value -near 2 -indicates a hard DA task. We also observe the influence of the hyperparameters λ (with fixed β) and β (with fixed λ) on our method DASF. The tested values for these parameters are 0, .01, 0.1, .25, .5, .75 and 1.

Parsimonious Unsupervised and Semi-Supervised Domain Adaptation with Good Similarity Functions 25 Finally, we observe the behavior of the algorithm SSDASF when we combine labeled target points and labeled source points in the learning sample. In other words, we measure the ability of our method to learn a low-error classifier when a part of the learning sample is drawn according to the target domain. For that purpose, each DA task is repeated 9 times by using the semi-supervised extension SSDASF with the addition of 9 random sets of 2,4,8,10,12,14,16,18 and 20 labeled target examples in the learning sample. For these cases, we compare results with a SF-classifier learned only from the considered target labeled sample. Additionally, we regard the impact of the parameter κ of Problem (SSDASF opt ). In this case, we fix λ, β and the number of labeled target data at 10. The tested κ are 0, . 01, 0.1, .25, .5, .75, .80, .85, .90, .95, .99 and 1. Note that, in this context, we add target (both labeled and unlabeled) landmarks in R, while for DASF R contains only the learning source examples9 . Moreover, in this study we have not reported the observation of λ and β of Problem (SSDASF opt ), since the behavior of SSDASF for these parameters is the same than for DASF.

Simultaneously, we compute the average time costs of each algorithm with fixed parameters. Actually, the baseline is the one of learning a SF-classifier. Then, we report the duration of the other methods as the ratio of this baseline10 . We also consider the execution time of the first iteration of our approaches (reported as it1 ). Recall that considering all the possible pairs is completely intractable and that our iterative method provides a way to tackle this problem. Within these experiments, we will show that our iterative procedure leads to a very reasonable and competitive additional cost.

Synthetic Toy Problem Setup

As the source domain we consider a classical binary problem with two inter-twinning moons, each class corresponding to one moon (Figure 6). We then considerate 8 different target domains by rotating anticlockwise the source domain according to 8 angles. The higher the angle, the more difficult the problem becomes. For each domain, we generate 300 instances (150 of each class). Moreover, to assess the generalization ability of our approach, we evaluate each algorithm on an independent test set of 1500 points drawn from the target domain (not provided to the algorithm). Each DA problem is repeated 10 times and the results will come next.

Choice of the "Best" Similarity Function Before presenting the results and in order to evaluate if K ST is a better similarity on the target domain, we propose to empirically study the ( ,γ)-guarantees on the target sample according to Definition 1. For that purpose, given R = {x j } du j=1 , we estimate as a function of γ from a labeled target sample {x i , y i } dt i =1 (with true labels but only for this evaluation). Indeed, for a given γ, is the proportion of examples x i verifying

x j ∈R y i y i K(x i , x j )/d u < γ. For each similarity function, we compute according to 20 values of γ between 0 and 1. We then obtain a curve representing as a function of γ. By considering each DA problem (each rotation angle), we obtain two curves and the best similarity function is the one with a lower area under the curve, meaning a lower error in average. Figure 7 shows the goodness guarantees of the similarity functions over each problem. We observe for hardest problems (≥ 50 • ) an improvement of the goodness with the normalized similarity K ST . For easier tasks, this improvement is not significant, justifying the fact that the similarity K can be better. Our normalized similarity thus seems relevant only for hard DA problems. Note that the rate is relatively high because we consider only landmarks from the source sample to study our adaptation capability.

Results

The average accuracy of each method is reported in Table 2. We also indicate the average number of support vectors (SV) used by SVM, TSVM and DASVM, the number of landmarks (LAND.) selected by SF and DASF and an estimation of dH∆H (D S , D T ) between the marginal distributions in the initial φ R 0 -space and the final φ R f inal -space. We can make the following remarks.

-In average, DASF outperforms the other methods. It is significantly better for every problem with an angle greater than 20 • . While the accuracy of TSVM and DASVM falls down from 60 • , DASF still remains competitive even when the difficulty in- creases. As we have shown on Figure 7, we have the confirmation that the normalized similarity ( * ) is preferred in these cases. -The number of landmarks (LAND.) is significantly lower than the number of support vectors SV, which confirms that DASF produces very sparse models with good performances. The gain ratio is between 3 to 12. The DASF-classifiers are also sparser than the SF-ones which use a L1-regularization too. Finally, they tend to be sparser for difficult problems as suggested by Lemma 2. -The empirical H∆H-distance between the domains is lower at the last iterationbetween 1 and 9 -showing our iterative process is effectively able to quickly move closer the distributions. As evoked before, DASF tends to build a small projection space for hard tasks, probably to have sufficiently close domains, but it may imply a loss of expressiveness.

Figure 8 shows two DASF runs on two DA problems. For both cases, the empirical H∆H-distance decreases significantly in comparison with the first iteration. The algorithm stops when the joint error reaches a minimum after decreasing continuously. Note that the final projection space is not always the one with the lowest distance. This is because we need to find a good compromise between the minimization of the H∆Hdistance and the one of the source error. Thanks to the iterative procedure, DASF is then able to slightly auto-correct the projection space when it allows a better adaptation. For the 30 • example, DASF finds a null error classifier on the target test sample. For the more difficult 50 • example, DASF performs better than the SF-classifier learned only on the source data. Note that the source error increases, that is expected since we aim at being performing on the target domain. Fig. 8. Toy Problem: Two DASF runs. On the left for a 30 • rotation, on the right for a 50 • rotation. On the left y-axis is the error rate, on the right y-axis is the divergence measure. We provide the error rates of the classifiers h l built at each iteration on the source and target test samples, the divergence dH∆H , the reverse classifier joint error, the error on the target test sample of a SF-classifier learning without DA as a baseline. DASF: Influence of the Hyperparameters λ and β We aim at observing how the correct classification rate evolves according to different values of the hyperparameters of our global Problem (DASF opt ) for DASF. Experiments reported on Figure 9(a), respectively Figure 9(b), correspond to the average correct classification rate for each rotation angle according to λ ∈ [0; 1] (with the bestβ), respectively β ∈ [0; 1] (with the best λ). Moreover, in Table 3, we indicate the average number of reasonable points (i.e. the sparsity) associated with the learned models. We can make the following remarks:

-Concerning λ, on Figure 9(a) we note that for the 4 easiest tasks, this parameter does not influence a lot the results: The gain is between 0 and 0.1. However, for the 4 hardest tasks, chosen a relevant λ shows better results: The gain is between 0.1 and 0.2. For all problems, the best value seems to stand between 0.1 and 0.25. From Table 3(a), we note that the sparsity of the models does not really depend on the value of λ, indeed this sparsity is also influenced by β and it is the combination of the both that leads to sparser models. -On Figure 9(b), we remark that the models are more sensitive to β than λ. In fact, when β tends to the best value, the increasing of the correct classification rate is more significant than for λ: The gain is between 0.05 and 0.35. Like in the observation of λ, the hardest tasks are more sensitive to β. The relevant value of β seems to stand between 0.5 and 1. Moreover, as expected by Lemma 2, the sparsity increases with the value of β associated with the best model (see We consider here SSDASF, the semi-supervised extension of DASF combining source and target labeled samples by solving (SSDASF opt with the setup of Algorithm 2. Firstly, on Figure 10(a) we observe the average correct classification rates by adding target labeled samples of different sizes. The results show that the classifier's performance increases with the number of labeled target examples which is an expected behavior. The more difficult the problem, the more significant the increase. However, for the hardest tasks (≥ 70 • ) we are not able to find an efficient classifier in comparison with a SF-classifier only learned from the labeled target sample (without DA). It is coherent with the analysis of the semi-supervised generalization bound since for the hardest tasks, the models need more target labels when the domains are far, and sometimes it is more reliable to focus only on target data.

Secondly, on Figure 10(b) we observe the behavior of SSDASF (using 10 target labels) according to the hyperparameter κ which weights the importance of the labeled target data in Problem (SSDASF opt ). We fix λ = 0.15 and β = 0.75. As expected, this method needs a high κ value between 0.9 to 0.99: The gain is between 0.1 to 0.5, and again the impact is higher for the hardest problems. From Table 4, κ directly influences the sparsity of the models for the easiest tasks. However, for the hardest ones, i.e. when B R tends to be high, κ has a lower impact. Finally, as expected from Lemma 3, the use of target labeled data leads to less sparse models.

Computational Costs

We report now in Table 5. Toy Problem: The average computational costs of each method measured as a ratio of the baseline SF.

Rotation angle 20 mated due to the lack of information on the target sample. SVM performs often better than the two previous ones that can be explained by the similarity between the train and test data. DASF has the best behavior on average. It always improves the results of a SF-classifier, avoiding negative transfer, and is the best for 18 concepts. Moreover, it always outputs significantly sparser models. As an illustration, we give in Figure 12 the landmarks selected for the concept PERSON.

• 30 • 40 • 50 • 60 • * 70 • * 80 • * 90 • * AVERAGE SVM 1 1 1 1 1 1 1 1 1 SF 1 1 1 1 1 1 1 1 1 TSVM 3 3 1 1 1 1 2 3 1 .

Computational Costs

The average execution time of each algorithm (with fixed parameters) is reported in Table 7. We recall that the SF-classifier learning is the baseline. For this real corpus, DASVM is significantly more costly. Unlike the toy problem, SVM is on average longer than the baseline and DASF quicker than TSVM. This is probably a direct consequence of the use of the L1-norm regularization. Indeed, the size of the set of landmarks is lower than the quantity of possible support vectors. Again, an interesting point is that the cost of the first iteration of our method (DASF it1 ) is the same as the cost of a SF learning.

Parsimonious Unsupervised and Semi-Supervised Domain Adaptation with Good Similarity Functions 33 Moreover, the additional cost due to the iterations of DASF is again very reasonable: it is of a factor 5.4 on average and significantly lower than DASVM and TSVM.

Results

The results evaluated with the F-measure are reported in Table 8. DASF obtains the best results on average and outputs again significantly sparser models. Finally, for those hard tasks, the normalized similarity is always preferred ( * ), showing that DASF is effectively able to deal with non symmetric non PSD good similarities. K ST has the interest of incorporating some target information which seems useful for hard DA tasks.

DASF: Influence of the Hyperparameters λ and β

In these experiments, we observe on Figure 13 the impacts on the F-measure of λ (with the best β) and β (with the best λ). We make the following remarks:

-From Figure 13(a), the parameter λ shows a relative influence except for the concept CAR where the value leading to the best classifier is near 0.25 (for which the gain is at least 0.15). For the others, the gain is lower than 0.1. The best λ depends on the considered problem but must be greater than 0, indicating that the corresponding regularization is necessary. -From Figure 13(b), β clearly shows a higher impact: For BOAT, CAR and PLANE the gain is between 0.1 and 0.15. Except for PERSON where the gain is quasi null, the choice of a relevant β can imply an improvement of at least 0.05 and even more. The value associated with the best classifier is greater than 0 and belongs to [0.01; 0.25] except for the concept PLANE which prefers a β greater than 0.5.

Like for the toy problems, the parameter β has a higher impact. Thus, for lightening a bit the search of relevant parameters, one can focus more precisely on β than on λ.

SSDASF: Influence of Combining Source and Target Labeled Learning Sample On Figure 14(a), we can observe the average results for each concept by running SS-DASF on a combination of source and target labeled learning samples. These results improve those obtained without target labels. We can remark that with less than 8 target labeled examples, our extended approach SSDASF always improves the results in comparison with a SF-classifier learned only from the target labeled data. Some concepts may even need more than 20 target examples that shows that the addition of a few target labels can be very useful.

On Figure (14(b)) are reported results for the different values of κ (with 10 target labels and the best λ and β). Then, we clearly see that a relevant value for κ stands between 0.9 and 0.99 showing that the target labels give an important -additionalinformation during the learning process for these hard DA tasks.

Finally, it appears that, for some concepts, the used visual features may be not very expressive which can explain the difficulty to obtain better results. In fact, in many image processing or multimedia issues, data are often represented with multimodal or multiview features in order to have a higher level of expressiveness. Taking into account such multimodal features would lead to further investigation, out of the scope of this paper. But this might be clearly a promising perspective.

Computational Costs

Table 9 corresponds to the average computational costs (with fixed parameters) reported as a ratio of the baseline (SF). The only difference with the previous image classification task (c.f. Section 7.4.1) is that TSVM is here quicker than DASF. This may be due to the difficulty of the task. In fact, in Section 7.4.1 the distance between the marginal distributions is low, whereas in this experiment the distance is large. This imply a harder construction of the set of pairs: When the points are far from each other, the minimization of the objective function of Problem (7) needs more time.

Lastly, SSDASF (and its first iteration) is about 1.5 more longer than the unsupervised DASF. The Problem (SSDASF opt ) is actually constructed by adding constraints to Problem (DASF opt ). Then, it explains why it may need more time for being solved. For both DASF and SSDASF, the overhead cost due to the iterations is again relatively reasonable with a factor 10 on average, showing that the iterative approach is still competitive in terms of computational cost.

Conclusion and Perspectives

In this paper, we have proposed a novel domain adaptation approach that makes use of the framework of Balcan et al. (Balcan et al., 2008a;Balcan et al., 2008b) allowing one to deal with similarity functions potentially non-PSD and non-symmetric. Our method relies on a regularization term that helps to build a projection space -made of similarities to landmark points -by selecting the landmarks that are both close to the source and target examples. We have also proposed an effective iterative procedure in order to lighten the search of the projection space by a reweighting of the similarities. The linear formulation of the method enables the proposed algorithm to output sparse models, even when the DA task is hard. We have also studied the generalization ability of our method according to the framework of robustness which allows us to take into account our regularizers. Moreover, we have extended our method for allowing the use of some few target labels. We have shown experimentally good adaptation capabilities on various tasks. Furthermore, our method always outputs sparser models which is clearly an advantage for a large scale application perspective. Additionally, our results show that a similarity renormalized according to a DA objective in a non-PSD and non-symmetric way enables us to infer better models for difficult domain adaptation problems. Finally, we present and discuss several perspectives.

Designing Non-PSD Similarity Function by Metric Learning. From our experimental evaluation (Section 7.1), it appears that the use of non-PSD non-symmetric functions can be useful for solving domain adaptation tasks. So far, we have only proposed a simple heuristic for designing such similarities. It is nevertheless an important issue to be able to automatically design relevant good similarities. We think that a possible direction is to investigate some metric learning approaches for domain adaptation. At the moment, few methods exist [START_REF] Zhang | Transfer metric learning by learning task relationships[END_REF][START_REF] Geng | DAML: Domain adaptation metric learning[END_REF][START_REF] Cao | Distance metric learning under covariate shift[END_REF][START_REF] Kulis | What you saw is not what you get: Domain adaptation using asymmetric kernel transforms[END_REF] and they mainly focus on PSD similarities. A possible way could be to combine such approaches with non-PSD similarity learning like the work of [START_REF] Bellet | Learning good edit similarities with generalization guarantees[END_REF].

Parsimonious Unsupervised and Semi-Supervised Domain Adaptation with Good Similarity Functions 37

Building a Projection Space of Landmark Points. According to the theory of (Balcan et al., 2008a;Balcan et al., 2008b), a low-error linear classifier can be learned in the explicit φ R -space induced by the mapping function φ R , defined by the landmarks (see Equation ( 2)). In fact, according to Theorem 2, the process needs enough different and representative landmarks for learning a good classifier. On the other hand, using a lot of landmarks implies a high dimensional projection space and thus to deal with a more complex optimization problem. One possible perspective is to use a pre-processing step for selecting a limited set of relevant landmark points (such as clustering [START_REF] Macqueen | Some methods of classification and analysis of multivariate observations[END_REF] for example) in order to deal with a lower dimensional space. An important issue in this context is to select the ratio of source and target instances to use in the projection space. Indeed, in our experiments, we have noticed that in the unsupervised setting, the addition of target instances in the space of landmarks does not improve the results while the addition of target landmarks appears necessary in the semi-supervised approach. Moreover, this step is clearly related with the metric learning perspective evoked above since the projection space also depends on the similarity and a good similarity could compensate the lack of dimension.

Relationships with other DA frameworks The two previous perspectives are of high importance for precisely modeling the domain adaptation problem. For example, if the source and target domains are not very different, we have to slightly modify a relevant projection space for the source domain. This can be done by looking for some few new relevant landmark points. Some outlier detection can eventually help to find the part of the density that requires more attention. However, if the two domains are very different, we then must modify drastically the projection space. Another interesting and important perspective is also to investigate the link with reweighting methods for domain adaptation like [START_REF] Jiang | Instance weighting for domain adaptation in nlp[END_REF][START_REF] Mansour | Domain adaptation: Learning bounds and algorithms[END_REF][START_REF] Sugiyama | Direct importance estimation with model selection and its application to covariate shift adaptation[END_REF] and in particular their relationships with our iterative procedure for reweighting similarities. Another point concerns our generalization bound: The divergence measure d H∆H used is not directly linked with the framework of robustness. In their extended work, [START_REF] Xu | Robustness and generalization[END_REF] mention in their perspectives that the sum of the absolute values of the deviations between the expectations of source and target examples in each part of the instance space cover can be used to bound the domain adaptation error. It may lead to better convergence bound but deserves more investigation in our case.

Combining Multiple Source Data. To deal efficiently with images or video corpora, it is necessary to use multimodal or multiview representations allowing one to combine multiple features taking into account various information (such as colors, textures, spatiotemporal descriptors, . . . ). A perspective is then to consider an adaptation of some multisource frameworks presented in (Balcan et al., 2008b;Ben-David et al., 2010a;[START_REF] Chattopadhyay | Multi-source domain adaptation and its application to early detection of fatigue[END_REF][START_REF] Duan | Domain adaptation from multiple sources via auxiliary classifiers[END_REF][START_REF] Mansour | Domain adaptation with multiple sources[END_REF]. Another standpoint could be to study some multi-tasks approaches [START_REF] Ando | A framework for learning predictive structures from multiple tasks and unlabeled data[END_REF][START_REF] Fei | Structured feature selection and task relationship inference for multi-task learning[END_REF][START_REF] Xu | Multi-task learning with task relations[END_REF].

Parsimonious Unsupervised and Semi-Supervised Domain Adaptation with Good Similarity Functions 39

where B R = min

Fig. 2 .

 2 Fig. 2. The intuition behind Theorem 1. The source domain points are in (dark) green (pos.+, neg.-), the target domain points are in (light) orange.

Fig. 3 .

 3 Fig. 3. A set of positive (red crosses) and negative (blue circles) points.

  (a): x A = (.05, .35), +1 , x B = (.10, .35), +1 , x C = (.05, .10), +1 , x D = (.15, .10), +1 , x E = (.10, .10), -1 ,

Fig. 4 .

 4 Fig. 4. The reverse validation process in the φ R -space. Step 1: Learn the classifier h with the Problem (DASFopt). Step 2: Auto-label the target sample with h. Step 3: Learn the reverse classifier h r on the autolabeled target sample with the Problem (SFopt). Step 4: Evaluate h r on the source sample (with a k-folds process).

  3, at a given iteration Parsimonious Unsupervised and Semi-Supervised Domain Adaptation with Good Similarity Functions 19 associated bipartite matching C ST : a line corresponds to a pair (xs, xt). The points in the new φ R l+1space after the reweighting procedure.

Fig. 5 .

 5 Fig. 5. An iteration of DASF. The source points are in (dark) green (pos. +, neg. -), the unlabeled target ones are (light) orange circles.

  be obtained by choosing appropriate η, η with d l sufficiently large and/or by Parsimonious Unsupervised and Semi-Supervised Domain Adaptation with Good Similarity Functions 23 considering an upper bound of the function f (κ) verifying this equality, we must then have d T l < ln 4 δ

Fig. 6 .

 6 Fig. 6. Toy Problem: On the left: a source sample. On the right: a target sample with a 50 • rotation.

  (a) For a 20 • task. (b) For a 30 • task. (c) For a 40 • task. (d) For a 50 • task. (e) For a 60 • task. (f) For a 70 • task. (g) For a 80 • task. (h) For a 90 • task.

Fig. 7 .

 7 Fig. 7. Toy Problem: Goodness of the similarities over the target samples: (Epsilon), as a function of γ (Gamma).

  (a) The average rate according to λ with β = 0.75. The average rate according to β with λ = 0.15.

Fig. 9 .

 9 Fig. 9. Toy Problem: The correct classification rate according to λ and β in Problem (DASFopt) of DASF.

  (a) The average rates for each rotation angle according to the quantity of labeled target examples in the learning sample. The result obtained without source data (i.e. considering only target labels) is indicated with the dashed black line with big dashes. The average rates according to κ with 10 target labeled examples, λ = 0.15 and β = 0.75.

Fig. 10 .

 10 Fig. 10. Toy Problem: The average correct classification rates obtained by combining source and target labeled samples in Problem (SSDASFopt), i.e. with SSDASF.

Fig. 12 .

 12 Fig. 12. Image Classification: The 6 landmarks selected for the concept PERSON, the first three images are positive and the last three are negative (PascalVOC).

7. 4

 4 .2. Adaptation from PascalVOC 2007 to TrecVid 2007 Setup In the last experiment, we select the 6 common concepts between TrecVid 2007 and PascalVOC 2007. For each concept, we keep our previous PascalVOC train set as the source domain and take, as the target domain, a TrecVid set of examples with the same ratio +/as the train set. dH∆H is about 1.4, justifying the high difference between the two corpora and thus a potentially hard DA task.

  (a) The F-measure according to λ with β fixed. The F-measure according to β with λ = 0.15.

Fig. 13 .

 13 Fig. 13. Image Classification: The results for each concept according to λ and β in Problem (DASFopt), with DASF.

  (a) The F-measure according to the quantity of labeled target examples in the learning sample. "Without Source Data" corresponds to the result obtain with a SF-classifier learned only from the target labeled sample. The F-measure according to κ with 10 labeled target examples, λ = 0.15 and β fixed.

Fig. 14 .

 14 Fig. 14. Image Classification: The F-measure obtained for each concept by combining source and target labeled samples in Problem (SSDASFopt), i.e. with SSDASF.

  xt)∈C ST |K(x s , x j ) -K(x t , x j )| andN S η = max xa,x b ∼D S ρ(xa,x b )≤η t φ R (x a ) -t φ R (x b ) ∞ , N T η = max xa,x b ∼D T ρ(xa,x b )≤η t φ R (x a ) -t φ R (x b ) ∞ .Proof. First, by applying Theorem 4 on the target domain and on the source domain, with Lemma 3 and eventually two different covers of X, we have respectively:with probability 1 -δ 4 and N T η = max xa,x b ∼D T ρ(xa,x b )≤η t φ R (x a ) -t φ R (x b ) ∞ , κ ê rr T (h) η = max xa,x b ∼D S ρ(xa,x b )≤η t φ R (x a ) -t φ R (x b ) ∞ , (1 -κ) ê rr S (h) ≤ (1 -κ)Let h be the hypothesis minimizing ê rr κ (h),h * = argmin h ∈H {err T (h )/ ê rr κ (h) ≤ ê rr κ (h )} and let A = 1 2 d H∆H (D S , D T ) + ν, then err T (h) ≤ err κ (h) + (1 -κ)A,from Lemma 4, ≤ ê rr κ (hκ)A, by Theorem 4 on the two domain errors with M = max(M η , M η ), ≤ ê rr κ (h * ) + κκ)A, since ê rr κ (h) ≤ ê rr κ (h * ), ≤ err κ (h * ) κ)A, by Lemma 4.

  Parsimonious Unsupervised and Semi-Supervised Domain Adaptation with Good Similarity Functions 21Algorithm 2 SSDASF: Semi-Supervised Domain Adaptation with Similarity Function input Similarity function K, landmark set R, labeled sample LS = (LS P S , LS P T ), target sample T S output classifier h SSDASF

  and LS be a labeled learning sample of size d l constituted of θd l instances i.i.d. from target distribution P T and (1 -θ)d l examples i.i.d. from source distribution P S . Let η , η > 0, with M = max(M η , M η ) a covering number for X, β > 0, λ > 0 and B R > 0. For all h ∈ H minimizing the empirical error by Problem (SSDASF opt ), if h

* = argmin h ∈H {err T (h )/ ê rr κ (h) ≤ ê rr κ (h )},

Table 2 .

 2 Parsimonious Unsupervised and Semi-Supervised Domain Adaptation with Good Similarity Functions 27 Toy Problem: Average accuracy over the 8 toy problems.

	Rotation angle	20 •	30 •	40 •	50 •	60 • *	70 • *	80 • *	90 • *
	SVM	89.68	75.99	68.84	60.00	47.18	26.12	19.22	17.2
		±0.78	±0.92	±0.85	±1.08	±2.82	±3.12	±0.28	±0.37
	SV					18
						±0.99
	SF	92.4	81.81	72.55	57.85	43.93	39.2	35.93	36.73
		±3.13	±4.62	±7.60	±4.81	±4.46	±9.64	±10.93	±10.17
	Land.			24		22	20	20	20
			±1.72		±3.57	±2.06	±2.82	±1.51
	TSVM	100	78.98	74.66	70.91	64.72	21.28	18.92	17.49
		±0.00	±2.31	±2.17	±0.88	±9.10	±1.26	±1.10	±1.12
	SV	28	37	37	37	38	35	37	36
		±1.92	±3.77	±2.66	±1.50	±2.67	±2.93	±2.10	±1.69
	DASVM	100	78.41	71.63	66.59	61.57	25.34	21.07	18.06
		±0	±4.56	±4.16	±4.01	±4.15	±3.28	±2.33	±2.66
	SV	20	20	26	28	29	34	38	23
		±3.13	±4.42	±6.80	±2.81	±3.62	±7.58	±6.20	±4.95
	DASF	99.80	99.55	91.03	81.27	65.23	61.95	60.91	59.75
		±0.40	±1.19	±3.30	±4.36	±6.36	±4.88	±2.24	±2.11
	Land.	10	10	9	8	4	4	4	3
		±2.32	±1.59	±2.21	±3.27	±0.99	±2.16	±1.84	±1.06
	dH∆H in φ R 0	0.58	1.16	1.31	1.34	1.34	1.32	1.33	1.31
		±0.04	±0.04	±0.04	±0.04	±0.03	±0.03	±0.03	±0.05
	dH∆H in φ R f inal 0.33	0.66	0.82	0.85	0.39	0.40	0.49	0.45
		±0.12	±0.11	±0.13	±0.11	±0.15	±0.05	±0.12	±0.09

Table 3 .

 3 Toy Problem: The average landmark number (i.e. the sparsity) according to λ and β from DASF. Bold values are associated with the best model. (a) The sparsity according λ with β = 0.75. The sparsity according to β with λ = 0.15.

	Rot. angle	20 • 30 • 40 • 50 • 60 • 70 • 80 • 90 •	(b) Rot. angle	20 • 30 • 40 • 50 • 60 • 70 • 80 • 90 •
	λ = 0	16	12	13	8	12	6	7	8	β = 0	24	24	24	24	22	20	20	20
	λ = 0.01	15	10	9	6	5	5	8	11	β = 0.01	22	18	20	20	4	6	6	11
	λ = 0.1	10	9	8	6	3	3	2	6	β = 0.1	16	17	17	19	3	4	5	9
	λ = 0.25	15	11	12	5	4	5	6	3	β = 0.25	13	11	13	12	3	3	5	7
	λ = 0.5	18	17	14	10	6	6	9	4	β = 0.5	11	10	8	11	3	3	3	7
	λ = 0.75	13	15	13	10	8	9	8	8	β = 0.75	12	16	11	11	3	4	3	6
	λ = 1	15	21	16	9	12	12	8	7	β = 1	14	11	8	6	3	5	4	5

Table 3

 3

	(b)) and with the difficulty

Table 4 .

 4 Toy Problem: The average number of landmarks selected (i.e. the sparsity) according to κ, with λ = 0.15 and β = 0.75 from SSDASF.

	Rotation angle	20 • 30 • 40 • 50 • 60 • 70 • 80 • 90 •
	κ = 0	24	22	16	18	11	8	17	8
	κ = 0.01	18	19	11	17	15	7	15	6
	κ = 0.1	22	18	13	10	11	9	4	11
	κ = 0.25	21	19	14	17	10	17	6	11
	κ = 0.5	19	18	19	11	12	8	13	10
	κ = 0.75	19	17	16	20	9	14	8	14
	κ = 0.8	22	20	10	16	12	14	9	16
	κ = 0.85	24	18	24	18	7	14	13	11
	κ = 0.9	24	21	18	23	14	12	9	10
	κ = 0.95	21	23	20	14	11	12	16	14
	κ = 0.99	7	7	7	7	12	9	11	7
	SSDASF: Influence of Combining Source and Target Labeled Learning Sample

  Table 5 the average execution time of each algorithm with fixed

		1
	Correct Classification	0.6 0.7 0.8 0.9
							Without Source Data
		0.5
		2	4	6	8	10	12	14	16	18	20
					Labeled Target Examples
		20 deg.			40 deg.		60 deg.	80 deg.
		30 deg.			50 deg.		70 deg.	90 deg.

Table 6 .

 6 Image Classification: The F-measure results for each concept (CONC.) on the PascalVOC test target domains according to the F-measure. AVG. is the average result.

	8

Table 7 .

 7 Image Classification: The average computational costs of each method measured as a ratio of the baseline SF.

	CONC.	bird	boat	bottle *	bus	car	cat	chair	cycle	cow diningtable
	SVM	5.5	0.8	2.1	2	1.3	9	3.4	8.8	0.3	1.9
	SF	1	1	1	1	1	1	1	1	1	1
	TSVM	18.2	4.1	8	6	3.3	11.4	8.7	28.6	2.8	5.7
	DASVM	4254	1440	3870	4860	1470	3428	2674	2828	900	1300
		4.9	6	6	9	7.3	5	3.8	6.8	2.7	2.1
	CONC.	dog *	horse monitor motorbike person * plane	plant	sheep	sofa	train	AVG.
	SVM	1.4	3.7	4.2	5	2.1	2.9	0.5	1.4	2	1.4	2 .2
	SF	1	1	1	1	1	1	1	1	1	1	1
	TSVM	1.9	7.4	12.2	5.9	4.5	10	0.7	4.4	15.9	10.1	8 .49
	DASVM	340	3553	4230	3060	675	1710	3900	1836	1912	1550	2489
	DASF	6.1	5.8	8.8	5.5	5.6	5	3.7	3.6	5.7	5.5	5 .4

Table 8 .

 8 Image Classification: The F-measure results obtained for each concept on the TrecVid target domains according to the F-measure. AVERAGE is the average result.

		CONCEPT	boat *	bus *	car *	monitor *	person *	plane *	AVERAGE
		SVM	0.56	0.25	0.43	0.19	0.52	0.32	0 .38
		SV	351	476	1096	698	951	428	667
		SF	0.49	0.46	0.50	0.34	0.45	0.54	0 .46
		LAND.	214	224	176	246	226	178	211
		TSVM	0.56	0.48	0.52	0.37	0.46	0.61	0 .50
		SV	498	535	631	741	1024	259	615
		DASVM	0.52	0.46	0.55	0.30	0.54	0.52	0 .48
		SV	202	222	627	523	274	450	383
		DASF	0.57	0.49	0.55	0.42	0.57	0.66	0 .54
		LAND.	120	130	254	151	19	7	113
		0.7
		0.6
	F-measure	0.5
		0.4
		0.3
		0	0.25	0.5	0.75		1
				Lambda
		Boat		Car	Person
		Bus		Monitor	Plane

  Parsimonious Unsupervised and Semi-Supervised Domain Adaptation with Good Similarity Functions 35

		0.7										0.7										0.7
		0.6										0.6										0.6
		0.5										0.5										0.5
	F-measure	0.3 0.4									F-measure	0.3 0.4									F-measure	0.3 0.4
		0.2										0.2										0.2
		0.1										0.1										0.1
		0										0										0
		2	4	6	8	10	12	14	16	18	20	2	4	6	8	10	12	14	16	18	20	2	4	6	8	10	12	14	16	18	20
					Labeled Target Examples							Labeled Target Examples							Labeled Target Examples
					Boat			Without source data					Bus		Without Source Data					Car		Without Source Data
		0.7										0.7										0.7
		0.6										0.6										0.6
		0.5										0.5										0.5
	F-measure	0.3 0.4									F-measure	0.3 0.4									F-measure	0.3 0.4
		0.2										0.2										0.2
		0.1										0.1										0.1
		0										0										0
		2	4	6	8	10	12	14	16	18	20	2	4	6	8	10	12	14	16	18	20	2	4	6	8	10	12	14	16	18	20
					Labeled Target Examples							Labeled Target Examples							Labeled Target Examples
				Monitor		Without Source Data				Person		Without Source Data					Plane		Without Source Data

Table 9 .

 9 Image Classification: The average computational costs of each method measured as a ratio of the baseline SF.

	CONCEPT	boat *	bus *	car *	monitor *	person *	plane *	AVERAGE
	SVM	0.8	2	1.3	4.2	2.1	2.9	2 .2
	SF	1	1	1	1	1	1	1
	TSVM	5	7	3.6	13.2	5.5	11	7 .5
	DASVM	3870	720	2370	2790	300	540	1765
	DASFit 1 DASF	1 9.5	1 10	1 8	1 23	1 3.4	1 10.5	1 10 .7
	SSDASFit 1 SSDASF	4.4 29.8	2 14.4	0.4 6.6	1 29	0.6 3.4	1.5 13	1 .6 16

Note that surveys can be found in(Jiang,

[START_REF] Jiang | A literature survey on domain adaptation of statistical classifiers[END_REF][START_REF] Quionero-Candela | Dataset Shift in Machine Learning[END_REF].

Meaning that X can be partitioned into Mη subsets, Mη finite, cf[START_REF] Xu | Robustness and generalization[END_REF] for more details.

The DA bound: ∀h ∈ H, err T (h) ≤ err S (h) + 1 2 d H∆H (D S , D T ) + ν.

This intractability has been confirmed empirically: In such a case, none of the experiments have led to a result in a reasonable amount of time.

In our experiments, we take arbitrarily N ≤ 30.

i.e. those with a non-null weight α j .

Eventually normalized to ensure K l+1 ∈ [-1, 1].

This point is discussed in the conclusion.

For example, a cost of 0.5 means that the algorithms need a running time half as long and a cost of 2 means a duration of twice as long.

Acknowledgments

The authors are very grateful to Marc Sebban for his many useful remarks that were the basis of a significant improvement of the paper.

We would like to acknowledge support for this project from the french project VideoSense ANR-09-CORD-026 of the ANR and the IST Programme of the European Community, under the PASCAL2 Network of Excellence, IST-2007-216886.

parameters. We take the SF-classifier learning as the baseline, which with SVM is the fastest. Firstly, we can observe that the first iteration of DASF (DASF it1 ) needs the same time as the usual SF algorithm. The additional cost due to the iterations of DASF is reasonable since for at most 10 iterations, it is between 4 and 8 times longer than DASF it1 . Secondly, our method DASF is faster than DASVM. It takes between almost one-third as long. Nevertheless, TSVM is quicker than DASF, probably due to the cost of computing the pairs for DASF. Finally, we observe for the three adaptive methods -TSVM, DASVM and DASF -that the lowest costs are obtained for 40 • to 70 • rotations.

We have not reported the costs for SSDASF, since the execution times of SSDASF and DASF for these easy tasks are almost the same.

Image Classification Setup

In this section, we experiment our approach on PascalVOC 2007 [START_REF] Everingham | The PASCAL visual object classes challenge 2007 (VOC2007) results[END_REF]) and TrecVid 2007[START_REF] Smeaton | High-Level Feature Detection from Video in TRECVid: a 5-Year Retrospective of Achievements[END_REF] corpora. The goal is to identify visual objects and scenes in images and videos. TrecVid corpus is constituted of images extracted from videos and can be seen as an image corpus. Visual features used for those experiments are based on the prediction scores of 15 "intermediate" visual concepts (ANIMAL, BUILDING, CAR, CARTOON, EXPLOSION-FIRE, FLAG-US, GREENERY, MAPS, ROAD, SEA, SKIN FACE, SKY, SNOW, SPORTS, STUDIO SETTING) which have been successfully used in previous TrecVid evaluations. Each of those intermediate concepts are detected using SVM-classifiers from color moments and edge orientations on 260 blocs of 32×32 pixels (data dimension is 3900) according to [START_REF] Ayache | Image and video indexing using networks of operators[END_REF] (Figure 11 is an illustration).

We made two experiments. Section 7.4.1 deals with the first one where the objective is to evaluate the DA capability of our algorithm on close domains. The Section 7.4.2 presents the second experiment which stands in an usual DA setup with potentially very different domains.

Adaptation Capability when the Label Ratio is Different Between Source and Target Sample

Setup

The PascalVOC benchmark is constituted of 5000 training images, 5000 test images and a list of 20 concepts to identify. Train and test sets are in fact relatively close ( dH∆H 0.05) and a DA step is not necessary. We rather propose to evaluate the DA capability of our algorithm when the ratio +/is different between the source and target samples, leading to a harder DA task. Our objective is not to provide a solution in such a situation (specific methods already exist like [START_REF] Seah | Predictive distribution matching svm for multi-domain learning[END_REF]), but rather to evaluate if our method can avoid negative transfer and improve the accuracy over the test set. Since the two domains are close, we only evaluate our unsupervised approach DASF (adding labeled target examples will actually correspond to adding more labeled source instances).

In general, the ratio between positive and negative examples (ratio +/-) is less than 10% in this dataset. For each concept, we generated a source sample constituted of all the training positive examples and negative examples independently drawn such that the ratio +/is 1 3 / 2 3 . We keep the original test set as the target sample. We applied the five methods previously described for learning a binary classifier for each concept. Due to the relative small ratio +/in the target sample, we evaluate the performances according to the well known F-measure defined by 2.P recision.Recall P recision+Recall .

Results

The results are reported in Table 6. First, TSVM and DASVM perform badly, probably because of the difference between target and source ratios +/which cannot be esti-

Appendix Proof of Theorem 8

In order to prove this theorem, we first need two technical lemmas from Ben-David et al. (2010a) able to link err T (h), err κ (h) and ê rr κ (h).

Lemma 4 (Ben-David et al. (2010a)). Let h be an hypothesis in a class H, then,

Lemma 5 (Ben-David et al. (2010a)). Let h be a fixed hypothesis, if a random sample of size d l is generated by drawing i.i.d. θd l points from P T and (1 -θ)d l points from P S , then for any δ > 0, with probability at least 1 -δ (over the choice of the samples),

Then, in order to take into account our regularizers, we use again the framework of robustness. For readability reasons, we recall the generalization bound of [START_REF] Xu | Robustness and generalization[END_REF] for robust algorithms introduced previously in Section 4.2.2.

Theorem 4 [START_REF] Xu | Robustness and generalization[END_REF]). If a learning sample LS = {(x i , y i )} d l i=1 is drawn i.i.d. from a distribution P and if an algorithm A is (M, (LS)) robust, then for any δ > 0, with probability at least 1 -δ,

where err P (A LS ) and ê rr P (A LS ) are respectively the generalization and the empirical errors over P of the model A LS learned from LS, L(•, •) being upper bounded by L U P .

By combining source and target labels, this theorem cannot be used directly on err κ since the learning sample LS = (LS S , LS T ) contains examples coming from two different distributions. However, by definition of err κ and ê rr κ , the corresponding error on the source domain and on the target one are evaluated independently on each domain. A solution is then to apply the robustness theorem on each domain error and then to consider the convex combination of the two bounds with respect to κ.

Assuming a normalization such that L U P = 1 in our case, we can now prove Theorem 8.