On the Out-of-distribution Generalization of Probabilistic Image Modelling
Year: 2021

Abstract:
Out-of-distribution (OOD) detection and lossless compression constitute two problems that can be solved by the training of probabilistic models on a first dataset with subsequent likelihood evaluation on a second dataset, where data distributions differ. By defining the generalization of probabilistic models in terms of likelihood we show that, in the case of image models, the OOD generalization ability is dominated by local features. This motivates our proposal of a Local Autoregressive model that exclusively models local image features towards improving OOD performance. We apply the proposed model to OOD detection tasks and achieve state-of-the-art unsupervised OOD detection performance without the introduction of additional data. Additionally, we employ our model to build a new lossless image compressor: NeLLoC (Neural Local Lossless Compressor) and report state-of-the-art compression rates and model size.

heading: 1 Introduction
text: Probabilistic modeling has achieved great success in the modeling of images. Likelihood based models, e.g. Variational Auto-Encoders (VAE) [22], Flow [21], Pixel CNN [49, 41] are shown to successfully generate high quality images, in addition to estimating underlying densities.
The goal of probabilistic modelling is to use a model pθ to approximate the unknown data distribution pd using the training data {x1, . . . , xN} ∼ pd. A common method to learn parameters θ is to minimize some divergence between pd and pθ, for example, a popular choice is the KL divergence
KL(pd||pθ) = −H(pd)− ∫ log pθ(x)pd(x)dx, (1)
where the entropy of the data distribution is a constant. Since we only have access to finite pd data samples x1, . . . , xN , the second term is typically approximated using a Monte Carlo estimation
KL(pd||pθ) ≈ − 1
N N∑ n=1 log pθ(xn)− const.. (2)
Minimizing the KL divergence is therefore equivalent to Maximum Likelihood Estimation. A typical evaluation criterion for the learned models is the test likelihood 1M ∑M m=1 log pθ(xm), with test set {x1, . . . , xM} ∼ pd. We refer to this evaluation as in-distribution (ID) generalization, since both training and test data are sampled from the same distribution pd. However, in this work, we are interested in out-of-distribution (OOD) generalization such that the test data are drawn from po, where po 6= pd. To motivate our study of this topic, we firstly introduce two applications: lossless compression and OOD detection, that both can make use of the OOD generalization property. ∗Co-first author, the work was done during an internship in Huawei Noah’s Ark Lab.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).

heading: 1.1 Model-based Lossless Compression
text: Lossless compression has a strong connection to probabilistic models [33]. Let {x1, . . . , xM} be test data to compress, where xm is sampled from some underlying distribution with PMF pd. If pd is known, we can design a compression scheme to compress each data xm to a bit string with length approximately − log2 pd(xm)2. As M → ∞, the averaged compression length will approach the entropy of the distribution pd, that is; 1M ∑M m=1− log2 pd(xm)→ H(pd) where H(·) denotes entropy. In this case, the compression length is optimal under Shannon’s source coding theorem [45], i.e. we cannot find another compression scheme with compression length less than H(pd). In practice, however, the true data distribution pd is unknown and we must use a model pθ ≈ pd to build the lossless compressor. Recent work successfully apply deep generative models such as VAEs [47, 48, 23], Flow [19, 3] to conduct lossless compression. We note that the underlying models are designed to focus on test data that follows the same distribution as the training data, resulting in test compression rates that depend on the ID generalization ability of the model.
However, in practical compression applications, the distribution of the incoming test data is unknown, and is usually different from the training distribution pd: X otest = {x′1, . . . , x′M} where x′ ∼ po 6= pd. To achieve good compression performance, a lossless compressor model should still be able to assign high likelihood for these OOD data. This practical consideration motivates encouragement of the OOD generalization ability of the model.
Empirical results [48, 19] have shown that we can still use model pθ (trained to approximate pd) in order to compress test data X otest with reasonable compression rates. However, the phenomenon that these models can generalize to OOD data lacks intuition and key components, affecting this generalization ability, remain underexplored. Consideration of recent advances in likelihood-based OOD detection next allows us to further investigate these questions and lead to our proposal of a new model that can encourage OOD generalization.

heading: 1.2 Likelihood-based OOD Detection
text: Given a set of unlabeled data, sampled from pd, and a test data x′ then the goal of OOD detection is to distinguish whether or not x′ originates from pd. A natural approach [5] involves fitting a model pθ to approximate pd and treat sample x′ as in-distribution if its (log) likelihood is larger than a threshold; log pθ(x′) > . Therefore, a good OOD detector model should assign low likelihood to the OOD data. In contrast to lossless compression, this motivates discouragement of the OOD generalization ability of the model.
Surprisingly, recent work [36] report results showing that popular deep generative models, including e.g. VAE [22], Flow [21] and PixelCNN [41], can assign OOD data higher density values than in-distribution samples, where such OOD data may contain differing semantics, c.f . the samples used for maximum likelihood training. We demonstrate this phenomenon using PixelCNN models, trained on Fashion MNIST (CIFAR10) and tested using MNIST (SVHN). Figure 1 provides histograms of model evaluation using negative bits-per-dimension (BPD), that is; the log2 likelihood normalized by data sample dimension (larger negative BPD corresponds to larger likelihood). We corroborate previous work and observe that tested models assign higher likelihood to the OOD data, in both cases. This counter intuitive phenomenon suggests that likelihood-based approaches may not make for good OOD image detection criterion, yet encouragingly also illustrates that a probabilistic model, trained using one dataset, may be employed to compress data originating from a different distribution with a potentially higher compression rate. This intuition builds a connection between OOD detection and lossless compression. Inspired by this link, we next investigate the underlying latent causes of image model generalizability, towards improving both lossless compression and OOD detection.

heading: 2 OOD Generalizations of Probabilistic Image Models
text: Previous work studies the potential causes of the surprising OOD detection phenomenon: OOD data may have higher model likelihood than ID data. For example, [37] used a typical set to reason about the source of the effect, while the work of [40] argues that likelihoods are significantly affected by
2For a compression method like Arithmetic Coding [50], the message length is always within two bits of − log2 pd(xm) [33], also see Section 4.1.
image background statistics or by the size and smoothness of the background [26]. In this work, we alternatively consider a recent hypothesis proposed by [43] (also implicitly discussed in [24] for a flow-based model): low-level local features, learned by (CNN-based) probabilistic models, are common to all images and dominate the likelihood. From the perspective of OOD generalization, this allows formulation of the following related conjectures:
• Models can generalize to OOD images as local features are shared between image distributions. • Models can generalize well to OOD images since local features dominate the likelihood.
In the work of [43], the authors investigated their original hypothesis by studying the differences between individual pixel values and neighbourhood mean values and additionally considered the correlation between models trained on small image patches and trained, alternatively, on full images. To further investigate this hypothesis, we rather propose to directly model the in-distribution dataset, using only local feature information. If the hypothesis is true, then the proposed local model alone should generalize well to OOD images. By contrasting such an approach with a standard full model, that considers both local and non-local features, we are also able to study the contribution that local features make to the full model likelihood. We first discuss how to build a local model for the image distribution and then use the proposed model to study generalization on OOD datasets.

heading: 2.1 Local Model Design
text: Autoregressive models have proven popular for modeling image datasets and common instantiations include PixelCNN [49, 41], PixelRNN [49] and Transformer based models [7]. Assuming data dimension D, the Autoregressive model pf (x) can be written as
pf (x) = p(x1) D∏ d=2 p(xd|x1, . . . , xd−1), (3)
informally we refer to this type of model as a “full model” since it can capture all dependencies between each dimension (pixel). Similarly, we can define a local autoregressive model pl(x) where pixel xij , at image row i column j, depends on previous pixels with fixed horizon h:
pl(x) = ∏ ij p(xij |x[i−h:i−1,j−h:j+h], x[i,j−h:j−1]), (4)
with zero-padding used in cases where i or j are smaller than h. Figure 2b illustrates the resulting local autoregressive model dependency relationships. We implement this model using a masked CNN [49], with kernel size k=2×h+1 in our first network layer, to mask out future pixel dependency. A full PixelCNN model would then proceed to stack multiple masked CNN layers, where increasing kernel depth affords receptive field increases. In contrast, we employ masked CNN with 1×1 convolutions in subsequent layers. Such 1×1 convolutions can model the correlation between channels, as in [21], and additionally prevent our local model obtaining information from pixels outwith the local feature region, defined by h. Pixel dependencies are therefore defined solely using the kernel size of the first masked CNN layer, allowing for easy control over model local feature size. We note that the proposed local autoregressive model can also be implemented using alternative backbones e.g. Pixel RNN [49] or Transformers [7]. We plot local model samples in Figure 4. Unlike full autoregressive models [49, 41], which can be used to generate semantically coherent samples, we find the samples from the local model are locally consistent yet have no clear semantic meaning.

