Year: 2019

Abstract:
In many real-world applications, we want to exploit multiple source datasets of similar tasks to learn a model for a different but related target dataset – e.g., recognizing characters of a new font using a set of different fonts. While most recent research has considered ad-hoc combination rules to address this problem, we extend previous work on domain discrepancy minimization to develop a finite-sample generalization bound, and accordingly propose a theoretically justified optimization procedure. The algorithm we develop, Domain AggRegation Network (DARN), is able to effectively adjust the weight of each source domain during training to ensure relevant domains are given more importance for adaptation. We evaluate the proposed method on real-world sentiment analysis, digit recognition and object recognition datasets and show that DARN can significantly outperform the state-of-the-art alternatives.

heading: 1 INTRODUCTION
text: Many machine learning algorithms assume the learned predictor will be tested on the data from the same distribution as the training data. This assumption, although reasonable, is not necessarily true for many real-world applications. For example, patients from one hospital may have a different distribution of gender, height and weight from another hospital. Consequently, a diagnostic model constructed at one location may not be directly applicable to another location without proper adjustment. The situation becomes even more challenging when we want to use data from multiple source domains to build a model for a target domain, as this requires deciding, e.g., how to rank the source domains and how to effectively aggregate these domains when training complex models like deep neural networks. Including irrelevant or worse, adversarial, data from certain source domains can severely reduce the performance on the target domain, leading to undesired consequences.
To address this problem, researchers have been exploring methods of transfer learning (Pan & Yang, 2009) or domain adaptation (Mansour et al., 2009a; Cortes et al., 2019), where a model is trained based on labelled source data and unlabelled target data. Most existing works have focused on single-source to single-target (“one-to-one”) domain adaptation, using different assumptions such as covariate shift (Shimodaira, 2000; Gretton et al., 2009; Sugiyama & Kawanabe, 2012) or concept drift (Jiang & Zhai, 2007; Gama et al., 2014). When dealing with multiple source domains, one may attempt to directly use these approaches by combining all source data into a large joint dataset and then apply one-to-one adaptation. This naı̈ve aggregation method will often fail as not all source domains are equally important when transferring to a specific target domain. There are some works on multi-source to single-target adaptation. Although many of them are theoretically motivated with cross-domain generalization bounds, they either use ad-hoc aggregation rules when developing actual algorithms (Zhao et al., 2018; Li et al., 2018) or lack finite-sample analysis (Mansour et al., 2009b;c; Hoffman et al., 2018a). This leaves a gap between the theory for multi-source adaptation and theoretically sound algorithm for domain aggregation.
This research has three contributions: First, we extend prior work on one-to-one adaptation using discrepancy (Cortes et al., 2019) to develop a finite-sample cross-domain generalization bound for multi-source adaptation. We show that in order to improve performance on the specific target domain, there is a trade-off between utilizing all source domains to increase effective sample size, versus removing source domains that are underperforming or not similar to the target domain. Second, motivated by our theory and domain adversarial method (Ganin & Lempitsky, 2015; Ganin
et al., 2016), we propose Domain AggRegation Network (DARN), that can effectively aggregate multiple source domains dynamically during the course of training. Unlike previous works, our aggregation scheme (Eq. (6)), which itself is of independent interest in some other contexts, is a direct optimization of our generalization upper bound (Eq. (3)) without resorting to heuristics. Third, our experiments on sentiment analysis, digit recognition and object recognition show that DARN can significantly outperform state-of-the-art methods.
Section 2 introduces necessary background on one-to-one adaptation based on discrepancy. Then Section 3 elaborates our theoretical analysis and the corresponding algorithm deployment. Section 4 discusses about related approaches in more detail, highlighting the key differences to the approach developed here. Section 5 empirically compares the performance of the proposed method to other alternatives. Finally, Section 6 concludes this work.

