summaries: This paper presents an interesting quantization technique that is, unusually, end-to-end trainable and not just an inference technique. According to the experiments, the method achieves better performance and computational savings as compared to other quantization method baselines. The results are admirably demonstrated on a variety of models, including CNN and RNN-based neural nets, as well as on several datasets in different domains, including ImageNet, CIFAR10, and PTB. We see the method seems to generalize across all of these.

summaries: This paper outlines a new method that allows using a variety of precision in the numerical representation of the network to increase performance (both in terms of accuracy and speed). They learn a threshold value for which all activation values above the threshold are learned at full precision, while all below are learned at reduced precision. This enables substantial performance gains.

summaries: This paper introduces Precision Gating, a novel mechanism to quantize neural network activations to reduce the average bitwidth, resulting in networks with fewer bitwise operations. The idea is to have a learnable threshold Delta that determines if an output activation should be computed in high or low precision, determined by the most significant bits of the value. Assuming that high activations are more important, these are computed at higher precision.

abstractText: We propose precision gating (PG), an end-to-end trainable dynamic dual-precision quantization technique for deep neural networks. PG computes most features in a low precision and only a small proportion of important features in a higher precision to preserve accuracy. The proposed approach is applicable to a variety of DNN architectures and significantly reduces the computational cost of DNN execution with almost no accuracy loss. Our experiments indicate that PG achieves excellent results on CNNs, including statically compressed mobile-friendly networks such as ShuffleNet. Compared to the state-of-the-art prediction-based quantization schemes, PG achieves the same or higher accuracy with 2.4× less compute on ImageNet. PG furthermore applies to RNNs. Compared to 8-bit uniform quantization, PG obtains a 1.2% improvement in perplexity per word with 2.7× computational cost reduction on LSTM on the Penn Tree Bank dataset.

authors:
Martı́n Abadi
Paul Barham
Jianmin Chen
Zhifeng Chen
Andy Davis
Jeffrey Dean
Matthieu Devin
Sanjay Ghemawat
Geoffrey Irving
Michael Isard
Manjunath Kudlur
Josh Levenberg
Rajat Monga
Sherry Moore
Derek G. Murray
Benoit Steiner
Paul Tucker
Vijay Vasudevan
Pete Warden
Martin Wicke
Yuan Yu
Xiaoqiang Zheng

title: TensorFlow: A System for Largescale Machine Learning

venue: USENIX Conf. on Operating Systems Design and Implementation,

authors:
Shijie Cao
Lingxiao Ma
Wencong Xiao
Chen Zhang
Yunxin Liu
Lintao Zhang
Lanshu Nie
Zhi Yang

title: SeerNet: Predicting Convolutional Neural Network Feature-Map Sparsity through Low-Bit Quantization

venue: Conf. on Computer Vision and Pattern Recognition (CVPR),

authors:
Liang-Chieh Chen
George Papandreou
Iasonas Kokkinos
Kevin Murphy
Alan L. Yuille

title: DeepLab: Semantic Image Segmentation with Deep Convolutional Nets, Atrous Convolution, and Fully Connected CRFs

venue: IEEE Trans. on Pattern Analysis and Machine Intelligence,

authors:
Jungwook Choi
Zhuo Wang
Swagath Venkataramani
Pierce I-Jen Chuang
Vijayalakshmi Srinivasan
Kailash Gopalakrishnan

title: PACT: Parameterized Clipping Activation for Quantized Neural Networks

venue: arXiv e-print,

authors:
Matthieu Courbariaux
Itay Hubara
Daniel Soudry
Ran El-Yaniv
Yoshua Bengio

title: Binarized Neural Networks: Training Deep Neural Networks with Weights and Activations Constrained to +1 or -1

authors:
Jia Deng
Wei Dong
Richard Socher
Li-Jia Li
Kai Li
Li Fei-Fei

title: ImageNet: A Large-Scale Hierarchical Image Database

authors:
Zhen Dong
Zhewei Yao
Amir Gholami
Michael W. Mahoney
Kurt Keutzer

title: HAWQ: Hessian AWare Quantization of Neural Networks With Mixed-Precision

venue: Int’l Conf. on Computer Vision (ICCV),

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep Residual Learning for Image Recognition

authors:
Qinyao He
He Wen
Shuchang Zhou
Yuxin Wu
Cong Yao
Xinyu Zhou
Yuheng Zou

title: Effective Quantization Methods for Recurrent Neural Networks

authors:
Sepp Hochreiter
Jürgen Schmidhuber

title: Long Short-Term Memory

venue: Neural Computation,

authors:
Weizhe Hua
Yuan Zhou
Christopher De Sa
Zhiru Zhang
G. Edward Suh

title: Boosting the Performance of CNN Accelerators with Dynamic Fine-Grained Channel Gating

venue: Int’l Symp. on Microarchitecture (MICRO),

authors:
Weizhe Hua
Yuan Zhou
Christopher M De Sa
Zhiru Zhang
G. Edward Suh

title: Channel Gating Neural Networks

venue: Advances in Neural Information Processing Systems (NeurIPS),

authors:
Itay Hubara
Matthieu Courbariaux
Daniel Soudry
Ran El-Yaniv
Yoshua Bengio

title: Quantized Neural Networks: Training Neural Networks with Low Precision Weights and Activations

venue: Journal of Machine Learning Research (JMLR),

authors:
Sergey Ioffe
Christian Szegedy

