Clarinet: A One-step Approach Towards Budget-friendly Unsupervised Domain Adaptation

1 Introduction

Domain Adaptation (DA) aims to train a target-domain classifier with data in source and target domains [Yan et al., 2017; Zhou et al., 2019b]. Based on the availability of data in the target domain (e.g., fully-labeled, partially-labeled and unlabeled), DA is divided into three categories: supervised DA [Sukhija et al., 2016], semi-supervised DA [Ao et al., 2017; Zhou et al., 2019a] and unsupervised DA (UDA) [Gong et al., 2018; Liu et al., 2020; Saito et al., 2017; Fang et al., 2019]. In practice, UDA methods have been applied to many real-world problems, such as object recognition [Agresti et al., 2019; Deng et al., 2019; Zhao et al., 2019].

UDA methods train a target-domain classifier with massive true-label data from the source domain (true-label source data) and unlabeled data from the target domain (unlabeled target data). Existing works in the literature can be roughly categorised into the following three groups: integral-probability-metrics based UDA [Long et al., 2015]; adversarial-training based UDA [Ganin et al., 2016; Long et al., 2018]; and causality-based UDA [Gong et al., 2016; Gong et al., 2018; Zhang et al., 2015]. Since adversarialtraining based UDA methods extract better domain-invariant representations via deep networks, they usually have good target-domain accuracy [Sankaranarayanan et al., 2018].

∗Equal Contribution

†Corresponding Author

However, the success of UDA still highly relies on the scale of true-label source data. Namely, the target-domain accuracy of a UDA method (e.g., CDAN) decays when the scale of true-label source data decreases. Hence, massive true-label source data are inevitably required by UDA methods, which is very expensive and prohibitive especially when the budget is limited [Liu et al., 2019]. This circumstance may hinder the promotion of DA to more areas.

While determining the correct label from many candidates is laborious, choosing one of the incorrect labels (i.e., complementary labels) would be much easier and thus less costly, especially when we have many candidates [Ishida et al., 2017]. For example, suppose that we need to annotate labels of a bunch of animal images from 1, 000 candidates. One strategy is to ask crowd-workers to choose the true labels from 1, 000 candidates, while the other is to judge the correctness of a label randomly given by the system from the candidates. Apparently, the cost of the second strategy is much lower than that of the first one [Ishida et al., 2019].

This brings us a novel problem setting, budget-friendly UDA (abbreviated as BFUDA), which aims to transfer knowledge from complementary-label source data to unlabeled target data (Figure 1). We describe this problem setting using the word budget-friendly since, compared to ordinary UDA, we can greatly save the labeling cost by annotating complementary labels in the source domain rather than annotating true labels [Ishida et al., 2017; Yu et al., 2018]. Please note that, existing UDA methods cannot handle BFUDA, as they require fully-true-label source data [Liu et al., 2020; Saito et al., 2017] or at least 20% true-label source data (demonstrated in [Liu et al., 2019; Shu et al., 2019]).

A straightforward but weak solution to BFUDA is a twostep approach, which sequentially combines complementarylabel learning (CLL) methods and existing UDA methods (green dash line in Figure 1) 1 . CLL methods are used to assign pseudo labels for complementary-label source data. Then, we can train a target-domain classifier with pseudolabel source data and unlabeled target data using existing UDA methods. Nevertheless, pseudo-label source data contain noise, which may cause poor domain-adaptation performance of such two-step approach [Liu et al., 2019].

1 We implement this two-step approach and take it as a baseline.

Therefore, we propose a powerful one-step solution to BFUDA, complementary label adversarial network (CLARINET). It maintains two deep networks trained by adversarial way simultaneously, where one can accurately classify complementary-label source data, and the other can discriminate source and target domains. Since Long et. al. [2018] and Song et. al. [2009] have shown that multimodal structures of distributions can only be captured sufficiently by the crosscovariance dependency between the features and classes (i.e., true labels), we set the input of domain discriminator D as the outer product of feature representation (e.g., gs in Figure 2) and mapped classifier prediction (e.g., T (fs) in Figure 2).

