summaries: This paper carefully observes the behavior of weight magnitudes during training, finding the is a stage of saturation that is closely related to the winning lottery tickets drawing. Based on this observation the authors hypothesize that we can draw lottery tickets early but too early pruning can irreversibly hurt the learning capability for complex pattern. To remedy this and draw the tickets as soon as possible, the authors propose to adopt gradual pruning, which 1) can start early without hurting the learning capability too much; 2) avoid computation-heavy iterative pruning in previous works.

summaries: The paper is dedicated to conducting an in-depth investigation of the structure of winning lottery tickets. The author provides supporting evidence for the structure of the early winning tickets: 1) lottery tickets emerge when the weight magnitude of a model saturates with SGD optimization. 2) pruning before model saturation may result in accuracy degradation. In the experiment part, they employ the memorization capacity analysis and discover the early wining tickets without expensive iterative pruning. The author also conducts extensive experiments with various ResNet architectures on both CIFAR 10 and ImageNet, achieving state-of-the-art results with only 1/5 of the total epochs for iterative pruning.

summaries: This paper attempts an in depth study of the lottery ticket hypothesis. The lottery ticket hypothesis holds that sparse sub-networks exist inside dense large models and that the sparse sub-networks achieve at least as good an accuracy as the underlying large model. These sub-networks are discovered by training and iteratively pruning the dense model. This paper investigates the epoch at which pruning should occur as well as the epoch at which weights should be rewound when retraining. Then, the authors conduct experiments with different pruning strategies (one-shot vs. gradual) in an attempt to find such sparse models (or "winning tickets") earlier than they otherwise would have been found.

abstractText: The recent success of the lottery ticket hypothesis by Frankle & Carbin (2018) suggests that small, sparsified neural networks can be trained as long as the network is initialized properly. Several followup discussions on the initialization of the sparsified model have discovered interesting characteristics such as the necessity of rewinding (Frankle et al. (2019)), importance of sign of the initial weights (Zhou et al. (2019)), and the transferability of the winning lottery tickets (S. Morcos et al. (2019)). In contrast, another essential aspect of the winning ticket, structure of the sparsified model, has been little discussed. To find the lottery ticket, unfortunately, all the prior work still relies on computationally expensive iterative pruning. In this work, we conduct an in-depth investigation of the structure of winning lottery tickets. Interestingly, we discover that there exist many lottery tickets that can achieve equally good accuracy much before the regular training schedule even finishes. We provide insights into the structure of these early winning tickets with supporting evidence. 1) Under stochastic gradient descent optimization, lottery ticket emerges when weight magnitude of a model saturates; 2) Pruning before the saturation of a model causes the loss of capability in learning complex patterns, resulting in the accuracy degradation. We employ the memorization capacity analysis to quantitatively confirm it, and further explain why gradual pruning can achieve better accuracy over the one-shot pruning. Based on these insights, we discover the early winning tickets for various ResNet architectures on both CIFAR10 and ImageNet, achieving state-of-the-art accuracy at a high pruning rate without expensive iterative pruning. In the case of ResNet50 on ImageNet, this comes to the winning ticket of 75.31% Top-1 accuracy at 80% pruning rate in only 22% of the total epochs for iterative pruning.

authors:
Yoonho Boo
Sungho Shin
Wonyong Sung

title: Memorization capacity of deep neural networks under parameter quantization

venue: IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP),

authors:
Yann Le Cun
John S. Denker
Sara A. Solla

title: Optimal brain damage

venue: In Advances in Neural Information Processing Systems,

authors:
Felix Draxler
Kambis Veschgini
Manfred Salmhofer
Fred A Hamprecht

title: Essentially no barriers in neural network energy landscape

venue: arXiv preprint arXiv:1803.00885,

authors:
Jonathan Frankle
Michael Carbin

title: The lottery ticket hypothesis: Finding sparse, trainable neural networks

venue: arXiv preprint arXiv:1803.03635,

authors:
Jonathan Frankle
Gintare Karolina Dziugaite
Daniel M Roy
Michael Carbin

title: Stabilizing the lottery ticket hypothesis

venue: arXiv preprint arXiv:1903.01611,

authors:
Song Han
Jeff Pool
John Tran
William J. Dally

title: Learning both Weights and Connections for Efficient Neural Networks

venue: arXiv e-prints, art

authors:
Namhoon Lee
Thalaiyasingam Ajanthan
Philip H.S. Torr

title: SNIP: Single-shot Network Pruning based on Connection Sensitivity

authors:
Hao Li
Asim Kadav
Igor Durdanovic
Hanan Samet
Hans Peter Graf

title: Pruning filters for efficient convnets

authors:
Yuanzhi Li
Colin Wei
Tengyu Ma

title: Towards explaining the regularization effect of initial large learning rate in training neural networks

authors:
Zhuang Liu
Jianguo Li
Zhiqiang Shen
Gao Huang
Shoumeng Yan
Changshui Zhang

title: Learning Efficient Convolutional Networks Through Network Slimming

venue: In The IEEE International Conference on Computer Vision (ICCV),

authors:
Zhuang Liu
Mingjie Sun
Tinghui Zhou
Gao Huang
Trevor Darrell

title: Rethinking the Value of Network Pruning

authors:
Huizi Mao
Song Han
Jeff Pool
Wenshuo Li
Xingyu Liu
Yu Wang
William J Dally

title: Exploring the Granularity of Sparsity in Convolutional Neural Networks

venue: In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR) Workshops,

authors:
Pavlo Molchanov
Arun Mallya
Stephen Tyree
Iuri Frosio
Jan Kautz

title: Importance estimation for neural network pruning

authors:
Ari S. Morcos
Haonan Yu
Michela Paganini
Yuandong Tian

title: One ticket to win them all: generalizing lottery ticket initializations across datasets and optimizers

authors:
Wei Wen
Chunpeng Wu
Yandan Wang
Yiran Chen
Hai Li

title: Learning Structured Sparsity in Deep Neural Networks

venue: In NIPS,

authors:
Hattie Zhou
Janice Lan
Rosanne Liu
Jason Yosinki

title: Deconstructing lottery tickets: Zeros, signs, and the supermask

venue: arXiv preprint arXiv:1905.01067v2,

authors:
Michael Zhu
Suyog Gupta

title: To prune, or not to prune: exploring the efficacy of pruning for model compression

venue: arXiv preprint arXiv:1710.01878,

heading: 1 INTRODUCTION

text:
Deep Neural Networks (DNNs) achieve superior accuracy in a wide spectrum of applications through the use of very large and deep models (Goodfellow et al. (2016)). These high-capacity but complex models, however, pose a tremendous challenge for their deployment, particularly in resource-constrained edge environments. Over the years, many techniques have been developed to compress the models to a compact counterpart to alleviate the computational costs. Among these techniques, pruning less important parameters to obtain a compact sub-network has emerged to be a popular and efficient approach (Cun et al. (1990); Han et al. (2015)). In search of these sub-networks, new intuitions are also built up for understanding the DNN working mechanism, one example of which is the recently proposed "lottery ticket hypothesis" by Frankle & Carbin (2018).
The lottery ticket hypothesis states that, once a sub-network is found to match the accuracy of the original neural network, the sub-network (i.e., lottery ticket) together with its initialized weights can be trained in isolation and still achieve accuracy comparable to the original network within a similar number of iterations. This conjecture intrigues discussions on a series of topics, such as the importance of initialization scheme (Liu et al. (2018), Zhou et al. (2019)), the role of over-parameterization in training (Frankle et al. (2019)) and even the transferability of the "winning ticket" (S. Morcos et al. (2019)). However, all these discussions start from the point that the winning ticket has been obtained after painfully long iterative pruning procedures, which often take up to thousands of epochs. When and how a winning ticket can be found in the course of pruning procedures has not been studied; most of the prior works use a traditional way of repeated cycles of pruning and retraining, which makes such study less practical.
In this work, we provide insights to find the winning tickets early. We start with an interesting observation that there exist many lottery tickets that can achieve equally good accuracy much before the regular training schedule finishes.
This leads to our in-depth investigation of the weight magnitude; we discover that a model saturates early but not too early under stochastic gradient descent (SGD) optimization. To understand this characteristic of the winning lottery tickets, we conjecture that pruning a premature model causes the loss of capability in learning complex patterns, leading to accuracy degradation. We confirm this conjecture with the empirical evidence as well as the quantitative analysis based on the memorization capacity. Using this analysis framework, we further provide a reasoning behind the success of the gradual pruning over the one-shot pruning. Based on these insights, we identify the early winning tickets for various ResNet architectures on both CIFAR10 and ImageNet, achieving state-of-the-art accuracy at a high pruning rate without expensive iterative pruning. In the case of ResNet50 on ImageNet, this comes to the winning ticket of 75.31% Top-1 accuracy at 80% pruning rate obtained within only 22% of the total epochs for iterative pruning. This promising outcome not only sheds light on understanding the optimization behavior of the pruned models but also enables performance gain for fast training of the pruned models.

heading: 2 RELATED WORK