heading: 2.2 Local Model Generalization
text: To investigate the generalization ability of our local autoregressive model, we fit the model to Fashion MNIST (grayscale) and CIFAR10 (color) training datasets and test using in-distribution (ID) images (respective dataset test images) and additional out-of-distribution (OOD) datasets: MNIST, KMNIST (grayscale) and SVHN, CelebA3 (color). Both models use the discretized mixture of logistic distributions [41] with 10 mixtures for the predictive distribution and a ResNet architecture [49, 14]. We use a local horizon length h=3 (kernel size k=7) for both grayscale and color image data. We compare our local autoregressive model to a standard full autoregressive model (i.e. a standard PixelCNN), with additional network architecture and training details found in Appendix A. Tables 1, 2
report comparisons in terms of BPD (where lower values entail higher likelihood) for Fasion MNIST and CIFAR10, respectively. We observe that for in-distribution (ID) data, the full model has better generalization ability c.f . the local model (0.11 and 0.13 BPD, respectively). This is unsurprising as training and test data originate from the same distribution; both local and non-local features, as learned by the full model, help ID generalization. For OOD data, we observe that the local model has generalization ability similar to the full model, exhibiting very small empirical gaps (only ≈ 0.02 BPD on average), showing that the local model alone can generalize well to OOD distributions. We thus verify the hypothesis considered at the start of Section 2.
For simple datasets containing gray-scale images, the PixelCNN model is flexible enough to capture both local and global features. We notice that, in Table 1, our local model exhibits even better OOD generalization than the full model. This drives us to further study the role of non-local features for generalization. When the local horizon size increases, the model will be able to learn features with greater non-locality. We thus vary the local horizon size to study generalization ability under this property, see Table 3. We find the model has poor generalization performance when local features are too small and increasing the horizon size helps ID generalization but decreases the OOD generalization. A consistent phenomenon is observed when considering color images, see Appendix B.1. We can thus conclude: non-local features are not shared between images distributions, overfitting to non-local features will hurt generalization.
Table 3: Generalization of local model with different horizon sizes. The model is trained on FashionMNIST dataset.
Method h=1 h=2 h=3 h=4 h=5
(ID) Fashion 3.17 2.93 2.89 2.88 2.88
(OOD) MNIST 1.54 1.48 1.49 1.50 1.51 (OOD) KMNIST 2.54 2.43 2.44 2.46 2.47
These hypotheses indicate two opposing strategies for the considered tasks:
OOD detection: distributions are distinguished by dataset-unique features, thus building non-local models, able to discount common local features, improves the detector distinguishability power.
3We down-sample the original CelebA to 32×32×3, see Appendix A.2 for details.
Lossless compression: OOD generalization is possible due to the sharing of local features between distributions. Employing only a local model can encourage OOD generalization, by preventing the model from over-fitting to dataset-unique features, specific to the training distribution.
Sections 3 and 4 will further demonstrate how contrasting modeling strategies can benefit these tasks.

heading: 3 OOD Detection with Non-Local Model
text: As was discussed in Section 1.2, local image features are observed to be largely common across the real-world image distribution and can be treated as a domain-prior. Therefore, in order to detect whether or not an image is out-of-distribution, we can stipulate a non-local model able to discount local features of the image distribution; denoted here pnl(x). It is however not easy to build such a non-local model directly, since the concept of “non-local” lacks a mathematically rigorous definition. However, we propose that a non-local model can be considered to be the complement of a local model, from a respective full model. In the following section, we therefore propose to use a product of experts to indirectly define pnl(x), and demonstrate how this may be used for OOD detection.

