Convolutional Neural Networks with Compression Complexity Pooling for Out-of-Distribution Image Detection

1 Introduction

The distributional uncertainty refers to an uncertainty originated from the inconsistency between training and test distributions [Malinin and Gales, 2018]. Recently, measuring the distributional uncertainty of deep neural networks has gained much attention, in order to detect out-of-distribution samples which come from outside the training distribution. In contrast to the existing belief that the softmax output of deep neural networks is not an appropriate measure for the uncertainty, a recent study found out that the softmax score can distinguish out-of-distribution (OOD) samples from in-distribution (ID) ones to a degree [Hendrycks and Gimpel, 2017].

Since then, several methods have shown promising results for the OOD detection [Liang et al., 2018; Lee et al., 2018b; Lakshminarayanan et al., 2017; Lee et al., 2018a], but most of them still have limitations from a practical perspective in that they need to find the optimal values of hyperparameters or retrain the model by using advanced objectives. For example, [Liang et al., 2018] improved performance by temperature scaling and input perturbation that manipulate the softmax outputs; this kind of calibration technique requires a set of OOD samples used for adjusting its hyperparameters, but it results in assuming a specific test distribution. On the other hand, [Lee et al., 2018a] defined an alternative loss function to detect OOD samples better; it has to retrain the model due to the newly designed loss function. In this sense, our motivation is to see how far OOD detection can be done without using the OOD set for validation while employing the already deployed softmax classifier without retraining it.

The state-of-the-art method [Lee et al., 2018b] tries to detect OOD samples based on the Mahalanobis distance from class means instead of using the softmax output, by utilizing the feature maps obtained from the convolutional neural network (CNN). In particular, they estimate the class-conditional probability, which is more appropriate and effective to detect OOD samples than the softmax output which provides mere relative confidence among classes. However, they obtain feature vectors of input images by averaging each feature map, also known as the global average pooling (GAP). We notice that the spatial information of input images disappears in the process of averaging feature vectors, and this eventually leads to limited performance in OOD detection.

To tackle this challenge, we introduce normalized compression distance (NCD) [Li et al., 2004] to obtain the feature vectors of input images without the loss of spatial information. The NCD is a general method to measure the intrinsic distance between two arbitrary objects using off-the-shelf compression algorithms (e.g., 7-zip, bzip, and lzw), and it evaluates how many shared patterns are eliminated when two discrete sequences are compressed together. With its solid theoretical backgrounds and general applicability, the NCD is widely used in various domains, including brain diagnosis [Berek et al., 2014], spam filtering [Spracklin and Saxton, 2007], and malware classification [Borbely, 2016]. Based on the NCD, we aim to accurately measure how similar the feature maps of a test sample are with those of training samples, and use it to determine whether the test sample comes from OOD or not.

In this paper, we present MALCOM, MAhaLanobis distance with COMpression complexity pooling, which effectively measures the confidence score (i.e., distributional uncertainty) of an input image while capturing the spatial information within the feature maps. Specifically, we propose compression complexity pooling to compute the feature vector by using the NCD between the feature maps of a test sample and the prototypical maps that summarize the whole training set. Our extensive experiments demonstrate that MALCOM shows better performances in detecting OOD images than state-of-the-art methods in realistic scenarios where OOD images are not available for its validation. MALCOM is also easily extended to adopt a calibration technique whose hyperparameters need to be tuned, and it successfully achieves the best performance.

2 Preliminaries

2.1 Constrained Out-of-Distribution Detection

Before proceeding to describe notions closely related to our method, we need to understand what we want to tackle in this work: out-of-distribution detection without retraining networks and without sniffing out-of-distribution samples. Let Dtrain = {(xn, yn)}Nn=1 be the training dataset and M(·; θ) be the model trained on Dtrain. Then each sample xn of Dtrain is assumed to be an observation from the in-distribution (ID). The out-of-distribution (OOD) detection task is to obtain an OOD score function κ(·;Dtrain, θ,φ) for discrimination between ID and OOD. In other words, given a test instance x∗ , the function κ(x∗ ) assigns a higher score to x∗ if it comes from OOD than ID. There are many ways to define a score function κ, but we work on the task under the following constraints:

• The score function parameter φ should be independent from a distribution of test data x∗ , i.e., φ is determined only by the training set. This is intuitive in that x∗ does not assume any test distribution. This requirement implies that using OOD samples for hyperparameter tuning is not allowed.
• The model parameter θ should not be changed; i.e., the model trained initially for classification should not be retrained for OOD detection. By doing so, a score function is able to measure the distributional uncertainty of models that are already trained and deployed in real-world applications.

There are few existing methods satisfying these conditions: the softmax output detector [Hendrycks and Gimpel, 2017] and the simplified Mahalanobis detector [Lee et al., 2018b].

2.2 Mahalanobis Detector

The Mahalanobis detector, one of the best-performing OOD detectors, introduces an effective method to remove the correlation among the feature maps of a hidden layer [Lee et al., 2018b]. We note that combining multiple layers does not always lead to the improvement of detection performances in some cases.

Simplified Mahalanobis Detector

We factor out a simplified version of the Mahalanobis detector, Mahalanobis-vanilla (MV), because the whole Mahalanobis detector method needs OOD samples to tune the hyperparameters of input preprocessing and layer weights used for the weighted sum, which fails to satisfy our first requirement discussed in Section 2.1. For more details about the whole Mahalanobis detector, please refer to [Lee et al., 2018b].

MV only uses the feature maps of the last hidden layer obtained from a CNN. To be precise, we denote the output of the l-th hidden layer of the networkMbyMl for l = 1, . . . ,L, where L is the number of hidden layers. For the l-th hidden layerMl, let f cl be the c-th feature map of its output for c = 1, . . . , Cl, where Cl is the number of the feature maps of the l-th hidden layer. Then, Ml(x) is a 3D tensor of size Cl ×Hl ×Wl and f cl (x) is a 2D matrix of size Hl ×Wl for any c and l, where Hl and Wl are respectively the height and the width of each feature map in the l-th layer. The global average pooling (GAP) of the l-th layer is defined by a vector ml of size Cl,

where [M]i,j refers the (i, j)-th entry in a matrix M, and ‖ is the concatenation operation.

MV utilizes only the last hidden layer (i.e., the L-th layer) to obtain the OOD score function, so its class means ˆµk and tied-covariance ˆΣ are defined as follows: 1

where K is the number of classes and Nk is the number of samples in class k. Then, the OOD score function of MV, denoted by ˆκ, is defined by

In this equation, MV computes centered data with respect for each class then performs linear projection to the centered data by using the inverse of ˆΣ. Practically, the inverse of an empirical covariance matrix is approximated by (MoorePenrose) pseudo-inverse, which uses the singular value decomposition [Barata and Hussein, 2012]. For this reason, computing the Mahalanobis distance of a sample from each class mean becomes equivalent to computing the norm (i.e., the Euclidean distance from the origin) after performing the principal component analysis where the origin is each class mean, which eventually removes the feature correlations.

1 To avoid notational confusion, we use different accents for different methods, except for our main method MALCOM: ˆa, ¯a, and ˜a for MV, MA, and MALCOM++, respectively.

Degeneracy of Simply Extended Mahalanobis Detector

From the observation that MV has the power of removing the correlation over feature maps, one may extend this concept to all the other hidden layers. We define the Mahalanobisassemble (MA) detector, by concatenating the averages of the feature maps (i.e., GAP) of all layers. Then, the class means and the tied-covariance are defined as

From the experiments, we find an interesting observation that this simply extended MA detector, denoted by ¯κ, significantly improves the performance in many cases; however, in some cases, MA performs worse than MV (see the DenseNetSVHN case in Table 1). This implies that concatenating GAP vectors from all layers may result in the loss of information about discrimination between ID and OOD samples because GAP cannot extract useful information from relatively lowlevel features (Details are discussed in Section 4.2).

2.3 Normalized Compression Distance

To address the degeneracy problem in MA, we focus on hindering the loss of spatial information of feature maps caused by GAP. To this end, we introduce normalized compression distance (NCD), which is a compression-based metric, in order to capture shared patterns between a test sample and the training dataset. The high-level idea of NCD is measuring how many repeated patterns commonly exist in two objects by using a data compression technique. To make it easier, we consider only binary strings. Formally, given a compression method Z and two binary strings x, y ∈ {0, 1}∗ , NCD is defined as

where Z(x) is the compressed length of x, and x‖y is the concatenation of the two strings. Intuitively, if we assume that Z(x‖y) = Z(y‖x) and Z(x) > Z(y) while fixing x, we observe that the numerator of NCD becomes small in case that the length of the compression bits of x‖y and that of y do not differ much; this means the compressor utilizes much of the information about x to compress y, so the compressor does not need many additional bits to compress y. A compressor Z can be one of the off-the-shelf compressors, including 7-zip, gzip, and bzip. Note that the better compressor we choose, the closer NCD approximates a distance metric [Cilibrasi and Vit´anyi, 2005].

3 ProposedMethod

In this section, to resolve the degeneracy of MA discussed in Section 2.2, we present MALCOM which adopts NCD to measure the distance between the feature maps of a test sample and those of training samples.

3.1 Compression Complexity Pooling

We propose compression complexity pooling (CCP) which is able to capture the spatial information of a feature map. For a hidden layer of size C×H×W, CCP first transforms each 2D feature map of size H×W into a 1D string, then calculates the NCD of the string from the other 1D string that is obtained from a pre-selected feature map in the same way. Because CCP generates a single value from each feature map of a hidden layer, it can be regarded as a global pooling operation which measures the relative complexity from the pre-selected sample.

Transformation of a Feature Map into a String. As the NCD takes strings as its input, we need to transform a 2D feature map into a 1D string. The transformation is composed of a quantizing function and a linearizing function. For the number of quantization levels ν ∈ N, let Γ := {γ1, . . . , γν} be a set of quantization levels. Then, a quantizing function q : R → Γ maps a continuous value into one of the quantization levels. In addition, given a feature map of size H×W, a linearizing function λ : MH×W(Γ) → ΓH·W maps a 2D matrix into a 1D vector by rearranging the order of the matrix entries (i.e., a flatten function). Note that every feature map f cl in the same layerMl has the same linearizing function λl, whereas the quantizing functions qc l are all different for each feature map. Finally, the transformed 1D string can be represented as (λl ◦ qcl )(f cl ). The details about the transformation of our method are discussed in Section 4.1.

NCD from a Random Sample

To explain how NCD works in the CCP, we consider a single feature map f cl . In the training process, we randomly select a sample s from Dtrain as a reference for computing the NCD of an input image. For the fixed sample s and a test sample x, we can calculate the NCD value dcl (x; s) by

For an image x, it is obvious that the distance becomes small if x is similar to s in some aspects, and it would be large otherwise. Now, given a layer, the final output of CCP is obtained by aggregating NCD values of all the feature maps from the layer, i.e.,ρl(x; s) =‖Cl c=1 dcl (x, s). (8)

This can be interpreted as a distance-vector of x from s; the compression of linearized 1D feature maps considers sequential patterns in them, and it consequently enables to capture of the spatial information of the original 2D feature maps. A remaining question here is how to choose a representative sample from the whole training dataset.

NCD from Prototypical Maps

Because a randomly selected sample s has a high variance as well as does not represent the entire training dataset, we generate a prototypical map for each feature map. The prototypical map is obtained by averaging the feature maps of all training samples. Precisely, we define the c-th prototypical map zcl of the l-th layer as

We observe that if we use qc l to quantize the prototypical map zcl of size H×W, only few quantization levels appear in the output map. This is because most values are collapsed to the average during the summarization of feature maps by Equation (9). Thus, we need to design an alternative quantizing function pcl for the prototypical map zcl . Let RTi be the rate of how many times the i-th quantization level γi appears among all the quantization levels in the training dataset. Then we quantize the prototypical map zcl so that the appearance rate RPi of the i-th quantization level γi observed from the quantized prototypical map pcl (zcl ) becomes similar to that from the training set (i.e., RTi). In other words, the quantizing function pcl satisfies the following conditions:

The prototypical map is obtained for each feature map, so the definition of the CCP should be revised accordingly. For the c-th feature map of the l-th layer f cl , Equations (7) and (8) can be rewritten based on the prototypical maps Z := {zcl for any l and c}:

3.2 MALCOM: Mahalanobis Detector with CCP Confidence Score for OOD Image Detection