heading: 2 BACKGROUND ON CROSS-DOMAIN GENERALIZATION
text: This section provides necessary background from previous work on one-to-one domain adaptation (Cortes et al., 2019). Let X be the input space, Y ⊆ R be output space andH ⊆ {h : X 7→ Y} be a hypothesis set. A loss function L : Y × Y 7→ R+ is µ-admissible1 if
∀y, y′, y′′ ∈ Y |L(y′, y)− L(y′′, y)| ≤ µ |y′ − y′′|. (1)
The discrepancy (Mansour et al., 2009a) between two distributions P,Q over X is defined as
disc(P,Q) = max h,h′∈H
|LP (h, h′)− LQ(h, h′)| where LP (h, h′) = Ex∼P [L(h(x), h′(x))].
This quantity can be computed or approximated empirically given samples from both distributions. For classification problems with 0-1 loss, it reduces to the well-known dA-distance (Kifer et al., 2004; Blitzer et al., 2008; Ben-David et al., 2010) and can be approximated using a domain-classifier loss w.r.t. H (Zhao et al., 2018; Ben-David et al., 2007, Sec.4), while for regression problems with L2 loss, it reduces to a maximum eigenvalue (Cortes & Mohri, 2011, Sec.5); see Section 3.2 for more details. For two domains (P, fP ), (Q, fQ) where fP , fQ : X 7→ Y are the corresponding labeling functions, we have the following cross-domain generalization bound:
Theorem 1 (Proposition 5 & 8, Cortes et al. (2019)) Let Rm(H) be the Rademacher complexity ofH given sample size m,HQ = {x 7→ L( h(x), fQ(x) ) : h ∈ H} be the set of functions mapping x to its loss w.r.t. fQ andH,
ηH = µ×min h∈H
( max
x∈supp(P̂ ) |fP (x)− h(x)|+ max x∈supp(Q̂) |fQ(x)− h(x)|
) , (2)
be a constant measuring how well H can fit the true models where supp(P̂ ) means the support of the empirical distribution P̂ (using the µ from Eq. (1)), and MQ = supx∈X ,h∈H L( h(x), fQ(x) ) be the upper bound on loss for Q. Given Q̂ with m points sampled iid from Q labelled according to fQ, for δ ∈ (0, 1),∀h ∈ H, w.p. at least 1− δ,
LP (h, fP ) ≤ LQ̂(h, fQ) + disc(P,Q) + 2Rm(HQ) + ηH +MQ
√ log(1/δ)
2m .
This theorem provides a way to generalize across domains when we have sample Q̂ labelled according to fQ and an unlabelled sample P̂ . The first term is the usual loss function for the sample Q̂, while the second term disc(P,Q) can be estimated based on the unlabelled data Q̂, P̂ . ηH measures how well the model family H can fit the example from the datasets, and it is not controllable once H is given. The final term, as a function of sample size m, determines the convergence speed.
1For example, the common Lp losses are µ-admissible (Cortes et al., 2019, Lemma 23).

heading: 3 DOMAIN AGGREGATION NETWORKS

heading: 3.1 THEORY
text: Suppose we are given k source domains {(Si, fSi) : i ∈ [k] def = {1, 2, . . . , k}} and a target domain (T, fT ) where Si, T are distributions over X and fSi , fT : X 7→ Y are their respective labelling functions. For simplicity, assume that each sample Ŝi has m points, drawn iid from Si and labelled according to fSi . We are also given m unlabelled points T̂ drawn iid from T . We want to leverage all source domains’ information to learn a model h ∈ H minimizing LT (h, fT ). One naı̈ve approach could be to combine all the source domains into a large joint dataset and conduct one-to-one adaptation to the target domain using Theorem 1. However, including data from irrelevant or even adversarial domains is likely to jeopardize the performance on the target domain, which is sometimes referred to as negative transfer (Pan & Yang, 2009). Moreover, as certain source domains may be more similar or relevant to the target domain than the others, it makes more sense to adjust their importance according to their utilities. We propose to find domain weight αi ≥ 0 such that ∑k i=1 αi = 1 to achieve this. Our main theorem below sheds some light on how we should combine the source domains (the proof is provided in Appendix A):
Theorem 2 Given k source domains datasets {(x(i)j , y (i) j ) : i ∈ [k], j ∈ [m]} with m iid examples each where Ŝi = {x(i)j } and y (i) j = fSi(x (i) j ), for any α ∈ ∆ = {α : αi ≥ 0, ∑ i αi = 1}, δ ∈ (0, 1), and ∀h ∈ H, w.p. at least 1− δ
LT (h, fT ) ≤ ∑ i αi ( LŜi(h, fSi) + disc(T, Si) + 2Rm(HSi) + ηH,i ) + ‖α‖2MS √ log(1/δ) 2m ,
(3) where HSi = {x 7→ L(h(x), fSi(x)) : h ∈ H} is the set of functions mapping x to the corresponding loss, ηH,i is a constant similar to Eq. (2) with Q̂ = Ŝi, P̂ = T̂ and MS = supi∈[k],x∈X ,h∈H L(h(x), fSi(x)) is the upper bound on loss on the source domains.
There are several observations. (1) In the last term of the bound, m/‖α‖22 serves as the effective sample size. If α is uniform (i.e., [1/k, . . . , 1/k]>), then the effective sample size is km; if α is onehot, then we effectively only havem points from exactly one domain. (2) Rm(HSi) determines how expressive the model familyH is w.r.t. the source data Si. It can be estimated from samples (Bartlett & Mendelson, 2002, Theorem 11), but the computation is non-trivial for a model family like deep neural networks. The ηH,i is uncontrollable once the hypothesis classH (e.g., neural network architecture) is given. Using a richer H is not always beneficial. Richer H can reduce the ηH,i and also help us find a better function h with smaller source losses LŜi , but it will increase the Rm(HSi). As removing these two terms does not seem to be empirically significant, we ignore them below for simplicity. (3) Let gh,i
def = LŜi(h, fSi) + disc(T, Si). Small gh,i indicates that we can achieve
small loss on domain Si, and it is similar to the target domain (i.e., small disc(T, Si), estimated from T̂ , Ŝi). We may want to emphasize on Si by setting αi close to 1, but this will reduce the effective sample size. Therefore, we have to trade-off between the terms in this bound by choosing a proper α. (4) When Si and T are only partially overlapped, it might be difficult to find a suitable αi. In such cases, we can artificially split the given source domains into smaller datasets (e.g., by using clustering) then apply our method on the finer scale. This strategy requires that the learning algorithm has low computational complexities w.r.t. k, the number of source domains. As we will see later in Section 3.3, this is indeed the case for our algorithm.
Before we proceed to develop an algorithm based on the theorem, let us compare Eq. (3) to existing finite-sample bounds. The bound of Blitzer et al. (2008, Theorem 3) is informative when we have access to a small set of labelled target examples. In such cases, we can improve our bound by using this small labelled target set as an additional source domain Sk+1. We can also perform better model selection using such labelled set. The bound of Zhao et al. (2018, Theorem 2) is based on the dA-distance, which is a special case of disc in our bound. Moreover, our bound (Eq. (3)) use samplebased Rademacher complexity, which is generally tighter than other complexity measures such as VC-dimension (Bartlett & Mendelson, 2002; Koltchinskii et al., 2002; Bousquet et al., 2003).

