Title: CAUTIOUS DEEP LEARNING

Abstract: Most classifiers operate by selecting the maximum of an estimate of the conditional distribution p(y|x) where x stands for the features of the instance to be classified and y denotes its label. This often results in a hubristic bias: overconfidence in the assignment of a definite label. Usually, the observations are concentrated on a small volume but the classifier provides definite predictions for the entire space. We propose constructing conformal prediction setsVovk et al. ( 2005) which contain a set of labels rather than a single label. These conformal prediction sets contain the true label with probability 1 -α. Our construction is based on p(x|y) rather than p(y|x) which results in a classifier that is very cautious: it outputs the null set -meaning "I don't know" -when the object does not resemble the training examples. An important property of our approach is that classes can be added or removed without having to retrain the classifier. We demonstrate the performance on the ImageNet ILSVRC dataset and the CelebA and IMDB-Wiki facial datasets using high dimensional features obtained from state of the art convolutional neural networks.

1. INTRODUCTION:

We consider multiclass classification with a feature space X and labels Y = {1, . . . , k} . Given the training data (X 1 , Y 1 ), . . . , (X n , Y n ), the usual goal is to find a prediction function F : X -→ Y with low classification error P (Y = F (X)) where (X, Y ) is a new observation of an input-output pair. This type of prediction produces a definite prediction even for cases that are hard to classify.

In this paper we use conformal predictionVovk et al. (2005) where we estimate a set-valued function C : X -→ 2 Y with the guarantee that P (Y ∈ C (X)) ≥ 1 -α for all distributions P . This is a distribution-free confidence guarantee. Here, 1 -α is a user-specified confidence level. We note that the "classify with a reject option" Herbei & Wegkamp (2006) also allows set-valued predictions but does not give a confidence guarantee.

The function C can sometimes output the null set. That is, C(x) = ∅ for some values of x. This allows us to distinguish two types of uncertainty. When C(x) is a large set, there are many possible labels consistent with x. But when x does not resemble the training data, we will get C(x) = ∅ alerting us that we have not seen examples like this so far.

There are many ways to construct conformal prediction sets. Our construction is based on finding an estimate p(x|y) of p(x|y). We then find an appropriate scalar t y and we set C(x) = {y : p(x|y) > t y }. The scalars are chosen so that P (Y ∈ C(X)) ≥ 1 -α. We shall see that this construction works well when there is a large number of classes as is often the case in deep learning classification problems. This guarantees that x's with low probability -that is regions where we have not seen training data -get classified as ∅.

An important property of this approach is that p(x|y) can be estimated independently for each class. Therefore, x is predicted to a given class in a standalone fashion which enables adding or removing classes without the need to retrain the whole classifier. In addition, we empirically demonstrate that the method we propose is applicable to large-scale high-dimensional data by applying it to the ImageNet ILSVRC dataset and the CelebA and IMDB-Wiki facial datasets using features obtained from state of the art convolutional neural networks.

Paper Outline. In section 2 we discuss the difference between p(y|x) and p(x|y). In section 3 we provide an example to enlighten our motivation. In section 4 we present the general framework of conformal prediction and survey relevant works in the field. In section 5 we formally present our method. In section 6 we demonstrate the performance of the proposed classifier on the ImageNet challenge dataset using state of the convolutional neural networks. In section 7 we consider the problem of gender classification from facial pictures and show that even when current classifiers fails to generalize from CelebA dataset to IMDB-Wiki dataset, the proposed classifier still provides sensible results. Section 8 contains our discussion and concluding remarks. The Appendix in the supplementary material contains some technical details.

Related Work.:

There is an enormous literature on set-valued prediction. Here we only mention some of the most relevant references. The idea of conformal prediction originates from Vovk et al. (2005) . There is a large followup literature due to Vovk and his colleagues which we highly recommend for the interested readers. Statistical theory for conformal methods was developed in Lei (2014) ; Lei et al. (2013) ; Lei & Wasserman (2014) , and the multiclass case was studied in Sadinle et al. (2017) where the goal was to develop small prediction sets based on estimating p(y|x). The authors of that paper tried to avoid outputting null sets. In this paper, we use this as a feature, similarly to Vovk et al. (2003) . Finally, we mention a related but different technique called classification with the "reject option" Herbei & Wegkamp (2006) . This approach permits one to sometimes refrain from providing a classification but it does not aim to give confidence guarantees.

2. p(y|x) VERSUS p(x|y):

Most classifiers -including most conformal classifiers -are built by estimating p(y|x). Typically one sets the predicted label of a new x to be f (x) = arg max y∈Y { p(y|x)}. Since p(y|x) = p(x|y)p(y)/p(x) the prediction involves the balance between p(y) and p(x|y). Of course, in the special case p(y) = 1/k for all y, we have arg max y∈Y {p(y|x)} = arg max y∈Y {p(x|y)}.

However, for set-valued classification, p(y|x) can be negatively affected by p(y) and p(x|y). Indeed, in this case there are significant advantages to using p(x|y) to construct the classifier. Taking p(y) into account ties the prediction of an observation x with the likelihood of observing that class. Since there is no restriction on the number of classes, ultimately an observation should be predicted to a class regardless of the class popularity. Normalizing by p(x) makes the classifier oblivious to the probability of actually observing x. When p(x) is extremely low (an outlier), p(y|x) still selects the most likely label out of all tail events. In practice this may result with most of the space classified with high probability to a handful of classes almost arbitrarily despite the fact that the classifier has been presented with virtually no information in those areas of the space. This approach might be necessary if a single class has to be selected ∀x ∈ X . However, if this is not the case, then a reasonable prediction for an x with small p(x) is the null set.

There are also conformal methods utilizing p(y|x) to predict a set of classes (Sadinle et al., 2017; Vovk et al., 2003) . This methods does not overcome the inherent weakness within p(y|x). As will be explained later on, the essence of this methods is to classify x to C (x) = {y | P (y | x) ≥ t} for some threshold t. Due to the nature of p(y|x) the points which are most likely to be predicted as the null set are when P (y = j|x) = 1 k , for all classes j ∈ Y. But this is exactly the points in space for which any set valued prediction should predict all class as possible.

As we shall see, conformal predictors based on p(x|y) can overcome all these issues.

3. MOTIVATING EXAMPLE -IRIS DATASET:

The Iris flower data set is a benchmark dataset often used to demonstrate classification methods. It contains four features that were measured from three different Iris species. In this example, for visualization purposes, we only use two features: the sepal and petal lengths in cm.

Figure 1 shows the decision boundaries for this problem comparing the results of (a) K-nearest neighbors (KNN), (b) support vector machines with the RBF kernel (SVM) and (c) our conformal prediction method using an estimate p(x|y).

Both the KNN and the SVM methods provide sensible boundaries between the class where there are observations. In areas with low density p(x) the decision boundaries are significantly different. The SVM classifies almost all of the space to a single class. The KNN creates an infinite strip bounded between two (almost affine) half spaces. In a hubristic manner, both methods provide very different predictions with probability near one without sound justification.

The third plot shows the conformal set C(x) = {y : p(x|y) > t y } where the t y is chosen as described in Section 5. The result is a cautious prediction. If a new X falls into a region with little training data then we output ∅. In such cases our proposed method modestly avoids providing any claim.

4. CONFORMAL PREDICTION:

Let (X 1 , Y 1 ), . . . , (X n , Y n ) be n independent and identically distributed (iid) pairs of observations from a distribution P . In set-valued supervised prediction, the goal is to find a set-valued function

EQUATION

where (X, Y ) denotes a new pair of observations. Conformal prediction -a method created by Vovk and collaborators Vovk et al. (2005) -provides a general approach to construct prediction sets based on the observed data without any distributional assumptions. The main idea is to construct a conformal score, which is a real-valued, permutationinvariant function ψ(z, D) where z = (x, y) and D denotes the training data. Next we form an augmented dataset Vovk et al. (2005) proves that P (Y ∈ C(X)) ≥ 1 -α for all distributions P . There is a great flexibility in the choice of conformity score and 4.1 discusses important examples.