Due to the nature of complementary-label classification, predicted probability of each class (i.e., each element of fs, Figure 2) is relatively close. According to [Song et al., 2009], this kind of predicted probabilities could not provide sufficient information to capture the multimodal structure of distributions. To fix it, we propose a mapping function T to make the predicted probabilities more scattered (i.e., T(fs), Figure 2) than previous ones (i.e., fs, Figure 2). By doing so, the mapped classifier predictions can better indicate their choice. In this way, we can take full advantage of classifier predictions and effectively align distributions of two domains. Our ablation study (see Table 2) verifies that T indeed helps improve the target-domain accuracy.

We conduct experiments on 6 BFUDA tasks and compare CLARINET with a series of competent baselines. Empirical results demonstrated that CLARINET can effectively transfer knowledge from complementary-label source data to unlabeled target data and is superior to all baselines.

2 Budget-friendly Unsupervised Domain Adaptation

In this section, we propose a novel problem setting, called budget-friendly unsupervised domain adaptation (BFUDA), and prove a learning bound of this new problem. Then, we show how BFUDA brings benefits to domain adaptation field.

2.1 Problem Setting

Let X ⊂ Rd be a feature (input) space and Y := {1, ...,K} be a label (output) space. A domain is defined as follows.

Definition 1 (Domains for BFUDA). Given random variables Xs,Xt ∈ X, Ys, Y s, Yt ∈ Y, the source and target domains are joint distributions P(Xs, Y s) and P(Xt, Yt), where the joint distributions P(Xs, Ys) ̸= P(Xt, Yt) and P(Y s = c|Ys = c) = 0 for all c ∈ Y.

Then, we propose BFUDA problem as follows.

Problem 1 (BFUDA). Given independent and identically distributed (i.i.d.) labeled samples Ds = {(xis , yis )}ns i=1 drawn from the source domain P(Xs, Y s) and i.i.d. unlabeled samples Dt = {xit }nt i=1 drawn from the target marginal distribution P(Xt), the aim of BFUDA is to train a classifier F : X → Y with Ds and Dt such that F can accurately classify target data drawn from P(Xt).

It is clear that it is impossible to design a suitable learning procedure without any assumptions on P(Xs, Y s). In this paper, we use the assumption for unbiased complementary learning proposed by [Ishida et al., 2019; Ishida et al., 2017]:

for all k, c ∈ Y = {1, ..., K} and c ̸= k.

2.2 Learning Bound of BFUDA

This subsection presents a learning bound of BFUDA. Practitioner may safely skip it. The ℓ : RK ×Y → R+ is a loss function. The decision function is a vector-valued function h : X → RK and hk is the k-th element of h. The complementary risk for h with respect to ℓ over P(Xs, Y s) is

The risks for the decision function h with respect to loss ℓ over implicit distribution P(Xs, Ys), P(Xt, Yt) are:

Then, we introduce our main theorem as follows.

Theorem 1. Given a loss function ℓ and a hypothesis H ⊂ {h : X → RK }, then under unbiased assumption, for any h ∈ H, we have

where Ls(h) := ∑Kk=1 ∫X ℓ(h(x), k)dPXs -(K-1)Ls(h), PXs , PXt are source and target marginal distributions, Λ = minh∈H Rs(h) + Rt(h), and dℓH(PXs , PXt ) is the distribution discrepancy defined in [Ben-David et al., 2010].

Proof. We firstly investigate the connection between Ls(h) and Ls(h) under unbiased assumption in Eq. (1). Given K × K matrix Q whose diagonal elements are 0 and other elements are 1/K, we represent the unbiased assumption by η = Qη, where η = [P (Y s = 1|Xs), ..., P (Y s = K|Xs)]T and η = [P(Ys = 1|Xs), ..., P(Ys = K|Xs)]T . Note that Q has inverse matrix Q-1 whose diagonal elements are -(K - 2) and other elements are 1. Thus, we have that

According to Eq. (2), we have P(Ys = k|Xs) = 1 - (K - 1)P(Y s = k|Xs), which implies that

Hence, Ls(h) = Ls(h). Combining Eq. (3) with the domain adaptation bound presented in [Ben-David et al., 2010]

we prove this theorem.

In this bound, the first term, i.e., Eq. (3), is the source classification error based on complementary-label source data. The second term is the distribution discrepancy distance between two domains and Λ is the difference in labeling functions across the two domains. The empirical form of Eq. (3) is known as complementary-label loss (see Eq. (5)).