heading: 3.1 Product of Experts and Non-Local Model
text: As demonstrated in Section 2.2, the full model pf (x) and the local model pl(x) can be easily built for the image distribution, e.g. a full autoregressive model and a local autoregressive model. We further assume the full model allows the following decomposition:
pf (x) = pl(x)pnl(x)
Z , (5) where Z = ∫ pl(x)pnl(x)dx is the normalizing constant. This formulation can also be thought of as a product of experts (PoE) model [17] with two experts; pl (local expert) and pnl (non-local expert). An interesting property of the PoE model is that if a data sample x′ has high full model probability pf (x
′), it should possess high probability mass in each of the expert components4. Therefore, the PoE model assumption is consistent with our image modelling intuition: a valid image requires both valid local features (e.g. stroke, texture, local consistency) and valid non-local features (semantics).
By our model assumption, the density function of the non-local model can be formally defined and is proportional to the likelihood ratio:
pnl(x) ∝ pf (x)
pl(x) ≡ p̂nl(x), (6)
where p̂nl(x) denotes the unnormalized density. For the OOD detection task, we require only p̂nl(x) in order to provide a score classifying whether or not test data x is OOD and therefore do not require to estimate the normalization constant Z. We also note that as we increase the local horizon length for pl, the local model will converge to a full model pl → pf , and p̂nl(x) = 1 becomes a constant and inadequate for OOD detection. This further suggests the importance of using a local model. Figure 3 shows histograms of p̂nl(·) for both ID and OOD test datasets. We observe that the majority of ID test data obtains higher likelihood than OOD data, illustrating the effectiveness of non-local models.

heading: 3.2 Connections to Related Methods
text: We highlight that the score p̂nl(x) that we use to conduct OOD detection allows a principled likelihood interpretation: the unnormalized likelihood of a non-local model. We believe this to be the first time that the likelihood of a non-local model is considered in the literature. However, other likelihood ratio variants have been previously explored for OOD detection. We briefly discuss related work and highlight where our method differs from relevant literature.
In [40], it is assumed that each data sample x can be factorized as x = {xb, xs}, where xb is a background component, characterized by population level background statistics: pb. Further, xs
4This PoE property differs from a Mixture of Experts (MoE) model that linearly combines experts. If data x′ has high probability in the local model (e.g. pl(x′) = 0.9) but low probability in the non-local model (e.g. pnl(x
′) = 0.1), the probability in the full PoE model pf (x′) ∝ 0.9 ∗ 0.1 is also small. On the contrary, if we assume pf is a MoE: pf = 12pl + 1 2 pnl, then pl(x′) = 0.9 and pnl(x′) = 0.1 results in a high full MoE model pf (x ′) value i.e. pf (x′) = 0.5 ∗ 0.9 + 0.5 ∗ 0.1 = 0.5. We refer to [17] for additional PoE model details.
p̂nl(x)=
pf (x) pl(x) for both ID test datasets (FashionMNIST, CIFAR10) and OOD datasets (MNIST, SVHN). ID test datasets obtain significantly higher likelihoods, on average, in each case.
then constitutes a semantic component, characterized by patterns belonging specifically to the indistribution data: ps. A full model, fitted on the original data, (e.g. Flow) can then be factorized as pf (x) = pf (xb, xs) = pb(xb)ps(xs) and the semantic model can correspondingly be defined as a ratio: ps(x) =
pf (x) pb(x) , where pf (x) is a full model. In order to estimate pb(xb), the authors of [40] design a perturbation scheme and construct samples from pb(xb) by adding random perturbation to the input data. A further full generative model is then fitted to the samples towards estimating pb. In our method, both pl(x) and pnl(x) constitute distributions of the same sample space (that of the original image x) whereas ps and pb in [40] form distributions in different sample spaces (that of xs and xb, respectively). Additionally, in comparison with our local and non-local experts factorization of the model distribution, their decomposition of an image into ‘background’ and ‘semantic’ parts may not be suitable for all image content and the construction of samples from pb(xb) (adding random perturbation) lacks principled explanation. In [44, 43], the score for OOD detection is defined as s(x) =
pf (x) pc(x) where pf is a full model and pc is a complexity measure containing an image domain prior. In practice, pc is estimated using a traditional compressor (e.g. PNG or FLIF), or a model trained on an additional, larger dataset in an attempt to capture general domain information [43]. In comparison, our method does not require the introduction of new datasets and our explicit local feature model, pl, can be considered more transparent than PNG of FLIF. Additionally, our likelihood ratio can be explained as the (unnormalized) likelihood of the non-local model for the in-distribution dataset, whereas the score described by [43, 44] does not offer a likelihood interpretation. In Section 4, we discuss how the proposed local model may be utilized to build a lossless compressor, further highlighting the connection between our OOD detection framework and traditional lossless compressors (e.g. PNG or FLIF). In Table 6, we report experimental results showing that a lossless compressor based on our model significantly improves compression rates c.f . PNG and FLIF, further suggesting the benefits of the introduced OOD detection method.