heading: 3.2 ALGORITHM
text: In this section, we illustrate how to develop a practical algorithm based on Theorem 2. Ignoring the constants, we would like to minimize the upper bound of Eq. (3):
min h∈H min α∈∆
Uh(α) = 〈gh,α〉+ τ‖α‖2 (4)
where gh = [gh,1, . . . , gh,k]> and τ > 0 is a hyper-parameter. If we can solve the inner minimization exactly given h, then we can treat the optimal α∗(h) as a function of h and solve the outer minimization over h effectively. In the following, we show how to achieve this.
Given gh, the inner minimization can be reformulated as a second-order cone programming problem, but it has no closed-form solution due to the τ‖α‖2 term. Consider the following problem (z = −gh/τ recovers the inner minimization):
min α∈∆
−〈z,α〉+ ‖α‖2 (5)
The Lagrangian for its dual problem is
Λ(α,λ, ν) = −z>α + ‖α‖2 − λ>α + ν(1>α− 1) ν ∈ R,λ 0 Taking the derivative w.r.t. α and setting it to zero gives
∂Λ ∂α = −z + α/‖α‖2 − λ + ν1 = 0 =⇒ α∗/‖α∗‖2 = z− ν1 + λ.
Notice that α 6= 0 so we have the constraint ‖z − ν1 + λ‖2 = 1. Using this α∗ in Λ gives the following dual problem
max ν,λ
−ν s.t. ‖z− ν1 + λ‖2 = 1 and λ 0
We would like to decrease ν as much as possible, and the best we can attain is the ν∗ satisfying ‖[z − ν∗1]+‖2 = 1 where [v]+ = max(0,v). In this case, the optimal λ∗ can be attained as λ∗i = 0 if zi − ν∗ > 0, otherwise λ∗i = ν
∗ − zi; see Fig. 1. Although we do not have a closed-form expression for the optimal ν∗, we can use binary search to find it, starting from the interval [zmin−1, zmax] where zmin, zmax are the minimum and maximum of z respectively. Then we can recover the primal solution as
α∗ = [z− ν∗1]+/‖[z− ν∗1]+‖1. (6)
Eq. (6) gives rise to a new way to project any vector z to the probability simplex, which is of independent interest and may be used in some other contexts.2 It resembles the standard projection onto the simplex based on squared Euclidean distance (Duchi et al., 2008, Eq.(3)). One subtle but crucial difference is that our Eq. (5) uses ‖α‖2 instead of ‖α‖22. Recall that z = −gh/τ . Here τ can be interpreted as a temperature parameter. On one hand, if τ 0, all z will have similar values and thus the optimal ν∗ will be close to zmax and α∗ will be close to uniform. On the other hand, as τ → 0, zmax will stand out from the rest zi and eventually ν∗ = zmax − 1. This means the gh,i corresponding to the zmax is small enough so we focus solely on this domain and ignore all other domains (even though this will reduce effective sample size as discussed in Section 3.1).
From a different perspective, if we define F ∗∆(α) = ‖α‖2, then Eq. (5) equals −F∆(z), where F∆, F ∗ ∆ are convex conjugates of each other, where we use ∆ to emphasize their dependency on the simplex domain. Then our objective Eq. (4) can be expressed as
min h∈H
−F∆(z) = −F∆(−gh/τ)
2For example, if we consider z to be the logits of the final classification layer of a neural network, this projection provides another way to produce class probabilities similar to the softmax transformation.
We can optimize our objective and train a neural network h using gradient-based optimizer. The optimal α∗(h) is merely a function of h and we can backprop through it. To facilitate the gradient computation and show that we can efficiently backprop through the projection of Eq. (6), we derive the Jacobian J = ∂α/∂z in Appendix B. This ensures effective end-to-end training.
Now we elaborate more on how to compute gh,i. The LŜi(h, fSi) is the task loss. The disc(T, Si) depends on whether the task is classification or regression. For classification, disc coincides with the dA-distance, so we use the domain classification loss (Zhao et al., 2018; Ben-David et al., 2007):
disc(T̂ , Ŝi) = 2
( 1−min
hd ̂T,Si(hd)
) ̂T,Si(hd) = 1
2m 2m∑ i=1 ∣∣hd(x)− δx∈T̂ ∣∣ where ̂T,Si(hd) is the sample domain classification loss of a domain classifier hd : X 7→ {0, 1}. This minimization over hd will become maximization once we move it outside of the disc due to the minus sign. Then our objective consists of minh and maxhd , which resembles adversarial training (Goodfellow et al., 2014): learning a task classifier h to minimize loss and a domain classifier hd to maximize domain confusion. More specifically, if we decompose the neural network h into a feature extractor hfea and a label predictor hy (i.e., h(x) = hy(hfea(x))), we can learn a domainclassifier hd on top of hfea to classify hfea(x) between Si and T as a binary classification problem, where the domain itself is the label (see Fig. 2). To achieve this, we use the logistic loss to approximate ̂T,Si(hd) and apply the gradient reversal layer (Ganin & Lempitsky, 2015; Ganin et al., 2016) when optimizing disc through backpropagation.
If we are solving regression problems with L2 loss, then disc(T̂ , Ŝi) = ‖MT −MSi‖2 is the largest eigenvalue (in magnitude) of the difference of two matrices MT = 1m ∑ j hfea(x (T ) j )h > fea(x (T ) j ) and MSi = 1 m ∑ j hfea(x (i) j )h > fea(x (i) j ) (Mansour et al., 2009a; Cortes & Mohri, 2011, Sec.5), which can be conveniently approximated using mini-batches and a few steps of power iteration.

