A Barachant

S Bonnet

M Congedo

C Jutten

A Brain-Switch using Riemannian Geometry

This paper addresses the issue of asynchronous brain-switch. The detection of a specific brain pattern from the ongoing EEG activity is achieved by using the Riemannian geometry, which offers an interesting framework for EEG mental task classification, and is based on the fact that spatial covariance matrices obtained on short-time EEG segments contain all the desired information. Such a brain-switch is valuable as it is easy to set up and robust to artefacts. The performances are evaluated offline using EEG recordings collected on 6 subjects in our laboratory. The results show a good precision (Positive Predictive Value) of 92% with a sensitivity (True Positive Rate) of 91%.

Introduction

Asynchronous BCIs are of major interest in order to set-up practical BCI system in real-life conditions. Such BCI attempts to detect predefined brain pattern during operation and the user can send a command at any time. This is the most natural way but also the more difficult since one has to discriminate specific brain patterns with respect to the ongoing brain activity. A particular case of asynchronous BCI is called a brain-switch when only one brain state is to be detected in the ongoing brain activity [START_REF] Mason | A brain-controlled switch for asynchronous control applications[END_REF]. A brain-switch could allow the user to indicate the system s/he is ready for an action [START_REF] Pfurtscheller | The hybrid BCI[END_REF] or simply sends a binary command very much like an electrical switch. The false rate should be kept as low as possible to let the communication system silent, when the user does not intend to communicate. Different brain-switches have been proposed based on different sources of BCI control, such as the post-imagery beta ERS [START_REF] Müller-Putz | Fast set-up asynchronous brain-switch based on detection of foot motor imagery in 1-channel EEG[END_REF].

Motor Imagery (MI) is a mental simulation or rehearsal of a movement without motor output, which results in the activation of dedicated cortical areas (somatosensory cortex) in given frequency bands. MI is often used in BCI applications since the brain patterns and areas involved are well known. Moreover, from the user point of view, it is also a natural way to interact. It has been observed that spatial covariance matrices are central to the detection process and that the respect of their topology using Riemannian geometry can improve the problem at hand. In this paper we propose to build a brain-switch based on direct manipulations of spatial covariance matrices using concepts of distance and geometric mean using a Riemannian metric. The classifier is first trained using a self-paced motor imagery BCI system and then evaluated offline on test recording which follows the same paradigm.

Methods

In the proposed approach, spatial covariance matrices are the features of interest for the brainswitch detection task and they are manipulated by doing computations within the manifold of symmetric positive-definite (SPD) matrices. The brain-switch is implemented on a sliding trial manner, where each trial is detected as a (specific) brain pattern and the result is aggregated within time to activate or not the brain-switch.

Riemannian Metric

Let X ∈ R C×Nt be a short-time segment of EEG signal, which corresponds to a trial of motor imagery: C is the number of channels and N t is the number of samples in a trial. We assume further that X has been band-pass filtered in a pre-processing step, and that the spatial covariance matrix of the trial is estimated by the Sample Covariance Matrix (SCM) :

P = 1 N t -1 XX T (1)
A key observation is that SCMs are symmetric positive-definite (SPD) matrices that belong to the manifold P (C). Using Riemannian geometry, it is possible to define precisely the distance between any two SPD matrices P 1 and P 2 as :

δ R (P 1 , P 2 ) = C c=1 log 2 λ c 1/2 (2)
with {λ c , c = 1 . . . C} the eigenvalues of P -1 1 P 2 [START_REF] Förstner | A metric for covariance matrices[END_REF]. This formula has some reminiscence with the common spatial pattern technique as demonstrated in [START_REF] Barachant | Common spatial pattern revisited by riemannian geometry[END_REF]. If we are now given a set of M covariance matrices, it is possible to estimate the (Frechet) mean of this set using :

G (P 1 , . . . , P M ) = arg min P∈P (C) M m=1 δ 2 R (P, P m ) (3)
Although no closed-form expression does exist, this (geometric) mean can be computed efficiently using an iterative algorithm [START_REF] Barachant | Riemannian geometry applied to BCI classification[END_REF].

Brain-switch based on covariance matrices

The estimate of the covariance matrix of the band-pass filtered EEG signal in the specific condition y = s, (e.g., left-hand or right-hand movement imagination) can be readily obtained using the previous section as :

G s = G(P i , i |y i = s)
It can be expected that all these points will be clustered in a very delimited portion of the manifold P (C). This allows us to define a region of interest (ROI) in the manifold based on the intra-class covariance matrix and a threshold distance. The ROI is parameterized by the equation : Ω = {P | δ R (P, G s ) < ǫ} where ǫ = m + 3s with m and s denote respectively the median and standard deviation of the point-to-center distances {δ R (P i , G s ), i |y i = s}.

This simple criterion is very efficient to remove large amplitude EEG artifacts from the analysis. However, it may not be not specific enough during a brain-switch operation mode. To improve the specificity of the detection, a second step consists in estimating the geometric mean G s = G(P i , i |y i = s and δ R (P i , G s ) < ǫ) of the covariance matrices corresponding to the unspecific activity restricted to the computed ROI. By definition, the unspecific activity class is composed by all the activities excluding the specific one. The restriction to the ROI reduces the diversity of the unspecific activity class and thus allows the estimation of the corresponding mean covariance matrix. Again a very simple criterion is to decide whether a test trial belongs to the class of the closest mean in terms of Riemannian distance. The whole algorithm can be described as follows :

y = s if δ R (P, G s ) < ǫ and δ R (P, G s ) < δ R (P, G s) s otherwise (4)
This classification output is then integrated along time to improve robustness. As a consequence, the brain-switch will be triggered ON when the specific activity is detected continuously for a given period of time T s , typically 1 s. After being triggered, the brain-switch remains halted until the unspecific activity is detected continuously for another period of time T s, typically 1s.

Results

The brain-switch precision and sensitivity is now evaluated using EEG recordings collected on 6 subjects in our laboratory. These datasets have been recorded before the development of the algorithm presented in this paper, with an adaptive implementation of spatial filtering by CSP and classification by LDA. For this reason, the results presented hereby are related to offline processing of these measurements. For each subject, 16 active electrodes (from g.tec) are disposed on the whole scalp according to the 10/20 system ( Fpz F7 F3 Fz F4 F8 T7 C3 Cz C4 T8 P7 P3 Pz P4 P8). A sampling frequency of 512 Hz and a general band-pass filter between 8 and 30 Hz were used. The training stage consists in a self-paced motor imagery paradigm and lasts up to 15 min. The user is sited in front of a computer screen and a continuous visual feedback is provided. It consists in a blue vertical bar which evolves jointly with the detection output. The user strokes a key to indicate the system that s/he wants to begin a specific mental task. Each mental task is performed until the switch is triggered ON, with a maximal duration of 10 s. The algorithms are continuously adapted. The testing phase of 5 min is done on a self-paced operation mode similarly to the training stage, but without the adaptation of algorithms. It is important to notice that the unspecific activity corresponds to a concentrated resting state and does not reflect the whole diversity of the unspecific activity, which can be seen during long-term EEG recording.

Figure 1 shows the manifold of spatial covariance matrices in case of two channels. Each point represents an 2 × 2 SPD matrices estimated on a sliding windows of 1 second, either in specific condition (red points) or unspecific one (blue points). We note that the matrices belonging to the specific activity class lie in a compact area while the other ones are spread over a larger area. Moreover, we see that the points corresponding to the specific activity are close to the boundary of the manifold which is a cone. Such locations correspond to high correlations between the two chosen electrodes.

Figure 2 shows the class-dependent distribution of Riemannian distances from the center of the ROI during the learning stage for user E. In this example, 96.5% of the trials corresponding to the specific activity are within the ROI while 20% of the trials corresponding to the unspecific activity are outside the ROI. A visual inspection of the signal shows that most of rejected trials correspond to artifacts.

Figure 3 shows the classification process on the test data for user E. The threshold of detection given Eq. 4 is represented by the dashed line. In this example, 85% of unspecific activities and 72% of specific activities have been correctly classified.

Figure 4 shows the temporal output of the brain-switch for 10 realisations of specific mental tasks of various length after the integration along time. During this period, only one event is a false positive. We can also see that the switch triggered ON at the beginning of most trials, shows the reactivity of the brain-switch.

Finally, the results for the 6 subjects are given in Table 1. The average performance is about 91% for both P P V (Positive Predictive Value) and T P R (True Positive Rate) with 0.4 F P (False Positive) per minute, that is similar to the state of the art [START_REF] Müller-Putz | Fast set-up asynchronous brain-switch based on detection of foot motor imagery in 1-channel EEG[END_REF].

Conclusions

The presented method is easy to set up in the EEG experiments. No parameters are needed to be set, and the large amplitude artifacts are natively handled. Offline results appear promising to go beyond the state-of-the-art. In addition, the training stage relies only on the estimation of class-related covariance matrices. The precision (PPV) could be improved by increasing the time T s in return of losing sensitivity (TPR). Such an optimisation of timing should be done according to the application. This algorithm will be used in our next brain-switch experiments.

Figure 1 :

 1 Figure 1: Covariance matrices positions for user E, channel Fz and C4. Training stage

Figure 2 :

 2 Figure 2: Distributions of the distance to the center of the ROI δ R (G s , P i ) for the training data, user E.

Figure

  Figure 3: Classification of test data, user E

Table 1 :

 1 3: Classification of test data, user E Results obtained offline for the 6 users.

									True label Switch trigger		U ser PPV TPR TP/min FP/min
												A	100	84	4.8	0
												E	94	100	6.4	0.4
												G	94	100	6.8	0.4
												I	80	64	2.6	0.6
	100	110	120	130	140	150 Time (s)	160	170	180	190	200	J	83	100	5.2	1
												M	100	100	7.2	0
	Figure 4: Temporal output of the brain-	mean 91.8 91.3	5.5	0.4
	switch for test data, user E


Florence Despetis

Nadjette Bengourna

Berangere Lartigue

Sandra Spagnol

Nathalie Olivi-Tran

Three dimensional reconstruction of aerogels from TEM images

The knowledge of the internal structure of porous materials is of main importance to compute their physical properties. We focus here on base catalyzed and colloidal silica aerogels, which are fractal materials and we use an original method for the reconstruction of these aerogels from TEM images. The method used is iterative and leads to the same fractal dimension as the real material, computed from the internal two point correlation function.

INTRODUCTION

Aerogels are light porous and often fractal materials. Presently, they are used for the building insulation, and in the past years they were synthesized in high purity or doped silica glasses, Cerenkov counters... Therefore, the modeling of the structure of such materials has been of main importance in order to understand their physical properties [1].

In the end of the 90's , the works of Torquato et al [2][3][4] and Levitz et al. [5,6] resulted in the statistical modeling of porous materials from TEM (Transmission Electronic Microscopy). Yet, their studies are mainly focused on the modeling of the porosity of the material and not of the distribution of matter. In fact, their modeling is statistical or half statistical (from 2D images: cuts) but conserves the physical properties of the whole material.

More recently several authors also modeled porous materials such as sandstones, ultrafiltration cakes,etc. [7][8][9] . These reconstructions remain statistical and no research has addressed fractal materials.

Here, our method allows us to model the structures of three kinds of silica aerogels (two base catalyzed silica aerogels of different densities and one colloidal aerogel) directly from their TEM (Transmisson Electron Microscopy). This is an alternative method to model base catalyzed aerogels [10,11]. We prove, after the reconstruction (first stage), by calculating the two point correlation function of the matter distribution inside the sample that the fractal dimension D of the sample and of the numerical reconstructed model are the same. The question whether the reconstruction is almost quantitative or remains statistical is discussed at the end of this paper taking account the pore distribution (second stage).

EXPERIMENTAL PROCESS

The synthesis of base catalyzed aerogels is well known by now [START_REF] Brinker | Sol gel science: The Physics and Chemistry of Sol-Gel processing[END_REF]. We will recall here the main chemical characteristics for the preparation of our aerogels samples (TEOS issued and Ludox issued and base catalyzed). Three aerogels were synthesized using two different methods. Samples B35 and B100 were obtained from standard hydrolysis and polycondensation reactions of tetramethylorthosilicate (T M OS) diluted in ethanol. They are labelled B for basic hydrolysis conditions is performed by adding hydrochloric acid aqueous solution. After the alcohol supercritical drying treatment the density of aerogels is respectively 0.35g/cm 3 , 0.1g/cm 3 and 0.475g/cm 3 with an accuracy of ±0.05g/cm 3 .

For the TEM imaging, aerogels were crushed in ethanol and suspension put down on carbon film supported by a 300 mesh copper grid. In the TEM images, the darkness corresponds to the quantity of matter at the corresponding location on the image. Only the samples with the lowest thickness lead to an image which could be exploited. Indeed, for large thicknesses, the electronic flux lead to dark images with no contrast regarding different thickness within the sample itself.

We have to add that we used only base catalyzed (B35 and B100) and colloidal (LS) aerogels because we observed no structural evolution during the samples expositions to the electronic flux of the TEM: the TEM images were focused and did not evolve neither in position nor in contrast. In contrast, we tried to analyze by TEM images the structure of acid catalyzed and neutral catalyzed silica aerogels, but the TEM images were out of focus and the samples were moving under the electronic flux, meaning that there was a rearrangement of matter within the sample. The fact that colloidal and base catalyzed silica aerogels have a minimal characteristic thickness of their branches (particles) larger than the other cited types of silica aerogels explains that the samples studied here are stable even during exposure to an electronic flux.

NUMERICAL PROCESS

Image processing

We analyzed the TEM image of the base catalyzed aerogel. The first step is to mesh the photography for which we use the scale of the image and the mean size of the particles composing the aerogel on the TEM photography.

We choose a section of the image where the particles do not overlap too much (i.e. the depth of the sample is not too large) and we slide the boundaries of the image section so that at least one particle per boundary touches it. Once we have cut this section of the photography, we mesh it, each square of the mesh having an edge lower or equal to the size of one particle. Now we have a square meshed image of part of the aerogel. As the original image is in the TIFF format, we transform it in another format (ASCII PNM) where each mesh is associated to an integer: this number gives the greyscale of the mesh (from 0 to 255). Knowing that each mesh corresponds approximately to one particle or more particles having the same x and y coordinates, we are able to deduce from the greyscale the number of particles which are on the same vertical line on the same mesh. In our model, we made the hypothesis that two particles at most are on the same vertical line in the z direction (depth). Therefore , we set a threshold in the greyscale: if a mesh has a greyscale below the threshold it corresponds to only one voxel (pixel in 3d) with a z coordinate corresponding to the greyscale but if it is above the threshold, it corresponds to two voxels on the same vertical line where the depth of each voxel corresponds to respectively 1/3 and 2/3 of its greyscale (the darker the deeper).

Analysis of the three-dimensional structure via fractal laws

To obtain a structure which has the same fractal characteristics as the real aerogels, we used an iterative process. The point here is to adjust the threshold in the greyscale in order, first, to remove the background of the TEM image and second, to obtain a fractal dimension enclosed between 1.8 and 2 (fractal dimension of the experimental samples [START_REF] Brinker | Sol gel science: The Physics and Chemistry of Sol-Gel processing[END_REF].

We start by considering the two points correlation function for the voxels

g(r) =< n(r 0 )n(r 0 + r) > 0 (1)
This function defines how many voxels can be found at a distance r from a voxel at r 0 .

For random fractals, one may also average the two point correlation functions over different realizations of the whole pattern. We made this last and we averaged the results over three sections coming from three different TEM images of the same original sample. By integrating equation (1), we obtain a relation between average volume (i.e. the aera of the TEM image multiplied by the computed depth in voxels) and length scale. For a homogeneous fractal of fractal dimension D this is :

N (R) = R 0 dr < n(r 0 )n(r 0 + r) > 0 ∝ R D (2)
So by computing the two points correlation function and by integrating it, we can obtain the fractal dimension D of the three dimensional reconstructed structure. If the fractal dimension D is not in the correct range, we lower or increase the threshold (which modifies the depth and also the average volume). This allows us to verify that our reconstruction is statistically exact.

RESULTS AND DISCUSSION

Figure 1 is the Small Angle XRay Scattering (SAXS) graph for our B35 and B100 samples. The slope of the fractal domain (between the arrows) gives the fractal dimension D = 1.8. For the LS475 sample, we redirect the reader to ref. [START_REF] Brinker | Sol gel science: The Physics and Chemistry of Sol-Gel processing[END_REF]. We present the TEM images for three different types of aerogels: B35, B100 and LS475. These TEM images are presented in figures 2,3 and 4.

Figure 5 (left) is an example of the section (see the black square in fig. 3) of the preceding images that we chose to analyze (in this case it is the base catalyzed aerogel of density 0.100g.cm -3 : B100). The corresponding meshed image is presented in figure 5 (right). One may see that each mesh corresponds to roughly one particle in size and location except that, as meshes are placed on-lattice, it may occur that one real particle may be shared by two meshes.

It is clear from figure 5 that there is a greyscale. After analyzing this greyscale, as presented in section II, we obtain a reconstructed image of a small piece of aerogel in figure 6. The reconstructed image has a low depth as explained in section II.

As it is difficult to obtain the same fractal character as the real aerogel from a reconstructed image, we computed the two points correlation functions (as shown in previous section) on the coordinates of each reconstructed particles (i.e. the coordinates corresponding to the voxels which represent the particles). Figure 7 shows an example the two point correlation functions for the three types of aerogels that we used.

The fractal dimensions obtained from these correlation functions and after averaging over three different results from three different TEM images are:

• Base catalyzed aerogels of 0.035g.cm -3 ± 0.005g.cm -3 density (B35): the computed fractal dimension D = 1.9 ± 0.5

• Base catalyzed aerogels of 0.100g.cm -3 ± 0.005g.cm -3 density (B100): the computed fractal dimension D = 1.8 ± 0.5

• Ludox base catalyzed aerogels of 0.450g.cm -3 ± 0.005g.cm -3 (LS45): the computed fractal dimension D = 1.85 ± 0.5

It is worth noticing that, as we use the coordinates of the voxels to compute the two point correlation function, we may directly compare it with the pore chord distribution function.

As a hypothesis, this implies that the surface of the pores is smooth and that their are no necks between the particles (which is obviously not the case here, but this is a hypothesis)

. Following Levitz [START_REF] Levitz | [END_REF]14], the pore chord distribution may be defined as the number of segments linking two particles composing the aerogel as a function of the segment length r.

If the material has a fractal distribution of mass (which is the case for our materials), the pore chord distribution scales as [START_REF] Levitz | [END_REF][14][15][16][17]:

f (R) ∝ 1 R D-1 (3)
As we used the fractal dimensions D of our samples as a parameter, it is easy to obtain the pore chord distribution. This may simply lead to the permeability of our samples [START_REF] Levitz | [END_REF][14][15][16][17].

We have to say that the permeability of such materials cannot be found in literature, so we cannot compare our numerical results to experimental data.

As a conclusion to the discussion, we may say that no one made an exact reconstruction of a fractal material. Our reconstruction method is half statistical . We may say that:

• the greyscale gives the number of particles on the same vertical line and their statistical depths

• we used no dilation of the depths

• the previous point shows that there is only an indeterminacy on the z direction of the voxel coordinates

CONCLUSION

We used a new method to reconstruct base catalyzed and colloidal types of silica aerogels which may be used for other fractal materials. Here, we did not focus on the pore network although it is possible (as we wrote it) to compare with the pore distribution. Our method allows us to obtain directly the distribution of matter from a TEM image.

We made TEM images of base catalyzed and colloidal silica. Using an iterative numerical technique on these images taking account of the fractal dimension of the experimental samples (well known in the literature) we obtained three dimensional reconstructed samples of our silica aerogels. This opens new possibilities to compute the internal structure of fractal porous materials and therefore to model their physical properties. 1)) and integrated (corresponding to eq.( 2)) two points correlation functions where the distances are in pixels (edge of a voxel). Upper graph: B35, Middle graph: B100, Bottom graph: LS475

FIG. 1 .

 1 FIG. 1. Small Angle XRay Scattering graph for B35 and B100 aerogels corresponding to our samples. The slope of the fractal domain gives the fractal dimension D = 1.8. For the LS475(Ludox) sample see ref.[START_REF] Brinker | Sol gel science: The Physics and Chemistry of Sol-Gel processing[END_REF]

FIG. 7 .

 7 FIG.7. Example of rough (corresponding to eq. (1)) and integrated (corresponding to eq.(2)) two

FIG. 2. TEM image of a B35 aerogel

FIG. 3. TEM image of a B100 aerogel


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

Sparse Domain Adaptation in Projection Spaces based on Good Similarity Functions

Keywords: Machine Learning, Transfer Learning, Domain Adaptation, Binary Classification, Similarity Functions

We address the problem of domain adaptation for binary classification which arises when the distributions generating the source learning data and target test data are somewhat different. We consider the challenging case where no target labeled data is available. From a theoretical standpoint, a classifier has better generalization guarantees when the two domain marginal distributions are close. We study a new direction based on a recent framework of Balcan et al. allowing to learn linear classifiers in an explicit projection space based on similarity functions that may be not symmetric and not positive semi-definite. We propose a general method for learning a good classifier on target data with generalization guarantees and we improve its efficiency thanks to an iterative procedure by reweighting the similarity function -compatible with Balcan et al. framework -to move closer the two distributions in a new projection space. Hyperparameters and 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 evaluate it on a synthetic problem and on real image annotation task.

I. INTRODUCTION

In machine learning, many approaches for learning binary classifiers are built under the assumption that learning data are representative of test data. While this assumption can be relevant for some tasks, it is not always true for every applications. To overcome this drawback, some transfer learning methods [START_REF] Pan | A survey on transfer learning[END_REF] have been proposed to adapt a model from a source domain to a target one. In this paper, we address the problem of domain adaptation (DA) where the 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] Quionero-Candela | Dataset Shift in Machine Learning[END_REF]. DA is an important issue for the efficient application of machine learning methods and many approaches have been proposed in the literature. While some of them proposed to use a few labeled data from the target domain [START_REF] Ben-David | A theory of learning from different domains[END_REF], [START_REF] Bergamo | Exploiting weakly-labeled web images to improve object classification: a domain adaptation approach[END_REF], [START_REF] Daumé | Frustratingly easy domain adaptation[END_REF], [START_REF] Schweikert | An empirical analysis of domain adaptation algorithms for genomic sequence analysis[END_REF], we consider the more challenging problem where no target labeled data is available.

