Domain Generalization via Multidomain Discriminant Analysis
Shoubo Hu Kun Zhang Zhitang Chen Laiwan Chan
stat.ML cs.LG


Alibaba Cloud Quantum Development Platform: Large-Scale Classical Simulation of Quantum Circuits
    [
    December 30, 2023
================================================================================================




Domain generalization (DG) aims to incorporate knowledge from multiple source domains into a single model that could generalize well on unseen target domains. This problem is ubiquitous in practice since the distributions of the target data may rarely be identical to those of the source data. In this paper, we propose Multidomain Discriminant Analysis (MDA) to address DG of classification tasks in general situations. MDA learns a domain-invariant feature transformation that aims to achieve appealing properties, including a minimal divergence among domains within each class, a maximal separability among classes, and overall maximal compactness of all classes. Furthermore, we provide the bounds on excess risk and generalization error by learning theory analysis. Comprehensive experiments on synthetic and real benchmark datasets demonstrate the effectiveness of MDA.




§ INTRODUCTION

Supervised learning has made considerable progress in tasks such as image classification <cit.>, object recognition <cit.>, and object detection <cit.>. In standard setting, a model is trained on training or source data and then applied on test or target data for prediction, where one implicitly assumes that both source and target data follow the same distribution. However, this assumption is very likely to be violated in real problems. For example, in image classification, images from different sources may be collected under different conditions (e.g., viewpoints, illumination, backgrounds, etc), which makes classifiers trained on one domain perform poorly on instances of previously unseen domains. These problems of transferring knowledge to unseen domains are known as domain generalization (DG; <cit.>). Note that no data from target domain is available in DG, whereas unlabeled data from the target domain is usually available in domain adaptation, for which a much richer literature exists (e.g., see <cit.>).

Denote the space of feature X by 𝒳 and the space of label Y by 𝒴. A domain is defined as a joint distribution ℙ(X, Y) over 𝒳×𝒴. In DG of classification tasks, one is given m sample sets, which were generated from m source domains, for model training. The goal is to incorporate the knowledge from source domains to improve the model generalization ability on an unseen target domain. An example of DG is shown in Figure <ref>. 



Although various techniques such as kernel methods <cit.>, support vector machine (SVM) <cit.>, and deep neural network <cit.>, have been adopted to solve DG problem, the general idea, which is learning a domain-invariant representation with stable (conditional) distribution in all domains, is shared in most works. Among previous works, kernel-based methods interpret the domain-invariant representation as a feature transformation from the original input space to a transformed space ℝ^q, in which the (conditional) distribution shift across domains is minimized.

Unlike previous kernel-based methods, which assume that ℙ(Y|X) keeps stable and only ℙ(X) changes across domains (i.e., the covariate shift situation <cit.>), the problem of DG or domain adaptation has also been investigated from a causal perspective <cit.>. In particular, <cit.> pointed out that for many learning problems, especially for classification tasks, Y is usually the cause of X, and proposed the setting of target shift (ℙ(Y) changes while ℙ(X|Y) stays the same across domains), conditional shift (ℙ(Y) stays the same and ℙ(X|Y) changes across domains), and their combination accordingly. <cit.> proposed to do domain adaptation with conditionally invariant components of X, i.e., the transformations of X that have invariant conditional distribution given Y across domains. <cit.> then used this idea for DG, under the assumption of conditional shift. 

Their assumptions stem from the following postulate of causal independence <cit.>:
[Independence of cause and mechanism]
If Y causes X (Y → X), then the marginal distribution of the cause, ℙ(Y), and the conditional distribution of the effect given cause, ℙ(X|Y), are “independent” in the sense that ℙ(X|Y) contains no information about ℙ(Y).

According to postulate <ref>, ℙ(X|Y) and ℙ(Y) would behave independently across domains. However, this independence typically does not hold in the anti-causal direction <cit.>, so ℙ(Y|X) and ℙ(X) tends to vary in a coupled manner across domains. Under assumptions that ℙ(X|Y) changes while ℙ(Y) keeps stable, generally speaking, both ℙ(Y|X) and ℙ(X) change across domains in the anti-causal direction, which is clearly different from the covariate shift situation.

In this paper, we further relax the causally motivated assumptions in <cit.> and propose a novel DG method, which is applicable when both ℙ(X|Y) and ℙ(Y) change across domains. 
Our method focuses on separability between classes and does not enforce the transformed marginal distribution of features to be stable, which allows us to relax the assumption of stable ℙ(Y). To improve the separability, a novel measure named average class discrepancy, which measures the class discriminative power of source domains, is proposed. Average class discrepancy and other three measures are unified in one objective for feature transformation learning to improve its generalization ability on the target domain.





As the second contribution, we derive the bound on excess risk and generalization error[<cit.> proved the generalization error bound of DG in general settings] for kernel-based domain-invariant feature transformation methods. To the best of our knowledge, this is one of the first works to give theoretical learning guarantees on excess risk of DG. 
Lastly, experimental results on synthetic and real datasets demonstrate the efficacy of our method in handling varying class prior distributions ℙ(Y) and complex high-dimensional distributions, respectively.

This paper is organized as follows. Section 2 gives the background on kernel mean embedding. Section 3 introduces our method in detail. 
Section 4 gives the bounds on excess risk and generalization error for kernel-based methods. Section 5 gives experimental settings and analyzes the results. Section 6 concludes this work.



§ PRELIMINARY ON KERNEL MEAN EMBEDDING

Kernel mean embedding is the main technique to characterize probability distributions in this paper. Kernel mean embedding represents probability distributions as elements in a reproducing kernel Hilbert space (RKHS). More precisely, an RKHS ℋ over domain 𝒳 with a kernel k is a Hilbert space of functions f:𝒳→ℝ. Denoting its inner product by ⟨·, ·⟩_ℋ, RKHS ℋ fulfills the reproducing property ⟨ f(·), k(x,·) ⟩_ℋ = f(x), where ϕ(x)  k(x,·) is the canonical feature map of x. The kernel mean embedding of a distribution ℙ(X) is defined as <cit.>:

    μ_X𝔼_X[ϕ(X)] = ∫ _𝒳^ϕ(x)d ℙ (x) ,

where 𝔼_X[ϕ(X)] is the expectation of ϕ(X) with respect to ℙ(X). It was shown that μ_X is guaranteed to be an element in the RKHS if 𝔼_X[k(x,x)]<∞ is satisfied <cit.>. In practice, given a finite sample of size n, the kernel mean embedding of ℙ(X) is empirically estimated as μ̂_X = 1/n∑^n_i=1ϕ(x_i), where {x_i}^n_i=1 are independently drawn from ℙ(X). When k is a characteristic kernel <cit.>, 
μ_X captures all information about ℙ(X) <cit.>, which means that ‖μ_X - μ_X^'‖_ℋ = 0 if and only if ℙ(X) and ℙ(X^') are the same distribution.





§ MULTIDOMAIN DISCRIMINANT ANALYSIS



 §.§ PROBLEM DEFINITION

DG of classification tasks is studied in this paper. Let 𝒳 be the feature space, 𝒴 be the space of class labels, and c be the number of classes. A domain is defined to be a joint distribution ℙ(X,Y) on 𝒳×𝒴.

