{'fraction_non_alphanumeric': 0.036853328388651956, 'fraction_numerical': 0.010708325607268681, 'mean_word_length': 4.570100697134005, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 6, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Selective Classification for Deep Neural Networks

Selective classification techniques (also known as reject option) have not yet been considered in the context of deep neural networks (DNNs). These techniques can potentially significantly improve DNNs prediction performance by trading-off coverage. In this paper we propose a method to construct a selective classifier given a trained neural network. Our method allows a user to set a desired risk level. At test time, the classifier rejects instances as needed, to grant the desired risk (with high probability). Empirical results over CIFAR and ImageNet convincingly demonstrate the viability of our method, which opens up possibilities to operate DNNs in mission-critical applications. For example, using our method an unprecedented 2% error in top-5 ImageNet classification can be guaranteed with probability 99.9%, and almost 60% test coverage.


Introduction
While self-awareness remains an illusive, hard to define concept, a rudimentary kind of selfawareness, which is much easier to grasp, is the ability to know what you don't know, which can make you smarter. The subfield dealing with such capabilities in machine learning is called selective prediction (also known as prediction with a reject option), which has been around for 60 years [1,5]. The main motivation for selective prediction is to reduce the error rate by abstaining from prediction when in doubt, while keeping coverage as high as possible. An ultimate manifestation of selective prediction is a classifier equipped with a "dial" that allows for precise control of the desired true error rate (which should be guaranteed with high probability), while keeping the coverage of the classifier as high as possible.
Many present and future tasks performed by (deep) predictive models can be dramatically enhanced by high quality selective prediction. Consider, for example, autonomous driving. Since we cannot rely on the advent of "singularity", where AI is superhuman, we must manage with standard machine learning, which sometimes errs. But what if our deep autonomous driving network were capable of knowing that it doesn't know how to respond in a certain situation, disengaging itself in advance and alerting the human driver (hopefully not sleeping at that time) to take over? There are plenty of other mission-critical applications that would likewise greatly benefit from effective selective prediction.
The literature on the reject option is quite extensive and mainly discusses rejection mechanisms for various hypothesis classes and learning algorithms, such as SVM, boosting, and nearestneighbors [8,13,3]. The reject option has rarely been discussed in the context of neural networks (NNs), and so far has not been considered for deep NNs (DNNs). Existing NN works consider a cost-based rejection model [2,4], whereby the costs of misclassification and abstaining must be specified, and a rejection mechanism is optimized for these costs. The proposed mechanism for classification is based on applying a carefully selected threshold on the maximal neuronal response of the softmax layer. We that call this mechanism softmax response (SR). The cost model can be very useful when we can quantify the involved costs, but in many applications of interest meaningful costs are hard to reason. (Imagine trying to set up appropriate rejection/misclassification costs for disengaging an autopilot driving system.) Here we consider the alternative risk-coverage view for selective classification discussed in [5].
Ensemble techniques have been considered for selective (and confidence-rated) prediction, where rejection mechanisms are typically based on the ensemble statistics [18,7]. However, such techniques are presently hard to realize in the context of DNNs, for which it could be very costly to train sufficiently many ensemble members. Recently, Gal and Ghahramani [9] proposed an ensemble-like method for measuring uncertainty in DNNs, which bypasses the need to train several ensemble members. Their method works via sampling multiple dropout applications of the forward pass to perturb the network prediction randomly. While this Monte-Carlo dropout (MC-dropout) technique was not mentioned in the context of selective prediction, it can be directly applied as a viable selective prediction method using a threshold, as we discuss here.
In this paper we consider classification tasks, and our goal is to learn a selective classifier (f, g), where f is a standard classifier and g is a rejection function. The selective classifier has to allow full guaranteed control over the true risk. The ideal method should be able to classify samples in production with any desired level of risk with the optimal coverage rate. It is reasonable to assume that this optimal performance can only be obtained if the pair (f, g) is trained together. As a first step, however, we consider a simpler setting where a (deep) neural classifier f is already given, and our goal is to learn a rejection function g that will guarantee with high probability a desired error rate. To this end, we consider the above two known techniques for rejection (SR and MC-dropout), and devise a learning method that chooses an appropriate threshold that ensures the desired risk. For a given classifier f , confidence level δ, and desired risk r * , our method outputs a selective classifier (f, g) whose test error will be no larger than r * with probability of at least 1 − δ.
Using the well-known VGG-16 architecture, we apply our method on CIFAR-10, CIFAR-100 and ImageNet (on ImageNet we also apply the RESNET-50 architecture). We show that both SR and dropout lead to extremely effective selective classification. On both the CIFAR datasets, these two mechanisms achieve nearly identical results. However, on ImageNet, the simpler SR mechanism is significantly superior. More importantly, we show that almost any desirable risk level can be guaranteed with a surprisingly high coverage. For example, an unprecedented 2% error in top-5 ImageNet classification can be guaranteed with probability 99.9%, and almost 60% test coverage.

Problem Setting
We consider a standard multi-class classification problem. Let X be some feature space (e.g., raw image data) and Y, a finite label set, Y = {1, 2, 3, . . . , k}, representing k classes. Let P (X, Y ) be a distribution over X × Y. A classifier f is a function f : X → Y, and the true risk is a given loss function, for example the 0/1 error. Given a labeled set [5] is a pair (f, g), where f is a classifier, and g : X → {0, 1} is a selection function, which serves as a binary qualifier for f as follows, Thus, the selective classifier abstains from prediction at a point x iff g(x) = 0. The performance of a selective classifier is quantified using coverage and risk. Fixing P , coverage, defined to be φ(f, g) = ∆ E P [g(x)], is the probability mass of the non-rejected region in X . The selective risk of f, g) is Clearly, the risk of a selective classifier can be traded-off for coverage. The entire performance profile of such a classifier can be specified by its risk-coverage curve, defined to be risk as a function of coverage [5]. Consider the following problem. We are given a classifier f , a training sample S m , a confidence parameter δ > 0, and a desired risk target r * > 0. Our goal is to use S m to create a selection function g such that the selective risk of (f, g) satisfies where the probability is over training samples, S m , sampled i.i.d. from the unknown underlying distribution P . Among all classifiers satisfying (2), the best ones are those that maximize the coverage.