Some theoretical DA frameworks [START_REF] Ben-David | A theory of learning from different domains[END_REF], [START_REF] Mansour | Domain adaptation: Learning bounds and algorithms[END_REF] indicate that a classifier learned only from the labeled source data can perform well on the target data if the source and target marginal distributions are relatively close, under the assumption that the two domains are related. This suggests a natural approach for a successful DA: move closer the source and target distributions while keeping a good classifier on the source domain. Following this idea, several methods -based on different hypothesis or discrepancy measures -have been proposed for reweighting the learning data [START_REF] Mansour | Domain adaptation: Learning bounds and algorithms[END_REF], [START_REF] Huang | Correcting sample selection bias by unlabeled data[END_REF], [START_REF] Sugiyama | Direct importance estimation with model selection and its application to covariate shift adaptation[END_REF]. Bruzzone et al. [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 removes source labeled points and adds self labeled target points to the learning sample. Another idea consists in finding a common relevant feature space where the two distributions are close [START_REF] Ben-David | A theory of learning from different domains[END_REF]. However, this principle relies mainly on heuristics specific to particular tasks.

In this article, we propose a new DA approach for binary classification, based on a recent framework of Balcan et al. [START_REF] Balcan | Improved guarantees for learning via similarity functions[END_REF], [START_REF]A theory of learning with similarity functions[END_REF] allowing to learn in an explicit projection space defined by good similarity functions that may be not symmetric nor positive semi-definite (PSD) i.e. that generalize kernel functions. They show that it is possible to learn a good linear classifier in a space defined by similarities to some relevant landmark examples. These landmarks offer a natural set of features to transfer. Our idea is to automatically modify this projection space for moving closer source and target points, leading to a good adaptation on the target domain. For this purpose, we present a general approach based on a regularizer focusing on landmark points close to both source and target examples. We formulate it in a 1-norm regularized linear program leading naturally to very sparse models. Our approach is then more flexible than SVM-based methods. Moreover, we propose an iterative process based on the absence of PSD and symmetric requirements to improve the tractability of the method. We evaluate it on a synthetic problem and on real image annotation corpora.

The paper is organized as follows. Section II introduces a classical DA theory [START_REF] Ben-David | A theory of learning from different domains[END_REF]. Section III deals with the framework of Balcan et al. [START_REF] Balcan | Improved guarantees for learning via similarity functions[END_REF]. Our approach is presented in Section IV and its iterative enhancement in Section V. Finally, the algorithm is experimentally evaluated in Section VI.

II. 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, we have a source domain represented by a distribution P S and a target domain represented by a somewhat different distribution P T . D S and D T are the respective marginal distributions over X. A learning algorithm is provided with a Labeled Source sample LS = {(x i , y i )} d l i=1 drawn i.i.d.

+ +++ + + + + + + + + -- - -- - - - ---
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 and zero otherwise. Finding the optimal hyperplane is NP-hard in general. However, an estimation 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, Mansour et al. [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∆Hdistance and the source domain expected error of a classifier are low (see Fig. 1). According to [START_REF] Ben-David | Impossibility theorems for domain adaptation[END_REF], minimizing these two terms appears necessary to ensure a good adaptation.

III. LEARNING WITH GOOD SIMILARITY FUNCTIONS

In this part, we present the framework proposed by Balcan et al. of similarity based binary linear classifiers. A similarity 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 PSD, to ensure learning in the implicit high dimensional space defined by the kernel. Due to the PSD requirement, considering kernels can be a strong limitation and defining a good kernel is a tricky task in general. Balcan et al. [START_REF] Balcan | Improved guarantees for learning via similarity functions[END_REF], [START_REF]A theory of learning with similarity functions[END_REF] consider a rather intuitive notion of a good similarity function that overcomes some of these limitations. We review it by beginning with their definition.

Definition 1 ([11]

). 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 set of reasonable points such that the following conditions hold:

(i) A 1probability mass of examples (x, y) satisfy

E (x ,y )∼P yy K(x, x )|R(x ) = 1 ≥ γ, (ii) Pr x [R(x ) = 1] ≥ τ .
From this definition, a large proportion of examples must be on average more similar, with respect to the margin γ, to the reasonable points of the same class than to the reasonable points of the opposite class (i). Moreover, at least a proportion τ of the examples should be reasonable (ii). Definition 1 includes all valid kernels as well as some non-PSD similarity functions and is thus a generalization of kernels [START_REF] Balcan | Improved guarantees for learning via similarity functions[END_REF], [START_REF]A theory of learning with similarity functions[END_REF]. In general the reasonable points are unknown a priori. Therefore, in the 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. 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 ) .
Let LS a set of d l labeled points, R a set of -enoughd u landmarks. Then, with a high probability, the induced distribution in the φ R -space has a low error separator with a margin relative to γ. Thus, one can efficiently find a separator α ∈ R du by solving the linear problem of (2) (based on the hinge loss presented in [START_REF] Balcan | Improved guarantees for learning via similarity functions[END_REF]).

min α= α1,..,α du 1 d l d l i=1   1 -y i du j=1 α j K(x i , x j )   + + λ α 1 , (2)
where [1-z] + = max(0, 1-z) is the hinge loss. The learned linear model is then denoted by g(x) = du j=1 α j K(x, x j ). This leads to a natural two steps algorithm for learning the classifier: select a random set of potential landmarks and then learn a binary classifier h(x) = sign[g(x)] in the space induced by the landmarks selected, i.e. those with α j =0. Note that when a φ R -space (of dim. d ) has been defined 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 . In the following, a linear classifier learned in this framework is called a SF classifier and for sake of simplicity we will denote H φ R by H and each similarity function is assumed to fulfill Definition 1.

IV. DOMAIN ADAPTATION WITH GOOD SIMILARITY FUNCTIONS

We now present our DA method based on learning with 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 distributions, (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., solving (2) involves to learn -only from the source domain -a good linear classifier in the explicit φ R -space 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 to move closer the domains by selecting landmarks that are both similar to the source and target examples. To achieve this goal, we propose to add a regularization term on α in [START_REF] Quionero-Candela | Dataset Shift in Machine Learning[END_REF]. 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. In the following, we denote by LS = {(x i , y i )} d l i=1 the labeled source sample drawn from P S (LS |X denoting the set {x i / (x i , y i ) ∈ LS} d l i=1 ), by R = {x j } du j=1 the landmark set and by T S the unlabeled target sample drawn from D T .

A. Optimization Problem

Solving (2) not only minimizes the expected source error but also defines a relevant projection space for the source domain, since landmarks 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, which will tend to decrease the distance between the marginal distributions. To define our regularizer, we have investigated the notion of algorithmic robustness proposed by Xu and Mannor [START_REF] Xu | Robustness and generalization[END_REF] (see Definition 2 in Section IV-B). 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 closed to a training point of the same label, the deviation between the losses of each point has to be low. They also introduce a notion of pseudorobustness where it is sufficient to fulfill the robustness property for only a subpart of the training sample. This result actually assumes that the test and training data are generated from the same distribution and is thus not valid in a DA scenario. However, the authors have conjectured that it would hold for DA by taking into account a divergence measure. Despite this drawback, we propose to follow this conjecture in defining an heuristic to move closer the source and target samples. According to this idea, the samples may be similar if for pairs (x s ,x t ) of close source and target instances of the same class, the deviation between the losses of x s and x t is low. This leads us to construct a term to minimize for decreasing this deviation. By considering the hinge loss of the formulation of (2), for any learned model g and any such pair (x s ,x t ) of the class y we obtain, let (a) = L(g, (x s , y)) -L(g, (x t , y))

(a) = 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, (a) ≤ du j=1 α j K(x s , x j ) -K(x s , x j ) (a) ≤ du j=1 α j K(x s , x j ) -K(x t , x j ) (a) ≤ ( 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. It is hard to select the best pairs a priori, especially without target labels. Considering all the possible pairs is clearly intractable and we suggest, in Section V-C, a solution to build our pairs of source-target points to be moved closer. Given this pair set C ST ⊂ LS |X × T S, we then propose to add the new regularization term of line (3) for each pair of C ST , weighted by a parameter β. This term tends to select the landmarks with similarities close to some source and target points. Let R be a set of d u candidate landmarks, our following global optimization (4) corresponds to (2) with the addition of our regularizer and can be easily formulated as a linear program.

min α F (α) = 1 d l d l i=1   1 -y i du j=1 α j K(x i , x j )   + + λ α 1 + β (xs,xt)∈C ST ( t φ R (x s ) -t φ R (x t )) diag(α) 1 . (4)

B. Sparsity Analysis and Generalization Bounds

We provide a theoretical sparsity analysis and generalization bounds of our method. We suppose (X, ρ) is a compact metric space and the similarity K is continuous in its first argument. We also make the following hypothesis on C ST ,

∀x j ∈ R, max (xs,xt)∈C ST |K(x s , x j ) -K(x t , x j )| > 0. (5)
Hypothesis [START_REF] Daumé | Frustratingly easy domain adaptation[END_REF] means that for each coordinate x j , there is at least one pair of points that brings an information with different coordinate values, which is not a strong restriction. We begin with an analysis of the learned model sparsity.

Lemma 2. For any λ > 0, β > 0, and any 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 α * is the optimal solution of (4), then α * 1 ≤ 1 βB R + λ .
Proof: See Appendix A. According to this lemma, the model sparsity depends on the parameters λ, β, and on the quantity B R which is related to the distance between the points in C ST . When the two domains are far from each other, i.e. the task is hard, B R tends to be high which can imply an increase of the sparsity.

We recall now the robustness definition and its associated theorem on the generalization ability of robust algorithms. Actually, this framework (Xu and Mannor [START_REF] Xu | Robustness and generalization[END_REF]) allows us to consider the regularizers in the generalization bound.

Definition 2 ([14]). Given a learning sample LS, an algo

- rithm A is (M, (LS)) robust if X × Y can be partitioned into M disjoint sets, denoted as {C i } M i=1 , such that ∀s ∈ LS, s, u ∈ C i ⇒ L(g, s) -L(g, u) ≤ (LS),
with g the model learned from LS, L the loss function of A.

Theorem 2 ([14]). If LS = {(x i , y i )} d l
i=1 is drawn i.i.d. from a distribution P and if the 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 and ê rr P are respectively the expected and the empirical errors over P , L being upper bounded by L U P .

We can prove that our method is robust on the source domain which leads to the following generalization bound for the expected source error.

Theorem 3. If LS = {(x i , y i )} d l i=1 is drawn i.i.d. from P S , then (4) is (2M η , Nη βB R +λ ) robust on the source domain P S , where N η = max xa,x b ∼D S ρ(xa,x b )≤η t φ R (x a )-t φ R (x b ) ∞ with η > 0
and M η is the η-covering number of X (see [START_REF] Xu | Robustness and generalization[END_REF] for more details). Thus 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: See Appendix B. We now derive a generalization bound for the expected target domain error directly from Theorems 1 and 3.

Theorem 4. 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 classifier, 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 ) + ν,
where ν is the joint error over the domains, d H∆H (D S , D T ) is the H∆H-distance between the marginal distribution.

The constant

Nη βB R +λ depends on our regularizers and on N η that can be obtained as small as wished by continuity of K.

C. Reverse Classifier and Validation

A crucial point is the choice of the hyperparameters of our method. We propose to follow the idea of TrCV from Zhong et al. [START_REF] Zhong | Cross validation framework to choose amongst models and datasets for transfer learning[END_REF]. However, this approach relies on valid kernels and some few target labels. Since we may consider non-PSD and non-symmetric similarity functions and no label on the target domain, we make a little adaptation. We use their concept of reverse validation based on a reverse classifier evaluated on the source domain (Fig. 2), but directly in the projection space found. The justification of this choice comes from the fact that if the domains are sufficiently close and related, then the reverse classifier must be also efficient on 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. Since we do not have any information on the target distribution we define the reverse classifier h r as the best SF classifier learned with (2), in the φ R -space, from the target sample {(x,h(x))} x∈T S self-labeled by the classifier h learned with (4). Given k-folds on the source sample (LS = ∪ k i=1 LS i ), we use k -1 labeled folds as labeled examples for learning h and we evaluate h r on the last k th fold. The 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 ). We finally consider the DA capability of the classifier as an empirical estimation of the last term ν of the bound of Theorem 1 defined by ν = ê rr S (h r )+ ê rr T (h r ), where ê rr T (h r ) being evaluated by cross-validation over the auto-labeled target sample. We then select the hyperparameters minimizing ν. Note that with this choice and the minimization of (4), we try to minimize the three terms of the bound of Theorem 1.

V. AN ITERATIVE REWEIGHTING: A WAY TO LIGHTEN

THE SEARCH OF THE PROJECTION SPACE Building the pair set C ST is a priori hard since we have no target label. Moreover, the set of relevant pairs allowing a good adaptation depends generally on the considered task and testing all the possible sets, with the reverse validation, is clearly intractable. To tackle this problem, we propose an iterative approach based on a selection of a limited number of pairs and a reweighting scheme of the similarities keeping close distributions. We finally present a stopping criterion based on the empirical estimation of the joint error.

A. Selecting the pairs of C ST

We propose to construct pairs from two subsets of the two samples 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 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 .
Using these two sets, we build C ST ⊂ U S ×U T as a bipartite matching by minimizing the euclidean distance in the φ R lspace:

(xs,xt)∈C ST t φ R l (x s ) -t φ R l (x t ) 2 2
. This is a way to infer pairs of close source-target points in the φ R l -space considered at iteration l. Limiting the subsets to small 1 N allows us to build efficiently this bipartite matching, which is not a too restrictive heuristic since the notion of pseudorobustness does not require to consider all the points.

B. A New Projection Space by Iterative Reweighting

The landmarks selected by solving (4), i.e. those with non null α j , define a projection space where the distributions tend to be close. We propose to re-use these α j to force the new space to move closer the distributions by reweighting 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 weighting 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 ) (eventually normalized to ensure K l+1 ∈ [-1, 1]). It can be seen as a kind of contraction of the space to keep the dH∆H 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 corresponds exactly to minimize their L 1 -distance in the φ R l+1 -space. Actually, 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 Fig. 3. We then iterate the process 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 (4) 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, which can be empirically estimated by evaluating and γ from Definition 1 on LS. In fact, we pay attention to keep only those that offer the best ( ,γ)-guarantees, ensuring a sufficiently good similarity. Note that a bad similarity would lead to a dramatic increase of the expected source error.

