Few-Shot Non-Parametric Learning with Deep Latent Variable Model
Authors: Zhiying Jiang
Yiqin Dai
Ji Xin
Ming Li
Jimmy Lin
Venue: NeurIPS 2022 Accept (2022)
Keywords: Data Compression
Kolmogorov Complexity
Few-Shot Learning
Generative Model

Abstract: Most real-world problems that machine learning algorithms are expected to solve face the situation with (1) unknown data distribution; (2) little domain-specific knowledge; and (3) datasets with limited annotation. We propose Non-Parametric learning by Compression with Latent Variables (NPC-LV), a learning framework for any dataset with abundant unlabeled data but very few labeled ones. By only training a generative model in an unsupervised way, the framework utilizes the data distribution to build a compressor. Using a compressor-based distance metric derived from Kolmogorov complexity, together with few labeled data, NPC-LV classifies without further training. We show that NPC-LV outperforms supervised methods on all three datasets on image classification in the low data regime and even outperforms semi-supervised learning methods on CIFAR-10. We demonstrate how and when negative evidence lowerbound (nELBO) can be used as an approximate compressed length for classification. By revealing the correlation between compression rate and classification accuracy, we illustrate that under NPC-LV how the improvement of generative models can enhance downstream classification accuracy.

Few-Shot Non-Parametric Learning with Deep Latent Variable Model
Zhiying Jiang" 1.2 Yiqin Dai
Ji Xin' University of Waterloo zhiying jian@euaaterlo. ca {ji.xin, mli, hnmnllin/wwateerroooo
Ming Li'
Jimmy Lin'
AFAIK.
quinn@afaik.io io
Abstract
Most real-world problems that machine learning algorithms are expected to solve face the situation with (1) unknown data distribution; (2) little domain-specific knowledge; and (3) datasets with limited annotation. We propose Non-Parametric learning by Compression with Latent Variables (NPC-LV), learning framework for any dataset with abundant unlabeled data but very few labeled ones. By only training generative model an unsupervised way, the framework utilizes the data distribution to build compressor. Using a compressor-base distance metric derived from Kolmogorov complexity, together with few labeled data, NPC-LV classifies without further training. We show that NPC-LV outperforms supervised methods on all three datasets on image classification in the low data regime and even outperforms remi-supervised learning methods on CIFAR-10 10. We demonstrate how and when negative evidence lowerbound (nELBO) can be used approximate compressed length for classification. By revealing the correlation between compression rate and classification accuracy, we illustrate that under NPC-LV how the improvement of generative models can enhance downstream classification accuracy.
Introduction
The progress of deep neural networks drives great success of supervised learning with huge labeled datasets 1 3 However, large labeled datasets are luxurious in many applications and huge amounts of training parameters make the model easy overfit and hard to generalize to other datasets. The urge to learn with small labeled dataset prompts Few-Shot Learning (FSL). However, most few- shot classification settings require either an auxiliary "support set" [4] 5 6 7 that contains classes, each with A samples (c-way k--hot); or prior knowledge about the dataset, where data augmentation can be performed within the same dataset datasets [2 [3]. This setting is not widely applicable to every dataset in practice, as it requires either the elaborate construction of an additional "support set" or augmentation algorithms tailored to specific datasets. Pre-trained models, on the other hand, do not require adhoc "support" and have proved to be good at few-shot learning [14] and even zero-shot learning [15). However, thousands of millions of training parameters make the model hard to be retrained but only fine-tuned. When the data distribution substantially different from any datasets used in pre-training, the inductive bias from pre-training holds up fine-tuning, making the model less pliable [16].
9 10 or from other feaakty-lbelee//mllbeellldiiiii
Goals from the above learning paradigms can be summarized as design algorithms that can be applied to any dataset, and can learn with few labeled data, ideally with no training. "No Free Lunch" [I7 implies that it's impossible have an algorithm that both "universal" and "best". But how good can a "universal" algorithm be, especially in the low data regime, with no external data resources? Specifically, we are interested in a new setting, Non-Supported Few-Shot Learning (NS-FSL), defined as follows:
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Given any target dataset D = (x1,X2,.... X2...., x., belonging to classes. For each class, we have k labeled samples (1 S S 10). The remaining ck unlabeled samples need to be classified into c classes without the need of support sets, any other datasets, or training parameters.
This setting is similar semi-supervised learning's but excludes labeled information in training. Ravi and Larochelle [88 demonstrate that it's hard to optimize neural network when labeled data is scarce. In order to make minimum assumptions about labeled data, we aim at using parameter-free methods. The goal is to grasp the data-specific distribution p(x), with minimal premises on the conditional probability distribution p(y xx. Deep generative models with explicit density estimation are perfect candidates for this goal. The problem then becomes: given trained generative models, how to take full advantage of the information obtained from them for classification? Using a latent representation only utilizes p(z|x), x), which just includes partial information. Even for those latent generative models that do not suffer from posterior collapse [99 p(z) x)'s insufficiency for classification with non- parametric methods like k-nearest-neighhor is shown in both previous works (20 21 and our experiments.
Inspired by previous work that uses compressor
distance metries for non-parametric learn- ing 122 12 24, (25), we propose Non-Parametric learning by Compression with Latent Variables compressors and
(NPC-LV), learning framework that consists of seep-generative-modl-bbeee compressor-basee distance metrics. It leverages the power of deep generative models without ex- ploiting any label information the probabilisstic modeling procedure. With no further training. this framework can be directly used for classification. By separating probabilistic modeling from down- stream tasks that require labels, we grasp the unique underlying structures of the data every dataset, and further utilize these structures in downstream tasks with no parameter tuning needed. We view this learning framework as baseline this setting, for any dataset. We argue it is "parameter-fres as there are no parameters involved in the classification stage for labeled data. Basically it means training a generative model as is and getting a classifier for free.
Our contributions are as follows: (I) We frame existing methods into a general learning framework NPC, based on which we derive NPC-LV, flexible learning framework with replaceable modules. (2) We use NPC-LV as a baseline for a common learning scenario NS-FSL with neither support sets nor further training. (3) Our method outperforms supervised methods by up to 11.8% on MNIST. 18.0% on FashionMNIST, 59% on CIFAR-10 on image classification in the low data regime. outperforms non non-parametric methods using latent representation on all three datasets. It even outperforms semi-supervised learning methods on CIFAR-10. 10. (4) We show how negative evidence lowerbound (nELBO) can be used for classification under this framework. (5) We find the correlation between bitrate and classification accuracy. This finding suggests how improvements in the domain can further boost classification accuracy under this framework.
of
2 Background
2.1 Information Theory - Data Compression
In a compression scenario, suppose we have a sender Alice and a receiver Bob. Alice wants to send a message that contains a sequence of symbols x = of the lossless compressor is compress x into the minimum amount of bits x' that can later be decompressed back to x by Bob. To achieve the shortest compressed length, shorter codes are assigned symbols with higher probability. According to Shannon's 's Source Coding Theorem (26), this length of bits is no shorter than the entropy of the sequence, whose definition is Hxx) & E log Pdata (x)). where Paatu (x) represents the probability distribution of each symbol in the sequence. Instead of coding symbols one by one, stream code algorithms like Asymmetric Numeral Systems (ANS) [27] convert x to sequence of bits x' and reaches this optimal code length for the whole sequence with an overhead of around 2 bits, given Paam (x). However, the "true" probabilistic distribution pdata (x) is unknown to us. We can only access samples and approximate it with pa (x). That is:
Rn,) to Bob. The ultimate goal
E - log po (x)] 2 Hx) A E log Pasta (x)].
(1)
Given an entropy coding scheme, the better (x) approximates Pdata (x). the closer we can get to the minimum code length. Modeling (x(x) is where deep generative model with density estimation can help. Possible coding schemes and generative models for compressors are discussed in 3.2

---

2.2 Algorithmic Information Theory - Kolmogorov Complexity and Information Distance
While information theory is built on data distributions, algorithmic information theory considers "single" objects without the notion of a probability distribution. Kolmogorov complexity K (z) [28] used to describe the length of the shortest binary program that can produce on universal computer, which is the ultimate lower bound of information measurement. Similarly, the Kolmogorov complexity of given y is the length of the binary program that on input outputs x, denoted as K (x]ly) Based on Kolmogorov complexity, Bennett et al. [29] derive information distance E(r, v):
F(x,,)) v) max (<lw)) (ul==)) = K ( - min (K(),, (w))
(2)
The idea behind this measurement, at a high level, that the similarity between two objects indicates the existence of simple program that can convert one to another. The simpler the converting program is, the more similar the objects are. For example, the negative an image is very similar to the original one as the transformation can be simply described as "inverting the color of the image".
Theorem 1. The function E(x,8) y) is an admissible distance and a metric. minimal in the sense that for every admissible distance D, we have Exz, v) D(x, v) 01).
Intuitively, admissible distance refers to distances that are meaningful (e.g., excluding metries like D(r, 3) = 0.3 for any # y) and computable (formal definition is in Appendix B). Combining these definitions, we can see Theorem I means (zz. y) is universal discover all effective similarities between two objects (proof is shown in Appendix H).
way that it is optimal and can
In order to compare the similarity, relative distance is preferred. Li al. 30 propose normalized version of Ea y) called Normalized Information Distance (NID).
Definition 1 (NID). NID is a function: Pt x Q - [0, 1), where Q is non-empty set, defined as: max [ K (I w), K (2)(²)
NID(E,)) y)
max K (x), K K(w)
Equation (3) can be interpreted follows: Given two sequences x. y, K(y) 2 K(x): (a, v) K(y) 1(x y)
[(x y)
(4)
K K(v)
K(y)
where T(x: 9) = K(v) K (yll:) means the mutual algorithmic information. ((ze))
K means the
shared information (in bits) per bit of information contained in the most informative sequence, and Equation 4 here is specific case of Equation 3 Theoreticallly, NID is desirable distance metric as it satisfies the metrie (in)equalities (definition in Appendix B) up to additive precision (11/(() where (-) is the maximum complexities of objects involved in (in)equalities (proof shown in (11
3 Non-Parametrr learning by Compression with Latent Variables
Non- Non-Parametric learning by Compression (NPC) consists of three modules a distance metric, compressor and an aggregation method shown in Figure [ NPC-LV leverages NPC by including neural compressors based on deep generative models. We introduce the derivation of compressor- based distance metrics in Section 3.1 the generative-model-bee based compressor in Section 3.2 an integration of this framework with generative models in Section 3.3
3.1 Compressor-based Distance Metric
Universal as NID is, it is uncomputable, because Kolmogorov complexity is uncomputable. Cilibrasi and Vitányi (32 propose Normalized Compression Distance (NCD), a quasi-universal distance metric based on real-world compressors. In this context, K K(x) can be viewed as the length of x after being maximally compressed. Suppose we have ((x)) as the length of compressed produced by real-world compressor, then NCD is defined as:
NCD(r, y) = C(zy) min (Ca)), C(v))
(5)
Note that K (zy) denotes the length of the shortest program computing x and without telling which one is which (i.e., seperator encoded between and y).
3

---

Compressor
Compressor
Aggregation
Compreesor
Metric
0.48
Probabilisic Model
Coding Scheme
Compressor
10w)
NPC framework with trainable deep probabilistic models. indicated with dashed lines.
Figure 1:
Replaceable modules are
The better the compressor is, the closer NCD approximates NID. With a normal compressor (discussed in detail in Appendix B), NCD has values in [0,1] and satisfies the distance metric (in)equalities up to Ollog n//n) where n means the maximum binary length of a string involved [33] NCD
thus computable in that it not only uses compressed length to approximate K k(x) but also replaces
conditional Kolmogorov complexity with C(ry) that only needs simple concatenation of xr y. Li
al. [31] simplify NCD by proposing another compression-ben based dissimilarity measurement (CDM):
C(ry)
CDM(2, v)
(6)
C(x) CCy)
Chen et al.
24 use another variation ranging from 0 to 1:
CLM(2, v) = C(x) + C(y) C'æy)
C(zy)
NCD, CDM and CLM different variations of Kolmogorov-based distance metries. We empirically evaluate their performance in Section 5
3.2 Trained Generative Models Compressors
Previous works 24 29 demonstrate the suc- cess of compression-basee distance metries in sequential datasets like time series, DNA, and texts using non-neural compressors like gzip, bzip2, PPMZ. Deee--eeerraive-mmdde--ee compressors take Con-maraeettic learning by Compression (NPC) to the next level by ex- panding more data types using better com- pressors. We mainly focus on variational au- toencoder (VAE) based compressors with a brief introduction to other neural compressors.
BB-ANS (Alice: compress)
Initial BE-ANS (Bob: decompress)
received biistream
decode x with g5
decade with p(s)
encode px(Xix)
decode xv(x
encode with pi
encode with (s(x)
Figure BB-ANS compress decompress
VAE Family: The relation between VAE and "bits-back" has been revealed in multiple previous works 34 35) Townsend et al. (36 use latent variable models by connecting Asymmetric Numeral Systems (ANS) (27 the "bits-back" argument [37] (BB-ANS). In the setting of the "bits-back argument", we assume Alice has some extra bits of information to send to Bob alongside x. It's also assumed that both Alice and Bob have access to p(z), Pe (x (x|z) and go (z(x) where z the latent variable; p(z) is the prior distribution of z: Pe ((z) represents a generative network and go (z(z)xx (z/x) represents an inference network. As shown in Figure 2 Alice first decodes the extra information according to qo (z( to generate sample z is further used to encode x with pa (x and z itself encoded using p(z). Bob then reverses this procedure and recovers the extra bits by encoding with qs (z) xz).). For single data point, the length of the final bitstream is:
N Rextra + log (z|x) log Pa (x zz) log p(z).
(8)
We the expectation of N 7lexm is equal the negative evidence lower bound (nELBO):
Note that "encoding", "decoding" here follows data compression's convention instead of variational autoencoder's.

---

Po(x, z)
nextra =
go (ze (x) log
= -ELBO
(9)
4o (z/x)
ELBO above is derived from the back argument" in the context of compression. Now, from the perspective of latent variable models like VAË, the derivation often starts from the fact that px(
(x|2)pp(( is intractable. 4e (z(x)) is then introduced as an inference model to approximate p x
in order work around the intractability problem, which brings up the marginal log likelihood:
po [x,
+ [x((x(x) log (0(z(x)
log pe (x) = 2 (x log
(z (z/z)) x)
p(z]x)
(10)
ELBO po()) Dlas x [lp(2/x)]
We only need to optimize the lower bound, minimizing nELBO means maximizing log (x() the likelihood of generating real data and minimizing KL divergence between (z(z)x) and p(zl p(z|x) at the same time, which is the same objective function from what we derive using "bits-back".
This equivalence demonstrates that an optimized latent variable model can be used directly for compression as, from the data compression perspective, it minimizes the code length attainable by bits-back coding using the model. With the help of ANS, we can encode symbols into bitstreams or decode bitstreams back to symbols with trained latent variable models. Details of ANS and discretizing continuous latent variables are shown in Appendix D and E.
ARM: Autoregressive models (ARMs) model p(x) as: p(x) = p(#o) IT== p(t,p(((1))) The exact likelihood estimation makes it capable of lossless compression. But instead of using ANS, which is a stack-like coding scheme, queue-like ones (e.g., Arithmetic Coding (AC) (38) should be used. Computational inefficiency is the main drawback of ARMs such as RNN [39], but causal convolutions 40 can alleviate the problem.
IDF: Integer Discrete Flow (IDF) can also optimize towards the exact log likelihood. Similar to other flow-based models, it utilizes an invertible transformation f. but works on discrete distributions with additive coupling and rounding operations. For IDF, ANS can be used as the entropy coder.
Our experiments and discussion are mainly about VAE-based compressors as their architectures can be flexibly changed under the "bits-back" argument.
3.3 NPC-LV
We'n ve shown in Section 3.2 that we can plug in any trained latent variable model in exchange for near optimal compressor under the framework of BB-ANS. To show that the coding scheme is replaceable, we introduce a coding scheme variation, Bit-Swap (43) in the following experiments. The difference between BB-ANS and Bit-Swap is the encoding and decoding order when there is more than one latent variable. A detailed comparison is shown in Appendix F. The generative model we use for both BB-ANS and Bit-Swap is hierarchical latent generative model (details are in Appendix G), also known as Deep Latent Gaussian Model (DLGM) 44
Aggregation: In addition coding schemes and probabilistic models for compressors, aggregation methods can also be replaced. Previous works [32] assume zy in C(ry) means the "concatenation" " of two inputs. We expand this assumption to more general case where "aggregation" can be another kind of aggregation function, represented as C'v((1r, y)) in Figure [ We justify this generalization as distance metries not admissible (shown
changing aggregations methods may make compressor-bent in Appendix B). More sophisticated strategies of aggregation are left to future work. We also discuss other replaceable modules in detail Appendix A.
We use BB-ANS with NCD as a concrete instance to demonstrate this framework on a classification task shown in Algorithm| D f and D mean the unlabeled and labeled training sets; predetined functions are in teal. The algorithm can be simplified into four steps: (1) Train a VAE on the unlabeled training dataset; (2) Apply ANS with discretization
the trained VAE to get compressor; (3) Calculate the distance matrix between pairs (Xest: Xtrain) with the compressor and NCD; (4) Run N-Nearest-Neighbor(kANe classifier with the distance matrix.
nELBO as estimated compressed length: Specifically for VAE-based compressors, nELBO the estimated length of the compressed bitstream Equation 9 shows. Therefore, use it directly
5

---

Algorithm 1 NPC-LV (use
VAE and NCD as an example)
Input: k; Diest Drain taiin
D DL
urain DL
(X4, ,4}
train:
trained vae train VAE(D train
vae_ _ne_copressor = (traiid vae)
for Xtest in Drest do
C_Xtest leen/vae_comprrssortxeee..
distances []
for Xuain in X do
// Calculate NCD distance with C(z), Cly), and C(b(x,))) v))
C Xgain = co_ppesserrssoor( aggregate(Xjent Xtrain) )
C_agg- len( ceen(vae_comea
NCD (C_agg min (C Xiest C_Xirain] max (C_ X_eestt X_rina
distances push(NCD, distances)
end for
k
Lenneeee__iniiie ]rgsont(distancces)]:k]]
Vhest majority( i E k [_eerest_indicies]
end for
without actual compression. This can further simplify our method don't need discretize continuous distributions or apply an entropy coder.
The reason why the underlying data distribution can help the classification is based on the manifold assumption, which is a common assumption in SSL [45]. It states that the input space consists of multiple low-dimensional manifolds, and data points lying on the same manifold have the same labels. This assumption helps alleviate the curse of dimensionality and may explain the effectiveness of using ANN with few labeled data. Due to the fact that training process does not use labeled data, our method does not rely on other common assumptions in SSL like the smooth assumption and the low-density assumption. The facts that NPC-LV makes very few assumptions about datasets and that compressors are aatastype- make this framework extensible to other data types beyond images. For example, the combination of autoregressive model (e.g., character recursive neural network) and arithmetic coding [46] can be used in our framework for sequential data.
Related Work
Non-parametric learning with Information Distance: Bennett et al.
29 propose information
distance as universal metric, based on which several papers [47 48
propose more fine-grained
distance metrics. Chen et al. 24 Li et al. [31, Cilibrasi and Vitányi 32 derive more practical distance metrics based without any training parameters, those compressor based distance metries can produce an effective distance matrix for clustering and classification on time series datasets. Cilibrasi and Vitányi B2) further push this direction to more types of datasets, including images that are represented in "#" (black pixel) and "."' (white pixel). We unify previous work in the NPC framework, expand it real image datasets and leverage it with neural compressors.
compressors. Empirical results [2]
23
24
25 show that even
Shannon 26 establishes source coding theorems, showing that entropy rate is the limit of code rate for lossless compression. Huffman Coding [4] achieves the optimal symbol code whose length is upper-bounded by H(x) + 1 per symbol. The I bit overhead is due to the fact that
Compression:
- logg p(z) is not always an integer. Stream coding techniques like AC [38] and ANS [27] further optimize by representing the whole message with numeral systems. These entropy coders then can be combined with probabilistic modeling using neural networks [46 50 5T and used in our framework.
Semi-Supervised Learning with VAE: The evaluation paradigm in this paper is closest to Semi- Supervised Learning (SSL). Kingma et al. [52] design two frameworks for utilizing autoencoders in downstream classification tasks. The first (M1) is to train a tSVM 53) with latent representation output by trained VAE. The second (M2) to train VAE with labels as another latent variable. MI only requires a standard VAE but tSVM suffers from optimization difficulty (54), making it hard
be generally applicable for VAE. More recent VAE-based methods (55] 56) are built on M2. These methods don't 't train a generative model in unsupervised way like we do.

---

Data
MNIST
FashionMNIST
CIFAR-10
#Shot
5
10
50
10
50
10
50
Supervised
Learning
SVM
69.4+22
77.1
87.6#04
67.1+21
71.0#16
78.4
21.
23.6:0.5
27.2+12
#Param
35,280
35,280
105,840
CNN
72.4:35
83.7=26
93.2+28
67.4x19
70.6:25
80.5
23,4
28.3
38. 119
#Param
1.199,882
1,199,882
1,626,442
VGG
69.415.7
83,92332
94.420.
62.814.1
70.51445
81.5
22.2+1.6
29.7
42,6:12
#Param
28.148.362
28.148.362
28.149,514
Semi Semi-Suppervieed Learning
VAT
97.0zo.
97.410.1
98,410.1
74.1208
78.4103
87.1
25.4
27.8
60.9
#Param
1,469,354
1,469,354
1,469,642
MT
78.4+20
82.8+19
98.6+02
58.1
70.8+0x
87.1
31.7+1.
35.9
64.3+14
#Param
1,469,354
1,469,354
1,469,642
Non-Parametric Learning
Single #Param
65.6112
76,8208
86.3103
40.211.1
53.4111
70.020.1
17.3108
19.2.0.7
23,4
Hier #Param
73.613.
82.3.2.1
90.411.4
69.5
72.5119
78.7
22.211.6
24.2.449
26.2129
0
0
Non-Parametric learning by Compression with Latent Variables (NPC-LV)
nELBO
75.2:15
81.4
91.0+10
72.2+22
76.7
85.6#11
34.1+18
34.6=200
35.6:25
#Param
0
Bit-Swap
75.7:36
83,3209
90.91022
73.5137
76.0
82.6:12
32.2
1.
35.7
#Param
0
0
0
BB-ANS
77.6204
84.6221
91.4106
74.1132
77.2.1.
83.2.0.7
35.3
36.0
37.4
#Param
Table 1: Test accuracy of methods with number of learnable parameters for classification. #Shot refers to the the number of training samples per class. Results report means and the 95% confidence interval over five trials. Note that "#Param" refers to parameters specifically for supervised training.
Few-Shot Learning: Similar to our setting, FSL also targets the low labeled data regime. Many previous papers [4] 6 on FSL are based on meta-learning, where the model is fed with an extra
labeled support set, in addition to the target dataset. Another line of work [
9
10
[T] [2
[3] utilize
data augmentation. Although some of them do not require extra datasets [ 9 10 the augmentation
algorithms can hardly be applied to every other dataset [57] Metric-based methods
(58) utilize
distance metrics for FSL. But instead of modeling the probability distribution of a dataset, they model the "distance" between any pair of data points with a neural network, which still requires many labeled data during ppre-training" Our work is similar to metric-based methods in that both have the essence of nearest-neighhor. The difference is that in the "pre-training" stage, our model is not trained to learn the distance but to reconstruct the image as all standard generative models do. More importantly, we use no labeled data in this stage.
Experiments
We compare our method with supervised learning, sumiviupereiee learning, non- -orramaeetric learning and traditional Jon-Parametric learning by Compression (NPC) on MNIST, FashionMNIST and CIFAR-10 [59 60 61]. For each dataset, we first train a hierarchical latent generative model with unlabeled training sets. During the stage of calculating the distance metric using compression, we pick 1,000 samples from the test set, due to the cost of compression and pair-wise computation, together with = (5, 10, 50} labeled images per class from the training set. We also report the result for n = 50 although it is beyond our setting. We keep the selected dataset the same for every method compared. We use bold to highlight the cases outperform supervised methods, use underline to highlight the case we outperform SSL, and use italic to highlight the highest accuracy among all methods for reference. We perform compression with two coding schemes (BB-ANS and Bit-Swap) and also use nELBO for compressed length directly.
Comparison with Supervised Learing: Supervised models are trained on 10n labeled data. In Ta- ble [ when n = 50, CNN and VGG surpass NPC-IV. In the cases where the number of labeled data is extremely limited (c.g., 5, 10 labeled data points per class), however, the BB-ANS variant
7

---

MNIST
FashionMNIST
CIFAR- 10
NCD
CLM
CDM
NCD
CLM
CDM
NCD
CLM
CDM
gzip
86.1
85.6
85.6
81.7
82.6
82.6
31.3
30.3
30.3
bz2
86.8
86.4
86.4
81.7
79.0
79.0
28.0
27.5
27.5
Izma
87.4
88.5
88.5
80.6
82.7
82.7
31.4
30.0
30.0
WehP
86.4
87.9
87.9
69.9
67.3
67.3
33.3
34.2
34.2
PNG
86.8
89.1
89.1
74.8
76.9
76.9
32.2
28.9
28,9
BitSwap
93.2
90.9
93.2
84.3
84.0
84.0
36.9
36,9
36.9
BBANS
93.6
93.4
93.4
84.5
83.6
83.6
40.2
40.8
40.8
Table 2: Classification accuracy using different compressors and distance metrics.
outperforms all methods in every dataset. For MNIST, both BB-ANS and Bit-Swap produce more accurate results than supervised methods on 5-shot experiments; BB-ANS performs slightly better than the supervised methods in the 10-shot scenario. For FashionMNIST, all three variants outperform in 5-shot, 10-shot, and even 50-shot settings. For CIFAR- 10, given 10 labeled data points per class, NPC-LV surpasses the accuracy of CNN by 27.2% and improves the accuracy of VGG by 21.2%. This enhancement is more significant in the 5-shot setting: NPC-LV improves the accuracy of CNN by 50.9% and by 59.0% for VGG. In general, we can see as the labeled data become fewer, NPC-LV becomes more advantageous.
Comparison with Semi-Supervised Learning: The input of NS-FSL is similar to SSL in that both unlabeled data and labeled data are involved. The difference lies in the fact that (1) our training doesn't use any labeled data and is purely unsupervised; (2) only need to train the model once, while SSL needs to retrain for different n; (3) we use fewer labeled data points, which is a more practical setting for real-world problems. We choose strong semi-supervised methods that make few assumptions about the dataset. We use consistency regularization methods instead of pseudo-labeling ones as pseudo-labeling methods often assume that decision boundary should pass through low- density region of the input space (e.g.. Lee (62) ). Specifically, we choose Mean Reachee ("MT") [63] and VAT [64]. The core of both is based
the intuition that realistic perturbation of data points
shouldn't it affect the output. We train both models with n labeled samples per class together with an unlabeled training set (training details are shown in Appendix C).
As we can see, NPC-LV achieves higher accuracy for CIFAR-I0 in the low data regime, has competitive result on FashionMNIST, and is much lower on MNIST. The strength of our method is more obvious with more complex datasets. It's a surprising result because we do not implement any data augmentation implicitly or explicitly unlike consistency regularization methods, which utilize data perturbation and can be viewed as data augmentation. It's worth noting that on all three datasets our method using BB-ANS always outperforms at least one semi-supervised methods on the 10-shot setting, indicating that SSL methods trade "universality" for "performance" while our method is more like a baseline. Speed-wise, NPC-LV only requires training once for the generative model, and can run ANN different shots (n) with no additional cost. In contrast, SSL methods require the whole pipeline to be retrained for every n..
Comparison with Non-Parametric Learning: In this experiment, we explore the effectiveness of using latent representations directly with kNN. We train the same generative model we use in NPC-LV ("Hier"), as well as vanilla VAE with a single latent variable ("Single""). T that the latent representation of the vanilla one not as expressive as the hierarchical one. Although the latent representation using the hierarchical architecture performs reasonably well and surpasses supervised methods in the 5-shot setting on MNIST and FashionMNIST, it's still significantly lower than NPC-LV in all settings. The result suggests that NPC-LV can utilize trained latent variable models more effectively than simply utilizing latent representations for classification.
We investigate how Pon-Paramettic learning by Compression (NPC) with non-neural compressors perform with different distance metrics. We evaluate with NCD, CLM, and CDM as distance metrics, and gzip, bz2, Izma, WebP, and PNG as compressors, using 1,000 images from the test set and 100 samples per class from the training set. The result shown in Table 2 For distance metrics, we can see CLM and CDM perform similarly well but it's not clear under what cireumstances a distance metric superior to the rest. For compressors, both Bit-Swap and BB-ANS perform much better than other compressors, indicating that can significantly improve NPC. BB-ANS turns out to be the best compressor for classification on all three datasets.
Comparison with NPC:
conetiiv-modll-baesee compressors
8

---

Analyses and Discussion
6.1 nELBO as Compressed Length
As we've shown in Section 3.2 nELBO can be viewed as the expected length of the compressed bitstream N Textra Thus, theoretically it can be used directly to approximate compressed length. In this way, we don't t need to apply ANS to VAE for the actual compression, which largely simplifies the method and boosts speed. However, as we can see Table using nELBO doesn't It always perform better than an actual compressor like BB-ANS. This may be because nELBO in a well-trained model regards the aggregation of two images as out-o--distribution data points; while the discretization in the actual compressor forces close probability with certain level of precision to be discretized into the same bin, lowering the sensitivity. Better aggregation strategies need to be designed to mitigate the gap.
6.2 Performance Gain and Task Difficulty
We find that our method is more advan- tageous on more complex datasets with a lower shot number in terms of the relative performance. Specifically, we average all methods' accuracy that NPC-LV compared across different shot settings and datasets, denoted as We then calculate the excess rate with BB-ANS variant's accuracy by b-a 100%. The result is shown in Table The lower left part of the table represents higher task difficulty. As the shot number decreases (from right to left) and/or as the difficulty of the dataset increases (from top to bottom), our framework's performance enhancement gets higher.
5-shot
10-shot
50-shot
MNIST
4.8%
1.9%
-0.1%
MNSHI
22.4%
12.3%
3.9%
CIFAR-10
55.8%
38.1%
6.3%
Table 3: NPC-LV's excess rate compared with the average of all other methods.
6.3 Bitrate versus Classification Accuracy
The origin of the NPC framework comes from intuition that length of x after being maximally compressed by real-world compres- closer sor close K (xx). Theoretically, this length approximates the minimum length of the expression (C(x) & (x)), the closer the compressor-basse distance metrics the normalized information distance. We in-
MNIST
to
FashionMNIST
Accuracy
vestigate, empirically, whether the bitrate tually reflects the classification accuracy. We
plot bitrate versus classification accuracy for
0.4
each compressor in Table 2 on three datasets shown in Figure 3 We use the bitrate, which is (N nexuraa d, where N is the length of the compressed bitstream, nexura the length of the extra bits, and d is the number of pix- els. As can see, a very strong monotonic decreasing correlation between bitrate and ac- curacy emerges, with Spearman coefficient (65] 0..96, meaning the lower the bitrate is, the higher the classification accuracy is. This means the correlation between bitrate and classification accuracy holds empirically regardless of datasets. will be interesting to investigate in the future whether the correlation remains for lossy compression.
WeeP
PNG
CIFAR-10
AMB
Bitrate
Figure 3: Bitrate versus Classification Accuracy

---

6.4 Parallelization and Limitation
The training of generative models can be parallelized using modern GPUs. Compression, however, is not easy to parallelize. The calculation of CDF and PDF are parallelizable for common probability distributions like Gaussian distribution, but the ANS algorithm is not trivial to parallelize. Fortunately, efficient implementations for ANS on GPUs have been developed [6]] to exploit GPU's parallelization power. During distance computation stages, as only pair-wise distances are needed, we can use multiple threads to accelerate the computation. For classification, we show that NPC-LV performs well in the low labeled data regime, where the complexity of computation may not be a concern, yet the complexity of (n²²) may still hinder applications involving pair-wise distance computations like clustering on large datasets, unless we exploit parallelization for compression.
Conclusion
In this paper, propose learning framework, Non-Parametric learning by Compression with Latent Variables (NPC-LV), to address a common learning scenario, Non-Supported Few-Shot-Learning (NS-FSL). This framework is versatile in that every module is replaceable, leading to numerous variations. We use image classification as a case study to demonstrate how to use a trained latent generative model directly for downstream classification without further training. It outperforms supervised learning and non -onrammmtt learning on three datasets and semi-supervie on CIFAR-10 in the low data regime. We thus regard it as baseline in NS-FSI.. The equivalence between optimizing latent variable models and achieving the shortest code length not only shows how nELBO can be used for classification, but also indicates that improvements in latent probabilistic models can benefit neural compressors. The relationship between compression rate and classification accuracy suggests that improvements in neural compressors can further benefit classification. Thus, an enhancement of any module in this chain can boost classification accuracy under this framework.
learning
Acknowledgments
This research was supported in part by the Natural Sciences and Engineering Research Council (NSERC) of Canada, in part by the Global Water Futures program funded by the Canada First Research Excellence Fund (CFREF), and in part by NERC OGP0046506 and Leading Innovative and Entrepreneur teams program of Zhejiang, number 2019R02002, as well as NSFC grant 61 61832019.
References
[1] Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. International Conference Learning Representations (ICLR), 2014.
[2] Ilya Sutskever, Oriol Vinyals, and Quoc V Le. Sequence to sequence learning with neural networks. In Advances Neural Information Processing Systems (NeurIPS), pages 3104-3112, 2014.
[3] Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry, In International Conference on Machine Learning (ICML), pages 1263-1272. PMLR, 2017.
[4] Oriol Vinyals, Charles Blundell, Timothy Lillicrap, Daan Wierstra, et al. Matching networks for one shot learning. Advances in Neural Information Processing Systems (NeurIPS), 29: 3630-3638, 2016.
[5] Harrison Edwards and Amos Storkey. Towards neural statistician. International Conference on Learning Representations (ICLR), 2016.
[6] Jake Snell, Kevin Swersky, and Richard Zemel. Prototypical networks for few-shot learning. In Advances in Neural Information Processing Systems (NeurIPS), pages 4080-4090, 2017.
[7] Flood Sung. Yongxin Yang, Li Zhang, Tao Xiang, Philip HS Torr, and Timothy M Hospedales. Learning to compare: Relation network for few-shot learning. In Proceedings of the IEEE conference on Computer Vision and Pattern Recognition (CVPR), pages 1199-1208, 2018
10

---

[8] Roland Kwitt, Sebastian Hegenbart, and Mare Niethammer. One-shot learning of scene locations via feature trajectory transfer. In Proceedings of the IEEE conference on Computer Vision and Puttern Recognition (CVPR), pages 78-86, 2016.
[9] Bharath Hariharan and Ross Girshick. Low-shot visual recognition by shrinking and hallucinat- ing features. Proceedings of the IEEE International Conference on Computer Vision (ICCV), pages 3018-3027, 2017.
[10] Eli Schwartz, Leonid Karlinsky, Joseph Shtok, Sivan Harary, Mattias Marder, Abhishek Kumar, Rogério Schmidt Feris, Raja Giryes, and Alexander M Bronstein. Delta-encoder: an effective sample synthesis method for few-shot object recognition. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
[11] Tomas Pfister, James Charles, and Andrew Zisserman. Domain-adaptive discriminative one-shot learning of gestures. In European Conference on Computer Vision (ECCV), pages 814-829. Springer, 2014.
[12] Matthijs Douze, Arthur Szlam, Bharath Hariharan, and Hervé Jégou. Low-shot learning with large-scale diffusion. In Proceedings of the IEEE conference on Computer Vision and Pattern Recognition (CVPR), pages
2018.
[13] Hang Gao, Zheng Shou, Alireza Zareian, Hanwang Zhang, and Shih-Fu Chang. Low-shot learning via eerariance-preserviin adversarial augmentation networks. In Advances Neural Information Processing Systems (NeurIPS), 2018.
[14] Tom B Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. arXiv preprint arXiv:2005. 240.:00005..411. 14165, 2020.
[15] Raul Puri and Bryan Catanzaro. Zero-shot text classification with generative language models. arXiv preprint arXiv: 1912:1912..0165, 2019.
[16] Qizhe Xie, Zihang Dai, Eduard Hovy, Thang Luong, and Quoc Le. Unsupervised data augmen- tation for consistency training. Advances in Neural Information Processing Systems (NeurIPS), 33, 2020.
[17] David H Wolpert and William G Macready. No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation, 1(1):67-82, 1997.
[18] Sachin Ravi and Hugo Larochelle. Optimization as model for few-shot learning. International Conference on Learning Representations (ICLR), 2016
[19] Samuel Bowman, Luke Vilnis, Oriol Vinyals, Andrew Dai, Rafal Jozefowicz, and Samy Bengio. Generating sentences from a continuous space. In Proceedings of The 20th SIGNLL Conference on Computational Natural Language Learning, pages 10-21, 2016.
[20] Shengjia Zhao, Jiaming Song, and Stefano Ermon. Infovae: Balancing learning and inference in variational autoencoders. In Proceedings of the AAAI conference on Artificial Intelligence, volume 33, pages 5885-5892. 2019.
[21] Tim R Davidson, Luca Falorsi, Nicola De Cao, Thomas Kipf, and Jakub M Tomezak. Hyper- spherical variational auto-encoders. In Conference on Uncertainty in Artificial Intelligence (UAT), pages 856-865. Association For Uncertainty in Artificial Intelligence (AUAI), 2018.
[22] Xin Chen, Sam Kwong, and Ming Li. A compression algorithm for DNA sequences and its applications in genome comparison. Genome Informatics, 10:51-61, 1999.
[23] Eamonn Keogh, Stefano Lonardi, and Chotirat Ann Ratanamahatana. Towards parameter-free data mining. In Proceedings of the tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 206-215, 2004.
[24] Xin Chen, Brent Francia, Ming Li, Brian Mckinnon, and Amit Seker. Shared information and program plagiarism detection. IEEE Transactions on Information Theory, 50(7):1555-1551, 2004.
11

---

[25] Manuel Cebrián, Manuel Alfonseca, and Alfonso Ortega. Common pitfalls using the normalized compression distance: What watch out for compressor. Communications in Information & Systems, 5(4):367-384, 2005.
[26] Claude Elwood Shannon. A mathematical theory of communication. The Bell System Technical Journal, 27(3)3379 423, 1948.
[27] Jarek Duda. Asymmetric numeral systems. arXiv preprint arXiv:0902.02771, 2009.
[28] Andrei N Kolmogorov. On tables of random numbers. pages 369-376, 1963.
[29] Charles H Bennett, Péter Gács, Ming Li, Paul MB Vitányi, and Wojciech H Zurek. Information distance. IEEE Transactions on Information Theory, 4074):1407-1142,, 1998.
[30] Ming Li, Jonathan H Badger, Xin Chen, Sam Kwong, Paul Kearney, and Haoyong Zhang. An information- based sequence distance and its application to whole mitochondrial genome phylogeny. Bioinformatics, 17(2): 194114,, 2001.
[31] Ming Li, Xin Chen, Xin Li, Bin Ma, and Paul MB Vitányi. The similarity metric. IEEE transactions on Information Theory, 50(12):320-33244 2004.
[32] Rudi Cilibrasi and Paul MB Vitányi. Clustering by compression. IEEE Transactions on Information Theory, 51(4)11523-545, 2005.
[33] Paul MB Vitányi, Frank Balbach, Rudi I. Cilibrasi, and Ming Li. Normalized information distance. In Information Theory and Statistical Learning, pages 45-82 Springer, 2009.
[34] Xi Chen, Diederik P Kingma, Tim Salimans, Yan Duan, Prafulla Dhariwal, John Schulman, Ilya Sutskever, and Pieter Abbecl. Variational lossy autoencoder. International Conference on Learning Representations (ICLR), 2016.
[35] Antti Honkela and Harri Valpola. Variational learning and bits-back coding: an information- theoretic view to bayesian learning. IEEE transactions on Neural Networks, 15(4):800-8 2004.
[36] James Townsend, Thomas Bird, and David Barber. Practical lossless compression with latent variables using bits back coding. In International Conference on Learning Representations (ICLR), 2019.
[37] Brendan Frey and Geoffrey E. Hinton. Efficient stochastic source coding and an application to bayesian network source model. The Computer Journal, 40(2):157-165, 1997.
[38] Ian Witten, Radford M Neal, and John G Cleary. Arithmetic coding for data compression. Communications of the ACM, 30(6):520-54) -400 1987.
[39] David E Rumelhart, Geoffrey E Hinton, and Ronald Williams. Learning internal represen- tations by error propagation. Technical report, California Univ San Diego La Jolla Inst for Cognitive Science, 1985.
[40] Aäron Van den Oord, Nal Kalchbrenner, Lasse Espeholt, Koray Kavukcuoglu, Oriol Vinyals. and Alex Graves. Conditional image generation with pixelenn decoders. In Advances in Neural Information Processing Systems (NeurIPS), volume 29, 2016.
[41] Aaron Van den Oord, Nal Kalchbrenner, and Koray Kavukeuoglu. Pixel recurrent neural networks. In International Conference Machine Learning (ICML), pages 1747-1756. PMLR. 2016.
[42] Emiel Hoogeboom, Jorn Peters, Rianne Van Den Berg, and Max Welling. Integer discrete flows and lossless compression. Advances in Neural Information Processing Systems (NeurIPS), 32.
2019.
[43] Friso Kingma, Pieter Abbeel, and Jonathan Ho. Bit-swap: Recursive bits-back coding for lossless compression with hierarchical latent variables. In International Conference on Machine Learning (ICML), pages 3408-3417. PMLR, 2019.
12

---

[44] Danilo Jimenez Rezende, Shakir Mohamed, and Daan Wierstra. Stochastic backpropagation and approximate inference in deep generative models. In International Conference on Machine Learning (ICML), pages 1288-1286. PMLR, 2014.
[45] Jesper E Van Engelen and Holger H Hoos. A survey on semi-supervised learning, Machine Learning, 109(2):373-440, 2020.
[46] Mohit Goyal, Kedar Tatwawadi, Shubham Chandak, and Idoia Ochoa. Deepzip: Lossless data compression using recurrent neural networks. In 2019 Data Compression Conference (DCC), pages 575-575, IEEE, 2019.
[47] Stéphane Grumbach and Fariza Tahi. A new challenge for compression algorithms: genetic sequences. Information Processing & Management, 3066):85-8888 886, 1994.
[48] Peter N Yianilos. Normalized forms for two common metrics. NEC Res. Inst., Rep, pages 91-082, 2002.
[49] David A Huffman. A method for the construction of minimum-reduudane, codes. Proceedings of the IRE, 1090)1109--111,, 1952.
[50] Jürgen Schmidhuber and Stefan Heil. Sequential neural text compression. IEEE Transactions on Neural Networks, 7(1):142-146, 1996.
[51] Matthew V Mahoney. Fast text compression with neural networks. In FLAIRS conference, pages 230-234, 2000.
[52] Diederik P Kingma, Shakir Mohamed, Danilo Jimenez Rezende, and Max Welling. Semi- supervised learning with deep generative models. Advances in Neural Information Processing Systems (NeurlPS), pages 3581-3589, 2014.
[53] Vladimir Vapnik. The nature of statistical learning theory. Springer science & business media, 1999.
[54] Ronan Collobert, Fabian Sinz, Jason Weston, Léon Bottou, and Thorsten Joachims. Large scale transductive SVMs. Journal of Machine Learning Research, 7(8), 2006.
[55] Lars Maaløe, Casper Kaae Sønderby, Søren Kaae Sønderby, and Ole Winther. Auxiliary deep generative models. In International Conference on Machine Learning (ICML), pages 1445-1453. PMLR, 2016.
[56] Tom Joy, Sebastian M Schmon, Philip HS Torr, N Siddharth, and Tom Rainforth. Rethinking semi-supervised learning in vaes. arXiv preprint arXi::2006. 10102, 2020.
[57] Yaqing Wang, Quanming Yao, James T Kwok, and Lionel M Ni. Generalizing from a few examples: A survey on few-shot learning. ACM Computing Surveys (CSUR), 53(3):1-34, 2020.
[58) Gregory Koch, Richard Zemel, Ruslan Salakhutdinov, et al. Siamese neural networks for one-shot image recognition. In ICML deep learning workshop, volume 2. Lille, 2015.
[59] Yann LeCun and Corinna Cortes. MNIST handwritten digit database. 2010. URL http:
//yann. lecun. www.uncco/eeeeeeeeee wwwpwwwt./ccccecccttct /eeeexddm/mmma/ ewdb//mbbb////////////////m
[60] Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-MNIST: novel image dataset for benchmarking machine learning algorithms. 2017.
[61] Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. 2009.
[62] Dong-Hyun Lee. Pseudo-label: The simple and efficient semi-supervised learning method for deep neural networks. In Workshop on Challenges Representation Learning, ICMI., volume page 896, 2013.
[63] Antti Tarvainen and Harri Valpola. Mean teachers are better role models: Weight-averaged con- sistency targets improve semi-supervised deep learning results. Advances in Neural Information Processing Systems (NeurIPS), 2017.
13

---

[64] Takeru Miyato, Shin-ichi Maeda, Masanori Koyama, and Shin Ishii Virtual adversarial training: a regularization method for supervised and supervisd learning. IEEE transactions on pattern analysis and machine intelligence, 41(8):1979-1993 2018.
[65] Charles Spearman. The proof and measurement of association between two things, The American Journal of Psychology, 100(3/4):441-71, 1987.
[66] Fabian Giesen. Interleaved entropy coders. arXiv preprint 140.:3140..3392, 2014.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes] See abstract and the end of the introduction.
(b) Did you describe the limitations of your work? [Yes] See Section 6.4
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See Appendix I.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs all theoretical results? [Yes] Although we point to the reference for some unimportant proofs.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes] See supplemen-
tary materials.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Appendix C.
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes] See Table
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix C.
4. If you are using existing assets (e.g., code, data, models) or curating/relcasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes] See Section 5 and Appendix C.
(b) Did you mention the license of the assets? [Yes] In both Section and Appendix C. URL? [Yes] The only new asset is our own code and we provide in supplemental material.
(c) Did you include any assets either in the supplemental material
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A] Datasets are public available with MIT license.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A] There are personal or offensive content in MNIST, FashionMNIST and CIFAR10.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A] No crowdsourcing or human subjects involved.
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A] No crowdsourcing or human subjects involved.
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A] No crowdsourcing or human subjects involved.
14


Reviews:
[{"review_id": "bh0kL1mPU-H", "reviewer": "Reviewer_PPrq", "summary": "The paper provides a link between compressed sensing, non-parametric learning, and deep classification networks. By formulating classical compressed sensing results in context of deep learning, the authors propose a learning framework for deep generative modeling using compression, known as Non-Parametric learning by Compression with Latent Variables (NPC-LV). Experiments are conducted on image classification on standard benchmarks (MNIST, CIFAR-10, and Fashion MNIST) and demonstrate compelling results compared to prior work. A strong theoretical analysis support the method.  ", "questions": "In Table 1, for several experiments on MNIST and FashionMNIST, the best performing methods appears to be self-supervised learning and not supervised learning. Why is this the case, and why isn’t supervised learning always achieving top result?\n", "limitations": "Analysis is very thorough and limitations are discussed in section 6.3. Given that one of the limitations is complexity, it would be helpful to report required training/evaluation times and comparison to those of baselines.\n", "rating": 9, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The key strength of the paper is the original and novel idea of unification of two streams of research: compressed sensing and classification using deep neural networks. The description of distances and metric learning from compressed sensing and reformulation into DL terminology is extremely helpful and useful. The proposed method demonstrates very compelling results on three image classification benchmarks, outperforming supervised learning and non-parametric learning methods, and semi-supervised learning under low data regime. Theoretical results include derivation of equivalence between optimizing latent variable models and shortest code length, using negative evidence lower bound (nELBO) analysis. Empirically, the authors also show an inverse relationship between accuracy and bitrate. \n\nOverall, the paper is very promising and has few weaknesses. The key limitation seems to be that analysis is focused on VAE and image classification. It would be valuable to understand the relationships of NPC-LV with respect to other popular generative models, e.g., GANs. In computer vision, is is standard practice to learn a good representation, e.g., using VAE or GAN, and re-use the learned space for fine-tuning to many down-stream tasks. In this context, it may be valuable to understand evaluate how good of a representation does NPC-LV learn in comparison to VAE/GAN. However, even with existing analysis and setup, I believe the paper is very promising and would encourage research at the intersection of compressed sensing and DL representation learning, and thus a great contribution to NeurIPS. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "UvZRE5Qm_wD", "reviewer": "Reviewer_679F", "summary": "Hi all, I am so very sorry for the incorrect review !! \n\nThe authors prropose a strategy for few shot learning by using data compression and nearest neighbor classification.  They focus in particular on a distance based on the kolmogorov complexity. The latter being uncomputable, the authors use different types of compression-based distances.\n\nGiven a couple of images, the authors thus compress each individually as well as their aggregation in order to be able to compute the distance.\n\nThe authors test their méthodes on multiple datasets : MNIST, FASHIONMNIST and CIFAR10 and show very competitive results.", "questions": "What is the effect of the difficulty of the task ? How such a method compete with other representation learning strategies ?", "limitations": "Limitations are given and discussed by the authors in section 6.3.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\nThe paper propose a novel method based on theoretical grounds and demonstrate its usability with deep learning. The paper seems theoretically sounds. It is very easy to read and the context is well presented for non expert readers. The experimental section support the contribution with competitive results.\n\n## weaknesses\nThe datasets are known to be easy discriminative tasks... I think that it woul be interesting to see how the method generalizes with more difficult tasks. A deeper focus on representation learning strategies would help get insight about the benefit of the method.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "6248v5RrBvu", "reviewer": "Reviewer_oRFK", "summary": "This paper describes a generative model trained in an unsupervised fashion which utilizes the data distribution to build the compressor. The theory presented in this paper is a minor extension of previous work (see the details below) and the experimental results is not convincing and lack of interpretation and detailed analysis.", "questions": "As I pointed out in the weakness of the paper, weak evaluations and lack of interpretations are the main issue of the paper. It will be helpful if the paper can detail the analysis and reveal the insights about why the proposed method can outperform the supervised methods and semi-supervised methods using ablation study. It is also important to make the experimental section more convincing with fair comparison.\n\nMoreover, it is critical to make sure the theory is well connected to the experimental results and support the performance gains.\n\nLast but not least, it is imperative to enhance the uniqueness (novelty) of the paper by explaining the difference of the paper compared to [36] as applying the compression theory to the distance metric in few-shot learning seems to be straight forward and the improvement is incremental.", "limitations": "N.A.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The strength of the paper lies in that it proposes a compression-based distance metric and applied it to the few-shot learning.  The experimental results show that the proposed method outperforms some of supervised methods and semi-supervised learning methods on image classification.\n\nThe weakness are as follows:\n\n(1)\tCompared to the theory proposed in the reference [36], the contribution of this paper seems to be quite incremental as they are all about performing lossless compression with latent variable models. The mathematical framework is largely similar and the intuition behind is the same. The only difference is that in this paper, the compression is applied to the distance metric in few-shot learning setting up which turns out to be a pretty straight-forward extension of [36].\n(2)\tThe experimental results shown in the paper is somewhat not convincing. For instance, the paper claims that the performance of the proposed method is better than supervised learning methods. However, the paper fails to present what components and for what reasons it can outperform supervised learning methods. Because with data samples are fully labeled, supervised learning performances are frequently served as a upper bound of the semi-supervised learning or few-shot learning performances. Without detailed explanations and looking into the insight of the comparison, it is hard to believe the fairness of the comparison.\n(namely is the supervised learning methods state-of-the-art, how are the parameter settings of these comparative methods etc)\n(3)\tThe theory presented in this paper are either an extension of the work in [36] or disconnected with the experimental results presented afterward. Namely, I have no idea how to apply these theory to the few shot learning problem and how does these theory support the incremental performance in the experiments. As intuitively, if we compress the distance, we either lose the information and preserve all the information (will not increase the information), so it is not clear where the performance gain comes from. A separate ablation study may help to illustrate the performance gain.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept