summaries: This paper proposes BRECQ which is a new Post Training Quantization (PTQ) method. The goal of the paper is to push the limit of PTQ to low bit precision (INT2). They try to address this by considering both inter and intra-layer sensitivity to find the best update to the model parameters so that the output from a block is minimally changed/perturbed. Furthermore, the authors also consider mixed precision quantization setting.

summaries: This paper explores the post-training inference quantization. Based on second-order quantization error analysis, it proposes to reconstruct quantized model in a block level to achieve SOTA accuracy for INT2 weight quantization, which distinguish this paper from previous reported layer-wise reconstruction approach. The proposed approach is intuitive and supported by extensive experiments across a wide range of image classification and object detection tasks.

summaries: I couldn't follow the method described in the paper. The authors are basically trying to address post-training quantization by perturbing the the weights of a trained DNN. The goal is to perturb the weights so that the quantized DNN will behave similar to the original full-precision DNN. The authors draw a link between this optimization problem and optimizing for the "reconstruction" of the output activations of a block (see Equation 7). The technique BRECQ, shown in Algorithm 1, is basically to optimize the perturbation of the weights for the right hand side of Equation 7 for each block of a DNN.

abstractText: We study the challenging task of neural network quantization without end-toend retraining, called Post-training Quantization (PTQ). PTQ usually requires a small subset of training data but produces less powerful quantized models than Quantization-Aware Training (QAT). In this work, we propose a novel PTQ framework, dubbed BRECQ, which pushes the limits of bitwidth in PTQ down to INT2 for the first time. BRECQ leverages the basic building blocks in neural networks and reconstructs them one-by-one. In a comprehensive theoretical study of the second-order error, we show that BRECQ achieves a good balance between crosslayer dependency and generalization error. To further employ the power of quantization, the mixed precision technique is incorporated in our framework by approximating the inter-layer and intra-layer sensitivity. Extensive experiments on various handcrafted and searched neural architectures are conducted for both image classification and object detection tasks. And for the first time we prove that, without bells and whistles, PTQ can attain 4-bit ResNet and MobileNetV2 comparable with QAT and enjoy 240× faster production of quantized models. Codes are available at https://github.com/yhhhli/BRECQ.

title: Natural gradient works efficiently in learning

venue: Neural computation,

authors:
Haoli Bai
Jiaxiang Wu
Irwin King
Michael Lyu

title: Few shot network compression via cross distillation

venue: In Proceedings of the AAAI Conference on Artificial Intelligence,

authors:
Ron Banner
Yury Nahshan
Daniel Soudry

title: Post training 4-bit quantization of convolutional networks for rapid-deployment

venue: In Advances in Neural Information Processing Systems,

authors:
Aleksandar Botev
Hippolyt Ritter
David Barber

title: Practical gauss-newton optimisation for deep learning

venue: arXiv preprint arXiv:1706.03662,

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

title: Zeroq: A novel zero shot quantization framework

venue: In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,

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 preprint arXiv:1805.06085,

authors:
Yoni Choukroun
Eli Kravchik
Fan Yang
Pavel Kisilev

title: Low-bit quantization of neural networks for efficient inference

venue: IEEE/CVF International Conference on Computer Vision Workshop (ICCVW),

authors:
Xin Dong
Shangyu Chen
Sinno Pan

title: Learning to prune deep neural networks via layer-wise optimal brain surgeon

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

title: Hawq: Hessian aware quantization of neural networks with mixed-precision

venue: In Proceedings of the IEEE International Conference on Computer Vision,

authors:
Steven K. Esser
Jeffrey L. McKinstry
Deepika Bablani
Rathinakumar Appuswamy
Dharmendra S. Modha

title: Learned step size quantization

venue: In International Conference on Learning Representations,

authors:
Ruihao Gong
Xianglong Liu
Shenghu Jiang
Tianxiang Li
Peng Hu
Jiazhen Lin
Fengwei Yu
Junjie Yan

title: Differentiable soft quantization: Bridging full-precision and low-bit neural networks

authors:
Zichao Guo
Xiangyu Zhang
Haoyuan Mu
Wen Heng
Zechun Liu
Yichen Wei
Jian Sun

title: Single path one-shot neural architecture search with uniform sampling

venue: In European Conference on Computer Vision,

authors:
Qingchang Han
Yongmin Hu
Fengwei Yu
Hailong Yang
Bing Liu
Peng Hu
Ruihao Gong
Yanfei Wang
Rui Wang
Zhongzhi Luan

title: Extremely low-bit convolution optimization for quantized neural network on modern computer architectures

venue: In 49th International Conference on Parallel Processing-ICPP,

authors:
Song Han
Huizi Mao
William J Dally

title: Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding

venue: arXiv preprint arXiv:1510.00149,

authors:
Babak Hassibi
David G Stork

title: Second order derivatives for network pruning: Optimal brain surgeon

venue: In Advances in neural information processing systems,

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,

authors:
Geoffrey Hinton
Oriol Vinyals
Jeff Dean

title: Distilling the knowledge in a neural network

venue: arXiv preprint arXiv:1503.02531,

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: The Journal of Machine Learning Research,

authors:
Itay Hubara
Yury Nahshan
Yair Hanani
Ron Banner
Daniel Soudry

title: Improving post training neural quantization: Layer-wise calibration and integer programming

venue: arXiv preprint arXiv:2006.10518,

authors:
Daniel Jakubovitz
Raja Giryes
Miguel RD Rodrigues

title: Generalization error in deep learning

venue: In Compressed Sensing and Its Applications,

authors:
Diederik P Kingma
Jimmy Ba

title: Adam: A method for stochastic optimization

venue: arXiv preprint arXiv:1412.6980,

authors:
Yann A LeCun
Léon Bottou
Genevieve B Orr
Klaus-Robert Müller

title: Efficient backprop

venue: In Neural networks: Tricks of the trade,

authors:
Yuhang Li
Xin Dong
Wei Wang

title: Additive powers-of-two quantization: An efficient nonuniform discretization for neural networks

authors:
Tsung-Yi Lin
Priya Goyal
Ross Girshick
Kaiming He
Piotr Dollár

title: Focal loss for dense object detection

venue: In Proceedings of the IEEE international conference on computer vision,

title: Deep learning via hessian-free optimization

authors:
James Martens
Roger Grosse

title: Optimizing neural networks with kronecker-factored approximate curvature

venue: In International conference on machine learning,

authors:
Markus Nagel
Mart van Baalen
Tijmen Blankevoort
Max Welling

title: Data-free quantization through weight equalization and bias correction

authors:
Markus Nagel
Rana Ali Amjad
Mart van Baalen
Christos Louizos
Tijmen Blankevoort

title: Up or down? adaptive rounding for post-training quantization

venue: arXiv preprint arXiv:2004.10568,

authors:
Yury Nahshan
Brian Chmiel
Chaim Baskin
Evgenii Zheltonozhskii
Ron Banner
Alex M Bronstein
Avi Mendelson

title: Loss aware post-training quantization

authors:
Antonio Polino
Razvan Pascanu
Dan Alistarh

title: Model compression via distillation and quantization

venue: arXiv preprint arXiv:1802.05668,

authors:
Ilija Radosavovic
Raj Prateek Kosaraju
Ross Girshick
Kaiming He
Piotr Dollár

title: Designing network design spaces

authors:
Shaoqing Ren
Kaiming He
Ross Girshick
Jian Sun

title: Faster r-cnn: Towards real-time object detection with region proposal networks. In Advances in neural information processing

authors:
Mark Sandler
Andrew Howard
Menglong Zhu
Andrey Zhmoginov
Liang-Chieh Chen

title: Mobilenetv2: Inverted residuals and linear bottlenecks

authors:
Hardik Sharma
Jongse Park
Naveen Suda
Liangzhen Lai
Benson Chau
Vikas Chandra
Hadi Esmaeilzadeh

title: Bit fusion: Bit-level dynamically composable architecture for accelerating deep neural network

venue: ACM/IEEE 45th Annual International Symposium on Computer Architecture (ISCA),

authors:
Mingxing Tan
Bo Chen
Ruoming Pang
Vijay Vasudevan
Mark Sandler
Andrew Howard
Quoc V Le

title: Mnasnet: Platform-aware neural architecture search for mobile

venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,

authors:
Lucas Theis
Iryna Korshunova
Alykhan Tejani
Ferenc Huszár

title: Faster gaze prediction with dense networks and fisher pruning

venue: arXiv preprint arXiv:1801.05787,

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

title: Haq: Hardware-aware automated quantization with mixed precision

authors:
Peisong Wang
Qiang Chen
Xiangyu He
Jian Cheng

title: Towards accurate post-training network quantization via bit-split and stitching

venue: In Proc. 37nd Int. Conf. Mach. Learn.(ICML),

authors:
Barret Zoph
Quoc V Le

title: Neural architecture search with reinforcement learning

venue: arXiv preprint arXiv:1611.01578,

heading: 1 INTRODUCTION

text:
The past decade has witnessed the rapid development of deep learning in many tasks, such as computer vision, autonomous driving, etc. However, the issue of huge computation cost and memory footprint requirements in deep learning has received considerable attention. Some works such as neural architecture search (Zoph & Le, 2016) try to design and search a tiny network, while others, like quantization (Hubara et al., 2017), and network pruning (Han et al., 2015) are designed to compress and accelerate off-the-shelf well-trained redundant networks.
Many popular quantization and network pruning methods follow a simple pipeline: training the original model and then finetune the quantized/pruned model. However, this pipeline requires a full training dataset and many computation resources to perform end-to-end backpropagation, which will greatly delay the production cycle of compressed models. Besides, not all training data are always ready-to-use considering the privacy problem. Therefore, there is more demand in industry for quantizing the neural networks without retraining, which is called Post-training Quantization. Although PTQ is fast and light, it suffers from severe accuracy degeneration when the quantization precision is low. For example, DFQ (Nagel et al., 2019) can quantize ResNet-18 to 8-bit without accuracy loss (69.7% top-1 accuracy) but in 4-bit quantization, it can only achieve 39% top-1 accuracy. The primary reason is the approximation in the parameter space is not equivalent to the approximation in model space thus we cannot assure the optimal minimization on the final task loss.
Recent works like (Nagel et al., 2020) recognized the problem and analyzed the loss degradation by Taylor series expansion. Analysis of the second-order error term indicates we can reconstruct each layer output to approximate the task loss degeneration. However, their work cannot further quantize the weights into INT2 because the cross-layer dependency in the Hessian matrix cannot be ignored when the perturbation on weight is not small enough. In this work, we analyze the second-order
∗Equal contribution, Corresponding author.
error based on the Gauss-Newton matrix. We show that the second-order error can be transformed into network final outputs but suffer from bad generalization. To achieve the best tradeoff, we adopt an intermediate choice, block reconstruction. In addition, our contributions are threefold:
1. Based on the second-order analysis, we define a set of reconstruction units and show that block reconstruction is the best choice with the support from theoretical and empirical evidence. We also use Fisher Information Matrix to assign each pre-activation with an importance measure during reconstruction. 2. We incorporate genetic algorithm and the well-defined intra-block sensitivity measure to generate latency and size guaranteed mixed precision quantized neural networks, which fulfills a general improvement on both specialized hardware (FPGA) and general hardware (ARM CPU). 3. We conduct extensive experiments to verify our proposed methods. We find that our method is applicable to a large variety of tasks and models. Moreover, we show that post-training quantization can quantize weights to INT2 without significant accuracy loss for the first time.

heading: 2 PRELIMINARIES