C. Stopping Criterion

We consider here the estimated joint error ν related to the adaptation capability in the current space. Controlling this term and its decreasing during the iterative process can provide a nice way to stop the algorithm. Following

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 ; Build C ST α l ← Solve our Problem 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 )
Section IV-C, at a given iteration l this term is defined by νl = ê rr S (h r l ) + ê rr T (h r l ). An increasing of νl between two iterations means that the new projection space found is no longer relevant and the current one must be preferred. Then, our process stops at iteration l when ν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.

VI. EXPERIMENTS

In this section, we evaluate our approach DASF on a synthetic toy problem and on a real image annotation task. The similarity function used is based on a Gaussian kernel. To obtain a non-symmetric and non-PSD similarity K * , we apply the following normalization from a Gaussian kernel K: given a set of landmarks R, for every

x j ∈ R, K * (., x j ) =              K(.,x j )-µ x j σ x j if -1≤ K(.,x j )-μ x j σx j ≤1, -1 if -1≥ K(.,x j )-μ x j σx j , 1 if K(.,x j )-μ x j σx j ≥1,
where μx j is the empirical mean of similarities to x j over LS |X ∪T S and σx j is the empirical unbiased estimate of the standard deviation. However, depending on the considered samples, K * does not always offer better ( ,γ,τ )-good guarantees than the Gaussian kernel. In the following, we only indicate the similarity which obtains the best results. Problems favouring K * are indicated with a * , as we will see they correspond generally to harder DA tasks. We compare DASF with a classical SVM learned only on 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 use a classical Gaussian kernel 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]. Parameters of DASVM and DASF are tuned according to a grid search. We also measure the behavior of a SF classifier trained only on the source domain. For DASF and SF, the landmarks are taken from the labeled source sample. Following (1), we assess the distance dH∆H between the marginal distributions by learning a SF classifier to separate source from target samples, a small value indicates close distributions while a larger value indicates a hard DA task.