2.3 How does BFUDA Bring Benefits to DA Field?

Collecting true-label data is always expensive in the real world. Thus, learning from less expensive data [Kumar et al., 2017; Sakai et al., 2017] has been extensively studied in machine learning field, including label-noise learning [Han et al., 2018b; Han et al., 2018a], complementary-label learning [Ishida et al., 2019; Yu et al., 2018; Ishida et al., 2017] and so on. Among all these research directions, obtaining complementary labels is a cost-effective option. As described in the previous works mentioned above, compared with choosing the true class out of many candidate classes precisely, collecting complementary labels is obviously much easier and less costly. In addition, a classifier trained with complementarylabel data is equivalent to a classifier trained with true-label data as shown in [Ishida et al., 2019].

At present, the success of DA still highly relies on the scale of true-label source data, which is a critical bottleneck. With limited budget, it is unrealistic to obtain enough truelabel source data and thus cannot achieve a good distribution adaptation result. For the same budget, we can get multiple times more complementary-label data than the true-label data. In addition, the adaptation scenario is limited to some commonly used datasets, as they have sufficient true labels to support distributional adaptation. Thus if we can reduce the labeling cost in the source domain, for example, by using complementary-label data to replace true-label data (i.e. BFUDA), we can promote DA to more fields. Due to existing UDA methods require at least 20% true-label source data [Shu et al., 2019], they cannot handle BFUDA problem. To address BFUDA problem directly, we propose a powerful solution, CLARINET, as follows.

3 CLARINET: One-step BFUDAApproach

The proposed CLARINET (Figure 2) mainly consists of feature extractor G, label predictor F and domain discriminator D. Furthermore, we add a mapping function T between the label predictor F and domain discriminator D to take full advantage of classifier predictions. In this section, we first introduce two losses used to train CLARINET, and then the whole training procedures of CLARINET is presented.

3.1 Loss Function in CLARINET

In this subsection, we show how to compute the two losses mentioned above in CLARINET after obtaining mini-batch ds fromDs and dt fromDt.

Complementary-label Loss. We first divided ds into K disjoint subsets according to the complementary labels in ds,

where ds,k ∩ ds,k′ = ∅ if k ̸= k′ and ns,k = |ds,k|. Then, following Eq. (3), the complementary-label loss on ds,k is

where ℓ can be any loss and we use the cross-entropy loss, πk is the proportion of the samples complementary-labeled k. The total complementary-label loss on ds is as follows.

As shown in Section 2.2, the complementary-label loss (i.e., Eq. (6)) is an unbiased estimator of the true-label-data risk. Namely, the minimizer of complementary-label loss agrees with the minimizer of the true-label-data risk with no constraints on the loss ℓ and model F ◦G [Ishida et al., 2019].

Remark 1. Due to the negative part in Ls(G, F, ds), minimizing it will cause over-fitting [Kiryo et al., 2017]. To overcome this problem, we use a correctional way [Ishida et al., 2019] to minimize Ls(G, F, ds) (lines 7-13 in Algorithm 1).

Scattered Conditional Adversarial Loss. According to [Song et al., 2009], it is significant to capture multimodal structures of distributions using cross-covariance dependency between the features and classes (i.e., true labels). Since there are no true-label target data in UDA, CDAN adopts outer product of feature representations and classifier predictions (i.e., outputs of the softmax layer) as new features of two domains [Long et al., 2018]. The newly constructed features have shown great ability to discriminate source and target domains, since classifier predictions of true-label source data are dispersed, expressing the predicted goal clearly.

However, in the complementary-label classification mode, we observe that the predicted probability of each class (i.e., each element of fs in Figure 2) is relatively close. Namely, it is hard to find significant predictive preference from the classifier predictions. According to [Song et al., 2009], this kind of predictions cannot provide sufficient information to capture the multimodal structure of distributions. To fix it, we propose a mapping function T to scatter the classifier predictions f = [f1, ..., fK]T (f could be fs or ft in Figure 2),

It is a common approach of adjusting the "temperature" of categorical distribution. As l → 0, the output of T(f) will approach a Dirac ("one-hot") distribution.