text:
Notations Vectors are denoted by small bold letters and matrices (or tensors) are denoted by capital bold letters. For instance, W and w represent the weight tensor and its flattened version. Bar accent denotes the expectation over data points, e.g. ā. Bracketed superscript w(`) indicates the layer index. For a convolutional or a fully-connected layer, we mark its input and output vectors by x and z. Thus given a feedforward neural network with n layers, we can denote the forward process by
x(`+1) = h(z(`)) = h(W(`)x(`) + b(`)), 1 ≤ ` ≤ n, (1) where h(·) indicates the activation function (ReLU in this paper). For simplicity, we omit the analysis of bias b(`) as it can be merged into activation. || · ||F denotes the Frobenius norm. Quantization Background Uniform symmetric quantization maps the floating-point numbers to several fixed-points. These points (or grids) have the same interval and are symmetrically distributed. We denote the set that contains these grids asQu,symb = s×{−2b−1, . . . , 0, . . . , 2b−1− 1}. Here, s is the step size between two grids and b is the bit-width. Quantization function, denoted by q(·) : R → Qu,symb , is generally designed to minimize the quantization error:
min ||ŵ −w||2F . s.t. ŵ ∈ Q u,sym b (2)
Solving this minimization problem, one can easily get the q(·) by leveraging the rounding-to-nearest operation b·e. Rounding-to-nearest is a prevalent method to perform quantization, e.g. PACT (Choi et al., 2018). However, recently some empirical or theoretical evidence supports that simply minimizing the quantization error in parameter space does not bring optimal task performances. Specifically, Esser et al. (2020) propose to learn the step size s by gradient descent in quantization-aware training (QAT). LAPQ (Nahshan et al., 2019) finds the optimal step size when the loss function is minimized without re-training the weights. Their motivations are all towards minimizing a final objective, which is the task loss, i.e.,
minE[L(ŵ)], s.t. ŵ ∈ Qu,symb . (3) While this optimization objective is simple and can be well-optimized in QAT scenarios, it is not easy to learn the quantized weight without end-to-end finetuning as well as sufficient training data and computing resources. In post-training quantization settings, we only have full precision weights that w? = arg minw E[L(w)] where w ∈ R and a small subset of training data to do calibration. Taylor Expansion It turns out that the quantization imposed on weights could be viewed as a special case of weight perturbation. To quantitatively analyze the loss degradation caused by quantization, Nagel et al. (2020) use Taylor series expansions and approximates the loss degradation by
E[L(w + ∆w)]− E[L(w)] ≈ ∆wTḡ(w) + 1 2 ∆wTH̄(w)∆w, (4)
where ḡ(w) = E[∇wL] and H̄(w) = E[∇2wL] are the gradients and the Hessian matrix and ∆w is the weight perturbation. Given the pre-trained model is converged to a minimum, the gradients can be safely thought to be close to 0. However, optimizing with the large-scale full Hessian is memoryinfeasible on many devices as the full Hessian requires terabytes of memory space. To tackle this problem, they make two assumptions:
1. Layers are mutual-independent, thus the Hessian is in the form of layer-diagonal1 and Kroneckerfactored, i.e., H̄(w
(`)) = E[x(`)x(`),T ⊗ H(z(`))], where ⊗ is the Kronecker product. 2. The second-order derivatives of pre-activations are constant diagonal matrix (H(z
(`)) = c × I) which is independent of input data points.
At last, the objective is transformed into a practical proxy signal, the change in feature-maps (z = Wx), and the quantized model can be obtained by a layer-by-layer feature map reconstruction algorithm (with few calibration images). Recent works, like Bit-Split (Wang et al., 2020) and AdaQuant (Hubara et al., 2020), also take this layer-wise objective to improve the post-training quantization. However, they failed to quantize weights to INT2. We think the inherent reason is that when ∆w grows higher, the former assumptions do not hold and an accurate signal is required.

heading: 3 PROPOSED METHOD

heading: 3.1 CROSS-LAYER DEPENDENCY

text:
Denote the neural network output z(n) = f(θ), the loss function can be represented by L(f(θ)) where θ = vec[w(1),T, . . . ,w(n),T]T is the stacked vector of weights in all n layers. The Hessian matrix can be computed by
∂2L
∂θi∂θj =
∂
∂θj ( m∑ k=1 ∂L ∂z (n) k ∂z (n) k ∂θi ) = m∑ k=1 ∂L ∂z (n) k ∂2z (n) k ∂θi∂θj + m∑ k,l=1 ∂z (n) k ∂θi
∂2L
∂z (n) k ∂z (n) l
∂z (n) l
∂θj , (5)
where z(n) ∈ Rm. Since the pretrained full precision model is converged to a local minimum, we can assume the Hessian is positive-semidefinite (PSD). Specifically, the converged model has ∇z(n)L close to 0 so the first term in Eq. (5) is neglected and Hessian becomes the Gauss-Newton (GN) matrix G(θ). GN matrix can be written in matrix form (Botev et al., 2017) as
H(θ) ≈ G(θ) = Jz(n)(θ)TH(z (n))Jz(n)(θ), (6)
where Jz(n)(θ) is the Jacobian matrix of the network output with respect to the network parameters. However, in practice, we cannot explicitly compute and store the Jacobian for each input data point in such a raw form. To reduce the computation and memory budget, we will transform the secondorder error into the network output, as shown in the following theorem. Theorem 3.1. Consider an n-layer feedforward neural network with ReLU activation function. Assuming all weights are quantized, the second-order error optimization can be transformed by:
arg min θ̂ ∆θTH̄(θ)∆θ ≈ arg min θ̂
E [ ∆z(n),TH(z (n))∆z(n) ] . (7)
Remark 3.1. The same transformation is also applicable for activation quantization. The quadratic loss is defined as E[∆γTH(γ)∆γ] where ∆γ = vec[∆x(1),T, . . . ,∆x(n),T]T.
We prove the theorem using the quadratic form, details can be found in Appendix A.1. Here we provide a sketch of the proof by matrix form. The product of perturbation and Jacobian can be thought as the first-order Taylor approximation of the change in network output ∆z(n):
∆z(n) = ẑ(n) − z(n) ≈ Jz(n)(θ)∆θ. (8)
Therefore, combining Eq. (8) and Eq. (6) we can transform the large-scale second-order error into the change in network outputs characterized by the output Hessian H(z
(n)). The theorem indicates a simple observation, suppose a well-trained teacher model and an initialized student model, we can minimize their discrepancy by reconstructing the network’s final output z(n), which coincides with and generalizes the distillation (Hinton et al., 2015; Polino et al., 2018). LAPQ (Nahshan et al., 2019) also considers the dependency but their optimization does not rely on second-order information. However, we should emphasize that distillation requires the same computation and data resources as in normal training procedure, which is impractical for PTQ with limited data.
1To prevent ambiguity, we hereby use layer-diagonal Hessian to replace the common name “block-diagonal Hessian” because the block in this paper means a building block in the CNNs.

heading: 3.2 BLOCK RECONSTRUCTION

text:
Although the network output reconstruction has an accurate estimation of the second-order error, we find in practice it is worse than the layer-by-layer reconstruction in PTQ. The primary reason for this is optimizing the whole networks over 1024 calibration data samples leads to over-fitting easily. As Jakubovitz et al. (2019) explained, the networks can have perfect expressivity when the number of parameters exceeds the number of data samples during training, but lower training error does not ensure lower test error. We find layer-wise reconstruction acts like a regularizer which reduces the generalization error by matching each layer’s output distribution. In other words, both layer-wise and network-wise output reconstruction has their own drawbacks. And there should be a better bias-variance trade-off choice to conduct reconstruction at an intermediate granularity.
The layer-wise optimization corresponds to layer-diagonal Hessian (Fig. 1b blue parts) and the network-wise optimization corresponds to full Hessian (Fig. 1b green parts). Similarly, we can define an intermediate block-diagonal Hessian. Formally, if layer k to layer ` (where 1 ≤ k < ` ≤ n) form a block, the weight vector is defined as θ̃ = vec[w(k),T, . . . ,w(`),T]T and the Hessian can be also transformed by ∆θ̃TH̄(θ̃)∆θ̃ = E[∆z(`),TH(z(`))∆z(`)]. Such block-diagonal Hessian ignores the inter-block dependency and considers the intra-block dependency but it produces less generalization error. Then we can block-by-block reconstruct the intermediate output.
To this end, we define 2 extra kinds of intermediate reconstruction granularity: Stage-wise reconstruction and Block-wise reconstruction. These 4 reconstruction granularities are described below:
1. Layer-wise Reconstruction: Assume the Hessian matrix is layer-diagonal and optimize the layer output one-by-one. It does not consider cross-layer dependency and resemble existing methods (Nagel et al., 2020; Hubara et al., 2020; Wang et al., 2020). 2. Block-wise Reconstruction: A block is the core component in modern CNN, such as the Residual Bottleneck Block as shown in Fig. 1a. This method assumes the Hessian matrix is blockdiagonal and block-by-block perform reconstruction, which ignores inter-block dependencies. 3. Stage-wise Reconstruction: A stage is where the featuremaps will be downsampled and generate more channels, which is believed to produce higher-level features. Typical CNN in ImageNet dataset contains 4 or 5 different stages. This method simultaneously optimizes all layers within a stage and thus considers more dependencies than the block-wise method. 4. Network-wise Reconstruction: Optimize the whole quantized network by reconstructing the output of the final layers. This method resembles distillation but does not result in good performances with few images because of high generalization error.
The relationship between network, stage, block, and layer is illustrated in Fig. 1a. We test these 4 kinds of reconstruction granularity and find that block-wise optimization outperforms others. We think this is because the main off-diagonal loss in the Hessian is concentrated in each block, as Fig. 1b orange part illustrated, while the inter-block loss is small and can be ignored in the opti-
Algorithm 1: BRECQ optimization Input: Pretrained FP model; Calibration dataset, iteration T for all i = 1, 2, . . . , N -th block in the FP model do
Collect input data to the block x(i), the FP output z(i) and its gradient g(z (i)) ; for all j = 1, 2, . . . , T -iteration do Get quantized output ẑ(i) and compute ∆z(i) = z(i) − ẑ(i); Descend Eq. (10) and update the rounding of all the weights in this block (Eq. (16)); if Activation Quantization is triggered then
Update the activation quantization step size (Eq. (18)).
After optimization, compute the sensitivity for each layer and between layers (2-bit only); return Quantized model, Sensitivities for mixed precision;
mization. The shortcut connections, which is proposed in (He et al., 2016), may also increase the dependencies within a block. Also, the stage-wise or net-wise optimization suffer from the bad generalization on the validation set and degenerate the final performances. We report the quantitative comparison in Sec. 4.1. We name our algorithm BRECQ, because we choose block as our base reconstruction unit. It is necessary to point out that our analysis does not give the optimal configuration of the reconstruction granularity. The choice of block-wise optimization comes from our experiments and we find this choice has two merits. (1) No hyper-parameters included and (2) applicable for all models and all tasks we tested.

heading: 3.3 APPROXIMATING PRE-ACTIVATION HESSIAN

text:
With block-diagonal approximated Hessian matrix, we can measure the cross-layer dependency inside each block and transform any block’s second-order error to the output of this block E[∆z(`),TH(z(`))∆z(`)]. This objective requires the further computation of the knowledge in the rest of the network, i.e., pre-activation Hessian H(z
(`)). One way is to follow Nagel et al. (2020) and assume H(z
(`)) = c × I. Therefore the quadratic loss becomes ||∆z(`)||2. This method might be easy to implement but lose too much information.
We use the diagonal Fisher Information Matrix (FIM) to replace the pre-activation Hessian. Formally, given a probabilistic model p(x|θ), the FIM is defined as:
F̄(θ) = E [ ∇θ log pθ(y|x)∇θ log pθ(y|x)T ] = −E [ ∇2θ log pθ(y|x) ] = −H̄(θ)log p(x|θ). (9)
The FIM is equal to the negative expected Hessian of the log-likelihood function, therefore, a simple corollary is that the Hessian of task loss will become FIM if the model distribution matches the true data distribution (LeCun et al., 2012). Although matching true data distribution seems impossible, this is the best we can do since the pretrained model is converged.
The diagonal of the pre-activation FIM is equal to the squared gradients of each elements, which is successfully used in Adam (Kingma & Ba, 2014) for the second momentum. The optimization objective becomes
min ŵ
E [ ∆z(`),TH(z (`))∆z(`) ]
= min ŵ
E [ ∆z(`),Tdiag ( ( ∂L
∂z (`) 1
)2, . . . , ( ∂L
∂z (`) a
)2 ) ∆z(`) ] . (10)
Compared with the MSE minimization, the above minimization incorporates the squared gradient information. If the output has higher absolute gradients, it will receive more attention when being reconstructed. A similar method for pruning the pre-activation has been proposed in Theis et al. (2018).
Note that BRECQ is compatible with any optimization method, like STE (Hubara et al., 2017). Here we adopt adaptive rounding (Nagel et al., 2020) for weights and learned step size (Esser et al., 2020) for activation step size because we observe they generally perform better in PTQ, see details in Appendix B.4.1. We formulate the overall calibration algorithm for a unified precision model in algorithm 1. We should emphasize that we only need a small subset (1024 in our experiments) of the
whole training dataset to calibrate the quantized model. And we can obtain a quantized ResNet-18 within 20 minutes on a single GTX 1080TI GPU.

heading: 3.4 MIXED PRECISION

text:
To further push the limit of post-training quantization, we employ mixed precision techniques, which can be formulated by
min c L(ŵ, c), s.t. H(c) ≤ δ, c ∈ {2, 4, 8}n. (11)
Here, c is the bit-width vector with the shape of number of layers. H(·) is a hardware performance measurement function, which is used to ensure the mixed precision model has the same or lower hardware performance (e.g., memory and speed) than a predefined threshold δ. We choose 2, 4, 8-bit for mixed precision because they are most common in practical deployment.
Regarding the training lossL, we find that nearly all existing literature (Cai et al., 2020; Hubara et al., 2020; Dong et al., 2019) uses layer-wise measurement. They all assume the sensitivity within a layer is independent and can be summed together. Therefore, the mixed precision problem becomes an integer programming problem. However, we argue that the loss measurement should contain two parts: diagonal loss and off-diagonal loss, the first is the same with previous works and measure the sensitivity of each layer independently, while the off-diagonal loss is used to measure the cross-layer sensitivity. Theoretically, we should examine all permutations, which results in 3n possibilities and prohibits the search algorithm. Our first attempt is to reduce the off-diagonal loss into the blocklevel as we mentioned that the Hessian can be approximated to a block-diagonal matrix. Granted, we still find the search space is large, for example, if a block has four layers, then we have to consider the 34 = 81 permutations for a single block. Based on our preliminary experiments, we find that 4-bit and 8-bit quantization nearly do not drop the final accuracy. Hence we only take 2-bit permutations into consideration and drastically reduce the search space. We use genetic algorithm (Guo et al., 2020) to search the optimal bitwidth configuration with hardware performance threshold, the algorithm is located in algorithm 2. Due to space limits, we put related works in Appendix 5. Readers can refer to related works for a brief discussion on quantization and secondorder analysis.

heading: 4 EXPERIMENTS

text: In this section, we report experimental results for the ImageNet classification task and MS COCO object detection task. The detailed implementation of the experiments can be found in the Appendix B.4.4. The rest of this section will contain ablation study on reconstruction granularity, classification and detection results, mixed precision results and comparison with quantization-aware training. In Appendix B, we conduct more experiments, including the impact of the first and the last layer, the impact of calibration dataset size and data source.

heading: 4.1 ABLATION STUDY

text:
We test four kinds of reconstruction granularity: Net-wise, Stage-wise, Block-wise, and Layer-wise
reconstruction. We conduct ImageNet experiments using MobileNetV2 and ResNet-18 with 2- bit weight quantization for all layers except for the first and the last layer. It can be seen from Table 1 that Block-wise optimization outperforms other methods. This result implies that the generalization error in net-wise and stage-wise optimization outweighs their off-diagonal loss. In ResNet-
18, we find the difference is not significant, this can be potentially attributed to that ResNet-18 only has 19 layers in the body and the block size, as well as the stage size, is small, therefore leading to indistinct results.

heading: 4.2 IMAGENET

text: We conduct experiments on a variety of modern deep learning architectures, including ResNet (He et al., 2016) with normal convolution, MobileNetV2 (Sandler et al., 2018) with depthwise separa-

heading: Methods Bits (W/A) ResNet-18 ResNet-50 MobileNetV2 RegNet-600MF RegNet-3.2GF MnasNet-2.0

heading: Methods Bits (W/A) ResNet-18 ResNet-50 MobileNetV2 RegNet-600MF RegNet-3.2GF MNasNet-2.0

text: ble convolution and RegNet (Radosavovic et al., 2020) with group convolution. Last but not least important, we also investigate the neural architecture searched (NAS) models, MNasNet (Tan et al., 2019). In Table 2, we only quantize weights into low-bit integers and keep activations full precision. We compare with strong baselines including Bias Correction, optimal MSE, AdaRound, AdaQuant, and Bit-split. Note that the first and the last layer are kept with 8-bit. While most of the existing methods have good performances in 4-bit quantization, they cannot successfully quantize the model into 2-bit. Our method consistently achieves the lowest accuracy degradation for ResNets (within 5%) and other compact models. We further quantize activations into 4-bit to make the quantized model run on integer-arithmetic hardware platforms. We find that 4-bit activation quantization can have a huge impact on RegNet and MobileNet. Nonetheless, our methods produce higher performance than other state-of-the-arts. To be noted, BRECQ is the first to promote the 2W4A accuracy of PTQ to a usable level while all other existing methods crashed.

heading: Models Methods Precision Accuracy Model Size Training Data GPU hours

heading: 4.3 COMPARISON WITH QUANTIZATION-AWARE TRAINING

text: In this section, we compare our algorithm (post-training quantization) with some quantization-aware training methods, including PACT (Choi et al., 2018), DSQ (Gong et al., 2019), LSQ (Esser et al., 2020), and a mixed precision technique HAQ (Wang et al., 2019). Table 4 shows that although BRECQ is a PTQ method with limited available data, it can achieve comparable accuracy results with existing quantization-aware training models. In addition, our method can surpass them in 4- bit MobileNetV2 while using less than one training GPU hours. Our method also has comparable accuracy with HAQ, which is a training-based mixed precision method. Note that our GPU hours include 3 unified precision training (2-, 4-, 8-bit respectively) and further mixed-precision training only needs to check the lookup table. Instead, HAQ would end-to-end search for each hardware performance threshold from scratch.

heading: 4.4 MS COCO

text: To validate the effectiveness of BRECQ on other tasks, we conduct object detection on the twostage Faster-RCNN (Ren et al., 2015) and the one-stage RetinaNet (Lin et al., 2017). ResNet-18, 50 as well as MobileNetV2 are adopted as backbones for the detection model. Results in Table 5 demonstrate our method nearly does not drop the performance in 4-bit weight quantization and 8- bit activation. In particular, BRECQ only decreases 0.21% mAP performance on 4-bit ResNet-18 backboned Faster RCNN. On 4-bit ResNet-50 backboned RetinaNet, our method is outperforms the mixed precision based ZeroQ model by 3% mAP. Even when the weight bit decreases to 2, the model still achieves near-to-original mAP.

heading: 4.5 MIXED PRECISION

text: In this section, we test (1) model-size guaranteed mixed precision and (2) FPGA latency guaranteed mixed precision2 to unleash the potential of mixed precision and further push the limit of PTQ. We choose ResNet-18, MobileNetV2, and RegNetX-600MF to validate the efficacy of our algorithm. Note that in this section, we keep activation in 8-bit because we only compare the discrepancy between the unified and mixed precision in weights. We omit 3-bit weight quantization in unified precision because it is usually unfriendly to the hardware. Latency settings can be found in Appendix B.4.3. From Fig. 2 we find that (1) mixed precision consistently outperforms unified precision, especially when using extremely low-bit, e.g., up to 10% accuracy increase with the same latency as the 2-bit model. (2) mixed precision can produce many bit configurations that can adapt to plenty of hardware requirements while unified precision can only have 2 fixed models.

heading: 5 RELATED WORKS

text:
Quantization Model quantization can be classified into two categories: Quantization-aware Training (QAT) and Post-training Quantization (PTQ). Rounding floating-point numbers to fixed-points numbers will produce 0 gradients almost everywhere. Therefore, most QAT methods employ the Straight-Through Estimator (STE) for gradients approximation. Gong et al. (2019) uses a differentiable tanh function to gradually approach the step function. Choi et al. (2018); Esser et al. (2020) introduces parameterized clipping thresholds to learn it by STE. Apart from uniform quantization, some works like Li et al. (2019) argue that non-uniform quantization has better performance than uniform quantization while keeping its efficiency. Despite the promising results given by QAT methods, they usually need more than 100 GPU hours to get it. In that case, PTQ plays an important role which is what we focus on in this paper. Generally, most deep learning models can be safely quantized to 8-bit without re-training. Data-Free Quantization Nagel et al. (2019) even do layer-wise 8-bit PTQ without any data. However, in 4-bit quantization, most parameter space-based methods cannot obtain good performances. Recently, Nagel et al. (2020) propose to do layer-wise calibration and made huge progress in 4-bit quantization. Our work continues its analysis on Taylor expansion and considers the off-diagonal loss. Another perspective of quantification is the precision allocation scheme. Hardware-aware Quantization (HAQ Wang et al. (2019)) leverages reinforcement learning to search the optimal bitwidth configuration. Hessian-aware Weight Quantization (HAWQ) (Dong et al., 2019) utilizes the second-order information to decide the bitwidth. Mixed precision also appears in PTQ, such as the Pareto frontier method in ZeroQ (Cai et al., 2020) and the Integer Programming method in AdaQuant (Hubara et al., 2020).
Second-order Analysis and Optimization The history of second-order information in perturbation analysis can be traced to the 1990s like Optimal Brain Surgeon (Hassibi & Stork, 1993; Dong et al., 2017). The Hessian matrix is essential for pruning and quantization. As aforementioned, HAWQ uses the largest eigenvalue of Hessian to determine the sensitivity. Hessian matrix is also important for second-order optimization like Newton’s method as it consists of the curvature information. However, calculating the real full Hessian is prohibitive on today’s deep learning architectures. Therefore, approximations are made to simplify the calculation and make the storage more flexible, e.g., Gauss-Newton optimization with Kronecker-factored recursive approximation Botev et al. (2017). Hessian-Free optimization (Martens, 2010) avoids the explicit computation of the Hessian matrix by solving the linear system g = Hv. Second-order optimization with FIM is called Natural Gradient Descent (Amari, 1998). K-FAC (Martens & Grosse, 2015) utilizes the layer-diagonal FIM and the approximation of the expected Kronecker product to compute the curvature information.

heading: 6 CONCLUSION

text:
In this paper, we propose BRECQ, a post-training quantization framework by analyzing the secondorder error. We show that the reconstruction of quantization at the block granularity arrives at a good balance of cross-layer dependency and first order approximation, especially in 2-bit weight quantization where no prior works succeed to quantize. BRECQ is compatible with mixed precision and can reduce the search cost. To our best knowledge, BRECQ reaches the highest performance in post-training quantization and is the first to be on a par with quantization-aware training using 4-bit.
2We also test mobile CPU latency guaranteed mixed precision, located in Appendix B.3.

heading: ACKNOWLEDGMENT

text: We thank Markus Nagel and anonymous reviewers for their kind help of this work. This project is primarily supported by NSFC 61876032.

heading: A MAIN PROOFS

heading: A.1 PROOF OF THEOREM 3.1

text:
Proof. We will prove the theorem using quadratic form. Denote the weight vector shape as θ ∈ Rd, and the network output vector shape as z(n) ∈ Rm. The quadratic form of the ∆θTH(θ)∆θ can be represented by:
∆θTH(θ)∆θ = d∑ i=1 ∆θ2i ( ∂2L ∂θ2i ) + 2 d∑ i<j ∆θi∆θj ∂L ∂θiθj = d∑ i=1 d∑ j=1 ( ∆θi∆θj ∂L ∂θiθj ) , (12)
where L is the cross-entropy loss. Based on Eq. (5), we have
∂2L
∂θiθj = m∑ k,l ∂z (n) k ∂θl ∂2L ∂z (n) k z (n) l ∂z (n) l ∂θj (13)
Substituting above equation in Eq. (12), we have
∆θTH(θ)∆θ = d∑ i=1 d∑ j=1 ∆θi∆θj ( m∑ k=1 m∑ l=1 ∂z (n) k ∂θi ∂2L ∂z (n) k z (n) l ∂z (n) l ∂θj ) (14a)
= d∑ i=1 d∑ j=1 m∑ k=1 m∑ l=1
( ∆θi∆θj ∂z (n) k
∂θi
∂2L
∂z (n) k z (n) l
∂z (n) l
∂θj
) (14b)
= m∑ k=1 m∑ l=1
( ∂2L
∂z (n) k z (n) l )( d∑ i=1 ∆θi ∂z (n) k ∂θi ) d∑ j=1 ∆θj ∂z (n) k ∂θj  (14c) = (∆θJ [ z(n)
θ
] )TH(z (n))(∆θJ [ z(n)
θ
] ), (14d)
where we define the J[xy ] is the Jacobian matrix of x w.r.t. y. To this end, we use the first-order Taylor expansion as we did in Eq. (8) to approximate the change in network output, i.e.,
∆z(n) ≈ ∆θJ [ z(n)
θ
] (15)
Therefore, the final objective is transformed to ∆z(n),TH(z (n))∆z(n).

heading: B EXPERIMENTS

heading: B.1 EFFECT OF THE FIRST AND THE LAST LAYER

text:
Many papers claim that the first and the last layer can have a huge impact on the final accuracy. In this section, we investigate this phenomenon as well as the impact of the first and the last layer on hardware performances. We test ResNet-18, MobileNetV2 as well as RegNet-600MF. Our observations include:
1. In terms of accuracy, the 4-bit quantization is essentially good, both of these two layers won’t drop too much accuracy (with 0.2%). But in 2-bit quantization, the last fully connected layer is far more important than the first layer. We also observe that the first layer in MobileNetV2 and RegNet (3×3 kernels, 32 channels) is slightly more sensitive than that in ResNet-18 (7×7 kernel, 64 channels). 2. In terms of model size, the first layer merely has a minor impact because the input images only have 3 channels, while the last layer contains many weight parameters and greatly affects the memory footprint. We should point out that just the model size in the first layer is low doesn’t mean the memory burden is low, because the input image will cost huge memory space. 3. In terms of latency, the situation depends on the architecture. For example, in ResNet-18 the first layer has a huge impact on the latency, while in MobileNetV2 and RegNet-600MF the last layer is more important than the first layer. This is because the latency is affected by multiple factors, such as the input size of the featuremap, the FLOPs, and the weight memory size. The arithmetic intensity (OPs/byte) greatly affects the latency. We find that the operations with high arithmetic intensity, i.e., shallow layers in the network, generate a less latency gap between different bitwidths.
In conclusion, we find that keeping the first and the last layer 8-bit is unnecessary. Especially in ResNet-18, we find that setting all layers to 4-bit results in 53.3 ms latency and is faster than the 59.8 ms in 2-bit quantization (with first and last layer 8-bit), but the accuracy is even 4% higher. Such phenomenon indicates the potential power of the mixed precision.

heading: B.2 EFFECT OF DATA

text: We evaluated the influence of the size of calibration dataset and the source of the data on ResNet-18. We test different numbers of input data point and find that the improvement in 4-bit quantization is trivial. Yet in 2-bit quantization we can see that the accuracy increases 5% when #data points increase. We also test the distilled data introduced in ZeroQ (Cai et al., 2020). Distilled data is learned from pretrained models’ BN statistics, i.e., x1distilled = arg minx∈R ∑n i=1((µi−µ̂i)2+(ςi− ς̂i)) where µi and ςi is the original mean and variance in BN statistics of the (i)-th layer. We find that distilled data performs good in 4-bit quantization but still has a large margin with the original ImageNet dataset in 2-bit quantization. We also find the final accuracy does not benefit much from the increase of number of distilled data, this might because the distilled data are minimized by a same objective and has low diversity.

heading: B.3 MOBILE CPU LATENCY GUARANTEED MIXED PRECISION

text:
In this section, we test the mobile CPU latency guaranteed mixed precision. The latency lookup table is tested using the technique in Gong et al. (2019). We only validate it on ResNet-18 and ResNet-50 because the current low-bit General Matrix Multiply (GEMM) implementation only supports normal convolution. The results concur with Fig. 2. Below 4-bit, the mixed precision can achieve better task performance than the unified precision models. For ResNet-50, the improvement is lower than that for ResNet-18 and any other mixed precision models. We think this is because the sensitivity in ResNet-50 is not distinct and therefore the improvement brought by mixed precision is trivial.
B.4 IMPLEMENTATION

heading: B.4.1 LEARNING STRATEGIES

text:
In this work, we mainly focus on developing optimization objective rather than optimization strategies. We observe adaptive rounding performs well in post-training quantization. A brief introduction on AdaRound is given below, the detailed algorithm can be found in Nagel et al. (2020).
Traditional quantization function is performed by rounding-to-nearest operation: ŵ = s × clip(bw/se, n, p). AdaRound optimizes the rounding policy in post-training quantization. Specifically, all weights are initially rounded by floor operation, and a learnable variable v determines the final rounding result to be flooring or ceiling. A sigmoid-like function σ(·) keeps the learnable variable v moving between 0 and 1 and a regularization term assures the σ(v) can converged to either 0 or 1. The formulation is given by
ŵ = s× clip ( bw s c+ σ(v), n, p ) (16)
The minimization problem together with the regularization is given by
arg min v
E [ ∆z(`),Tdiag(( ∂L
∂z (`) 1
)2, . . . , ( ∂L
∂z (`) a
)2)∆z(`) ] + λ
∑ i ( 1− |2σ(vi)− 1|β ) , (17)
where progressively decreasing β in the calibration ensures the σ(v) converged to binary values. The activations cannot be quantized using adaptive rounding because they vary with different input data points. Thus, we can only adjust its quantization step size Esser et al. (2020). Denoting the quadratic loss in above equation as Lq , the gradients of step size is given by
∂Lq ∂s =  ∂Lq ∂x̂
if x > n
∂Lq ∂x̂
( x̂
s − x s
) if 0 ≤ x < α
0 if x ≤ 0
, (18)
where all step size in the block will be optimized.

heading: B.4.2 GENETIC ALGORITHM FOR MIXED PRECISION

text:
Algorithm 2: Genetic algorithm Input: Random initialized population P0 with population size S; Iteration T , mutation
probability p; Hardware performance threshold δ; Hardware measurement function H(·)
TopK = ∅ ; for all t = 1, 2, . . . , T -th iteration do
Evaluate fitness value (Eq. (11)) for each individual ; Update and sort TopK based on fitness function; repeat
New bitwidth configuration by crossover ccross = Crossover(TopK); Pcrossover := Pcrossover + ccross if H(ccross) < δ;
until Size of Pcrossover equal to S/2; repeat
New bitwidth configuration by mutation cmutate = Mutate(TopK,probability = p); Pmutate := Pmutate + cmutate if H(cmutate) < δ;
until Size of Pmutate equal to S/2; Pt = Pcrossover ∪ Pmutate; Pmutate = ∅, Pcrossover = ∅;
Get the best fitted entry and then do the overall block reconstruction (cf. algorithm 1); return mixed precision model

heading: B.4.3 LATENCY ACQUISITION

text:
We test the latency of quantized neural networks on a self-developed simulator of a precisionvariable accelerator for NN. The basic architecture of this accelerator is inspired by typical systolicmatrix multiplication. The accelerator supports the per-channel quantization parameter. The precision of each layer of a NN is highly configurable in this accelerator, supporting 9 types of precision combination: activation: 2-, 4-, 8-bit × weight: 2-, 4-, 8-bit, see Fig. 5a. With the support of scalable function-unit (Sharma et al., 2018), the peak performance of the accelerator is able to achieve corresponding linear improvement as the precision decreases. For example, the peak performance of this accelerator is 256 GMAC/s in 8-bit × 8-bit precision, and it scales to 512 GMAC/s in 8- bit × 4-bit precision and 4 TMAC/s in 2-bit × 2-bit precision. Although this accelerator provides considerable computation resources especially in low precision, the parallelism of the specific layer (like depthwise convolution) and the bandwidth of on-chip buffer is limited. Consequently, actual performance may not scale accurately along with the peak performance, and the final performance differs according to the size and type of layers. The simulator performs cycle-accurate simulation and evaluation for a given NN executed on the accelerator, so we can get an equivalent evaluation by using this simulator. The simulator is available in the provided source codes.
For the acquisition of mobile ARM CPU latency, we adopt the redesigned low-bit GEMM implementation in Han et al. (2020). Fig. 5b shows a brief overview of the low-bit GEMM implementation. Since there is no instruction supporting the bit-width below 8 on ARM architecture, we can
not get a higher computation efficiency for extremely low-bit such as 2-bit and 4-bit. But we can acquire a better memory access efficiency. The primary speedup comes from the reduction of data movement. Specifically, we can conduct more times of addition in the same 8-bit register before we have to move it to a 16-bit register to avoid overflow. The lower bit-width is used, the less movement is needed. Together with the optimized data packing and data padding, we can run mixed precision quantization on Raspberry Pi 3B, which has a 1.2 GHz 64-bit quad-core ARM Cortex-A53. Note that this implementation is not optimized for depthwise separable or group convolution, therefore we only verify the latency on ResNets.
B.4.4 IMPLEMENTATION DETAILS
The ImageNet dataset consists of 1.2M training images and 50K test images. We follows standard pre-process (He et al., 2016) to get 1024 224×224 input images as the calibration dataset. We fold the batch normalization layer into convolution and freeze the BN statistics before post-training quantization. We use Adam optimizer (Kingma & Ba, 2014) to learn the weight rounding and activation range to reconstruct the block output. Note that some layers are not a component of any block, such as the first convolutional layer and the last fully connected layer and the last convolutional layer in the MobileNetV2. These layers use naive layer reconstruction. The batch size of learning is set to 32 and each block will be optimized for 2 × 104 iterations. The learning rate is set to 10−3 during the whole learning process. Other hyper-parameters such as the temperature β are kept the same with Nagel et al. (2020). For activation step size, we also use Adam optimizer and set the learning rate to 4e-5. Note that we do not implement the gradient scale as introduced in the original paper (Esser et al., 2020). After reconstruction, we will store the sensitivity measured on the calibration dataset. Note that we will store intra-block sensitivity in 2-bit quantization. The sensitivity, as well as hardware performances for each layer, will be stored in a lookup table. When calculating the fitness value and determining the hardware performances in a genetic algorithm, we will check the lookup table. For genetic algorithm, we set the population size to 50 and evolve 100 iterations to obtain the best individual. The first population is initialized by Gaussian distribution and we round the samples to integers in [0, 1, 2], corresponding to bit-width [2, 4, 8]. The mutation probability is set to 0.1. The genetic algorithm usually completes the evolution in only about 3 seconds.
For object detection tasks, we use 256 training images taken from the MS COCO dataset for calibration. The image resolution is set to 800 (max size 1333) for ResNet-18 and ResNet-50, while the image resolution for MobileNetV2 is set to 600 (max size 1000). Note that we only apply block reconstruction in the backbone because other parts of the architecture, such as Feature Pyramid Net, do not have the block structure. Therefore a naive layer reconstruction is applied to the rest of the network. Learning hyper-parameters are kept the same with ImageNet experiments.

title: BRECQ: PUSHING THE LIMIT OF POST-TRAINING QUANTIZATION BY BLOCK RECONSTRUCTION


summaries: This paper discussed how data properties (e.g., label noise, label imbalance, data size) affects calibration error. The author designed experiments on varying computer vision datasets (i.e., cifar10, cifar100, eurosat and iNaturalist) qualitatively: 1) calibration error for various individual classes under class-imbalance situation; 2) calibration error for different scale of label noise; 3) calibration error under non-uniform noise; 4) calibration error under various scale of dataset size; 5) Calibration error under different combinations of data augmentations. The experimental results show that poor calibration performance accompanies with large noisy label rate, large imbalance ratio and small dataset size. For the reason of small dataset size causing poor calibration error, this paper provided the theoretical proof.