title: Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift

authors:
Alex Krizhevsky
Geoffrey Hinton

title: Learning Multiple Layers of Features from Tiny Images

venue: Tech report,

authors:
Alex Krizhevsky
Ilya Sutskever
Geoffrey E Hinton

title: Imagenet Classification with Deep Convolutional Neural Networks

authors:
Siu Kwan Lam
Antoine Pitrou
Stanley Seibert

title: Numba: A LLVM-based Python JIT Compiler

venue: Workshop on the LLVM Compiler Infrastructure in HPC,

authors:
Darryl D. Lin
Sachin S. Talathi
V. Sreekanth Annapureddy

title: Fixed Point Quantization of Deep Convolutional Networks

venue: Int’l Conf. on Machine Learning (ICML),

authors:
Yingyan Lin
Charbel Sakr
Yongjune Kim
Naresh Shanbhag

title: PredictiveNet: An energyefficient convolutional neural network via zero prediction

venue: Int’l Symp. on Circuits and Systems (ISCAS),

authors:
Thang Luong
Hieu Pham
Christopher D. Manning

title: Effective Approaches to Attention-based Neural Machine Translation

venue: Conf. on Empirical Methods in Natural Language Processing (EMNLP),

authors:
Ningning Ma
Xiangyu Zhang
Hai-Tao Zheng
Jian Sun

title: ShuffleNet V2: Practical Guidelines for Efficient CNN Architecture Design

venue: European Conf. on Computer Vision (ECCV),

authors:
Mitchell P. Marcus
Mary Ann Marcinkiewicz
Beatrice Santorini

title: Building a Large Annotated Corpus of English: The Penn Treebank

venue: Comput. Linguist.,

authors:
Asit Mishra
Eriko Nurvitadhi
Jeffrey J Cook
Debbie Marr

title: WRPN: Wide Reduced-Precision Networks

venue: Int’l Conf. on Learning Representations (ICLR),

authors:
Israt Nisa
Aravind Sukumaran-Rajam
Sureyya Emre Kurt
Changwan Hong
P. Sadayappan

title: Sampled Dense Matrix Multiplication for High-Performance Machine Learning

venue: Int’l Conf. on High-Performance Computing (HIPC),

authors:
Eunhyeok Park
Sungjoo Yoo
Peter Vajda

title: Value-aware Quantization for Training and Inference of Neural Networks

authors:
Olaf Ronneberger
Philipp Fischer
Thomas Brox

title: U-Net: Convolutional Networks for Biomedical Image Segmentation

venue: Medical Image Computing and Computer-Assisted Intervention (MICCAI),

authors:
Florian Schroff
Dmitry Kalenichenko
James Philbin

title: FaceNet: A Unified Embedding for Face Recognition and Clustering

authors:
Mingcong Song
Jiechen Zhao
Yang Hu
Jiaqi Zhang
Tao Li

title: Prediction Based Execution on

venue: Deep Neural Networks. Int’l Symp. on Computer Architecture

authors:
Ashish Vaswani
Noam Shazeer
Niki Parmar
Jakob Uszkoreit
Llion Jones
Aidan N. Gomez
Lukasz Kaiser
Illia Polosukhin

title: Attention Is All You Need

authors:
Kuan Wang
Zhijian Liu
Yujun Lin
Ji Lin
Song Han

title: HAQ: Hardware-Aware Automated Quantization With Mixed Precision

venue: Conf. on Computer Vision and Pattern Recognition

authors:
Peiqi Wang
Xinfeng Xie
Lei Deng
Guoqi Li
Dongsheng Wang
Yuan Xie

title: HitNet: Hybrid Ternary Recurrent Neural Network

authors:
Bichen Wu
Alvin Wan
Xiangyu Yue
Peter Jin
Sicheng Zhao
Noah Golmant
Amir Gholaminejad
Joseph Gonzalez
Kurt Keutzer

title: Shift: A Zero FLOP, Zero Parameter Alternative to Spatial Convolutions

authors:
Bichen Wu
Yanghan Wang
Peizhao Zhang
Yuandong Tian
Peter Vajda
Kurt Keutzer

title: Mixed Precision Quantization of ConvNets via Differentiable Neural Architecture Search

authors:
Xiaowei Xu
Yukun Ding
Sharon Xiaobo Hu
Michael Niemier
Jason Cong
Yu Hu
Yiyu Shi

title: Scaling for Edge Inference of Deep Neural Networks

venue: Nature Electronics,

authors:
Hengshuang Zhao
Xiaojuan Qi
Xiaoyong Shen
Jianping Shi
Jiaya Jia

title: ICNet for RealTime Semantic Segmentation on High-Resolution Images

authors:
Ritchie Zhao
Weinan Song
Wentao Zhang
Tianwei Xing
Jeng-Hau Lin
Mani Srivastava
Rajesh Gupta
Zhiru Zhang

title: Accelerating Binarized Convolutional Neural Networks with SoftwareProgrammable FPGAs

venue: Int’l Symp. on Field-Programmable Gate Arrays (FPGA),

authors:
Ritchie Zhao
Yuwei Hu
Jordan Dotzel
Christopher De Sa
Zhiru Zhang

title: Improving Neural Network Quantization using Outlier Channel Splitting

authors:
Shu-Chang Zhou
Yu-Zhi Wang
He Wen
Qin-Yao He
Yu-Heng Zou