Let 𝔓_𝒳×𝒴 denote the set of domains ℙ(X,Y) and 𝔓_𝒳 denote the set of distributions ℙ(X) on 𝒳. We assume that there is an underlying finite-variance unimodal distribution over 𝔓_𝒳×𝒴. In practice, domains are not observed directly, but given in the form of finite sample sets.

[Data-generating process]
Each sample set is assumed to be generated in two separate steps: 1) a domain ℙ^s(X,Y) is sampled from 𝔓_𝒳×𝒴, where s is the domain index; 2) n^s independent and identically distributed (i.i.d.) instances are then drawn from ℙ^s(X,Y).


Suppose there are m domains sampled from 𝔓_𝒳×𝒴, the set of m observed sample sets is denoted by 𝒟={𝒟^s}^m_s=1, where each 𝒟^s = { ( x^s_i, y^s_i) }^n^s_i=1 consists of n^s i.i.d. instances from ℙ^s(X,Y). Since in general ℙ^s(X,Y) ≠ℙ^s^'(X,Y), instances in 𝒟 are not i.i.d.

In DG of classification tasks, one aims to incorporate the knowledge in 𝒟 into a model which could generalize well on a previously unseen target domain. In this work, features X are first mapped to an RKHS ℋ.

Then we resort to learning a transformation from the RKHS ℋ to a q-dimensional transformed space ℝ^q, in which instances of the same class are close and instances of different classes are distant from each other. 1-nearest neighbor is adopted to conduct classification in ℝ^q.






 §.§ REGULARIZATION MEASURES




  §.§.§ Average Domain Discrepancy

To achieve the goal that instances of the same class are close to each other, we first consider minimizing the discrepancy of the class-conditional distributions, ℙ^s(X|Y=j), within each class over all source domains. 

For ease of notation, the class-conditional distribution of class j in domain s, ℙ^s(X|Y=j), is denoted by ℙ^s_j. Denoting the kernel mean embedding (<ref>) of ℙ^s_j by μ^s_j, the average domain discrepancy is defined below.

[Average domain discrepancy]
Given the set of all class-conditional distributions 𝒫 = {ℙ^s_j} for s∈{ 1, …, m } and j ∈{ 1,…,c }, the average domain discrepancy, Ψ^add(𝒫), is defined as

    Ψ^add(𝒫) 1/cm2∑^c_j=1∑_1 ≤ s < s^'≤ m‖μ^s_j - μ^s^'_j‖^2_ℋ,

where m2 is the number of 2-combinations from a set of m elements, ‖·‖^2_ℋ denotes the squared norm in RKHS ℋ, and ‖μ^s_j - μ^s^'_j‖_ℋ is thus the Maximum Mean Discrepancy (MMD; <cit.>) between ℙ^s_j and ℙ^s^'_j.


The following theorem shows that Ψ^add(𝒫) is suitable for measuring the discrepancy between class-conditional distributions of the same class from multiple domains.


Let 𝒫 denote the set of all class-conditional distributions. If k is a characteristic kernel <cit.>, Ψ^add(𝒫)=0 if and only if ℙ^1_j = ℙ^2_j=…=ℙ^m_j, for j=1,…, c.



Since k is a characteristic kernel, ‖μ_ℙ - μ_ℚ‖_ℋ is a metric and attains 0 if and only if ℙ = ℚ for any distributions ℙ and ℚ <cit.>. Therefore, ‖μ^s_j - μ^s^'_j‖_ℋ = 0 if and only if ℙ^s_j = ℙ^s^'_j for all s and s^' given j, which means ℙ^1_j = ℙ^2_j=…=ℙ^m_j within each class j. Conversely, if ℙ^1_j = ℙ^2_j=…=ℙ^m_j for j=1,…, c, then each term ‖μ^s_j - μ^s^'_j‖=0 and Ψ^add(𝒫) is thus 0. 




  §.§.§ Average Class Discrepancy

Minimizing average domain discrepancy Ψ^add (<ref>) would make the means of class-conditional distributions of the same class close in ℋ. However, it is possible that the means of class-conditional distributions of different classes are also close, which is a major source of performance reduction of existing kernel-based DG methods. To this end, average class discrepancy is proposed. 

[Average class discrepancy]
Let 𝒫 denote the set of all class-conditional distributions. The average class discrepancy is defined as

    Ψ^acd(𝒫) 1/c2∑_1 ≤ j < j^'≤ c‖ u_j - u_j^'‖^2_ℋ,

where u_j = ∑^m_s=1ℙ(S=s|Y=j) μ^s_j is the mean representation of class j in RKHS ℋ. 




It was shown in <cit.> that the MMD between two distributions ℙ and ℚ, MMD[ ℙ, ℚ ] ≤√(C) W_1 ( ℙ, ℚ ) for some constant C satisfying sup_x∈𝒳 k(x, x) ≤ C < ∞, where W_1 ( ℙ, ℚ ) denotes the first Wasserstein distance <cit.> between distributions ℙ and ℚ. In other words, if ℙ and ℚ are distant in MMD metric, they are also distant in the first Wasserstein distance. Therefore, distributions of different classes tend to be distinguishable by maximizing average class discrepancy, Ψ^acd(𝒫). 



  §.§.§ Incorporating Instance-level Information

Both average domain discrepancy Ψ^add(𝒫) (<ref>) and average class discrepancy Ψ^acd(𝒫) (<ref>) are defined based on the kernel mean embedding of class-conditional distributions ℙ^s_j. By simultaneously minimizing Ψ^add (<ref>) and maximizing Ψ^acd (<ref>), one would make class-conditional kernel mean embeddings within each class close and the those of different classes distant in ℋ. However, certain subtle information, such as the compactness of the distribution, is not captured in Ψ^add and Ψ^acd. As a result, although all mean embeddings satisfy the desired condition, there may still be a high chance of misclassification for some instances. To incorporate such information conveyed in each instance, we propose two extra measures based on kernel Fisher discriminant analysis <cit.>. The first is multidomain between-class scatter.

[Multidomain between-class scatter] Let 𝒟 denote the set of n instances from m domains, each of which consists of c classes. The multidomain between-class scatter is

    Ψ^mbs(𝒟) 1/n∑^c_j=1 n_j‖ u_j - u̅‖^2_ℋ,

where n_j is the total number of instances in class j, and u̅ = ∑^c_j=1 P(Y=j) u_j is the the mean representation of the entire set 𝒟 in ℋ.


