Title: WILDLY UNSUPERVISED DOMAIN ADAPTATION AND ITS POWERFUL AND EFFICIENT SOLUTION Anonymous

Abstract: In unsupervised domain adaptation (UDA), classifiers for the target domain (TD) are trained with clean labeled data from the source domain (SD) and unlabeled data from TD. However, in the wild, it is hard to acquire a large amount of perfectly clean labeled data in SD given limited budget. Hence, we consider a new, more realistic and more challenging problem setting, where classifiers have to be trained with noisy labeled data from SD and unlabeled data from TD-we name it wildly UDA (WUDA). We show that WUDA ruins all UDA methods if taking no care of label noise in SD, and to this end, we propose a Butterfly framework, a powerful and efficient solution to WUDA. Butterfly maintains four models (e.g., deep networks) simultaneously, where two take care of all adaptations (i.e., noisy-to-clean, labeled-to-unlabeled, and SD-to-TD-distributional) and then the other two can focus on classification in TD. As a consequence, Butterfly possesses all the conceptually necessary components for solving WUDA. Experiments demonstrate that under WUDA, Butterfly significantly outperforms existing baseline methods. 1 INTRODUCTION Domain adaptation (DA) aims to learn a discriminative classifier in the presence of a shift between training data in source domain and test data in target domain (Ben-David et al.

Ps:

Ps Pxt The blue line denotes that UDA transfers knowledge from clean source data (Ps) to unlabeled target data (Px t ). However, perfectly clean data is hard to acquire. This brings wildly unsupervised domain adaptation (WUDA), namely transferring knowledge from noisy source data ( Ps) to unlabeled target data (Px t ). Note that label corruption process (black dash line) is unknown in practice. To handle WUDA, a compromise solution is a two-step approach (green line), which sequentially combines label-noise algorithms ( Ps → Ps, label correction) and existing UDA ( Ps → Px t ). This paper proposes a robust one-step approach called Butterfly (red line, Ps → Px t directly), which eliminates noise effects from Ps.

Figure 1 : Wildly unsupervised domain adaptation (WUDA). transfer knowledge from noisy labeled data in source domain ( P s , i.e., noisy source data) to unlabeled target data (P xt ). Unfortunately, existing UDA methods share an implicit assumption that there are no noisy source data. Namely, these methods focus on transferring knowledge from clean source data (P s ) to unlabeled target data (P xt ). Therefore, these methods cannot well handle the WUDA.

To validate this fact, we empirically reveal the deficiency of existing UDA methods (Figure 2 ). To improve these methods, a straightforward solution is a two-step approach. In Figure 1 , we can first use label-noise algorithms to train a model on noisy source data, then leverage this trained model to assign pseudo labels for noisy source data. Via UDA methods, we can transfer knowledge from pseudo-labeled source data ( Ps ) to unlabeled target data (P xt ). Nonetheless, pseudo-labeled source data are still noisy, and such two-step approach may not eliminate noise effects.

To circumvent the issue of two-step approach, we present a robust one-step approach called Butterfly. In high level, Butterfly directly transfers knowledge from P s to P xt , and uses the transferred knowledge to construct target-specific representations. In low level, Butterfly maintains four networks dividing two branches (Figure 3 ): Two networks in Branch-I are jointly trained on noisy source data and pseudo-labeled target data (data in mixture domain (MD)); while two networks in Branch-II are trained on pseudo-labeled target data.

The reason why Butterfly can be robust takes root in the dual-checking principle (DCP): Butterfly checks high-correctness data out, from not only the data in MD but also the pseudo-labeled target data. After crosspropagating these high-correctness data, Butterfly can obtain high-quality domain-invariant representations (DIR) and target-specific representations (TSR) simultaneously in an iterative manner. If we only check data in MD (i.e., single checking), the error existed in pseudo-labeled target data will accumulate, leading to low-quality DIR and TSR.

We conduct experiments on simulated WUDA tasks, including 4 MNIST-to-SYND tasks, 4 SYND-to-MNIST tasks and 24 human-sentiment tasks. Besides, we conduct experiments on 3 real-world WUDA tasks. Empirical results demonstrate that Butterfly can robustly transfer knowledge from noisy source data to unlabeled target data. Meanwhile, Butterfly performs much better than existing UDA methods when source domain (SD) suffers the extreme (e.g., 45%) noise.

2. WILDLY UNSUPERVISED DOMAIN ADAPTATION:

In this section, we first define a new, more realistic and more challenging setting called wildly unsupervised domain adaptation (WUDA), and explain the nature of WUDA. Then, we empirically show that representative UDA methods cannot handle WUDA well, which motivates us to propose Butterfly (see Section 3).

Definition 1 (Wildly Unsupervised Domain Adaptation). Let X t be a multivariate random variable defined on the space X with respective a probability density p xt , (X s , Y s ) be a multivariate random variable defined (Long et al., 2015) ), domain-adversarial neural network (DANN, a adversarial training based method (Ganin et al., 2016) ), asymmetric tri-training domain adaptation (ATDA, a pseudo-label based method (Saito et al., 2017) ) and transferable curriculum learning (TCL, a robust UDA method (Shu et al., 2019) ). B-Net is our proposed WUDA method. We report target-domain accuracy of all methods when the noise rate of source domain changes (a) from 5% to 70% (symmetry-flip noise) and (b) from 5% to 45% (pair-flip noise). Clearly, when the noise rate of source domain increases, target-domain accuracy of representative UDA methods drops quickly while that of B-Net keeps stable consistently. Nature of WUDA. Specifically, there are five distributions involved in WUDA setting: 1) a marginal distribution on source data, i.e., p xs in Definition 1; 2) a marginal distribution on target data, i.e., p xt in Definition 1; 3) an incorrect conditional distribution of label given x s , q(y s |x s ); 4) a correct conditional distribution of label given x s , p(y s |x s ) and 5) a correct conditional distribution of label given x t , p(y t |x t ).

Based on Definition 1 and Appendix A.2, noisy source data Ds are drawn from ps (x s , y s ) = p xs (x s )((1ρ)p(y s |x s ) + ρq(y s |x s )), where ρ is the noise rate in source data. Namely, source data Ds are mixture of correct source data from p xs (x s )p(y s |x s ) and incorrect data from p xs (x s )q(y s |x s ). Target data D t are drawn from p xt . In WUDA setting, we aim to train a classifier with Ds and D t . This classifier is expected to accurately annotate data from p xt , i.e., to accurately simulate distribution 5). WUDA ruins representative UDA methods. We take a simple example to illustrate why WUDA ruins representative UDA methods. We corrupt source data using symmetry flipping (Patrini et al., 2017) and pair flipping (Han et al., 2018) (Appendix B). Namely, the corrupted source data ( Ds in Definition 1) are drawn from Ps whose density is ps (x s , y s ) = p xs (x s )((1 -ρ)p(y s |x s ) + ρq(y s |x s )). We draw the target data D t from P xt whose density is p xt . To instantiate source and target data, we leverage MNIST and SYND (Figure 6 in Appendix C), respectively. Thus, we first construct two WUDA tasks with symmetry-flip noise: corrupted SYND→MNIST (S→M) and corrupted MNIST→SYND (M→S). In Figure 2 (a), we report target-domain accuracy of representative UDA methods, when the noise rate ρ of SD changes from 5% to 70%. It is clear that target-domain accuracy of these representative UDA methods drops quickly when ρ increases. This means that WUDA ruins representative UDA methods. Then, we construct another two WUDA tasks with pair-flip noise. In Figure 2 (b), we report target-domain accuracy, when the noise rate ρ of SD changes from 5% to 45%. Again, WUDA still ruins representative UDA methods. Note that pair-flip noise is much harder than symmetry-flip noise, and its noise rate cannot be over 50% in practice (Han et al., 2018) . However, the proposed Butterfly network (abbreviated as B-Net, Figure 3 ) performs robustly when ρ increases (blue lines in Figure 2 ). In following sections, we will introduce Butterfly framework, and explain why Butterfly achieves better target-domain accuracy consistently.

3. BUTTERFLY: TOWARDS ROBUST ONE-STEP APPROACH:

To realize a robust WUDA approach, we propose a Butterfly framework (a one-step approach, Algorithm 1), which trains four networks dividing into two branches (Figure 3 ). By using DCP, Branch-I checks which data is correct in MD; while Branch-II checks which pseudo-labeled target data is correct. To ensure these checked data highly-correct, we apply the small-loss trick based on memorization effects of deep learning (Arpit et al., 2017) . After cross-propagating these checked data (Bengio, 2014) , Butterfly can obtain high-quality DIR and TSR simultaneously in an iterative manner.