D = {(X 1 , Y 1 ), . . . , (X n , Y n ), (X n+1 , Y n+1 )} where (X n+1 , Y n+1 ) is set equal to arbitrary values (x, y). We then define R i = ψ((X i , Y i ), D ) for i = 1, . . . , n + 1. We test the hypothesis H 0 : Y = y that the new label Y is equal to y using the p-value π(x, y) = 1/(n + 1) n+1 i=1 I(R i ≥ R n+1 ). Then we set C(x) = {y : π(x, y) ≥ α}.

As described above, it is computationally expensive to construct C(x) since we must re-compute the entire set of conformal scores for each choice of (x, y). This is especially a problem in deep learning applications where training is usually expensive. One possibility for overcoming the computational burden is based on data splitting where p(x|y) is estimated from part of the data and the conformal scores are estimated from the remaining data; see Vovk (2015) ; Lei & Wasserman (2014) . Another approach is to construct the scores from the original data without augmentation. In this case, we no longer have the finite sample guarantee P (Y ∈ C(X)) ≥ 1 -α for all distributions P , but we do get the asymptotic guarantee P (Y ∈ C(X)) ≥ 1 -α -o P (1) as long as some conditions are satisfied1 . See Sadinle et al. (2017) for further discussion on this point.

4.1. EXAMPLES:

Here are several known examples for conformal methods used on different problems.

Supervised Regression. Suppose we are interested in the supervised regression problem. Let f : X → Y be any regression function learned from training data. Let i denote the residual error of f on the observation i, that is,

i = | f (X i ) -Y i |. Now we form the ordered residuals (1) ≤ • • • ≤ (n)

, and then define 