Then to prioritize the discriminator on those easy-totransfer examples, following [Long et al., 2018], we measure the uncertainty of the prediction for sample x by

Thus the scattered conditional adversarial loss is as follows,

Algorithm 1 CLARINET: One-step BFUDA Approach

Parameters: learning rate γ1 and γ2, epoch Tmax, start epoch Ts, iteration Nmax, class number K, tradeoff λ, network parameter

Output: the neural network F ◦ G, namely the target domain clas-

1: Initialize θF◦G and θD; 2: for t = 1, 2. . . . . .Tmax do 3: Shuffle the training set Ds, Dt; 4: for N = 1, 2. . . . . . Nmax do 5: Fetch mini-batch ds, dt fromDs, Dt; 6: Divide ds into {ds,k}Kk=1; 7: Calculate {Ls(G, F, ds,k)}Kk=1 using Eq. (5), and Ls(G, F, ds) using Eq. (6); 8: if mink{Ls(G, F, ds,k)}Kk=1 ≥ 0 then 9: Update θF◦G = θF◦G - γ1▽Ls(G, F, ds); else Calculate Lneg = ∑Kk=1 min{0, Ls(G, F, ds,k)}; Update θF◦G = θF◦G + γ1▽Lneg; end if if t > Ts then Calculate Ladv(G, F, D, ds, dt) using Eq. (9); Update θD = θD - γ2▽Ladv(G, F, D, ds, dt); Update θF ◦G = θF ◦G + γ2λ▽Ladv(G, F, D, ds, dt); end if

θF◦G and θD. sifier for Dt. 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: end for 20: end for

where ωs(x) and ωt(x) are 1 + e-H(G,F,x) , g(x) is G(x) ⊗ T(F ◦ G(x)) and ds[X] is the feature part of ds.

3.2 Training Procedure of CLARINET

Based on the two losses proposed in Section 3.1, in CLARINET, we try to solve the following optimization problem,

where D tries to distinguish the samples from different domains by minimizing Ladv, while F ◦ G wants to maximize the Ladv to make domains indistinguishable. To solve the minimax optimization problem in Eq. (10), we add a gradient reversal layer [Ganin et al., 2016] between the domain discriminator and the classifier, which multiplies the gradient by a negative constant (-λ) during the back-propagation. λ is a hyper-parameter between the two losses to tradeoff source risk and domain discrepancy.

The training procedures of CLARINET are shown in Algorithm 1. First, we initialize the whole network (line 1) and shuffle the training set (line 3). During each epoch, after minbatch ds and dt are fetched (line 5), we divide the source mini-batch ds into {ds,k}Kk=1 using Eq. (4) (line 6). Then, {ds,k}Kk=1 are used to calculate the complementarylabel loss for each class (i.e., {Ls(G, F, ds,k)}Kk=1 ) and the whole complementary-label loss Ls(G, F, ds) (line 7).

If mink{Ls(G, F, ds,k)}Kk=1 ≥ 0, we calculate the gradient ▽Ls(G, F, ds) and update parameters of G and F using gradient descent (lines 8-9). Otherwise, we sum negative elements in {Ls(G, F, ds,k)}Kk=1 as Lneg (line 11) and calculate the gradient with ▽Lneg (line 12). Then, we update parameters of G and F using gradient ascent (line 12), which is suggested by [Ishida et al., 2019]. When the number of epochs (i.e., t) is over Ts, we start to update parameters of D (line 14). We calculate the scattered conditional adversarial loss Ladv (line 15). Then, Ladv is minimized over D (line 16), but maximized over F ◦ G (line 17) for adversarial training.

4 Experiments

Based on five commonly used datasets: MNIST (M), USPS (U), SVHN (S), MNIST-M (m) and SYN-DIGITS (Y), we verify efficacy of CLARINET on 6 BFUDA tasks: M → U, U → M, S → M, M → m, Y→ M and Y→ S. Note that, we generate complementary-label data according to [Ishida et al., 2019].

4.1 Baselines