title: Balanced Quantization: An Effective and Efficient Approach to Quantized Neural Networks

venue: Journal of Computer Science and Technology,

authors:
Shuchang Zhou
Yuxin Wu
Zekun Ni
Xinyu Zhou
He Wen
Yuheng Zou

title: DoReFa-Net: Training Low Bitwidth Convolutional Neural Networks with Low Bitwidth Gradients

venue: arXiv preprint,

authors:
Chenzhuo Zhu
Song Han
Huizi Mao
William J. Dally

title: Trained Ternary Quantization

heading: 1 INTRODUCTION

text:
In recent years, deep neural networks (DNNs) have demonstrated excellent performance on many computer vision and language modeling tasks such as image classification, semantic segmentation, face recognition, machine translation, and image captioning (Krizhevsky et al., 2012; He et al., 2016a; Ronneberger et al., 2015; Chen et al., 2016; Zhao et al., 2018; Schroff et al., 2015; Luong et al., 2015; Vaswani et al., 2017). One evident trend in DNN design is that as researchers strive for better accuracy, both the model size and the number of DNN layers have drastically increased over time (Xu et al., 2018). At the same time, there is a growing demand to deploy deep learning technology in edge devices such as mobile phones, VR/AR glasses, and drones (Wu et al., 2019). The limited computational, memory, and energy budgets on these devices impose major challenges for the deployment of large DNN models at the edge.
DNN quantization is an important technique for improving the hardware efficiency of DNN execution (Zhao et al., 2017). Numerous studies have shown that full-precision floating-point computation is not necessary for DNN inference — quantized fixed-point models produce competitive results with a small or zero loss in prediction accuracy (Lin et al., 2016; He et al., 2016b; Zhou et al., 2016; 2017). In some cases, quantization may even improve model generalization by acting as a form of regularization. Existing studies mainly focus on static quantization, in which the precision of each weight and activation is fixed prior to inference (Hubara et al., 2017; He et al., 2016b). Along this line of work, researchers have explored tuning the bitwidth per layer (Wu et al., 2018b; Wang et al., 2019; Dong et al., 2019) as well as various types of quantization functions (Wang et al., 2018; Courbariaux et al., 2016; Li et al., 2016; Zhou et al., 2016). However, static DNN quantization methods cannot exploit input-dependent characteristics, where certain features can be computed in a lower precision during inference as they contribute less to the classification result for the given input. For
example, in computer vision tasks, the pixels representing the object of interest are typically more important than the background pixels.
In this paper, we reduce the inefficiency of a statically quantized DNN via precision gating (PG), which computes most features with low-precision arithmetic operations and only updates few important features to a high precision. More concretely, PG first executes a DNN layer in a low precision and identifies the output features with large magnitude as important features. It then computes a sparse update to increase the precision of those important output features. Intuitively, small values make a small contribution to the DNN’s output; thus approximating them in a low precision is reasonable. Precision gating enables dual-precision DNN execution at the granularity of each individual output feature, and therefore greatly reducing the average bitwidth and computational cost of the DNN. We further introduce a differentiable gating function which makes PG applicable to a rich variety of network models.
Experimental results show that PG achieves significant compute reduction and accuracy improvement on both CNNs and LSTMs. Compared to the baseline CNN counterparts, PG obtains 3.5% and 0.6% higher classification accuracy with up to 4.5× and 2.4× less computational cost for CIFAR-10 and ImageNet, respectively. On LSTM, compared to 8-bit uniform quantization PG boosts perplexity per word (PPW) by 1.2% with 2.8× less compute on the Penn Tree Bank (PTB) dataset. Our contributions are as follows:
1. We propose precision gating (PG), which to the best of our knowledge is the first end-toend trainable method that enables dual-precision execution of DNNs. PG is applicable to a wide variety of CNN and LSTM models. 2. PG enables DNN computation with lower average bitwidth than other state-of-the-art quantization methods. By employing a low-cost gating scheme, PG has the potential to reduce DNN execution costs in both commodity and dedicated hardware. 3. PG achieves the same sparsity during back-propagation as forward propagation, which dramatically reduces the computational cost for both passes. This is in stark contrast to prior dynamic DNN optimization methods that focus only on reducing the inference cost.

heading: 2 RELATED WORK

