Domain Adaptation with Asymmetrically-Relaxed Distribution Alignment

Introduction

Despite breakthroughs in supervised deep learning across a variety of challenging tasks, current techniques depend precariously on the i.i.d. assumption. Unfortunately, real-world settings often demand not just generalization to unseen examples but robustness under a variety of shocks to the data distribution. Ideally, our models would leverage unlabeled test data, adapting in real time to produce improved predictions. Unsupervised domain adaptation formalizes this problem as learning a classifier from labeled source domain data and unlabeled data from a target domain, to maximize performance on the target distribution.

Without further assumptions, guarantees of target-domain accuracy are impossible (Ben-David et al., 2010b). However, well-chosen assumptions can make possible algorithms with non-vacuous performance guarantees. For example, under the covariate shift assumption (Heckman, 1977; Shimodaira, 2000), although the input marginals can vary between source and target ($p_{S}(x)\neq p_{T}(x)$), the conditional distribution of the labels (given features) exhibits invariance across domains ($p_{S}(y|x)=p_{T}(y|x)$). Some consider the reverse setting label shift (Saerens et al., 2002; Zhang et al., 2013; Lipton et al., 2018), where although the label distribution shifts ($p_{S}(y)\neq p_{T}(y)$), the class-conditional input distribution is invariant ($p_{S}(x|y)=p_{T}(x|y)$). Traditional approaches to both problems require the source distributions’ support to cover the target support, estimating adapted classifiers via importance-weighted risk minimization (Shimodaira, 2000; Huang et al., 2007; Gretton et al., 2009; Yu & Szepesvári, 2012; Lipton et al., 2018).

Problematically, assumptions of contained support are violated in practice. Moreover, most theoretical analyses do not guaranteed target accuracy when the source distribution support does not cover that of the target. A notable exception, Ben-David et al. (2010a) leverages capacity constraints on the hypothesis class to enable generalization to out-of-support samples. However, their results (i) do not hold for high-capacity hypothesis classes, e.g., neural networks; and (ii) do not provide intuitive interpretations on what is sufficient to guarantee a good target domain performance.

A recent sequence of deep learning papers have proposed empirically-justified adversarial training schemes aimed at practical problems with non-overlapping supports (Ganin et al., 2016; Tzeng et al., ). Example problems include generalizing from gray-scale images to colored images or product images on white backgrounds to photos of products in natural settings. While importance-weighting solutions are useless here (with non-overlapping support, weights are unbounded), domain-adversarial networks (Ganin et al., 2016) and subsequently-proposed variants report strong empirical results on a variety of image recognition challenges.

The key idea of domain-adversarial networks is to simultaneously minimize the source error and align the two distributions in representation space. The scheme consists of an encoder, a label classifier, and a domain classifier. During training, the domain classifier is optimized to predict each image’s domain given its encoding. The label classifier is optimized to predict labels from encodings (for source images). The encoder weights are optimized for the twin objectives of accurate label classification (of source data) and fooling the domain classifier (for all data).

Although Ganin et al. (2016) motivate their idea via theoretical results due to Ben-David et al. (2010a), the theory is insufficient to justify their method. Put simply, Ben-David et al. (2010a) bound the test error by a sum of three terms. The domain-adversarial objective minimizes two among these, but this minimization may cause the third term to increase. This is guaranteed to happen when the label distribution shifts between source and target. Consider the case of cat-dog classification with non-overlapping support. Say that the source distribution contains $50\%$ dogs and $50\%$ cats, while the target distribution contains $25\%$ dogs and $75\%$ cats. Successfully aligning these distributions in representation space requires the classifier to predict the same fraction of dogs and cats on source and target. If one achieves $100\%$ accuracy on the source data, then target accuracy will be at most $75\%$ (Figure 1(a)).

In this paper, we propose asymmetrically-relaxed distribution alignment, a relaxed distance for aligning data across domains that can be minimized without requiring latent-space distributions to match exactly. The new distance is minimized whenever the density ratios in representation space from target to source are upper bounded by a certain constant, such that the target representation support is contained in the source representation’s. The relaxed distribution alignment need not lead to a poor classifier on the target domain under label distribution mismatch (Figure 1(b)). We demonstrate theoretically that the relaxed alignment is sufficient for a good target domain performance under a concrete set of assumptions on the data distributions. Further, we propose several practical ways to achieve the relaxed distribution alignment, translating the new distance into adversarial learning objectives. Empirical results on synthetic and real datasets show that incorporating our relaxed distribution alignment loss into adversarial domain adaptation gives better classification performance on the target domain. We make the following key contributions:

We propose an asymmetrically relaxed distribution matching objective, overcoming the limitation of standard objectives under label distribution shift.

We provide theoretical analysis demonstrating that under a clear set of assumptions, the asymmetrically relaxed distribution alignment can provide target-domain performance guarantees.

We propose several distances that satisfy the desired properties and are optimizable by adversarial training.