text:
The lottery ticket hypothesis was first proposed in Frankle & Carbin (2018) where the presence of a trainable subnetwork that achieves compelling final accuracy with the inherited initial values for the un-pruned connections is demonstrated. This paper also argued that the initial weight of the original network is essential for maintaining good accuracy when the model is sparsified. This claim has been extended to the over-parameterized neural networks on the larger datasets in Frankle et al. (2019) with the notion of "rewinding"; the authors claim that rewinding of the weights not to the initial values but to the values after a few epochs can stabilize the accuracy of the winning lottery tickets. As a follow-up work, Zhou et al. (2019) studied the critical components of the lottery tickets such as zeros, signs and the super-mask. Also, S. Morcos et al. (2019) investigated the transferability of winning tickets obtained in one dataset to the network of a similar structure for the other datasets. But none of these focused on the structure of the winning lottery tickets; it involves several repetitions of the full training schedule for iterative pruning and retraining, often taking hundreds to thousands of epochs. In this work, we demonstrate that many winning tickets can be found in the early stage of the baseline training schedule, drastically reducing the computational effort to obtain them.
Most work on the lottery ticket hypothesis, including this work, rely on magnitude-based weight pruning for identifying unimportant weights to be pruned (usually via global sorting). Such an intuitive method was first proposed in Han et al. (2015) and became popular. Afterwards, more complex pruning methodologies have been presented to improve pruning performance, such as having different pruning criteria (Li et al. (2017), Wen et al. (2016), Liu et al. (2017)) or different pruning granularity (Mao et al. (2017), Molchanov et al. (2019)). While these attempts offer insights on training pruned models, there is little discussion about the interesting interplay between the pruning criteria and the structure of a model pruned by it. In this work, we reveal that the pruned structure obtained based on the weight magnitude has tangible impact on the final accuracy, and further propose a way to quantitatively distinguish good structures for pruning.
There have been various strategies to apply pruning to the neural networks. Iterative pruning by Han et al. (2015) involves several repetition of pruning (with gradual increase of the pruning rate) and retraining. One can increase the repetition cycles arbitrarily large to achieve good accuracy at high pruning rate; Frankle & Carbin (2018) employed iterative pruning with hundreds to thousands of pruning epochs to match the baseline accuracy for the challenging neural networks. On the other hand, gradual pruning introduced by Zhu & Gupta (2017) determines the pruning rate and frequency via a polynomial equation as a function of the starting and ending epochs as well as the target pruning rate. Although it provides a systematic pruning schedule, there is lack of discussion about when to start the gradual pruning. Lastly, Lee et al. (2018) proposes a method of pruning weights at initialization. This method takes most advantage in performance since a pruned model can be obtained without any expensive retraining procedures. However, its effectiveness has not been demonstrated for the challenging neural networks on large datasets such as ImageNet. In contrast, we propose a mechanism to identify the winning lottery ticket early in the course of baseline training so that we can avoid costly iterative pruning while maintaining the baseline accuracy.

heading: 3 STRUCTURE OF EARLY WINNING TICKETS

text:
In this section, we extend the lottery ticket hypothesis by Frankle & Carbin (2018); Frankle et al. (2019) to discuss the early winning tickets. The lottery ticket hypothesis can be summarized as:
for a given network of f(x;w0 m0) with the initial weight w0 and the mask of all ones m0, there exists a winning lottery ticket mf where |mf |/|m0| = 1 − p% (p is the pruning rate) and training of f(x;wv mf ) for 0 < v f achieves test accuracy comparable to the baseline f(x;wf m0). There are two main components of a winning lottery ticket: the sparsified structure mf and the weight that initializes it, wv . In the previous work, mf has been obtained only after expensive iterative pruning. We characterize the structure of the early lottery ticket ms where s f , then propose a strategy for finding it early.

heading: 3.1 EXTENDED LOTTERY TICKET EXPLORATION

text:
Frankle et al. (2019) suggests that a lottery ticket found after a baseline training can achieve the accuracy of the baseline model if it is initialized with the weight of the baseline model after a few epochs, which is called rewinding. We extend this exploration toward different structures obtained at different epochs of the baseline training (via magnitude-based weight pruning).
Fig. 1 shows the validation accuracy after retraining of a ResNet20 model on CIFAR10 pruned at different epochs of its baseline training. The same learning rate schedule of 0.1 reduced by 10x at epoch 120 and 160 is used for both the baseline training and retraining, and the total number of epochs is 200. The rows (= v) correspond to the different rewinding epoch, whereas the columns (= s) correspond to the different epoch that we apply one-shot pruning (pruning rate= 80%). For example, the validation accuracy along the lottery ticket configurations of (s = 200, v = 0 ∼ 200) resembles the phenomena of "rewinding" observed in Frankle et al. (2019).
Interestingly, Fig. 1 further demonstrates that the winning tickets emerge at much earlier epochs of the baseline training; the lottery ticket configurations of (s ≥ 100, v ≥ 5) achieve almost the same accuracy as the accuracy of (s = 200, v = 200). The accuracy then gradually decreases as s ≤ 80. This result implies two important aspects: 1) a winning ticket can be found in the middle of the baseline training so that one can avoid expensive iterative pruning used in the prior work, and 2) the winning ticket, however, does not emerge arbitrarily early in the process of training. In the following sections, we investigate the characteristics of these early winning tickets. In particular, we focus on their structure, as the weight initialization is not the major factor provided a proper rewinding.

heading: 3.2 ANALYSIS ON WEIGHT MAGNITUDE

text:
As the first step of understanding the characteristics of the early winning tickets, we focus on the important quantity of pruning, weight magnitude. At pruning, we determine the structure of the sparsified model based on the rank of the
weight magnitude (via global sorting). Therefore, the change in the weight magnitude during training has large impact on the lottery ticket structure.
In Fig. 2a, we measure the standard deviation of weight (Wstd) for each layer in the course of training ResNet20 on CIFAR10 (note: the mean of weight is typically near zero). The same learning rate schedule is used as above. The first thing to note is that the change in Wstd has strong correlation with the learning rate change. In particular, different layers show different rate of change in Wstd when the learning rate is 0.1, but from the second learning rate (after epoch 120), all the weights follow a very similar decreasing trend.
This trend in Wstd can be understood via steps of stochastic gradient descent. From the typical setting of weight update with momentum and weight decay, we have:
vt+1 = mvt + (λwt + wg,t), wt+1 = wt − ηvt+1. (1)
where wt, wg,t and vt are the weight, gradient and momentum at step t, respectively; m is the momentum factor, η is the learning rate and λ is the weight decay factor. After n steps,
vt+n = m nvt + n∑ k=1 (mn−kwg,t+k−1) + λ n∑ k=1 (mn−kwt+k−1), (2)
wt+n = (1− ηλ)nwt − η n∑ k=1 ((1− ηλ)n−k(mvt+k−1 + wg,t+k−1)). (3)
From this derivation, we can see that the two factors determine the mode of change in Wstd. When learning rate is high, the gradient terms play the major role in weight update. On the other hand, if the gradient activity becomes low, e.g., when the learning rate is low and the gradients oscillate around zero, we can further simplify Eq. 3. Assume that mnvt approaches to zero when n is relatively large, wt+k−1 ≈ wt, and ∑n k=1((1 − ηλ)n−kwg,t+k−1) and∑n
k=1(m n−kwg,t+k−1) approach to zero as the gradients oscillate around zero, we have vt+i ≈ λwt1−m . Then wt+n is
approximated as,
wt+n ≈ (1− ηλ)nwt − η n−1∑ i=0 ((1− ηλ)imλwt 1−m ). (4)
Note that (1− ηλ)n ≈ 1− nηλ since ηλ 1 and ∑n−1 i=0 ((1− ηλ)i) ≈ n. Thus,
wt+n ≈ (1− nηλ)wt − nηλmwt 1−m = (1− nηλ 1−m )wt. (5)
In other words, when the gradient activity is low, the change in Wstd is dominated by the both the learning rate and the weight decay. As an example, in Fig. 2a, Wstd is decreased with the slope following Eq. 5 when learning rate is low; Wstd of layer 10 is decreased by 1.5e-3 in 782 updates of CIFAR10 (with λ =1e-4 and m = 0.9), confirming the slope from Eq. 5.
These two modes governing the change of weight magnitude are critical for understanding the behavior of pruning. In particular, the interplay between learning rate and weight decay causes the per-layer pruning rate to converge after enough number of epochs. Fig. 2b shows the pseudo per-layer pruning rate, where we just measure the layer-wise pruning rate without really pruning out the weights in the model, for the same CIFAR10 training experiment. As the figure shows, the per-layer pruning rates saturate around epoch 100, indicating that pruning before that would select the weights based on the premature model.
Moreover, although the weight magnitude is an important factor, we discovered that the ranking of individual weight does not play a critical role in winning lottery tickets. Specifically, we empirically show that there exist many winning lottery tickets that are vastly different in terms of its sparse structure mv. Fig. 3 shows the hamming distance of the sparse structure of the lottery tickets at different configuration (s, v). Note that the two distant lottery tickets (e.g., (s = 200, v = 100) and (s = 100, v = 100)) show large hamming distance of 0.159 (where x/y = 200/100) while achieving the equally good accuracy as shown in Fig. 1, indicating that the ranking of the weights itself can not explain the quality of the structure of the lottery ticket.

heading: 3.3 UNDERSTANDING IMPACT OF PRUNED STRUCTURE

text:
The weight magnitude analysis motivates us not to prune a model too early. It is also implied that a distance-based metric might not reveal the winning structure of the model at different epochs. To understand the early winning structures, we further investigate the impact of the sparsified structure on the final accuracy. Considering that a highly pruned network is likely to have limited learning capability, we make a conjecture that the accuracy degradation of a pruned model is due to the loss of capability for learning complex pattern if pruned too early. Recently, Li et al. (2019) reveals that the training behavior of a sufficiently over-parameterized model with non-linearity highly depends on the learning rate schedule, where a model tends to memorize the complex patterns when a small learning rate is applied while learning simple patterns with a large learning rate. To validate this claim in the context of pruning, we construct an experiment where a model is pseudo-pruned at every epoch of the baseline training then retrained with large or small learning rate for just one epoch. For the pseudo-pruned-then-retrained (PPR) model at each baseline epoch, we measure the validation accuracy recovered from the retraining.
Fig.4 shows the result of this experiment on CIFAR10 ResNet20. When it is retrained with the large retraining learning rate (= 0.1), in just 1-epoch retraining, the PPR models from all the baseline epochs achieve the accuracy matching with the baseline accuracy. This indicates that those pruned models maintain the capability of learning the simple patterns. Whereas, when the small retraining learning rate (= 0.01) is used, the accuracy of the PPR models pruned at later epochs (epoch 100-200) is higher than the accuracy of the models from earlier epochs (epoch 20-60). This reveals that the PPR models from different epoch exhibit varying capability of learning complex patterns. In particular, the accuracy of the PPR models increases until around 100 epoch of the baseline training, then it saturates. Note that this coincides with the epoch when the early winning tickets emerges in Fig. 1.
Based on this observation, we hypothesize that the models pruned at 100 epoch of the baseline training or later will preserve the capability of learning complex patterns. To validate this hypothesis, we conducted the memorization test proposed by Boo et al. (2019), where a model is trained with training data of varying size with the randomized labels.
A model has "high memorization capacity" if it achieves high training accuracy for a large data size. Fig. 5 (left) shows the training accuracy of the models pruned at different epochs, measured from 10 independent simulations (the average capacity shown as solid lines, and min and max shown as the shaded regions). As the training data size increases, the memorization capacity decreases. The model pruned too early (i.e., at epoch 20) suffers higher degradation in the memorization capacity compared to the models pruned at later epochs (i.e., at epochs 120 or 200). Also, Fig. 5 (right) shows that those models pruned at later than 100 epochs (i.e., the early winning tickets) exhibit similar memorization capacity. This result not only confirms our conjecture on the impact of pruned structure to the capability of learning complex patterns, but also leads us to employ the PPR accuracy check as a computationally reasonable heuristic to discover the early winning tickets.

heading: 3.4 UNDERSTANDING GRADUAL PRUNING

text:
Gradual pruning is a popular pruning approach that applies pruning gradually over a period of training. For example, gradual pruning proposed by Zhu & Gupta (2017) provides a systematic way to schedule iterative pruning as follows:
st = sf + (si − sf ) (
1− t− t0 n∆t
)3 , (6)
where sf and si are the final and initial sparsity, and t is the time when pruning is applied. Eq. 6 determines how much sparsity is applied at a certain time step t. But it is still a user-hyper-parameter to decide when t0 or how often ∆t apply pruning. Based on the insights we discussed in the previous section, we explain why gradual pruning helps to obtain better lottery tickets.
The reasoning behind the gradual pruning is that the model can be changed graciously if the pruning is applied gradually. In terms of the early winning ticket analysis, there are two factors playing the critical role: 1) by applying low pruning rate in the beginning, the structure found at that pruning level can preserve the memorization capacity better, 2) once pruning is applied, the remaining weights of the pruned model is updated via SGD, granting a chance for the pruned model to adopt its weights toward better accuracy. Thanks to these two factors, a structure with better memorization capacity can be found when the increased pruning rate is applied next time.
Table 1 confirms this explanation using the CIFAR10 ResNet20 example. In this experiment, we perform the memorization test for the 4-step gradual pruning as well as four 1-step pruning at the corresponding epoch for comparison. The gap in memorization capacity is maintained across the different epochs, demonstrating that the memorization capacity is maintained thanks to the gradual application of pruning and the evolution of weights after pruning. This suggests a strategy for gradual pruning where 1) we can use gradual pruning to reduce the loss of capability in learning complex patterns, and 2) by applying a smaller pruning rate in the beginning, we can start pruning early and finding the winning lottery tickets faster. The benefit of this strategy combining gradual pruning with the early winning tickets will be demonstrated in Sec. 4.

heading: 4 EXPERIMENTS: FINDING WINNING TICKET EARLY

text: In this section, we demonstrate our strategy of finding the early winning tickets over popular neural networks on CIFAR10 and ImageNet. The detail experimental setup is described in Appendix A. We perform the lottery ticket experiments of Sec. 3.1 for both one-shot and gradual pruning with the pruning rate of 80%.We also conduct the PPR accuracy check of Sec. 3.3 to predict from which epoch the early winning ticket can be found. By comparing the two results, we demonstrate that the proposed heuristic for finding early winning tickets works robustly across the networks and the datasets. Furthermore, we showcase our gradual pruning strategy by comparing the performance in terms of the accuracy and the required pruning epochs with the existing lottery ticket approaches.

heading: 4.1 EXPERIMENTS ON CIFAR10

text: Table 2 summarizes the lottery ticket experiments of ResNet20 and ResNet56 on CIFAR10 dataset. In case of one-shot pruning, the winning tickets can be found from epoch 100. In case of gradual pruning, the gradual pruning schedule can start from epoch 75 (which is earlier than the one-shot pruning). Note that the gradual pruning can achieve better accuracy as it can preserve higher memorization capacity as discussed in Sec. 3.4. Fig. 6a shows the pseudo-pruning curve that highlights the presence of the winning tickets from the epoch around 100, which is consistent with the results of the lottery ticket experiment in Table 2.

heading: 4.2 EXPERIMENTS ON IMAGENET

text: Table 3 summarizes the lottery ticket experiments on ImageNet dataset, and the predicted results of the early winning tickets from the pseudo-pruning are shown in Fig. 6b. Similar to the CIFAR10 experiments, the results of the lottery ticket experiment matches with the results from the PPR accuracy check (which indicates epoch 45 for early winning tickets), demonstrating the robust behavior of the proposed strategy of finding the early winning tickets. Furthermore, the gradual pruning at the early winning tickets achieves the accuracy near to the baseline (ResNet18: baseline=69.7% vs ours=69.24%, ResNet50: baseline=75.7% vs ours=75.31%), showcasing the superior quality of the winning tickets discovered by the proposed gradual pruning strategy.

heading: 4.3 PERFORMANCE GAIN FROM EARLY WINNING TICKET

text: To demonstrate the performance gain from our gradual pruning strategy, the pruning results of the proposed algorithm (GP + EWT) and the previous implementation of iterative pruning (IP) along with the winning ticket (WT) of Frankle & Carbin (2018) are shown for the ResNet variants on CIFAR10 and ImageNet in Table 4. Our GP+EWT algorithm consistently achieves high pruning rate with the number of pruning epochs even lower than the regular retraining epochs for all the models, i.e., 80% pruning with negligible accuracy degradation on ResNet50 for ImageNet. In contrast, the iterative pruning approach (IP+WT) achieves the similar accuracy at the cost of more than 4.5× increase in the total training epochs.

heading: 5 CONCLUSION

text: In this work, we investigate the structure of the winning lottery ticket, which leads to the computationally efficient discovery of the winning lottery tickets. Based on a careful analysis of the characteristics of the structure of the winning lottery tickets, we proposed a computationally reasonable heuristic to identify when the early lottery tickets emerge. Furthermore, we proposed a gradual pruning strategy incorporating the early lottery ticket analysis to achieve high accuracy at large pruning rate. This results in the state-of-the-art accuracy on ResNet50 for 80% pruning only within 22% of the total epochs for iterative pruning.

heading: A EXPERIMENTAL SETUP

text:
A.1 EXPERIMENTS ON CIFAR10
We try to find the winning tickets early for ResNet20 (baseline accuracy: 92.5%) and ResNet56 (baseline accuracy: 94.25%) on CIFAR10 dataset. All the baseline models are trained using SGD optimizer with momentum (m =0.9) and weight decay (λ =1e-4) for 200 epochs. The initial learning rate for the first 120 epochs is 0.1 and decrease to 0.1× every 40 epochs. For the lottery ticket experiments, the retraining schedule is the same as the baseline learning rate schedule. Following convention, we do not prune the first and the last layers of the ResNets.
A.2 EXPERIMENTS ON IMAGENET
We further try to find the winning tickets early for ResNet18 (baseline accuracy: 69.7%) and ResNet50 (baseline accuracy: 75.7%) on ImageNet dataset. All the baseline models are trained using SGD optimizer with momentum (m =0.9) and weight decay (λ =1e-4) for 90 epochs. The initial learning rate for the first 30 epochs is 0.1 and decrease to 0.1× every 30 epochs. For the lottery ticket experiments, the retraining schedule is the same as the baseline learning rate schedule. Following convention, we do not prune the first and the last layers of the ResNets.

heading: B DISCUSSION

text:
B.1 IMPACT OF STRUCTURED SPARSITY ON LOTTERY TICKET HYPOTHESIS
In this section, we expand our scope of analysis on the characteristics of the early winning tickets toward the sparsity obtained via structured pruning. Structured pruning is a popular method that prunes weights by a group. For example, Liu et al. (2017) proposes channel-pruning, where a group consists of weights along each channel. The main motivation of looking at the structured sparsity is that there is a significant discrepancy in the best pruning rate we can achieve between the element-wise pruning (i.e., group-size=1) and the structured pruning (i.e., group-size=channel). For example, on CIFAR10-VGG19, the element-wise pruning achieves 95% of pruning rate whereas the channel-pruning achieves 70% of pruning rate for the same level of accuracy (Liu et al. (2018)). Although such discrepancy has been observed for quite a while, there is no in-depth investigation to understand why. To find out the reasoning behind it, we analyze the impact of structured sparsity with varying group sizes in the context of the lottery ticket hypothesis, as illustrated in Fig.7.
First, we revisit the extended lottery ticket experiments of Fig. 1 while applying group sparsity along the channel dimension (instead of pruning individual weights). Fig. 8 shows the results when the group size (gs) is 8. Comparing
it with Fig. 1, there are two notable points; 1) there is > 1% accuracy degradation when the group size is increased from 1 to 8, and 2) when gs = 8, the trend that the tickets drawn at epochs s > 100 achieve the higher accuracy disappears (as highlighted with a red rectangle in the figure). (Note that the two figures achieve the similar accuracy when s < 60 (colored in yellow), but the tickets with high accuracy (colored in green) can only be seen in Fig. 1.) The former observation makes sense as the more regularization on the sparse weight structure would result in the lower accuracy. But the latter observation is quite surprising; it seems that a distinct behavior of the lottery ticket hypothesis (i.e., the opportunity of finding winning tickets given a proper initialization) is disrupted as a group structure is asserted on the sparsity.
We can find a clue on this disrupted behavior by employing the memorization capacity analysis. Table 5 shows the results of memorization capacity experiments on CIFAR10-ResNet20 with an increasing group size gs = {1, 2, 4, 8, 16, 32, 64}. The memorization capacity degrades significantly as the group size increases. Intuitively, by asserting a large group size, the model’s expressivity is degraded and it becomes harder to learn the complex patterns, leading to accuracy loss. Note that we had a similar observation when the tickets are drawn too early (cf.,s < 60 in Fig. 1). From this, we can
hypothesize that the winning tickets disappear as the memorization capacity is degraded, which can be observed when the tickets are drawn too early or the group sparsity is forced.
Fig. 9 further demonstrates the impact of structured sparsity on the saturation of pruning accuracy. For different group sizes, the figure shows the accuracy of CIFAR10-ResNet20 80% pruned at varying epochs. It can be observed that the models with the larger group size not only achieve the lower accuracy but also converge at earlier epochs. (E.g., the knee points for gs = 1 and gs = 16 are around 90 and 50 epochs, respectively.) This experimental result supports our claim that the larger group size enforced in the sparse structure results in the earlier convergence of the pruned models that misses the winning tickets.
B.2 MODE CONNECTIVITY OF EARLY WINNING TICKETS
Mode connectivity is a phenomenon that SGD solutions are connected through paths of approximately equal loss (Draxler et al. (2018)). It provides the perspective of how well the models trained via a proposed method can generalize. In the context of early winning tickets, we for the first time reveal that the lottery tickets drawn early based on PPR are indeed connected from the one obtained by IMP, whereas the tickets chosen too early do not.
For the mode connectivity experiments, we draw three lottery tickets - one drawn too early (i.e., a premature ticket, PT), one drawn based on PPR (i.e., an early winning ticket, EWT), and one at the end of the training schedule (i.e., a winning ticket, WT). Note that all the tickets are trained from the same initial weights and with the same retraining schedule. Then we linearly interpolate PT and EWT with WT, and plot the test error for different interpolation coefficient (from 0 to 1).
Fig. 10 shows the results of the mode connectivity experiments for ImageNet and CIFAR10. For both datasets, the linearly interpolated models between PT and WT depict a barrier, indicating that PT and WT are disconnected. Whereas, the linearly interpolated models between EWT and WT show consistently low test error. Note that such linear mode connectivity is observed even when 1) the weights are sparse (i.e., 80% pruning rate) and 2) the mask distance is large (cf., Fig. 3). This intriguing observation counters some observations of prior work; Draxler et al. (2018) claims that it takes a careful search (instead of a simple linear interpolation) to find a pass connecting the modes, and the existence of such a non-linear pass requires enough number of parameters. Our novel observation of early lottery tickets provide a new aspect of sparse model training; the sparse structures mature early in the training, and they converge to a flat local minimum even if its shape is vastly distant. A deeper investigation about the sparse structure of the lottery tickets and the mode connectivity is an interesting future research topic.

heading: C EARLY WINNING TICKET ALGORITHMS

text:
In this section, we describe the detail algorithms for finding early winning tickets via one-shot and gradual pruning.
Algorithm 1: Early Winning Ticket Identification with One-Shot Pruning Require: Initial weights θ0, learning rate schedule LS := {η(n)}, n = 0, 1, ..., N − 1, pruning ratio p, PPR
accuracy checking period TPPR, PPR accuracy saturation detection threshold kPPR, PPR retraining learning rate ηPPR;
Initialize model with θ0, t = 0; Step 1: Early winning ticket (EWT) identification by tracking PPR accuracy for i = 0; i < N ; i++ do
Train the model with learning rate η(i) for one epoch; if i % TPPR = 0 then
Save a copy of the model and optimization state; Prune p% of the model parameters and create a mask mPPR,t; Train the pruned model θi ◦mPPR for one epoch and obtain the test accuracy AccPPR,t; Restore the model and optimization state with the saved copy; if AccPPR,t′ <= AccPPR,t′−1 for t′ = t, t− 1, ..., t− kPPR + 1 then
Set the model parameters to θi ◦mPPR,t; break;
end t++;
end end Step 2: Retraining EWT with the same LS for i = 0; i < N ; i++ do
Train the pruned model with learning rate η(i) for one epoch; end
Algorithm 2: Early Winning Ticket Identification with Gradual Pruning Require: Initial weights θ0, learning rate schedule LS := {η(n)}, n = 0, 1, ..., N − 1, pruning ratio p, PPR
accuracy checking period TPPR, PPR accuracy saturation detection threshold kPPR, PPR retraining learning rate ηPPR, gradual pruning period Tgr;
Initialize model with θ0, t = 0; Step 1: Early winning ticket (EWT) identification by tracking PPR accuracy for i = 0; i < N ; i++ do
Train the model with learning rate η(i) for one epoch; if i % TPPR = 0 then
Save a copy of the model and optimization state; Prune p% of the model parameters and create a mask mPPR,t; Train the pruned model θi ◦mPPR for one epoch and obtain the test accuracy AccPPR,t; Restore the model and optimization state with the saved copy; if AccPPR,t′ <= AccPPR,t′−1 for t′ = t, t− 1, ..., t− kPPR + 1 then
break; end t++;
end end Step 2: Gradual Pruning to refine the EWT structure for i = 0; i < Tgr; i++ do
Prune model gradually toward the pruning ratio p according to Eq. (6) and create a mask mgr,i; Train the pruned model θgr,i ◦mgr,i for one epoch;
end Step 3: Retraining EWT with the same LS for i = 0; i < N ; i++ do
Train the pruned model with learning rate η(i) for one epoch; end


summaries: This paper proposes a neural network architecture for image classification, which can more accurately recognize the unknown class that is not presented in the training data than the prior work. The key idea is to organize the features into a binary tree and use the product of probabilities along the paths to the leaf node to predict whether the test image has all the relevant features that should present in known classes. This proposed method is compared to multiple baselines and demonstrates superior results in image classification, especially for correctly predicting the unknown class.

summaries: This paper proposes the unknown-aware deep neural network (UDN), which can be used to discover out-of-distribution samples for neural network classifiers. Its main idea is to introduce PR subnets to model the product relationship instead of the dot product of regular networks, then it can avoid over-fitting. Experimental results demonstrate that UDN can discover unknown samples more precisely than several baselines.

summaries: This paper is about a novel method to detect unknown samples which are of a different class than the trained ones. The idea is to use an output subnet which use a fully connected layer and a binary tree which encode the product relationship instead of the sum currently used in state of the art method (particularly the softmax with low confidence). The binary tree is made of split nodes which are responsible to produce a probability distribution from the root to each leaf. The max path i.e. the path with the largest probabilities determines the class of the input and can be used to measure how confident the classifier is about the classification decision. Combine multiple subnets and the tool obtained is able to do complex predictions and maintain a good generalization performance. The method also uses an information theory based regularization which decrease the probability of having subnets with uniform probability distribution i.e. a large entropy. Experiments on CIFAR-10 and MNIST against CIFAR-100, SVHN show that the method has an improved rejection accuracy while maintaining a good classification accuracy on the test set.

abstractText: An important property of image classification systems in the real world is that they both accurately classify objects from target classes (“knowns”) and safely reject unknown objects (“unknowns”) that belong to classes not present in the training data. Unfortunately, although the strong generalization ability of existing CNNs ensures their accuracy when classifying known objects, it also causes them to often assign an unknown to a target class with high confidence. As a result, simply using low-confidence detections as a way to detect unknowns does not work well. In this work, we propose an Unknownaware Deep Neural Network (UDN for short) to solve this challenging problem. The key idea of UDN is to enhance existing CNNs to support a product operation that models the product relationship among the features produced by convolutional layers. This way, missing a single key feature of a target class will greatly reduce the probability of assigning an object to this class. UDN uses a learned ensemble of these product operations, which allows it to balance the contradictory requirements of accurately classifying known objects and correctly rejecting unknowns. To further improve the performance of UDN at detecting unknowns, we propose an information-theoretic regularization strategy that incorporates the objective of rejecting unknowns into the learning process of UDN. We experiment on benchmark image datasets including MNIST, CIFAR-10, CIFAR-100, and SVHN, adding unknowns by injecting one dataset into another. Our results demonstrate that UDN consistently outperforms state-of-the-art methods at rejecting unknowns – up to 20 point gains in accuracy, while still preserving the classification accuracy.

title: Outlier Analysis: Second Edition

authors:
Stephen D. Bay
Mark Schwabacher

title: Mining distance-based outliers in near linear time with randomization and a simple pruning rule

venue: In KDD, pp

authors:
Abhijit Bendale
Terrance E. Boult

title: Towards open set deep networks

venue: In CVPR,

authors:
Markus M. Breunig
Hans-Peter Kriegel
Raymond T. Ng
Jörg Sander

title: LOF: identifying density-based local outliers

venue: In SIGMOD, pp

authors:
Jinghui Chen
Saket Sathe
Charu C. Aggarwal
Deepak S. Turaga

title: Outlier detection with autoencoder ensembles

venue: In SDM,

authors:
Jesse Davis
Mark Goadrich

title: The relationship between precision-recall and roc curves

venue: In Proceedings of the 23rd international conference on Machine learning,

authors:
Sarah M. Erfani
Sutharshan Rajasegarar
Shanika Karunasekera
Christopher Leckie

title: High-dimensional and large-scale anomaly detection using a linear one-class SVM with deep learning

venue: Pattern Recognition,

authors:
Yarin Gal
Zoubin Ghahramani

title: Dropout as a bayesian approximation: Representing model uncertainty in deep learning

venue: In ICML,

authors:
Ian Goodfellow
Yoshua Bengio
Aaron Courville

title: Deep Learning

authors:
Dan Hendrycks
Kevin Gimpel

title: A baseline for detecting misclassified and out-ofdistribution examples in neural networks

authors:
Dan Hendrycks
Mantas Mazeika
Thomas Dietterich

title: Deep anomaly detection with outlier exposure

venue: In ICLR,

title: Random decision forests

venue: ICDAR ’95,

authors:
Gao Huang
Zhuang Liu
Laurens van der Maaten
Kilian Q. Weinberger

title: Densely connected convolutional networks

authors:
Edwin M. Knorr
Raymond T. Ng

title: Algorithms for mining distance-based outliers in large datasets

venue: In VLDB, pp

authors:
Peter Kontschieder
Madalina Fiterau
Antonio Criminisi
Samuel Rota Bulò

title: Deep neural decision forests

venue: In ICCV, pp

title: Learning multiple layers of features from tiny images

venue: Technical report,

authors:
Alex Krizhevsky
Geoffrey Hinton

authors:
Alex Krizhevsky
Ilya Sutskever
Geoffrey E. Hinton

title: Imagenet classification with deep convolutional neural networks

venue: In NIPS, pp

authors:
Shiyu Liang
Yixuan Li
R. Srikant

title: Enhancing the reliability of out-of-distribution image detection in neural networks

venue: In International Conference on Learning Representations,

authors:
Si Liu
Risheek Garrepalli
Thomas G. Dietterich
Alan Fern
Dan Hendrycks

title: Open category detection with PAC guarantees

authors:
Andrey Malinin
Mark Gales

title: Predictive uncertainty estimation via prior networks

venue: In NeurIPS,

authors:
Larry M. Manevitz
Malik Yousef

title: One-class svms for document classification

venue: J. Mach. Learn. Res.,

authors:
Yuval Netzer
Tao Wang
Adam Coates
Alessandro Bissacco
Bo Wu
Andrew Y Ng

title: Reading digits in natural images with unsupervised feature learning

venue: In NIPS workshop on deep learning and unsupervised feature learning,

authors:
Minh-Nghia Nguyen
Ngo Anh Vien

title: Scalable and interpretable one-class svms with deep learning and random fourier features

authors:
Adam Paszke
Sam Gross
Soumith Chintala
Gregory Chanan
Edward Yang
Zachary DeVito
Zeming Lin
Alban Desmaison
Luca Antiga
Adam Lerer

title: Automatic differentiation in pytorch

authors:
Pramuditha Perera
Vishal M. Patel

title: Learning deep features for one-class classification

authors:
Gabriel Pereyra
George Tucker
Jan Chorowski
Łukasz Kaiser
Geoffrey Hinton

title: Regularizing neural networks by penalizing confident output distributions

venue: arXiv preprint arXiv:1701.06548,

authors:
Sridhar Ramaswamy
Rajeev Rastogi
Kyuseok Shim

title: Efficient algorithms for mining outliers from large data sets

venue: In ACM SIGMOD Record,

authors:
Lukas Ruff
Nico Görnitz
Lucas Deecke
Shoaib Ahmed Siddiqui
Robert A. Vandermeulen
Alexander Binder
Emmanuel Müller
Marius Kloft

title: Deep one-class classification

authors:
Thomas Schlegl
Philipp Seeböck
Sebastian M. Waldstein
Ursula Schmidt-Erfurth
Georg Langs

title: Unsupervised anomaly detection with generative adversarial networks to guide marker discovery

venue: In IPMI,

authors:
Bernhard Schölkopf
John C. Platt
John C. Shawe-Taylor
Alex J. Smola
Robert C. Williamson

title: Estimating the support of a high-dimensional distribution

venue: Neural Comput.,

title: Probability Theory: An Analytic View

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

title: Rethinking the inception architecture for computer vision

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

authors:
David M.J. Tax
Robert P.W. Duin

title: Support vector data description

venue: Mach. Learn.,

authors:
Apoorv Vyas
Nataraj Jammalamadaka
Xia Zhu
Dipankar Das
Bharat Kaul
Theodore L. Willke

title: Out-of-distribution detection using an ensemble of self supervised leave-out classifiers

venue: In ECCV,

authors:
Shuangfei Zhai
Yu Cheng
Weining Lu
Zhongfei Zhang

title: Deep structured energy based models for anomaly detection

authors:
Bo Zong
Qi Song
Martin Renqiang Min
Wei Cheng
Cristian Lumezanu
Daeki Cho
Haifeng Chen

title: Deep autoencoding gaussian mixture model for unsupervised anomaly detection

heading: 1 Introduction

text:
Motivation. In recent years, Convolutional Neural Networks (CNN) have been used with great success for a rich variety of classification problems, particularly when dealing with high dimensional, complex data such as images or time series (Goodfellow et al., 2016). A CNN classifier (Krizhevsky et al., 2012) typically classifies test objects as one of the target classes supplied in the training set. In this, state-of-the-art classifiers make the implicit assumption that all testing objects belong to one of the target classes. However, this assumption is rarely true in real-world deployments of CNN classifiers. Consider for example, an autonomous car or healthcare system: it is extremely likely that the system will be exposed to objects that were not in its training set. We call such objects “unknowns”.
Clearly, blindly assigning these unknowns into one of the target classes degrades the prediction accuracy. Worst yet, it can lead to serious safety concerns. For example, in a collaboration with a top hospital in the US (name removed due to anonymity), we have been developing a seizure detector that classifies patients into different types of seizures based on EEG signals collected during the clinical observation of 4,000 patients. The detector was trained based on 6 types of seizures observed in the training data. However, when deployed, the CNN classifier may encounter patients who have types of seizures that do not exist in the training data because they are rare or even unknown by the medical community. Misclassifying these patients into the existing types of seizures brings serious risks and potential harm due to the potential for mistreatment of these patients. Ideally, in this case, the unknowns would be recognized and rejected by the classifier.
In this work, we focus on this important problem, describing a deep neural network that not only accurately classifies test objects into known target classes, but also correctly rejects unknowns.
State-of-the-Art. In a typical CNN, the output of the last fully connected layer is fed into a softmax layer to generate a class probability in [0, 1] for each target class. An object will then be assigned to the class with the maximal probability. Intuitively, unknowns would be detected by leveraging this confidence, as was done in Bendale & Boult (2016); Hendrycks & Gimpel (2017); Liang et al. (2018). Since unknowns should not exhibit as many features of a target class versus known objects, the CNN should report a lower confidence. In prior work (Bendale & Boult, 2016; Hendrycks & Gimpel, 2017; Liang et al., 2018), the maximal probability or the largest value in the input vector to the softmax layer (maximal weighted sum) is used as a confidence to detect unknowns. In particular, an object will be rejected as an unknown if its confidence is smaller than a predetermined cutoff threshold ct.
However, as shown in our experiments (Sec. 5), these state-of-the-art methods are not particularly effective at rejecting unknowns. This is because CNNs achieve high classification accuracy by providing a strong ability to generalize, allowing it to overcome the gap between the training and testing data (Goodfellow et al., 2016). Unfortunately, this strength here is also a weakness, because it increases the chance of erroneously assigning an unknown to some target class even if it is quite different from the training objects in any target class. More specifically, the maximal probability (or maximal weighted sum) in a CNN is computed by the weighted sum operation on the multiple features produced by the convolutional layers. Because of this sum operation, an unknown can be classified to a target class with high confidence even if it matches some key features of a target class only by chance. Therefore, the requirements of accurately classifying the knowns and correctly rejecting the unknowns conflict with each other.
Proposed Approach and Contributions. In this work we propose an Unknown-aware Deep Neural Network (UDN for short) to overcome this problem.
The key intuition of UDN is to modify the CNN to use a product operation which models the product relationship among the features produced by the convolutional layers. This way, similar to the product rule in probability theory (Stroock, 2010), if just one feature indicative of a target class is not matched, the probability of assigning an object to this class is greatly reduced. Since an unknown is unlikely to match most of the features of a target class, the chance of assigning an unknown to a target class with high confidence is reduced. Therefore, the confidence produced by UDN should more effectively detect unknowns than the typical maximal probability/maximal weighted sum produced by classical CNNs. In UDN, the product operations are learned as a set of product relationship (PR) subnets leveraging the hierarchical nature of the binary tree structure. The strong bias of the classification decisions made via the product operations and the generalization ability introduced by the ensemble nature of multiple PR subsets together balance the contradictory requirements of accurately classifying known objects and correctly rejecting unknowns.
In addition, we propose an information-theoretic regularization strategy that actively incorporates the objective of unknown rejection into the learning process of UDN. This further improves the accuracy of UDN at rejecting unknowns by enlarging the confidence gap between unknown and known objects. We then show that the final loss function of UDN is fully differentiable. Therefore, UDN can be learned by following the common practice of back-propagation in deep neural networks.
We demonstrate the effectiveness of UDN using a rich variety of benchmark datasets including MNIST, CIFAR-10, CIFAR-100, and SVHN. UDN outperforms the state-of-the-art up to 20 points in the accuracy of unknown rejection – while preserving the accuracy of the underlying CNN at classifying objects from the target classes.

heading: 2 Related Work

text:
Out-of-Distribution Detection. In Bendale & Boult (2016), CNNs were adapted to discover unknowns by adding one additional unknown class to the softmax layer. This
method, called OpenMax, measures the distance between the maximal weighted sum vector produced for a test object and the mean maximal weighted sum vectors of the target classes that this test object is most likely assigned to. This distance is translated to a probability by the OpenMax layer. A testing object will be assigned to the unknown class if this probability is larger than a pre-defined cutoff threshold. Similarly, Malinin & Gales (2018) detects out-of-distribution objects by parameterizing a prior distribution over predictive distributions, so called Prior Networks (PNs), while Hendrycks & Gimpel (2017) directly uses softmax probabilities to detect out-of-distribution objects.
ODIN (Liang et al., 2018) detects unknowns using a two-pass inference strategy. That is, each test image goes through the inference stage twice. During the second inference round, each input is perturbed based on the gradient of its loss acquired in the first inference. The goal is to make the maximal probability produced by softmax more effective at separating unknowns. One problem with ODIN is that it introduces two extra hyper-parameters to control the level of perturbation, which are hard to tune.
As shown in experiments, our UDN method significantly outperforms OpenMax and ODIN, because UDN uses the maximal path probability as confidence measure, which as the product of multiple probabilities w.r.t. a set of nodes, is more effective in rejecting unknowns than using maximal weighted sum or maximal probability as a confidence measure.
MC-Dropout (Gal & Ghahramani, 2016) uses Bayesian model to reason about model uncertainty by casting dropout training in deep neural networks as as approximate Bayesian inference in deep Gaussian processes. It then rejects a testing object as unknown if the uncertainty about this object is large. As shown in experiments, MC-Dropout in many cases outperforms OpenMax and ODIN in rejecting unknowns, although is still worse than our UDN. Further, it scarifies the accuracy of classifying the known classes.
In Liu et al. (2018) and Vyas et al. (2018), methods were proposed to detect the objects that do not belong to known classes in a “clean” training dataset. However, these methods rely on a “contaminated” training set that contains a fraction of unknowns, i.e., that were not in the original clean training data. In other words, they solve the problem of rejecting “known unknowns”, while our UDN instead focuses on the problem of rejecting “unknown unknowns”. Our UDN does not require any labeled unknowns in training.
Deep Outlier Detection. Methods in Perera & Patel (2018); Erfani et al. (2016); Ruff et al. (2018); Nguyen & Vien (2018); Schlegl et al. (2017); Zhai et al. (2016); Chen et al. (2017); Zong et al. (2018); Hendrycks et al. (2019) use representation learning of deep neural networks to enhance the classical unsupervised outlier detection methods such as one-class classification (Schölkopf et al., 2001; Manevitz & Yousef, 2002; Tax & Duin, 2004) and neighbor-based methods (Breunig et al., 2000; Knorr & Ng, 1998; Ramaswamy et al., 2000; Bay & Schwabacher, 2003). However, unlike our work which focuses on enhancing the CNNs to reject the unknown objects during the inference process, these outlier detection methods do not take the classification objective into consideration. Instead, these methods detect outliers from a given dataset as the objects that significantly deviate from the majority of this dataset (Aggarwal, 2017), without using any labeled outliers or normal objects.
Deep Neural Decision Forest. Similar to the deep neural decision forest (DNDF) (Kontschieder et al., 2015), nodes in UDN at the final FC layers are connected to the split nodes of multiple trees. However, UDN is different from DNDF in several important ways. First, conceptually UDN corresponds to a variation of CNN model by replacing the softmax layer with tree structures such that the CNN can model the product relationship among the features learned by CNN, while DNDF instead enhances a random forest classifier with the feature learning ability of a CNN. Second, UDN incorporates the objective of unknown rejection into the learning process, while DNDF only considers the classification of known classes. Third, DNDF estimates both the decision node parametrizations θ and the leaf predictions π by using a two-step optimization strategy, where θ and π are updated alternatively to minimize the log-loss, while UDN is fully differentiable and therefore can be optimized in one step. Forth, in DNDF different trees share the FC layers (except the final FC layer) of the CNNs, while UDN divides all FC layers into m independent components,
each of which is connected to one individual tree. This ensures independence among the trees and improves the classification accuracy because of the excellent generalization capability.

heading: 3 An Unknown-aware Deep Neural Network

text: In this section, we first introduce the structure of unknown-aware deep neural network (UDN). Next, we show how UDN distinguishes unknown from known objects. A regularization strategy is introduced in Sec. 4 to further improve the accuracy of UDN at rejecting unknowns.

heading: 3.1 UDN: Network Structure

text:
As depicted in Fig. 1, UDN is composed of the convolutional module and M independent product relationship (PR) subnets, whereM corresponds to a user definable hyper-parameter.
PR Subnet. The PR subnet is designed to model the product relationship among the features produced by the convolutional layers. Each PR subnet contains one fully connected (FC) component connected to a binary tree structure. Within each individual tree T , each split node of T is connected to one output node of the final layer of the FC component. The mapping between the FC output nodes and the split nodes can be arbitrary. Any FC output node can be connected to the root node of the tree. The set of split nodes of T is denoted as N . The set of leaf nodes is denoted as L. Each split node ni ∈ N converts the output xi of the FC node it consumes data from into a value in the [0 , 1 ] range by applying the sigmoid function σ(xi), where σ(xi) = (1 + e−xi )−1.
Each leaf node l ∈ L is parameterized using a C-dimensional probability distribution πl, where C denotes the number of classes. One element πil of πl w.r.t. the ith class is computed as the softmax output of a to be learned parameter wil :
πil = softmax(w i l) = ew i l∑C
j=1 e wjl
(1)
Product Relationship. Next, we show how a PR subnet models the product relationship using the path probability µl(x) defined in Eq. 2, where x denotes an input object and l denotes a path from the root node to a leaf node l.
µl(x) = ∏ ni∈Nl d(xi) (2)
In Eq. 2, Nl denotes the set of split nodes on the path from root to a leaf l. Given a node ni ∈ Nl, d(xi) = σ(xi) if the left child of ni is included in this path. Otherwise, d(xi) = 1 − σ(xi). For example, as shown in Fig. 1, on the path of n11 → n12 → n15 → l13, d12 w.r.t. n12 is set as 1 − σ(x12 ), because n12 is connected to its right child n15 on this path.
Therefore, d(xi) indicates the probability that input x will be routed from node ni down to the next node on path l. Accordingly, µl(x ) models the probability of input x reaching leaf l, i.e., the probability of path l.
Since the d(xi) of each split ni corresponds to the output xi produced by the FC node w.r.t. ni, essentially the path probability µl(x ) is jointly determined by the output of multiple FC nodes. Therefore, µl(x) successfully models the product relationship among the features produced by CNN. The existence of one FC node that leads to small d(xi) will make the probability of the whole path l small.
Prediction. At each leaf node l of T , a PR subnet produces a prediction for a given input object x using Eq. 3.
PPR[y|x, π] = ∑ l∈L πlyµl(x) (3)
In Eq. 3, π = {πl |l ∈ L}, and πly denotes the probability that leaf l believes an input sample x belongs to class y. µl(x) denotes the path probability of l. Generally speaking, the prediction is given by the probability produced at the leaf node l weighted by the probability of input x reaching leaf l.
Finally, as an ensemble of a set of PR subnets PR = {PR1 , . . . ,PRM }, UDN produces a prediction for an input x by averaging the output of each subnet, i.e.:
PPR[y|x] = 1
| PR | |PR|∑ i=1 PPRi [y|x, π] (4)
Similar to the typical ensemble structures like random forest (Ho, 1995), the ensemble of multiple PR subnets results in good generalization performance in classifying objects from target classes, even if each individual PR subnet could be overfit to the training examples.
Note when we setup the network structure of UDN, the mapping between the FC output nodes and the split nodes of the binary tree is arbitrary. The parameters w.r.t. each node is learned in an end-to-end fashion through back propagation. In the training process that minimizes the loss, the important features for a known class will be automatically learned and mapped to the split nodes on the same path. In other words, we do not have to group features explicitly. Instead, the grouping of the features is learned automatically. Fig. 1 shows the final results of the training. For example, since nodes f11, f12, and f16 are not on the same path, these nodes are not considered to correspond to the key features of any class.

heading: 3.2 UDN: Unknown Rejection

text:
Max Path. Based on the above architecture, given a testing object x, each PR subnet in UDN produces a probability distribution µl(x ) over each path from the root to a leaf l. As shown in Eq. 2, the probability of a path is computed as the product of the probabilities (d(xn)) produced by all split nodes on that path. Given an object x, a given path will have an extremely small probability if x does not fit the features represented by the split nodes on this path (hence small d(xn)), because the product of multiple small probabilities will diminish quickly. One path will stand out when all its split nodes produce large probabilities on x, marked as bold line in Figure 1. We call this path the max path, because it has the maximal probability among all paths.
Since the learned πl on each leaf is invariant w.r.t. input x, essentially it is the max path that determines the class of x by Eq. 3. Therefore, the probability of the max path µl(x ) (or max path probability) can be used to measure how confident the classifier is about its classification decision of object x. The larger the max path probability is, the more confident
the classifier is about the object. More specially, given an object x and a PR subnet PR, the confidence is measured as:
CFPR(x; Θ) = max{µl(x)|l ∈ L} (5)
where max{µl(x )|l ∈ L} denotes the max path probability of subnet PR for the given object x. Since UDN is an ensemble of a set of PR subnets, the final confidence of object x is measured as:
CFPR(x) = 1
| PR | |PR|∑ i=1 CFPRi(x; Θi) (6)
Effectiveness of Using Max Path to Reject Unknowns. Intuitively this max path probability can be expected to be more effective at detecting unknowns than the maximal weighted sum in CNN. Typically an unknown will not get large probability on every split node on the max path, and one low probability node will limit the max path probability because of the product operation used in the computation. In contrast, the maximal weighted sum in CNN tends to fall off much more slowly because the score is computed based on the sum operation (with weights) on multiple features, such that a single matching feature can make the score high. This is confirmed in our experiments (Sec. 5.2, Appendix B, Appendix C).

heading: 4 Incorporating Unknown Rejection into the Learning Process

heading: 4.1 Information Theory-based Regularization

text:
To ensure the effectiveness of using the max path probability to reject unknowns, we further incorporate the objective of unknown rejection into the learning process of UDN by introducing a regularization. The key idea is to use an information theory-based approach to prevent the generation of a PR subnet whose paths show uniform probability distribution. This ensures that the max path probability of each subnet will be generally much larger than the probabilities of other paths, making it more effective at rejecting unknowns. To achieve this, we penalize the paths whose probability distribution has a large entropy and hence is close to uniform (Pereyra et al., 2017).
Given a subnet PR with |L| paths, each input x ∈ X can use any of |L| paths to reach leaf nodes. The entropy of the path probability distribution of input x is given by:
H(µ(x)) = − ∑ l∈L µl(x)log(µl(x)) (7)
We then apply a softmax function on the probability distribution as a normalization. The revised entropy of the path probability distribution is given by:
H(µ′(x)) = − ∑ l∈L µ′l(x)log(µ ′ l(x)) (8)
where µ′l(x ) = softmax (µl(x )) = exp(µl (x))∑
li∈L exp(µli (x))
is the softmax transformation of µl(x ).
To penalize the subnet whose path probability distribution is close to uniform, we add the entropy w.r.t. each training sample to the log-loss term. Given the training set X and the output Y, the penalized log-loss term of one subnet PR is represented as:
L(PR;X ,Y) = ∑
(x,y)∈X×Y
−log(PPR[y|x,Θ, π]) + βH(µ′(x|Θ)) (9)
where β controls the strength of the penalty and PPR[y |x ,Θ, π] is defined in Eq. 3. Θ represents the learned parameters at the convolutional layers and FC layers.
The total log-loss for the UDN composed of |PR| subnets is then defined as:
L(PR;X ,Y) = 1 | PR | |PR|∑ i=1 L(PRi;X ,Y) (10)

heading: 4.2 Training a UDN

text: Training a UDN requires finding a set of parameters Θ and π that minimize the total log loss defined in Eq. 10. To minimize Eq. 10, we can independently minimize the penalized loss (Eq. 9) of each individual subnet. In Appendix A, we show that the loss function is fully differentiable. As a result, we are able to employ SGD to minimize the loss w.r.t. Θ and π, following the common practice of back-propagation in deep neural networks.

heading: 5 Experimental Evaluation

heading: 5.1 Overview of Experimental Setting

text:
Datasets. We demonstrate the effectiveness of UDN on several benchmark image datasets. Specifically, we train models on CIFAR-10 (Krizhevsky & Hinton, 2009), CIFAR100 (Krizhevsky, 2009), and SVHN (Netzer et al., 2011) datasets. Given a trained model on one dataset, we consider examples from other datasets as unknowns when testing the model. In addition, we also sample some classes from the training data as unknowns and test these samples on the model trained for the rest of the classes. Due to the lenght constraints we present the results on the CIFAR-100 and SVHN models in Appendix B and Appendix C.
Methodology. We evaluate: (1) CNNs with Weighted-Sum as a baseline. The weighted sum score is utilized as the confidence measure; (2) OpenMax (Bendale & Boult, 2016), (3) ODIN (Liang et al., 2018), (4) Softmax (Hendrycks & Gimpel, 2017), and (5) MCDropout (Gal & Ghahramani, 2016): the state-of-the-art unknown rejection methods described in related work (Sec. 2); (6) our UDN model without the regularization term applied to the loss function and (7) UDN-Penalty : our UDN with the regularization term (Eq. 9).
The results show that our UDN and UDN-Penalty significantly outperform OpenMax, ODIN, MC-Dropout and Softmax through a variety of unknown rejection experiments, while still preserving the accuracy of classifying objects from target classes.
Experimental Setup. We ran experiments on 4 P100 GPU instances on Google cloud. All models are implemented in Pytorch (Paszke et al., 2017).
Hyper-parameter Settings. All networks are trained using mini-batches of size 128. The momentum is set to 0.9 for all models. The weighted decays are set to 0.0001. When testing MNIST on models trained for other datasets, we increase its color channel from 1 to 3 by copying the original gray images 3 times.
Evaluation Metric. Following the literature of unknown rejection, we use two metrics to measure the effectiveness of UDN at distinguishing known and unknown images, namely true negative rate (TNR) at 95% true positive rate (TPR) and AUROC. TNR at 95% TPR can be interpreted as the probability that an unknown image (negative) is correctly recognized when the TPR is 95%. True positive rate can be computed by TPR = TP /(TP + FN), where TP and FN denote true positives (knowns are correctly classified as knowns) and false negatives (known images are misclassified as unknowns) respectively. The true negative rate (TNR) can be computed by TNR = TN/(FP+TN), where FP and TN denote false positives (unknowns are misclassified as knowns) and true negatives (unknowns are correctly recognized) respectively.
AUROC corresponds to the Area Under the Receiver Operating Characteristic curve, which is a threshold independent metric (Davis & Goadrich, 2006). It can be interpreted as the probability that a positive example is assigned a higher detection score than a negative example. In addition, we also measure the accuracy of these methods at classifying the knowns into target classes.

heading: 5.2 CIFAR-10

text:
We tested all approaches on DenseNet (Huang et al., 2017). All methods use the same DenseNet architecture to ODIN (Liang et al., 2018). For our UDN and UDN-Penalty, the output is connected to 10 depth-5 trees. Specifically, the output of the convolutional layer is broadcast to 10 different sets of FC layers. Each set contains 3 FC layers. The final FC layer with 63 (2 (5+1) − 1 ) hidden nodes is connected to a tree. The training time of UDN is 9.4 hours, slightly slower than training a DenseNet model (9.1 hour). For the evaluation of ODIN, we directly use the model published by the authors. The temperature parameter T and the perturbation magnitude η used by ODIN are set to 1000 and 0.0014. We set the drop rate of MC-Dropout as 0.2 and the number of forward passes as 100. We set these parameters by the suggestion of the authors or parameter tuning.
As shown in Table 1, in almost all cases UDN and UDN-Penalty outperform Softmax, Weighted-sum, OpenMax, ODIN, and MC-Dropout in rejecting unknowns, without giving up our ability to correctly classify the CIFAR-10 images. Specifically, UDN and UDN-Penalty outperforms other methods up to 10 points in TNR. UDN and UDN-Penalty also significantly outperform other methods in AUROC. In particular, UDN and UDN-Penalty achieve about 98% AUROC when detecting SVHN as unknowns. This indicates that our methods can effectively separate knowns and unknowns under a wide range of parameter settings.
The performance gain results from our UDN architecture, where the confidence of each image is computed as the product of the probabilities produced at the split nodes on the path. This multiplication of probabilities enlarges the confidence gap, making it able to better reject unknowns than alternate approaches. The only exception is that MC-Dropout performs the best on rejecting MNIST as unknowns, showing that MC-Dropout is probably good at separating unknowns which are simplistic yet very different from known objects.
In addition, UDN achieves slightly better classification accuracy compared to Softmax, Weighted-Sum, OpenMax, and ODIN that use the classical DenseNet. The classification accuracy of MC-Dropout is worse than other methods because of the Bayesian inference.
Our UDN-Penalty outperforms UDN in rejecting unknowns in all cases. This is because by introducing regularization to penalize path probability distributions that have a large entropy, UDN-Penalty leads to larger maximal path probabilities for inliers. At the same time, its classification accuracy decreases slightly, because the regularization introduces overfitting (Szegedy et al., 2016). However, this is effectively alleviated because of the ensemble of the PR subnets. Therefore, the drop in classification accuracy is very small.

heading: 6 Conclusion

text: In this work, we proposed an augmentation to CNNs, UDN, which effectively rejects unknown objects that do not belong to any class seen in the training data. UDN achieves this by replacing softmax layer in traditional CNNs with a novel tree ensemble that takes the product of feature values, balancing the contradictory requirements of accurately classifying knowns and correctly rejecting unknowns in one network structure. A regularization strategy is proposed for UDN to further enhance its unknown rejection capacity.

heading: A Learning of UDN

text:
Learning Decision Nodes by Back-Propagation
Given a decision tree, the gradient of the loss L with respect to Θ can be decomposed by the chain rule as follows:
∂L ∂Θ (Θ, π;x, y) = ∑ n∈N ∂L(Θ, π;x, y) ∂fn(x; Θ) ∂fn(x; Θ) ∂Θ (11)
Here, the derivative of the second part ∂fn(x ;Θ)∂Θ is identical to the back-propagation process of traditional CNN modules and thus is omit here. Now let’s show how to compute the first part:
∂L(Θ, π;x, y) ∂fn(x; Θ) = ∂(−log(PT [y|x,Θ, π]) + βH(µ′(x|Θ))) ∂fn(x; Θ)
= ∂(−log(PT [y|x,Θ, π])
∂fn(x; Θ) + β ∂(H(µ′(x|Θ))) ∂fn(x; Θ))
(12)
where ∂(−log(PT [y|x,Θ, π])
∂fn(x; Θ) = − ∑ l∈L πly PT [y|x,Θ, π] ∂µl(x|Θ) ∂fn(x; Θ)
(13)
and ∑ l∈L ∂µl(x|Θ) ∂fn(x; Θ) = − ∑ l∈L µl(x|Θ) ∂log(µl(x|Θ)) ∂fn(x; Θ)
= − ∑ l∈L µl(x|Θ)(1l↙nd̄n(x; Θ)− 1l↘ndn(x; Θ))
= − ∑ l∈Lnl µl(x|Θ)d̄n(x; Θ) + ∑ l∈Lnr µl(x|Θ)dn(x; Θ)
(14)
By using the chain rule, we get:
∂(H(µ′(x|Θ))) ∂fn(x; Θ)) = ∑ l∈L ∂(H(µ′(x|Θ))) ∂(µ′l(x|Θ)) ∂(µ′l(x|Θ)) ∂(µl(x|Θ)) ∂(µl(x|Θ)) ∂fn(x; Θ))
(15)
where ∑ l∈L ∂(H(µ′(x|Θ))) ∂(µ′l(x|Θ)) = ∑ l∈L ∂(µ′l(x|Θ)log(µ′l(x|Θ))) ∂(µ′l(x|Θ))
= ∑ l∈L (1 + log(µ′l(x|Θ))) (16)
and ∑ l∈L ∂(µ′l(x|Θ)) ∂(µl(x|Θ)) = ∑ l∈L (sl(1− sl) + ∑ k 6=l slsk)
where
sl = eµl(x|Θ)∑ k∈L e µk(x|Θ)
Learning Prediction Nodes by Back-Propagation
Given a decision tree, the gradient of the Loss L w.r.t. the weights w of the prediction nodes (defined in Eq. 1) can be decomposed by the chain rule as follows:
∂L ∂w (Θ, π;x, y) = ∑ l∈L ∂L(Θ, π;x, y) ∂πl ∂πl ∂wl
(17)
where
∂L(Θ, π;x, y) ∂πly = − µl(x|Θ) PT [y|x,Θ, π]) (18)
and
∂πly ∂wli = { πly(1− πly) y = i −πlyπli y 6= i (19)
Therefore,
∂L(Θ, π;x, y) ∂wli = ∑ y∈Y ∂L(Θ, π;x, y) ∂πly ∂πly ∂wli
= ∂L(Θ, π;x, i)
∂πli
∂πli ∂wli + ∑ y 6=i ∂L(Θ, π;x, y) ∂πly ∂πly ∂wli
= −µl(x|Θ)(πli(1− πli)) PT [i|x,Θ, π]) + ∑ y 6=i µl(x|Θ)πlyπli PT [y|x,Θ, π])
(20)

heading: B CIFAR-100 Experiments

text:
Similar to the CIFAR-10 experiments, all methods use the same DenseNet (Huang et al., 2017) architecture to ODIN (Liang et al., 2018). For our UDN and UDN-Penalty, the output is connected to 10 trees. The depth of each tree is 6. Again, for the evaluation of ODIN, we directly use the model published by the authors. The temperature parameter T and the perturbation magnitude η used by ODIN are set to 1000 and 0.0014, as recommended by the authors. We set the drop rate of MC-Dropout as 0.2 after parameter tuning and set the number of forward passes as 100 as suggested by the authors.
In this set of experiments we use the images in CIFAR-10 and SVHN as the unknowns. Moreover, we also randomly pick 10 classes from the CIFAR-100 training data. We then use these samples as unknowns and test them on the model trained using the rest of the
CIFAR-100 training data. We run this process for 10 times and report the average TNR and AUROC.
As shown in Table 2, our UDN significantly outperform other methods in all cases by at least 9 points in TNR and 5 points in AUROC.

heading: C SVHN Experiments

text:
Same to the CIFAR-100 experiments above, we tested all approaches based on the same DenseNet architecture. For our UDN and UDN-Penalty, the output is connected to 10 trees. The depth of each tree is 4. For ODIN, the temperature parameter T and the perturbation magnitude η used by ODIN are set to 1000 and 0.0014 after parameter tuning. We set the drop rate of MC-Dropout as 0.5 and the number of forward passes as 100 as suggested by the authors.
We use the images in CIFAR-10 and CIFAR-100 as the unknowns. At the same time we also randomly pick 1 classes from the SVHN training data and use these samples as unknowns. We then test them on the model trained using the rest of the SVHN training data. We run this process for 10 times and report the average TNR and AUROC.
As shown in Table 3, in all cases our UDN outperform other methods in both TNR and AUROC. In particular, UDN outperforms all other methods by at least 12 points in TNR.

heading: D Parameter Tuning

text: In our UDN, The key hyper-parameters are the number of PR subnets and the depth of the binary tree. In general, the depth of the tree depends on the number of the classes. The more classes the dataset has, the higher the tree should be. In our experiments, when the depth of the tree is no smaller than 6 and the number of PR subnet is above 10, our method works well in general. When the number of classes in the training data is small such as MINIST and CIFAR-10, setting the depth of the three as a smaller value such as 4 also works. But a larger depth of the tree or more subnets does not harm the effectiveness of our UDN method. Therefore, these parameters are easy to tune.

title: Unknown-Aware Deep Neural Network