text:
Quantizing activations. Prior studies show that weights can be quantized to low bitwidth without compromising much accuracy (Zhu et al., 2017); however, quantizing activations with a low bitwidth (e.g., 4 bits) typically incurs a nontrivial accuracy degradation (Mishra et al., 2018; Zhou et al., 2016). This is partially caused by large activation and weight outliers, which stretch the quantization grid too wide and too sparse under a low precision, thus increasing the error (Park et al., 2018; Zhao et al., 2019). To address this problem, Choi et al. (2018) propose PACT to reduce the dynamic range of the activations through clipping the outliers using a learnable threshold. PACT provides a more effective quantization scheme under a very low bitwidth (e.g., 4 bits). In this work we incorporate the PACT method in the training flow of PG to handle the large outliers.
Prediction-based execution. Prior works have explored predicting ReLU-induced zeros and maxpooling compute redundancy to lower the computational cost of CNNs. For example, Lin et al. (2017); Song et al. (2018) propose zero-prediction to utilize a few of the most-significant bits in the input activations to predict the sign of the output activation. Zero-prediction removes redundancy by exploiting the fact that negative outputs will be suppressed by the ReLU anyway. Yet, this method only applies to ReLU activations and only when a linear layer is directly followed by ReLU. Hence such method does not apply to RNNs that use sigmoid or tanh as the activation function and many modern CNN networks that use batch normalization (Ioffe & Szegedy, 2015) before ReLU. Hua et al. (2019a;b) propose channel gating to dynamically turn off a subset of channels that contribute little to the model prediction result. Precision gating is orthogonal to this pruning technique as channel gating executes the whole network at the same precision.
More recently, Cao et al. (2019) propose SeerNet, which also executes a CNN model in dual precision. For each convolutional layer, SeerNet first executes a quantized version of the layer and uses the results to predict the output sparsity induced by the ReLU or the computational sparsity induced by the max-pooling layer. For those activations that are not suppressed according to the prediction, SeerNet computes the original convolution in full-precision (32-bit float). One key dif-
Input Activations = << + ℎ
ference between PG and SeerNet is that PG reuses the result of the low-precision compute as a partial product when it performs the high-precision multiplication in the update phase. In contrast, the full-precision compute in SeerNet does not reuse the output from the quantized layer, which incurs a higher execution cost.
Feature-level precision tuning. There is also prior work that uses a different precision to handle the outlier quantization. Park et al. (2018) propose value-aware quantization where the majority of data are computed at reduced precision while a small number of outliers are handled at high precision. Our approach is significantly different because we allow dual precision for every feature, not only for the outliers.

heading: 3 PRECISION GATING (PG)

text: In this section we first describe the basic mechanism of PG. We then discuss how to design the gating scheme to accelerate both forward and backward passes. Finally, we consider incorporating outlier clipping to reduce the quantization error.

heading: 3.1 BASIC FORMULATION