Loss function in Butterfly. Four networks trained by Butterfly share the same loss function but with different inputs.

EQUATION

where n is the batch size, and F represents a network (e.g., F 1 , F 2 , F t1 and F t2 ). D = {(x i , yi )} n i=1 is a mini-batch for training a network, where {x i , yi } n i=1 could be data in MD or TD (Figure 3 ), and θ represents parameters of F and u = [u 1 , ..., u n ] T is an n-by-1 vector whose elements equal 0 or 1. (•, •) is the cross-entropy loss. For two networks in Branch-I, following Saito et al. (2017) , we also add a regularizer |θ T f 11 θ f 21 | in their loss functions, where θ f 11 and θ f 21 are weights of the first fully-connect layer of F 1 and F 2 . With this regularizer, F 1 and F 2 will learn from different features. Nature of the loss L. In loss function L, we have n instances: (x i , yi ), where i = 1, 2, . . . , n. For the i th instance, we will compute its cross-entropy loss (i.e., (F (x i ), yi )), and we will denote this instance as "selected" if u i = 1. Thus, the nature of L is actually the average value of cross-entropy loss of these "selected" instances. Note that, we need to set a constrain to prevent n i=1 u i = 0 in L, which means that we need to select at least one instance to compute L.

Training procedure of Butterfly. For two networks in each branch, they will first check high-correctness data out and then cross update their parameters using these data.

Based on loss function defined in Eq. ( 1), entire training procedures of Butterfly are shown in Algorithm 1. First, we initialize training data for two branches ( D for Branch-I and Dl t for Branch-II), four networks (F 1 , F 2 , F t1 and F t2 ) and the number of pseudo labels (line 2). In the first epoch (T = 1), following Saito et al. (2017) , Dl t is the same with Ds (i.e., we use noisy source data as pseudo-labeled target data) since we cannot annotate pseudo labels for target data when T = 1. After mini-batch Ď is fetched from D (line 4), F 1 and F 2 check high-correctness data out and update their parameters (lines 5) using Algorithm 2. Using similar procedures, F t1 and F t2 also update their parameters using Algorithm 2 (lines 6-7).

In each epoch, after N max mini-batch updating, we randomly select n l t unlabeled target data and assign them pseudo labels using F 1 and F 2 (lines 8). Following Saito et al. (2017) , the Labeling function in Algorithm 1 (line 8) assigns pseudo labels for unlabeled target data, when predictions of F 1 and F 2 agree and at least one of them is confident about their predictions (probability above 0.9 or 0.95). Using this function, we can obtain the pseudo-labeled target data Dl t for training Branch-II in the next epoch. Then, we merge Dl t and Ds to be D for training Branch-I in the next epoch (line 9). Finally, we update n l t , R(T ) and R t (T ) in lines 10-11 according to Saito et al. (2017) and Han et al. (2018) . Note that R(T ) is a piecewise-defined linear function. Namely, when

T ≥ T k , R(T ) = 1 -τ ; when T ≤ T k , R(T ) = 1 -T /T k × τ .

In Algorithm 1, we use τ to represent the noise rate (i.e., the ratio of data with incorrect labels) in MD and use τ t to represent the noise rate in TD. However, in WUDA, we cannot obtain the ground-truth τ and τ t . Thus, we regard τ and τ t as hyper-parameters. Note that τ and τ t are robustly set to 0.4 and 0.05 in experiments.

Checking process in Butterfly. In Algorithm 2, we first obtain four inputs: 1) networks F 1 and F 2 , and 2) a mini-batch D, and 3) learning rate η and 4) remember rate α (line 1). Then, we will obtain the best u 1 by solving a minimization problem (line 2). L represents the loss function defined in Eq. (1). θ 1 represents the parameters of the network F 1 . Similarly we will obtain the best u 2 (line 3). θ 2 represents the parameters of the network F 2 . Next, θ 1 and θ 2 are updated using gradient descent, where the gradients are computed using a given optimizer (lines 4-5). Finally, we substitute the updated θ 1 into F 1 and the updated θ 2 into F 2 and output F 1 and F 2 (line 6).

Solution to minimization problems in Algorithm 2. In line 2 or 3 in Algorithm 2, we need to solve a minimization problem: min u :1u >α|D| L(θ, u ; F, D) and return the best u as u (u 1 in line 2 and u 2 in line 3). In this paragraph, we will show how to quickly solve this problem using a sorting algorithm. Recall the nature of the loss L, we know L is the average value of cross-entropy losses of "selected" instances, and 1u is the number of these "selected" instances. Thus this minimization problem is equivalent to "given a fixed F (F 1 or F 2 ) and n instances in D, how to select at least k instances such that L is minimized", where k = α|D| . To solve this problem, we first use a sorting algorithm (top_k function in TensorFlow) to sort these n instances according to their cross-entropy losses (F 1 (x i ), yi ). Then, we select k instance with the smallest cross-entropy losses. Finally, let u i of these k instances be 1 and u i of the other instances be 0, and we can get the best u = [u 1 , . . . , u n ]. The average value of cross-entropy losses of these k instances is the minimized value of L(θ, u ; F, D) under the constrain 1u > α|D|.

4. BUTTERFLY VS. TWO-STEP APPROACH:

This section analyzes why Butterfly is better than two-step approach using theoretical results in Appendix D. Practitioner may safely skip it. Following Ben-David et al. (2010) , we derive an upper bound of target-domain risk for WUDA. Compared to existing UDA bounds, the WUDA bound has two extra terms (see Eq. ( 6)): ∆ s (noise effect from source data), and ∆ t (noise effects from pseudo labels of target data). We will use ∆ s and ∆ t to show why Butterfly (a one-step approach) can eliminate noise effects while two-step methods cannot. 

11: Update R(T ) = 1 -min{ T T k τ, τ }, Rt(T ) = 1 -min{ T T k τt, τt}; end 12: Output Ft1 and Ft2 Algorithm 2 Checking(F 1 , F 2 , D, η, α) 1: Input networks F1, F2, mini-batch D, learning rate η, remember rate α; 2: Obtain u1 = arg min u 1 :1u 1 >α|D| L(θ1, u 1 ; F1, D); // Check high-correctness data 3: Obtain u2 = arg min u 2 :1u 2 >α|D| L(θ2, u 2 ; F2, D); // Check high-correctness data 4: Update θ1 = θ1 -η∇L(θ1, u2; F1, D); // Update θ1 5: Update θ2 = θ2 -η∇L(θ2, u1; F2, D);

// Update θ2 6: Output F1 and F2 Two-step approach (a compromise solution). To reduce noise effects, a straightforward solution is twostep approach. In the first step, we can train a classifier with noisy source data using Co-teaching (Han et al., 2018) and use this classifier to annotate pseudo labels for source data. In the second step, we use ATDA (Saito et al., 2017) to train a target-domain classifier with pseudo-label-source data and target data.

However, two-step approach may not reduce noise effects ∆ s (i.e., not alleviating noise effects from source data). In two-step approach, after using Co-teaching, ∆ s will become pseudo-label-source effects ∆ s (see Eq. ( 7)). The first part of ∆ s may be less than that of ∆ s due to Co-teaching, but the second term of ∆ s may be higher than that of ∆ s since Co-teaching does not consider to minimize it. Thus, it is hard to say whether ∆ s < ∆ s . This means that, the two-step approach may not really reduce noise effects ∆ s . Besides, two-step approach does not take care of eliminating ∆ t explicitly. Based on above analysis, we can find that a two-step approach cannot eliminate ∆ s and ∆ t .

One-step approach (Butterfly). To eliminate noise effects ∆ = ∆ s + ∆ t , Butterfly aims to select correct data simultaneously from noisy source data and pseudo-labeled target data (see Section 3). Let ρ s 01 be the probability that incorrect data is selected from noisy source data, and ρ t 01 be the probability that incorrect data is selected from pseudo-labeled target data. Theorem 3 shows that ∆ → 0 if ρ s 01 → 0 and ρ t 01 → 0. Since Butterfly can select correct data with a high probability (i.e., ρ s 01 → 0 and ρ t 01 → 0), noise effects will be eliminated (∆ → 0). 

5. EXPERIMENTS:

Simulated WUDA tasks. We verify the effectiveness of our approach on three benchmark datasets (vision and text), including MNIST, SYN-DIGITS (SYND) and human-sentiment analysis (i.e., Amazon products reviews on book, dvd, electronics and kitchen). They are used to construct 14 basic tasks: MNIST→SYND (M→S), SYND→MNIST (S→M), book→dvd (B→D), book→electronics (B→E), . . . , and kitchen → electronics (K→E). These tasks are often used for evaluation of UDA methods (Ganin et al., 2016; Saito et al., 2017; 2018) . Since all source datasets are clean, we corrupt source data using symmetry flipping (Patrini et al., 2017) and pair flipping (Han et al., 2018 ) (Appendix B) with noise rate ρ chosen from {0.2, 0.45}. So, for each basic task, we have four kinds of noisy source data: Pair-45% (P45), Pair-20% (P20), Symmetry-45% (S45), Symmetry-20% (S20). Namely, we evaluate the performance of each method using 32 simulated WUDA tasks: 8 digit tasks and 24 human-sentiment tasks. Note that the human-sentiment task is a binary classification problem, so pair flipping is equal to symmetry flipping. Thus, we only have 24 human-sentiment tasks. Results on human-sentiment tasks are reported in Appendix E.

Real-world WUDA tasks. We also verify the efficacy of our approach on "cross-dataset benchmark" including Bing, Caltech256, Imagenet and SUN (Tommasi and Tuytelaars, 2014) . In this benchmark, Bing, Caltech256, Imagenet and SUN contain common 40 classes. Since Bing dataset was formed by collecting images retrieved by Bing image search, it contains rich noisy data, with presence of multiple objects in the same image and caricaturization (Tommasi and Tuytelaars, 2014) . We use Bing as noisy source data, and Caltech256, Imagenet and SUN as unlabeled target data, which can form three real-world WUDA tasks. Besides, we also test our method on two common UDA tasks ( MNIST→SVHN and SVHN→MNIST) to help compare with other UDA-based papers in literature.

Baselines. We realize Butterfly using four networks (abbreviated as B-Net) and compare B-Net with following baselines: 1) ATDA: representative pseudo label based UDA method (Saito et al., 2017) ; 2) deep adaptation networks (DAN): representative IPM based UDA method (Long et al., 2015) ; 3) DANN: representative adversiral training based UDA method (Ganin et al., 2016) ; 4) TCL: an existing robust UDA method; 5) Co teaching+ATDA (Co+ATDA): a two-step method (see Section 4); 6) Co teaching+TCL (Co+TCL): a two-step method. Implementation details are demonstrated in Appendix F.

Results on simulated WUDA (including 8 tasks). Table 1 reports the accuracy on the unlabled target data (i.e., target-domain accuracy) in 8 tasks. As can be seen, average target-domain accuracy of B-Net is higher than those of all baselines. On S20 case (the easiest case), most methods work well. ATDA has a satisfactory performance although it does not consider the noise effects explicitly. Then, when facing harder cases (i.e., P20 and P45), ATDA fails to transfer useful knowledge from noisy source data to unlabeled target data. When facing the hardest cases (i.e., M→S with P45 and S45), DANN has higher accuracy than DAN and ATDA have. However, when facing the easiest cases (i.e., S→M with P20 and S20), the performance of DANN is worse than that of DAN and ATDA. Although two-step method Co+ATDA (or Co+TCL) outperforms ATDA (or TCL) in all 8 tasks, it cannot beat one-step method: B-Net in terms of average target-domain accuracy. This result is an evidence for the claim in Section 4. In the task S→M with P20, Co+ATDA outperforms all methods (slightly higher than B-Net), since pseudo-labeled source data are almost correct. Results on real-world WUDA (including 3 tasks). Table 2 reports the target-domain accuracy for 3 tasks. B-Net enjoys the best performance on all tasks. It should be noted that, in both Bing→Caltech256 and Bing→ImageNet tasks, ATDA is slightly worse than B-Net. However, in Bing→SUN task, ATDA is much worse than B-Net. The reason is that the DIR between Bing and SUN are more affected by noisy source data. This phenomenon is also observed when comparing DANN and TCL. Compared to Co+ATDA, ATDA is slightly better than Co+ATDA. This abnormal phenomenon can be explained using ∆ (see Section 4), after using Co-teaching to assign pseudo labels for noisy source data, the second term in ∆ s may increase, which results in that ∆ increases, i.e., noise effects actually increase. This phenomenon is an evidence that a two-step method may not really reduce noise effects.

Results on two UDA tasks. (Malach and Shalev-Shwartz, 2017) to check data in MD and TD. 3) DCP-M: realize DCP via MentorNet (Jiang et al., 2018) 4 reports average target-domain accuracy of above baselines and B-Net. As can be seen, 1) B-Net benefits from adding the constraint to the loss function L; 2) realizing DCP by Co-teaching is better than using Decoupling or MentorNet; and 3) DCP is necessary since accuracy of B-Net is higher than those of B-Net-S, B-Net-T, B-Net-ST and B-Net-M.

6. CONCLUSIONS:

This paper opens a new problem called wildly unsupervised domain adaptation (WUDA). However, existing UDA methods cannot handle WUDA well. To address this problem, we propose a robust one-step approach called Butterfly. Butterfly maintains four deep networks simultaneously: Two take care of all adaptations; while the other two can focus on classification in target domain. We compare Butterfly with existing UDA methods on 32 simulated and 3 real-world WUDA tasks. Empirical results demonstrate that Butterfly can robustly transfer knowledge from noisy source data to unlabeled target data. In future, we will extend our Butterfly framework to address open-set UDA when source domain contains noisy data. Symmetry flipping:

Q =        1 -ρ ρ K-1 . . . ρ K-1 ρ K-1 ρ K-1 1 -ρ ρ K-1 . . . ρ K-1 . . . . . . . . . ρ K-1 . . . ρ K-1 1 -ρ ρ K-1 ρ K-1 ρ K-1 . . . ρ K-1 1 -ρ        , Pair flipping: Q =       1 -ρ ρ 0 . . . 0 0 1 -ρ ρ 0 . . . . . . . . . . . . 0 1 -ρ ρ ρ 0 . . . 0 1 -ρ      

.

Following Han et al. (2018) ; Jiang et al. (2018) , we can corrupt clean-label datasets manually using the noise transition matrix Q .

C DATASETS VISUALIZATION:

Figure 6 shows datasets: MNIST and SYND. Figure 7 shows datasets: Bing, Caltech256, Imagenet and SUN (taking "horse" as the common class). 

D THEORETICAL ANALYSIS:

This section presents some interesting theoretical findings related to WUDA problem. We use following notations in this section: 1) a space X ⊂ R d and Y = {1, 2, . . . , K} as a label set; 2) ps (x s , ỹs ), p s (x s , y s ) and q s (x s , y s ) represent densities of noisy, correct and incorrect multivariate random variables (m.r.v.) defined on X × Y, respectively1 , and pxs (x s ), p xs (x s ) and q xs (x s ) are their marginal densities; and 3) p xt (x t ) represents density of m.r.v. x t defined on X ; and 4) we use (h(x), h (x)) to represent loss function between two labelling functions; and 5) we use Rs (h) = E ps(xs,ỹs) [ (h(x s ), ỹs )] and R s (h) = E ps(xs,ys) [ (h(x s ), y s )] to represent expected risks on the noisy and correct m.r.v.; and 6) we use Rs (h, h 

) = E pxs (xs) [ (h(x s ), h (x s ))], R s (h, h ) = E px s (xs) [ (h(x s ), h (x s ))] and R t (h, h ) = E px t (xt) [ (h(x t ), h (x t ))] to

EQUATION

where (h(x s )) = [ (h(x s ), 1), ..., (h(x s ), K)] T and η(x s ) = [p Ys|Xs (1|x s ), ..., p Ys|Xs (K|x s )] T . If ps (x s , ỹs ) is generated by sample selection as described in in Appendix A.2, we have

EQUATION

where η q (x s ) = [q Ys|Xs (1|x s ), ..., q Ys|Xs (K|x s )] T .

Remark 2. In Eq. ( 5), E qx s (xs) [η T q (x s ) (h(x s ))] represents the expected risk on the incorrect m.r.v.. To ensure to obtain useful knowledge from Ps , we need to avoid Rs (h

) ≈ E qx s (xs) [η T q (x s ) (h(x s ))]. Specifically, we assume: there is a constant 0 < M s < ∞ such that E qx s (xs) [η T q (x s ) (h(x s ))] ≤ R s (h) + M s .

Theorem 1 shows that the expected risk Rs (h) only equals R s (h) when two cases happen: 1) Q = I and ρ = 0 and 2) some special combinations (e.g., special p xs , q xs , Q, η and ) to make the second term in Eq. ( 4) equal zero or to make the second term in Eq. ( 5) equal ρR s (h). Case 1) means that data in source domain is clean, which is not real in the wild. Case 2) almost never happens, since it is hard to find such special combinations when p xs , q xs , Q and η are unknown. Thus, Rs (h) has an essential difference with R s (h). 

