A

Appendix

Organization of the appendix: 1). We first list the pseudocode of the proposed algorithms in Sec. B.
2). We then provide detailed proofs for all the corollaries and theorems presented in the main paper inSec. C. 3). We describe more experimental details in Sec. D, including dataset description, networkarchitecture and training parameters of the proposed and baseline methods, and more analysis of theexperimental results. 4). We introduce and discuss more related work about domain adaptation in
Sec. E.

B

Pseudocode

Due to space limit of the main paper, we provide pseudocode of both algorithms, including the hardversion and the soft version, in this section.
Algorithm 1 Multiple Source Domain Adaptation
1: for t = 1 to 1 do(t)bS }k and D
bT , each of size m
2:
Sample {Si }ki=1 and T (t) from {Di i=13:
for i = 1 to k do
(t)
4:
"bi
"bS (t) (h) minh0 2H H "bT (t) ,S (t) (h0 )
i

5:
6:
7:

(t)

(t)

i

Compute wi := exp(b"i )end for(t)
Select i(t) := arg maxi2[k] "bi// Hard version(t)

8:
Backpropagate gradient of "bi(t)9:for i = 1 to k do
(t)
(t) P
(t)
10:
Normalize wi
wi / i0 2[k] wi0
11:
end forP(t) (t)12:
Backpropagate gradient of i2[k] wi "bi
13: end forC

ProofsC.1

Proof of Corollary 1// Soft version

Corollary 1 (Worst case classification bound). Let H be a hypothesis class with V Cdim(H) = d. If
bT and {DbS }k are the empirical distributions generated with m i.i.d. samples from each domain,Di i=1
then, for 0 < < 1, with probability at least 1, for all h 2 H, we have:⇢1bT ; DbS ) +"T (h)  max "bSi (h) + dH H (D
i
2
i2[k]

i

+O

s

1
m

✓

log

Proof. For each one of the k source domain, from Thm. 1, for 8 > 0, w.p.b
following inequality hold:
1bS , DbT ) +"T (h)  "bSi (h) + dH H (D
i
2

13

i+O

r

k

m
+ d log
d

1

◆!

(2)

/k, we have thed log(m/d) + log(k/ )m!

Using a union bound argument, we have:
s ✓
⇢
◆!!
1
1
k
m
bT ; DbS ) + i + O
Pr "T (h) > max "bSi (h) + dH H (Dlog + d log
i
2
m
d
i2[k]
0
1
s ✓
!
◆
_
1
1
k
m
bT ; DbS ) + i + O
A Pr @"T (h) > "bSi (h) + dH H (Dlog + d log
i
2
m
d
i2[k]
s ✓
◆!!
X
1
1
k
m
bT ; DbS ) + i + O
Pr "T (h) > "bSi (h) + dH H (Dlog + d log
i
2
m
d
i2[k]
X

/k =
i2[k]

⌅

which completes the proof.
C.2

Proof of Theorem 2

Theorem 2 (Average case classification bound). Let H be a hypothesis class with V Cdim(H) = d.
bS }k are the empirical distributions generated with m i.i.d. samples from each domain, and
If {D
i i=1
b
DT is the empirical
P distribution on the target domain generated from mk samples without labels,
then, 8↵ 2 Rk+ , i2[k] ↵i = 1, and for 0 < < 1, w.p.b. at least 1, for all h 2 H, we have:
s
◆
✓
◆!
X ✓
1
1
1
km
bT ; DbS ) + ↵ + O"T (h) ↵i "bSi (h) + dH H (Dlog + d log
(3)
i
2
km
d
i2[k]
P
where ↵ is the risk of the optimal hypothesis on the mixture source domain i2[k] ↵i Si and T .
Proof. Consider a mixture distributionof the k source domains where the mixture weight is givenP:=by ↵. Denote it as DS̃
i2[k] ↵i DSi . Let S̃ be the combined samples from k domains, thenequivalently S̃ can be seen as a sample of size km sampled i.i.d. from DS̃ . Apply Thm. 1 using DT
as the target domain and DS̃ as the source domain, we know that for 0 < < 1, w.p.b. at least 1,!
r1
d log(km/d) + log(1/ )b ,DbT ) + ↵ + O"T (h)  "bS̃ (h) + dH H (D
(8)
S̃
2
km
On the other hand, for 8h 2 H, we have:"bS̃ (h) =

X

i2[k]

↵i "bSi (h)b ,DbT ) as follows:
and we can upper bound dH H (DS̃b ,DbT ) = 2 sup | Pr(A)dH H ( D
S̃

A2AH

=2

H

sup

A2AH

2
2
=

H

sup
A2AH

X

i2[k]

X

i2[k]

H

↵i

|

b
D
S̃

X

↵i ( Pr (A)
bS
D
i

i2[k]

X

i2[k]

↵i | Pr (A)

sup
A2AH

Pr (A)|bTD

H

Pr (A))|bT
D

Pr (A)|

bS
D
i

bT
D

bS
D
i

bT
D

| Pr (A)bS , DbT )↵ i dH H ( Di

Pr (A)|

where the first inequality is due to the triangle inequality and the second inequality is by the subP
b ,D
bT )
additivity of the sup function. Replace "bS̃ (h) with i2[k] ↵i "bSi (h) and upper bound dH H (DS̃PbS , DbT ) in (8) completes the proof.
by↵ i dH H ( D
⌅
i2[k]

i

14

C.3

Proof of Theorem 3

Before we give a full proof, we first describe the proof strategy at a high level. Roughly, the proof
contains three parts. The first part contains a reduction from regression to classification by relating
the pseudo-dimension of the hypothesis class H and its corresponding threshold binary classifiers.
The second part uses H-divergence to relate the source and target domains when they differ. The lastpart uses standard generalization analysis with pseudo-dimension for regression, when the source andtarget domains coincide.
C.3.1

First Part of the Proof

To begin with, let H = {h : X ! [0, 1]} be a set of bounded real-valued functions from the input
space X to [0, 1]. We use P dim(H) to denote the pseudo-dimension of H, and let P dim(H) = d.
We first prove the following lemma that will be used in proving the main theorem:
Lemma 1. For h, h0 2 H := {h : X ! [0, 1]}, where P dim(H) = d, and for any distribution DS ,DT over X ,1|"S (h, h0 ) "T (h, h0 )|  dH̄ (DS , DT )20
where H̄ := {I|h(x) h0 (x)|>t : h, h 2 H, 0  t  1}.
Proof. By definition, for 8h, h0 2 H, we have:|"S (h, h0 )"T (h, h0 )|  sup |"S (h, h0 )h,h0 2H= suph,h0 2H"T (h, h0 )|Ex⇠S [|h(x)h0 (x)|]

Ex⇠T [|h(x)h0 (x)|](9)

Since ||h||1  1, 8h 2 H, then 0  |h(x) h0 (x)|  1, 8x 2 X , h, h0 2 H. We now use Fubini’s
theorem to bound Ex⇠S [|h(x) h0 (x)|] Ex⇠T [|h(x) h0 (x)|] :Ex⇠S [|h(x)h0 (x)|] Ex⇠T [|h(x) h0 (x)|]Z 1⇣=
Pr(|h(x) h0 (x)| > t)Pr(|h(x)h0 (x)| > t)h0 (x)| > t)Pr(|h(x)h0 (x)| > t) dt

S

0



Z 1

Pr(|h(x)
S

0

 sup

t2[0,1]

Pr(|h(x)STTh0 (x)| > t)Pr(|h(x)T⌘dth0 (x)| > t)

Now in view of (9) and H̄, we have:
sup

sup

S

= sup | Pr(h̄(x) = 1)
h̄2H̄

S

= sup | Pr(A)
A2AH̄

S

h0 (x)| > t)Pr(|h(x)h,h0 2H t2[0,1]Pr(|h(x)Th0 (x)| > t)Pr(h̄(x) = 1)|
T

Pr(A)|
T1= dH̄ (DS , DT )2
Combining all the inequalities above finishes the proof.
Next we bound P dim(|H H|):
Lemma 2. If P dim(H) = d, then P dim(|H⌅

H|)  2d.

Proof. By the definition of pseudo-dimension, we immediately have V Cdim(H̄) = P dim(|H H|).
Next observe that each function g 2 H̄ could be represented as a two layer linear threshold neuralnetwork, with two hidden units, one bias input unit and one output unit. Specifically, since|h(x)h0 (x)| > t () max{h(x)15h0 (x)

t, h0 (x)h(x)

t} > 0which is also equivalent tosgn(h(x)h0 (x)t) + sgn(h0 (x)h(x)t) > 0(10)

The above expression can then be implemented by a two layer one output linear threshold neuralnetwork. Hence from [3, Chapter 6, 8], the VC dimension of H̄ is at most twice of the pseudodimension of H, completing the proof.
⌅
C.3.2

Second Part of the Proof

One technical lemma we will frequently use is the triangular inequality w.r.t. "D (h), 8h 2 H:
Lemma 3. For any hypothesis class H and any distribution D on X , the following triangularinequality holds:
8h, h0 , f 2 H, "D (h, h0 )  "D (h, f ) + "D (f, h0 )Proof.
"D (h, h0 ) = Ex⇠D [|h(x) h0 (x)|]  Ex⇠D [|h(x) f (x)|+|f (x) f (x)|] = "D (h, f )+"D (f, h0 )⌅Now we prove the following lemma in the regression setting when there is only one source domain
and one target domain.
Lemma 4. Let H be a set of real-valued function from X to [0, 1], and DS , DT be the source andtarget distributions, respectively. Define H̄ := {I|h(x) h0 (x)|>t : h, h0 2 H, 0  t  1}. Then
8h 2 H, the following inequality holds:
1"T (h)  "S (h) + dH̄ (DT ; DS ) +
2

where

:= inf h0 2H "S (h0 ) + "T (h0 ).

Proof. Let h⇤ := arg minh0 2H "S (h0 ) + "T (h0 ). For 8h 2 H:

"T (h)  "T (h⇤ ) + "T (h, h⇤ )= "T (h⇤ ) + "T (h, h⇤ ) "S (h, h⇤ ) + "S (h, h⇤ ) "T (h⇤ ) + |"T (h, h⇤ ) "S (h, h⇤ )| + "S (h, h⇤ )1 "T (h⇤ ) + "S (h, h⇤ ) + dH̄ (DT , DS )2
1⇤
 "T (h ) + "S (h) + "S (h⇤ ) + dH̄ (DT , DS )2
1= "S (h) + dH̄ (DT ; DS ) +2
The first and fourth inequalities are by the triangle inequality, and the third one is from Lemma. 1.
C.3.3

⌅

Third Part of the Proof

In this part of the proof, we use concentration inequalities to bound the source domain error "S (h)and the divergence dH̄ (DT ; DS ) in Lemma 4.

We first introduce the following generalization theorem in the regression setting when the source andtarget distributions are the same:
Lemma 5 (Thm. 10.6, [36]). Let H be a family of real-valued functions from X to [0, 1]. Assume
that P dim(H) = d. Then, for 8 > 0, w.p.b. at least 1
over the choice of a sample of size m,
the following inequality holds for all h 2 H:
s ✓
◆!
1
1
m
"(h)  "b(h) + O
log + d logmd16The next lemma bounds the H-divergence between the population distribution and its corresponding
empirical distribution:
Lemma 6. Let DS and DT be the source and target distribution over X , respectively. Let H be aclass of real-valued functions from X to [0, 1], with P dim(H) = d. Define H̄ := {I|h(x) h0 (x)|>t :h, h0 2 H, 0  t  1}. If S and T are the empirical distributions of DS and DT generated with mi.i.d. samples from each domain, then, for 0 < < 1, w.p.b. at least 1, we have:
s ✓
◆!
1
1
m
log + d log
dH̄ (DS ; DT )  dH̄ (S; T ) + O
mdProof. By the definition of pseudo-dimension, we have V Cdim(H̄) = P dim(|H H|). Now from
Lemma 2, P dim(|H H|)  2P dim(H) = 2d, so V Cdim(H̄)  2d. The lemma then follows
from Ben-David et al. [8, Lemma 1] using standard concentration inequality.
⌅
C.3.4

Proof of the Generalization Bound under Regression Setting

We first prove a generalization bound for regression problem when there is only one source domain
and one target domain. The extension to multiple source domains follows exactly as the proof ofThm. 2.
bS
Theorem 4. Let H be a set of real-valued function from X to [0, 1] with P dim(H) = d. Let D
bT ) be the empirical distribution induced by sample of size m drawn from DS (DT ). Then w.p.b. at(Dleast 1, 8h 2 H,!
r
1
d log(m/d) + log(1/ )bb"T (h)  "bS (h) + dH̄ (DS , DT ) + + O
(11)
2
m
where

= inf h0 2H "S (h0 ) + "T (h0 ) and H̄ := {I|h(x) h0 (x)|>t : h, h0 2 H, 0  t  1}.

Proof. Combine Lemma 4, Lemma 5 and Lemma 6 using union bound finishes the proof.

D⌅

Details about Experiments

In this section, we describe more details about the datasets and the experimental settings. We extensively evaluate the proposed methods on three datasets: 1). We first evaluate our methods on Amazon
Reviews dataset [11] for sentiment analysis. 2). We evaluate the proposed methods on the digits
classification datasets including MNIST [29], MNIST-M [17], SVHN [37], and SynthDigits [17].
3). We further evaluate the proposed methods on the public dataset WebCamT [52] for vehicle
counting. It contains 60,000 labeled images from 12 city cameras with different distributions. Dueto the substantial difference between these datasets and their corresponding learning tasks, we will
introduce more detailed dataset description, network architecture, and training parameters for eachdataset respectively in the following subsections.
D.1