We empirically show that our asymmetrically relaxed distribution matching losses improve target performance when there is a label distribution shift in the target domain, and perform comparably otherwise.

Preliminaries

We are interested in bounding the classification risk of a $(\phi,h)$-pair on the target domain:

The second term in (2) becomes zero if the latent space labeling function is domain-invariant. To see this, we apply

The third term in (2) is zero when $p_{T}^{\phi}$ and $p_{S}^{\phi}$ are the same.

Domain-adversarial learning

Domain-adversarial approaches focus on minimizing the first and third term in (2) jointly. Informally, these approaches minimize the source domain classification risk and the distance between the two distributions in the latent space:

where $D$ is a distance metric between distributions and $\Omega$ is a regularization term. Standard choices of $D$ such as a domain classifier (Jensen-Shannon (JS) divergence Per (Nowozin et al., 2016), there is a slight difference between JS-divergence and the original GAN objective (Goodfellow et al., 2014). We will use the term JS-divergence for the GAN objective. ) (Ganin et al., 2016), Wasserstein distance (Shen et al., 2018) or Maximum Mean Discrepancy (Huang et al., 2007) have the property that $D(p_{S}^{\phi},p_{T}^{\phi})=0$ if $p_{S}^{\phi}\equiv p_{T}^{\phi}$ and $D(p_{S}^{\phi},p_{T}^{\phi})>0$ otherwise. In the next section, we will show that minimizing (4) with such $D$ will lead to undesirable performance and propose an alternative objective to align $p_{S}^{\phi}$ and $p_{T}^{\phi}$ instead of driving them to be identically distributed.

A Motivating Scenario

If $D(p_{S}^{\phi},p_{T}^{\phi})=0$ if and only if $p_{S}^{\phi}\equiv p_{T}^{\phi}$, $\mathcal{E}_{S}(\phi,h)=D(p_{S}^{\phi},p_{T}^{\phi})=0$ indicates $\mathcal{E}_{T}(\phi,h)\geq\left\lvert\rho_{S}-\rho_{T}\right\rvert$.

The proof follows the intuition of Figure 1(a): If $\rho_{S}<\rho_{T}$, the best we can do is to map $\rho_{T}-\rho_{S}$ proportion of positive samples from the target inputs to regions of latent space corresponding to negative examples from the source domain while maintaining the label consistency for remaining ones. Switching the term positive/negative gives a similar argument for $\rho_{T}<\rho_{S}$. Proposition 3.1 says that if there is a label distribution mismatch $\rho_{T}\neq\rho_{S}$, minimizing the objective (4) to zero imposes a positive lower bound on the target error. This is especially problematic in cases where a perfect pair $\phi,h$ may exist, achieving zero error on both source and target data (Figure 1(b)).

Asymmetrically-relaxed distribution alignment It may appear contradictory that minimizing the first and third term of (2) to zero guarantees a positive $\mathcal{E}_{T}(\phi,h)$ and thus a positive second term when there exists a pair of $\phi,h$ such that $\mathcal{E}_{T}(\phi,h)=0$ (all three terms are zero). However, this happens because although $D(p_{S}^{\phi},p_{T}^{\phi})=0$ is a sufficient condition for the third term of (2) to be zero, it is not a necessary condition. We now examine the third term of (2):

This expression (5) shows that if the source error $\mathcal{E}_{S}(\phi,h)$ is zero then it is sufficient to say the third term of (2) is zero when the density ratio $p_{T}^{\phi}(z)/p_{S}^{\phi}(z)$ is upper bounded by some constant for all $z$. Note that it is impossible to bound $p_{T}^{\phi}(z)/p_{S}^{\phi}(z)$ by a constant that is smaller than $1$ so we write this condition as $\sup_{z\in\mathcal{Z}}p_{T}^{\phi}(z)/p_{S}^{\phi}(z)\leq 1+\beta$ for some $\beta\geq 0$. Note that this is a relaxed condition compared with $p_{T}^{\phi}(z)\equiv p_{S}^{\phi}(z)$, which is a special case with $\beta=0$.

Relaxing the exact matching condition to the more forgiving bounded density ratio condition makes it possible to obtain a perfect target domain classifier in many cases where the stricter condition does not, by requiring only that the (latent space) target domain support is contained in the source domain support, as shown in Figure 1(b). The following proposition states that our relaxed matching condition does not suffer from the previously-described problems concerning shifting label distributions (Proposition 3.1), and provides intuition regarding just how large $\beta$ may need to be to admit a perfect target domain classifier.

For every $\rho_{S},\rho_{T}$, there exists a construction of $(p_{S},p_{T},\phi,h)$ such that $\mathcal{E}_{S}(\phi,h)=0$, $\mathcal{E}_{T}(\phi,h)=0$ and $\sup_{z\in\mathcal{Z}}p_{T}^{\phi}(z)/p_{S}^{\phi}(z)\leq\max\left\{\frac{\rho_{T}}{\rho_{S}},\frac{1-\rho_{T}}{1-\rho_{S}}\right\}$.

