summaries: This paper introduces the idea of wildly unsupervised domain adaptation, where the source labels are noisy and the target data is unsupervised. To tackle this, the authors propose an architecture based one two branches: one acting on the mixed source-target data and the other on the target data only. During training, each branch is updated using the idea of co-teaching, by finding the samples with the lowest loss values. Pseudo-labeling is then applied to the target data, and the process iterates. 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.  This paper presents a method for unsupervised domain adaptation. The problem is well known in literature and follows the setting of labeled source and unlabeled target set. This work proposes the “butterfly network” suitable to train on noisy data (labels) and assign pseudo-labels to the target set. The butterfly network consists in two branches one for source+target and one for target only data. Both use the same optimization objective and a “checking” mechanism has been devised for pseudo-labelling the data.
abstractText: 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.
references.authors: D. Arpit S. Jastrzebski N. Ballas D. Krueger E. Bengio M. Kanwal T. Maharaj A. Fischer A. Courville Y. Bengio
references.title: A closer look at memorization in deep networks
references.authors: S. Ben-David J. Blitzer K. Crammer A. Kulesza F. Pereira J.W. Vaughan
references.title: A theory of learning from different domains. MLJ
references.authors: Y. Bengio
references.title: Evolving culture versus local minima
references.venue: In Growing Adaptive Machines,
references.authors: A. Bergamo L. Torresani
references.title: Exploiting weakly-labeled web images to improve object classification: a domain adaptation approach
references.venue: In NeurIPS,
references.authors: J. Deng W. Dong R. Socher L. Li K. Li F. Li
references.title: Imagenet: A large-scale hierarchical image database
references.venue: In CVPR,
references.authors: Y. Ganin V.S. Lempitsky
references.title: Unsupervised domain adaptation by backpropagation
references.venue: In ICML,
references.authors: M. Ghifary D. Balduzzi W.B. Kleijn M. Zhang
references.title: Scatter component analysis : A unified framework for domain adaptation and domain generalization
references.venue: doi: 10.1109/TPAMI
references.authors: B. Gong Y. Shi F. Sha K. Grauman
references.title: Geodesic flow kernel for unsupervised domain adaptation
references.venue: In CVPR, pages 2066–2073,
references.authors: M. Gong K. Zhang T. Liu D. Tao C. Glymour
references.title: Domain adaptation with conditional transferable components
references.venue: In ICML,
references.authors: M. Gong K. Zhang B. Huang C. Glymour D. Tao K. Batmanghelich
references.title: Causal generative domain adaptation
references.venue: networks. CoRR,
references.authors: A. Gretton K.M. Borgwardt M.J. Rasch B. Schölkopf A.J. Smola
references.title: A kernel two-sample test
references.venue: JMLR, 13:723–773,
references.authors: G. Griffin A. Holub P. Perona
references.title: Caltech-256 object category dataset
references.venue: Technical report, California Institute of Technology,
references.authors: Y. Guo M. Xiao
references.title: Cross language text classification via subspace co-regularized multi-view learning
references.venue: In ICML,
references.authors: B. Han Q. Yao X. Yu G. Niu M. Xu W. Hu I.W. Tsang M. Sugiyama
references.title: Co-teaching: Robust training of deep neural networks with extremely noisy labels
references.venue: In NeurIPS,
references.authors: J. Hoffman E. Tzeng T. Park J. Zhu P. Isola K. Saenko A.A. Efros T. Darrell
references.title: Cycada: Cycleconsistent adversarial domain adaptation
references.venue: In ICML,
references.authors: L. Jiang Z. Zhou T. Leung L. Li F. Li
references.title: Mentornet: Learning data-driven curriculum for very deep neural networks on corrupted labels
references.venue: In ICML,
references.authors: J. Lee M. Raginsky
references.title: Minimax statistical learning with wasserstein distances
references.venue: In NeurIPS,
references.authors: K. Lee X. He L. Zhang L. Yang
references.title: Cleannet: Transfer learning for scalable image classifier training with label noise
references.venue: In CVPR,
references.authors: Y. Li X. Tian M. Gong Y. Liu T. Liu K. Zhang D. Tao
references.title: Deep domain generalization via conditional invariant adversarial networks
references.venue: In ECCV,
references.authors: T. Liu D. Tao
references.title: Classification with noisy labels by importance reweighting
references.authors: M. Long Y. Cao J. Wang M.I. Jordan
references.title: Learning transferable features with deep adaptation networks
references.venue: In ICML,
references.authors: E. Malach S. Shalev-Shwartz
references.title: Decoupling "when to update" from "how to update
references.venue: In NeurIPS,
references.authors: S. Motiian Q. Jones S.M. Iranmanesh G. Doretto
references.title: Few-shot adversarial domain adaptation
references.venue: In NeurIPS,
references.authors: Giorgio Patrini Alessandro Rozza Aditya Krishna Menon Richard Nock Lizhen Qu
references.title: Making deep neural networks robust to label noise: A loss correction approach
references.venue: In CVPR,
references.authors: K. Saito Y. Ushiku T. Harada
references.title: Asymmetric tri-training for unsupervised domain adaptation
references.venue: In ICML,
references.authors: K. Saito K. Watanabe Y. Ushiku T. Harada
references.title: Maximum classifier discrepancy for unsupervised domain adaptation
references.venue: In CVPR,
references.authors: F. Schroff A. Criminisi A. Zisserman
references.title: Harvesting image databases from the web
references.venue: TPAMI, 33(4):754–766,
references.authors: Y. Shu Z. Cao M. Long J. Wang
references.title: Transferable curriculum for weakly-supervised domain adaptation
references.venue: In AAAI,
references.authors: T. Tommasi T. Tuytelaars
references.title: A testbed for cross-dataset analysis
references.venue: In ECCV TASK-CV Workshops,
references.authors: E. Tzeng J. Hoffman T. Darrell K. Saenko
references.title: Simultaneous deep transfer across domains and tasks
references.venue: In ICCV,
references.authors: E. Tzeng J. Hoffman K. Saenko T. Darrell
references.title: Adversarial discriminative domain adaptation
references.venue: In CVPR,
references.authors: J. Xiao J. Hays K.A. Ehinger A. Oliva A. Torralba
references.title: SUN database: Large-scale scene recognition from abbey to zoo
references.venue: In CVPR,
references.authors: M. Xiao Y. Guo
references.title: Feature space independent semi-supervised domain adaptation via kernel matching
references.venue: TPAMI, 37(1):54–66,
references.authors: T. Xiao T. Xia Y. Yang C. Huang X. Wang
references.title: Learning from massive noisy labeled data for image classification
references.venue: In CVPR,
references.authors: K. Zhang B. Schölkopf K. Muandet Z. Wang
references.title: Domain adaptation under target and conditional shift
references.venue: In ICML,
references.authors: K. Zhang M. Gong B. Schölkopf
references.title: Multi-source domain adaptation: A causal view
references.venue: In AAAI,
references.authors: j|Ys = i
references.title: The transition matrix Q is easily estimated in certain situations (Liu and Tao, 2016). However, in more complex situations, such as clothing1M dataset (Xiao et al., 2015), noisy source data is directly generated by selecting data from a pool, which mixes correct data (data with correct labels) and incorrect data (data with incorrect labels)
references.authors:  . Following Han
references.title: 2018), we can corrupt clean-label datasets manually using the noise transition matrix Q . C DATASETS VISUALIZATION Figure 6 shows datasets: MNIST and SYND
references.venue: Figure 7 shows datasets: Bing,
references.authors: Griffin
references.title: Under review as a conference paper at ICLR 2020 (a) Bing provided by Bergamo and Torresani
references.authors: Xiao
references.title: Visualization of 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
references.venue: X ⊂ R and Y = {1,
references.authors: deep learning Arpit
references.title: After cross-propagating these checked data
sections.heading: 1 INTRODUCTION
sections.text: 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., 2010; Ganin and Lempitsky, 2015; Xiao and Guo, 2015; Zhang et al., 2015; 2013). Currently, DA can be divided into three categories: supervised DA (Tzeng et al., 2015), semi-supervised DA (Guo and Xiao, 2012) and unsupervised DA (UDA) (Saito et al., 2017). When the number of labeled data is few in target domain, supervised DA is also known as few-shot DA (Motiian et al., 2017). Since unlabeled data in target domain can be easily obtained, UDA exhibits the greatest potential in the real world (Ganin and Lempitsky, 2015; Ganin et al., 2016; Gong et al., 2012; 2016; Long et al., 2015; Saito et al., 2017; 2018).
  UDA methods train with clean labeled data in source domain (i.e., clean source data) and unlabeled data in target domain (i.e., unlabeled target data) to obtain classifiers for the target domain (TD), which mainly consist of three orthogonal techniques: integral probability metrics (IPM) (Ghifary et al., 2017; Gong et al., 2016; Gretton et al., 2012; Lee and Raginsky, 2018; Long et al., 2015), adversarial training (Ganin et al., 2016; Gong et al., 2018; Hoffman et al., 2018; Li et al., 2018; Saito et al., 2018; Tzeng et al., 2017) and pseudo labeling (Saito et al., 2017). Compared to IPM- and adversarial-training-based methods, the pseudolabeling-based method (i.e., asymmetric tri-training domain adaptation (ATDA) (Saito et al., 2017)) can construct a high-quality target-specific representation, providing a better classification performance.
  However, in the wild, the data volume of source domain tends to be large. To avoid the expensive labeling cost, labeled data in source domain normally come from amateur annotators or the Internet (Lee et al., 2018; Schroff et al., 2011; Tommasi and Tuytelaars, 2014). This brings us a new, more realistic and more challenging problem, wildy unsupervised domain adaptation (abbreviated as WUDA, Figure 1). This adaptation aims to
  transfer knowledge from noisy labeled data in source domain (P̃s, i.e., noisy source data) to unlabeled target data (Pxt ). 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 (Ps) to unlabeled target data (Pxt ). 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 (P̂s) to unlabeled target data (Pxt). 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 Pxt , 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.