Details on Amazon Reviews evaluation

Amazon reviews dataset includes four domains, each one composed of reviews on a specific kindof product (Books, DVDs, Electronics, and Kitchen appliances). Reviews are encoded as 5000
dimensional feature vectors of unigrams and bigrams. The labels are binary: 0 if the product is ranked
up to 3 stars, and 1 if the product is ranked 4 or 5 stars.
We take one product domain as target and the other three as source domains. Each source domain
has 2000 labeled examples and the target test set has 3000 to 6000 examples. We implement theHard-Max and Soft-Max methods based on a basic network with one input layer (5000 units) andthree hidden layers (1000, 500, 100 units). The network is trained for 50 epochs with dropout rate
0.7. We compare Hard-Max and Soft-Max with three baselines: Baseline 1: MLPNet. It is thebasic network of our methods (one input layer and three hidden layers), trained for 50 epochs withdropout rate 0.01. Baseline 2: Marginalized Stacked Denoising Autoencoders (mSDA) [11]. It takes
the unlabeled parts of both source and target samples to learn a feature map from input space to a17new representation space. As a denoising autoencoder algorithm, it finds a feature representationfrom which one can (approximately) reconstruct the original features of an example from its noisy
counterpart. Baseline 3: DANN. We implement DANN based on the algorithm described in [17] withthe same basic network as our methods. Hyper parameters of the proposed and baseline methods are
selected by cross validation. Table 4 summarizes the network architecture and some hyper parameters.
Table 4: Network parameters for proposed and baseline methods
MethodMLPNetDANN
MDAN