summaries: This work is an empirical survey of the calibration problem with convnets. The authors use several existing benchmark datasets and create synthetic class-imbalance for datasets that are initially balanced. They then extend the well-known results on higher prediction error of minority class, to its calibration error. The work investigates several existing methods that alleviate prediction error in imbalanced datasets and examine their effect on calibration error. At last, the effect of dataset size and data augmentation on calibration error is reported. Later on, the effect of random label noise is also examined. The observations, although not surprising, have not been reported before

summaries: In this work, authors demonstrate that dataset properties can significantly affect calibration and suggest that calibration should be measured during dataset curation. In the field of applied AI to real-life problem, we face all the time decision-makings on what is the most effective strategy in the pipeline (eg. sampling, noise, labeling) and this paper present some evidence for those decisions.

abstractText: Neural networks are known to be data-hungry, and collecting large labeled datasets is often a crucial step in deep learning deployment. Researchers have studied dataset aspects such as distributional shift and labeling cost, primarily using downstream prediction accuracy for evaluation. In sensitive real-world applications such as medicine and self-driving cars, not only is the accuracy important, but also the calibration – the extent that model uncertainty reflects the actual correctness likelihood. It has recently been shown that modern neural networks are ill-calibrated. In this work, we take a complementary approach – studying how dataset properties, rather than architecture, affects calibration. For the common issue of dataset imbalance, we show that calibration varies significantly among classes, even when common strategies to mitigate class imbalance are employed. We also study the effects of label quality, showing how label noise dramatically increases calibration error. Furthermore, poor calibration can come from small dataset sizes, which we motive via results on network expressivity. Our experiments demonstrate that dataset properties can significantly affect calibration and suggest that calibration should be measured during dataset curation.