heading: 3.3 Experiments
text: We conduct OOD detection experiments using four different dataset-pairs that are considered challenging [36]: Fashion MNIST (ID) vs. MNSIT (OOD); Fashion MNIST (ID) vs. OMNIGLOT (OOD); CIFAR10 (ID) vs. SVHN (OOD); CIFAR10 (ID) vs. CelebA (OOD). We actively select not to include dataset pairs such as CIFAR10 vs. CIFAR100 or CIFAR10 vs. ImageNet since these contain duplicate classes and cannot be treated as strictly disjoint (or OOD) datasets [44]. Additional experimental details are provided in Appendix A. In Table 4 we report the ‘area under the receiver operating characteristic curve’ (AUROC), a common measure for the OOD detection task [15]. We compare against methods, some of which require additional label information5, or datasets. Our method achieves state-of-the-art performance in most cases without requiring additional information. We observed that the model-ensemble methods, WAIC [8] and MSMA [34] can achieve higher AUROC in the experiments involving color images yet are significantly outperformed by our approach in the case of grayscale data. We thus evidence that our simple method is consistently more reliable than alternative approaches and that our score function allows a principled likelihood interpretation.
5In principle methods that require labels correspond to classification, task-dependent OOD detection, which may be considered fundamentally different from task-independent OOD detection (with access to only image space information), see [1] for details. We compare against both classes of method, for completeness.

heading: 4 Lossless Compression with Local Model
text: Recent deep generative model based compressors [47, 3, 23, 18] are designed under the assumption that data to be compressed originates from the same distribution (source) as model training data. However, in practical scenarios, test images may come from a diverse set of categories or domains and training images may be comparatively limited [33]. Obtaining a single method capable of offering strong compresson performance on data from different sources remains an open problem and related study involves consideration of “universal” compression methods [33]. Based on our previous intuitions relating to generalization ability; to build such a “universal” compressor in the image domain, we believe a promising route involves leveraging models that only depend on common local features, shared between differing image distributions. We thus propose a new “universal” lossless image compressor: NeLLoC (Neural Local Lossless Compressor), built upon the proposed local autoregressive model and the concept of Arithmetic Coding [50]. In comparison with alternative recent deep generative model based compressors, we find that NeLLoC has competitive compression rates on a diverse set of data, yet requires significantly smaller model sizes which in turn reduces storage space and computation costs. We further note that due to our design choices, and in contrast to alternatives, NeLLoC can compress images of arbitrary size.
In the remaining parts of this section, we firstly discuss NeLLoC implementation and then provide further details on the most important resulting properties of the method.

heading: 4.1 Implementation of NeLLoC
text: Our NeLLoC implementation uses the same network backbone as that of our OOD detection experiment (Section 3): a Masked CNN with kernel size k = 2× h+ 1 (h is the horizon size) in the first layer and followed by several residual blocks with 1×1 convolution, see Appendix A for the network
architecture and training details. To realize the predictive distribution for each pixel, we propose to use a discretized Logistic-Uniform mixture distribution, which we now introduce.
Discretized Logistic-Uniform Mixture Distribution The discretized logistic mixture distribution, proposed by [41], has shown promising results for the task of modeling color images. In order to ensure numerical stability, the original implementation can provide only an (accurate) approximation and therefore cannot be used for our task of lossless compression, which requires exact numerical evaluation. We therefore propose to use the discretized Logistic-Uniform Mixture distribution, which mixes the original discretized logistic mixture distribution with a discrete uniform distribution:
x ∼ (1− α) ( K∑ i=1 πiLogistic(µi, si) ) + αU(0, . . . , 255), (7)
where U(0, . . . , 255) is the discrete uniform distribution over the support {0, . . . , 255}. The proposed mixture distribution can explicitly avoid numerical issues and its PMF and CDF can be easily evaluated without requiring approximation. We can then use this CDF evaluation in relation to Arithmetic Coding. In practice; we set α = 10−4 to balance numerical stability and model flexibility. We use K = 10 (mixture components) for all models in the compression task.
Arithmetic Coding Arithmetic coding (AC) [50] is a form of entropy encoding which utilizes a (discrete) probabilistic model p(·) to map a datapoint x to an interval [0, 1]. One fraction, lying in the interval, can then be used to represent the data uniquely. If we convert the fraction into a large message stream, the length of the message is always within two bits of − log2 p(x) [33]. Our vanilla NeLLoC implementation makes use of the decimal version of AC. In principle, NeLLoC can also be combined with an Asymmetric Numeral System (ANS) [11], which gives faster coding time yet sacrifices compression rate. The work of [13] further proposed interleaved-ANS (iANS), which enables coding a batch of data simultaneously. In Appendix C, we report comparison of NeLLoC-AC, NeLLoC-ANS and NeLLoC-iANS in terms of compression rate and run time6.