heading: 3.3 COMPLEXITY
text: Here we analyze the time and space complexities of the algorithm in each iteration. Similar to MDAN (Zhao et al., 2018), in each gradient step, we need to compute the task loss LŜi(h, fSi) and the disc(T, Si) (or dA-distance) using mini-batches from each source domain i ∈ [k]. The question is whether one can maintain the O(k) complexity given that we need to compute the weights using Eq. (6) and backprop through it. For the forward computation of α∗, in order to compute the threshold ν∗ to the > 0 relative precision, the binary search will cost O(k log(1/ )). As for the backward pass of gradient computation, according to our calculation in Appendix B, the Jacobian J = ∂α/∂z has a concise form, meaning that it is possible to compute the matrix-vector product Jv for a given vector v in O(k) time and space. Therefore, our space complexity is the same as MDAN but our time complexity is slightly slower by a factor of log(1/ ). In comparison, the time
complexity for MDMN (Li et al., 2018) isO(k2) because it requires computing the pairwise weights within the k source domains. When we have a lot of source domains, MDMN will be noticeably slower than MDAN and our DARN.

heading: 4 RELATED WORK
text: The idea of utilizing data from the source domain (S, fS) to train a model for a different but related target domain (T, fT ) has been explored extensively for the last decade using different assumptions (Pan & Yang, 2009; Zhang et al., 2015). For instance, the covariate shift scenario (Shimodaira, 2000; Gretton et al., 2009; Sugiyama & Kawanabe, 2012; Wen et al., 2014) assumes S 6= T but fS = fT , while concept drift (Jiang & Zhai, 2007; Gama et al., 2014) assumes S = T but fS 6= fT . More specifically, Theorem 1 (Cortes et al., 2019) shows that both covariate shift (as measured by the discrepancy disc) and model misspecification (as controlled by ηH) contribute to the adaptation performance (Wen et al., 2014).
Finding a domain-invariant feature space by minimizing a distance measure is common practice in domain adaptation, especially for training neural networks. Tzeng et al. (2017) provided a comprehensive framework that subsumes several prior efforts on learning shared representations across domains (Tzeng et al., 2015; Ganin et al., 2016). DARN uses adversarial domain classifier and the gradient reversal trick from Ganin et al. (2016). Instead of proposing a new loss for each pair of the source and target domains, our main contribution is the aggregation technique of computing the mixing coefficients α, which is derived from theoretical guarantees. When dealing with multiple source domains, our aggregation method can certainly be applied to other forms of discrepancies such as MMD (Gretton et al., 2012; Long et al., 2015; 2016), and other model architectures such as Domain Separation Network (Bousmalis et al., 2016), cycle-consistent model (Hoffman et al., 2018b), class-dependent adversarial domain classifier (Pei et al., 2018) and Known Unknown Discrimination (Schoenauer-Sebag et al., 2019).
Our work focuses on multi-source to single-target adaptation, which has been investigated in the literature. Sun et al. (2011) developed a generalization bound but resorted to heuristic algorithms to adjust distribution shifts. Zhao et al. (2018) proposed a certain ad-hoc scheme for the combination coefficients α, which, unlike ours, are not theoretically justified. Multiple Domain Matching Network (MDMN) (Li et al., 2018) computes domain similarities not only between the source and target domains but also within the source domain themselves based on Wasserstein-like measure. Calculating such pairwise weights can be computationally demanding when we have a lot of source domains. Their bound requires additional smooth assumptions on the labelling functions fSi , fT , and is not a finite-sample bound, as opposed to ours. As for the actual algorithm, they also use adhoc coefficients α without theoretical justification. Mansour et al. (2009b;c) consider multi-source adaptation where T = ∑ i βiSi is a convex mixture of source distributions with some weights βi. Our analysis does not require this assumption. Hoffman et al. (2018a) provides similar guarantees with different assumptions, but unlike ours, their bounds are not finite-sample bounds.