C(x) = y : | f (x) -y| ≤ ( (1-α)•n ) . If f is a consistent estimator of E[Y |X = x] then P (Y ∈ C(X)) = 1 -α + o P (1

R i = p (Y i | X i )

, where p is any consistent estimator of p(y|x). They defined the minimal ambiguity as A (C) = E (|C (X)|) which is the expected size of the prediction set. They proved that out of all the classifiers achieving the desired 1 -α coverage, this solution minimizes the ambiguity. In addition, the paper considers class specific coverage controlling for every class

P (Y ∈ C (X) | Y = y) ≥ 1 -α y .

Universal Predictor. Vovk et al Vovk et al. (2003 )Sadinle et al. (2017) introduce the concept of universal predictor and provide an explicit way to construct one. A universal predictor is the classifier that produces, asymptotically, no more multiple prediction than any other classifier achieving 1 -α level coverage. In addition, within the family of all 1 -α classifiers that produce the minimal number of multiple predictions it also asymptotically obtains at least as many null predictions.

5. THE METHOD:



5.1. THE CLASSIFIER:

Let p(x|y) be an estimate of the density p(x|y) for class Y = y. Define t y to be the empirical 1 -α quantile of the values { p(X i |y)}. That is,

EQUATION

where n y = i I(Y i = y). Assuming that n y → ∞ and minimal conditions on p(x|y) and p(x|y), it can be shown that t y P → t y where t y is the largest t such that y>t p(x|y)dx ≥ 1 -α. See Cadre et al. ( 2009) and Lei et al. (2013) . We set C(x) = {y : p(x|y) ≥ t y }. We then have the following proposition which is proved in the appendix.

Proposition 1 Assume the conditions in Cadre et al. (2009) stated also in the appendix. Let (X, Y )

be a new observation. Then

|P (Y ∈ C(X)) -(1 -α)| P → 0 as min y n y → ∞.

An exact, finite sample method can be obtained using data splitting. We split the training data into two parts. Construct p(x|y) from the first part of the data. Now evaluate { p(X i |y)} on the second part of the data and define t y using these values. We then set C(x) = {y : p(x|y) ≥ t y }. We then have:

Proposition 2 Let (X, Y ) be a new observation. Then, for every distribution and every sample size,

P (Y ∈ C(X)) ≥ 1 -α.

This follows from the theory in Lei & Wasserman (2014) . The advantage of the splitting approach is that there are no conditions on the distribution, and the confidence guarantee is finite sample.

There is no large sample approximation. The disadvantage is that the data splitting can lead to larger prediction sets. Algorithm 1 describes the training, and Algorithm 2 describes the prediction. 

5.2. CLASS ADAPTIVITY:

As algorithms 1 and 2 demonstrate, the training and prediction of each class is independent from all other classes. This makes the method adaptive to addition and removal of classes ad-hoc. Intuitively speaking, if there is 1 -α probability for the observation to be generated from the class it will be classified to the class regardless of any other information.

Another desirable property of the method is that it is possible to obtain different coverage levels per class if the task requires that. This is achieved by setting t y to be the 1 -α y quantile of the values { p(X i |y)}.

5.3. DENSITY ESTIMATION:

The density p(x|y) has to be estimated from data. We use the standard kernel density estimation method, which was shown to be optimal in the conformal setting under weak conditions in Lei, Robins and Wasserman Lei et al. (2013) .

Density estimation in high dimensions is a difficult problem. Nonetheless, as we will show in the numerical experiments (Section 6), the proposed method works well in these tasks as well. An intuitive reason for this could be that the accuracy of the conformal prediction does not actually require p(x|y) to be close to p(x|y) in L 2 . Rather, all we need is that the ordering imposed by p(x|y) approximates the ordering defined by p(x|y). Specifically, we only need that {(x, x ) : p(x|y) > p(x |y) + ∆} is approximated by {(x, x ) : p(x|y) > p(x |y) + ∆} for ∆ > 0. We call this "ordering consistency." This is much weaker than the usual requirement that ( p(x|y) -p(x|y)) 2 dx be small. This new definition and implications on the approximation of p (x | y) will be further expanded in future work.

6. IMAGENET CHALLENGE EXAMPLE:

The ImageNet Large Scale Visual Recognition Challenge (ILSVRC) Deng et al. (2009) is a large visual dataset of more than 1.2 million images labeled across 1, 000 different classes. It is considered a large scale complex visual dataset that reflects object recognition state-of-the-art through a yearly competition.

In this example we apply our conformal image classification method to the ImageNet dataset. We remove the last layer from the pretrained Xception convolutional neural network Chollet (2016) and use it as a feature extractor. Each image is represented as a 2, 048 dimensional feature in R 2048 . We learn for each of the 1, 000 classes a unique kernel density estimator trained only on images within the training set of the given class. When we evaluate results of standard methods we use the For conformal methods the confidence level is predefined. The method calibrates the number of classes in the prediction sets to satisfy the desired accuracy level. The the main component affecting the results is the hyperparameter α. For small values of α the accuracy will be high but so does the number of classes predicted for every observation. For large values of α more observations are predicted as the null set and less observations predicted per class. Figure 2 (a) presents the trade-off between the α level and the number of classes and the proportion of null set predictions for this example. For example 0.5, accuracy would require on average 2.7 predictions per observation and 0.252 null set predictions. The actual selection of the proper α value is highly dependent on the task. As discussed earlier, a separate α y for each class can also be used to obtain different accuracy per class.

Figures 2 (b ) and (c) show illustrative results from the ImageNet validation set. (b) presents a picture of a "Barber Shop". When α = 0.6 the method correctly suggests the right class in addition to several other relevant outcomes such as "Bakery". When α = 0.8 only the "Barber Shop" remains. (c) show a "Brain Coral". For α = 0.6 the method still suggests classes which are clearly wrong. As α increases the number of classes decrease and for α = 0.8 only "Brain Coral" and "Coral Reef " remains, both which are relevant. At α = 0.9 "Coral Reef " remains, which represents a misclassification following from the fact that the class threshold is lower than that of "Brain Coral". Eventually at α = 0.95 the null set is predicted for this picture.

Figure 5 shows a collage of 20 images using α = 0.7. To avoid selection bias we've selected the first 20 images in the ImageNet validation set.

6.1 OUTLIERS Figure 3 (a) shows the outcome when the input is random noise. We set the threshold α = 0.01. This gives a less conservative classifier that should have the largest amount of false positives. Even with such a low threshold all 100 random noise images over 1, 000 categories are correctly flagged as 2017) results with a top prediction average of 0.0836 (with 0.028 standard error) to "Kite" and 0.0314 (0.009) to "Envelope". The top-5 classes together has mean probability of 0.196, much higher than the uniform distribution expected for prediction of random noise. Testing 11 different paintings with α = 0.5 all result with the null set. When testing the Inception-v4 model output, 7/11 paintings are classified with probability greater than 0.5 to either "Coil", "Ant", "Poncho", "Spider Web" and "Rapeseed" depending on the image. We train a standard convolutional neural network (5 convolution and 2 dense layers with the corresponding pooling and activation layers) to perform gender classification on CelebA. It converges well obtaining 0.963 accuracy on a held out test set, but fails to generalize to the IMDB-Wiki dataset achieving 0.577 accuracy, slightly better than a random guess. The discrepancy between the two datasets follows from the fact that facial images are reliant on preprocessing to standardize the input.