+ |R s (h, ft ) -R s (h)| (iii) domain dissimilarity + | Rs (h) -R s (h)| + | Rs (h, ft ) -R s (h, ft )|

(iv) noise effects from source ∆s

EQUATION

)

Remark 3. To ensure that we can gain useful knowledge from ft (x t ), we assume: there is a constant 0

< M t < ∞ such that E qx s (x) [ (h(x), ft (x))] ≤ R s (h, ft ) + M t and E qx t (x) [ (h(x), ft (x))] ≤ R t (h, f t ) + M t , where q xt (x) = p xt (x)1 A (x)/P xt (A) and A = {x : ft (x) = f t (x)}.

It is clear that the upper bound of R t (h, f t ), shown in Eq. ( 6), has 5 components. However, existing UDA methods only focus on minimizing (i) + (ii) (Ganin et al., 2016; Ghifary et al., 2017; Long et al., 2015) or (Saito et al., 2017) , which ignores terms (iv) and (v) (i.e., ∆ = ∆ s + ∆ t ). Thus, in theory, existing UDA methods cannot handle wildly unsupervised domain adaptation well.

(i) + (ii) + (iii)

D.2 TWO-STEP APPROACH IS A COMPROMISE SOLUTION:

To reduce noise effects, a straightforward solution is two-step approach. In the first step, we can train a classifier with noisy source data using Co-teaching (Han et al., 2018) and use this classifier to annotate pseudo labels for source data. In the second step, we use ATDA (Saito et al., 2017) to train a target-domain classifier with pseudo-label-source and target data.

Nonetheless, the pseudo-labeled source data is still noisy. Let labels of noisy source data ỹs be replaced with pseudo labels ỹ s after pre-processing. Noise effects ∆ will become pseudo-label effects ∆ p as follows.

EQUATION

where R s (h) and R s (h, ft ) correspond to Rs (h) and Rs (h, ft ) in ∆ s . It is clear that the difference between ∆ p and ∆ is ∆ s -∆ s . The first term in ∆ s may be less than that in ∆ s due to Co-teaching, but the second term in ∆ s may be higher than that in ∆ s since Co-teaching does not consider to minimize it. Thus, it is hard to say whether ∆ s < ∆ s (i.e., ∆ p < ∆). This means that two-step approach may not really reduce noise effects.

D.3 WHY DOES BUTTERFLY CAN ELIMINATE NOISE EFFECT?:

To eliminate noise effects ∆, we aim to select correct data simultaneously from noisy source data and pseudo-labeled target data. In theory, we prove that noise effects will be eliminated if we can select correct data with a high probability. Let ρ s 01 represent the probability that incorrect data is selected from noisy source data, and ρ t 01 represent the probability that incorrect data is selected from pseudo-labeled target data. Theorem 3 shows that ∆ → 0 if ρ s 01 → 0 and ρ t 01 → 0 and presents a new upper bound of R t (h, f t ). Theorem 3. Given two m.r.v. (X s , Y s , U s ) defined on X × Y × V and (X t , U t ) defined on X × V, under the assumptions in Remarks 2 and 3, ∀ ∈ (0, 1), there are δ s and δ

t , if E p x t (xt) [ (h(x t ), f t (x t ))] ≤ R t (h, f t ) + ρ s

01 M t , ρ s 01 < δ s and ρ t 01 < δ t , for any labeling function h, we will have 

EQUATION

where

p xt (x) = p xt (x)1 B (x)/P xt (B), Rpo s (h, u s ) = (1 -ρ us ) -1 E ppo s (xs,ys,us) [u s (h(x s ), y s )], Rpo t (h, ft , u t ) = (1 -ρ ut ) -1 E ppo t (xt,ut) [u t (h(x t ), ft (x t ))], Rpo s (h, ft , u s ) = (1 -ρ us ) -1 E ppo s (xs,ys,us) [u s (h(x s ), ft (x s ))], ppo s (x s , y s , u s ) is the density of (X s , Y s , U s ), ppo t (x t , u t ) is the density of (X t , U t ), ρ us = X K ys=1 ppo s (x s , y s , 0)dx s < 1, ρ ut = X ppo t (x t , 0)dx t < 1, B = X /A and V = {0, 1}. Remark 4.

In Appendix H.3.1, we give precise definitions of ρ s 01 and ρ t 01 and demonstrate the meaning of

E p x t (xt) [ (h(x t ), f t (x t ))] ≤ R t (h, f t ) + ρ s 01 M t (Remark 5).

Data drawn from the distribution of (X s , Y s , U s ) can be regarded as a pool that mixes the selected (u s = 1) and unselected (u s = 0) noisy source data. Data drawn from the distribution of (X t , U t ) can be regarded as a pool that mixes the selected (u t = 1) and unselected (u t = 0) pseudo-labeled target data. Theorem 3 shows that if selected data have a high probability to be correct ones (ρ s 01 → 0 and ρ t 01 → 0), then ∆ s and ∆ t approach 0, meaning that noise effects are eliminated. This motivates us to find a reliable way to select correct data from noisy source data and pseudo-labeled target data and build up a one-step approach for WUDA.

Why Butterfly? Guided by Theorem 3, a robust approach should check high-correctness data out (meaning ρ s 01 → 0 and ρ t 01 → 0). This checking process will make (iv) and (v), 2 + 2 , become 0. Then, we can obtain gradients of Rpo s (h, u s ), Rs (h, ft , u s ) and Rpo t (h, ft , u t ) w.r.t. parameters of h and use these gradients to minimize them, which minimizes (i) and (ii) as (i) + (ii) ≤ Rpo s (h, u s ) + Rs (h, ft , u s ) + Rpo t (h, ft , u t ). Note that (iii) cannot be directly minimized since we cannot pinpoint clean source data. However, following Saito et al. (2017) , we can indirectly minimize (iii) via minimizing Rpo

s (h, u s ) + Rpo s (h, ft , u s ), as (iii) ≤ R s (h, ft ) + R s (h) ≤ Rpo s (h, u s ) + Rpo s (h, ft , u s ) + 2

, where the last inequality follows Eq. ( 8). This means that a robust approach guided by Theorem 3 can minimize all terms in the right side of inequality in Eq. ( 9).

To realize this robust approach, we propose a Butterfly framework (Algorithm 1), which trains four networks dividing into two branches (Figure 3 ). By using dual-checking principle, Branch-I checks which data is correct in the mixture domain; while Branch-II checks which pseudo-labeled target data is correct. To ensure these checked data highly-correct, we apply the small-loss trick based on memorization effects of deep learning Arpit et al. (2017) . After cross-propagating these checked data Bengio (2014) , Butterfly can obtain high-quality DIR and TSR simultaneously in an iterative manner. Theoretically, Branch-I minimizes (i) + (ii) + (iii) + (iv); while Branch-II minimizes (ii) + (v). This means that Butterfly can minimize all terms in the right side of inequality in Eq. ( 9). Note that empirical estimators of Rpo s (h, u s ), Rpo t (h, ft , u t ) and Rpo s (h, ft , u s ) (in Theorem 3) can be expressed using the loss function of Butterfly (see Eq. ( 1)).

Relations to Co-teaching. As Butterfly is related to Co-teaching, we discuss their major differences here.

Although Co-teaching (Han et al., 2018) applies the small-loss trick and the cross-update technique to train deep networks against noisy data, it can only deal with one-domain problem instead cross-domain problem.

Besides, we argue that Butterfly is not a simple mixtrue of Co-teaching and ATDA for two reasons.

First, network structure of Butterfly is different with that of ATDA and Co-teaching: Butterfly maintains four networks; while ATDA maintains three and Co-teaching maintains two. We cannot simply combine ADTA and Co-teaching to derive Butterfly. Second, we have justified that the sequential mixture of Co-teaching and ATDA (i.e., two-step method) cannot eliminate noise effects caused by noisy source data (see Section 4). Specifically, two-step methods only take care of part of noise effects but Butterfly takes care of the whole noise effects. Thus, Butterfly is the first method to eliminate noise effects rather than alleviate it.

Relations to TCL. Recently, transferable curriculum learning (TCL) is a robust UDA method to handle noise Shu et al. (2019) . TCL uses small-loss trick to train the domain-adversarial neural network (DANN) Ganin et al. (2016) . However, TCL can only minimize (i) + (ii) + (iv), while Butterfly can minimize all terms in the right side of Eq. ( 9).