heading: 5 EXPERIMENTS
text: In this section, we compare DARN with several other baselines and state-of-the-art methods for the popular tasks: sentiment analysis, digit recognition and object recognition. The following methods are compared. (1) The SRC (for source) method uses only labelled source data to train the model. It merges all available source examples to form a large dataset to perform training without adaptation. (2) TAR (for target) is another baseline that uses only m labelled target data instances. It serves as upper bound of the best we can achieve if we had access to the true label of the target data. (3) Domain Adversarial Neural Network (DANN) (Ganin et al., 2016) is similar to our method in that we both use adversarial training objectives. It is not obvious how to adapt DANN to the multisource setting. Here we follow previous protocol (Zhao et al., 2018) and merge all source data to form a large joint source dataset of km instances for DANN to perform adaptation. (4) Moment Matching for Multi-Source Domain Adaptation (M3SDA) (Peng et al., 2019) is a recent state-ofthe-art method that combines moment matching and maximizing classifier discrepancy (Saito et al., 2018). We use their public code with a few necessary adjustments (change classification head based on the number of classes etc.) (5) Multisource Domain Adversarial Network (MDAN) (Zhao et al.,
2018) resembles our method in that we both dynamically assign each source domain an importance weight during training. However, unlike ours, their weights are not theoretically justified. We use the soft version of MDAN since they reported that it performs better than the hard version, and we use their code. (6) Multiple Domain Matching Network (MDMN) (Li et al., 2018) computes weights not only between source and target domains but also within source domain themselves. We use their code of computing weights in our implementation. All the methods are applied to the same neural network structure to ensure fair comparison. Our PyTorch implementation will be available online after acceptance.

heading: 5.1 SENTIMENT ANALYSIS
text: Setup. We use the Amazon review dataset (Blitzer et al., 2007; Chen et al., 2012) that consists of positive and negative product reviews from four domains (Books, DVD, Electronics and Kitchen). Each of them is used in turn as the target domain and the other three are used as source domains. Their sample sizes are 6465, 5586, 7681, 7945 respectively. We follow the common protocol (Chen et al., 2012; Zhao et al., 2018) of using the top-5000 frequent unigrams/bigrams of all reviews as bag-of-words features and train a fully connected model (MLP) with [1000, 500, 100] hidden units for classifying positive versus negative reviews. The dropout drop rate is 0.7 for the input and hidden layers. In each run, we randomly sample 2000 reviews from each domain as labelled source or unlabelled target training examples, while the remaining instances are used as test examples for evaluation. The hyper-parameters are chosen based on cross-validation. The model is trained for 50 epochs and the mini-batch size is 20 per domain. The optimizer is Adadelta with a learning rate of 1.0. The soft version of MDAN has an additional parameter γ = 1/τ which is the inverse of our temperature τ . The chosen parameters are γ = 10.0 for MDAN and γ = 0.9 for our DARN, which are selected from a wide range of candidate values.
Results and Analysis. Table 1 summarizes the classification accuracies. The last column is the average accuracy of four domains, and the standard errors are calculated based on 20 runs. (1) Most of the time, DANN with joint source data performs worse than SRC which has no adaptation. This may be because it does not adjust for the each source domain, and as a result, it fails to ignore irrelevant data to avoid negative transfer. (2) Some domains are harder to adapt to than the others. For example, the accuracies of SRC and TAR on the Electronics domain are very close to each other, indicating that this requires little to no adaptation. Yet, our DARN is the closest to the TAR performance here. The Books domain is more challenging as the improvement over the SRC method is small, even though there exists a large gap between SRC and TAR. (3) DARN is always within the best performing methods and significantly outperforms others in the Electronics domain. Note that MDMN additionally computes similarities within source domains in each iteration, which can be computationally expensive (O(k2) per iteration) if the number of source domains is large. Instead, our method focuses on the discrepancy between source and target domains (O(k) per iteration) and can achieve similar performance on this problem.