Both Ψ^mbs(𝒟) and Ψ^acd(𝒫) measure the discrepancy between the distributions of different classes. The difference stems from the weight n_j in Ψ^mbs(𝒟) (<ref>). By adding n_j, each term in Ψ^mbs(𝒟) is equivalent to pooling all instances of the same class together and summing up their distance to u̅. In other words, Ψ^mbs(𝒟) corresponds to a simple pooling scheme. Note that when the proportion of instances of each class is the same across all domains (i.e., n^s_j / n^s = n^s'_j / n^s', ∀ s, s' for j = 1, …, c, where n^s_j is the number of instances of class j in domain s), Ψ^mbs(𝒟) is consistent with the between-class scatter in <cit.>.

Multidomain within-class scatter, as a straightforward counterpart of multidomain between-class scatter (<ref>), is defined as follows.
[Multidomain within-class scatter]
    Let 𝒟 denote the set of n instances from m domains, each of which consists of c classes. The multidomain within-class scatter is
    
    Ψ^mws(𝒟) 1/n∑^c_j=1∑^m_s=1∑^n^s_j_i=1‖ϕ(x^s_i ∈ j) - u_j‖^2_ℋ,

	where x^s_i ∈ j denotes the feature vector of ith instance of class j in domain s.


The definition above indicates that multidomain within-class scatter measures the sum of the distance between the canonical feature map of each instance and the mean representation in RKHS ℋ of the class it belongs to. It differs from average domain discrepancy in that the information of every instance is considered in multidomain within-class scatter. As a result, by minimizing Ψ^mws(𝒟), one increases the overall compactness of the distributions across classes. Similar to Ψ^mbs(𝒟), when the proportion of instances of each class is the same across all domains (i.e., n^s_j / n^s = n^s^'_j / n^s', ∀ s, s' for j = 1, …, c), Ψ^mws(𝒟) is consistent with the within-class scatter in <cit.>.

We note that each of the measures has its unique contribution and that ignoring any of them may lead to sub-optimal solutions, as demonstrated by the empirical results and illustrated in Appendix A.



 §.§ FEATURE TRANSFORMATION


Our method resorts to finding a suitable transformation from RKHS ℋ to a q-dimensional transformed space ℝ^q, i.e., 𝐖: ℋ↦ℝ^q. We elaborate how the proposed measures are transformed to ℝ^q in this section.

According to the property of norm in RKHS, Ψ^add(𝒫) can be equivalently computed as

    ( 1/cm2∑^c_j=1∑_1 ≤ s < s^'≤ m (μ^s_j - μ^s^'_j) (μ^s_j - μ^s^'_j)^T),

where (·) denotes the trace operator.

Let the data matrix 𝐗=[ x_1, …, x_n]^T∈ℝ^n × d, where d is the dimension of input features X and n = ∑^m_s=1n^s, and the feature matrix Φ=[ ϕ(x_1), …, ϕ(x_n) ]^T, where ϕ: ℝ^d↦ℋ denotes the canonical feature map. Then 𝐖 can be expressed as a linear combination of all canonical feature maps in Φ <cit.>, i.e., 𝐖 = Φ^T𝐁, where 𝐁 is a matrix collecting coefficients of canonical feature maps. Then by applying the transformation 𝐖, Ψ^add(𝒫) in trace formulation (<ref>) becomes

    Ψ^add_𝐁
    = ( 𝐁^T𝐆𝐁),


where 


    𝐆 = 1/cm2∑^c_j=1∑_1 ≤ s < s^'≤ mΦ (μ^s_j - μ^s^'_j ) (μ^s_j - μ^s^'_j )^TΦ^T.



Similarly, after applying the transformation 𝐖, average class discrepancy Ψ^acd(𝒫) (<ref>), multidomain between-class scatter Ψ^mbs(𝒟) (<ref>), and multidomain within-class scatter Ψ^mws(𝒟) (<ref>) are given by:


    Ψ^acd_𝐁 = ( 𝐁^T𝐅𝐁), Ψ^mbs_𝐁 = ( 𝐁^T𝐏𝐁), 
       Ψ^mws_𝐁 = ( 𝐁^T𝐐𝐁),


where


    𝐅 = 1/c2∑_1 ≤ j < j^'≤ cΦ (u_j - u_j^') ( u_j - u_j^')^TΦ^T, 
       𝐏 = 1/n∑^c_j=1 n_jΦ ( u_j - u̅ ) ( u_j - u̅ )^TΦ^T, 
       𝐐 = 1/n∑^c_j=1∑^m_s=1∑^n^s_j_i=1Φ ( ϕ(x^s_i ∈ j) - u_j) ( ϕ(x^s_i ∈ j) - u_j )^TΦ^T.





 §.§ EMPIRICAL ESTIMATION


In practice, one exploits a finite number of instances from m source domains to estimate the transformed measures in ℝ^q. Since all measures depend on μ^s_j and u_j, the estimation of measures reduces to the estimation of μ^s_j and u_j (s = 1,…,m, j = 1, …, c) using the source data. Let x^s_i ∈ j denote the feature vector of ith instance of class j in domain s and n^s_j denote the total number of instances of class j in domain s, each μ^s_j can be empirically estimated as

    μ̂^s_j    = 1/n^s_j∑^n^s_j_i=1ϕ(x^s_i ∈ j).


The empirical estimation of u_j requires ℙ(S=s|Y=j), which can be estimated using Bayes rule as ℙ(S=s|Y=j) = Pr(Y=j|S=s) Pr(S=s) /Pr(Y=j). Since it is usually hard to model the underlying distribution over 𝔓_𝒳×𝒴, we assume that the probabilities of sampling all source domains are equal, i.e., Pr(S=s) = 1/m for s=1,…, m given 𝒟. As a result, ℙ(S=s|Y=j) = n^s_j / n^s/∑^m_s'=1(n^s'_j/ n^s'). Then the empirical estimation of the mean representation of class j in RKHS ℋ is given by


    û_j    = ∑^ m _s=1n^s_j / n^s/∑^m_s'=1(n^s'_j/ n^s') μ̂^s_j.


By substituting the empirical class-conditional kernel mean embedding (<ref>) and empirical mean representation of each class (<ref>) into formulation (<ref>), (<ref>), (<ref>), and (<ref>), these matrices can be estimated from m observed sample sets using the kernel trick <cit.>.



 §.§ THE OPTIMIZATION PROBLEM

Following the solution in <cit.> and in the spirit of Fisher's discriminant analysis <cit.>, we unify measures introduced in previous sections and solve the matrix 𝐁 as

    _𝐁Ψ^acd_𝐁+ Ψ^mbs_𝐁/Ψ^add_𝐁 + Ψ^mws_𝐁.

It can be seen that through maximizing the numerator, the objective (<ref>) preserves the separability among different classes. Through minimizing the denominator, (<ref>) tries to find a domain-invariant transformation which improves the overall compactness of distributions of all classes and make the class-conditional distributions of the same class as close as possible.

By substituting the transformed average domain discrepancy (<ref>), average class discrepancy, multidomain between-class scatter, and multidomain within-class scatter (<ref>), adding 𝐖^T𝐖 = 𝐁^T𝐊𝐁 for regularization, and introducing a trade-off between the measures for further flexibility into the objective (<ref>), we aim to achieve

    _𝐁 = ( 𝐁^T( β𝐅 + (1 - β) 𝐏) 𝐁) /( 𝐁^T( γ𝐆 + α𝐐 + 𝐊)𝐁) ,

where α, β, and γ are trade-off parameters controlling the significance of corresponding measures. Since the objective (<ref>) is invariant to re-scaling of 𝐁, rewriting (<ref>) as a constrained optimization problem and setting the derivative of its Lagrangian to zero (see Appendix B) yields the following generalized eigenvalue problem:

    ( β𝐅 + (1 - β) 𝐏) 𝐁 = ( γ𝐆 + α𝐐 + 𝐊) 𝐁Γ,

where Γ=diag(λ_1, …, λ_q) is the diagonal matrix collecting q leading eigenvalues, 𝐁 is the matrix collecting corresponding eigenvectors.[In practice, γ𝐆 + α𝐐 + 𝐊 is replaced by γ𝐆 + α𝐐 + 𝐊 + ϵ𝐈 for numerical stability, where ϵ is a small constant and set to be 1e-5 for kernel-based DG methods in all experiments.] 

Computing the matrices 𝐆, 𝐅, 𝐏, and 𝐐 takes 𝒪(n^2). Solving the generalized eigenvalue problem (<ref>) takes 𝒪(qn^2). In sum, the overall computational complexity is 𝒪(n^2+qn^2), which is the same as existing kernel-based methods. After the transformation learning, unseen target instances can then be transformed into ℝ^q using 𝐁 and Γ. 

We term the proposed method Multidomain Discriminant Analysis (MDA) and summarize the algorithm in Algorithm <ref>.





§ LEARNING THEORY ANALYSIS

We analyze the the excess risk and generalization error bound after applying feature transformation 𝐖.

In standard setting of learning theory analysis, the decision functions of interest are f: 𝒳↦𝒴. However, our DG problem setting is much more general in the sense that not only ℙ(X) changes (as in the covariate shift setting), but ℙ(Y|X), which corresponds to f in learning theory, also changes across domains. As a result, the decision functions of interest in our analysis are f: 𝔓_𝒳×𝒳↦𝒴. ℙ^s and ℙ^s_X are used interchangeably to denote the marginal distribution of X in domain s.

Let k̅ be a kernel on 𝔓_𝒳×𝒳 and ℋ_k̅ be the associated RKHS. As in <cit.>, we consider kernel k̅ = k_ℙ (ℙ^1, ℙ^2) k_x(x_1, x_2), where k_ℙ and k_x are kernels on 𝔓_𝒳 and 𝒳, respectively. To ensure that k̅ is universal, we consider a particular form for k_ℙ. Let k^'_x be another kernel on 𝒳 and ℋ_ k^'_x be its associated RKHS, γ be a mapping γ: 𝔓_𝒳↦ℋ_k^'_x. Then k_ℙ defined as a kernel k_γ on ℋ_ k^'_x, i.e. k_ℙ (ℙ^1, ℙ^2) = k_γ( γ( ℙ^1 ), γ( ℙ^2 ) ) would lead k̅ to be universal <cit.>. We consider following assumptions regarding the kernels and loss function in our analysis:

The kernels k_x, k^'_x and k_γ are bounded respectively by U^2_ k_x, U^2_ k^'_x and U^2_k_γ.


The canonical feature map γ_ k_γ: ℋ_ k^'_x↦ℋ_ k_γ, where ℋ_ k_γ is the RKHS associated with k_γ, fulfills that ∀ v, w ∈ℋ_ k^'_X, there is a constant L_ k_γ satisfying

    ‖γ_ k_γ(v) - γ_ k_γ(w) ‖≤ L_ k_γ‖ v - w ‖.



The loss function ℓ: ℝ×𝒴↦ℝ_+ is L_ℓ-Lipschitz in its first variable and bounded by U_ℓ.


Assumption 2 and 3 are satisfied when the kernels are bounded. An example of widely adopted bounded kernel is the Gaussian kernel. As a result, we also adopt Gaussian kernel throughout our algorithm. 

Let X̃^t = ( ℙ^t_X, X^t ) and Y^t denote the extended input and output pattern of decision function f over target domain, respectively. The quantity of interest is the excess risk, which is the difference between expected test loss of empirical loss minimizer and expected loss minimizer. For functions in the unit ball centered at the origin in the RKHS of ϕ(X̃^t), the control of the excess risk is given in the following theorem.


Under assumptions 2 – 4, and further assuming that ‖f̂‖_ℋ_k̅≤ 1 and ‖ f^*‖_ℋ_k̅≤ 1, where f̂ denotes the empirical risk minimizer and f^* denotes the expected risk minimizer, then with probability at least 1 - δ there is

    𝔼[ ℓ( f̂(X̃^̃t̃𝐖), Y^t ) ] - 𝔼[ ℓ ( f^*(X̃^̃t̃𝐖), Y^t ) ] 
    ≤    4 L_ℓ L_ k_γ U_k^'_x U_k_x√(( 𝐁^T𝐊𝐁) / n ) + √( 2 log 2 δ^-1/ n ),

where the expectations are taken over the joint distribution of the test domain ℙ^t(X^t, Y^t), n is the number of training samples, and 𝐊 = ΦΦ^T.


See Appendix C for proof. The first term in the bound above involves the size of the distortion (𝐁^T𝐊𝐁) introduced by 𝐁. Therefore, a poor choice of 𝐁 would loose the guarantee. The second term is of order O(n^-1/2) so it would converge to zero as n tends to infinity given δ.

Another quantity of interest is the generalization error bound, which is the difference between the expected test loss and empirical training loss of the empirical loss minimizer. The generalization error bound of DG in a general setting is given in <cit.>. Therefore, we derive it for the case where one applies feature transformation involving 𝐁. Let X̂̃̂^s_i denote the input pattern (ℙ̂^s, x^s_i), where ℙ̂^s is the empirical distribution over features in domain s, and x^s_i is the ith observed feature in domain s. Similarly, y^s_i is the ith label in domain s. With ℰ(f, ∞) being the expected test loss, the generalization bound involving 𝐁 is given in the following theorem.




Under assumptions 2 – 4, and assuming that all source sample sets are of the same size, i.e. n^s = n̅ for s=1, …, m, then with probability at least 1 - δ there is

        sup_ ‖f ‖_ ℋ_ k̅   ≤1  |1/m ∑^m_s=1 1/n^s ∑^n^s_i=1 ℓ( f( X̂̃̂^s_i 𝐖 ), y^s_i ) - ℰ(f, ∞) |

    ≤    U_ℓ ( √(  log2 δ^-1 / 2m n̅  ) + √(  logδ^-1 / 2m  ) ) + √( (𝐁^T 𝐊𝐁 ) ) 

         ( c_1 √( log2 δ^-1 m / n̅ ) + c_2 ( √( 1/m n̅ ) + √( 1/m ) ) ),  
where c_1 = 2√(2) L_ℓ U_k_x L_k_γ U_k^'_x, c_2 = 2 L_ℓ U_k_x U_k_γ.






See Appendix D for proof. The first term is of order O(m^-1/2) and converges to zero as m →∞. The second term, involving (𝐁^T𝐊𝐁), again depends on the choice of 𝐁. The remaining part would converge to zero only if both m and n̅ tend to infinity and log m / n̅ = o(1). In a general perspective, our method, as well as existing ones relying on feature extraction 
can all be viewed as ways of finding transformation 𝐁, which could minimize the generalization bound on the test domain, under different understandings of the DG problem.




§ EXPERIMENTS




 §.§ EXPERIMENTAL CONFIGURATION

We compare MDA with the following 9 methods:

    
  * Baselines: 1-nearest neighbor (1NN) and support vector machine (SVM) with RBF kernel.
    
  * Feature extraction methods: kernel principal component analysis (KPCA; <cit.>) and kernel Fisher discriminant analysis (KFD; <cit.>). 1NN is applied on the transformed features for classification.
    
  * SVM-based DG method: low-rank exemplar-SVMs (L-SVM; <cit.>).
    
  * Neural network-based DG method: CCSA <cit.>. The network setting follows <cit.>.
    
  * Kernel-based DG methods: domain invariant component analysis (DICA; <cit.>), scatter component analysis (SCA; <cit.>), and conditional invariant DG (CIDG; <cit.>). 1NN is applied on the domain-invariant representations for classification.


For 1NN and SVM baselines, instances in source domains are directly combined for training in both synthetic and real data experiments. For other methods, in experiments with synthetic data, the models are trained on two source sample sets, validated on one target sample set, and tested on the other target sample set. In real data experiments, we first selected hyper-parameters by 5-fold cross-validation using only labeled source sample sets. Then the model with optimal parameter settings was applied on the target domain. The classification accuracy on the target domain serves as the evaluation criterion for different methods. Since measures in section 3.2 are defined as the averaged distance, we naturally put them on a equal footing by setting β = 0.5, α = γ = 1. Thus in practice, these parameters are set to be an interval containing values in the above balanced case. The hyper-parameters required by each method and the values validated in the experiments are given in Appendix E.







 §.§ SYNTHETIC DATA

We investigate the influence of variation in the class prior distribution, ℙ(Y), on different DG methods. Two-dimensional data is generated from three different domains and each domain consists of three classes. Each dimension of the data follows a Gaussian distribution 𝒩(μ, σ), where μ is the mean and σ is the standard deviation. The settings of the distribution of the synthetic data are listed in Table <ref>. Domains 1 and 2 are source domains and domain 3 is the target domain. 
The setting in Table <ref> is the base condition where class prior distributions are uniform in all domains, i.e., ℙ^1(Y)= ℙ^2(Y)=ℙ^3(Y). Then we change ℙ(Y) of one source domain to be distributions shown in Figure <ref> to <ref> and keep ℙ(Y) of the other source domain and target domain uniform to compare different DG methods. Note that CCSA is based on convolutional neural network and thus not suitable for 2-dimensional synthetic data.

The results of different methods on different settings of class prior distributions in source domains are given in Table <ref> (also visualized in Appendix F). The accuracy of 1NN is 33.33% in all cases thus omitted in Table <ref>. It can be seen that MDA performs best in the base setting, as well as all settings with different ℙ(Y) in source domains. DICA performs equally well as MDA in (2a, 2c) setting but its accuracy is heavily influenced by the variation in ℙ(Y). Compared with other methods, MDA is much more robust against the variation in ℙ(Y), which is consistent with our expectation because we essentially work with the class-conditional, not the marginal, distributions.



 §.§ OFFICE+CALTECH DATASET

We evaluate the performance of different DG methods on Office+Caltech dataset <cit.>, which is a widely used benchmark for DG tasks. Office+Caltech consists of photos from four different datasets: Amazon (A), Webcam (W), DSLR (D), and Caltech-256 (C) <cit.>. Since there are 10 shared classes in these datasets, photos of these classes are selected and those from the same original dataset form one domain in Office+Caltech. Thus, the domains within Office+Caltech corresponds to the biases of different data collection procedures <cit.>.
The 4096-dimensional DeCAF_6 features <cit.> are adopted in the experiments to ensure that the feature spaces, 𝒳, are consistent across all domains.

The accuracies on different choices of target domains are shown in Table <ref>. MDA again performs best, yet by a smaller margin of improvement compared to that of the synthetic experiment. In particular, MDA is the only kernel-based method that outperforms 1NN in (A, C) case which is probably because of the newly proposed average class discrepancy (<ref>). L-SVM outperforms other kernel-based methods and ranks the second. Note that other 4 cases, such as A, D, C → W, are not reported since 1NN baseline could already achieve accuracies higher than 90%.





 §.§ VLCS DATASET

The second real data experiment uses the VLCS dataset. It consists of photos of five common classes extracted from four datasets: Pascal VOC2007 (V) <cit.>, LabelMe (L) <cit.>, Caltech-101 (C) <cit.>, and SUN09 (S) <cit.>. Photos from the same dataset form one domain in VLCS. DeCAF_6 features of 4096 dimensions are again adopted in the experiments to ensure the consistency of feature spaces over different domains. The training and test procedures are the same as in experiments on the Office+Caltech dataset. The parameters of L-SVM were trained (validated) on 70% (30%) source instances due to its high complexity.

The accuracies are given in Table <ref>. It is interesting to see that SVM baseline outperforms all DG methods in 6 cases. This is probably because many instances of different classes are overlapped in VLCS, so using 1NN in the transformed space is more likely to misclassify them compared with SVM. Apart from SVM baseline, MDA performs best in 8 out of 10 cases compared with other DG methods. CCSA outperforms MDA in the case of S being the target domain, which may indicate that neural networks extracted better features in this case. 
Inspired by the results of SVM, kernel-based methods together with SVM classifier may be a promising direction for further VLCS accuracy improvement. 



§ CONCLUSION

In this paper, we proposed a method called Multidomain Discriminant Analysis (MDA) to solve the DG problem of classification tasks. Unlike existing works, which typically assume stability of certain (conditional) distributions, 
MDA is able to solve DG problems in a more general setting where both ℙ(Y) and ℙ(X|Y) change across domains. The newly proposed measures, average domain discrepancy and average class discrepancy, together with two measures based on kernel Fisher discriminant analysis, are theoretically analyzed and incorporated into the objective for learning the domain-invariant feature transformation. We also prove bounds on the excess risk and generalization error for kernel-based DG methods. The effectiveness of MDA is verified by experiments on synthetic and two real benchmark datasets. 



  §.§.§ Acknowledgements

SH thanks Lequan Yu for comments on a previous draft of this paper. KZ acknowledges the support by National Institutes of Health (NIH) under Contract No. NIH-1R01EB022858-01, FAINR01EB022858, NIH-1R01LM012087, NIH-5U54HG008540-02, and FAIN- U54HG008540, by the United States Air Force under Contract No. FA8650-17-C-7715, and by National Science Foundation (NSF) EAGER Grant No. IIS-1829681. The NIH, the U.S. Air Force, and the NSF are not responsible for the views reported in this article. This work was partially funded by the Hong Kong Research Grants Council. 







§ APPENDIX




§ QUANTITIES' PROPERTY ILLUSTRATION

The illustrations comparing average domain discrepancy with multidomain within-class scatter, and average class discrepancy with multidomain between-class scatter are given in Figure <ref> and <ref>.







§ DERIVATION OF THE LAGRANGIAN

Since the objective 

    _𝐁 = ( 𝐁^T( β𝐅 + (1 - β) 𝐏) 𝐁) /( 𝐁^T( γ𝐆 + α𝐐 + 𝐊)𝐁)

is invariant to re-scaling 𝐁→δ𝐁, we rewrite (<ref>) as a constrained optimization problem:

    _𝐁    ( 𝐁^T( β𝐅 + (1 - β) 𝐏) 𝐁) 
    
    s.t.     ( 𝐁^T( γ𝐆 + α𝐐  + 𝐊 )𝐁) = 1,

which yields the Lagrangian

    ℒ =    ( 𝐁^T( β𝐅 + (1 - β) 𝐏) 𝐁) 
        - ( ( 𝐁^T( γ𝐆 + α𝐐  + 𝐊 )𝐁 - 𝐈_q) Γ),

where Γ is a diagonal matrix containing the Lagrange multipliers and 𝐈_q denotes the identity matrix of dimension q. Setting the derivative with respect to 𝐁 in the Lagrangian (<ref>) to zero yields the following generalized eigenvalue problem:

    ( β𝐅 + (1 - β) 𝐏) 𝐁 = ( γ𝐆 + α𝐐  + 𝐊) 𝐁Γ.




§ PROOF OF THEOREM 2


Under assumptions 2 – 4, and further assuming that ‖f̂‖_ℋ_k̅≤ 1 and ‖ f^*‖_ℋ_k̅≤ 1, where f̂ denotes the empirical risk minimizer, f^* denotes the expected risk minimizer, then with probability at least 1 - δ there is

    𝔼[ ℓ( f̂(X̃^̃t̃𝐖), Y^t ) ] - 𝔼[  ℓ ( f^*(X̃^̃t̃𝐖), Y^t ) ] 
    ≤    4 L_ℓ  L_ k_γ U_k^'_x U_k_x√(( 𝐁^T𝐊𝐁)  / n )  + √( 2 log 2 δ^-1/ n ),

where the expectations are taken over the joint distribution of the test domain ℙ^t(X^t, Y^t), n is the number of training samples, and 𝐊 = ΦΦ^T.



First, we use the following result.

[Generalization bound based on Rademacher complexity]
Define 𝒜 = { x ↦ℓ( f(x), y): f ∈ℋ} to be the loss class, the composition of the loss function with each of the hypotheses. With probability at least 1 - δ:

    L(f̂) - L(f^*) ≤ 4 ℛ_n(𝒜) + √( 2 log2/δ/ n ),

where L(f̂) denotes the expected test risk of the empirical risk minimizer, L(f̂) denotes the expected test risk of the expected risk minimizer, ℛ_n(𝒜) denotes the Rademacher complexity of loss class 𝒜, and n denotes the number of training points.


By applying theorem <ref>, with probability at least 1- δ there is

    𝔼_ℙ^t_X [ ℓ( f̂(X̃^̃t̃𝐖), Y^t ) ] - 𝔼_ℙ^t_X [  ℓ ( f^*(X̃^̃t̃𝐖), Y^t ) ] ≤ 4 ℛ_n(𝒜) + √( 2 log 2 δ^-1/ n ),

where 𝒜 denotes the loss class { x ↦ℓ(f( ℙ, x), y): ‖ f ‖_ℋ_k̅≤ 1 }, ℛ_n(·) denotes the Rademacher complexity and n is the number of training points.

Since the loss function ℓ is L_ℓ-Lipschitz in its first variable, there is

    ℛ_n(𝒜) = ℛ_n(ℓ∘ f) ≤ L_ℓℛ_n( ℋ_k̅ ).


To obtain the Rademacher complexity of ℋ_k̅, i.e. ℛ_n( ℋ_k̅ ), we adopt the following theorem.

[Rademacher complexity of L_2 ball]
Let ℱ = { z ↦⟨ w, z ⟩ : ‖ w ‖_2≤ B_2} (bound on weight vectors). Assume 𝔼_Z ∼ p^*[ ‖ Z ‖^2_2] ≤ C^2_2 (bound on spread of data points). Then

    ℛ_n(ℱ) ≤B_2C_2/√(n),

where n denotes the number of training points.


According to the function class we restricted, B_2 in theorem <ref> in our case is 1. For the bound of feature maps of data in ℋ_k̅ (corresponds to C_2), there is

    ‖k̅( X̃^̃t̃𝐖, ·) ‖
    
    =     ‖γ_ k_γ( γ( ℙ^t )) ⊗ k_X(X^t, ·) 𝐖‖
    ≤    L_ k_γ‖γ( ℙ^t ) ‖‖ k_X(X^t, ·) 𝐖‖
    ≤    L_ k_γ U_k^' U_k‖𝐖‖_HS.


Note that 𝐖 = Φ^T𝐁 and 𝐊 = ΦΦ^T is invertible. It follows that ( 𝐁^T𝐊𝐁 ) defines a norm consistent with the Hilbert-Schmidt norm ‖𝐖‖_HS. Therefore, by applying theorem <ref>, there is


    ℛ_n(𝒜)  ≤ L_ℓ L_ k_γ U_k^' U_k√(( 𝐁^T𝐊𝐁 )  / n ).

Combining it with (<ref>) gives the results.




§ PROOF OF THEOREM 3


Under assumptions 2 – 4, and assuming that all source sample sets are of the same size, i.e. n^s = n̅ for s=1, …, m, then with probability at least 1 - δ there is

        sup_ ‖f ‖_ ℋ_ k̅   ≤1  |1/m ∑^m_s=1 1/n^s ∑^n^s_i=1 ℓ( f( X̂̃̂^s_i 𝐖 ), y^s_i ) - ℰ(f, ∞)  |

    ≤    U_ℓ ( (  log2 δ^-1 / 2m n̅  )^1/2 + (  logδ^-1 / 2m  )^1/2 ) + √( (𝐁^T 𝐊𝐁 ) ) ( c_1 ( log2 δ^-1 m / n̅ )^1/2  + c_2 ( ( 1/m n̅  )^ 1/2  + ( 1/m  )^ 1/2  ) ) 
 
where c_1 = 2√(2) L_ℓ U_k_x L_k_γ U_k^'_x, c_2 = 2 L_ℓ U_k_x U_k_γ.



Follow the idea in <cit.>, the supremum of the generalization error bound can be decomposed as

    sup_‖ f ‖_ℋ_k̅≤ 1 |1/m∑^m_s=11/n^s∑^n^s_i=1ℓ( f( X̂̃̂^s_i𝐖 ), y^s_i) - ℰ(f, ∞)  |
    ≤    sup_‖ f ‖_ℋ_k̅≤ 1 |1/m∑^m_s=11/n^s∑^n^s_i=1( ℓ( f( X̂̃̂^s_i𝐖 ), y^s_i) - ℓ( f( X̃^s_i𝐖 ), y^s_i) ) |
        + sup_‖ f ‖_ℋ_k̅≤ 1 |1/m∑^m_s=11/n^s∑^n^s_i=1ℓ( f( X̃^s_i𝐖 ), y^s_i) - ℰ(f, ∞) |
    
        :=     (I) + (II),

where X̂̃̂^s_i = ( ℙ̂^s, x^s_i ), X̃^s_i = ( ℙ^s, x^s_i ).

Bound of term (I)

According to the assumption that the loss ℓ is L_ℓ -Lipschitz in its first variable, we have

    (I) ≤    L_ℓsup_‖ f ‖_ℋ_k̅≤ 1 1/m∑^m_s=11/n^s∑^n^s_i=1| f( X̂̃̂^s_i𝐖 ) - f( X̃^s_i𝐖 ) |
    ≤    L_ℓsup_‖ f ‖_ℋ_k̅≤ 1 1/m∑^m_s=1‖  f( (ℙ̂^s, ·) 𝐖) - f( (ℙ^s, ·) 𝐖) ‖_∞


For any x ∈𝒳 and ‖ f ‖_ℋ_k̅≤ 1, using the reproducing property of the kernel k̅ and Cauchy-Schwarz inequality, we have

    | f( (ℙ̂^s, x) 𝐖) - f( (ℙ^s, x) 𝐖) |    = |⟨k̅( (ℙ̂^s, x) 𝐖, ·) - k̅( (ℙ^s, x) 𝐖, ·), f ⟩|
       ≤‖ f ‖‖k̅( (ℙ̂^s, x) 𝐖, ·) - k̅( (ℙ^s, x) 𝐖, ·) ‖


According to the assumption, there is ‖ f ‖≤ 1. For the second term in (<ref>) we have

    ‖k̅( (ℙ̂^s, x) 𝐖, ·) - k̅( (ℙ^s, x) 𝐖, ·) ‖
    
        =    ‖γ_ k_γ( γ( ℙ̂^s )) ⊗ k_X(x, ·) 𝐖  -  γ_ k_γ( γ( ℙ^s )) ⊗ k_X(x, ·) 𝐖‖
    ≤   ‖γ_ k_γ( γ( ℙ̂^s )) ⊗ k_X(x, ·)  -  γ_ k_γ( γ( ℙ^s )) ⊗ k_X(x, ·) ‖‖𝐖‖_HS
    
        =    ‖𝐖‖_HS( ⟨k̅( (ℙ̂^s, x), · ) - k̅( (ℙ^s, x) , · ),  k̅( (ℙ̂^s, x), · ) - k̅( (ℙ^s, x) , · ) ⟩)^1/2
    ≤   ‖𝐖‖_HS k(x,x)^1/2( k_γ( γ( ℙ^s ), γ( ℙ^s ) ) + k_γ( γ( ℙ̂^s ), γ( ℙ̂^s ) ) - 2 k_γ( γ( ℙ^s ), γ( ℙ̂^s ) ) )^1/2
    ≤    U_k‖𝐖‖_HS‖γ_ k_γ( γ( ℙ^s ) ) - γ_ k_γ( γ( ℙ̂^s ) ) ‖
    ≤    U_k L_ k_γ‖𝐖‖_HS‖γ( ℙ̂^s ) - γ( ℙ^s ) ‖.


Combining (<ref>), (<ref>) and ‖ f ‖≤ 1, there is

    | f( (ℙ̂^s, x) 𝐖) - f( (ℙ^s, x) 𝐖) |≤ U_k L_ k_γ‖𝐖‖_HS‖γ( ℙ̂^s ) - γ( ℙ^s ) ‖.


Now we derive the bound on ‖γ( ℙ̂^s ) - γ( ℙ^s ) ‖. For independent real zero-mean random variables x_1, …, x_n such that | x_i|≤ C for i = 1, …, n, Hoeffding's inequality states that  ∀ϵ > 0:

    P[ |1/n∑^n_i=1 x_i| > ϵ] ≤ 2 exp( - nϵ^2/ 2C^2).


Set the δ = 2 exp( - nϵ^2/ 2C^2), then with probability at least 1- δ:

    |1/n∑^n_i=1 x_i| < √(2)C √(log 2 δ^-1/n).


Similar result holds for zero-mean independent random variables ϕ(x_1), …, ϕ(x_n) with values in a separable complex Hilbert space and such that ‖ϕ(x_i) ‖≤ C, for i = 1, …, n:

    ‖1/n∑^n_i=1ϕ(x_i) ‖ < √(2)C √(log 2 δ^-1/n).


For independent uncentered variables ϕ^'( x_i ) with mean M, bounded by C. Let ϕ( x_i ) = ϕ^'( x_i ) - M denote the re-centered variables, now bounded at worst by 2C by the triangle inequality. Set δ = 2 exp( - nϵ^2/ 8 C^2),  we obtain with probability at least 1-δ that:

    ‖1/n∑^n_i=1ϕ^'(x_i) - M ‖ < 2 √(2)C √(log 2 δ^-1/n)


Based on the result of (<ref>), we have 

    ‖γ( ℙ̂^s ) - γ( ℙ^s ) ‖ = ‖1/n^s∑^n_i=1ϕ^'(x^s_i) - 𝔼_X∼ℙ^s [ ϕ^'(X) ] ‖≤ 3U_k^'√(log 2 δ^-1/n̅)


Combining (<ref>) and (<ref>) we have

    sup_‖ f ‖_ℋ_k̅≤ 1 ‖  f( (ℙ̂^s, ·) 𝐖) - f( (ℙ^s, ·) 𝐖) ‖_∞≤ 2√(2) U_k L_ k_γ U_k^'‖𝐖‖_HS√(log 2 δ^-1/n̅)


Conditionally to the draw of {ℙ^s}_1 ≤ s ≤ m, we can apply (<ref>) to each (ℙ^s, ℙ̂^s ) the the union bound over s = 1, …, m to get that with probability at least 1 - δ:

    (I) ≤ 2√(2) L_ℓ U_k L_ k_γ U_k^'‖𝐖‖_HS√(log 2 δ^-1 + log m /n̅)


Bound of term (II)

This section follows the idea of <cit.> so steps of proof that are largely unchanged are omitted. First, we define the conditional (idealized) test error for a given test distribution ℙ^t_XY as

    ℰ(f, ∞| ℙ^t_XY) := 𝔼_ (X^t, Y^t) ∼ℙ^t_XY[ ℓ( f(X̃^t𝐖), Y^t) ],


where X̃^t = (P^t_X, X^t).

Then (II) is further decomposed as

    (II) ≤   1/m∑^m_s=11/n^s∑^n^s_i=1( ℓ( f( X̃^s_i𝐖 ), y^s_i) - ℰ(f, ∞|ℙ^s_XY) ) + 1/m∑^m_s=1( ℰ(f, ∞|ℙ^s_XY) - ℰ(f, ∞) ) 
    
        :=     (IIa) + (IIb)


Bound of term (IIa)

In the case where conditioning on {ℙ^s_XY}_1≤ s ≤ m, the observations in 𝒟 = { (x^s_i, y^s_i) }^m, n^s_s=1, i=1 are now independent (but not identically distributed) for this conditional distribution. We can thus apply the McDiarmid inequality to the function

    ζ( 𝒟) := sup_‖ f ‖_ℋ_k̅≤ 1 1/m∑^m_s=11/n^s∑^n^s_i=1( ℓ( f( X̃^s_i𝐖 ), y^s_i) - ℰ(f, ∞|ℙ^s_XY) ).


When n^s = n^s^' = n̅ for all s, s^', that with probability 1- δ over the draw of 𝒟, it holds

    |ζ - 𝔼[ ζ|{ℙ^s_XY}_1≤ s ≤ m] |≤ U_l√(log2δ^-1/2m n̅).


Then by the standard symmetrization technique, 𝔼[ ζ|{ℙ^s_XY}_1≤ s ≤ m] can be bounded via Rademacher complexity as:

    𝔼[ ζ|{ℙ^s_XY}_1≤ s ≤ m] 
        
        ≤   2/m𝔼_(x^s_i, y^s_i)𝔼_(ϵ^s_i)[ sup_‖ f ‖_ℋ_k̅≤ 1 ∑^m_s=11/n^s∑^n^s_i=1ϵ^s_i( ℓ( f( X̃^s_i𝐖 ), y^s_i) ) |{ℙ^s_XY}_1≤ s ≤ m] 
    ≤    2 L_ℓ U_k U_ k_γ‖𝐖‖_HS√(1/m n̅),

where the last inequality is from the bound of the Rademacher complexity of the loss class ℓ∘ f.

Bound of term (IIb)

Since the {ℙ^s_XY}_1≤ s ≤ m are i.i.d., the McDiarmid inequality can be applied to the function

    ξ( {ℙ^s_XY}_1≤ s ≤ m) := sup_‖ f ‖_ℋ_k̅≤ 1 1/m∑^m_s=1( ℰ(f, ∞|ℙ^s_XY) - ℰ(f, ∞) ),


then one obtains that with probability 1- δ over the draw of {ℙ^s_XY}_1≤ s ≤ m, it holds

    |ξ - 𝔼[ξ] |≤ U_ℓ√(logδ^-1/ 2m ).


Similarly, by the standard symmetrization technique, 𝔼[ξ] is bounded as

    𝔼[ξ]
        
        
        ≤   2/m𝔼_{ℙ^s_XY}_1≤ s ≤ m𝔼_ (X^s, Y^s)_1 ≤ s ≤ m𝔼_ (ϵ^s)_1 ≤ s ≤ m[ sup_‖ f ‖_ℋ_k̅≤ 1 ∑^m_s=1ϵ^sℓ( f( X̃^s𝐖 ), Y^s)  ] 
    ≤    2 L_ℓ U_k U_k_γ‖𝐖‖_HS√( 1 / m ),

where the last inequality is again from the bound of the Rademacher complexity of the loss class ℓ∘ f.

Finally, 𝐖 = Φ^T𝐁 and 𝐊 = ΦΦ^T is invertible. It follows that ( 𝐁^T𝐊𝐁 ) defines a norm consistent with the Hilbert-Schmidt norm ‖𝐖‖_HS. By combining the above results we obtain the announced result.




§ EXPERIMENTAL CONFIGURATIONS

Due to the difference in techniques adopted in different methods, there is/are different hyper-parameter(s) in each method require tuning in the experiments.


    
  * 1NN: since there is no hyper-parameter to be determined in 1NN, instances in source domains are directly combined for training. Then we apply the trained model on target domains and report the test accuracy.
    
  * SVM: the regularization coefficient C requires tuning in SVM. C ∈{ 0.1, 0.5, 1.0, 2.0, 5.0, 10.0 } are validated in the experiments.
    
  * KPCA and KFD: the kernel width σ_k requires tuning. σ_k∈{ 0.1d_M, 0.2d_M, 0.5d_M, d_M, 2d_M, 5d_M}, where d_M = median( ‖x_i - x_j‖^2_2), ∀x_i, x_j∈𝒟, are validated.
    
  * E-SVM: four hyper-parameters (λ_1, λ_2, C_1, C_2) require tuning. λ_1∈{ 0.1, 1, 10 }, λ_2∈{ 0.5λ_1, 1λ_1, 2λ_1}, and C_1, C_2∈{ 0.1, 1, 10 } are validated.
    
  * CCSA: two hyper-parameters (lr, α) require tuning. learning rate lr ∈{ 0.5, 1.0, 1.5 } and α∈{ 0.1, 0.25, 0.4 } are validated.
    
  * DICA: Two parameters (λ, ϵ) require tuning. λ∈{ 1e-3, 1e-2, 1e-1, 1.0, 1e1, 1e2, 1e3} 
 and ϵ∈{ 1e-3, 1e-2, 1e-1, 1.0, 1e1, 1e2, 1e3} were validated.
    
  * SCA: Two parameters (β, δ) require tuning. β∈{ 0.1, 0.3, 0.5, 0.7, 0.9 }, 
 δ∈{ 1e-3, 1e-2, 1e-1, 1.0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6} were validated.
    
    
  * CIDG: Three hyper-parameters (β, α, γ) require tuning. β∈{ 0.1, 0.3, 0.5, 0.7, 0.9 }, 
 γ∈{ 1e-3, 1e-2, 1e-1, 1, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6}, and 
 α∈{ 1, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9}, were validated.
    
    
  * MDA: Three hyper-parameters (β, α, γ) require tuning. β∈{ 0.1, 0.3, 0.5, 0.7, 0.9 }, 
 γ∈{ 1e-3, 1e-2, 1e-1, 1.0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6}, and 
 α∈{ 1, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9}, were validated.


For feature extraction methods (i.e., KPCA and KFD) and kernel-based DG methods (i.e., DICA, SCA, CIDG, and MDA), 
in real data experiments, different number of leading eigenvectors (corresponds to the dimension of the transformed subspace) that contribute to certain proportions (i.e. { 0.2, 0.4, 0.6, 0.8, 0.92, 0.94, 0.96, 0.98 }) of the sum of all eigenvalues are tested and the highest accuracies are reported for each method.



§ SYNTHETIC EXPERIMENTAL RESULTS VISUALIZATION

In this section, we show the data distribution of source domains in the transformed domain-invariant subspace ℝ^q of the synthetic experiment for kernel-based DG methods: SCA, CIDG, MDA, which are proposed for classification problems. The results are given in Figure <ref> and <ref>.

We observe from the results that: 1) the transformation learned from MDA performs the best in terms of the separation of different classes of target domains; 2) the overlapped region in source domains(green and red classes) is handled slightly better in MDA than in CIDG; 3) SCA has difficulty in separating instances of different classes in part of the cases.