heading: 4.2 Properties of NeLLoC
text: Universal Image Compressor As discussed previously, the motivation for designing NeLLoC is to realize an image compressor that is applicable (generalizable) to images originating from differing distributions. Towards this, NeLLoC conducts compression depending on local features which are shown to constitute a domain prior for all images. In addition to universality properties, we next discuss other important aspects towards making NeLLoC practical when considering real applications.
Arbitrary Image Size Common generative models, e.g. VAE or Flow, can only model image distributions with fixed dimension. Therefore, lossless compressors based on such models [47, 19, 3, 18, 23] can only compress images of fixed size. Recently, HiLLoC [48] explore fully convolutional networks, capable of accommodating variable size input images, yet still requires even height and width7. L3C [35], based on a multi-scale autoencoder, can compress large images yet also requires height and width to be even. NeLLoC is able to compress images with arbitrary size based on an alternative and simple intuition: we only model the conditional distribution, based on local neighbouring pixels. We thus do not model the distribution of the entire image and can therefore, in contrast to HiLLoC and L3C, compress arbitrary image sizes without padding requirements.
To validate method properties, we compare the compression performance of NeLLoC with both traditional image compressors and recently proposed generative model based compressors. We train NeLLoC with horizon length h = 3 on two (training) datasets: CIFAR10 (32×32) and ImageNet32 (32×32) and test on the previously introduced test sets, including both ID and OOD data. We also test on ImageNet64 with size 64×64 and a full ImageNet8 test set (with average size 500×374). Table 6 provides details of the comparison. We find NeLLoC achieves better BPD in a majority of cases. Exceptions include LBB [18] having better ID generalization for CIFAR and HiLLoC [48] having better OOD generalization in the full ImageNet, when the model is trained on ImageNet32.
Small Model Size In comparison with traditional codecs such as PNG or FLIF, one major limitation of current deep generative model based compressors is that they require generation and storage of
6We provide practical implementations of NeLLoC with different coders and pre-trained models at https://github.com/zmtomorrow/NeLLoC.
7For images with odd height or width, padding is required. 8Images with height or width greater than 1000 are removed, resulting in a total of 49032 test images.
models of very large size. For example, HiLLoC [48] contains 24 stochastic hidden layers, resulting in a capacity and parameter size of 156 MegaBytes (MB) using 32-bit floating point model weights. This poses practical challenges relating to both storage and transmission of such models to real, often resource-limited, edge-devices. Since NeLLoC only models the local region, a small network: three Residual blocks with 1×1 convolutions (except the first layer) is enough to achieve state-of-the-art compression performance. Accordingly the parameter size requirement is only 2.75 MB. We also investigate the compression task under NeLLoC with 1 and 0 residual block, which have parameter size of 1.34 and 0.49 MB respectively, and yet still observe respectable performance. We report model size comparisons in Table 6. In principle, NeLLoC can be also combined with other resource saving techniques such as binary network weights to realize the generative model components. This would further reduce model size [4], which we consider a promising line of future investigation.
Computation Cost and Speed The computational complexity and speed for a neural based lossless compressor depends on two stages: (1) Inference stage: in order to compress or decompress the pixel xd, a predictive distribution of xd needs to be generated by the probabilistic models; (2) Coding stage: uses the pixel value xd and its distribution to generate the binary code representing xd (encoding) or uses the predictive distribution and the binary code to recover xd (decoding). The computation cost and speed of the second stage heavily depends on the implementation (e.g. programming language) and the choice of coding algorithms, see Appendix C for a discussion about how different coders trade off between speed and accuracy. We here only discuss the computational cost pertaining to the first inference stage, which is affected by two factors: computational complexity and parallelizability.
1. Computational complexity: given an image with size N×N , the full autoregressive model distribution of pixel xij depends on all previews pixels p(xij |x[1:i,1:j]) and the computational cost of conditional distribution calculation scales as O(N2). For latent variable models (e.g. [48, 47]) or flow models (e.g. [3]) the predictive distribution of xi depends on all other pixels and therefore also scales with O(N2). In direct contrast, our local autoregressive model only depends on local regions with horizon h, so computation of p(xij |x[i−h:i−1,j−h:j+h], x[i,j−h:j−1]) scales with only O(h2) and typically h N in practice. This results in significant reduction of computational cost, enabling efficient usage of NeLLoC on CPUs. In Appendix C, we show that NeLLoC, with interleaved ANS coder, is able to compress or decompress the CIFAR10 dataset within 0.1s per image on a CPU. This gives us evidence, for the first time, that computation need not be a limitation of generative lossless compression. Further implementation improvements (e.g. C++, faster coders such as tANS [12]), will make NeLLoC a strong candidate to supersede traditional image compression methods.
2. Parallelizability: a second key property affecting compression speed is parallelizability. Neural compressors that make use of latent variable models [47, 48] can allow for the distribution of each pixel to be independent (given decompressed latents). Flow models with an isotropic base distribution will also result in appealing decompression times on average. However for a full autoregressive model, the predictive distribution of each pixel must be generated in sequential order and thus the decompression stage cannot be directly parallelized. This results in the decompression stage scaling with image size. In contrast to a full autoregressive model, where sequential decompressing is inevitable, we note that with NeLLoC each pixel only depends on a local region. The fact that multiple pixels exist with non-overlapping local regions allows simultaneous decompression at each step, enabling parallelization. Alternatively, we can split an image into patches and compress each patch individually, thus parallelizing the decompression phase.
Table 5 shows the compression BPD when we split full ImageNet images into patches. BPD slightly increases when we increase the number of patches. Splitting an image into patches assumes each patch is independent, which weakens the predictive performance. This results in a trade-off between compression speed and rate: ≈0.1 BPD overhead can offer ∼×400 speed up in compression, decompression (assuming infinite compute), potentially proving extremely valuable for practical applications.