heading: 5.2 DIGIT RECOGNITION
text: Setup. Following the setting from previous work (Ganin et al., 2016; Zhao et al., 2018), we use the four digit recognition datasets in this experiment (MNIST, MNIST-M, SVHN and Synth). MNIST
is a well-known gray-scale images for digit recognition, and MINST-M (Ganin & Lempitsky, 2015) is a variant where the black and white pixels are masked with color patches. Street View House Number (SVHN) (Netzer et al., 2011) is a standard digit dataset taken from house numbers in Google Street View images. Synthetic Digits (Synth) (Ganin & Lempitsky, 2015) is a synthetic dataset that mimic SVHN using various transformations. One of the four datasets is chosen as unlabelled target domain in turn and the other three are used as labelled source domains.
MNIST images are resized to 32× 32 and represented as 3-channel color images in order to match the shape of the other three datasets. Each domain has its own given training and test sets when downloaded. Their respective training sample sizes are 60000, 59001, 73257, 479400, and the respective test sample sizes are 10000, 9001, 26032, 9553. In each run, 20000 images are randomly sampled from each domain’s training set as actual labelled source or unlabelled target training examples, and 9000 images are randomly sampled from each domain’s test set as actual test examples for evaluation. The model structure is shown in Appendix D. There is no dropout and the hyperparameters are chosen based on cross-validation. It is trained for 50 epochs and the mini-batch size is 128 per domain. The optimizer is Adadelta with a learning rate of 1.0. Validation selected γ = 0.5 for MDAN and γ = 0.1 for DARN.
Results and Analysis. Table 2 shows the classification accuracy of each target dataset over 20 runs. (1) All methods except DANN can consistently outperform SRC. Again, without proper adjustment for each source domain, DANN with joint source data can perform worse than SRC. This suggests the importance of ignoring irrelevant data to avoid negative transfer. (2) DARN significantly outperforms MDAN and MDMN across all four domains, especially on the MNIST-M and SVHN domains. Notice that even though MDAN and MDMN have generalization guarantees, they both resort to ad-hoc aggregation rules to combine the source domains during training. Instead, our aggregation (Eq. (6)) is a direct optimization of the upper bound (Theorem 2) thus is theoretically justified and empirically superior for this problem.

heading: 5.3 OBJECT RECOGNITION: OFFICE-HOME
text: To showcase the applicability of our method to more complicated real-world tasks, we use the challenging Office-Home dataset (Venkateswara et al., 2017). It contains images of 65 everyday objects such as spoon, sink, mug and pen from four different domains: Art, Clipart, Product and Real-World. One of the four datasets is chosen as unlabelled target domain in turn and the other three are used as labelled source domains.
The respective sample sizes are 2427, 4365, 4439, 4357. In each run, 2000 images are randomly sampled from each domain as labelled source or unlabelled target training examples, and the rest images are used as test images for evaluation. We use the ResNet50 He et al. (2016) pretrained from the ImageNet in PyTorch as the base network for feature learning and put an MLP with [1000, 500, 100, 65] units on top for classification. It is trained for 50 epochs and the mini-batch size is 32 per domain. The optimizer is Adadelta with a learning rate of 1.0. MDAN uses γ = 1.0 while DARN uses γ = 0.5.
Table 3 shows the classification accuracy of each target dataset over 20 runs. Most existing works in the literature focused on single-source to single-target adaptation on this problem (e.g., see (Long et al., 2018)). Compared to them, using multi-source methods can significantly boost performance,
revealing the importance of using multiple source domains when possible. Even though this is a significantly more challenging problem with more classes and much fewer images compared to the digits datasets, our DARN achieves state-of-the-art performance in this setting, excelling existing methods by a noticeable margin.
5.4 VISUALIZING DOMAIN IMPORTANCE
To demonstrate how DARN can effectively aggregate multiple source domains, we visualize the source domain weights (i.e., α in DARN) for the Amazon dataset. We also compared to the weights produced by MDMN, using the original authors’ code.
Fig. 3 and Fig. 4 compare the evolution of source domain weights during training. In each subfigure, every row corresponds to the weights of the source domains when learning for one target domain. The white stripe indicates there is no target domain weight and darker stripe means less weight. They are evaluated at the end of each epoch over 50 epochs. To avoid noisy values due to small mini-batch size, the values are exponential moving averages with a decay rate of 0.95. (1) For DARN, as Electronics and Kitchen are more related to each other than Books and DVD, their respective weights remain higher during training. This is reasonable since we have overlapping products (e.g., blenders) in both domains. The α is changing dynamically during training, showing the flexibility of our method to adjust domain importance when needed. (2) In comparison, the domain weights produced by MDMN are not very stable. We take a closer look at the MDMN weights and notice that they change drastically, especially towards the end of the training. It can produce alternating one-hot vectors α, changing from one domain to a different domain and ignoring the rest. This instability makes their domain weights hard to interpret.