We compare CLARINET with the following baselines: gradient ascent complementary label learning (GAC) [Ishida et al., 2019], namely non-transfer method, and several two-step methods, which sequentially combine GAC with UDA methods (including DAN [Long et al., 2015], DANN [Ganin et al., 2016] and CDAN [Long et al., 2018]). In two-step approach, GAC method is first used to assign pseudo labels for complementary-label source data. Then, we train the classifier with pseudo-label source data and unlabeled target data using UDA methods. Thus, we have four possible baselines: GAC, GAC+DAN, GAC+DANN and GAC+CDAN. For twostep methods, they share the same pseudo-label source data on each task. Note that, in this paper, we use the entropy conditioning variant of CDAN.

4.2 Experimental Setup

We design our feature extractor G, label predictor F and domain discriminator D according to the architecture from previous works. More precisely, we pick the structures of feature extractor G from [Ganin et al., 2016; Long et al., 2018]. The label predictor F and domain discriminator D all share the same structure in all tasks, following CDAN [Long et al., 2018]. We follow the standard protocols for unsupervised domain adaptation and compare the average classification accuracy based on 5 random experiments. For each experiment, we take the result of the last epoch. The batch size is set to 128 and the number of epochs is set to 500. SGD optimizer (momentum = 0.9, weight decay = 5×10-5 ) is with an initial learning rate of 0.005 in adversarial network and 5×10-5 in classifier. In mapping function T, l is set to 0.5. We update λ according to [Long et al., 2018]. For parameters of each baseline, we all follow the original settings. We implement all methods with default parameters by PyTorch. The code of CLARINET is available at github.com/Yiyang98/BFUDA.

4.3 Results on BFUDA Tasks

Table 1 reports the target-domain accuracy of 5 methods on 6 BFUDA tasks. As shown, our CLARINET performs best on each task and the average accuracy of CLARINET is significantly higher than those of baselines. Compared with GAC method, CLARINET successfully transfers knowledge from complementary-label source data to unlabeled target data. Since CDAN has shown much better adaptation performance than DANN and DAN [Long et al., 2018], GAC+CDAN should outperform other two-step methods on each task. However, on the task U→M, the accuracy of GAC+CDAN is much lower than that of GAC+DANN. This abnormal phenomenon shows that the noise contained in pseudo-label source data significantly reduces transferability of existing UDA methods. Namely, we cannot obtain the reliable adaptation performance by using two-step BFUDA approach.

Figure 3 shows the target-domain accuracy of two-step methods and CLARINET on 6 BFUDA tasks when increasing epochs. It is clear to see that the accuracy of CLARINET gradually and steadily increases and eventually converges, achieving the best accuracy on each task. The accuracy of GAC+CDAN always reaches plateau quickly. For GAC+DANN, its accuracy is unstable and significantly drops after certain epochs on M→U, M→m tasks. While the accuracy of GAC+DAN is relatively stable but not satisfactory.

4.4 Ablation Study

Finally, we conduct experiments to show the contributions of components in CLARINET. We consider following baselines:

• C w/ LCE: train CLARINET by Algorithm 1, while replacing Ls(G, F, Ds) by cross-entropy loss.
• C w/o T: train CLARINET by Algorithm 1, without mapping function T .

C w/ LCE uses the cross-entropy loss to replace the complementary-label loss. The target-domain accuracy of C w/ LCE will show if UDA methods can address the BFUDA problem. Comparing CLARINET with C w/o T reveals whether the mapping function T takes effect. As shown in Table 2, the target-domain accuracy of C w/ LCE is much lower than that of other methods. Namely UDA methods cannot handle BFUDA tasks directly. Although C w/o T achieves better accuracy than two-step methods, its accuracy is still worse than CLARINET's. Thus, the mapping function T can help improve the adaptation performance under BFUDA.

5 Conclusion

This paper presents a new problem setting for the domain adaptation field, called budget-friendly unsupervised domain adaptation (BFUDA), which exploits economical complementary-label source data instead of expensive truelabel source data. Since existing UDA methods cannot address BFUDA problem, we propose a novel one-step BFUDA approach, called complementary label adversarial network (CLARINET). Experiments conducted on 6 BFUDA tasks confirm that CLARINET effectively achieves distributional adaptation from complementary-label source data to unlabeled target data and outperforms competitive baselines.

Acknowledgements

The work presented in this paper was supported by the Australian Research Council (ARC) under FL190100149 and DP170101632. We would like to thank the anonymous reviewers for their thoughtful comments. The first author particularly thanks the support by UTS-CAI during her visit.