Input layer
5000
5000
5000

Hidden layers(1000, 500, 100)
(1000, 500, 100)
(1000, 500, 100)Epochs50
50
50

Dropout
0.01
0.01
0.7

Domains
N/A
1
3

Adaptation weight
N/A
0.01
0.1

N/A
N/A
10

To validate the statistical significance of the results, we run a non-parametric Wilcoxon signed-ranked
test for each task to compare Soft-Max with the other competitors, as shown in Table 5. Each cellcorresponds to the p-value of a Wilcoxon test between Soft-Max and one of the other methods, under
the null hypothesis that the two paired samples have the same mean. From these p-values, we see
Soft-Max is convincingly better than other methods.

MLPNetSoft-Max
B
D
E
K

D.2

0.550
0.000
0.066
0.306

Table 5: p-values under Wilcoxon test.
mSDA
Best-Single-DANN Combine-DANN
Soft-Max
Soft-Max
Soft-Max
0.101
0.072
0.000
0.001

0.521
0.000
0.097
0.001

0.013
0.051
0.150
0.239

Hard-Max
Soft-Max
0.946
0.000
0.022
0.008

Details on Digit Datasets evaluation

We evaluate the proposed methods on the digits classification problem. Following the experiments
in [17], we combine four popular digits datasets-MNIST, MNIST-M, SVHN, and SynthDigits tobuild the multi-source domain dataset. MNIST is a handwritten digits database with 60, 000 training
examples, and 10, 000 testing examples. The digits have been size-normalized and centered in a
28 ⇥ 28 image. MNIST-M is generated by blending digits from the original MNIST set over patches
randomly extracted from color photos from BSDS500 [4, 17]. It has 59, 001 training images and9, 001 testing images with 32 ⇥ 32 resolution. An output sample is produced by taking a patch
from a photo and inverting its pixels at positions corresponding to the pixels of a digit. For DA
problems, this domain is quite distinct from MNIST, for the background and the strokes are no longer
constant. SVHN is a real-world house number dataset with 73, 257 training images and 26, 032
testing images. It can be seen as similar to MNIST, but comes from a significantly harder, unsolved,
real world problem. SynthDigits consists of 500; 000 digit images generated by Ganin et al. [17]from WindowsTM fonts by varying the text, positioning, orientation, background and stroke colors,
and the amount of blur. The degrees of variation were chosen to simulate SVHN, but the two datasets
are still rather distinct, with the biggest difference being the structured clutter in the background of
SVHN images.
We take MNIST-M, SVHN, and MNIST as target domain in turn, and the remaining three as sources.
We implement the Hard-Max and Soft-Max versions according to Alg. 1 based on a basic network,
as shown in Fig. 4. The baseline methods are also built on the same basic network structure to put
them on a equal footing. The network structure and parameters of MDAN are illustrated in Fig. 4.
The learning rate is initialized by 0.01 and adjusted by the first and second order momentum in the
training process. The domain adaptation parameter of MDAN is selected by cross validation. In eachmini-batch of MDAN training process, we randomly sample the same number of unlabeled target
images as the number of the source images.
18