title: Implementing crowdsourcing-based relevance experimentation: an industrial perspective

venue: Information retrieval,

authors:
Peter M Attia
Aditya Grover
Norman Jin
Kristen A Severson
Todor M Markov
Yang-Hung Liao
Michael H Chen
Bryan Cheong
Nicholas Perkins
Zi Yang

title: Closed-loop optimization of fast-charging protocols for batteries with machine learning

authors:
Mariusz Bojarski
Davide Del Testa
Daniel Dworakowski
Bernhard Firner
Beat Flepp
Prasoon Goyal
Lawrence D Jackel
Mathew Monfort
Urs Muller
Jiakai Zhang

title: End to end learning for self-driving cars

venue: arXiv preprint arXiv:1604.07316,

authors:
Mateusz Buda
Atsuto Maki
Maciej A Mazurowski

title: A systematic study of the class imbalance problem in convolutional neural networks

venue: Neural Networks,

authors:
Chris Callison-Burch
Mark Dredze

title: Creating speech and language data with amazon’s mechanical turk. In Proceedings of the NAACL HLT 2010 workshop on creating speech and language data with Amazon’s

authors:
Kaidi Cao
Colin Wei
Adrien Gaidon
Nikos Arechiga
Tengyu Ma

title: Learning imbalanced datasets with label-distribution-aware margin loss