Selection with Guaranteed Risk Control
In this section, we present a general technique for constructing a selection function with guaranteed performance, based on a given classifier f , and a confidence-rate function κ f : X → R + for f . We do not assume anything on κ f , and the interpretation is that κ can rank in the sense that if , for x 1 , x 2 ∈ X , the confidence function κ f indicates that the confidence in the prediction f (x 2 ) is not higher than the confidence in the prediction f (x 1 ). In this section we are not concerned with the question of what is a good κ f (which is discussed in Section 4); our goal is to generate a selection function g, with guaranteed performance for a given κ f . For the reminder of this paper, the loss function is taken to be the standard 0/1 loss function (unless explicitly mentioned otherwise).
be a training set, assumed to be sampled i.i.d. from an unknown distribution P (X, Y ). Given also are a confidence parameter δ > 0, and a desired risk target r * > 0. Based on S m , our goal is to learn a selection function g such that the selective risk of the classifier (f, g) satisfies (2).
For θ > 0, we define the selection function g θ : X → {0, 1} as For any selective classifier (f, g), we define its empirical selective risk with respect to the labeled sample S m ,r The selection with guaranteed risk (SGR) learning algorithm appears in Algorithm 1. The algorithm receives as input a classifier f , a confidence-rate function κ f , a confidence parameter δ > 0, a target risk r * , and a training set S m . The algorithm performs a binary search to find the optimal bound guaranteeing the required risk with sufficient confidence. The SGR algorithm outputs a selective classifier (f, g) and a risk bound b * . In the rest of this section we analyze the SGR algorithm. We make use of the following lemma, which gives the tightest possible numerical generalization bound for a single classifier, based on a test over a labeled sample.

Algorithm 1 Selection with Guaranteed Risk (SGR)
1: SGR(f ,κ f ,δ,r * ,S m ) 2: Sort S m according to κ f (x i ), x i ∈ S m (and now assume w.l.o.g. that indices reflect this ordering). 3: z min = 1; z max = m 4: for i = 1 to k = ∆ log 2 m do 5: We emphasize that the numerical bound of Lemma 3.1 is the tightest possible in this setting. As discussed in [10], the analytic bounds derived using, e.g., Hoeffding inequality (or other concentration inequalities), approximate this numerical bound and incur some slack. For any selection function, g, let P g (X, Y ) be the projection of P over g; that is, P g (X, Y ) = ∆ P (X, Y |g(X) = 1). The following theorem is a uniform convergence result for the SGR procedure.
The sampling distribution of m i labeled examples in SGR is determined by the following process: sample a set S m of m examples from the product distribution P m and then use g i to filter S m , resulting in a (randon) number m i of examples. Therefore, the left-hand side of (5) equals Clearly, Therefore, An application of the union bound completes the proof.

Confidence-Rate Functions for Neural Networks
Consider a classifier f , assumed to be trained for some unknown distribution P . In this section we consider two confidence-rate functions, κ f , based on previous work [9,2]. We note that an ideal confidence-rate function κ f (x) for f , should reflect true loss monotonicity. Given (x 1 , y 1 ) ∼ P and (x 2 , y 2 ) ∼ P , we would like the following to hold: Obviously, one cannot expect to have an ideal κ f . Given a confidence-rate functions κ f , a useful way to analyze its effectiveness is to draw the risk-coverage curve of its induced rejection function, g θ (x|κ f ), as defined in (3). This risk-coverage curve shows the relationship between θ and R(f, g θ ). For example, see Figure 2(a) where a two (nearly identical) risk-coverage curves are plotted. While the confidence-rate functions we consider are not ideal, they will be shown empirically to be extremely effective. 1 The first confidence-rate function we consider has been around in the NN folklore for years, and is explicitly mentioned by [2,4] in the context of reject option. This function works as follows: given any neural network classifier f (x) where the last layer is a softmax, we denote by f (x|j) the soft response output for the jth class. The confidence-rate function is defined as κ = ∆ max j∈Y (f (x|j)). We call this function softmax response (SR).
Softmax responses are often treated as probabilities (responses are positive and sum to 1), but some authors criticize this approach [9]. Noting that, for our purposes, the ideal confidence-rate function should only provide coherent ranking rather than absolute probability values, softmax responses are potentially good candidates for relative confidence rates.
We are not familiar with a rigorous explanation for SR, but it can be intuitively motivated by observing neuron activations. For example, Figure 1 depicts average response values of every neuron in the second-to-last layer for true positives and false positives for the class '8' in the MNIST dataset (and qualitatively similar behavior occurs in all MNIST classes). The x-axis corresponds to neuron indices in that layer (1-128); and the y-axis shows the average responses, where green squares are averages of true positives, boldface squares highlight strong responses, and red circles correspond to the average response of false positives. It is evident that the true positive activation response in the active neurons is much higher than the false positive, which is expected to be reflected in the final softmax layer response. Moreover, it can be seen that the large activation values are spread over many neurons, indicating that the confidence signal arises due to numerous patterns detected by neurons in this layer. Qualitatively similar behavior can be observed in deeper layers.
The MC-dropout technique we consider was recently proposed to quantify uncertainty in neural networks [9]. To estimate uncertainty for a given instance x, we run a number of feedforward iterations over x, each applied with dropout in the last fully connected layer. Uncertainty is taken as the variance in the responses of the neuron corresponding to the most probable class. We consider minus uncertainty as the MC-dropout confidence rate.

Empirical Results
In Section 4 we introduced the SR and MC-dropout confidence-rate function, defined for a given model f . We trained VGG models [17] for CIFAR-10, CIFAR-100 and ImageNet. For each of these models f , we considered both the SR and MC-dropout confidence-rate functions, κ f , and the induced rejection function, g θ (x|κ f ). In Figure 2 we present the risk-coverage curves obtained for each of the three datasets. These curves were obtained by computing a validation risk and coverage for many θ values. It is evident that the risk-coverage profile for SR and MC-dropout is nearly identical for both the CIFAR datasets. For the ImageNet set we plot the curves corresponding to top-1 (dashed curves) and top-5 tasks (solid curves). On this dataset, we see that SR is significantly better than MC-dropout on both tasks. For example, in the top-1 task and 60% coverage, the SR rejection has 10% error while MC-dropout rejection incurs more than 20% error. But most importantly, these risk-coverage curves show that selective classification can potentially be used to dramatically reduce the error in the three datasets. Due to the relative advantage of SR, in the rest of our experiments we only focus on the SR rating. We now report on experiments with our SGR routine, and apply it on each of the datasets to construct high probability risk-controlled selective classifiers for the three datasets.