text:
We first define a linear layer in a neural network (either convolutional or fully-connected) as O = I∗W, where O, I, and W are the output, input, and weights, respectively. Suppose I is represented in a B-bit fixed-point format, which is shown in Figure 1. PG partitions I into (1) Ihb, the Bhb most-significant bits (MSBs), and (2) Ilb, the remaining Blb least-significant bits (LSBs). Here B = Bhb +Blb. More formally, we can write:
I = Ihb << Blb + Ilb (1)
Here<< denotes the left shift operator. We can then reformulate a singleB-bit linear layer into two lower-precision computations as:
O = Ohb + Olb = [W ∗ (Ihb << Blb)] + [W ∗ Ilb] (2)
Ohb is the partial product obtained by using the MSBs of input feature (Ihb) whereas Olb represents the remaining partial product computed with Ilb.
Precision gating works in two phases. In the prediction phase, PG performs the computation Ohb = W ∗ (Ihb << Blb). Output features of Ohb greater than a learnable gating threshold ∆ are considered important. In the update phase, PG computes Olb = W ∗ Ilb only for the important features and adds it to Ohb. The overall execution flow of PG is illustrated in Figure 2, where unimportant output features only take the upper path while important ones are computed as the sum of both paths. More precisely, this can be summarized as follows:
O =
{ Ohb Ohb ≤ ∆
Ohb + Olb Ohb > ∆ (3)
In essence, PG intends to compute the majority of (unimportant) features with Bhb bits and only a small set of important features with B bits. The importance of each element in the output O is calculated by comparing the magnitude of its partial sum Ohb to ∆. Let Sp be the percentage of
unimportant activations over all features. PG saves Sp·BlbB fraction of the compute in the original DNN model. PG thus achieves dual-precision execution using a lightweight gating mechanism which only adds a comparison operation. The goal is to minimize the average bitwidth of the multiply-add operations in the DNN execution.

heading: 3.2 EFFICIENT LEARNABLE GATING SCHEME

text:
PG automatically learns a gating threshold ∆c,l during training for each output channel in each DNN layer. A larger ∆c,l indicates that more output features are computed in low-precision, resulting in greater computational savings but possibly at the expense of reduced model accuracy. Define ∆ as the vector containing each gating threshold ∆c,l. We formulate the problem of optimizing ∆ as minimizing the original model loss L along with an L2 penalty term:
min W,∆
L(I, y;W,∆) + σ ‖∆− δ‖2 (4)
Here y is the ground truth label, σ is the penalty factor, and δ is the gating target, a target value for the learnable threshold. The penalty factor and gating target are hyperparameters which allow a user to emphasize high computation savings (large σ or δ) or accuracy preservation (small σ or δ).
Training a model with precision gating can be performed on commodity GPUs using existing deep learning frameworks. We implement PG on GPU as the equation O = Ohb + mask Olb, where mask = 1Ohb>∆ is a binary decision mask and represents element-wise multiplication. During forward propagation, most elements in mask are 0. PG therefore saves hardware execution cost by only computing a sparse Olb in the update phase. If PG is implemented in a dedicated hardware accelerator, MSBs and LSBs will be wired separately; The prediction phase can be controlled by a multiplexer, and only computes LSB convolutions while Ohb exceeds the threshold, thus achieving savings in both compute cycles and energy.
The mask is computed using a binary decision function (i.e., a step function), which has a gradient of zero almost everywhere. To let gradients flow through mask to ∆, we use a sigmoid on the backward pass to approximate the step function. Specifically, we define mask = sigmoid(α(Ohb− ∆)) only on the backward pass as in the previous work Hua et al. (2019b). Here α changes the slope of the sigmoid, thus controlling the magnitude of the gradients.

heading: 3.3 SPARSE BACK-PROPAGATION

text:
A sparse update phase only reduces the computational cost during the inference (forward propagation). We further propose to save the compute during the back-propagation by modifying the forward function of the PG block. Specifically, we square the mask element-wise.
O = Ohb + mask 2 Olb (5)
Given that mask is a binary tensor, mask2 in Eq. (5) preserves the same value as mask. Thus the forward pass remains unchanged. During the back-propagation, an additional mask term is introduced in computing the gradient of O with respect to the gating threshold ∆ in Eq. (6) because of the element-wise square. Consequently, the update of ∆ only requires the result of mask Olb which has already been computed during the forward pass.
∂O ∂∆ ≈ ∂O ∂mask ∂sigmoid(α(Ohb −∆)) ∂∆ = 2 ·mask Olb ∂sigmoid(α(Ohb −∆)) ∂∆ (6)
The gradient of O with respect to the weights W in Eq. (7) employs the same sparse mask Olb as the update of ∆. Therefore, precision gating can reduce the computational cost of both forwardprogagtion (inference) and back-propagation by the same factor.
∂O ∂W = ∂Ohb ∂W + mask2 ∂Olb ∂W = ∂Ohb ∂W + ∂mask Olb ∂W (7)

heading: 3.4 OUTLIER CLIPPING

text:
PG predicts important features using low-precision computation. One difficulty with this is that DNN activations are distributed in a bell curve, with most values close to zero and a few large outliers. The top row of Figure 3(a) shows some activations as blue dots, including a single outlier. If we quantize each value to 4 bits (second column) and use 2 most-significant bits in the prediction phase (third column), we see that almost all values are rounded to zero. In this case, PG can only distinguish the importance between the single outlier and the rest of the values no matter what ∆ is. Thus, the presence of large outliers greatly reduces the effectiveness of PG.
To address this, we combine PG with PACT (Choi et al., 2018), which clips each layer’s outputs using a learnable clip threshold. The bottom row of Figure 3 shows how clipping limits the dynamic range of activations, making values more uniformly distributed along the quantization grid. Now
the 2 most-significant bits can effectively separate out different groups of values based on magnitude. We apply PACT to PG in CNNs, which commonly use an unbounded activation function such as ReLU. RNNs, on the other hand, typically employ a bounded activation function (e.g., tanh, sigmoid) that often makes PACT unnecessary.

heading: 4 EXPERIMENTS

text:
We evaluate PG using ResNet-20 (He et al., 2016a) and ShiftNet-20 (Wu et al., 2018a) on CIFAR10 (Krizhevsky & Hinton, 2009), and ShuffleNet V2 (Ma et al., 2018) on ImageNet (Deng et al., 2009). ResNet is a very popular CNN architecture for image classification. ShiftNet and ShuffleNet are more compact architectures designed specifically for mobile and edge devices. We set the expansion rate of ShiftNet to be 6 and choose the 0.5× variant of ShffleNet V2 for all experiments. On CIFAR-10, the batch size is 128, and the models are trained for 200 epochs. The initial learning rate is 0.1 and decays at epoch 100, 150, 200 by a factor of 0.1 (i.e., multiply learning rate by 0.1). On ImageNet, the batch size is 512 and the models are trained for 120 epochs. The learning rate decays linearly from an initial value of 0.5 to 0.
We also test an LSTM model (Hochreiter & Schmidhuber, 1997) on the Penn Tree Bank (PTB) (Marcus et al., 1993) corpus. The model accuracy is measured by perplexity per word (PPW), where a lower PPW is better. Following the configuration used by He et al. (2016b) and Hubara et al. (2017), the number of hidden units in the LSTM cell is set to 300, and the number of layers is set to 1. We follow the same training setting as described in He et al. (2016b), except that the learning rate decays by a factor of 0.1 at epoch 50 and 90. All experiments are conducted on Tensorflow (Abadi et al., 2016) with NVIDIA GeForce 1080Ti GPUs. We report the top-1 accuracy for all experiments.
We replace the convolutional layers in CNNs and the dense layers in LSTM with the proposed PG block. Moreover, the following hyperparameters in PG need to be tuned appropriately to achieve a low average bitwidth with a high accuracy.
• The full bitwidth B – this represents the bitwidth for high-precision computation in PG. B is set to 5 or less on CIFAR-10, 5 or 6 on ImageNet, and 3 or 4 on PTB. • The prediction bitwidthBhb – this represents the bitwidth for low-precision computation. • The penalty factor σ – this is the scaling factor of the L2 loss for gating thresholds ∆. • The gating target δ – the target gating threshold. We use a variety of values δ ∈ [−1.0, 5.0]
in our experiments. • The coefficient α in the backward pass – α controls the magnitude of gradients flowing
to ∆. We set α to be 5 across all experiments.

heading: 4.1 CNN RESULTS

text:
To compare the hardware execution efficiency across different techniques, we compute the average bitwidth (Bavg) of all features in a DNN model:
Bavg = Bhb + (1− Sp)× (B −Bhb) (8)
Here Sp denotes sparsity in terms of the percentage of low-precision activations (i.e., number of unimportant features divided by total features). The computational cost of DNNs is proportional to the average bitwidth. Our results on CNNs are presented in Tables 1 and 2.
We first compare PG against two widely adopted quantization schemes — uniform quantization (UQ) and PACT (Choi et al., 2018). In Table 1, columns 3 and 4 show the average bitwidth and model accuracy of PG, respectively; columns 5-7 list the bitwidth and corresponding model accuracy of UQ and PACT, respectively. At each row, PG achieves a better accuracy with a lower average bitwidth (Bavg vs. Bits). Specifically, PG achieves 6.7% and 1.6% higher accuracy with 1.25× computational cost reduction, and 6.6% and 0.5% higher accuracy with 1.54× computational cost reduction than 2-bit UQ and PACT on ShiftNet-20 and ResNet-20 for CIFAR-10 (rows 3 and 6), respectively. We observe the same trend on ShuffleNet for ImageNet, where PG improves the accuracy of 5-bit UQ and PACT by 1.0% and 1.4% with 1.22× computational cost reduction (row 9). It is also worth noting that PG can recover the accuracy of the floating-point ShiftNet-20, ResNet-20, and ShuffleNet V2 0.5×with 3.9, 3.2, and 4.7 average bitwidth, respectively. This demonstrates that PG, using a learnable threshold, can predict unimportant features and reduce their bitwidth without compromising accuracy. The results compared to quantization baselines are visualized in Figure 4, which plots accuracy vs. average bitwidth — uniform quantization (squares), PACT (triangles), and PG (circles) are shown on separate curves. Results closer to the upper-left corner are better.
We then compare PG with Fix-Threshold, which is an extension of the zero-prediction (Lin et al., 2017; Song et al., 2018). Lin et al. (2017); Song et al. (2018) explicitly predict ReLU-induced zeros during inference. To have a fair comparison, we extend their technique to predict an arbitrary fixed threshold to achieve the same or lower Bavg as PG, reported as Fix-Threshold in Table 1. For CIFAR-10, we observe that PG achieves 20.2% and 18.7% higher accuracy with 1.75× and 1.38× computational cost reduction than Fix-Threshold on ShiftNet-20 and ResNet-20 (rows 3 and 6), respectively. The gap in accuracy becomes even larger on ShuffleNet V2 for ImageNet dataset. With the same or a lower average bitwidth, the accuracy of PG is at least 26% higher than FixThreshold (rows 7-9). In conclusion, PG consistently outperforms Fix-Threshold because PG uses a learnable gate function which can adjust its threshold to the clipped activation distribution.
We further compare PG with SeerNet (Cao et al., 2019) in Table 2. For each convolutional layer, SeerNet executes a quantized version of the same layer to predict the output sparsity. It then computes in full precision the output activations that are not suppressed according to the prediction. Since the code of SeerNet is currently unavailable, we implement the network in Tensorflow and boost its accuracy by retraining the network. We reduce the average bitwidth of SeerNet while keeping a comparable accuracy as PG. For CIFAR-10, PG reduces the computational cost of ResNet-20 3.3× more than SeerNet at the same prediction accuracy. Meanwhile for the hardware-friendly ShiftNet-20, PG achieves 3.2% higher accuracy with 4.5× less compute than SeerNet. For ImageNet, PG on ShuffleNet also achieves 0.4% higher accuracy with 2.4× computational cost reduction than SeerNet. It is worth noting that SeerNet does not reuse the outputs from the quantized layer, which may incur a nontrivial overhead in execution time. In contrast, when PG invokes the update phase, it reuses the outputs of the low-precision computation from the prediction phase.
In order to evaluate the efficacy of the learnable thresholds, we further sweep a series of manually set thresholds on the ResNet-20 for CIFAR-10. Table 3 shows the results where we use a dual-precision mode of B/Bhb = 3/2. As the threshold decreases from 3 to -4, the average bitwidth in the update phase consistently increases. This is expected because we compute more output features in a high precision. The model prediction accuracy therefore increases. Compared to these manually set thresholds, PG achieves a much improved model accuracy (91.2%) with a higher sparsity (90.1%).
To quantify the impact of sparse back-propagation described in Section 3.3, we run PG with and without sparse back-propagation on CNNs. Table 4 compares the sparsity in the update phase of PG with and without back-propagation under the same model accuracy and average bitwidth. Interestingly, we find that the sparsity in the update phase of PG with sparse back-propagation is consistently higher than that of PG without sparse back-propagation across the tested models and datasets. For both CIFAR-10 and ImageNet, the sparsity increases by between 6% and 21%. We hypothesize that sparse back-propagation zeros out the gradients flowing to non-activated LSB convolutions in the update phase, which leads to a higher sparsity.

heading: 4.2 LSTM RESULTS

text: PG also works well on RNNs. Table 5 reports our results applying PG on an LSTM model for the PTB corpus. Here, we only compare with the uniform quantization since PACT, Fix-Threshold, and SeerNet do not work for sigmoid or tanh activation functions. Although Hubara et al. (2017) claim that quantizing both weights and activations to 4 bits does not lower PPW, we observe a PPW degradation when B decreases from 8 to 4 bits in our implementation. The LSTM with 8-bit activations is therefore considered as the full-accuracy model. We observe the same trend as in the CNN evaluation where PG enables the 3-bit LSTM cell to improve the PPW by 1.2% and reduce the computational cost by 2.7× compared to the 8-bit uniform quantization.

heading: 4.3 SPARSE KERNEL SPEEDUP

text:
The sparse update phase of PG can be implemented efficiently with a new kernel called sampled dense-dense matrix multiplication (SDDMM). A convolutional layer with PG is then factorized into a regular low-precision convolution bounded with a low-precision SDDMM. To evaluate the potential speedup of PG, we implement the SDDMM kernel in Python leveraging a high performance JIT compiler Numba (Lam et al., 2015) and test it on the ResNet-20 model for CIFAR-10. Table 6 shows the layer-wise sparsity and the kernel speedup compared to the dense matrix multiplication baseline on Intel Xeon Silver 4114 CPU (2.20GHz). With the high sparsity (from 76% to 99%) in each layer induced by PG, the SDDMM kernel achieves up to 8.3× wall clock speedup over the general dense matrix-matrix multiplication (GEMM) kernel. The significant wall clock speedup shows a good potential of deploying PG on commodity hardware.
For a GPU implementation, we need to replace the GEMM kernel with the SDDMM kernel to accelerate the update phase. Mainstream deep learning frameworks such as Tensorflow currently do not provide a built-in operator for SDDMM, which is essential for achieving high performance on GPUs. Nevertheless, Nisa et al. (2018) have recently demonstrated that a highly optimized SDDMM kernel with a similar sparsity shown in Table 6 can achieve about 4× speedup over a GEMM ker-
nel. This shows strong evidence that PG has a potential to obtain high speedup on GPUs as well. Additionally, our approach is a good fit for the specialized accelerator architectures proposed by Lin et al. (2017) and Song et al. (2018). Due to the high sparsity, DNNs with PG are estimated to get at least 3× speedup and 5× energy efficiency on these dedicated hardware accelerators. We leave the deployment of the SDDMM kernel on GPU and dedicated hardware to future work.

heading: 5 CONCLUSIONS

text: We propose precision gating, a dynamic dual-precision quantization method that can effectively reduce the computational cost of DNNs. PG assigns higher precision to important features and lower precision to the remaining features at run-time. The proposed technique is end-to-end trainable, allowing individual models to learn to distinguish important and unimportant features. Experimental results show that PG outperforms state-of-the-art quantization and prediction approaches by a large margin on both CNN and RNN benchmarks on datasets such as Imagenet and Penn Tree Bank. We will release the source code on the author’s website.

heading: ACKNOWLEDGMENTS

text: This work was supported in part by the Semiconductor Research Corporation (SRC) and DARPA. One of the Titan Xp GPUs used for this research was donated by the NVIDIA Corporation. We thank Jordan Dotzel (Cornell) for his helpful discussions during the camera-ready revision.

heading: A APPENDIX

text:
A.1 FEATURE VISUALIZATION
In precision gating, we expect that the model will learn to compute features whose prediction values exceed the threshold using a high-precision while keeping others computed using a low precision. In the image recognition task, we expect that high-precision features are mostly in the region where an object lies. To provide evidence that PG can effectively learn to identity those regions, in Figure 5, we visualize the decision maps extracted from the final convolutional layer that is modified to support PG in the ResNet-20 model. A decision map is a gray scale 2D image that has the same spatial size as the output feature map in the same convolutional layer. The brighter a pixel is in the decision map, the more probably the same spatial location in the output feature map will be computed using a high precision. The first row contains the original input images in CIFAR-10, and the second row shows their corresponding decision maps. We can see clearly that in each decision map, the locations of bright pixels roughly align with the object in the original image.
A.2 ADDITIONAL RESULTS
We provide more supplementary results in this section as shown in Table 7.

title: PRECISION GATING: IMPROVING NEURAL NETWORK EFFICIENCY WITH DYNAMIC DUAL-PRECISION ACTI- VATIONS


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.

summaries: 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.

summaries: 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.

authors:
D. Arpit
S. Jastrzebski
N. Ballas
D. Krueger
E. Bengio
M. Kanwal
T. Maharaj
A. Fischer
A. Courville
Y. Bengio

title: A closer look at memorization in deep networks

authors:
S. Ben-David
J. Blitzer
K. Crammer
A. Kulesza
F. Pereira
J.W. Vaughan

title: A theory of learning from different domains. MLJ

title: Evolving culture versus local minima

venue: In Growing Adaptive Machines,

authors:
A. Bergamo
L. Torresani

title: Exploiting weakly-labeled web images to improve object classification: a domain adaptation approach

venue: In NeurIPS,

authors:
J. Deng
W. Dong
R. Socher
L. Li
K. Li
F. Li

title: Imagenet: A large-scale hierarchical image database

venue: In CVPR,

authors:
Y. Ganin
V.S. Lempitsky

title: Unsupervised domain adaptation by backpropagation

venue: In ICML,

authors:
M. Ghifary
D. Balduzzi
W.B. Kleijn
M. Zhang

title: Scatter component analysis : A unified framework for domain adaptation and domain generalization

authors:
B. Gong
Y. Shi
F. Sha
K. Grauman

title: Geodesic flow kernel for unsupervised domain adaptation

venue: In CVPR, pages 2066–2073,

authors:
M. Gong
K. Zhang
T. Liu
D. Tao
C. Glymour

title: Domain adaptation with conditional transferable components

authors:
M. Gong
K. Zhang
B. Huang
C. Glymour
D. Tao
K. Batmanghelich

title: Causal generative domain adaptation

venue: networks. CoRR,

authors:
A. Gretton
K.M. Borgwardt
M.J. Rasch
B. Schölkopf
A.J. Smola

title: A kernel two-sample test

authors:
G. Griffin
A. Holub
P. Perona

title: Caltech-256 object category dataset

venue: Technical report, California Institute of Technology,

authors:
Y. Guo
M. Xiao

title: Cross language text classification via subspace co-regularized multi-view learning

authors:
B. Han
Q. Yao
X. Yu
G. Niu
M. Xu
W. Hu
I.W. Tsang
M. Sugiyama

title: Co-teaching: Robust training of deep neural networks with extremely noisy labels

authors:
J. Hoffman
E. Tzeng
T. Park
J. Zhu
P. Isola
K. Saenko
A.A. Efros
T. Darrell

title: Cycada: Cycleconsistent adversarial domain adaptation

authors:
L. Jiang
Z. Zhou
T. Leung
L. Li
F. Li

title: Mentornet: Learning data-driven curriculum for very deep neural networks on corrupted labels

authors:
J. Lee
M. Raginsky

title: Minimax statistical learning with wasserstein distances

authors:
K. Lee
X. He
L. Zhang
L. Yang

title: Cleannet: Transfer learning for scalable image classifier training with label noise

authors:
Y. Li
X. Tian
M. Gong
Y. Liu
T. Liu
K. Zhang
D. Tao

title: Deep domain generalization via conditional invariant adversarial networks

venue: In ECCV,

authors:
T. Liu
D. Tao

title: Classification with noisy labels by importance reweighting

authors:
M. Long
Y. Cao
J. Wang
M.I. Jordan

title: Learning transferable features with deep adaptation networks

authors:
E. Malach
S. Shalev-Shwartz

title: Decoupling "when to update" from "how to update

authors:
S. Motiian
Q. Jones
S.M. Iranmanesh
G. Doretto

title: Few-shot adversarial domain adaptation

authors:
Giorgio Patrini
Alessandro Rozza
Aditya Krishna Menon
Richard Nock
Lizhen Qu

title: Making deep neural networks robust to label noise: A loss correction approach

authors:
K. Saito
Y. Ushiku
T. Harada

title: Asymmetric tri-training for unsupervised domain adaptation

authors:
K. Saito
K. Watanabe
Y. Ushiku
T. Harada

title: Maximum classifier discrepancy for unsupervised domain adaptation

authors:
F. Schroff
A. Criminisi
A. Zisserman

title: Harvesting image databases from the web

authors:
Y. Shu
Z. Cao
M. Long
J. Wang

title: Transferable curriculum for weakly-supervised domain adaptation

venue: In AAAI,

authors:
T. Tommasi
T. Tuytelaars

title: A testbed for cross-dataset analysis

venue: In ECCV TASK-CV Workshops,

authors:
E. Tzeng
J. Hoffman
T. Darrell
K. Saenko

title: Simultaneous deep transfer across domains and tasks

venue: In ICCV,

authors:
E. Tzeng
J. Hoffman
K. Saenko
T. Darrell

title: Adversarial discriminative domain adaptation

authors:
J. Xiao
J. Hays
K.A. Ehinger
A. Oliva
A. Torralba

title: SUN database: Large-scale scene recognition from abbey to zoo

authors:
M. Xiao
Y. Guo

title: Feature space independent semi-supervised domain adaptation via kernel matching

authors:
T. Xiao
T. Xia
Y. Yang
C. Huang
X. Wang

title: Learning from massive noisy labeled data for image classification

authors:
K. Zhang
B. Schölkopf
K. Muandet
Z. Wang

title: Domain adaptation under target and conditional shift

authors:
K. Zhang
M. Gong
B. Schölkopf

title: Multi-source domain adaptation: A causal view

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

venue: Figure 7 shows datasets: Bing,

title: Under review as a conference paper at ICLR 2020 (a) Bing provided by Bergamo and Torresani

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

venue: X ⊂ R and Y = {1,

title: After cross-propagating these checked data

heading: 1 INTRODUCTION

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.

heading: 2 WILDLY UNSUPERVISED DOMAIN ADAPTATION

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.

heading: 3 BUTTERFLY: TOWARDS ROBUST ONE-STEP APPROACH

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|.

heading: 4 BUTTERFLY VS. TWO-STEP APPROACH

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).

heading: 5 EXPERIMENTS

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.

heading: 6 CONCLUSIONS

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.

heading: A REVIEW OF GENERATION OF NOISY LABELS

text: This section presents a review on two label-noise generation processes.

heading: A.1 TRANSITION MATRIX

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.

heading: A.2 SAMPLE SELECTION

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).

heading: B TRANSITION MATRIX Q

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 .

heading: C DATASETS VISUALIZATION

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

heading: D THEORETICAL ANALYSIS

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).

heading: D.1 WUDA RUINS UDA METHODS

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.

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

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.

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

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).

heading: E RESULTS ON HUMAN-SENTIMENT WUDA TASKS

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.

heading: F EXPERIMENTAL SETTINGS

heading: F.1 NETWORK STRUCTURE AND OPTIMIZER

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.

heading: F.2 EXPERIMENTAL SETUP

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.

heading: F.3 LINKS TO DATASETS

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).

heading: G RUNNING TIME

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.

heading: H PROOFS

text: This section provides proofs of theorems demonstrated in the supplementary.

heading: H.1 PROOF OF THEOREM 1

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.

heading: H.2 PROOF OF THEOREM 2

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.

heading: H.3 PROOF OF THEOREM 3

heading: H.3.1 PRELIMINARY

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).

heading: H.3.2 PROOF OF THEOREM 3

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.