heading: 5 Conclusion and Future Work
text: In this work, we propose the local autoregressive model to study OOD generalization in probabilistic image modelling and establish an intriguing connection between two diverse applications: OOD detection and lossless compression. We verify and then leveraged a hypothesis regarding local features and generalization ability in order to design approaches towards solving these tasks. Future work will look to study the generalization ability of probabilistic models in other domains e.g. text or audio, in order to widen the benefits of the proposed OOD detectors and lossless compressors.

heading: Acknowledgments
text: We would like to thank James Townsend and Tom Bird for discussion on the HiLLoC experiments. We thank Ning Kang for discussion regarding the parallelizability of NeLLoC.

Review summaries:
A surprising observation in the OOD literature is that OOD detection based on density estimation fails on some image datasets since the learned density tends to be higher on OOD data. A hypothesis for this phenomenon is that the likelihood is dominated by the local features of the image, resulting in the high-level features being ignored. Motivated by this observation, this paper proposes a model that learns local features of images. This model is used for two different applications: (1) by combining it with a full density estimation model, it gives a better OOD detection method, achieving state-of-the art performance (2) by pairing the model with the artihmetic coding algorithm, it gives a dataset compression method that achieves state-of-the-art compression rates on in- or out-of-distribution datasets.

Summary: This paper study on applying generative models on unsupervised out-of-distribution detection. Authors hypothesize that local features common to both in-distribution and out-of-distribution data dominate the likelihood of generative models. The authors show evidence of the hypothesis via comparing the fully autoregressive model’s likelihood and autoregressive model with local dependencies. Motivated by the results, the authors propose a ratio between the likelihood of model trained with full-dependencies and the likelihood of model trained with local dependencies. The authors show that the proposed metric outperforms conventional generative-model-based methods on CIFAR-10 and FashionMNIST domains. Finally, the authors apply local autoregressive models on universal lossless compression. The proposed compression scheme outperforms conventional methods. 

This paper proposes a new probabilistic image modeling approach based on a local autoregressive model. The local autoregressive model is implemented like the masked convolution operation in the pixelCNN model. The model is applied to two downstream tasks of OOD detection and lossless image compression. The OOD score is computed using the ratio between the likelihood from the full model versus the one from the local model. The idea is simple but shows some improvement over previous models.