We have used the default preprocessing provided by the datasets, to reflect a scenario in which the distribution of the samples changes between the training and the testing. Although the standard classification method fails in this scenario, the conformal method suggested in this paper still offers valid and sensible results both on CelebA and IMDB-Wiki when using the features extracted from the network trained on CelebA. perform well for this dataset. The level of accuracy is roughly 1 -α as expected by the design, while the proportion of null predictions is roughly α. Therefore for all α there are almost no false positives and all of the errors are the null set.

The IMDB-Wiki results are not as good, but better than naively using a 0.577 accuracy classifier. Figure 4 (c) show the classifier performance as a function of α. Both the accuracy and the number of false positives are tunable. For high values of 1-α the accuracy is much higher than 0.577, but would results in a large number of observations predicted as both genders. If cautious and conservative prediction is required small values of 1 -α would guarantee smaller number of false predictions, but a large number of null predictions. The suggested conformal method provide a hyper-parameter controlling which type of errors are created according to the prediction needs, and works even in cases where standard methods fail.

8. DISCUSSION:

In this paper we showed that conformal, set-valued predictors based on p(x|y) have very good properties. We obtain a cautious prediction associating an observation with a class only if the there is high probability of that observation is generated from the class. In most of the space the classifier predicts the null set. This stands in contrast to standard solutions which provide confident predictions for the entire space based on data observed from a small area. This can be useful when a large number of outliers are expected or in which the distribution of the training data won't fully describe the distribution of the observations when deployed. Examples of such, are object recognition systems used online continuously in real life. We also obtain a large set of labels in the set when the object is ambiguous and is consistent with many different classes. Thus, our method quantifies two types of uncertainty: ambiguity with respect to the given classes and outlyingness with respect to the given classes.

In addition, the conformal framework provides our method with its coverage guarantees and class adaptivity. It is straightforward to add and remove classes at any stage of the process while controlling either the overall or class specific coverage level of the method in a highly flexible manner. This desired properties comes with a price. The distribution of p(x|y) for each class is learned independently and the decision boundaries are indifferent to data not within the class. This might lead to decision boundaries which are inferior to current methods if the only goal is to distinguish between classes which are fully described by the training data. Alternative methods to learn p(x|y) taking all the training data into account might overcome this limitation and can be the focus of future investigations.

During the deployment of the method, evaluation of a large number of kernel density estimators is required. This is relatively slow compared to current methods. This issue can be addressed in future research with more efficient ways to learn ordering-consistent approximations of p(x|y) that can be deployed on GPU's.

:

A sequence of random variables X1, X2, . . . , is op (1) if ∀ > 0, limn→∞ P (|Xn| ≥ ) = 0.

Figures and Tables:

Figure 1: Classification boundaries for different methods for the Iris dataset. For the conformal prediction method (c) (with α = 0.05) the overlapping areas are classified as multiple classes and white areas are classified as the null set. For the standard methods (a-b), the decision boundaries can change significantly with small changes in some of the data points and the prediction cannot be justified in most of the space. Online version in color.

Figure 2: (a) Performance plot for the conformal method. Accuracy is empirically linear as a function of α but affect the number of classes predicted per sample. (b-c) are illustrative examples. When α = 0.6 both black and red classes are predicted. When α = 0.8 the red classes remain.

Figure 3: Classification results for (a) random noise; (b) Jackson Pollock "Rabit Hole"; (c) Muhammad Ali towering over Sonny Liston (1965 rematch). These pictures are outliers for the Imagenet categories. The left labels of each picture are provided by our method and the right are the results of the Inception-v4 model Szegedy et al. (2017).