Figure 4: MDAN network architecture for digit classification
D.3

Details on WebCamT Vehicle Counting

WebCamT is a public dataset for large-scale city camera videos, which have low resolution (352⇥240),
low frame rate (1 frame/second), and high occlusion. WebCamT has 60, 000 frames annotatedwith rich information: bounding box, vehicle type, vehicle orientation, vehicle count, vehicle reidentification, and weather condition. The dataset is divided into training and testing sets, with
42,200 and 17,800 frames, respectively, covering multiple cameras and different weather conditions.
WebCamT is an appropriate dataset to evaluate domain adaptation methods, for it covers multiple city
cameras and each camera is located in different intersection of the city with different perspectives andscenes. Thus, each camera data has different distribution from others. The dataset is quite challenging
and in high demand of domain adaptation solutions, as it has 6, 000, 000 unlabeled images from
200 cameras with only 60, 000 labeled images from 12 cameras. The experiments on WebCamT
provide an interesting application of our proposed MDAN: when dealing with spatially and temporally
large-scale dataset with much variations, it is prohibitively expensive and time-consuming to label
large amount of instances covering all the variations. As a result, only a limited portion of the dataset
can be annotated, which can not cover all the data domains in the dataset. MDAN provide an effective
solution for this kind of application by adapting the deep model from multiple source domains to theunlabeled target domain.
We evaluate the proposed methods on different numbers of source cameras. Each source camera
provides 2000 labeled images for training and the test set has 2000 images from the target camera.
In each mini-batch, we randomly sample the same number of unlabeled target images as the source
images. We implement the Hard-Max and Soft-Max version of MDAN according to Alg. 1, based on
the basic vehicle counting network FCN described in [52]. Please refer to [52] for detailed networkarchitecture and parameters. The learning rate is initialized by 0.01 and adjusted by the first andsecond order momentum in the training process. The domain adaptation parameter is selected bycross validation. We compare our method with two baselines: Baseline 1: FCN. It is our basic
network without domain adaptation as introduced in work [52]. Baseline 2: DANN. We implement
DANN on top of the same basic network following the algorithm introduced in work [17].