venue: In Advances in Neural Information Processing Systems,

authors:
Rich Caruana
Yin Lou
Johannes Gehrke
Paul Koch
Marc Sturm
Noemie Elhadad

title: Intelligible models for healthcare: Predicting pneumonia risk and hospital 30-day readmission

venue: In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining,

authors:
Mauro Cettolo
Jan Niehues
Sebastian Stüker
Luisa Bentivogli
Marcello Federico

title: Report on the 11th iwslt evaluation campaign, iwslt 2014

venue: In Proceedings of the International Workshop on Spoken Language Translation, Hanoi, Vietnam,

authors:
Koby Crammer
Michael Kearns
Jennifer Wortman

title: Learning from data of variable quality

authors:
Ekin D Cubuk
Barret Zoph
Dandelion Mane
Vijay Vasudevan
Quoc V Le

title: Autoaugment: Learning augmentation policies from data

venue: arXiv preprint arXiv:1805.09501,

authors:
Yin Cui
Menglin Jia
Tsung-Yi Lin
Yang Song
Serge Belongie

title: Class-balanced loss based on effective number of samples

authors:
Chuan Guo
Geoff Pleiss
Yu Sun
Kilian Q Weinberger

title: On calibration of modern neural networks

venue: arXiv preprint arXiv:1706.04599,

authors:
Bo Han
Jiangchao Yao
Gang Niu
Mingyuan Zhou
Ivor Tsang
Ya Zhang
Masashi Sugiyama

title: Masking: A new perspective of noisy supervision

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

authors:
Patrick Helber
Benjamin Bischke
Andreas Dengel
Damian Borth

title: Eurosat: A novel dataset and deep learning benchmark for land use and land cover classification

venue: IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing,

authors:
Joel Hestness
Sharan Narang
Newsha Ardalani
Gregory Diamos
Heewoo Jun
Hassan Kianinejad
Md Patwary
Mostofa Ali
Yang Yang
Yanqi Zhou

title: Deep learning scaling is predictable, empirically

venue: arXiv preprint arXiv:1712.00409,

authors:
Chien-Ju Ho
Shahin Jabbari
Jennifer Wortman Vaughan

title: Adaptive task assignment for crowdsourced classification

venue: In International Conference on Machine Learning,

authors:
Gao Huang
Zhuang Liu
Kilian Q Weinberger

title: Densely connected convolutional networks. corr abs/1608.06993 (2016)

venue: arXiv preprint arXiv:1608.06993,

authors:
Nathalie Japkowicz
Shaju Stephen

title: The class imbalance problem: A systematic study

venue: Intelligent data analysis,

authors:
David R Karger
Sewoong Oh
Devavrat Shah

title: Iterative learning for reliable crowdsourcing systems. In Advances in neural information processing

authors:
Melissa G Keith
Louis Tay
Peter D Harms

title: Systems perspective of amazon mechanical turk for organizational research: Review and recommendations

venue: Frontiers in Psychology,

authors:
Alex Kendall
Roberto Cipolla

title: Modelling uncertainty in deep learning for camera relocalization. corr abs/1509.05909

authors:
Ashish Khetan
Sewoong Oh

title: Achieving budget-optimality with adaptive schemes in crowdsourcing

authors:
Ranjay Krishna
Yuke Zhu
Oliver Groth
Justin Johnson
Kenji Hata
Joshua Kravitz
Stephanie Chen
Yannis Kalantidis
Li-Jia Li
David A Shamma

title: Visual genome: Connecting language and vision using crowdsourced dense image annotations

venue: International journal of computer vision,

authors:
Alex Krizhevsky
Geoff Hinton

title: Convolutional deep belief networks on cifar-10

venue: Unpublished manuscript,

authors:
Volodymyr Kuleshov
Nathan Fenner
Stefano Ermon

title: Accurate uncertainties for deep learning using calibrated regression

venue: arXiv preprint arXiv:1807.00263,

authors:
Yann LeCun
Léon Bottou
Yoshua Bengio
Patrick Haffner

title: Gradient-based learning applied to document recognition

venue: Proceedings of the IEEE,

title: Focal loss for dense object detection

authors:
John Miller
Karl Krauth
Benjamin Recht
Ludwig Schmidt

title: The effect of natural distribution shift on question answering models

venue: arXiv preprint arXiv:2004.14444,

authors:
Adam S Miner
Albert Haque
Jason A Fries
Scott L Fleming
Denise E Wilfley
G Terence Wilson
Arnold Milstein
Dan Jurafsky
Bruce A Arnow
W Stewart Agras

title: Assessing the accuracy of automatic speech recognition for psychotherapy

venue: npj Digital Medicine,

authors:
Mahdi Pakdaman Naeini
Gregory F Cooper
Milos Hauskrecht

title: Obtaining well calibrated probabilities using bayesian binning

venue: In Proceedings of the... AAAI Conference on Artificial Intelligence. AAAI Conference on Artificial Intelligence,

authors:
Alexandru Niculescu-Mizil
Rich Caruana

title: Predicting good probabilities with supervised learning

venue: In Proceedings of the 22nd international conference on Machine learning,

authors:
Myle Ott
Michael Auli
David Grangier
Marc’Aurelio Ranzato

title: Analyzing uncertainty in neural machine translation

venue: arXiv preprint arXiv:1803.00047,

authors:
Myle Ott
Sergey Edunov
Alexei Baevski
Angela Fan
Sam Gross
Nathan Ng
David Grangier
Michael Auli

title: fairseq: A fast, extensible toolkit for sequence modeling

venue: In Proceedings of NAACL-HLT 2019: Demonstrations,

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:
Genevieve Patterson
James Hays

title: Sun attribute database: Discovering, annotating, and recognizing scene attributes

venue: In 2012 IEEE Conference on Computer Vision and Pattern Recognition,

authors:
Geoff Pleiss
Manish Raghavan
Felix Wu
Jon Kleinberg
Kilian Q Weinberger

title: On fairness and calibration

authors:
Benjamin Recht
Rebecca Roelofs
Ludwig Schmidt
Vaishaal Shankar

title: Do imagenet classifiers generalize to imagenet

venue: arXiv preprint arXiv:1902.10811,

authors:
Ye Ren
PN Suganthan
N Srikanth

title: Ensemble methods for wind and solar power forecasting—a state-of-the-art review

venue: Renewable and Sustainable Energy Reviews,

authors:
Marco Tulio Ribeiro
Sameer Singh
Carlos Guestrin

title: why should i trust you?” explaining the predictions of any classifier

venue: In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining,

authors:
Hao Su
Jia Deng
Li Fei-Fei

title: Crowdsourcing annotations for visual object detection

venue: In Workshops at the Twenty-Sixth AAAI Conference on Artificial Intelligence,

authors:
Santosh K Suram
Yexiang Xue
Junwen Bai
Ronan Le Bras
Brendan Rappazzo
Richard Bernstein
Johan Bjorck
Lan Zhou
R Bruce van Dover
Carla P Gomes

title: Automated phase mapping with agilefd and its application to light absorber discovery in the v–mn–nb oxide system

venue: ACS combinatorial science,

authors:
Christian Szegedy
Vincent Vanhoucke
Sergey Ioffe
Jon Shlens
Zbigniew Wojna

title: Rethinking the inception architecture for computer vision

authors:
Bart Thomee
David A Shamma
Gerald Friedland
Benjamin Elizalde
Karl Ni
Douglas Poland
Damian Borth
Li-Jia Li

title: Yfcc100m: The new data in multimedia research

venue: Communications of the ACM,

authors:
Dimitris Tsipras
Shibani Santurkar
Logan Engstrom
Andrew Ilyas
Aleksander Madry

title: From imagenet to image classification: Contextualizing progress on benchmarks

venue: arXiv preprint arXiv:2005.11295,

authors:
Grant Van Horn
Oisin Mac Aodha
Yang Song
Yin Cui
Chen Sun
Alex Shepard
Hartwig Adam
Pietro Perona
Serge Belongie

title: The inaturalist species classification and detection dataset

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

title: Attention is all you need

venue: In Advances in neural information processing systems,

authors:
Yu-Xiong Wang
Deva Ramanan
Martial Hebert

title: Learning to model the tail

authors:
Chulhee Yun
Suvrit Sra
Ali Jadbabaie

title: Small relu networks are powerful memorizers: a tight analysis of memorization capacity

authors:
Bianca Zadrozny
Charles Elkan

title: Obtaining calibrated probability estimates from decision trees and naive bayesian classifiers

venue: In Icml,

authors:
Chiyuan Zhang
Samy Bengio
Moritz Hardt
Benjamin Recht
Oriol Vinyals

title: Understanding deep learning requires rethinking generalization

venue: arXiv preprint arXiv:1611.03530,

authors:
Yuchen Zhang
Xi Chen
Dengyong Zhou
Michael I Jordan

title: Spectral methods meet em: A provably optimal algorithm for crowdsourcing

authors:
Yudian Zheng
Guoliang Li
Yuanbing Li
Caihua Shan
Reynold Cheng

title: Truth inference in crowdsourcing: Is the problem solved

venue: Proceedings of the VLDB Endowment,

heading: 1 INTRODUCTION