sections.heading: 2 WILDLY UNSUPERVISED DOMAIN ADAPTATION
sections.text: 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 Xt be a multivariate random variable defined on the space X with respective a probability density pxt , (Xs, Ys) be a multivariate random variable defined
  on the space X ×C with respective a probability density p̃s, where C = {1, . . . ,K}. Let pxs be the marginal probability density of p̃s. Given i.i.d. data D̃s = {(xsi, ỹsi)}nsi=1 and Dt = {xti} nt i=1 drawn from P̃s and Pxt , in wildly unsupervised domain adaptation, we aim to train with D̃s and Dt to accurately annotate data drawn from Pxt , where pxs 6= pxt . Remark 1. In Definition 1, D̃s is noisy source data, Dt is unlabeled target data, and P̃s and Pxt are two probability measures corresponding to densities p̃s(xs, ỹs) and pxt(xt).
  Nature of WUDA. Specifically, there are five distributions involved in WUDA setting: 1) a marginal distribution on source data, i.e., pxs in Definition 1; 2) a marginal distribution on target data, i.e., pxt in Definition 1; 3) an incorrect conditional distribution of label given xs, q(ys|xs); 4) a correct conditional distribution of label given xs, p(ys|xs) and 5) a correct conditional distribution of label given xt, p(yt|xt).
  Based on Definition 1 and Appendix A.2, noisy source data D̃s are drawn from p̃s(xs, ys) = pxs(xs)((1− ρ)p(ys|xs) + ρq(ys|xs)), where ρ is the noise rate in source data. Namely, source data D̃s are mixture of correct source data from pxs(xs)p(ys|xs) and incorrect data from pxs(xs)q(ys|xs). Target data Dt are drawn from pxt . In WUDA setting, we aim to train a classifier with D̃s and Dt. This classifier is expected to accurately annotate data from pxt , 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 (D̃s in Definition 1) are drawn from P̃s whose density is p̃s(xs, ys) = pxs(xs)((1− ρ)p(ys|xs) + ρq(ys|xs)). We draw the target data Dt from Pxt whose density is pxt . 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.