E

More Related WorkA number of adaptation approaches have been studied in recent years. From the theoretical aspect,several theoretical results have been derived in the form of upper bounds on the generalization target
error by learning from the source data. A keypoint of the theoretical frameworks is estimating
the distribution shift between source and target. Kifer et al. [27] proposed the H-divergence tomeasure the similarity between two domains and derived a generalization bound on the target domainusing empirical error on the source domain and the H-divergence between the source and the target.
This idea has later been extended to multisource domain adaptation [9] and the corresponding
generalization bound has been developed as well. Ben-David et al. [8] provide a generalization boundfor domain adaptation on the target risk which generalizes the standard bound on the source risk.
This work formalizes a natural intuition of DA: reducing the two distributions while ensuring a low
19

Figure 5: Locations of the source&target camera map.
error on the source domain and justifies many DA algorithms. Based on this work, Mansour et al.
[33] introduce a new divergence measure: discrepancy distance, whose empirical estimate is basedon the Rademacher complexity [28] (rather than the VC-dim). Other theoretical works have also
been studied such as [32] that derives the generalization bounds on the target error by taking use of
the robustness properties introduced in [49]. See [13, 35] for more details.
Following the theoretical developments, many DA algorithms have been proposed, such as instancebased methods [44]; feature-based methods [6]; and parameter-based methods [15]. The generalapproach for domain adaptation starts from algorithms that focus on linear hypothesis class [12, 18].
The linear assumption can be relaxed and extended to the non-linear setting using the kernel trick,leading to a reweighting scheme that can be efficiently solved via quadratic programming [21].
Recently, due to the availability of rich data and powerful computational resources, non-linear
representations and hypothesis classes have been increasingly explored [2, 5, 11, 17, 20]. This lineof work focuses on building common and robust feature representations among multiple domains
using either supervised neural networks [20], or unsupervised pretraining using denoising autoencoders [47, 48].
Recent studies have shown that deep neural networks can learn more transferable features forDA [14, 20, 50]. Bousmalis et al. [10] develop domain separation networks to extract image
representations that are partitioned into two subspaces: domain private component and cross-domainshared component. The partitioned representation is utilized to reconstruct the images from both
domains, improving the DA performance. Reference [30] enables classifier adaptation by learning
the residual function with reference to the target classifier. The main-task of this work is limited tothe classification problem. Ganin et al. [17] propose a domain-adversarial neural network to learn
the domain indiscriminate but main-task discriminative features. Although these works generally
outperform non-deep learning based methods, they only focus on the single-source-single-target DA
problem, and much work is rather empirical design without statistical guarantees. Hoffman et al.
[23] present a domain transform mixture model for multisource DA, which is based on non-deeparchitectures and is difficult to scale up.
Adversarial training techniques that aim to build feature representations that are indistinguishable
between source and target domains have been proposed in the last few years [2, 17]. Specifically,
one of the central ideas is to use neural networks, which are powerful function approximators, toapproximate a distance measure known as the H-divergence between two domains [7, 8, 27]. The
overall algorithm can be viewed as a zero-sum two-player game: one network tries to learn feature
representations that can fool the other network, whose goal is to distinguish representations generated
from the source domain between those generated from the target domain. The goal of the algorithm is
to find a Nash-equilibrium of the game, or the stationary point of the min-max saddle point problem.
Ideally, at such equilibrium state, feature representations from the source domain will share the same
distributions as those from the target domain, and, as a result, better generalization on the target
domain can be expected by training models using only labeled instances from the source domain.

20