text:
Neural networks often require large amounts of labeled data to perform well, making data curation a crucial but costly aspect of deployment. Thus, researchers have studied dataset properties such as distributional shift (Miller et al., 2020) and the bias in crowd-sourced computer vision datasets (Tsipras et al., 2020) among others. Often, the evaluation criteria in such studies is downstream prediction accuracy. However, neural networks are increasingly deployed in sensitive real-world applications such as medicine (Caruana et al., 2015), self-driving cars (Bojarski et al., 2016), and scientific analysis (Attia et al., 2020), where not only accuracy matters but also calibration. Calibration is the extent to which model certainty reflects the actual correctness likelihood. Calibration can be important when costs of false positives and false negatives are asymmetric, e.g., for a deadly disease with cheap treatment, doctors might initiate treatment when the probability of being sick exceeds 10%. Beyond simple classification, calibration can be important for beam-search in NLP (Ott et al., 2018) and algorithmic fairness (Pleiss et al., 2017). Calibration in machine learning has been studied by e.g Zadrozny & Elkan (2001); Naeini et al. (2015). Niculescu-Mizil & Caruana (2005) have shown that small scale neural networks can yield well-calibrated predictions. However, it has recently been observed by (Guo et al., 2017) that modern neural networks are ill-calibrated, whereas the now primitive Lenet (LeCun et al., 1998) achieves good calibration.
In this work, we take a complementary approach; instead of focusing on network architecture, we study how calibration is influenced by dataset properties. We primarily focus on computer vision and perform extensive experiments across common benchmarks and more exotic datasets such as satellite images (the eurosat dataset (Helber et al., 2019)) and species detection (the iNaturalist dataset (Van Horn et al., 2018)). We consistently find that dataset properties can significantly affect calibration, causing effects comparable to network architecture. For example, we consider the ubiquitous problem of class imbalanced datasets, a common issue in practice (Van Horn et al., 2018; Krishna et al., 2017; Thomee et al., 2016). For such datasets, the miscalibration is not uniform but instead varies across the different classes. This problem persists even when common strategies to mitigate class imbalanced are employed. Another practical concern is generating high-quality labels via e.g. crowdsourcing (Karger et al., 2011). We demonstrate how labeling quality affects calibration, with noisier labels resulting in worse calibration. Additionally, we show that just the size of the dataset
has a strong effect on calibration. This also holds when one artificially increases the dataset size by data augmentation. We motivate our findings by considering the geometry of the cross-entropy loss and utilizing recent results on network expressivity (Yun et al., 2019). If the dataset is sufficiently small compared to the number of parameters, we argue that the lack of minimizer for the cross-entropy loss biases the network to high confidence and poor calibration. Our results highlight an underappreciated aspect of calibration and suggest that for sensitive applications, one should measure calibration during dataset curation.

heading: 2 BACKGROUND

text:
Calibration. Calibration has a traditional place in machine learning (Zadrozny & Elkan, 2001; Naeini et al., 2015). Before the advent of modern deep learning, Niculescu-Mizil & Caruana (2005) showed that neural networks can yield well-calibrated predictions for classification. However, Guo et al. (2017) showed that modern neural networks are ill-calibrated. Modern neural networks are modeled as e.g. resnet (He et al., 2016) or densenets (Huang et al., 2016). It is important to note that accuracy and calibration do not necessarily follow each other, but can move independently – modern neural networks are ill-calibrated, but still yield excellent accuracy. Beyond image classification, the importance of calibration in NLP has further been studied by Ott et al. (2018) and its relationship to fairness by Pleiss et al. (2017).
Metrics for Calibration. We let {xi} ∈ Rn×dx be a dataset of n datapoints with dx features and take {yi} to be the labels. Following Guo et al. (2017), we assume that a neural network h outputs h(xi) = (p̂i, ŷi), where ŷi is the predicted class and p̂i is the estimated probability that the prediction is correct. For evaluating calibration, we divide the interval [0, 1] into M equally sized bins and assign predictions to bins based upon p̂. Within each bin Bm we define the accuracy as acc(Bm) =
1 |Bm| ∑ i∈Bm 1(ŷi = yi). Similarly, we define the confidence as conf(Bm) = 1 |Bm| ∑ i∈Bm p̂i. For a well-calibrated model, we would expect the confidence and accuracy of each bin to be close to each other. Calibration error can be measured by their difference, evaluated on the test set. The
resulting metric is known as the expected calibration error (Naeini et al., 2015), often abbreviated as ece. Mathematically, it is defined as follows:
ece = M∑
m=1
|Bm| n ∣∣∣∣acc(Bm)− conf(Bm)∣∣∣∣ (1)

heading: 3 EXPERIMENTS

text:
Experimental setup. We consider the following computer vision datasets. Cifar10 & Cifar100 (Krizhevsky & Hinton, 2010) which contains 50,000 RGB images spanning ten or hundred classes respectively. Classes are balanced. Eurosat (Helber et al., 2019), which is a dataset of satellite images over continental Europe; there are ten balanced classes and 27,000 images in total. iNaturalist (Van Horn et al., 2018) which is a dataset for species detection. We use the FGVC6 version (FGVC6, 2019), compromising over 260,000 images and an imbalanced hierarchical class system compromising e.g., species and phylum. We perform classification at the ”class” level, resulting in nine classes. Across all datasets, we use the same architecture, Resnet50 (He et al., 2016). We use hyperparameters from the original resnet paper (He et al., 2016): cross-entropy loss optimized with SGD using a learning rate at 0.1 and decreased by a factor 0.1 after 50 % and 75 % of the training, a batch size of 128, a weight decay of 0.0001, and momentum of 0.9. For the cifar/eurosat/inaturalist, networks are trained over 62/30/331 × 103 gradient steps, corresponding to 160 epochs for each dataset. We use randomized cropping and random horizontal flipping for data augmentation, see Appendix A for data preprocessing. Experiments are repeated five times, with mean and standard deviations reported. Calibration error is measured in expected calibration error(ece) as in eq. (1), using M = 15 and evaluated on the test set.
Inbalanced dataset. A common problem in practice, not necessarily found in benchmark datasets, is class imbalance (i.e., the number of available samples varies between classes), see Van Horn et al. (2018); Krishna et al. (2017); Thomee et al. (2016). Here we study how imbalanced datasets affect
the calibration error for individual classes. Whereas the iNaturalist dataset is naturally imbalanced, the cifar and eurosat datasets are not. For these datasets, we simulate long-tailed class imbalance following Cao et al. (2019). We randomly reorder the classes from = 1 to n, and only keep a αi−1 fraction of examples for class i. Given some desired ratio ρ between the class with the most and fewest samples, one picks α such that αn−1 = ρ. Following Buda et al. (2018), we also consider a step-imbalance, where half of the classes are downsampled by a factor ρ. We consider ρ = 100 as done by e.g. Cao et al. (2019) and keep the test set balanced. For cifar/eurosat, we randomly chose what classes to subsample to eliminate class-specific properties. Since iNaturalist is already imbalanced, we keep it as it is, but note that the class-specific properties are correlated with class-specific imbalance. After this procedure, we train the DNNs as normal and give the average calibration error for individual classes. The results are shown in Figure 1. Generally, classes with fewer examples have significantly higher ECE, showing how imbalance can have a significant effect on model calibration. For the iNaturalist dataset, we have some outlier classes which is likely due to class-specific effects, e.g., the class with the most labels might be unusually hard to calibrate.
Methods for Imbalanced Datasets. As class imbalanced is a problem of practical importance, there is ample work on mitigating this issue. One common strategy is to sample the dataset unevenly when generating mini-batches, attempting to obtain a roughly balanced dataset. One can both oversample minority classes (Buda et al., 2018) and undersample the majority class (Japkowicz & Stephen, 2002). Another strategy is instead to weight the objective function to give all classes
approximately the same weight in the objective function. A common strategy is weight classes inversely proportional to their frequency (Wang et al., 2017). Recently, Cui et al. (2019) has proposed to reweight based upon the ”effective” number of samples, which is defined per a mathematical formula. We here investigate if the calibration issues of an imbalanced dataset persist when using such mitigation strategies. Thus, we consider the standard cross-entropy (original), resampling inversely proportional to the frequency (sampling), reweighting inversely proportional to the frequency (weighted), the weighting scheme of Cui et al. (2019) (CB), and the focal loss of Lin et al. (2017) (focal). Additionally we consider label smoothing (Szegedy et al., 2016) (label smooth). We construct imbalanced datasets as in the previous section. Due to limited computational resources, we only consider the three smallest datasets for these experiments. Calibration errors are given in Table 1, and we give the largest and smallest calibration error among classes and the average ratio of the two. We see that issues of imbalanced calibration errors, while sometimes improving, still persist. Standard deviations are given in Table 2 in Appendix A.
Label Quality. When collecting labels, for example via crowdsourcing, a common issue is label quality (Patterson & Hays, 2012; Su et al., 2012; Callison-Burch & Dredze, 2010). For example, workers might have poor incentives to perform well or lack the necessary skills for quality labeling. To study the effects of potentially mislabeled data, we artificially inject symmetric noise into the training set. This is done by selecting a random subset of the training set corresponding to some fixed fraction, and then shuffling the labels of this set. This setup follows conventions in label noise literature (Patrini et al., 2017; Han et al., 2018). Given these noisy labels, we train the networks and evaluate them on the original test-set (which has no noise). We consider five levels of label noise in increments of 0.1, starting at 0.0. The resulting calibration errors for various noise levels are given in Figure 2, where we see that label noise increases the calibration error across all datasets. Additionally, we consider the effects of non-uniform noise, studied by e.g. Crammer et al. (2006). For class i, we linearly increase a noise level pi from 0.0 to 0.5. Classes are randomly ordered. For each image with original class i, with probability pi we assign it to a new random class. The reassignment probability to class i is proportional to pi. Results are given in Figure 3, where noisier classes suffer from worse calibration. This underscores how label quality control in e.g. crowdsourcing (Su et al., 2012) can be not only important for accuracy, but also for calibration of downstream models.
Dataset size. The perhaps most common concern for collecting data is the dataset size, and model accuracy typically grows with this size (Hestness et al., 2017). Crowdsourcing labels and bounding boxes for images is common practice, with many researchers investigating strategies to reduce needed queries (Su et al., 2012) In practice, dataset size can be limited by costs of labeling, but also by obtaining the actual data (Suram et al., 2017). Motivated by this, we study the effect of dataset size upon the calibration error. We simply subsample the training sets of the datasets uniformly at random and thereafter train on them, comparing different sizes of the resulting dataset. We consider subsampled sizes, measured in fractions of the original size, from 1.0 to 0.2 in increments of 0.2, and also consider 0.1. The test set is not subsampled. The results of these experiments are given in Figure 4. We see that smaller datasets have substantially larger calibration errors, demonstrating the dramatic effect that dataset size can have not only on accuracy, but also on calibration error.
Augmentations. Beyond actual dataset size, it is common to artificially increase the size of the dataset by augmenting it, e.g., randomly cropping the images or slightly shifting the color balance (Cubuk et al., 2018). We have seen that the size of the dataset influences calibration, and now consider the effect of increasing the effective dataset size via augmentations. We use both randomized cropping and horizontal flipping for our training and consider removing these components while keeping other training parameters fixed. The outcome of this experiment is shown in Figure 5, and we see that removing data augmentations significantly increases the calibration error. Viewing data augmentation as a strategy of extending the training set, we again see how smaller training sets increase the calibration error, just as in Figure 4.
NLP. While we primarily focus on computer vision, we here consider experiments in NLP. Language models often generate text via beam-search, and it has been observed that calibration is important for this process (Ott et al., 2018). Here we investigate the effect of dataset size on calibration in NLP. We considering translation of the IWSLT’14 German to English dataset (Cettolo et al., 2014) using transformer architectures (Vaswani et al., 2017) with code and default hyperparameters from the publicly available fairseq codebase (Ott et al., 2019). As before, we simply subsample the training set uniformly at random for variable sizes and train the transformer with all other training parameters fixed. Figure 6 shows how the mean calibration error, with standard deviations as error bars, varies during training. Again we see how the dataset size influences the calibration. It is natural to guess that there might be word-level calibration issues too, e.g., rare words might have worse calibration.