A. Synthetic Toy Problem

As the source domain we consider a classical binary problem with two intertwinning moons, each class corresponding to one moon (Fig. 4). We then consider 8 different target domains by rotating anticlockwise the source domain according to 8 angles. The higher the angle is, the more difficult the problem becomes. For each domain, we generate . Two DASF executions. On the left with a 30 • rotation, on the right with a 50 • rotation. On the left y-axis is the error range, on the right y-axis the divergence range. 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 between the distributions, the joint error of the reverse classifier, the error on the target test sample of a SF classifier learning without DA as a baseline.

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. Each DA problem is repeated 10 times. The average accuracy of each method is reported on Tab. I. 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 in the initial φ R 0 -space and the final φ R f inal -space. We can make the following remarks. • DASF outperforms in average the other methods. It is significantly better for every task of angle greater than 20 • .

While the accuracy of TSVM and DASVM falls down from 60 • , DASF remains still competitive even when the difficulty increases. In this case, the normalized K * is preferred.

• The landmark number is significantly lower than the SV number, 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 distance between the domains is lower at the last iteration -between 1 and 9 -showing our iterative approach is effectively able to quickly move closer the distributions. As evoked before, DASF tends to build a small projection space for hard problems, probably to have sufficiently close domains, but this may imply a loss of expressiveness. Fig. 5 shows two DASF executions on two DA problems. For these cases, the dH∆H distance decreases significantly in comparison with iteration 1. DASF stops when the empirical joint error reaches a minimum after decreasing continuously. Note that the final projection space found is not always the one with the lowest dH∆H , this is because we need to find a compromise between the minimization of dH∆H and the one of the source error. Thanks to the iterative procedure, DASF is then able to slightly autocorrect the space found 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 finds a classifier, performing better than the SF classifier learned only on the source data. Note that the source error increases, which is expected since we aim at being performing on the target domain.

B. Image Classification

In this section, we evaluate DASF on PascalVOC'07 [START_REF] Everingham | The PASCAL Visual Object Classes Challenge 2007 (VOC2007) Results[END_REF] and TrecVid'07 [START_REF] Smeaton | High-Level Feature Detection from Video in TRECVid: a 5-Year Retrospective of Achievements[END_REF] 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]. We made two experiments.