To put it all together, we obtain twofold pooling vectors r that encode the spatial information by concatenating two vectors obtained by GAP and CCP.

where ρ(x;Z) :=‖Ll=1 ρl(x). Based on the twofold pooling vectors, we define a final OOD score function κ based on the Mahalanobis distance in order to remove the correlation between feature maps.

Feature Ensemble

Even though we focus on the constrained OOD detection for our main motivation (Sec 2.1), we additionally propose an extended version of MALCOM, called MALCOM++, for the special case that some OOD samples are available for its validation and a specific OOD distribution can be assumed at test time. To be specific, MALCOM++ adopts the feature ensemble, which defines the final confidence score by the weighted sum of the scores computed from multiple hidden layers, and it turns out to be effective where we can infer the test distribution from a validation set of OOD samples [Lee et al., 2018b]. It is worth noting that MALCOM++ summarizes the scores directly from multiple layers based on hyperparameters rather than utilizes concatenation.

4 Experiments

4.1 Experimental Settings

Models and Datasets. We choose two popular deep neural networks used for image classification: DenseNet [Huang et al., 2017] with 100 layers and growth rate k=12, and ResNet [He et al., 2016] with 34 layers. We train the networks with a softmax layer and cross entropy loss using three datasets: CIFAR-10, CIFAR-100 [Krizhevsky et al., 2009] and SVHN [Netzer et al., 2011]. 2 In addition to the three training datasets (i.e., ID), we use four additional image datasets as OOD samples in test distributions: TinyImageNet [Deng et al., 2009], LSUN [Yu et al., 2015], and iSUN [Xu et al., 2015]. To train the networks, SGD with initial learning rate 0.1 and Nesterov momentum 0.9 is used, and the weight decay is set to 0.0001, 0.0005, and the batch size is set to 64 and 128, respectively for DenseNet and ResNet. We repeat to train the models five times and report their average results for all experiments. The test accuracy for the classification is reported in Table 2.

CompetingMethods. We compare the performance of our method with that of the existing methods which detect OOD samples using pretrained softmax classifier: ODIN [Liang et al., 2018] and Mahalanobis detector [Lee et al., 2018b]. Both the methods utilize OOD samples to find the optimal hyperparameters. In this sense, they do not satisfy our first constraint describing that any test distributions should not be assumed. Nevertheless, we loosen the constraint and report the results to show relative performance compared to the state-of-the-art methods. We utilize the publicly available codes of ODIN and Mahalanobis provided by previous work. 3

2 Our experiments follow most of the experimental settings mainly used in previous work [Liang et al., 2018; Lee et al., 2018b].

EvaluationMetrics. We adopt the three performance metrics the same with the previous work [Lee et al., 2018b]: true negative rate (TNR) at 95% true positive rate (TPR), area under the receiver operating characteristic curve (AUROC), and detection accuracy.

Implementation Details

We employ the Lempel-Ziv-Welch (LZW) coding scheme [Welch, 1984] for the compression algorithm Z used to compute the NCD. The NCD only requires the lengths of compression results, and the LZW coding scheme has an advantage of computing the length of an input string in O(n); we further accelerate the computation by using GPU.

We quantize the feature maps by using the Lloyd-Max quantizer [Lloyd, 1982; Max, 1960], which effectively minimizes the information loss. We fix the number of levels to 4, known to perform well for images when it used with our compression scheme (i.e., LZW) [Pinho and Ferreira, 2011]. Specifically, we use Lloyd-Max quantizer to obtain the thresholds for quantization after gathering all values of each feature map of the training samples.

We adopt the Hilbert space-filling curve to linearize the 2D feature maps. Among several linearizations, including simple row-wise (or column-wise) strategies, linearizing images by Hilbert space-filling curve turns out to be effective when using NCD for images [Liang et al., 2008]. Note that each feature map of l-th hidden layer has the same size of Hl×Wl, so the linearizing function λl is defined for each layer. Our code is publicly available. 4

3 https://github.com/pokaxpoka/deep Mahalanobis detector

4.2 Results

Effectiveness of the CCP