Given this motivation, we propose relaxing from exact distribution matching to bounding the density ratio in the domain-adversarial learning objective (4). We call this asymmetrically-relaxed distribution alignment since we aim at upper bounding $p_{T}^{\phi}/p_{S}^{\phi}$ (but not $p_{S}^{\phi}/p_{T}^{\phi}$). We now introduce a class of distances between distributions that can be minimized to achieve the relaxed alignment:

Given a family of distributions defined on the same space $\mathcal{Z}$, a distance metric $D_{\beta}$ between distributions is called $\beta$-admissible if $D_{\beta}(p,q)=0$ when $\sup_{z\in\mathcal{Z}}p(z)/q(z)\leq 1+\beta$ and $D_{\beta}(p,q)>0$ otherwise.

Our proposed approach is to replace the typical distribution distance $D$ in the domain-adversarial objective (4) with a $\beta$-admissible distance $D_{\beta}$ so that minimizing the new objective does not necessarily lead to a failure under label distribution shift. However, it is still premature to claim the justification of our approach due to the following issues: (i) We may not be able get a perfect source domain classifier with $\mathcal{E}_{S}(\phi,h)=0$. This also indicates a trade-off in selecting $\beta$ as (a) higher $\beta$ will increase the upper bound ($\beta\mathcal{E}_{S}(\phi,h)$ according to (5)) on the third term in (2) (b) lower $\beta$ will make a good target classifier impossible under label distribution shift. (ii) Minimizing $D_{\beta}(p_{T}^{\phi},p_{S}^{\phi})$ as part of an objective does not necessarily mean that we will obtain a solution with $D_{\beta}(p_{T}^{\phi},p_{S}^{\phi})=0$. There may still be some proportion of samples from the target domain lying outside the support of source domain in the latent space $\mathcal{Z}$. In this case, the density ratio $p_{T}^{\phi}/p_{S}^{\phi}$ is unbounded and (5) becomes vacuous. (iii) Even when we are able optimize the objective perfectly, i.e., $\mathcal{E}_{S}(\phi,h)=D_{\beta}(p_{S}^{\phi},p_{T}^{\phi})=0$, with a proper choice of $\beta$ such that there exists $\phi,h$ such that $\mathcal{E}_{T}(\phi,h)=0$ holds simultaneously (e.g. Figure 1(b), Proposition 3.2), it is still not guaranteed that such $\phi,h$ is learned (e.g. Figure 2(a)), as the second term of (2) is unbounded and changes with $\phi$. Put simply, the problem is that although there may exist alignments perfect for prediction, there also exist other alignments that satisfy the objective but predict poorly (on target data). To our knowledge this problem effects all domain-adversarial methods proposed in the literature, and how to theoretically guarantee that the desired alignment is learned remains an open question.

Next, we theoretically study the target classification error under asymmetrically-relaxed distribution alignment. Our analysis resolves the above issues by (i) working with imperfect source domain classifier and relaxed distribution alignment; and (ii) providing concrete assumptions under which a good target domain classifier can be learned.

Bounding the Target Domain Error

In a manner similar to (2), Ben-David et al. (2007, 2010a) bound the target domain error by a sum of three terms: (i) the source domain error (ii) an $\mathcal{H}$-divergence between $p_{S}^{\phi}$ and $p_{T}^{\phi}$ (iii) the best possible classification error that can be achieved on the combination of $p_{S}^{\phi}$ and $p_{T}^{\phi}$. We motivate our analysis by explaining why their results are insufficient to give a meaningful bound for domain-adversarial learning approaches. From a theoretical upper bound, we may desire to make claims in the following pattern:

Let $\mathcal{M}_{\mathcal{A}}$ be a set of models that satisfy a set of properties $\mathcal{A}$ (e.g. with low training error), and $\mathcal{B}$ be a set of assumptions on the data distributions $(p_{S},p_{T},f)$. For any given model $M\in\mathcal{M}_{\mathcal{A}}$, its performance can be bounded by a certain quantity, i.e. $\mathcal{E}_{T}(M)\leq\epsilon_{\mathcal{A},\mathcal{B}}$.

Ideally, $\mathcal{A}$ should be observable on available data information (i.e. without knowing target labels), and assumptions $\mathcal{B}$ should be model-independent (independent of which model $M=(\phi,h)$ is learned among $\mathcal{M}_{\mathcal{A}}$). In the results of Ben-David et al. (2007, 2010a), terms (i) and (ii) are observable so $\mathcal{A}$ can be set as achieving low quantities on these two terms. Since term (iii) is unobservable we may want to make assumptions on it. This term, however, is model-dependent when $\phi$ is learned jointly. To make a model-independent assumption on term (iii), we need to take the supremum over all $(\phi,h)\in\mathcal{M}_{\mathcal{A}}$, i.e., all possible models that achieve low values on (i) and (ii). This supremum can be vacuous without further assumptions as a cross-label mapping may also achieve low source error and distribution alignment (e.g. Figure 2(a) v.s. Figure 1(b)). Moreover, when $\mathcal{H}$ contains all possible binary classifiers, the $\mathcal{H}$-divergence is minimized only if the two distributions are the same, thus suffering the same problem as Proposition 3.1 and is therefore not suitable for motivating a learning objective.