sections.heading: 3 BUTTERFLY: TOWARDS ROBUST ONE-STEP APPROACH
sections.text: 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.
  L(θ, u;F,D) = 1∑n i=1 ui n∑ i=1 ui`(F (xi), y̌i), (1)
  where n is the batch size, and F represents a network (e.g., F1, F2, Ft1 and Ft2). D = {(xi, y̌i)}ni=1 is a mini-batch for training a network, where {xi, y̌i}ni=1 could be data in MD or TD (Figure 3), and θ represents parameters of F and u = [u1, ..., un]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 |θTf11θf21| in their loss functions, where θf11 and θf21 are weights of the first fully-connect layer of F1 and F2. With this regularizer, F1 and F2 will learn from different features. Nature of the loss L. In loss function L, we have n instances: (xi, y̌i), where i = 1, 2, . . . , n. For the ith instance, we will compute its cross-entropy loss (i.e., `(F (xi), y̌i)), and we will denote this instance as “selected” if ui = 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 ui = 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 D̃lt for Branch-II), four networks (F1, F2, Ft1 and Ft2) and the number of pseudo labels (line 2). In the first epoch (T = 1), following Saito et al. (2017), D̃lt is the same with D̃s (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 Ď is fetched from D̃ (line 4), F1 and F2 check high-correctness data out and update their parameters (lines 5) using Algorithm 2. Using similar procedures, Ft1 and Ft2 also update their parameters using Algorithm 2 (lines 6-7).
  In each epoch, after Nmax mini-batch updating, we randomly select nlt unlabeled target data and assign them pseudo labels using F1 and F2 (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 F1 and F2 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 D̃lt for training Branch-II in the next epoch. Then, we merge D̃ l t and D̃s to be D̃ for training Branch-I in the next epoch (line 9). Finally, we update nlt, R(T ) and Rt(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 ≥ Tk, R(T ) = 1− τ ; when T ≤ Tk, R(T ) = 1− T/Tk × τ . 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 F1 and F2, and 2) a mini-batch D, and 3) learning rate η and 4) remember rate α (line 1). Then, we will obtain the best u1 by solving a minimization problem (line 2). L represents the loss function defined in Eq. (1). θ1 represents the parameters of the network F1. Similarly we will obtain the best u2 (line 3). θ2 represents the parameters of the network F2. 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 F1 and the updated θ2 into F2 and output F1 and F2 (line 6).
  Solution to minimization problems in Algorithm 2. In line 2 or 3 in Algorithm 2, we need to solve a minimization problem: minu′:1u′>α|D| L(θ,u′;F,D) and return the best u′ as u (u1 in line 2 and u2 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 (F1 or F2) and n instances in D, how to select at least k instances such that L is minimized”, where k = dα|D|e. 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 `(F1(xi), y̌i). Then, we select k instance with the smallest cross-entropy losses. Finally, let ui of these k instances be 1 and ui of the other instances be 0, and we can get the best u = [u1, . . . , un]. 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|.
sections.heading: 4 BUTTERFLY VS. TWO-STEP APPROACH
sections.text: 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.
  Algorithm 1 Butterfly Framework: quadruple training for WUDA problem 1: Input D̃s, Dt, learning rate η, fixed τ , fixed τt, epoch Tk and Tmax, iteration Nmax, # of pseudo-labeled target data ninit, max of ninit nlt,max; 2: Initial F1, F2, Ft1, Ft2, D̃lt = D̃s, D̃ = D̃s, nlt = ninit; for T = 1, 2, . . . , Tmax do
  3: Shuffle training set D̃; // Noisy dataset for N = 1, . . . , Nmax do
  4: Fetch mini-batch Ď from D̃; 5: Update Branch-I: F1, F2 = Checking(F1, F2, Ď, η, R(T )); // Check data in MD using Algorithm 2 6: Fetch mini-batch Ďt from D̃lt; 7: Update Branch-II: Ft1, Ft2 = Checking(Ft1, Ft2, Ďt, η, Rt(T )); // Check data in TD using Algorithm 2 end 8: Obtain D̃lt = Labelling(F1, F2, Dt, nlt); // Label Dt, following Saito et al. (2017) 9: Obtain D̃ = D̃s ∪ D̃lt; // Update MD 10: Update nlt = min{T/20 ∗ nt, nlt,max}; 11: Update R(T ) = 1−min{ T
  Tk τ, τ}, Rt(T ) = 1−min{ TTk τt, τt};
  end 12: Output Ft1 and Ft2
  Algorithm 2 Checking(F1, F2, D, η, α) 1: Input networks F1, F2, mini-batch D, learning rate η, remember rate α; 2: Obtain u1 = arg minu′1:1u′1>α|D| L(θ1,u ′ 1;F1, D); // Check high-correctness data 3: Obtain u2 = arg minu′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 ρs01 be the probability that incorrect data is selected from noisy source data, and ρt01 be the probability that incorrect data is selected from pseudo-labeled target data. Theorem 3 shows that ∆→ 0 if ρs01 → 0 and ρt01 → 0. Since Butterfly can select correct data with a high probability (i.e., ρs01 → 0 and ρt01 → 0), noise effects will be eliminated (∆→ 0).
sections.heading: 5 EXPERIMENTS
sections.text: 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.
  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, Figure 4-(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 (Figure 5-(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). 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. Table 3 reports the target-domain accuracy for 2 common UDA tasks. The target-domain accuracy of DAN, DANN and ATDA are results reported by Saito 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
  human-sentiment WUDA tasks) and 3 real-world WUDA tasks. We consider following baselines: 1) B w/o C: train B-Net by Algorithm 1, without adding |θTf11θf21| into the loss function of B-Net. 2) DCP-D: realize DCP via Decoupling (Malach and Shalev-Shwartz, 2017) to check data in MD and TD. 3) DCP-M: realize DCP via MentorNet (Jiang et al., 2018) 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 |θTf11θf21| 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 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.
sections.heading: 6 CONCLUSIONS
sections.text: 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.
sections.heading: A REVIEW OF GENERATION OF NOISY LABELS
sections.text: This section presents a review on two label-noise generation processes.
sections.heading: A.1 TRANSITION MATRIX
sections.text: We assume that there is a clean multivariate random variable (Xs, Ys) defined on X × Y with a probability density ps(xs, ys), where Y = {1, ...,K} is a label set with K labels. However, samples of (Xs, Ys) cannot be directly obtained and we only can observe noisy source data from the multivariate random variable (Xs, Ỹs) defined on X × Y with a probability density p̃s(xs, ỹs). p̃s(xs, ỹs) is generated by a transition probability Pr(Ỹs = j|Ys = i), i.e., the flip rate from a clean label i to a noisy label j. When we generate p̃s(xs, ỹs) using Q, we often assume that ∑K ys=1 ps(xs, ys) = ∑K ỹs=1
  p̃s(xs, ỹs), i.e., the class conditional noise (Liu and Tao, 2016). All these transition probabilities are summarized into a transition matrix Q, where Qij = Pr(Ỹs = j|Ys = i). The transition matrix Q is easily estimated in certain situations (Liu and Tao, 2016). However, in more complex situations, such as clothing1M dataset (Xiao et al., 2015), noisy source data is directly generated by selecting data from a pool, which mixes correct data (data with correct labels) and incorrect data (data with incorrect labels). Namely, how the correct label i is corrupted to j (i 6= j) is unclear.
sections.heading: A.2 SAMPLE SELECTION
sections.text: Formally, there is a multivariate random variable (Xs, Ys, Vs) defined on X ×Y×V with a probability density ppos (xs, ys, vs), where V = {0, 1} and Vs = 1 means “correct” and Vs = 0 means “incorrect”. Nonetheless, samples from (Xs, Ys, Vs) cannot be obtained and we can only observe (Xs, Ỹs) from a distribution with the following density.
  p̃s(xs, ỹs) = 1∑ vs=0 ppoXs,Ys|Vs(xs, ys|vs)p po Vs (vs), (2)
  where ppoVs(vs) = ∫ X ∑K ys=1
  ppos (xs, ys, vs)dxs. The density in Eq. (2) means that we lost the information from Vs. If we uniformly select samples drawn from p̃s(xs, ỹs), the noise rate of these samples is p po Vs
  (0). It is clear that the multivariate random variable (Xs, Ys|Vs = 1) is the clean multivariate random variable (Xs, Ys) defined in Appendix A.1. Then, qs(xs, ys) is used to describe the density of incorrect multivariate random variable (Xs, Ys|Vs = 0). Using ps(xs, ys) and qs(xs, ys), p̃s(xs, ỹs) can be expressed by the following equation.
  p̃s(xs, ỹs) = (1− ρ)ps(xs, ys) + ρqs(xs, ys), (3)
  where ρ = ppoVs(0). Here, we do not assume ∑K ys=1 ps(xs, ys) = ∑K ys=1
  qs(xs, ys). To reduce noise effects from incorrect data, scholars aim to recover the information of Vs, i.e., to select correct data from data drawn from p̃s(xs, ỹs) (Han et al., 2018; Jiang et al., 2018; Malach and Shalev-Shwartz, 2017).
sections.heading: B TRANSITION MATRIX Q
sections.text: Precise definitions of Symmetry flipping and Pair flipping are presented below, where ρ is the noise rate and K is the number of labels.
  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 .
sections.heading: C DATASETS VISUALIZATION
sections.text: Figure 6 shows datasets: MNIST and SYND. Figure 7 shows datasets: Bing, Caltech256, Imagenet and SUN (taking “horse” as the common class).
sections.heading: D THEORETICAL ANALYSIS
sections.text: This section presents some interesting theoretical findings related to WUDA problem. We use following notations in this section: 1) a space X ⊂ Rd and Y = {1, 2, . . . ,K} as a label set; 2) p̃s(xs, ỹs), ps(xs, ys) and qs(xs, ys) represent densities of noisy, correct and incorrect multivariate random variables (m.r.v.) defined on X ×Y , respectively1, and p̃xs(xs), pxs(xs) and qxs(xs) are their marginal densities; and 3) pxt(xt) represents density of m.r.v. xt defined on X ; and 4) we use `(h(x), h′(x)) to represent loss function between two labelling functions; and 5) we use R̃s(h) = Ep̃s(xs,ỹs)[`(h(xs), ỹs)] and Rs(h) = Eps(xs,ys)[`(h(xs), ys)] to represent expected risks on the noisy and correct m.r.v.; and 6) we use R̃s(h, h′) = Ep̃xs (xs)[`(h(xs), h
  ′(xs))], Rs(h, h
  ′) = Epxs (xs)[`(h(xs), h ′(xs))] and Rt(h, h′) = Epxt (xt)[`(h(xt), h ′(xt))] to represent expected
  1There 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..
  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 ft(xt) and f̃t(xt).
sections.heading: D.1 WUDA RUINS UDA METHODS
sections.text: Theoretically, we analyze why existing UDA methods cannot well transfer useful knowledge from noisy source data D̃s to unlabelled target data Dt directly. We first present a theorem to show relations between Rs(h) and R̃s(h). Theorem 1. For any labelling function h : X → Y , if p̃s(xs, ỹs) is generated by a transition matrix Q as demonstrated in Appendix A.1, we have
  R̃s(h) = Rs(h) + Epxs (xs)[η T (xs)(Q− I)`(h(xs))], (4)
  where `(h(xs)) = [`(h(xs), 1), ..., `(h(xs),K)]T and η(xs) = [pYs|Xs(1|xs), ..., pYs|Xs(K|xs)]T . If p̃s(xs, ỹs) is generated by sample selection as described in in Appendix A.2, we have
  R̃s(h) = (1− ρ)Rs(h) + ρEqxs (xs)[η T q (xs)`(h(xs))], (5)
  where ηq(xs) = [qYs|Xs(1|xs), ..., qYs|Xs(K|xs)]T . Remark 2. In Eq. (5), Eqxs (xs)[η T q (xs)`(h(xs))] represents the expected risk on the incorrect m.r.v.. To ensure to obtain useful knowledge from P̃s, we need to avoid R̃s(h) ≈ Eqxs (xs) [η T q (xs)`(h(xs))]. Specifically, we assume: there is a constant 0 < Ms <∞ such that Eqxs (xs)[η T q (xs)`(h(xs))] ≤ Rs(h) +Ms.
  Theorem 1 shows that the expected risk R̃s(h) only equals Rs(h) when two cases happen: 1) Q = I and ρ = 0 and 2) some special combinations (e.g., special pxs , qxs , Q, η and `) to make the second term in Eq. (4) equal zero or to make the second term in Eq. (5) equal ρRs(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 pxs , qxs , Q and η are unknown. Thus, R̃s(h) has an essential difference with Rs(h). Then, following proof skills in Ben-David et al. (2010), we derive the upper bound of Rt(h) as follows. Theorem 2. For any labelling function h : X → Y , we have
  Rt(h, ft) ≤ R̃s(h)︸ ︷︷ ︸ (i) risk on noisy data + |Rt(h, f̃t)− R̃s(h, f̃t)|︸ ︷︷ ︸ (ii) discrepancy between distributions + |Rs(h, f̃t)−Rs(h)|︸ ︷︷ ︸ (iii) domain dissimilarity
  + |R̃s(h)−Rs(h)|+ |R̃s(h, f̃t)−Rs(h, f̃t)|︸ ︷︷ ︸ (iv) noise effects from source ∆s + |Rt(h, ft)−Rt(h, f̃t)|︸ ︷︷ ︸ (v) noise effects from target ∆t . (6)
  Remark 3. To ensure that we can gain useful knowledge from f̃t(xt), we assume: there is a constant 0 < Mt <∞ such that Eqxs (x)[`(h(x), f̃t(x))] ≤ Rs(h, f̃t)+Mt and Eqxt (x)[`(h(x), f̃t(x))] ≤ Rt(h, ft)+Mt, where qxt(x) = pxt(x)1A(x)/Pxt(A) and A = {x : f̃t(x) 6= ft(x)}.
  It is clear that the upper bound of Rt(h, ft), 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 (i) + (ii) + (iii) (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.
sections.heading: D.2 TWO-STEP APPROACH IS A COMPROMISE SOLUTION
sections.text: 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 ỹs be replaced with pseudo labels ỹ′s after pre-processing. Noise effects ∆ will become pseudo-label effects ∆p as follows.
  ∆p = |R̃′s(h)−Rs(h)|+ |R̃′s(h, f̃t)−Rs(h, f̃t)|︸ ︷︷ ︸ pseudo-label-source effects ∆′s +∆t, (7)
  where R̃′s(h) and R̃ ′ s(h, f̃t) correspond to R̃s(h) and R̃s(h, f̃t) 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.
sections.heading: D.3 WHY DOES BUTTERFLY CAN ELIMINATE NOISE EFFECT?
sections.text: 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 ρs01 represent the probability that incorrect data is selected from noisy source data, and ρt01 represent the probability that incorrect data is selected from pseudo-labeled target data. Theorem 3 shows that ∆→ 0 if ρs01 → 0 and ρt01 → 0 and presents a new upper bound of Rt(h, ft). Theorem 3. Given two m.r.v. (Xs, Ys, Us) defined on X × Y × V and (Xt, Ut) defined on X × V , under the assumptions in Remarks 2 and 3, ∀ ∈ (0, 1), there are δs and δt, if Ep′xt (xt)[`(h(xt), ft(xt))] ≤ Rt(h, ft) + ρ s 01Mt, ρ s 01 < δs and ρ t 01 < δt, for any labeling function h, we will have
  |R̃pos (h, f̃t, us)−Rs(h, f̃t)|+ |R̃pos (h, us)−Rs(h)| < 2 . (8) Moreover, if ρs01 ≤ δs and ρt01 ≤ δt, we will have
  Rt(h, ft) ≤ R̃pos (h, us)︸ ︷︷ ︸ (i) risk on noisy data + |R̃pot (h, f̃t, ut)− R̃pos (h, f̃t, us)|︸ ︷︷ ︸ (ii) discrepancy between distributions + |Rs(h, f̃t)−Rs(h)|︸ ︷︷ ︸ (iii) domain dissimilarity
  + 2 ︸︷︷︸ (iv) noise effects from source ∆s + 2 ︸︷︷︸ (v) noise effects from target ∆t , (9)
  where p′xt(x) = pxt(x)1B(x)/Pxt(B), R̃ po s (h, us) = (1 − ρus)−1Ep̃pos (xs,ys,us)[us`(h(xs), ys)], R̃pot (h, f̃t, ut) = (1 − ρut)−1Ep̃pot (xt,ut)[ut`(h(xt), f̃t(xt))], R̃ po s (h, f̃t, us) = (1 − ρus)−1 Ep̃pos (xs,ys,us)[us`(h(xs), f̃t(xs))], p̃ po s (xs, ys, us) is the density of (Xs, Ys, Us), p̃ po t (xt, ut) is the density of
  (Xt, Ut), ρus = ∫ X ∑K ys=1 p̃pos (xs, ys, 0)dxs < 1, ρut = ∫ X p̃ po t (xt, 0)dxt < 1, B = X/A and V = {0, 1}.
  Remark 4. In Appendix H.3.1, we give precise definitions of ρs01 and ρt01 and demonstrate the meaning of Ep′xt (xt)[`(h(xt), ft(xt))] ≤ Rt(h, ft) + ρ s 01Mt (Remark 5).
  Data drawn from the distribution of (Xs, Ys, Us) can be regarded as a pool that mixes the selected (us = 1) and unselected (us = 0) noisy source data. Data drawn from the distribution of (Xt, Ut) can be regarded as a pool that mixes the selected (ut = 1) and unselected (ut = 0) pseudo-labeled target data. Theorem 3 shows that if selected data have a high probability to be correct ones (ρs01 → 0 and ρt01 → 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 ρs01 → 0 and ρt01 → 0). This checking process will make (iv) and (v), 2 + 2 , become 0. Then, we can obtain gradients of R̃pos (h, us), R̃s(h, f̃t, us) and R̃ po t (h, f̃t, ut) w.r.t. parameters of h and use these gradients to minimize them, which minimizes (i) and (ii) as (i) + (ii) ≤ R̃pos (h, us) + R̃s(h, f̃t, us) + R̃pot (h, f̃t, ut). 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 R̃pos (h, us) + R̃ po s (h, f̃t, us), as (iii) ≤ Rs(h, f̃t) +Rs(h) ≤ R̃pos (h, us) + R̃pos (h, f̃t, us) + 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 R̃pos (h, us), R̃ po t (h, f̃t, ut) and R̃pos (h, f̃t, us) (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).
sections.heading: E RESULTS ON HUMAN-SENTIMENT WUDA TASKS
sections.text: 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.
sections.heading: F EXPERIMENTAL SETTINGS
sections.heading: F.1 NETWORK STRUCTURE AND OPTIMIZER
sections.text: 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). F1, F2, Ft1 and Ft2 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.
sections.heading: F.2 EXPERIMENTAL SETUP
sections.text: For all 35 WUDA tasks and 2 UDA tasks, Tk is set to 5, Tmax 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. nlt,max is set to 15, 000 for digit tasks and UDA tasks, 500 for human-sentiment tasks and 4000 for real-world WUDA tasks. Nmax 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.
sections.heading: F.3 LINKS TO DATASETS
sections.text: 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).
sections.heading: G RUNNING TIME
sections.text: 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.
sections.heading: H PROOFS
sections.text: This section provides proofs of theorems demonstrated in the supplementary.
sections.heading: H.1 PROOF OF THEOREM 1
sections.text: Proof. We will fist prove Eq. (4) (Case 1) and then prove Eq. (5) (Case 2).
  Case 1. According to definition of R̃s(h), we have
  R̃s(h) = Ep̃s(xs,ỹs)[`(h(xs), ỹs)]
  = ∫ X K∑ ỹs=1 `(h(xs), ỹs)p̃s(xs, ỹs)dxs
  = ∫ X K∑ ỹs=1 `(h(xs), ỹs)p̃Ỹs|Xs(ỹs|xs)pxs(xs)dxs
  = ∫ X η̃T (xs)`(h(xs))pxs(xs)dxs, (10)
  where `(h(xs)) = [`(h(xs), 1), ..., `(h(xs),K)]T and η̃(xs) = [p̃Ỹs|Xs(1|xs), . . . , p̃Ỹs|Xs(K|xs)] T . According to definition of the transition matrix Q, we know that
  η̃T (xs) = η T (xs)Q, (11)
  where η(xs) = [pYs|Xs(1|xs), ... , pYs|Xs(K|xs)]T . Substituting Eq. (11) into Eq. (10), we have
  R̃s(h) = ∫ X ηT (xs)Q`(h(xs))pxs(xs)dxs
  = ∫ X ηT (xs)I`(h(xs))pxs(xs)dxs + ∫ X ηT (xs)(Q− I)`(h(xs))pxs(xs)dxs = Rs(h) + Epxs (xs)[η T (xs)(Q− I)`(h(xs))].
  Hence, Case 1 is proved.
  Case 2. According to definition of R̃s(h) and Eq. (3), we have
  R̃s(h) = Ep̃s(xs,ỹs)[`(h(xs), ỹs)]
  = ∫ X K∑ ỹs=1 `(h(xs), ỹs)p̃s(xs, ỹs)dxs
  = ∫ X K∑ ys=1 `(h(xs), ys) ( (1− ρ)ps(xs, ys) + ρqs(xs, ys) ) dxs
  = (1− ρ) ∫ X K∑ ys=1 `(h(xs), ys)ps(xs, ys)dxs + ρ ∫ X K∑ ys=1 `(h(xs), ys)qs(xs, ys)dxs
  = (1− ρ)Rs(h) + ρ ∫ X K∑ ys=1 `(h(xs), ys)qYs|Xs(ys|xs)qxs(xs)dxs. (12)
  Let ηq(xs) = [qYs|Xs(1|xs), ..., qYs|Xs(K|xs)]T , we have
  R̃s(h) = (1− ρ)Rs(h) + ρEqxs (xs)[η T q (xs)`(h(xs))].
  Hence, Case 2 is proved.
sections.heading: H.2 PROOF OF THEOREM 2
sections.text: Proof. For any labelling function h, we have
  Rt(h, ft) = Rt(h, ft) + R̃s(h)− R̃s(h) +Rs(h, ft)−Rs(h, ft) = R̃s(h) +Rt(h, ft)− R̃s(h, ft) +Rs(h, ft)−Rs(h) +Rs(h)− R̃s(h)
  + R̃s(h, ft)−Rs(h, ft). (13) Since we do not know ft, we substitute following equations into Eq. (13),
  Rt(h, ft) = Rt(h, f̃t) +Rt(h, ft)−Rt(h, f̃t), R̃s(h, ft) = R̃s(h, f̃t) + R̃s(h, ft)− R̃s(h, f̃t), Rs(h, ft) = Rs(h, f̃t) +Rs(h, ft)−Rs(h, f̃t).
  Then, we have
  Rt(h, ft) = R̃s(h) +Rt(h, f̃t)− R̃s(h, f̃t) +Rs(h, f̃t)−Rs(h) + Rs(h)− R̃s(h) + R̃s(h, f̃t)−Rs(h, f̃t) +Rt(h, ft)−Rt(h, f̃t) ≤ R̃s(h) + |Rt(h, f̃t)− R̃s(h, f̃t)|+ |Rs(h, f̃t)−Rs(h)|
  + |R̃s(h)−Rs(h)|+ |R̃s(h, f̃t)−Rs(h, f̃t)|+ |Rt(h, ft)−Rt(h, f̃t)|. Hence, this theorem is proved.
sections.heading: H.3 PROOF OF THEOREM 3
sections.heading: H.3.1 PRELIMINARY
sections.text: Before stating the proof, we first present a random variable below.
  Let (Xt, Vt) be a m.r.v. defined on X × V with respective a density ppot (xt, vt), where V = {0, 1}. Vt can be regarded as perfect-selection random variables. Namely, Vt = 1 means ft(xt) = f̃t(xt) and Vt = 0 means ft(xt) 6= f̃t(xt). Let ppoVt(vt) be the marginal density of p po t (xt, vt). It is clear that, higher value of ppoVt(Vt = 1) means that f̃t is more like ft. In following, we use 1− ρvt to represent p po Vt (Vt = 1).
  Then, we will show 1) relation between (Xs, Ys, Vs) and (Xs, Ys, Us), 2) relation between (Xt, Vt) and (Xt, Ut) and definitions of ρs01 and ρ t 01. Based on (Xt, Vt) and (Xs, Ys, Vs) defined in Appendix A.2, the densities of (Xs, Ys, Us) and (Xt, Ut) can be expressed as follows. p̃poXs,Ys|Us(xs, ys|i) =ρ s 0ip po Xs,Ys|Vs(xs, ys|0) + ρ s 1ip po Xs,Ys|Vs(xs, ys|1),
  p̃poXt|Ut(xt|i) = ρ t 0ip po Xt|Vt(xt|0) + ρ t 1ip po Xt|Vt(xt|1),
  where ρsji = Pr(Vs = j|Us = i) represents the probability of the event: Vs = j given Us = i, ρtji = Pr(Vt = j|Ut = i) represents the probability of the event: Vt = j given Ut = i (i, j = 0, 1). Since ps(xs, ys) = ppoXs,Ys|Vs(xs, ys|1), qs(xs, ys) = p po Xs,Ys|Vs(xs, ys|0), p po Xt|Vt(xt|0) = pxt(xt)1A(xt)/Pxt(A) = qxt(xt) and ppoXt|Vt(xt|1) = pxt(xt)1B(xt)/Pxt(B) = p ′ xt(xt) (A = {x : f̃t(x) 6= ft(x)}, B = X/A), we have
  p̃poXs,Ys|Us(xs, ys|i) = ρ s 0iqs(xs, ys) + ρ s 1ips(xs, ys), (14)
  p̃poXt|Ut(xt|i) = ρ t 0iqxt(xt) + ρ t 1ip ′ xt(xt). (15)
  Next, we give a lemma to show relation between R̃pos (h, us) and Rs(h). Lemma 1. Given the multivariate random variable (Xs, Ys, Us) with the probability p̃pos (xs, ys, us) and Eq. (14), we have
  |R̃pos (h, us)−Rs(h)| ≤ ρs01 max{Eqs(xs,ys)[`(h(xs), ys)], Rs(h)}. (16)
  Proof. According to definition of R̃pos (h, us) in Theorem 3, we have
  R̃pos (h, us) = (1− ρus)−1 ∫ X 1∑ us=0 K∑ ys=1 us`(h(xs), ys)p̃ po s (xs, ys, us)dxs
  = (1− ρus)−1 ∫ X K∑ ys=1 `(h(xs), ys)p̃ po Xs,Ys|Us(xs, ys|1)p̃ po Us (1)dxs
  (a) = (1− ρus)−1(1− ρus) ∫ X K∑ ys=1 `(h(xs), ys) ( ρs01qs(xs, ys) + ρ s 11ps(xs, ys) ) dxs = ρs01Eqs(xs,ys)[`(h(xs), ys)] + ρ s 11Rs(h),
  where (a) is based on the definition of ρus and Eq. (14). Thus, we have
  |R̃pos (h, us)−Rs(h)| = |ρs01Eqs(xs,ys)[`(h(xs), ys)]− (1− ρ s 11)Rs(h)|
  ≤ ρs01 max{Eqs(xs,ys)[`(h(xs), ys)], Rs(h)}. This lemma is proved.
  Similar with Lemma 1, we can obtain |R̃pos (h, f̃t, ut)−Rs(h, f̃t)| ≤ ρs01 max{Eqxs (xs)[`(h(xs), f̃t(xs))], Rs(h, f̃t)}. (17) Then, we give another lemma to show relation between R̃pot (h, f̃t, us) and Rt(h, f̃t).
  Lemma 2. Given the multivariate random variable (Xt, Ut) with the probability p̃pos (xt, ut) and Eq. (15), if Ep′xt (xt)[`(h(xt), ft(xt))] ≤ Rt(h, ft) + ρ s 01Mt, then we have
  |R̃pot (h, f̃t, ut)−Rt(h, ft)| ≤ ρt01 max{Eqxt (xt)[`(h(xt), f̃t(xt))], Rt(h, ft)}+ ρ t 11ρ s 01Mt. (18)
  Proof. According to definition of R̃pot (h, f̃t, ut) in Theorem 3, we have
  R̃pot (h, f̃t, ut) = (1− ρut)−1 ∫ X 1∑ ut=0 ut`(h(xt), f̃t(xt))p̃ po t (xt, ut)dxt
  = (1− ρut)−1 ∫ X `(h(xt), f̃t(xt))p̃ po Xt|Ut(xt|1)p̃ po Ut (1)dxt
  (a) = (1− ρut)−1(1− ρut) ∫ X `(h(xs), f̃t(xt)) ( ρt01qxt(xt) + ρ t 11p po Xt|Vt(xt|1) ) dxt
  = ρt01Eqxt (xt)[`(h(xt), f̃t(xt))] + ρ t 11 ∫ X `(h(xt), f̃t(xt))p po Xt|Vt(xt|Vt = 1)dxt
  (b) = ρt01Eqxt (xt)[`(h(xt), f̃t(xt))] + ρ t 11 ∫ X `(h(xt), ft(xt))p po Xt|Vt(xt|Vt = 1)dxt
  = ρt01Eqxt (xt)[`(h(xt), f̃t(xt))] + ρ t 11 ∫ X `(h(xt), ft(xt))p ′ xt(xt)dxt
  = ρt01Eqxt (xt)[`(h(xt), f̃t(xt))] + ρ t 11Ep′xt (xt)[`(h(xt), ft(xt))], (19)
  where (a) is based on the definition of ρus and Eq. (14) and (b) is based on the definition of Vt (ft(xt) = f̃t(xt) when Vt = 1). Since Ep′xt (xt)[`(h(xt), ft(xt))] ≤ Rt(h, ft) + ρ s 01Mt, we have
  R̃pot (h, f̃t, ut) ≤ ρt01Eqxt (xt)[`(h(xt), f̃t(xt))] + ρ t 11(Rt(h, ft) + ρ s 01Mt). (20)
  Thus, we have
  |R̃pot (h, f̃t, ut)−Rt(h, ft)| = |ρt01Eqxt (xt)[`(h(xt), f̃t(xt))] + ρ t 11Ep′xt (xt)[`(h(xt), ft(xt))]
  −Rt(h, ft)| ≤ |ρt01Eqxt (xt)[`(h(xt), f̃t(xt))] + ρ t 11(Rt(h, ft) + ρ s 01Mt)
  −Rt(h, ft)| = |ρt01(Eqxt (xt)[`(h(xt), f̃t(xt))]−Rt(h, ft)) + ρ t 11ρ s 01Mt|
  ≤ ρt01 max{Eqxt (xt)[`(h(xt), f̃t(xt))], Rt(h, ft)}+ ρ t 11ρ s 01Mt.
  This lemma is proved.
  Remark 5. In Lemma 2, the assumption Ep′xt (xt)[`(h(xt), ft(xt))] ≤ Rt(h, ft) + ρ s 01Mt means that the expect risk restricted in B (i.e., Ep′xt (xt)[`(h(xt), ft(xt))]) can represent the true risk Rt(h, ft) when ρ s 01 is small, where B = {x : f̃t(x) = ft(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 f̃t even when we can perfectly select correct data from pseudo-labeled target data (ρt01 = 0).
  Inequalities (16), (17) and (18) show that if we can avoid to annotate incorrect data as “correct” (ρs01 = 0 and ρ t 01 = 0), we have R̃ po s (h, us) = Rs(h), R̃ po s (h, f̃t, ut) = Rs(h, f̃t) and R̃ po t (h, f̃t, ut) = Rt(h, ft). Nonetheless, ρs01 and ρ t 01 never equal 0, and Eqs(xs,ys)[`(h(x), y)], Eqxs (xs)[`(h(xs), f̃t(xs))] and Eqxt (xt)[`(h(xt), f̃t(xt))] may equal +∞ for some h. In next section, we prove that, under the assumption in Remarks 2 and 3, R̃pos (h, us) → Rs(h), R̃pos (h, f̃t, ut) → Rs(h, f̃t) and R̃pot (h, f̃t, ut) → Rt(h, ft) if ρs01 → 0 and ρt01 → 0. Moreover, we give a new upper bound of Rt(h, ft).
sections.heading: H.3.2 PROOF OF THEOREM 3
sections.text: Now, we prove Theorem 3 as follows.
  Proof. We first prove upper bounds of |R̃pos (h, us)−Rs(h)|, |R̃pos (h, f̃t, ut)−Rs(h, f̃t)| and |R̃pot (h, f̃t, ut)− Rt(h, ft)| under assumptions in Theorem 3. Based on Lemma 1, we have
  |R̃pos (h, us)−Rs(h)| = |ρs01Eqs(xs,ys)[`(h(xs), ys)]− (1− ρ s 11)Rs(h)|
  ≤ |ρs01(Rs(h) +Ms)− ρs01Rs(h)| = ρs01Ms.
  Similar, we have
  |R̃pos (h, f̃t, ut)−Rs(h, f̃t)| ≤ ρt01Mt,
  |R̃pot (h, f̃t, ut)−Rt(h, ft)| ≤ ρt01Mt + ρt11ρs01Mt.
  Since Ms and Mt are positive constants, it is clear that R̃ po s (h, us) → Rs(h), R̃pos (h, f̃t, ut) → Rs(h, f̃t) and R̃pot (h, f̃t, ut)→ Rt(h, ft) when ρs01 → 0 and ρt01 → 0. Specifically, ∀ ∈ (0, 1), let δt = /Mt and δs = /max{Ms, ρt11Mt}. When ρs01 < δs and ρt01 < δt, we have
  |R̃pos (h, us)−Rs(h)|+ |R̃pos (h, f̃t, ut)−Rs(h, f̃t)| < 2
  |R̃pot (h, f̃t, ut)−Rt(h, ft)| < 2 . Hence, we prove the Eq. (8). In following, we give a new upper bound of Rt(h, ft). Call back to Theorem 2, we replace 1) R̃s(h) with R̃ po s (h, us), 2) R̃s(h, f̃t) with R̃ po s (h, f̃t, ut), 3) Rs(h, f̃t) with R̃ po t (h, f̃t, ut). Then, we have
  Rt(h, ft) ≤ R̃pos (h, us) + |R̃ po t (h, f̃t, ut)− R̃pos (h, f̃t, ut))|+ |Rs(h, f̃t)−Rs(h)|
  + |R̃pos (h, us)−Rs(h)|+ |R̃pos (h, f̃t, ut)−Rs(h, f̃t)|+ |Rt(h, ft)− R̃pos (h, f̃t, ut)|.
  Let ρs01 ≤ δs and ρt01 ≤ δt, we have
  Rt(h, ft) ≤ R̃pos (h, us)︸ ︷︷ ︸ (i) risk on noisy data + |R̃pot (h, f̃t, ut)− R̃pos (h, f̃t, us)|︸ ︷︷ ︸ (ii) discrepancy between distributions + |Rs(h, f̃t)−Rs(h)|︸ ︷︷ ︸ (iii) domain dissimilarity
  + 2 ︸︷︷︸ (iv) noise effects from source ∆s + 2 ︸︷︷︸ (v) noise effects from target ∆t ,
  Hence, we prove this theorem.