Figure 3 (b) show results on Jackson Pollock paintings -an abstract yet more structured dataset.Testing 11 different paintings with α = 0.5 all result with the null set. When testing the Inception-v4 model output, 7/11 paintings are classified with probability greater than 0.5 to either "Coil", "Ant", "Poncho", "Spider Web" and "Rapeseed" depending on the image.

Figure3(c) is the famous picture of Muhammad Ali knocking out Sonny Liston during the first round of the 1965 rematch. "Boxing" is not included within in the ImageNet challenge. Our method correctly chooses the null set with α as low as 0.55. Standard method are forced to associate this image with one of the classes and choose "Volleyball" with 0.38 probability and the top-5 are all sport related predictions with 0.781 probability. This is good result given the constraint of selecting a single class, but demonstrate the impossibility of trying to create classes for all topics.

Figure 4 (a) and (b) show mean pixel values for females pictures within CelebA vs pictures in the IMDB-Wiki dataset. As seen, the IMDB-Wiki is richer and offers larger variety of human postures.

Figure 4: (a) Females faces mean pixel values in (a) CelebA; (b) IMDB-Wiki. Within CelebA the pictures are aliened with fixed posture, explaining why it naively fails to generalize to IMDB-Wiki images. (c) Performance plots for the conformal method on both CelebA and IMDB-Wiki.

). SeeLei and Wasserman Lei & Wasserman (2014). Suppose we observe independent and identically distributed Y i , . . . , Y n ∈ R d from distribution P . The goal is to construct a prediction set C for new Y . Lei, Robins and WassermanLei et al. (2013) use the level set C = {y : p(y) > t} where p is a kernel density estimator. They show that if t is chosen carefully then P (Y ∈ C) ≥ 1 -α for all P .Multiclass Classification. There are two notable solutions also using conformal prediction for the multiclass classification problem which are directly relevant to this work.

Table content: <table><tr><td>Unsupervised Prediction.</td></tr></table>

Algorithm 1 Training Algorithm Input: Training data Z = (X, Y ), Class list Y, Confidence level α, Ratio p. p list = list; t list = list The validation set α quantile p list .append ( p y ) ; t list .append t y return p list ; t list Algorithm 2 Prediction Algorithm Input: Input to be predicted x, Trained p list ; t list , Class list Y.

Table content: <table><tr><td/><td>Initialize lists</td></tr><tr><td>for y in Y do X y tr , X y val ← SubsetData (Z, Y, p) p y ← LearnDensityEstimator (X y tr ) t y ← Quantile ( p y (X y val ) , α)</td><td>Loop over all the classes independently Split X | y with ratio p</td></tr><tr><td>C = list</td><td>Initialize C (x)</td></tr><tr><td>for y in Y do</td><td>Loop over all the classes independently</td></tr><tr><td>if p y (x) ≥ t y then</td><td/></tr><tr><td>C.append (y)</td><td/></tr><tr><td>return C</td><td/></tr></table>

Peer review (iclr2019):
 The paper proposes deep learning extension of the classic paradigm of *conformal prediction*. Conformal prediction is similar to multi-label classification, but with a statistical sound way of thresholding each (class-specific) classifier: if our confidence in the assignment of an x to a class y is smaller than .alpha, then we say *do not know / cannot classify*). This is interesting when we expect out of distribution samples (e.g., adversarial ones). I think this paper, which is very well written, would make for nice discussions at ICLR, because it is (to my knowledge) the first that presents a deep implementation of the conformal prediction paradigm. However, there are a couple of issues, which is why I think it is definitely not a must have at ICLR. The concrete, deep implementation of the approach is rather straightforward and substandard for ICLR: Features are taken from an existing, trained SOTA DNN, then input KDE, based on which for each class the quantiles are computed (using a validation set). Thus, feature and hypothesis learning are not coupled, and the approach requires quite a lot of samples per class (however, oftentimes in multi-label prediction we observe a Zipf law, ie many classes have fewer than five examples). Furthermore, there is no coupling between the classes; each class is learned separately; very unlikely this will work better than a properly trained multi-class or (e.g., one-vs.-rest) multi-label classifier in practice. Since a validation set is used to compute the quantiles, substantial *power* is lost (data not used very efficiently; although that could be improved at the expense of expensive CV procedures).