To overcome these limitations, we propose a new theoretical bound on the target domain error which (a) treats the difference between $p_{S}^{\phi}$ and $p_{T}^{\phi}$ asymmetrically and (b) bounds the label consistency (second term in 2) by exploiting the Lipschitz-ness of $\phi$ as well as the separation and connectedness of data distributions. Our result can be interpreted as a combination of observable model properties and unobservable model-independent assumptions while being non-vacuous: it is able to guarantee correct classification for (some fraction of) data points from the target domain even where the source domain has zero density.

We introduce our result with the following construction:

The following statements hold simultaneously:

(Lipschitzness of representation mapping.) $\phi$ is $L$-Lipschitz: $d_{\mathcal{Z}}(\phi(x_{1}),\phi(x_{2}))\leq Ld_{\mathcal{X}}(x_{1},x_{2})$ for any $x_{1},x_{2}\in\mathcal{X}$.

(Imperfect asymmetrically-relaxed distribution alignment.) For some $\beta\geq 0$, there exist a set $B\subset\mathcal{Z}$ such that $\frac{p_{T}^{\phi}(z)}{p_{S}^{\phi}(z)}\leq 1+\beta$ holds for all $z\in B$ and $p_{T}^{\phi}(B)\geq 1-\delta_{1}$.

(Separation of source domain in the latent space.) There exist two sets $C_{0},C_{1}\subset\mathcal{X}$ that satisfy:

$p_{S}(C_{0}\cup C_{1})\geq 1-\delta_{2}$.

For $i\in\{0,1\}$, $f(x)=i$ for all $x\in C_{i}$.

$\inf_{z_{0}\in\phi(C_{0}),z_{1}\in\phi(C_{1})}d_{\mathcal{Z}}(z_{0},z_{1})\geq\Delta>0$.

Note that this construction does not require any information about target domain labels so the statements can be viewed as observable properties of $\phi$. We now introduce our model-independent assumption:

(Connectedness from target domain to source domain.) Given constants $(L,\beta,\Delta,\delta_{1},\delta_{2},\delta_{3})$, assume that, for any $B_{S},B_{T}\subset\mathcal{X}$ with $p_{S}(B_{S})\geq 1-\delta_{2}$ and $p_{T}(B_{T})\geq 1-\delta_{1}-(1+\beta)\delta_{2}$, there exists $C_{T}\subset B_{T}$ that satisfies the following conditions:

For any $x\in C_{T}$, there exists $x^{\prime}\in C_{T}\cap B_{S}$ such that one can find a sequence of points $x_{0},x_{1},...,x_{m}\in C_{T}$ with $x_{0}=x$, $x_{m}=x^{\prime}$, $f(x)=f(x^{\prime})$ and $d_{\mathcal{X}}(x_{i-1},x_{i})<\frac{\Delta}{L}$ for all $i=1,...,m$.

Given a $L$-Lipschitz mapping $\phi\in\Phi$ and a binary classifier $h\in\mathcal{H}$, if $\phi$ satisfies the properties in Construction 4.1 with constants $(L,\beta,\Delta,\delta_{1},\delta_{2})$, and Assumption 4.2 holds with the same set of constants plus $\delta_{3}$, then the target domain error can be bounded as

Notice that it is always possible to make Construction 4.1 by adjusting the constants $L,\beta,\Delta,\delta_{1},\delta_{2}$. Given these constants, Assumption 4.2 can always be satisfied by adjusting $\delta_{3}$. So Theorem 4.3 is a general bound.

The key challenge in bounding $\mathcal{E}_{T}(\phi,h)$ is to bound the second term in (2) by identifying sufficient conditions that prevent cross-label mapping (e.g. Figure 2(a)). To resolve this challenge, we exploit the fact that if there exist a path from a target domain sample to a source domain sample in the input space $\mathcal{X}$ and all samples along the path are mapped into two separate regions in the latent space (due to distribution alignment), then these two connected samples cannot be mapped to different regions, as shown in Figure 2(b).

2 Example of a perfect target domain classifier

To interpret our result, we construct a simple situation where $\mathcal{E}_{T}(\phi,h)=0$ is guaranteed when the domain adversarial objective with relaxed distribution alignment is minimized to zero, exploiting pure data-dependent assumptions:

Proof follows directly by observing that a construction of $\delta_{1}=\delta_{2}=\delta_{3}=0$ exists in Theorem 4.3. A simple example that satisfies Assumption 4.4 is Figure 2(b). For a real world example, consider the cat-dog classification problem. Say that source domain contains small-to-medium cats and dogs while target domain contains medium-to-large cats and dogs. The target domain consists of clusters (e.g. cats and dogs, or multiple sub-categories) and each of them overlaps with the source domain (the medium ones).