heading: 6 CONCLUSION AND FUTURE WORK
text: Our work uses the discrepancy (Mansour et al., 2009a; Cortes et al., 2019) to derive a finite-sample generalization bound for multi-source to single-target adaptation. Our theorem shows that, in order to achieve the best possible generalization upper bound for a target domain, we need to trade-off between including all source domains to increase effective sample size and removing source domains that are underperforming or not similar to the target domain. Based on this observation, we derive an algorithm, Domain AggRegation Network (DARN), that can dynamically adjust the weight of each source domain during end-to-end training. Experiments on sentiment analysis, digits recognition and object recognition show that DARN outperforms state-of-the-art alternatives. Recent
analysis (Zhao et al., 2019; Johansson et al., 2019) show that solely focusing on learning domain invariant features can be problematic when the marginal label distributions on Y between source and target domains are significantly different. Thus it makes sense to take ηH into consideration when a small amount of labelled data is available for the target domain, which we will explore in the future.

heading: A PROOF OF THEOREM 2
text: Theorem 2 Given k source domains datasets {(x(i)j , y (i) j ) : i ∈ [k], j ∈ [m]} with m iid examples each where Ŝi = {x(i)j } and y (i) j = fSi(x (i) j ), for any α ∈ ∆ = {α : αi ≥ 0, ∑ i αi = 1}, δ ∈ (0, 1), and ∀h ∈ H, w.p. at least 1− δ
LT (h, fT ) ≤ ∑ i αi ( LŜi(h, fSi) + disc(T, Si) + 2Rm(HSi) + ηH,i ) + ‖α‖2MS √ log(1/δ) 2m ,
where HSi = {x 7→ L(h(x), fSi(x)) : h ∈ H} is the set of functions mapping x to the corresponding loss, ηH,i is a constant similar to Eq. (2) with Q̂ = Ŝi, P̂ = T̂ and MS = supi∈[k],x∈X ,h∈H L(h(x), fSi(x)) is the upper bound on loss on the source domains.
Proof: The proof is similar to Cortes et al. (2019); Zhao et al. (2018). Given α ∈ ∆, the mixture Ŝ = ∑ i αiŜi can be considered as the joint source data with km points, where a point x
(i) from Ŝi has weight αi/m. Define Φ = suph∈H LT (h, fT )− ∑ i αiLŜi(h, fSi). Changing a point x (i) from Ŝi will change Φ at most MSαim . Using the McDiarmid’s inequality, we have Pr(Φ − E[Φ] > ) ≤ exp ( − 2
2m M2S‖α‖22
) . As a result, for δ ∈ (0, 1), w.p. at least 1− δ, the following holds for any h ∈ H
LT (h, fT ) ≤ ∑ i αiLŜi(h, fSi) + E[Φ] + ‖α‖2MS
√ log(1/δ)
2m .
Now we bound E[Φ]. LetHSi = {x 7→ L(h(x), fSi(x)) : h ∈ H}.
E[Φ] = EŜ [ sup h∈H LT (h, fT )− ∑ i αiLŜi(h, fSi) ]
≤ EŜ [ sup h∈H ∑ i αiLSi(h, fSi)− ∑ i αiLŜi(h, fSi) ] + sup h∈H ( LT (h, fT )− ∑ i αiLSi(h, fSi) )
≤ EŜ [∑ i αi sup h∈H ( LSi(h, fSi)− LŜi(h, fSi) )] + ∑ i αi sup h∈H (LT (h, fT )− LSi(h, fSi))
= ∑ i αiEŜi [ sup h∈H ( LSi(h, fSi)− LŜi(h, fSi) )] + ∑ i αi sup h∈H (LT (h, fT )− LSi(h, fSi))
≤ 2 ∑ i αiRm(HSi) + ∑ i αi sup h∈H (LT (h, fT )− LSi(h, fSi))
≤ ∑ i αi (2Rm(HSi) + disc(T, Si) + ηH,i) .
where first and second inequalities are using the subadditivity of sup, followed by the equality using the independence between the domains {Ŝi}, the second last inequality is due to the standard “ghost sample” argument in terms of the Rademacher complexity and the last inequality is due to Cortes et al. (2019, Proposition 8) for each individual Si.