heading: 4 THEORETICAL MOTIVATION

text:
Figure 4 and Figure 5 show that the size of the dataset affects calibration, with smaller datasets resulting in worse calibration. To explain this, let us consider the cross-entropy loss. We will let lij denote the logit for image i and class j. Furthermore, let ci be the index of the correct class for image i. The soft-max cross-entropy loss function is then defined as
` = ∑ i `i = − ∑ i log exp(lici)∑ j exp(lij) = − ∑ i ( lici + log (∑ j exp(lij) ))
(2)
We note that this loss function decreases monotonically as the logit lici increases. This implies that there is no global minimizer, but instead that if the other logits are fixed, we have `i → 0 as lici →∞. The logit tending to infinity implies that the confidence of the prediction tends to 1. The lack of minimizer for soft-max cross-entropy is in stark contrast with e.g. label smoothing, which penalizes large confidence, see Figure 7. Let us imagine that the network has infinite capacity. If we optimize it for a sufficient amount of time, we would expect ` to tend to zero, which implies that the logits tend to infinity. This corresponds to the confidence on the training set tending to 100%, which most likely implies overconfidence and poor calibration. We can formalize this observation, but we first need to state some assumptions.
Assumption 1 Let {xi} ∈ Rn×dx be a dataset of n datapoints with dx features each. Let {yi} ∈ {0, 1}n×c be a one-hot label encoding that assigns each image one out of c classes, where c is a constant. We assume that all datapoints {xi} are distinct, i.e. xi 6= xi,∀i 6= j.
Under such assumptions, recent results in network expressivity say that one can essentially memorize a training set (Yun et al., 2019) if the width is at least of order O( √ n). In an idealized setting, where we optimize the function without computational considerations, such expressivity means that the loss function can be optimized towards its minimizer 0. This means train set confidence growing to 100%, likely translating to poor calibration. We formalize this line of argument in Theorem 1.
Theorem 1 Let Assumption 1 hold. Let f be a Relu networks with four or more layers and with width at least Ω( √ n) and parameters w. Let ` be equal to the loss function in eq. (2). Then (i) minw `(f(w)) no global minima; (ii) the confidence tends to 1 as `→ 0.
The formal proof is given in Appendix B, we here provide some intuition. To prove (i) and (ii), it suffices that the network can fit the training set with 1.0 accuracy. This is typically the condition in practice (Zhang et al., 2016), and whereas we consider an idealized argument without computation costs, the conclusions agree with our experimental results. For the sake of contradiction, let us assume that we are in a global minima with parameters w and 100% accuracy. Now consider `i when we scale the final layer by (1 + α) for α > 0. The network output is then (1 + α)lij , and `i is − log ( exp((1 + α)lici)/ ∑ j exp((1 + α)lij) = log(1 + ∑ j 6=i exp ( (1 + α)(lij − lici) ) . The fact that we have perfect train accuracy means that (lij − lici) < 0 ∀j 6= ci. Thus, the loss must shrink, as ∑ j 6=i exp ( (1 + α)(lij − lici) ) decreases with α and as log is monotone. By contradiction, we are not in such a global minima. The results of Yun et al. (2019) say that we can always find weights which achieves perfect accuracy using O( √ n) parameters, and thus that there are no issues with fitting that dataset that prevents the loss from tending to 0. Thus, if the dataset is small compared to the number of parameters, we expect overconfidence and poor calibration. This conclusion agrees with observations of Guo et al. (2017), who show that depth and width increases miscalibration.

heading: 5 RELATED WORK

text:
There is much recent work on how datasets influence the behavior of neural networks. Tsipras et al. (2020) shows how the process used to collect labels for imagenet can introduce bias into the resulting dataset. Miller et al. (2020) studies how the shift between different datasets can influence the performance of question and answering systems. Recht et al. (2019) construct new test sets for imagenet and cifar10, and observe differences in generalization compared to the original test sets. Imbalanced datasets is a common issue when applying machine learning in practice (Van Horn et al., 2018; Krishna et al., 2017; Thomee et al., 2016), and researcher often describe the ”heavytail” of class labels (Cui et al., 2019). Traditional work on class imbalance includes Japkowicz & Stephen (2002) which investigates different sampling strategies, applicable to most machine learning models. For models of empirical risk minimization, one can instead reweight samples. A relatively recent reweighting scheme is proposed by Cui et al. (2019), where one uses the effective number of samples, which can be calculated from a simple formula.
For generating datasets, a common strategy is to employ crowdsourcing, where one lets ordinary people assign labels in a large-scale automated fashion, commonly via Amazon’s Mechanical Turk system (Keith et al., 2017). Typical applications of crowdsourcing include analyzing images and providing bounding boxes (Patterson & Hays, 2012; Su et al., 2012), providing linguistic annotations for natural language (Callison-Burch & Dredze, 2010), or evaluating the relevance of search engines results (Alonso, 2013). Another application is machine learning debugging Ribeiro et al. (2016). The idea of eliciting and aggregating crowdsourced labels efficiently has inspired much algorithmic work (Khetan & Oh, 2016; Zhang et al., 2014). Common issues include finding tasks that result in high-quality labels, dealing with inconsistent labels (Karger et al., 2011; Zheng et al., 2017) and heterogenous workers (Ho et al., 2013).
Calibration in machine learning has been studied for a long time (Zadrozny & Elkan, 2001; Naeini et al., 2015) due to its practical implications. For neural networks, Caruana et al. (2015) demonstrated that shallow neural networks can yield well-calibrated predictions on classification tasks. In contrast, Guo et al. (2017) show how modern neural networks are ill-calibrated, with width and depth resulting in worse calibration scores, and investigate mitigation strategies. Neural network calibration has implications in NLP (Ott et al., 2018), fairness (Pleiss et al., 2017) and reinforcement learning (Kuleshov et al., 2018). For applications such as medicine (Miner et al., 2020), meteorology (Ren et al., 2015) and autonomous vehicles (Bojarski et al., 2016) it can be important for performance. Reliable uncertainty estimates also allow one to integrate DNNS with other probabilistic models, incorporating e.g. camera information (Kendall & Cipolla, 2015).

heading: 6 CONCLUSIONS

text: We have investigated the effects that datasets can have on network calibration. By generating label noise and class imbalance synthetically, we show how calibration error increases with label noise and few samples. We also study how calibration changes with dataset size. Our work points towards the importance of high-quality dataset curation for generating well-calibrated predictions, and highlight issues that are relevant in high-stakes applications such as autonomous vehicles and medical applications. These calibration issues can potentially be mitigated both at dataset curation time and training time; we defer such studies to future work. A practical takeaway from this work is that for sensitive applications, one should evaluate calibration when collecting datasets.

heading: A APPENDIX

text: Data Preprocessing. For the cifar10 and cifar100 datasets, we use the original dataset size of 32- by-32 pixels. Cropping is performed by first padding with 4 pixels on each side, and thereafter performing a random 32-by-32 crop. For the eurosat dataset, the images are subsampled to 32-by32 pixels. Since the eurosat dataset does not have a dedicated train/test split, we split it ourselves, using a fixed random tenth of the dataset for testing across all experiments. Random cropping is performed as for cifar. For the inaturalist dataset, the images are resized into 64-by-64 images, and we pad by 8 pixels on each side before extracting a random 64-by-64 crop.

heading: B PROOF

text:
The results of Yun et al. (2019) mean that under Assumptions 1, there exists a four-layer Relu network with Ω( √ n) parameters that can memorize the dataset, perfectly matching the one-hot encoding of the labels. For details, we refer to Yun et al. (2019).
Proof Sketch for Theorem 1. We start with part (i). Assume for contradiction that we are in a global minima with loss `0 and perfect accuracy. Now, consider `i when we scale the final layer by (1 +α) for α > 0. The network output is then (1 + α)lkj , and `i is − log ( exp((1 + α)lici)/ ∑ j exp((1 +
α)lij) = log(1+ ∑ j 6=i exp ( (1+α)(lij− lici) ) . The fact that we have perfect train accuracy means
that (lij − lici) < 0 ∀j 6= ci. Thus the loss must shrink, as ∑ j 6=i exp ( (1 +α)(lij − lici) ) decreases with α and as log is monotone. This contradicts us being in such a global minima. If we do not have perfect accuracy, there must be some example k such that `k must be larger than log 2 (since there is another class with larger logit). Results of Yun et al. (2019) says that we can find network with perfect accuracy and thereafter scale the weight to less than log 2n . (ii). The confidence for a single example is exp(lici )∑
j exp(lj) = exp(−`i). We have noted how ` → 0, since ` =
∑ i `i we have `i → 0.
This implies that exp(−`i)→ 1 which means that the confidence approaches 1.