Asymmetrically-relaxed distances

So far, we have motivated the use of asymmetrically-relaxed distribution alignment which aims at bounding $p_{T}^{\phi}/p_{S}^{\phi}$ by a constant instead of driving towards $p_{S}^{\phi}\equiv p_{T}^{\phi}$. More specifically, we propose to use a $\beta$-admissible (Definition 3.3) distance $D_{\beta}$ in objective (4) to align the source and target encodings rather than the standard distances corresponding an adversarial domain classifier. In this section, we derive several $\beta$-admissible distance metrics that can be practically minimized with adversarial training. More specifically, we propose three types of distances (i) f-divergences; (ii) modified Wasserstein distance; (iii) reweighting distances; and demonstrate how to optimize them by adversarial training.

where $C_{f,\beta}=-f(\frac{1}{1+\beta})+f^{\prime}(\frac{1}{1+\beta})\frac{1}{1+\beta}-f^{\prime}(\frac{1}{1+\beta})$.

It can be shown that $\bar{f}_{\beta}$ is continuous, convex and $\bar{f}_{\beta}(1)=0$. As we already explained, $D_{\bar{f}_{\beta}}(p,q)=0$ if and only if $\frac{p(z)}{q(z)}\leq 1+\beta$ for all $z$. Hence is $D_{\bar{f}_{\beta}}$ is $\beta$-admissible.

Adversarial training According to Nowozin et al. (2016), adversarial training (Goodfellow et al., 2014) can be viewed as minimizing the dual form of $f$-divergences

Plugging in the corresponding $f$ for JS-divergence gives

where $g(z)$ can be parameterized by a neural network with sigmoid output as typically used in adversarial training.

2 Wasserstein distance

The idea behind modifying the Wasserstein distance is to model the optimal transport from $p$ to the region where distributions have $1+\beta$ maximal density ratio with respect to $q$. We define the relaxed Wassertein distance as

where $\prod_{\beta}(p,q)$ is defined as the set of joint distributions $\gamma$ over $\mathcal{Z}\times\mathcal{Z}$ such that

$W_{\beta}$ is $\beta$-admissible since no transportation is needed if $p$ already lies in the qualified region with respect to $q$.

Adversarial training Following the derivation for the original Wasserstein distance, the dual form becomes

Optimization with adversarial training can be done by parameterizing $g$ as a non-negative function (e.g. with soft-plus output $\log(1+e^{x})$ or RELU output $\max(0,x)$) and following Arjovsky et al. (2017); Gulrajani et al. (2017) to enforce its Lipschitz continuity approximately.

3 Reweighting distance

Given any distance metric $D$, a generic way to make it $\beta$-admissible is to allow reweighting for one of the distances within a $\beta$-dependent range. The relaxed distance is then defined as the minimum achievable distance by such reweighting.

Then the relaxed distance can be defined as

Such $D_{\beta}$ is $\beta$-admissible since the set $\{q_{w}:w\in\mathcal{W}_{\beta,q}\}$ is exactly the set of $p$ such that $\sup_{z\in\mathcal{Z}}p(z)/q(z)\leq 1+\beta$.

Adversarial training We propose an implicit-reweighting-by-sorting approach to optimize $D_{\beta}$ without parameterizing the function $w$ when $D$ can be optimized by adversarial training. Adversarially trainable $D$ shares a general form as

where $f_{1}$ and $f_{2}$ are monotonically increasing functions. According to (9), the relaxed distance can be written as

One step of alternating minimization on $D_{\beta}$, could consist of fixing $p,q,g$ and optimizing $w$. Then the problem becomes

Observe that the optimal solution to (11) is to assign $w(z)=1$ for the $\frac{1}{1+\beta}$ fraction of $z$ from distribution $q$, where $f_{2}(g(z))$ take the largest values. Based on this observation, we propose to do the following sub-steps when optimizing (11) as an alternating minimization step: (i) Sample a minibatch of $z\sim q$; (ii) Sort these $z$ in descending order according to $f_{2}(g(z))$; (iii) Assign $w(z)=1$ to the first $\frac{1}{1+\beta}$ fraction of the list. Note that this optimization procedure is not justified in principle with mini-batch adversarial training but we found it to work well in our experiments.

Experiments

To evaluate our approach, we implement Domain Adversarial Neural Networks (DANN), (Ganin et al., 2016) replacing the JS-divergence (domain classifier) with our proposed $\beta$-admissible distances (Section 5). Our experiments address the following questions: (i) Does DANN suffer the limitation as anticipated (Section 3) when faced with label distribution shift? (ii) If so, do our $\beta$-admissible distances overcome these limitations? (iii) Absent shifting label distributions, is our approach comparable to DANN?