E RESULTS ON HUMAN-SENTIMENT WUDA TASKS Tables 5 and 6 report the target-domain accuracy of each method for 24 human-sentiment WUDA tasks. For these tasks, B-Net has the highest average accuracy. It should be noted that two-step method does not always perform better than existing UDA methods, such as for 20%-noise situation. The main reason is Co-teaching performs poorly when pinpointing clean source data from noisy source data. Another observation is that noise effects is not eliminated like classification results on digit WUDA tasks. The main reason is that these datasets provide fixed features and we cannot extract better features in the training process. However, in digit WUDA tasks, we can gradually obtain better features for each domain and finally eliminate noise effects. We implement all methods on Python 3.6 with a NIVIDIA P100 GPU. We use MomentumSGD for optimization in digit and real-world tasks, and set the momentum as 0.9. We use Adagrad for optimization in human-sentiment tasks because of sparsity of review data (Saito et al., 2017) . F 1 , F 2 , F t1 and F t2 are 6-layer CNN (3 convolutional layers and 3 fully-connected layers) for digit tasks; and are 3-layer neural networks (3 fully-connected layers) for human-sentiment tasks; and are 4-layer neural networks (4 fully-connected layers) for real-world tasks. The ReLU active function is used as avtivation function of these networks.

Besides, dropout and batch normalization are also used. The network topology is shown in Figures 8, 9 and 10. As deep networks are highly nonconvex, even with the same network and optimization method, different initializations can lead to different local optimal. Thus, following Malach and Shalev-Shwartz (2017) , we also take four networks with the same architecture but different initializations as four classifiers. Figure 10 : The architecture of B-Net for real-world WUDA tasks. We added BN layer in the first FC layers in F 1 , F 2 , F t1 and F t2 . We also used dropout in the first FC layers in F 1 , F 2 , F t1 and F t2 (dropout probability is set to 0.5).

F.2 EXPERIMENTAL SETUP:

For all 35 WUDA tasks and 2 UDA tasks, T k is set to 5, T max is set to 30. Learning rate is set to 0.01 for simulated tasks and 0.05 for real-world WUDA tasks and UDA tasks, γ t is set to 0.05 for simulated tasks and 0.02 for real-world WUDA tasks and UDA tasks. Confidence level of labelling function in line 8 of Algorithm 1 is set to 0.95 for 8 digit tasks and 2 UDA tasks, and 0.9 for 24 human-sentiment tasks and 0.8 for real-world WUDA tasks. γ is set to 0.4 for digit tasks, 0.1 for human-sentiment tasks, 0.2 for real-world WUDA tasks and 0.1 for UDA tasks. n l t,max is set to 15, 000 for digit tasks and UDA tasks, 500 for human-sentiment tasks and 4000 for real-world WUDA tasks. N max is set to 1000 for digit tasks and UDA tasks, and 200 for human-sentiment and real-world tasks. Batch size is set to 128 for digit, real-world WUDA tasks and UDA tasks, and 24 for human-sentiment tasks. Penalty parameter is set to 0.01 for digit, real-world WUDA tasks and UDA tasks, and 0.001 for human-sentiment tasks.

To fairly compare all methods, they have the same network structure. Namely, ATDA, DAN, DANN, TCL and B-Net adopt the same network structure for each dataset. Note that DANN and TCL use the same structure for their discriminate networks. All experiments are repeated ten times and we report the average accuracy value and standard deviation (STD) of accuracy values of ten experiments.

F.3 LINKS TO DATASETS:

Digit datasets (MNIST and SYN Digit (SYND)) can be downloaded from official code of ATDA. The link is https://github.com/ksaito-ut/atda.

Sentiment datasets (Amazon products reviews) can be downloaded from the official code of marginalized Stacked Denoising Autoencoder (mSDA). The link is https://www.cse.wustl.edu/~mchen/ code/mSDA.tar.

Real-world datasets (BCIS) can be downloaded from the website of the project "A Testbed for Cross-Dataset Analysis": https://sites.google.com/site/crossdataset/home/files ("setup DENSE decaf7", 1.3GB, decaf7 features).

G RUNNING TIME:

Table 7 shows the average running time of each method on the task SYND→MNIST. Although B-Net trains four networks, its running time is still comparable to most baselines. 

H PROOFS:

This section provides proofs of theorems demonstrated in the supplementary.

H.1 PROOF OF THEOREM 1:

Proof. We will fist prove Eq. ( 4) (Case 1) and then prove Eq. ( 5) (Case 2).

Case 1. According to definition of Rs (h), we have

EQUATION

where (h(x s )) = [ (h(x s ), 1), ..., (h(x s ), K)] T and η(x s ) = [p Ỹs|Xs (1|x s ), . . . , p Ỹs|Xs (K|x s )] T . According to definition of the transition matrix Q, we know that

EQUATION

where η(x s ) = [p Ys|Xs (1|x s ), ... , p Ys|Xs (K|x s )] T . Substituting Eq. ( 11) into Eq. ( 10), we have

Rs (h) = X η T (x s )Q (h(x s ))p xs (x s )dx s = X η T (x s )I (h(x s ))p xs (x s )dx s + X η T (x s )(Q -I) (h(x s ))p xs (x s )dx s = R s (h) + E px s (xs) [η T (x s )(Q -I) (h(x s ))].

Hence, Case 1 is proved.

Lemma 2. Given the multivariate random variable (X t , U t ) with the probability ppo s (x t , u t ) and Eq. ( 15), if

EQUATION

Proof. According to definition of Rpo t (h, ft , u t ) in Theorem 3, we have 

Rpo t (h, ft , u t ) = (1 -ρ ut ) -1 X 1 ut=0 u t (

where (a) is based on the definition of ρ us and Eq. ( 14) and (b) is based on the definition of V t (f t (x t ) = ft (x t ) when V t = 1). This lemma is proved.

Remark 5. In Lemma 2, the assumption E p x t (xt) [ (h(x t ), f t (x t ))] ≤ R t (h, f t ) + ρ s 01 M t means that the expect risk restricted in B (i.e., E p x t (xt) [ (h(x t ), f t (x t ))]) can represent the true risk R t (h, f t ) when ρ s 01 is small, where B = {x : ft (x) = f t (x)}. In Butterfly, it is equivalent to that pseudo labels provided by noisy source data are more useful if we can select more correct data from noisy source data. If this assumption fails, we cannot gain useful knowledge from ft even when we can perfectly select correct data from pseudo-labeled target data (ρ t 01 = 0).

Inequalities ( 16), ( 17) and ( 18) show that if we can avoid to annotate incorrect data as "correct" (ρ s 01 = 0 and ρ 

:

There are two common ways to express the density of noisy m.r.v. (see Appendix A). One way is to use a mixture of densities of correct and incorrect m.r.v..

Figures and Tables:

Figure 2: WUDA ruins representative UDA methods. Representative UDA methods includes deep adaptation networks (DAN, a IPM based method (Long et al., 2015)), domain-adversarial neural network (DANN, a adversarial training based method (Ganin et al., 2016)), asymmetric tri-training domain adaptation (ATDA, a pseudo-label based method(Saito et al., 2017)) and transferable curriculum learning (TCL, a robust UDA method(Shu et al., 2019)). B-Net is our proposed WUDA method. We report target-domain accuracy of all methods when the noise rate of source domain changes (a) from 5% to 70% (symmetry-flip noise) and (b) from 5% to 45% (pair-flip noise). Clearly, when the noise rate of source domain increases, target-domain accuracy of representative UDA methods drops quickly while that of B-Net keeps stable consistently.

Figure3: Butterfly Framework. Two networks (F 1 and F 2 ) in Branch-I are jointly trained on noisy source data and pseudo-labeled target data (mixture domain). Two networks in Branch-II (F t1 and F t2 ) are trained on pseudo-labeled target data. By using dual-checking principle, Butterfly checks high-correctness data out from both mixture and pseudo-labeled target data. After cross-propagating checked data, Butterfly can obtain high-quality domain-invariant representations (DIR) and target-specific representations (TSR) simultaneously in an iterative manner. Note that the interaction between DIR and TSR happens via the shared CNN. Besides, in the first training epoch, since we do not have any pseudo-labeled target data, we need to use noisy source data as the pseudo-labeled target data, which followsSaito et al. (2017).

Figure 4: Target-domain accuracy vs. number of epochs on four SYND→MNIST WUDA tasks.

Figure 5: Target-domain accuracy vs. number of epochs on four MNIST→SYND WUDA tasks.

Figures 4 and 5 show the target-domain accuracy vs. number of epochs among ATDA, Co+ATDA and B-Net. Besides, we show the accuracy of ATDA trained with clean source data (ATDA-TCS) as a reference point. When accuracy of one method is close to that of ATDA-TCS (red dash line), this method successfully eliminates noise effects. From our observations, it is clear that B-Net is very close to ATDA-TCS in 7 out of 8 tasks (except for S→M task with P45, Figure4-(d)), which is an evidence that Butterfly can eliminate noise effects. Since P45 case is the hardest one, it is reasonable that B-Net cannot perfectly eliminate noise effects. An interesting phenomenon is that, B-Net outperforms ATDA-TCS in 2 M→S tasks (Figure5-(a), (c)). This means that B-Net transfers more useful knowledge (from noisy source data to unlabeled target data) even than ATDA-TCS (from clean source data to unlabeled target data). Results on real-world WUDA (including 3 tasks). Table2reports the target-domain accuracy for 3 tasks. B-Net enjoys the best performance on all tasks. It should be noted that, in both Bing→Caltech256 and Bing→ImageNet tasks, ATDA is slightly worse than B-Net. However, in Bing→SUN task, ATDA is much worse than B-Net. The reason is that the DIR between Bing and SUN are more affected by noisy source data. This phenomenon is also observed when comparing DANN and TCL. Compared to Co+ATDA, ATDA is slightly better than Co+ATDA. This abnormal phenomenon can be explained using ∆ (see Section 4), after using Co-teaching to assign pseudo labels for noisy source data, the second term in ∆ s may increase, which results in that ∆ increases, i.e., noise effects actually increase. This phenomenon is an evidence that a two-step method may not really reduce noise effects. Results on two UDA tasks. Table3reports the target-domain accuracy for 2 common UDA tasks. The target-domain accuracy of DAN, DANN and ATDA are results reported bySaito et al. (2017). Although the target-domain accuracy of B-Net is not always higher than that of ATDA, B-Net still has satisfactory performance on UDA problem. Note that, since B-Net is a WUDA method, it is reasonable that B-Net is not the state-of-the-art UDA method. Ablation study. Finally, we conduct thorough experiments to show the contribution of individual components in B-Net. We report average target-domain accuracy on 32 simulated WUDA tasks (8 digit and 24

to check data in MD and TD. 4) B-Net-S: train B-Net where the check is turned on for Source data in MD. 5) B-Net-T: train B-Net where the check is turned on for Target data in TD. 6) B-Net-ST: train B-Net where the checks are turned on for Source data in MD and Target data in TD. 7) B-Net-M: train B-Net where the check is turned on for all data in MD. Note that in the full B-Net, the checks are turned on for all data in MD and Target data in TD. Comparing B-Net with B w/o C reveals whether the constraint |θ T f 11 θ f 21 | takes effects. Comparing B-Net with DCP-D and DCP-M shows whether realizing DCP via Co-teaching is the optimal way. Comparing B-Net with B-Net-S, B-Net-T, B-Net-ST and B-Net-M reveals whether DCP is necessary. Table