First, the PascalVOC benchmark is constituted of a set of 5000 training images, a set of 5000 test images and a list of 20 concepts to identify. Training 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 an harder DA task. Our objective is not to provide a solution in such a situation (specific methods exist [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. 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 data and the negatives data are independently drawn such that the ratio +/is 1 3 / 2 3 . We keep the original test set as the target sample. We applied the 5 methods previously described for learning a binary classifier for each concept. Due to the relatively small ratio +/in the target sample, we evaluate the performances according to the well known F-measure. The results are reported on Tab. II. First, TSVM and DASVM perform badly, probably because of the difference between target and source ratios +/which cannot be estimated due to the lack of information on the target sample. SVM performs often better than the two previous ones which can be explained by the similarity between the train and test data. DASF has the best behavior in 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 on Fig. 6 the landmarks selected for the concept PERSON.

In the last experiment, we selected the 6 common concepts between TrecVid'07 and PascalVOC'07. For each concept, we keep our PascalVOC training set as the source domain and take, as the target domain, a TrecVid set of examples with the same ratio +/as the training set. dH∆H is about 1.4 justifying the high difference between the two corpora and thus a potentially hard DA task. The results evaluated with the F-measure are reported on Tab. III. DASF obtains the best results in average and outputs again significantly sparser models. Finally, for those hard tasks the normalized similarity K * is always preferred, showing that DASF is effectively able to deal with non-symmetric non-PSD good similarities. K * has the interest of incorporating some target information which seems useful for hard DA tasks.

VII. CONCLUSION

In this paper, we have proposed a novel domain adaptation approach that takes advantage of the framework of Balcan et al. [START_REF] Balcan | Improved guarantees for learning via similarity functions[END_REF], [START_REF]A theory of learning with similarity functions[END_REF] allowing to deal with similarity functions potentially non-PSD and non-symmetric. The method relies on a regularization term that helps to build a projection space, made of similarities to landmark points, by selecting those both close to the source and target examples. 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 allowing us to take into account our regularizers. Moreover, we have proposed an effective iterative process to lighten the search of the projection space by reweighting the similarities. We have experimentally shown good adaptation abilities on various tasks and our method always outputs sparser models which is clearly an advantage for a large scale application perspective.

As a future work, we intend to extend DASF to allow the use of a small labeled target sample to help a better projection space construction, potentially augmented as in [START_REF] Daumé | Co-regularization based semi-supervised domain adaptation[END_REF]. Another goal would be to exploit multimodality [START_REF] Duan | Domain adaptation from multiple sources via auxiliary classifiers[END_REF].

  (a) A high domain distance: The samples are easily separable, the classifier learned from LS performs badly on T S. A low domain distance: The classifier learned from LS performs well on the two domains.

Figure 1 .

 1 Figure 1. The intuition behind Theorem 1. The source points (LS) are in (dark) green (pos.+, neg.-), the target points (T S) are in (light) orange.

Figure 2 .

 2 Figure 2. The reverse validation. Step 1: Learning h with (4). Step 2: Auto-labeling the target sample by h. Step 3: Learning h r on the autolabeled target sample with (2). Step 4: Evaluation of h r on LS.

  The points in a φ R l -space, |R| = 2. The associated bipartite matching C ST : a line corresponds to a pair (xs, xt). The points in the new φ R l+1 -space after the reweighting procedure.

Figure 3 .

 3 Figure 3. An iteration of the reweighting process. The source points are (dark) green (pos. +, neg. -), the unlabeled target ones are (light) orange circle.

Figure 4 .

 4 Figure 4. Left: a source sample. Right: a target sample with a 50 • rotation.

Figure 5

 5 Figure 5. Two DASF executions. On the left with a 30 • rotation, on the right with a 50 • rotation. On the left y-axis is the error range, on the right y-axis the divergence range. 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 between the distributions, the joint error of the reverse classifier, the error on the target test sample of a SF classifier learning without DA as a baseline.

  corpora. The goal is to identify visual objects 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

Figure 6 .

 6 Figure 6. PascalVOC: The 6 landmarks selected for the concept PERSON, the first 3 images are positive and the last 3 are negative.

Table I THE

 I RESULTS (AVERAGE ACCURACY) OBTAINED FOR THE TWO MOONS TOY PROBLEM.

	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
	0.75	target error source error joint error of reverse classifier SF classifier target error divergence		0.75		0.75	target error source error joint error of reverse classifier SF classifier target error divergence	0.75
	0.5								0.5		0.5					0.5
	Error Rate								Divergence	Error Rate						Divergence
	0.25								0.25		0.25					0.25
	1	2	3	4	5	6	7	8	9		1	2	3	4	5	6
					Iteration								Iteration

Table II THE

 II RESULTS ON THE PASCALVOC TEST TARGET DOMAINS ACCORDING TO THE F-MEASURE. AVG. IS THE AVERAGE RESULT.

	CONCEPT	BIRD	BOAT	BOTTLE	*	BUS	CAR		CAT	CHAIR	CYCLE	COW	DININGTABLE
	SVM	0.18	0.29	0.01		0.16	0.28		0.23	0.24	0.10	0.15	0.15
	SV	867	351	587		476	1096		882	1195	392	681	534
	SF	0.18	0.27	0.11		0.12	0.34		0.20	0.21	0.10	0.11	0.10
	LAND.	237	203	233		212	185		178	241	139	239	253
	TSVM	0.14	0.14	0.11		0.16	0.37		0.14	0.22	0.13	0.12	0.13
	SV	814	704	718		445	631		779	864	390	888	515	CONC.	AVG.
	DASVM	0.16	0.22	0.11		0.14	0.37		0.20	0.23	0.14	0.11	0.15	SVM	0.22
	SV	922	223	295		421	866		1011	1418	706	335	536	SV	642
	DASF LAND. CONC.	0.20 50 DOG *	0.32 184 HORSE	0.12 78 MONITOR	0.17 94 MOTORBIKE	0.38 51 PERSON	*	0.23 378 PLANE	0.26 229 PLANT	0.16 192 SHEEP	0.16 203 SOFA	0.16 372 TRAIN	SF LAND. TSVM SV	0.19 210 0.17 705
	SVM	0.24	0.31	0.16		0.17	0.56		0.34	0.12	0.16	0.16	0.36	DASVM	0.20
	SV	436	761	698		670	951		428	428	261	631	510	SV	622
	SF LAND. TSVM	0.18 200 0.22	0.24 247 0.17	0.12 203 0.12		0.17 243 0.12	0.46 226 0.44		0.34 178 0.18	0.13 236 0.10	0.12 128 0.12	0.13 224 0.15	0.20 202 0.19	DASF LAND.	0.25 200
	SV	704	828	861		861	1111		585	406	474	866	652
	DASVM	0.22	0.23	0.12		0.14	0.55		0.30	0.12	0.13	0.17	0.28
	SV	180	802	668		841	303		356	1434	246	486	407
	DASF	0.25	0.32	0.16		0.18	0.58		0.35	0.15	0.20	0.18	0.42
	LAND.	391	384	287		239	6		181	293	153	167	75

Table III THE

 III RESULTS OBTAINED ON THE TRECVID TARGET DOMAINS ACCORDING TO THE F-MEASURE. AVG. IS THE AVERAGE RESULT.

	CONCEPT	BOAT *	BUS *	CAR *	MONITOR *	PERSON *	PLANE *	AVG.
	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

In our experiments we take N ≤ 30.

ACKNOWLEDGMENT This work was supported in part by the french project VideoSense ANR-09-CORD-026 of the ANR in part by the IST Programme of the European Community, under the PASCAL2 Network of Excellence, IST-2007-216886.

APPENDIX

A. Proof of Lemma 2 Proof: Recall F (.) refers to [START_REF] Bergamo | Exploiting weakly-labeled web images to improve object classification: a domain adaptation approach[END_REF]. First, for any α,

From Hypothesis (5

Since α * is optimal, we have F (α * ) ≤ F (0) = 1, with 0 the null vector. Then, we obtain directly,

B. Proof of Theorem 4

Proof: Let (X,ρ) a compact metric space. Then, with η > 0 and by definition of covering number, we can partition X in M η (finite) subsets, s.t. for x 1 ,x 2 belonging to the same subset ρ(x 1 ,x 2 )≤η. With Y divided in 2 subsets {-1},{+1} and following [START_REF] Xu | Robustness and generalization[END_REF], we partition X×Y in 2M η subsets such that points in the same subset are of the same class. Given K a continuous similarity in its first argument, a training set LS={(x i ,y i )} d l i=1 , a landmark set R={x j } du j=1 , λ>0, β>0 and a set C ST , let α * be the optimal solution of (4). For any s 1 =(x 1 ,y 1 ) ∈ LS, any s 2 =(x 2 ,y 2 ) s.t. s 1 , s 2 belong to the same subset, thus y 1 = y 2 and ρ(x 1 ,x 2 )≤η then, let (a) = L (g, (x 1 , y)) -L (g, (x 2 , y))

By 1-lipschitz property of the hinge loss, the successive application of Holder inequality and Lemma 2, we have,