We implement adversarial training with different $\beta$-admissible distances (Section 5) and compare their performance with vanilla DANN. We name different implementations as follows. (a) Source: source-only training. (b) DANN: JS-divergence (original DANN). (c) WDANN: original Wasserstein distance. (d) fDANN-$\beta$: $\beta$-admissible $f$-divergence, JS-version (7). (e) sDANN-$\beta$: reweighting JS-divergence (10), optimized by our proposed implicit-reweighting-by-sorting. (f) WDANN1-$\beta$: $\beta$-admissible Wasserstein distance (8) with soft-plus on critic output. (g) WDANN2-$\beta$: $\beta$-admissible Wasserstein distance (8) with RELU on critic output. (h) sWDANN-$\beta$: reweighting Wasserstein distance (10), optimized by implicit-reweighting-by-sorting. Adversarial training on Wasserstein distances follows Gulrajani et al. (2017) but uses one-sided gradient-penalty. We always perform adversarial training with alternating minimization (see Appendix for details).

We create a mixture-of-Gaussians binary classification dataset where each domain contains two Gaussian distributions, one per label. For each label, the distributions in source and target domain have a small overlap, validating the assumptions in our analysis. We create a label distribution shift with balanced source data (50% 0’s v.s. 50% 1’s) and imbalanced target data (10% 0’s v.s. 90% 1’s) as shown in Figure 3(a). Table 1 shows the target domain accuracy for different approaches. As expected, vanilla DANN fails under label distribution shift because a proportion of samples from the target inputs are mapped to regions of latent space corresponding to negative samples from the source domain (Figure 3(b)). In contrast, with our $\beta$-admissible distances, domain-adversarial networks are able to adapt successfully (Figure 3(c)), improving target accuracy from 89% (source-only) to 99% accuracy (with adaptation), except the cases where $\beta$ is too small to admit a good target domain classifier (in this case we need $\beta\geq 0.9/0.5-1=0.8$). We also experiment with label-balanced target data (no label distribution shift). All approaches except source-only achieve an accuracy above 99%, so we do not present these results in a separate table.

Real datasets

We experiment with the MNIST and USPS handwritten-digit datasets. For both directions (MNIST $\rightarrow$ USPS and USPS $\rightarrow$ MNIST), we experiment both with and without label distribution shift. The source domain is always class-balanced. To simulate label distribution shift, we sample target data from only half of the digits, e.g. or . Tables 2 and 3 show the target domain accuracy for different approaches with/without label distribution shift. As on synthetic datasets, we observe that DANN performs much worse than source-only training under label distribution shift. Compared to the original DANN, our approaches fair significantly better while achieving comparable performance absent label distribution shift.

Related work

Our paper makes distinct theoretical and algorithmic contributions to the domain adaptation literature. Concerning theory, we provide a risk bound that explains the behavior of domain-adversarial methods with model-independent assumptions on data distributions. Existing theories without assumptions of contained support (Ben-David et al., 2007, 2010a; Ben-David & Urner, 2014; Mansour et al., 2009; Cortes & Mohri, 2011) do not exhibit this property since (i) when applied to the input space, their results are not concerned with domain-adversarial learning as no latent space is introduced, (ii) when applied to the latent space, their unobservable constants/assumptions become $\phi$-dependent, which is undesirable as explained in Section 4. Concerning algorithms, several prior works demonstrate empirical success of domain-adversarial approaches, (Tzeng et al., 2014; Ganin et al., 2016; Bousmalis et al., 2016; Tzeng et al., ; Hoffman et al., 2017; Shu et al., 2018). Among those, Cao et al. (2018a, b) deal with the label distribution shift scenario through a heuristic reweighting scheme. However, their re-weighting presumes that they have a good classifier in the first place, creating a cyclic dependency.

Conclusions

We propose to use asymmetrically-relaxed distribution distances in domain-adversarial learning objectives, replacing standard ones which seek exact distribution matching in the latent space. While overcoming some limitations of the standard objectives under label distribution mismatch, we provide a theoretical guarantee for target domain performance under assumptions on data distributions. As our connectedness assumptions may not cover all cases where we expect domain adaptation to work in practice, (e.g. when the two domains are completely disjoint), providing analysis under other type of assumptions might be of future interest.

This work was made possible by a generous grant from the Center for Machine Learning and Health, a joint venture of Carnegie Mellon University, UPMC, and the University of Pittsburgh, in support of our collaboration with Abridge AI to develop robust models for machine learning in healthcare. We are also supported in this line of research by a generous faculty award from Salesforce Research.

References

Appendix A Proofs

where we use the following fact: For any fixed $z$, $h(z)\in\{0,1\}$, if $h(z)=0$ then $|h(z)-f(x)|=f(x)-h(z)$ for all $x$. Similarly, when $h(z)=1$, we have $|h(z)-f(x)|=h(z)-f(x)$ for all $x$. Thus we can move the integral over $x$ inside the absolute operation. ∎

Applying the fact that $p_{S}^{\phi}(z)=p_{T}^{\phi}(z)$ for all $z\in\mathcal{Z}$,