Figure 6: Visualization of MNIST and SYND.

Figure 7: Visualization of Bing, Caltech256, ImageNet and SUN (taking "horse" as the common class).

ns i=1 and D t = {x ti } nt i=1 drawn from Ps and P xt , in wildly unsupervised domain adaptation, we aim to train with Ds and D t to accurately annotate data drawn from P xt , where p xs = p xt . Remark 1. In Definition 1, Ds is noisy source data, D t is unlabeled target data, and Ps and P xt are two probability measures corresponding to densities ps (x s , ỹs ) and p xt (x t ).

Table content: <table/>

Algorithm 1 Butterfly Framework: quadruple training for WUDA problem 1: Input Ds, Dt, learning rate η, fixed τ , fixed τt, epoch T k and Tmax, iteration Nmax, # of pseudo-labeled target data ninit, max of ninit n l t,max ;

Table content: <table><tr><td>2: Initial F1, F2, Ft1, Ft2, Dl t = Ds, D = Ds, n l t = ninit;</td><td/></tr><tr><td>for T = 1, 2, . . . , Tmax do</td><td/></tr><tr><td>3: Shuffle training set D;</td><td>// Noisy dataset</td></tr><tr><td>for N = 1, . . . , Nmax do</td><td/></tr><tr><td>4: Fetch mini-batch Ď from D; 5: Update Branch-I: F1, F2 = Checking(F1, F2, Ď, η, R(T ));</td><td>// Check data in MD using Algorithm 2</td></tr><tr><td>6: Fetch mini-batch Ďt from Dl t ; 7: Update Branch-II: Ft1, Ft2 = Checking(Ft1, Ft2, Ďt, η, Rt(T ));</td><td>// Check data in TD using Algorithm 2</td></tr><tr><td>end</td><td/></tr><tr><td>8: Obtain Dl t = Labelling(F1, F2, Dt, n l t );</td><td>// Label Dt, following Saito et al. (2017)</td></tr><tr><td>9: Obtain D = Ds ∪ Dl t ; 10: Update n l t = min{T /20  *  nt, n l t,max };</td><td>// Update MD</td></tr></table>

Target-domain accuracy on 8 digit WUDA tasks (SYND↔MNIST). Bold value represents the highest accuracy in each row.

Table content: <table><tr><td colspan="3">Tasks Type DAN</td><td>DANN</td><td>ATDA</td><td>TCL</td><td>Co+TCL</td><td>Co+ATDA B-Net</td></tr><tr><td/><td>P20</td><td colspan="3">90.17% 79.06% 55.95%</td><td>80.81%</td><td>88.56%</td><td>95.37%</td><td>95.29%</td></tr><tr><td/><td>P45</td><td colspan="3">67.00% 55.34% 53.66%</td><td>55.97%</td><td>73.27%</td><td>75.43%</td><td>90.21%</td></tr><tr><td>S→M</td><td>S20</td><td colspan="3">90.74% 75.19% 89.87%</td><td>80.23%</td><td>85.88%</td><td>95.22%</td><td>95.88%</td></tr><tr><td/><td>S45</td><td colspan="3">89.31% 65.87% 87.53%</td><td>68.54%</td><td>75.69%</td><td>92.03%</td><td>94.97%</td></tr><tr><td/><td>P20</td><td colspan="3">40.82% 58.78% 33.74%</td><td>58.88%</td><td>59.08%</td><td>58.02%</td><td>60.36%</td></tr><tr><td/><td>P45</td><td colspan="3">28.41% 43.70% 19.50%</td><td>45.31%</td><td>47.15%</td><td>46.80%</td><td>56.62%</td></tr><tr><td>M→S</td><td>S20</td><td colspan="3">30.62% 53.52% 49.80%</td><td>56.74%</td><td>56.91%</td><td>56.64%</td><td>57.05%</td></tr><tr><td/><td>S45</td><td colspan="3">28.21% 43.76% 17.20%</td><td>49.91%</td><td>51.22%</td><td>54.29%</td><td>56.18%</td></tr><tr><td colspan="2">Average</td><td colspan="3">58.16% 58.01% 50.91%</td><td>62.05%</td><td>67.22%</td><td>71.73%</td><td>75.82%</td></tr></table>