We ablate the components of our method to investigate the effectiveness of GAP, CCP, and their combinations. For rigorous analyses, we evaluate a wide range of Mahalanobis distance-based detectors, including MV, MA, and MALCOM; they apply either GAP or CCP, or both of them to the feature maps obtained from a single or multiple hidden layers. Table 3 presents the results of the ablation study.

In Table 3, the detector using only CCP or using both GAP and CCP on all hidden layers performs the best in most cases. More concretely, we observe that CCP brings more significant improvements when CCP is applied to lower-level features, especially the case that only the first hidden layer is used. On the contrary, in the case of the high-level features in the last hidden layer, CCP shows moderate performances and does not seem to have superiority compared to GAP. In this sense, the CCP which takes advantage of spatial information becomes much helpful to accurately detect OOD samples, particularly for lower-level features encoding more spatial information of input images. In conclusion, CCP greatly contributes to performance improvement and becomes much effective where GAP cannot derive meaningful information from low-level features.

Effectiveness of the Prototypical Maps. To demonstrate the effectiveness of the proposed prototypical maps, we compare MALCOM that uses a randomly selected sample for CCP (from Equation (8)) with the one that adopts prototypical maps for CCP (from Equation (11)). In Table 4, the standard deviation of MALCOM with the prototypical maps is consistently smaller than the one with a random sample, which indicates that the robustness of our NCD is improved as we intended. Furthermore, MALCOM with the prototypical maps also shows slightly better performances than the other. This implies that the prototypical maps help NCD to distinguish OOD samples by encoding the information of all training samples in itself.

Main Results

The main comparison results are summarized in Table 5. For each experiment, we leave out 1000 images from ID and OOD test sets and use them for the validation; thus, these 2000 images are not used for MALCOM which does not need to tune any hyperparameter.

In Table 5, our proposed methods (i.e., MALCOM and MALCOM++) outperform the state-of-the-art method in most cases. From the extensive experiments, we conclude that MALCOM is more effective to detect OOD samples compared to existing methods while it keeps satisfying the conditions for the constrained OOD detection. Furthermore, it can be easily extended to adopt the calibration technique, which further improves the performance by using OOD samples for its validation.

4 https://github.com/hunu12/MALCOM

5 RelatedWork

Most previous work on OOD detection with softmax classifiers introduced parameters which help to enhance the performance. ODIN [Liang et al., 2018] designed two calibration techniques (i.e., temperature scaling and input preprocessing) to boost its performance by manipulating softmax outputs. [Vyas et al., 2018] proposed an objective to detect OOD samples based on an ensemble of classifiers, which are trained by partitioned sets of samples.The state-of-the-art method [Lee et al., 2018b] focuses on the internal features of the CNNs, while it involves hyperparameters for input preprocessing and logistic regression that aggregates confidence scores from each hidden layer.

Another line of research closely related to ours is NCD applications in the image-specific tasks [Lan and Harvey, 2005; Guha and Ward, 2014]. Since most compression methods take two strings as the input, most work mainly focused on quantization and linearization of input images. For example, [Mortensen et al., 2009] studied the robustness of the NCD for different linearizations on shifted or rotated images, and [Liang et al., 2008] investigated the effects of different compression methods for the NCD on medical images. Among them, [Coltuc et al., 2018] pointed out that using the NCD directly on raw images is not effective enough to measure the similarity, so they aggregated NCDs based on several filters to improve its robustness. Our work differs in that MALCOM applies the NCD to feature maps from CNNs rather than raw images or simply smoothed images.

6 Conclusion

This paper proposes MALCOM, which accurately measures the confidence score for OOD detection without using any hyperparameters and without retraining the model. To address the limitation of the existing methods that cannot exploit the spatial information of feature maps, we introduce the CCP which computes the outputs based on the NCD between two feature maps. Our extensive evaluation over image datasets shows that CCP leverages the spatial information of the feature maps, especially when being applied to low-level features, and this brings the performance improvement compared to the existing GAP. In addition, by using both the pooling techniques simultaneously, MALCOM achieves the best performance among all competing methods.

Acknowledgments

This research was supported by the NRF grant funded by the MSIT: (No. 2016R1E1A1A01942642) and (No. 2017M3C4A7063570), the IITP grant funded by the MSIT: (No. 2018-0-00584) and (IITP-2019-2011-1-00783).