Let $p_{S}$ be the uniform distribution over $$and$p_{T}$be the uniform distribution over$$. The labeling function$f$is set as$f(x)=1$iff$x\in[0,\rho_{S}]\cup[2,2+\rho_{T}]$such that the definition of$\rho_{S}$and$\rho_{T}$is preserved. We construct the following mapping$\phi$: For$x\in$$\phi(x)=x$. For$x\in[2,2+\rho_{T}]$$\phi(x)=(x-2)\rho_{S}/\rho_{T}$. For$x\in[2+\rho_{T},3]$$\phi(x)=1-(3-x)(1-\rho_{S})/(1-\rho_{T})$.$\phi$maps both source and target data into$$with$p_{S}^{\phi}$to be uniform over$$and$p_{T}^{\phi}(z)=\rho_{T}/\rho_{S}$when$z\in[0,\rho_{S}]$and$p_{T}^{\phi}(z)=(1-\rho_{T})/(1-\rho_{S})$when$z\in[\rho_{S},1]$. Since$p_{S}^{\phi}(z)=1$for all$z\in$we can conclude that$\sup_{z\in\mathcal{Z}}p_{T}^{\phi}(z)/p_{S}^{\phi}(z)\leq\max\left\{\frac{\rho_{T}}{\rho_{S}},\frac{1-\rho_{T}}{1-\rho_{S}}\right\}$ . ∎

Instead of working with Assumption 4.2 we first extend Construction 4.1 with the following addition

(Connectedness from target domain to source domain.) Let $C_{T}\subset\mathcal{X}$ be a set of points in the raw data space that satisfy the following conditions:

$\phi(C_{T})\subset\phi(C_{0}\cup C_{1})$.

For any $x\in C_{T}$, there exists $x^{\prime}\in C_{T}\cap(C_{0}\cup C_{1})$ such that one can find a sequence of points $x_{0},x_{1},...,x_{m}\in C_{T}$ with $x_{0}=x$, $x_{m}=x^{\prime}$, $f(x)=f(x^{\prime})$ and $d_{\mathcal{X}}(x_{i-1},x_{i})<\frac{\Delta}{L}$ for all $i=1,...,m$.

We now proceed to prove bound based on Constructions 4.1 and A.1. Later on we will show that Assumption 4.2 indicates the existence of Construction A.1 so that the bound holds with a combination of Constructions 4.1 and Assumption 4.2.

For the second term of (2), plugging in $r_{U}(z;\phi,h)=\left\lvert h(z)-f^{\phi}_{U}(z)\right\rvert$ gives

Applying $\left\lvert f^{\phi}_{T}(z)-f^{\phi}_{S}(z)\right\rvert\leq f^{\phi}_{T}(z)+f^{\phi}_{S}(z)$ to the first part of (13) gives

Similarly, applying $\left\lvert f^{\phi}_{T}(z)-f^{\phi}_{S}(z)\right\rvert=\left\lvert(1-f^{\phi}_{T}(z))-(1-f^{\phi}_{S}(z))\right\rvert\leq(1-f^{\phi}_{T}(z))+(1-f^{\phi}_{S}(z))$ to the second part of (13) gives

Combining the second part of (14) and the second part of (15)

For $i\in\{0,1\}$ if $x\in C_{i}$ then $f(x)=i$ and $\phi(x)\in C_{i}$. So if $f(x)=1,\phi(x)\in\phi(C_{0})$ or $f(x)=0,\phi(x)\in\phi(C_{1})$ holds we must have $x\notin C_{0}\cup C_{1}$. Therefore, following (16) gives

Now looking at the first part of (14) and the first part of (15)

Next we show that the first part of (18) is . Recall that $\phi(C_{T})\subset\phi(C_{0}\cup C_{1})$ and if $x\in C_{T}$ there exists $x^{\prime}\in C_{T}\cap(C_{0}\cup C_{1})$ with a sequence of points $x_{0},x_{1},...,x_{m}\in C_{T}$ such that $x_{0}=x$, $x_{m}=x^{\prime}$, $f(x)=f(x^{\prime})$ and $d_{\mathcal{X}}(x_{i-1},x_{i})<\frac{\Delta}{L}$ for all $i=1,...,m$. So for $x\in C_{T}$ and $f(x)=i$, we pick such $x^{\prime}$. Since $\phi$ is $L$-Lipschitz and $\phi(C_{T})\subset\phi(C_{0}\cup C_{1})$ we have $\phi(x_{0}),\phi(x_{1}),...,\phi(x_{m})\in\phi(C_{0}\cup C_{1})$ and $d_{\mathcal{Z}}(\phi(x_{i-1}),\phi(x_{i}))<\Delta$ for all $i=1,...,m$. Applying the fact that $\inf_{z_{0}\in\phi(C_{0}),z_{1}\in\phi(C_{1})}d_{\mathcal{Z}}(z_{0},z_{1})\geq\Delta>0$ we know that if $\phi(x)=\phi(x_{0})\in\phi(C_{j})$ for some $j\in\{0,1\}$ then $\phi(x^{\prime})=\phi(x_{m})\in\phi(C_{j})$. From $x^{\prime}\in C_{0}\cup C_{1}$ and $f(x^{\prime})=f(x)=i$ we have $\phi(x^{\prime})\in\phi(C_{i})$. Since $C_{0}\cap C_{1}=\emptyset$ we can conclude $i=j$ and thus $\phi(x)\in\phi(C_{i})$ if $f(x)=i$ for any $x\in C_{T}$. Therefore, if $x\in C_{T}$, neither $f(x)=1,\phi(x)\in\phi(C_{0})$ nor $f(x)=0,\phi(x)\in\phi(C_{1})$ can hold. Hence the first part of (18) is .