Table3reports the target-domain accuracy for 2 common UDA tasks. The target-domain accuracy of DAN, DANN and ATDA are results reported bySaito et al. (2017). Although the target-domain accuracy of B-Net is not always higher than that of ATDA, B-Net still has satisfactory performance on UDA problem. Note that, since B-Net is a WUDA method, it is reasonable that B-Net is not the state-of-the-art UDA method. Ablation study. Finally, we conduct thorough experiments to show the contribution of individual components in B-Net. We report average target-domain accuracy on 32 simulated WUDA tasks (8 digit and 24 Target-domain accuracy on 3 real-world WUDA tasks. The source domain is the Bing dataset that contains noisy information from the Internet. Bold value represents the highest accuracy in each row.

Table content: <table><tr><td>Target</td><td>DAN</td><td>DANN</td><td>ATDA</td><td>TCL</td><td>Co+TCL</td><td colspan="2">Co+ATDA B-Net</td></tr><tr><td colspan="2">Caltech256 77.83%</td><td colspan="2">78.00% 80.84%</td><td>79.35%</td><td>79.27%</td><td>79.89%</td><td>81.71%</td></tr><tr><td>Imagenet</td><td>70.29%</td><td colspan="2">72.16% 74.89%</td><td>72.53%</td><td>72.33%</td><td>74.73%</td><td>75.00%</td></tr><tr><td>SUN</td><td>24.56%</td><td colspan="2">26.80% 26.26%</td><td>28.80%</td><td>29.15%</td><td>26.31%</td><td>30.54%</td></tr><tr><td>Average</td><td>57.56%</td><td colspan="2">58.99% 60.66%</td><td>60.23%</td><td>60.25%</td><td>60.31%</td><td>62.42%</td></tr></table>

Target-domain accuracy on 2 UDA tasks. Bold value represents the highest accuracy in each row.

Table content: <table><tr><td>Tasks</td><td>DAN</td><td>DANN</td><td>ATDA</td><td>B-Net</td></tr><tr><td colspan="2">MNIST→SVHN -</td><td colspan="3">35.70% 52.80% 52.64%</td></tr><tr><td colspan="2">SVHN→MNIST 71.10%</td><td colspan="2">71.10% 85.00%</td><td>85.82%</td></tr></table>

Results of ablation study. Average target-domain accuracy on 8 simulated digit WUDA tasks (Digit), 24 simulated human-sentiment WUDA tasks (Sentiment) and 3 real-world WUDA tasks (Real-world). Bold value represents the highest accuracy in each row.

Table content: <table><tr><td>Digit</td><td>74.52%</td><td>59.19% 70.85% 71.93%</td><td>52.00%</td><td>72.27%</td><td>73.89%</td><td>75.82%</td></tr><tr><td>Sentiment</td><td>63.57%</td><td>61.37% 63.39% 61.49%</td><td>61.12%</td><td>61.73%</td><td>62.21%</td><td>63.77%</td></tr><tr><td colspan="2">Real-world 62.27%</td><td>59.82% 62.34% 61.91%</td><td>60.87%</td><td>62.24%</td><td>62.17%</td><td>62.42%</td></tr></table>

represent expected discrepancy between two labelling functions h, h under different marginal densities; 7) the ground-truth and pseudo labeling function of the target domain are denoted by f t (x t ) and ft (x t ). Ds to unlabelled target data D t directly. We first present a theorem to show relations between R s (h) and Rs (h). Theorem 1. For any labelling function h : X → Y, if ps (x s , ỹs ) is generated by a transition matrix Q as demonstrated in Appendix A.1, we have Rs

Table content: <table><tr><td>D.1 WUDA RUINS UDA METHODS</td></tr><tr><td>Theoretically, we analyze why existing UDA methods cannot well transfer useful knowledge from noisy</td></tr><tr><td>source data</td></tr></table>

Target-domain accuracy on 12 human-sentiment WUDA tasks with the 20% noise rate. Bold values mean the highest values in each row.

Table content: <table><tr><td>Tasks</td><td>DAN</td><td>DANN</td><td>ATDA</td><td>TCL</td><td>Co+TCL</td><td colspan="2">Co+ATDA B-Net</td></tr><tr><td>B→D</td><td>68.28%</td><td>68.08%</td><td colspan="3">70.31% 71.40% 67.81%</td><td>66.70%</td><td>71.84%</td></tr><tr><td>B→E</td><td>63.78%</td><td>63.53%</td><td colspan="3">72.79% 65.08% 60.54%</td><td>68.89%</td><td>75.92%</td></tr><tr><td>B→K</td><td>65.48%</td><td>64.63%</td><td colspan="3">71.79% 66.80% 61.23%</td><td>66.51%</td><td>76.32%</td></tr><tr><td>D→B</td><td>64.63%</td><td>64.52%</td><td colspan="3">70.25% 67.33% 65.22%</td><td>68.04%</td><td>70.56%</td></tr><tr><td>D→E</td><td>65.33%</td><td>65.16%</td><td colspan="3">69.99% 66.74% 64.55%</td><td>67.32%</td><td>73.73%</td></tr><tr><td>D→K</td><td>65.68%</td><td>66.28%</td><td colspan="3">74.53% 68.82% 67.98%</td><td>72.20%</td><td>77.97%</td></tr><tr><td>E→B</td><td>60.41%</td><td>60.15%</td><td colspan="3">63.89% 63.13% 61.18%</td><td>61.08%</td><td>62.22%</td></tr><tr><td>E→D</td><td>62.35%</td><td>61.67%</td><td colspan="3">62.30% 62.93% 60.81%</td><td>59.77%</td><td>63.53%</td></tr><tr><td>E→K</td><td>72.05%</td><td>71.51%</td><td colspan="3">74.00% 75.36% 72.65%</td><td>70.85%</td><td>78.96%</td></tr><tr><td>K→B</td><td>59.94%</td><td>59.40%</td><td colspan="3">63.53% 62.77% 60.71%</td><td>61.22%</td><td>63.36%</td></tr><tr><td>K→D</td><td>61.46%</td><td>61.51%</td><td colspan="3">64.66% 64.16% 64.15%</td><td>64.94%</td><td>66.98%</td></tr><tr><td>K→E</td><td>70.60%</td><td>72.23%</td><td colspan="3">74.75% 74.14% 68.95%</td><td>69.69%</td><td>76.96%</td></tr><tr><td colspan="2">Average 65.00%</td><td>64.89%</td><td colspan="3">69.40% 67.39% 64.65%</td><td>66.43%</td><td>71.53%</td></tr></table>

Target-domain accuracy on 12 human-sentiment WUDA tasks with the 45% noise rate. Bold values mean the highest values in each row.

Table content: <table><tr><td>Tasks</td><td>DAN</td><td>DANN</td><td>ATDA</td><td>TCL</td><td>Co+TCL</td><td colspan="2">Co+ATDA B-Net</td></tr><tr><td>B→D</td><td>52.43%</td><td>52.98%</td><td colspan="3">53.56% 54.44% 53.21%</td><td>54.32%</td><td>56.59%</td></tr><tr><td>B→E</td><td>52.17%</td><td>53.50%</td><td colspan="3">55.14% 54.14% 53.98%</td><td>57.34%</td><td>55.74%</td></tr><tr><td>B→K</td><td>52.89%</td><td>51.84%</td><td colspan="3">51.14% 53.32% 51.77%</td><td>53.28%</td><td>57.00%</td></tr><tr><td>D→B</td><td>53.11%</td><td>53.04%</td><td colspan="3">54.48% 53.27% 54.85%</td><td>55.95%</td><td>55.15%</td></tr><tr><td>D→E</td><td>51.30%</td><td>53.04%</td><td colspan="3">54.21% 53.77% 55.63%</td><td>56.08%</td><td>58.91%</td></tr><tr><td>D→K</td><td>52.15%</td><td>53.17%</td><td colspan="3">57.99% 52.45% 58.10%</td><td>59.94%</td><td>66.20%</td></tr><tr><td>E→B</td><td>51.38%</td><td>51.08%</td><td colspan="3">52.54% 52.14% 54.88%</td><td>53.30%</td><td>54.93%</td></tr><tr><td>E→D</td><td>52.83%</td><td>51.24%</td><td colspan="3">49.02% 52.57% 50.03%</td><td>49.62%</td><td>52.88%</td></tr><tr><td>E→K</td><td>54.21%</td><td>53.58%</td><td colspan="3">51.66% 55.04% 56.15%</td><td>52.10%</td><td>56.12%</td></tr><tr><td>K→B</td><td>50.44%</td><td>51.77%</td><td colspan="3">51.96% 51.50% 53.81%</td><td>52.59%</td><td>51.39%</td></tr><tr><td>K→D</td><td>52.20%</td><td>51.45%</td><td colspan="3">52.86% 53.19% 55.69%</td><td>54.52%</td><td>53.53%</td></tr><tr><td>K→E</td><td>54.72%</td><td>53.33%</td><td>52.11%</td><td colspan="2">53.46% 51.26%</td><td>52.62%</td><td>53.71%</td></tr><tr><td colspan="2">Average 52.49%</td><td>52.50%</td><td colspan="3">53.65% 53.27% 54.11%</td><td>54.31%</td><td>56.01%</td></tr><tr><td colspan="3">F EXPERIMENTAL SETTINGS</td><td/><td/><td/><td/></tr><tr><td colspan="4">F.1 NETWORK STRUCTURE AND OPTIMIZER</td><td/><td/><td/></tr></table>

The architecture of B-Net for digit WUDA tasks SYND ↔ MNIST. We added BN layer in the last convolution layer in CNN and FC layers in F 1 and F 2 . We also used dropout in the last convolution layer in CNN and FC layers in F 1 , F 2 , F t1 and F t2 (dropout probability is set to 0.5). The architecture of B-Net for human-sentiment WUDA tasks. We added BN layer in the first FC layers in F 1 and F 2 . We also used dropout in the first FC layers in F 1 , F 2 , F t1 and F t2 (dropout probability is set to 0.5).