Selective Guaranteed Risk for CIFAR-10
We now consider CIFAR-10; see [14] for details. We used the VGG-16 architecture [17] and adapted it to the CIFAR-10 dataset by adding massive dropout, exactly as described in [15]. We used data augmentation containing horizontal flips, vertical and horizontal shifts, and rotations, and trained using SGD with momentum of 0.9, initial learning rate of 0.1, and weight decay of 0.0005. We multiplicatively dropped the learning rate by 0.5 every 25 epochs, and trained for 250 epochs. With this setting we reached validation accuracy of 93.54, and used the resulting network f 10 as the basis for our selective classifier.
We applied the SGR algorithm on f 10 with the SR confidence-rating function, where the training set for SGR, S m , was taken as half of the standard CIFAR-10 validation set that was randomly split to two equal parts. The other half, which was not consumed by SGR for training, was reserved for testing the resulting bounds. Thus, this training and test sets where each of approximately 5000 samples. We applied the SGR routine with several desired risk values, r * , and obtained, for each such r * , corresponding selective classifier and risk bound b * . All our applications of the SGR routine (for this dataset and the rest) where with a particularly small confidence level δ = 0.001. 2 We then applied these selective classifiers on the reserved test set, and computed, for each selective classifier, test risk and test coverage. The results are summarized in Table 1, where we also include train risk and train coverage that were computed, for each selective classifier, over the training set.
Observing the results in Table 1, we see that the risk bound, b * , is always very close to the the target risk, r * . Moreover, the test risk is always bounded above by the bound b * , as required. Finally, we see that it is possible to guarantee with this method amazingly small 1% error while covering more than 78% of the domain.

Selective Guaranteed Risk for CIFAR-100
Using the same VGG architechture (now adapted to 100 classes) we trained a model for CIFAR-100 while applying the same data augmentation routine as in the CIFAR-10 experiment. Following precisly the same experimental design as in the CFAR-10 case, we obtained the results of Table 2 Here again, SGR generated tight bounds, very close to the desired target risk, and the bounds were never violated by the true risk. Also, we see again that it is possible to dramatically reduce the risk with only moderate compromise of the coverage. While the architecture we used is not state-of-the art, with a coverage of 67%, we easily surpassed the best known result for CIFAR-100, which currently stands on 18.85% using the wide residual network architecture [19]. It is very likely that by using ourselves the wide residual network architecture we could obtain significantly better results.

Selective Guaranteed Risk for ImageNet
We used an already trained Image-Net VGG-16 model based on ILSVRC2014 [16]. We repeated the same experimental design but now the sizes of the training and test set were approximately 25,000. The SGR results for both the top-1 and top-5 classification tasks are summarized in Tables 3 and 4, respectively. We also implemented the RESNET-50 architecture [12] in order to see if qualitatively similar results can be obtained with a different architecture. The RESNET-50 results for ImageNet top-1 and top-5 classification tasks are summarized in Tables 5 and 6, respectively. These results show that even for the challenging mageNet, with both the VGG and RESNET architectures, our selective classifiers are extremely effective, and with appropriate coverage compromise, our classifier easily surpasses the best known results for ImageNet. Not surprisingly, RESNET, which is known to achieve better results than VGG on this set, preserves its relative advantage relative to VGG through all r * values.

Concluding Remarks
We presented an algorithm for learning a selective classifier whose risk can be fully controlled and guaranteed with high confidence. Our empirical study validated this algorithm on challenging image classification datasets, and showed that guaranteed risk-control is achievable. Our methods can be immediately used by deep learning practitioners, helping them in coping with missioncritical tasks. We believe that our work is only the first significant step in this direction, and many research questions are left open. The starting point in our approach is a trained neural classifier f (supposedly trained to optimize risk under full coverage). While the rejection mechanisms we considered were extremely effective, it might be possible to identify superior mechanisms for a given classifier f . We believe, however, that the most challenging open question would be to simultaneously train both the classifier f and the selection function g to optimize coverage for a given risk level. Selective classification is intimately related to active learning in the context of linear classifiers [6,11]. It would be very interesting to explore this potential relationship in the context of (deep) neural classification. In this paper we only studied selective classification under the 0/1 loss. It would be of great importance to extend our techniques to other loss functions and specifically to regression, and to fully control false-positive and false-negative rates. This work has many applications. In general, any classification task where a controlled risk is critical would benefit by using our methods. An obvious example is that of medical applications where utmost precision is required and rejections should be handled by human experts. In such applications the existence of performance guarantees, as we propose here, is essential. Financial investment applications are also obvious, where there are great many opportunities from which one should cherry-pick the most certain ones. A more futuristic application is that of robotic sales representatives, where it could extremely harmful if the bot would try to answer questions it does not fully understand.