So far by combining (17) and (18) we have shown that the sum of (14) and (15) (which are the first two parts of (13)) can be upper bounded by $\delta_{1}+(1+\beta)\delta_{2}+\delta_{3}$. For the third part of (13) we have

Plugging (12) and (20) into (2) gives the result of Theorem 4.3 under Constructions 4.1 and A.1.

It remains to show that Assumption 4.2 implies the existence of a Construction A.1. To prove this, we first write $\phi(C_{T})\subset\phi(C_{0}\cup C_{1})$ as $C_{T}\subset\phi^{-1}(\phi(C_{0}\cup C_{1}))$. By Construction 4.1 we have $p_{S}(C_{0}\cup C_{1})\geq 1-\delta_{2}$. From (19) we have

Setting $B_{S}=C_{0}\cup C_{1}$ and $B_{T}=\phi^{-1}(\phi(C_{0}\cup C_{1})$ in Assumption 4.2 gives a construction of Construction A.1, thus concluding the proof.

The Fenchel Dual of $\bar{f}_{\beta}(u)$ can be written as

where $C_{f,\beta}=f(\frac{1}{1+\beta})-f^{\prime}(\frac{1}{1+\beta})\frac{1}{1+\beta}+f^{\prime}(\frac{1}{1+\beta})$.

Therefore, the modified $\bar{f}_{\beta}$-divergence can be written as

According to Nowozin et al. (2016), the GAN objecitve uses $f(u)=u\log u-(1+u)\log(1+u)$. Hence $f^{*}(t)=-\log(1-e^{t})$, $f^{\prime}(u)=\log\frac{u}{u+1}$ and $f^{\prime}(\frac{1}{1+\beta})=\log\frac{1}{2+\beta}$. So we need to parameterize T:\mathcal{Z}\mapsto\big{(}-\infty,\log\frac{1}{2+\beta}\big{]}. $T(z)=\log\frac{g(z)}{2+\beta}$ with $g(z)\in(0,1]$ satisfies the range constraint for $T$. Plugging $T(z)=\log\frac{g(z)}{2+\beta}$ into (6) gives the result of (7).

Appendix B Experiment Details

Synthetic datasets For source distribution, we sample class from $\mathcal{N}([-1,-0.3],diag(0.1,0.4))$ and class $1$ from $\mathcal{N}([1,0.3],diag(0.1,0.4))$. For target distribution, we sample class from $\mathcal{N}([-0.3,-1],diag(0.4,0.1))$ and class $1$ from $\mathcal{N}([0.3,1],diag(0.4,0.1))$. For label classifier, we use a fully-connect neural net with 3 hidden layers $(50,50,2)$ and the latent space is set as the last hidden layer. For domain classifier (critic) we use a fully-connect neural net with 2 hidden layers $(50,50)$.

Image datasets For MNIST we subsample 2000 data points and for USPS we subsample 1800 data points. The subsampling process depends on the given label distribution (e.g. shift or no-shift). For label classifier, we use LeNet and the latent space is set as the last hidden layer. For domain classifier (critic) we use a fully-connect neural net with 2 hidden layers $(500,500)$.

In all experiments, we use $\lambda=1$ in the objective (4) and ADAM with learning rate 0.0001 and $\beta_{1}=0.5$ as the optimizer. We also apply a l2-regularization on the weights of $\phi$ and $h$ with coefficient $0.001$.

More discussion on synthetic experiments. The only unexcepted failure is WDANN1-$2$, which achieves only 20% accuracy in 2-out-of-5 runs. Looking in to the low accuracy runs we found that the l2-norm of the encoder weights is clearly higher than the successful runs. Large l2-norm of weights in $\phi$ likely results in a high Lipschitz constant $L$, which is undesirable according to our theory. We only implemented l2-regularization to encourage Lipschitz continuity of the encoder $\phi$, which might be insufficient. How to enforce Lipschitz continuity of a neural network is still an open question. Trying more sophisticated approaches for Lipschitz continuity can a future direction.

Choice of $\beta$. Since a good value of $\beta$ may depend on the knowledge of target label distribution which is unknown, we experiment with different values of $\beta$. Empirically we did not find any clear pattern of correlation between value of $\beta$ and performance as long as it is big enough to accommodate label distribution shift so we would leave it as an open question. In practice we suggest to use a moderate value such as $2$ or $4$, or estimate based on prior knowledge of target label distribution.