Table content: <table><tr><td>DIR</td><td/><td/><td/></tr><tr><td>conv 5x5x64 ReLU Figure 8: FC 50 max-pool 3x3 2x2 stride conv 5x5x64 ReLU max-pool 3x3 2x2 stride 5x5x128 conv ReLU CNN units ReLU FC 50 units ReLU FC 50 units ReLU FC 50 units ReLU DIR DIR TSR TSR Input 5000 units units ReLU FC 128 units ReLU FC 128 units ReLU DIR TSR TSR Input 4096 units FC 1024 units ReLU FC 1024 units ReLU FC 1024 units ReLU Figure 9: FC 128 FC 128 units ReLU FC 1024 units ReLU</td><td>FC 3072 units ReLU FC 2 units Softmax FC 2 units Softmax FC 2 units Softmax FC 2 units Softmax F1 F2 Ft1 Ft2 FC 40 units Branch-I FC 2048 units ReLU FC 2048 units ReLU FC 2048 units ReLU FC 2048 units ReLU DIR DIR TSR TSR Branch-II Softmax FC 40 units Softmax FC 40 units Softmax Branch-I FC 10 units Softmax FC 10 units Softmax FC 10 units Softmax FC 10 units Softmax Branch-II F1 F2 Ft1 FC 40 units Ft2 Softmax</td><td>F1 F2 Ft1 Ft2</td><td>Branch-I Branch-II</td></tr></table>

Running time for each method on the task SYND→MNIST (minutes).

Table content: <table><tr><td colspan="4">Methods DAN DANN ATDA</td><td>TCL</td><td colspan="2">Co+ATDA B-Net</td></tr><tr><td>Time</td><td>17.17</td><td>9.02</td><td>17.17</td><td>14.04</td><td>18.28</td><td>20.55</td></tr></table>

h(x t ), ft (x t ))p po t (x t , u t )dx t = (1 -ρ ut ) -1 X (h(x t ), ft (x t ))p po Xt|Ut (x t |1)p po Ut (1)dx t -ρ ut ) -1 (1 -ρ ut ) x s ), ft (x t )) ρ t 01 q xt (x t ) + ρ t 11 p po Xt|Vt (x t |1) dx t = ρ t 01 E qx t (xt) [ (h(x t ), ft (x t ))] + ρ t 11 X (h(x t ), ft (x t ))p po Xt|Vt (x t |V t = 1)dx t (b) = ρ t 01 E qx t (xt) [ (h(x t ), ft (x t ))] + ρ t 11 X(h(x t ), f t (x t ))p po Xt|Vt (x t |V t = 1)dx

Table content: <table><tr><td>(a) = (1</td></tr></table>

Since E p x t (xt) [ (h(x t ), f t (x t ))] ≤ R t (h, f t ) + ρ s 01 M t , we have Rpo t (h, ft , u t ) ≤ ρ t 01 E qx t (xt) [ (h(x t ), ft (x t ))] + ρ t 11 (R t (h, f t ) + ρ s 01 M t ). R t (h, f t )| = |ρ t 01 E qx t (xt) [ (h(x t ), ft (x t ))] + ρ t 11 E p x t (xt) [ (h(x t ), f t (x t ))] -R t (h, f t )| ≤ |ρ t 01 E qx t (xt) [ (h(x t ), ft (x t ))] + ρ t 11 (R t (h, f t ) + ρ s 01 M t ) -R t (h, f t )| = |ρ t 01 (E qx t (xt) [ (h(x t ), ft (x t ))] -R t (h, f t )) + ρ t 11 ρ s 01 M t | ≤ ρ t 01 max{E qx t (xt) [ (h(x t ), ft (x t ))], R t (h, f t )} + ρ t 11 ρ s 01 M t .

Table content: <table><tr><td>(20)</td></tr><tr><td>Thus, we have</td></tr><tr><td>| Rpo</td></tr></table>

t 01 = 0), we have Rpo s (h, u s ) = R s (h), Rpo s (h, ft , u t ) = R s (h, ft ) and Rpo t (h, ft , u t ) = R t (h, f t ). Nonetheless, ρ s 01 and ρ t 01 never equal 0, and E qs(xs,ys) [ (h(x), y)], E qx s (xs) [ (h(x s ), ft (x s ))] and E qx t (xt)[ (h(x t  ), ft (x t ))] may equal +∞ for some h. In next section, we prove that, under the assumption in Remarks 2 and 3, Rpos (h, u s ) → R s (h), Rpo s (h, ft , u t ) → R s (h, ft ) and Rpo t (h, ft , u t ) → R t (h, f t ) if ρ s01 → 0 and ρ t 01 → 0. Moreover, we give a new upper bound of R t (h, f t ).Proof. We first prove upper bounds of| Rpo s (h, u s )-R s (h)|, | Rpo s (h, ft , u t )-R s (h, ft )| and | Rpo t (h, ft , u t )-R t (h, f t )| under assumptions in Theorem 3.Based on Lemma 1, we have| Rpo s (h, u s ) -R s (h)| = |ρ s 01 E qs(xs,ys) [ (h(x s ), y s )] -(1 -ρ s 11 )R s (h)| ≤ |ρ s 01 (R s (h) + M s ) -ρ s 01 R s (h)| = ρ s 01 M s .Specifically, ∀ ∈ (0, 1), let δ t = /M t and δ s = / max{M s , ρ t 11 M t }. When ρ s 01 < δ s and ρ t 01 < δ t , we have Hence, we prove the Eq. (8). In following, we give a new upper bound of R t (h, f t ). Call back to Theorem 2, we replace 1) Rs (h) with Rpo Rpos (h, u s ) -R s (h)| + | Rpo s (h, ft , u t ) -R s (h, ft )| + |R t (h, f t ) -Rpo s (h,ft , u t )|. Let ρ s 01 ≤ δ s and ρ t 01 ≤ δ t , we have R t (h, f t ) ≤ Rpo s (h, u s )

Table content: <table><tr><td>H.3.2 PROOF OF THEOREM 3</td><td/><td/><td/><td/></tr><tr><td colspan="2">Now, we prove Theorem 3 as follows.</td><td/><td/><td/></tr><tr><td>Similar, we have</td><td/><td/><td/><td/></tr><tr><td/><td>| Rpo</td><td/><td/><td/></tr><tr><td>| Rpo</td><td/><td/><td/><td/></tr><tr><td/><td/><td/><td colspan="2">(iii) domain dissimilarity</td></tr><tr><td>+</td><td>2</td><td>+</td><td>2</td><td>,</td></tr><tr><td colspan="2">(iv) noise effects from source ∆s</td><td/><td>(v) noise effects from target ∆t</td><td/></tr><tr><td>Hence, we prove this theorem.</td><td/><td/><td/><td/></tr></table>

Peer review (iclr2020):
This paper proposes a new problem setting in the domain adaptation field. Since it is impossible to obtain perfectly clean labeled source data in the real world, existing UDA methods cannot well handle real-world data. However, in wildly unsupervised domain adaptation (WUDA), we do not need a perfectly clean source data, which means that WUDA problem is a more general and realistic problem than existing ones. To address WUDA problem, the authors proposed Butterfly framework (based on dual checking principle) to simultaneously reduce the 1) noise effects in source domain and 2) distributional discrepancy between source and target domains. They tested the proposed method on simulated and real-world WUDA tasks (35 tasks in total), and the accuracy of proposed method is higher than those of representative UDA methods. They claim that Butterfly can eliminate noise effect, which is strongly supported by Figures 2, 4 and 5. They also present the ablation study to show that each part in Butterfly is meaningful. In general, this paper is easy to follow and clearly presents the main idea and learning procedures of Butterfly. Since WUDA, as a new problem, could lead a new research direction in the domain adaptation field, this paper should be presented in ICLR 2020. Detailed comments can be seen below. Pros: + WUDA, as a new problem, is very important for the domain adaptation field. + Butterfly, as a solution to WUDA, outperforms representative UDA methods on simulated and real-world WUDA tasks. + All claims are strongly supported by experimental results, and ablation study shows that each part in Butterfly is a necessary component. + Following Ben-David*s paper, this paper also presents an upper bound of the target domain risk. This is 1) the first WUDA bound and 2) probably the first DA bound related to pseudo labelling function. The conditions in Remark 3 are very interesting. + It is very nice to use noise effect Delta to explain the abnormal phenomenon in experiments. Cons: - The color scheme of figures is not friendly to color-blind people. The authors should do different line styles or marker styles. - The interaction between DIR and TSR happens via shared CNN, right? The authors should explain this in the caption of Figure 3. - When T = 1, you directly use source data as the pseudo-labeled target data since there are no pseudo-labeled target data in the first step (based on Algorithm 1). Is that correct? If yes, the authors should explain this in Figure 3 and the description of Algorithm 1. If no, please give a detailed explanation.