§ RELATED WORK

Compared with domain adaptation, domain generalization is a younger line of research. <cit.> are the first to formalize the domain generalization of classification tasks. Motivated by automatic gating of flow cytometry data, they adopted kernel-based methods and derived the dual of a kind of cost-sensitive SVM to solve for the optimal decision function. A feature projection-based method called Domain Invariant Component Analysis (DICA; <cit.>) was then proposed in 2013. DICA was the first to bring the idea of learning a shared subspace into domain generalization. It finds a transformation to a subspace in which the differences between marginal distributions ℙ(X) over domains are minimized while preserving the functional relationship between Y and X. 

Along this line, subsequent feature projection-based methods have been proposed. Scatter Component Analysis (SCA; <cit.>) is the first unified framework for both domain adaptation and domain generalization. It combines domain scatter, kernel principal component analysis and kernel Fisher discriminant analysis into an objective and trades between them to learn the transformation. Unlike previous works, the authors of Conditional Invariant Domain Generalization (CIDG; <cit.>) are the first to analyze domain generalization of classification tasks from causal perspective and thus consider more general cases where both ℙ(Y|X) and ℙ(X) vary across domains. They combine total scatter of class-conditional distributions, scatter of class prior-normalized marginal distributions, and kernel Fisher discriminant analysis to achieve the goal of domain generalization.

Besides the aforementioned methods in general, domain generalization problem also attracted extensive attention of computer vision community. <cit.> proposed a max-margin framework (Undo-Bias) in which each domain is assumed to be controlled by the sum of the visual world and a bias. A modified SVM-based method is adopted for solving the weights and biases in the model. Unbiased Metric Learning (UML; <cit.>), which is based on a learning-to-rank framework, first learns a set of distance metrics and then validate to select the one with best generalization ability. <cit.> adopted exemplar-SVM and introduced a nuclear norm based regularizer into the objective to learn a set of more robust examplar-SVMs for domain generalization purpose. <cit.> introduced Multi-task Autoencoder (MTAE), a feature learning algorithm that uses a multi-task strategy to learn unbiased object features, where the task is the data reconstruction. More recently, domain generalization methods based on deep neural networks <cit.> were proposed to cope with the problem induced by distribution shift.