heading: B JACOBIAN
text: Here we calculate the Jacobian Jij = ∂αi/∂zj for Eq. (6) in the main text:
α∗ = [z− ν∗1]+/‖[z− ν∗1]+‖1.
In the following, we write α = α∗, ν = ν∗ to simplify notations. Let S = {i : zi − ν > 0} be the support of the probability vector α. Jij = 0 if i /∈ S or j /∈ S since αi = 0 in the former case while zj does not contribute to the α in the latter case. Now consider the case i, j ∈ S. Let K = ‖[z− ν1]+‖1 = ∑ j∈S(zj − ν). Then αi = (zi − ν) · 1 K and
∂αi ∂zj =
( δi=j − ∂ν
∂zj ) · 1 K − 1 K2 · ∂K ∂zj · (zi − ν) = 1 K ( δi=j − ∂ν ∂zj − ∂K ∂zj · αi ) , (7)
where δi=j is the indicator or delta function. Now we compute ∂ν∂zj and ∂K ∂zj . By the definition of ν, we know that ∑
j∈S (zj − ν)2 = |S|ν2 − 2ν ∑ j∈S zj + ∑ j∈S z2j = 1
=⇒ ν = ∑ j∈S zj
|S| − √ A |S| where A = ∑ j∈S zj 2 − |S| ∑ j∈S z2j − 1  =⇒ ∂ν
∂zj =
1 |S| − Bj |S| √ A where Bj = ∑ j′∈S zj′ − |S|zj (8)
The first right-arrow is due to the quadratic formula and realizing that ∑ j∈S zj/|S| is the mean of the supported zj so ν must be smaller than it (i.e., we take − in the ± of the quadratic formula, otherwise some of the zj will not be in the support anymore). And
∂K ∂zj = 1− |S| · ∂ν ∂zj = Bj√ A . (9)
Plugging Eq. (8) and Eq. (9) in Eq. (7) gives
∂αi ∂zj = 1 K
[ δi=j − 1
|S| + Bj√ A · ( 1 |S| − αi )] Note that
Bj K = ∑ j′∈S zj′ − |S|zj∑ j′∈S(zj′ − ν) = ∑ j′∈S(zj′ − ν) + |S|(ν − zj)∑ j′∈S(zj′ − ν) = 1− |S|αj .
Then
Jij = ∂αi ∂zj = 1 K
( δi=j − 1
|S| ) + |S|√ A ( 1 |S| − αi )( 1 |S| − αj ) .
In matrix form,
J = 1
K
( Diag(s)− ss >
|S| ) + |S|√ A ( s |S| −α ◦ s )( s |S| −α ◦ s )> ,
where s = [s1, . . . , sk]> is a vector indicating the support si = δi∈S and ◦ is element-wise multiplication. More often, we need to compute its multiplication with a vector v
Jv = s K ◦ ( v − s >v |S| ) + |S|√ A ( s |S| −α ◦ s )( s |S| −α ◦ s )> v.
Note that all quantities except A have been computed during the forward pass of calculating Eq. (6). A can be computed in O(|S|) time so the overall computation is still O(k) since |S| ≤ k.

heading: C REGRESSION ON SYNTHETIC DATA
text: Due to the lack of publicly available multi-source regression datasets, we demonstrate our method on a synthetic regression problem here.
Setup. We use eight source domains, where the ith (i = {0, 1, . . . , 7}) domain data is generated by xi ∼ N (π4 i − 7π 8 , 0.2
2) and the output is y = sin(x) + where ∼ N (0, 0.052) is random noise. These eight domains evenly cover the sin function on [−π, π] (see Fig. 5a). Next we construct four target domains, where the jth (j = {0, 1, 2, 3}) domain is generated by xj ∼ N (π2 j − 3π 4 , 0.4
2). Similar to the source domains, these four target domains evenly cover [−π, π] (see Fig. 5b). Each source/target domain has 100 data points.
We use labelled source data and unlabelled target data for learning. We take on one target domain at a time, and learn a linear model from all eight source domains with MSE loss. The goal is to see whether our method can focus on the relevant source domains and learn a linear model that can perform well on the target domain.
Results and Analysis. First, Fig. 5b shows the learned models. The learned linear models can fit the target data very well. This shows that our DARN can learn a meaningful model for a specific target domain, using only labelled source data and unlabelled target data. Second, Fig. 5c shows the source domain weights (the α) for each target domain after training. The weight colors correspond to the colors in Fig. 5a. It is noticeable that DARN can focus well on the respective relevant source domains for each target domain and ignore the rest. Note that these values are automatically learned during the training of the model.

heading: D MODEL ARCHITECTURE FOR DIGIT RECOGNITION

Review summaries:
This paper studies multi-source domain adaptation problem. First this paper proposes a new theory for this domain that extends generalized discrepancy theory to multi-source setting. After derive a new generalization bound, this paper also proposes a new method based on the theory. Evaluation on real world datasets are proposed to show the efficiency of the proposed method.