The Unreasonable Effectiveness of Patches in Deep Convolutional Kernels Methods
Authors: Louis THIRY
Michael Arbel
Eugene Belilovsky
Edouard Oyallon
Venue: ICLR 2021 Poster (2021)
Keywords: convolutional kernel methods
image classification

Abstract: A recent line of work showed that  various forms of convolutional  kernel methods can be competitive with standard supervised deep convolutional networks on datasets like CIFAR-10, obtaining accuracies in the range of 87-90% while being more amenable to theoretical analysis. In this work, we highlight the importance of a data-dependent feature extraction step that is key to the obtain good performance in convolutional kernel methods. This step typically corresponds to a whitened dictionary of patches, and gives rise to a data-driven convolutional kernel methods.We extensively study its effect, demonstrating it is the key ingredient for high performance of these methods. Specifically, we show that one of the simplest instances of such kernel methods, based on a single layer of  image patches followed by a linear classifier is already obtaining classification accuracies on CIFAR-10 in the same range as previous more sophisticated convolutional kernel methods. We scale this method to the challenging ImageNet dataset, showing such a simple approach can exceed all existing non-learned representation methods. This is a new baseline for object recognition without representation learning methods, that  initiates the investigation of  convolutional kernel models  on ImageNet. We conduct experiments to analyze the dictionary that we used, our ablations showing they exhibit low-dimensional properties.

Published as a conference paper at ICLR 2021
THE UNREASONABLE EFFECTIVENESS OF PATCHES IN DEEP CONVOLUTIONAL KERNELS METHODS
Louis Thiry
Michael Arbel
Département d' Informatique de I'ENS ENS, CNRS, PSL. University Paris, France louis. wew.ttiirrres.e fr
Gatsby Computational Neuroscience Unit
University College London
London, United Kingdom
michael. n. abe 1 gma com
Eugene Belilovsky
Edouard Oyallon
Concordia University and Mila
CNRS, LIP6, Sorbonne University Paris, France @douard.oyallooee ip.. fr
Montreal, Canada
eugene. bugene.bellr looskyyoooooorra......
ABSTRACT
A recent line of work showed that various forms of convolutional kernel methods be competitive with standard supervised deep convolutional networks on datasets like CIFAR-10, obtaining accuracies in the range of 87 90% while being more amenable theoretical analysis. In this work, we highlight the importance of a data-dependent feature extraction step that is key to the obtain good performance in convolutional kernel methods. This step typically corresponds to a whitened dictionary of patches, and gives rise to data-driven convolutional kernel methods. We extensively study its effect, demonstrating is the key ingredient for high performance of these methods. Specifically, we show that one of the simplest instances of such kernel methods, based on a single layer of image patches followed by a linear classifier is already obtaining classification accuracies CIFAR-10 in the same range as previous more sophisticated convolutional kernel methods. We scale this method to the challenging ImageNet dataset, showing such simple approach can exceed all existing non-learned representation methods. This is a new baseline for object recognition without representation learning methods, that initiates the investigation of convolutional kernel models on ImageNet. We conduct experiments analyze the dictionary that used, our ablations showing they exhibit low- diweeniiioonll properties.
INTRODUCTION
Understanding the success of deep convolutional neural networks on images remains challenging because images are high-dimensional signals and deep neural networks are highly-non linear models with substantial amount of parameters: yet, the curse of dimensionality is seemingly avoided by these models. This problem has received plethora of interest from the machine learning community,
One approach taken by several authors (Mairal 2016 Li al.. 2019 Shankar al. 2020 Lu et al. 2014) has been to construct simpler models with more tractable analytical properties (Jacot et al.
2018 Rahimi and Recht 2008). that still share various elements with standard deep learning models.
Those simpler models are based on kernel methods with a particular choice of kernel that provides a convolutional representation of the data. In general, these methods are able achieve reasonable performances on the CIFAR- 10 dataset. However, despite their simplicity compared to deep learning models, it remains unclear which ones the multiple ingredients they rely on are essential. Moreover, due to their computational cost, it remains open to what extend they achieve similar performances on more complex datasets such as ImageNet. In this work, we show that an additional implicit ingredient, common to all those methods, consists in data- deta-dependent feature extraction step that makes the convolutional kernel driven (as opposed to purely handcrafted) and is key for obtaining good performances.

---

Published as a conference paper at ICLR 2021
Data driven convolutional kernels compute similarity between two images x and y, using both their translation invariances and statistics from the training set of images X. In particular, we focus on similarities K that obtained by first standardizing representation d of the input images and then feeding it to predefined kernel k:
K ( k(LØz, Loy),
where a rescaling and shift is (potentially) performed by a diagonal affine operator L = L( and is mainly necessary for the optimization step Jin et al. (200)): it is typically standardization. The kernel K (ac, y) is said to be data-driven if 4 depends on training set X, and data-independent
otherwise. This, for instance, is the case if dictionary is computed from the data (Li et al. 2019
Mairal 2016; Mairal et al.) 2014) or a ZCA (Shankar et al. 2020) is incorporated in this representation. The convolutional structure of the kernel K can come either from the choice of the representation +
(convolutions with a dictionary of patches (Coates et al. (011)) or by design of the predefined kernel k (Shankar et al. 2020),
combination of both (Li et al. 2019 Mairal 2016). One of the goal of this paper is to clearly state that kernel methods for vision do require to be data-driven and this is explicitly responsible for their success. We thus investigate, to what extent this common step is responsible for the success of those methods, via a shallow model.
Our methodology is based on ablation experiments: we would like to measure the effect of incorpo- rating data, while reducing other side effects related to the design of Q, such as the depth of Φ or the implicit bias of a potential optimization procedure. Consequently, we focus on 1-hidden layer neural networks of any widths, which have favorable properties, like the ability to be a universal approximator under non-restrictive conditions. The output linear layer shall be optimized for a classi- fication task, and we consider first layers which are predefined and kept fixed, similarly to Coates et al. (201T). We will see below that simply initializing the weights of the first layer with whitened patches leads to significant improvement of performances. compared to random initialization, wavelet initialization or even a learning procedure. This patch initialization is used by several works eLi al. 2019; Mairal 2016) and is implicitly responsible for their good performances. Other works rely on a whitening step followed by very deep kernels (Shankar et al., (020). yet we noticed that this was not sufficient in our context. Here, we also try to understand why incorporating whitened patches is helpful for classification. Informally, this method can be thought as one of the simplest possible in the context of deep convolutional kernel methods, and we show that the depth or the non- non-lineassties of such kernels play a minor role compared to the use of patches. In our work, we decompose and analyze each step of our feature design, on sold-standard datasets and find that a method based solely on patches and simple non-linearities is actually a strong baseline for image classification.
We investigate the effect of patch-based pre-processing for image classification through a simple baseline representation that does not involve learning (up to linear classifier) on both CIFAR-10 10 and ImageNet datasets: the path from CIFAR- 10 to ImageNet had never been explored until now in this context. Thus, we believe our baseline to be of high interest for understanding ImageNet's convolutional kernel methods, which almost systematically rely on patch (or descriptor of a patch) encoding step. Indeed, this method is straightforward and involves limited ad-hoe feature engineering compared to deep learning approach: here, contrary to (Mairal) 2016 Coates et al. 201 1 Recht eet al. 2019 (Shnnaar al. 2020; Li al., 2019) employ modern techniques that are necessary for scalability (from thousands to million of samples) but can still be understood through the lens of kernel methods (e.g., convolutional classifier, data augmentation, ...). Our work allows understand the relative improvement of such encoding step and we show that our method is a challenging baseline for classification on Imagenet: we outperform by a large margin the classification accuracy of former attempts to get rid of representation learning on the large-scale ImageNet dataset.
While the literature provides a detailed analysis of the behavior of a dictionary of patches for image compression (Wallace 1992), texture synthesis (Efros and Leung] 1999) or image inpainting (Criminisi et al. 2004), we have a limited knowledge and understanding of in the context of image classification.
The behavior of those dictionaries of patches in some classification methods is still not well un- derstood, despite often being the very first component of many classic vision pipelines (Perronnin et al. 2010: Lowe 2004, Oyallon et al. 2018b). Here, we proposed a refined analysis: we define a Euclidean distance between patches and show that the decision boundary between image classes can be approximated using a rough description of the image patches neighborhood: it is implicd for instance by the fame low-dimensional manifold hypothesis (Fefferman al. 2016).
2

---

Published as a conference paper at ICLR 2021
Our paper is structured follows: first, discuss the related works in Sec. Then, Sec. explains paper precisely how our visual representation is built. In Sec. 4 we present experimental results on the vision datasets CIFAR-10 10 and the large scale ImageNet. The final Sec. 4.3 is collection of numerical experiments to understand better the dictionary of patches that we used. Our code as well as commands to reproduce results are available here: https:: :tttps://gtii thu. com www.looitooopaaaaeaooooa
RELATED WORK
The seminal works by Coates et al. (2011) and[Coates and Ng (2011) study patch-bat based representations for classification on CIFAR- 10. They set the first baseline for a single-layer convolutional network initialized with random patches, and they show it achieve non-trivial performance (~ 80%) on the CIFAR-10 10 dataset. Recht et al. (2019) published an implementation of this technique and conducted numerous experiments with hundreds of thousands of random patches, improving the accuracy (~ 85%) on this dataset. However, both works lack two key ingredients: online optimization procedure (which allows to scale up to ImageNet) and well-designed linear classifier (as we propose factorization of our linear classifier).
Recently, (Li et al. 2019; Shankar et al., 2020) proposed to handcraft kernels, combined with deep learning tools, in order to obtain high-performances on CIFAR-10. Those performances match standard supervised methods (~ 90%) which involve end-to-end learning of deep neural networks. Note that the line of work (Li et al.] 2019 Shankar et al.) 2020 Mairal 2016) employs well- enginecred combination of patch-cxtracted representation and a cascade of kernels (possibly some neural tangent kernels). While their works suggest that patch extraction is crucial, the relative improvement due to basic-hyper parameters such as the number of patches or the classífier choice is unclear, well the limit of their approach to more challenging dataset. We address those issues.
From a kernel methods perspective, a dictionary of random patches can be viewed as the building block of random features method (Rahimi and Recht 2008) that makes kernel methods computationally tractable. |Rudi et al. (017) provided convergence rates and released an efficient implementation
of such a method. However, previously mentioned kernel methods (Mairal 2016 Li et al. 2019
Shankar et al.) 2020) have not been tested on ImageNet to our knowledge.
Simple methods involving solely a single-layer of features have been tested on the ImageNet-2010 datase] | using for example SIFT, color histogram and Gabor texture encoding of the image with K K-nearest neighbors, yet there is substential gap in accuracy that we attempt to fill in this work on ImageNee-2012 2 (or simply ImageNet). We note also that CNNs with random weights have been tested on ImageNet, yielding to low accuracies (~~ 20% top-1, (Arandjelovic et al. 2017)).
The Scattering Transform (Mallat 2012) is also deep non-linear operator that does not involve representation learning, which has been tested on ImageNet (~ 45% top-5 accuracy (Zarka et al. 2019) and CIFAR-10 (~ 80%. (Oyallon and Mallat 2015)) and is related to the HoG and SIFT transforms (Oyallon et al., 2018a). Some works also study directly patch encoders that achieve competitive accuracy ImageNet but involve deep cascade of layers that are difficult to interpret (Oyallon et al. 2017 Zarka et al. 2019 Brendel et al. 2019). Here, we focus on shallow classifiers.
3 METHOD
We first introduce our preliminary notations to describe an image. A patch p of size P of a larger image x, is a restriction of that image to squared domain of surface 2a We denote by 2 the size of the natural image x and require that P < N. Hence, for a spatial index i of the image, Pi.z represents the patch of image located at i. We further introduce the collection of all overlapping patches of that image, denoted by: Pa = {pr... i E Σ} where I is a spatial index set such that [ (N - P + 2 Fig. D corresponds to an overview of our classification pipeline that consist of 3 steps: initial whitening step of dictionary D of random patches, followed by a nearest neighbor quantization of images patches via 'D that are finally spatially averaged.
As one see on the Imagenet2010 leaderboard http://mgeenet.rgcccllleeeee/eee the accuracies on ImageNet2010 and ImageNet2012 are comparable.
and
3

---

Published as a conference paper at ICLR 2021
Whitening We describe the single pre-processe pre-processing step that we used on image data, namely whitening procedure on patches. Here, we view natural image patches of size P as samples from random vector of mean I and covariance E. We then consider whitening operators which act at the level each image patch by first subtracting its mean then applying the linear transformation -1/2 to the centered patch. The additional whitening regularization with parameter
W = (AI+ + 2 was used to avoid ill- ill-conditionnn effects.
Figure 1: Our classification pipeline described synthetically to explain how we build the representation Φ of an input image
Dictionary D
Dictionary D
Representation
input. T
patch
patch
pasch 2
patch 2
Split image in overlapping patches
Find Q nearest neighbours per patch
Spetial
Average pooling
The whitening operation is defined up isometry, but the Euclidean distance between whitened patches (i.e., the Mahamobolis distance (Chandra et al. I936)) is not affected by the choice of such isometry (choices leading PCA, 7CA, ...,, as discussed in Appendix A. In practice, the mean and covariance are estimated empirically from the training set to construct the whitening operators. For the sake of simplicity, we only consider whitened patches, and unless explicitly stated, we assume that each patch is already whitened, which holds in particular for the collection of patches in Pa of any image z. Once this whitening step is performed, the Euclidean distance over patches is approximatively isotropic and is used in the next section to represent our signals.
Figure 2: example whitened dictionary D with patch size P 6 from ImageNet- 128 (Left), ImageNet-64 (Middle), CIFAR-10 10 (Right). The atoms have been reordered via topographic algorithm from Montobbio et (2019) and contrast adjusted.
Q-Nearest Neighbors on patches The basic idea of this algorithm is compare the distances between each patch of an image and a fixed dictionary of patches D, with size [D] that is the number of patches extracted. Note that we also propose a variant where we simply use a soft-assignment operator. For a fixed dataset, this dictionary ' is obtained by uniformly sampling patches from images over the whole training set. We augment D into UJED -d3 because allows the dictionary of patches to be contrast invariant and we observe it leads to better classification accuracies; we still refer to it as D. An illustration is given by Fig. 2 Once the dictionary D is fixed, for each patch Pi.z consider the set C, of pairwise distances C,,z {llp,.> dll D). For each whitened patch we encode the Q-Nearest Neighbors of p..z. from the set D, for some Q E More formally, consider Tizz the Q-th smallest element of Cr and define the Q-Nearest Neighbors binary
4

---

Published as a conference paper at ICLR 2021
encoding follow, for (d. D I:
d(z)a1 f1, 1, [l... dll S Ti.
0, otherwise.
Eq. can be viewed as a Vector Quantization (VQ) step with hard-assignment (Coates and Ng 2011 The representation encodes the patch neighborhood in subset of randomly selected patches and can be seen as a crude description of the topological geometry of the image patches. Moreover, it allows to view the distance between two images 2, y as Hamming distance between the patches neighborhood encoding as:
Σ Lo( 1,d
In order to reduce the computational burden of our method, we perform an intermediary average- pooling step. Indeed, we subdivide I in squared overlapping regions Ij C I, leading to the representation d defined, for d E D by:
(())s. = Σ (())d VEZ
(4)
Hence, the resulting kernel simply given by K(x,y) = (x)), P(y)) Implementation details can be found in Appendix B. The next section describes classification pipeline, as we feed our representation to a linear classifier on challenging datasets.
4 EXPERIMENTS
We train shallow classifiers, i.e. linear classifier and 1-hidden layer CNN (I-layer) on top of our representation & on major image classification datasets, CIFAR-10 and ImageNet, which consist respectively of 50k small and 1.2M large color images divided respectively into 10 and 1 classes. For training, systematically used mini-batch SGD with momentum of 0.9, no weight decay and using the cross-entropy loss.
Classifier parametrization In each experiments, the spatial subdivisions Ij are implemented as an average pooling with kernel size 1 and stride 81. We then apply 2D batch-normalization (loffe and Szegedy| 2015) in order to standardize our features on the fly before feeding them to a linear classifier. In order reduce the memory footprint of this linear classifier (following the same line of idea of a "bottleneck" (He et al. 20166), we factorize into two convolutional operators. The first with kemeel size liz and stride reduces the number of channels from D co and the second one with kernel size K3 and stride 1 outputs a number of channel equal to the number of image classes. Then we apply a global average pooling. For the 1-hidden layer experiment, we simply add a ReLU non linearity between the first and the second convolutional layer.
4.1 CIFAR-10
Implementation details Our data augmentation consists in horizontal random flips and random crops of size 322 after reflect-padding with pixels. For the dictionary, choose patch size of P 6 and tested various sizes of the dictionary [D] and whitening regularization = 0.001 In all cases, used at epochs 100 and 150. The initial learning rate is 0.003 for (D] 2k and 0.001 for larger (D).
0.4/D). The classifier is trained for 175 epoch with learning rate decay of 0.1
Single layer experiments For the linear classification experiments, we used an average pooling of size k1 = and stride $ = 3, l2 1 and C2 128 for the first convolutional operator and k3 = 6 for the second one. Our results are reported and compared in Tab. Ta First, note that contrary to experiments done by CCoates et al. (2011), 1), our methods has surprisingly good accuracy despite the hard-assignment due to VQ. Sparse coding, soft-thresholding and orthogonal matching pursuit based representations used by Coates and Ng (2011): Recht al. (2019) can be seen soft-assignment VQ and yield comparable classification accuracy (resp. 81.5% with 6. patches and 85.6% with 2. 10 patches). However, these representations contain much more information than hard-assignment
5

---

Published as a conference paper at ICLR 2021
Table 1: Classification accuracies on CIFAR-10. VQ indicates whether vector quantization with hard-assignment is applied on the first layer.
(a) One layer patch-based classification accuracies on CIFAR-IO. Amongst methods relying on random patches
ours is the only approach operating online (and therefore allowing for scalable training).
Method
[
VQ
Online
P
Acc.
Coates et al. (2011
1k
6
68.6
Ba and Caruana (2014)
4k
X
/
81.6
Wavelets Ovallon and Mallat
2015
x
x
8
82.2
Recht et (2019)
0.2M7
x
85.6 6
SimplePatch (Ours)
10k
/
6
85.6
SimplePatch (Ours)
60A
6
86.7
SimplePatch (Ours)
60k:
6
86.9
(b) Supervised accuracies on CIFAR- 10 with comparable shallow supervised classifiers. Here, e2e stands for end-to-end classifier and I-layer for a I-layer classifier.
Method
VQ
Depth
Classifier Acc.
SimplePatch (Ours)
2
1-layer
88.5
AlexNet Krizhevsky et al. 2012)
x
5
e2e
89.1
NK (Shankar et al.. 2020)
x
5
e2e
89.8
CKN (Mairal 2016)
9
c2e
89.8
(c) Accuracies on CIFAR-10 with Handcrafted Kernels classifiers with and without data-driven reprensentations. For SimplePatch we replace patches with random gaussian noise. D-D stands for Data-Driven and D-I for Data-Independent.
Method
VQ
Online
Depth
D-I Accuracy (D-D Improvement)
Data used
Linearized (Samarin al. 2020)
x
65.6 (13.2)
e2e
NK (Shankar et al. 2020)
x
x
5
77.7 (8.1)
ZCA
Simple (random) Patch (Ours)
7
78.6 (8.1)
Patches
CKN (Mairal 2016)
2
(5.T
Patches
poo.............................
NTK L al. 2019)
X
X
Patches
TThis result was obtained from private communication with the author.
VQ as they allow to reconstruct large part of the signal. We get better accuracy with only coarse topological information on the image patches, suggesting that this information highly relevant for classification. To obtain comparable accuracies with a linear classifier, we use a single binary encoding step compared to Mairal (2016) and we need much smaller number of patches than Recht et al. ( and Ng (2011 Moreover, Recht et al. (2019) is the only work in the litterature. besides us, that achieves good performance using solcly linear model with depth one. To test the VQ importance, we replace the hard-assignment VQ implemented with binary non-linearity 1 -dl== (see Eq. 2 by a soft-assigmment VQ with a sigmoid function (1 + <llps..-[I-T.a) The accuracy increases by 0.2%, showing that the use soft-assignment in VQ which is crucial for performance in Coates and Ng (20TT) does not affect much the performances of our representation.
Importance of data-driven representations As we see in Tab the data-driven representation crucial for good performance of handcrafted kernel classifiers. We remind that a data-independent kernel is built without using the dataset, which is for instance the case with neural network randomly initialized. The accuracies from Shankar et al. 2020) correspond to Myrtle5 (CNN and kernel), because the authors only report accuracy without ZCA for this model. As sanity check, consider whose atoms are sampled from a Gaussian white noise: this step leads to a drop of 8.1 1. This is aligned with the finding of each work compared to: performances drop if no ZCA is

---

Published as a conference paper at ICLR 2021
Figure CIFAR-IO ablation experiments, train accuracies in blue, test accuracies in red.
accuracy (96)
100
100
100
100
80
210 2
2'
10.
10a
10 10 10
number of patches [n]
number of neighbors Q
patch size
whitening reqularization
applied or if patches are not extracted. Using dictionary of size |D] 2048, the same model trained end-to-end (including the learning of 'D) yields to the same accuracy (- 0.1 %), showing that here, sampling patches is as efficient as optimizing them. Note that our method also outperforms linearized
deep neural networks (Samarin al. 2020), i.e. trained in a lazy regime (Chizat et al. 2019).
Non-linear classification experiments To test the discriminative power of our features, use 1-hidden layer classifier with ReLU non-linearity and an average pooling of size k = 3 and stride 81 2, log = C2 2048 and hg 7 Our results are reported and compared with other non-linear classification methods in Tab [b Using a shallow non-linear classifier, our method is competitive with end-to-end trained methods (Li al. 2019 Shankar al. 2020; Krizhevsky et al., 2012). This further indicates the relevance of patches neighborhood information for classification task.
Syyper-paramete analysis CIFAR-10 is relatively small dataset that allows fast benchmarking. thus we conducted several ablation experiments order to understand the relative improvement due to each hyper-parameter of our pipeline. We thus vary the size of the dictionary [D], the patch size P. the number of nearest neighbors Q and the whitening regularization À which are the myyer-paramette of Φb Results are shown in Fig. 3 Note that even relatively small number of patches is competitive with much more complicated representations, such as Oyallon and Mallat (2015). While is possible to slightly optimize the performances according to P or Q, the fluctuations remain minor compared to other factors, which indicate that the performances of our method are relatively stable w.r.t. this set of syper-parameters. The whitening regularization behaves similarly to thresholding operator the eigenvalues of 1//2 it penalizes larger eigenvalues. Interestingly, we note that under certain threshold, this hand with both fast eigenvalue decay and stability to noise, that we discuss further in Sec. 4.3
does almost not affect the classification performances. This goes in
4.2 IMAGENET
Implementation details To reduce the computational overhead of our method on ImageNet, we followed the same approach as Chrabaszez et al. (2017): we reduce the resolution to 642, instead of the standard 224 length. They observed that this does not alter much the top-performances of standard models (5% to 10% drop of accuracy on average), and we also believe it introduces useful dimensionality reduction, as it removes fighffrryeency part of images that unstable (Malltt 1999.. We set the patch size to P = 6 and the whitening regularization to X = 10 Since ImageNet is much larger than CIFAR-10. CIFAR-10, we set Q = O.4/D). The parameters of the linear convolutional classifier are chosen to be: k 10, 6, l2 1, C2 256, k3 7. For the 1-hidden layer experiment, we used kernel size of l2 = -3 for the first convolution. Our models are trained during 60 epochs with an initial learning rate of 0.003 decayed by a factor 10 at epochs 40 and 50. During training, similarly to Chrabaszez et al.) (2017) we use random flip and we select random crops of size 64, after reflect-padding of size testing, we simply resize the image to 64. Note this procedure differs slightly from the usual procedure, which consists in resizing images while maintaining ratios, before random cropping.
restricted to |D] 2048 patches. As for
Classification experiments Tab 2a reports the accuracy of our method, as well as the accuracy of comparable methods. Despite a smaller image resolution, our method outperforms by a large margin (~ 10% Top5) the Scattering Transform (Mallat) 2012). which was the previous state-of-the-at method in the context of no roprressenntaoon learning. Note that our representation uses only 2.103 randomly selected patches which is tiny fraction of the billions of ImageNet patches.
7

---

Published as a conference paper at ICLR 2021
Table 2: Accuracy of our method on ImageNet.
(a) Handcrafted accuracies on ImageNet, via linear classifier. No other weights are explicitely optimized.
Method
[D]
VQ
P
Depth
Resolution
Top1
Tops
Random (Arandjelovic et al. 2017)
x
9
224
18.9
Wavelets (Zarka et al.] 2019)
X
32
2
224
26.1
44.7
SimplePatch (Ours)
2k
V
6
64
33.2
54.3
SimplePatch (Ours)
2k
12
128
35.9
57.4
SimplePatch (Ours)
2k
12
128
36.0
57.6
(b) Supervised accuracics on ImageNet, for which our model uses |D] = 2048 patches. c2c, 1-layer respectively stand for end-to-end, 1-hidden layer classifier.
Method
VQ
P
Depth
Resolution
Classifier
Top1
Top5
Belilovsky et al.
2018
224
e2e
26
Belilovsky et al.
2018
X
224
e2e
44
SimplePatch (Ours)
6
64
1-layer
39.4
62.1
BagNet (Brendel al. 2019)
9
50
224
e2e
70.0"
In 2b compare our performances with supervised models trained end-to-end, which also use convolutions with small receptive fields. Here, D = 2k. BagNets (Brendel et al.) 2019) have shown that competitive classification accuracies can be obtained with patch-encoding that consists of 50 layers. The performance obtained by our shallow experiment with --hidden layer classifier competitive with a BagNet with similar patch-size. It suggests once again that hard-assignment VQ does not degrade much of the classification information. We also note that our approach with a linear classifier outperforms supervised shallow baselines that consists of I or hidden-layee CNN (Belilovsky et al. 2018), which indicates that patch based representation is non-trivial baseline.
To measure the importance of the resolution on the performances, we run a linear classification experiment on ImageNet images with twice bigger resolution (N = 1282 Q = 12, l = 20, $1 = 12). observe that it improves classification performances. Note that the patches used are a space of dimension 432 >>> 1: this improvement is surprising since distance to nearest neighbors are known to be meaningless high- nigh-dimension (Beyer et al.) 1999). This shows form of low-dimensionality in the natural image patches, that study in the next Section.
4.3 DICTIONARY STRUCTURE
The performance obtained with the surprisingly simple classifier hints to a low dimensional structure in the classification problem that exploited by the patch based classifier we proposed. This motivates us to further analyse the structure of the dictionary of patches to uncover a lower dimensional structure and to investigate how the whitening, which highly affects performance, relates to such lower-dimensional structure.
Spectrum of As a preliminary analysis, we propose to analyse the singular values (spectrum) of 2/// sorted by a decreasing order as x 2 2 Adare with dext = 3p22 being the extrinsic dimension (number of colored pixels in each patch). From this spectrum, it is straightforward to compute the covariance dimension deoe of the patches defined as the smallest number of dimensions needed to explain 95% of the total variance. In other words, deon the smallest index such that
Ddear X 2 0.95 Sexz A₁ Fig. 4 (top) shows the spectrum for several values of P. normalized by X1 on CIFAR-10 10 and ImageNet-32. The first observation is that patches from ImageNet-32 dataset tend to be better conditioned than those from CIFAR-10 with a conditioning ratio 10 for ImageNet 1 for CIF This is probably due to the use of more diverse images than on CIFAR-1O. Second, note that the spectrum tends to decay at an exponential rate (linear rate in semi- logarithmic scale). This rate decreases the size of the patch increases (from dark brown to light brown) suggesting an increased covariance dimension for larger patches. This is further confirmed in Fig. bottom--left) which shows the covariance dimension d function of the
8

---

Published as a conference paper at ICLR 2021
Figure 4: (Top) Spectrum of 1/2 on CIFAR-10 (top-left) and ImageNet-64 (top-right) using small patch sizes in dark-brown to larger patch sizes in light-brown. Covariance dimension (bottom-left) and nearest neighbor dimension (bottom right) as a function of the extrinsic dimension of the patches.
10
Cifar10 raw patches
100
Imagenet raw patches
20.0
17.5
10
10-1
15.0
10-2
10-2
10.0
7.5
10
10-3
5.0
2.5
500
1000
1000
Covariance dimension
Nearest neighbor dimension
800
whitened ImageNet32
100
ImageNet32
600
whitened Cifar10
80
Cifar10
60
400
dcov
d
40
200
20
0
500
1000
500
1000
dext
dext
extrinsic dimension dext, with and without whitening. Before whitening, this linear dimension is much smaller than the ambient dimension: whitening the patches increases the linear dimensionality of the patches, which still increases at linear growth function of p2
Intrinsic dimension of D We propose to refine our measure of linear dimensionality to a non- linear measure of the intrinsic dimension. Under the assumption of low-dimensional manifold, if the manifold is non-linear, the linear dimensionality is only an upper bound of the true dimensionality of image patches. To get more accurate non-lineat estimates, we propose dimension diue introduced in (Levina and Bickel (2004). It relies on local estimate of the dimension around patch point y. obtained by finding the k-Nearest Neighbors this patch the whole dataset and estimating how much the Euclidean distance The (p) between the k-Nearest Neighbor and patch varies as & increases up to K E N:
the notion of intrinsic
2x-12
TK (p) Tk (p)
dimt (p)
Σ log
(5)
K-1
In high dimensional spaces, it is possible to have many neighbors that equi-distant p. thus Tı (p) would barely vary as increases. As a result the estimate dine(P) will have large values. Similarly, a small dimension means large variations of (p) since it possible to pack as many equidistant neighbors of p. This results in a smaller value for dint (p). An overall estimate of the dmmt is then obtained by averaging the local estimate dime (p) over all patches, i.e. dist DD] EpED d (p). Fig.
4 (bottom-right) shows the intrinsic dimension estimated using K = 4 103 and dictionary of size = 10 all cases, the estimated intrinsic dimension d much smaller than the extrinsic dimension d.xt 3P2.. Moreover, it grows even more slowly than the linear dimension when the patch size increases. Finally, even after whitening, d only about 10% of the total dimension, which is strong evidence that the natural image patches are low dimensional.
5 CONCLUSION
In this work, we shed light on data-driven kernels: we emphasize that they are necessary steps of any methods which perform well challenging datasets. We study this phenomenon through

---

Published as a conference paper at ICLR 2021
ablation experiments: used shallow, predefined visual representations, which is not optimized by gradient descent. Surprisingly, this method is highly competitive with others, despite using only whitened patches. Due to limited computational resourees, restricted ourselves ImageNet to small image resolutions and relatively small number of patches. Conducting proper large scale experiments is thus one of the research directions.
ACKNOWLEDGEMENTS
EO supported by GPU donation from NVIDIA. This work was granted access to the HPC resources of IDRIS under the allocation 2021-AD01 1011216R 216RR made by GENCI. This work was partly supported by AN--19-CHIA "SCAI". EB acknowledges funding from IVADO fundamentals grant. The authors would like to thank Alberto Bietti, Bogdan Cirstea, Lénaic Chizat, Arnak Dalayan, Corentin Dancette, Stéphane Mallat, Arthur Mensch, Thomas Pumir, John Zarka for helpful comments and suggestions, Julien Mairal provided additional numerical results that were helpful to this project.
REFERENCES
R. Arandjelovic, A. Zisserman, and.. Look, listen and learn. In Proceedings of the IEEE International Conference on Computer Vision, pages 609-617, 2017.
J. Ba and R. Caruana. Do deep really need to be deep? In Advances in neural information processing systems, pages 2654-2662, 2014.
E. Belilovsky, M. Eickenberg, and E. Oyallon. Greedy layerwise learning can scale to imagenet. arXiv preprint arXiv: 1444, 2018.
K. Beyer, Goldstein, R. Ramakrishnan, and U. Shaft. When is "nearest neighbor" meaningful? In International conference on database theory, pages 217-235. Springer, 1999.
W. Brendel, M. Bethge, and Approximating cnns with sog-o--local-features models works surprisingly well on imagenet. arXiv preprint aiv: 1904.00760, 2019.
M. P. Chandra et al. On the generalised distance in statistics. In Proceedings of the National Institute of Sciences of India, volume 2, pages 49-55, 1936.
L. Chizat, E. Oyallon, and F. Bach. On lazy training in differentiable programming. In Advances in Neural Information Processing Systems, pages 2937-2947, 2019.
P. Chrabaszez, I. Loshchilov, and F. Hutter. A downsampled variant of imagenet altemnatve to the CIFAR datasets. CoRR, abs/1 00000088819. 2017. URL http://tt////x...g////////////// 08819
A. Coates and A. Y. Ng. The importance of encoding versus training with sparse coding and vector quantization. 2011.
A. Coates, A. Ng, and H. Lee. An analysis of single-layer networks in unsupervised feature learning. In Proceedings of the fourteenth international conference artificial intelligence and statisties, pages 215-223, 2011.
A. Criminisi, P. Pérez, and K. Toyama. Region filling and object removal by exemplar- based image inpainting. IEEE Transactions on image processing, (3(9):1200-12 2004.
A. A. Efros and T. K. Leung. Texture synthesis by con-maraettric sampling. In Proceedings of the seventh IEEE international conference on computer vision, volume 2, pages 1033-1038. IEEE, 1999.
C. Fefferman, S. Mitter, and H. Narayanan. Testing the manifold hypothesis. Journal of the American Mathematical Society, 1944)983-1044, 2016.
K. He, X. Zhang. S. Ren. and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 770-778, 2016.
10

---

Published as a conference paper at ICLR 2021
S. loffe and C. Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. arXiv preprint 1rXiv:1502203116,,22 2015.
A. Jacot, F, Gabriel, and C. Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances neural information processing systems, pages -581, 2018
R. Jin, Y. Breitbart, and C. Muoh. Data discretization unification. Knowledge and Information Systems, 19(1):1, 2009.
A. Krizhevsky. I. Sutskever, and G. E. Hinton. Imagenet classification with deep convolutional neural networks, Advances neural information processing systems, pages 1097-1105, 2012.
E. Levina and P. J. Bickel. Maximum likelihood estimation of intrinsic dimension. In Advances in neural information processing systems 17, pages 777-784. MIT Press, 2004.
Z. Li, R. Wang, D. Yu, S. S. Du, W. Hu, R. Salakhutdinov, and S. Arora. Enhanced convolutional neural tangent kernels. arXiv preprint arXiv:1911.000 100.0.001..000010 2019.
D. G. Lowe. Distinctive image features from scale-invariant keypoints. International journal of computer vision, 60(2):91-110, 2004.
Z. Lu, A. May, K. Liu, A. B. Garakani, D. Guo, A. Bellet, L. Fan, M. Collins, B. Kingsbury, M. Picheny, al. How scale up kernel methods be good as deep neural nets. arXiv preprint arXiv: 11t:1441.4000 4000, 2014.
Mairal. End-to-end kernel learning with supervised convolutional kernel networks. In Advances in neural information processing systems, pages 1399-1407, 2016.
J. Mairal, P. Koniusz, Z. Harchaoui, and C. Schmid. Convolutional kernel networks. In Advances in neural information processing systems, pages 2627-2635, 2014.
S. Mallat. A wavelet tour of signal processing. Elsevier, 1999.
S. Mallat, Group invariant scattering. Communications on Pure and Applied Mathematics, 65(10): 1331-1398, 2012.
G. achacn Mahalanobis distance. Resonance, 4(6):20-26, 1999.
N. Montobbio, A. Sarti, and G. Citti. A metric model for the functional architecture of the visual cortex. 2019. httl:tttp://arri..or//aaaaa
02479
E. Oyallon and S. Mallat. Deep roto-translation scattering for object classification. In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2015.
E. Oyallon, E. Belilovsky, and S. Zagoruyko. Scaling the scattering transform: Deep hybrid networks. In Proceedings of the IEBE international conference on computer vision, pages 5618-5627, 2017.
E. Oyallon, E. Belilovsky, S. Zagoruyko, and M. Valko. Compressing the input for cnns with the first-order scattering transform. In The European Conference on Computer Vision (ECCV), September 2018a.
E. Oyallon, S. Zagoruyko, G. Huang, N. Komodakis, S. Lacoste-Julien, M. Blaschko, and E. Belilovsky. Scattering networks for hybrid representation learning. IEEE transactions on pattern analysis and machine intelligence, (1(9):2208-22211 2018b.
Perronnin, J. Sánchez, and T. Mensink. Improving the fisher kernel for large-scale image classifica- tion. In European conference on computer vision, pages 143-156. Springer, 2010.
A. Rahimi and B. Recht. Random features for large-scale kernel machines. Advances in neural information processing systems, pages 1177-1184, 2008.
B. Recht, R. Roelofs, L. Schmidt, and V. Shankar. Do imagenet classifiers generalize to imagenet? arXiv preprint ar Xiv: 1902. 10811, 2019.
11

---

Published as a conference paper at ICLR 2021
A. Rudi, L. Carratino, and L. Rosasco. Falkon: An optimal large scale kernel method. In Advances in Neural Information Processing Systems, pages 3888-3898, 2017.
M. Samarin, V. Roth, and D. Belius. On the empirical neural tangent kernel of standard finite-width convolutional neural network architectures. arXiv preprint arXiv:2006. 1.:.:2006.13645, 2020.
V. Shankar, Fang. W. Guo, Fridovich-Ken kernels without tangents. arXiv preprint mrXiv:2003.02237 2020.
Schmidt, J. Kagan-Kelley, and B. Recht. Neural
G. K. Wallace. The jpeg still picture compression standard. clectronics, 38()):xviixxxxix 1992.
IEEE transactions on consumer
Zarka, L. Thiry, T. Angles, and S. Mallat. Deep network classification by scattering and homotopy dictionary learning. arXiv preprint arXiv: 19ti::1900.0555 2019.
12

---

Published as a conference paper at ICLR 2021
A MAHANALOBIS DISTANCE AND WHITENING
The Mahalanobis distance Chandra et al. 1936 McLachlan 1999) between two samples x and x' drawn from random vector X with covariance Σ is defined
(M)(xx)) V (====")'>~<<==
the random vector X has identity covariance, is simply the usual euclidian distance Du (2, 2') = || - x'|
Using the diagonalization of the coraviance matrix, PAP" the affine whitening operators of the random vector X are the operators
w X + OA 0A-1/2p" (X - 1), OA E (x.
(6)
For example, the PCA whitening operator is
WPCA X - A 1/1 (X
and the ZCA whitening operator is
WZCA X + PA PA-1/1p1 (X 1t)
For all whitening operator w we have
|[((x) - (w(x)=w(x')) DM
since
[[((x) - w(x')l = 10A - 1/2 1/2pT pT((=== X')ll
=V =
-
= -M((zx)).
B IMPLEMENTATION OF THE PATCHES K-NEAREST-NEIGHBORS ENCODING
In this section, we explicitly write the whitened patches with the whitening operator W. Recall that we consider the following of euclidean pairwise distances:
Ci pi, pi.z Wdl d D}.
For each image patch we encode the K nearest neighbors of Wpt... in the set Wd, d E D, for some K 1 ... D.. We the square distance instead of the distance since it doesn' 't change the K nearest neighbors. We have
[W w I 2(p WTW)) + |Wd]
The term || 2 doesn't It affect the K nearest neighbors, so the K nearest neighbors are the K smallest values of
Wal2
(p... d d
2
This can be implemented in a convolution of the image using WFW d as filters and [Wd]2/2 as bias term, followed by a "vectorwise" non-linearity that binary encodes the K smallest values in the channel dimension. Once this computed, we can then easily compute
Wall? + (Piz) T W d), dED)
which is the quantity needed to compute the K nearest neighbors in the set of negative patches D. This is a computationally efficient way of doubling the number of patches while making the representation invariant negative transform.
13

---

Published as a conference paper at ICLR 2021
C ABLATION STUDY ON CIFAR-10
For this ablation study on CIFAR-10, 10, the reference experiment uses |D] = 2048 patches, a patch size = 6 number of neighbors K 0.4 2048 820 and whitening regularizer À le and yields 82.5% accuracy. Figure 5 shows the results in high resolution. We further performed an experiment, where we replaced the patches of CIFAR-10 by the patches of ImageNet: this leads to drop of 0.4% accuracy compared to the reference model. Note that the same model without data augmentation performs about 2% worse than the reference model.
100
100
accuracy (%)
90
90
80
75
70
65
2
2
22
10a
102
10a
patches [D]
number of neighbors K
100
100
95
accuracy (%)
X
85
80
70
70
10
10 whitening regularization
10-2
10
100
patch size Q
Figure 5: CIFAR-10 ablation experiments, train accuracies in blue, test accuracies in red. Number of patches (D] varies in (512, 1024, 2048, 4096). number of neighbors varies in {10, 50, 100, 500, 800, 1000, 1500), patch size Q varies in {4, 6, 7, 8J, whitening regularization varies in {0, 10-3 10- 10-3, 10-3 3,10-2, 1002.1000 1,1
D INTRINSIC DIMENSION ESTIMATE
The following estimate of the intrinsic dimension die is introduced in Levina and Bickel (2004) as follows
K
TK (p)
d (p)
log
(p)
where TA (p) is the euclidean distance hetween the patch and it's k-thh nearest neighbor int the training set.
14


Reviews:
[{"review_id": "dhElVqc8Jnq", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper proposes a powerful non-learning Kernal based baseline for ImageNet classification. The proposed non-learning Kernal based baseline (which can be interpretable to a vector quantization) shows comparable results (88.5) with AlexNet (89.1) in CIFAR-10 top-1 accuracy. The ImageNet result (39.4) shows that it is still challenging to classify the images without deep features, but about 40% is an impressive baseline without any learning method (e.g., these results is almost comparable to BagNet top-5 error).\n\n**Pros**\n\nThis paper shows that only using a shallow kernel can often be comparable to deep models, e.g., AlexNet.\n\n**Cons and questions**\n\n**[Motivation to the shallow method]**\nI wonder about the motivation of the proposed kernel-based non-learning method. Why we need a shallow kernel method while a deep data-driven method shows a significantly better result?\n\n**[Runtime comparison]**\nI would believe that if the authors can provide the number of learnable parameters, the number of flops, and the real latency time compared to the deep models can bring a huge practicalness to the real-world applications.\n\n**[More analysis would be expected]**\nApart from the accuracies, I would expect more analysis on the patch-side. For example, BagNet paper [1] shows that ImageNet classifiers are actually heavily relying on the local cues, e.g., fingers for Tench classes.\n- [1] W. Brendel, M. Bethge, and . . Approximating cnns with bag-of-local-features models works surprisingly well on imagenet. ICLR 2019\n\nIt will be interesting to many readers if the authors can provide additional analysis on the \"important\" patches for the image classification tasks. Explainability analysis, as Brendel et al. could be useful for many researchers.\n\n**[Additional questions]**\nIt may not be related to the original task, but I wonder a few things about the proposed method.\n\n- Is the proposed method robust to the adversarial perturbation? I notice that it could be difficult to attack the proposed method (because there is no gradient). It is okay to test with a black-box attack, e.g., generate an attacked image with well-known architectures, e.g., ResNet, and test the attacked accuracy.\n- Similarly, I wonder the proposed method is beneficial to the out-of-distributed (OOD) robustness, and other distribution shifts\n  - Hendrycks, Dan, and Kevin Gimpel. \"A baseline for detecting misclassified and out-of-distribution examples in neural networks.\" ICLR 2017.\n  - Hendrycks, Dan, and Thomas Dietterich. \"Benchmarking neural network robustness to common corruptions and perturbations.\", ICLR 2019.\n  - Hendrycks, Dan, et al. \"Natural adversarial examples.\" arXiv preprint arXiv:1907.07174 (2019).\n\n\nPlease consider to add \"explainability analysis\", \"adversarial robustness\", \"distribution shift robustness\" and \"OOD robustness\" to show the effectiveness of the paper.\n\n---\n\nPost-rebuttal review\n\nIn my initial review, my main concern was the motivation for the patch-based classification is unclear, and I asked some questions related to the further potential usage of the proposed method, particularly focusing on robustness.\n\nDuring the rebuttal process, the authors address most of my concerns well in their responses.\n\n- Main motivation: this work more focuses on the mathematical analysis of the image classification tasks, rather than performances (accuracy, runtime, ...). It makes sense to me, and I think this motivation needs to be encouraged to explore by many researchers.\n- Runtime or learnable parameters: tracking the runtime comparing to deep methods is non-trivial as the author clarified. However, the authors showed that the number of learnable parameters is much less than deep models (580k for the proposed method, a few M for AlexNet). I think this comparison fairly shows that the proposed method is efficient than deep models in terms of the number of parameters.\n- Other analysis that can support the motivation of this paper: I'd expect to see more robustness analyses such as the black box adversarial attack results, but I agree that this is out-of-scope of this work. To me, the responses to the additional comments are not helpful, but I understand that my questions can be out-of-scope of this work.\n\nHence, I'd like to change my score from 5 to 6.", "extra_scores": {}, "extra_text": {}}, {"review_id": "cJpDuuI2QT", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Briefing:\n\nThis paper mainly investigates the patch-based pre-processing for image classification. The patch-based pre-processing is done by a simple convolutional kernel constructed in a data-driven manner. \nThe paper achieved better or comparable performance to other more heavy comparisons using a much smaller kernel size.\n\nStrongpoints:\n\nThe paper shows that the simple whitening procedure (by mean and covariance from training-set) of first layer weights enhances the performance, rather than using a deep kernel, which can be much efficient.\n\n\nWeak points:\n\nAnalysis of the improvement: The reviewer tried to find an explainable reason for the performance improvement, although the title includes 'unreasonable'. Figure 3 seems to analyze the dictionary by covariance spectrum and intrinsic dimension, but it wasn't easy to catch the main idea. A more precise explanation of the experiments and the analysis is required.\n\nComments:\n\n(1) Table 1.a shows that the proposed method achieved good performance despite the hard-assignment. What if we apply soft-thresholding to the proposed method?\n\n(2) Experiments or discussion for the ImageNet performance with a lower number of the dictionary would be meaningful.\n\n(3) Ablation study (data-driven or not) in ImageNet performance would strengthen the contribution of the paper (in Table 2.a?)\n\n(4) It might be out of scope, but the reviewer could not fully catch the dictionary encoding usage just for the classification task. Is this possible to apply it to other task s.a. retrieval or other feature matching task? Then, discussion or experiments of the tasks would be required.\nOr, if not, the importance of the dictionary construction on the classification task would be required.\n\n(5) The proposed method only uses one or two layers of depth, one of the main contributions. Then, what if we use slightly more layers s.a. 3, 4, or 5? This addition of layers does not require much burden, and it would be better to add the layers if it can enhance performance.\n\n(6) It wasn't easy to catch how the paper constructs the kernel Phi, from the method. A clearer explanation of the procedure would be appreciated.\n\n(7) Qualitative analysis of each element of the dictionary would help readers catch the paper's contribution.\n\nNote: The reviewer does seem to catch the main strong-points and suggestions of the paper thoroughly. The reviewer requires a clearer explanation of the contribution with the replies for the above comment, and it would be required for the precise rating.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "4X5LfHyzCEz", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Summary\n\nThe authors propose using a data-driven dictionary of patches on CIFAR-10 and Imagenet, with a shallow classifier (linear / one hidden layer CNN) obtaining results comparable to end to end deeper architectures.\nThe proposed method consists in random sampling a dictionary of patches (2 * 10^3 for ImageNet) and using it to encode a binary representation (feature map), with Q nearest patches in the dictionary.\n\n#####################\n\nRating motivation\n\nThe idea of using small patches for ImageNet and CIFAR classification is interesting - the effectiveness of small (3x3, 5x5) patches having been shown for textures in earlier work of Varma & Zisserman (A Statistical Approach to Material Classification Using Image Patch Exemplars, TPAMI 2009). \nAnother strong point of the paper is that it achieves an impressive accuracy (88.5) on CIFAR-10, almost on par with end-to-end AlexNet and other patch based methods, using only a small fraction of the patches obtained from ImageNet.\nThe clarity and readability of the paper could be improved, especially to the benefit of readers less familiar with the topic.\n\n######################\n\nStrong aspects of the paper:\n\n- patch-based representation; data-driven kernels (although, it seems just random sampling)\n- shallow model, with good performance;\n- operates at lower resolution (64) on ImageNet, and obtains comparable performance to existing methods (trained end-to-end, and deeper).\n\n#######################\n\nWeaker points / questions:\n- please add one introduction paragraph in Section 3, describing the method. Just introducing the notation is a bit abrupt, and makes the section difficult to read. Please try to clarify from the beginning what the one layer CNN is trained on (seems d * j binary image).\n\n-please emphasize more the differences with Coates&Ng 2011, and compare on similar parameters (Tab 1a -- does the proposed method perform better because of using 10x , resp. 600x more patches in the dictionary, hence higher feature dimension?)\n\n- evaluation only on CIFAR-10 and ImageNet -- could improve this by comparing with the scatter transform of Sifre & Mallat, on a common benchmark, e.g. texture / material dataset). It might be interesting, in addition to CIFAR-10 to test the method on Materials in Context (MINC) dataset, or Describable Textures Dataset (~6.5K images).\n\n- How is the dictionary augmented? There is a mention of contrast invariance, and union over {d, -d} -- is the dictionary size |D| after augmentation? \n- Please explain / clarify equation 3 - why is it necessary and what is a benefit of viewing the distance between two images as a Hamming distance? Are there computational advantages?\n- Please clarify the notation in eqn. (4) - why is the step in Eq 4 necessary, and why not using a max-pooling layer in the one layer CNN? \n\n- Please expand the explanation of the difference between data-driven (D-D) vs Non-Data-Driven (Tab 1.c); Are the patches the same for all the methods? It would also help to have the total numbers for the data-driven column (and improvement number in brackets, e.g. 78.8 ( +13.2 ).\n- How would the method perform with larger patch sizes? (e.g. P=9, to have a closer comparison with BagNet).\n- In Sec. 4, please add a brief explanation of spectrum definition and intrinsic dimension.\n\n######################\n\nMinor (typos, editing …)\n- in Sec. 3(Method), first paragraph, \"squared domain of surface Q^2\" --> should be P^2; and patch size should be P;\n- Please use 500K, 1.2M instead of 5*10^5, 1.2 * 10^6 for the number of images in CIFAR-10 and ImageNet respectively.\n- Incomplete list of authors for Convolutional Kernel Methods.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "0W_3RvXjrua", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "My understanding is that this paper extends the approach from https://www-cs.stanford.edu/~acoates/papers/coatesng_nntot2012.pdf to use *patches* from an image as filters \n\nI enjoyed this paper quite a bit and the numbers are quite impressive (88.5 for a 2 layer network on Cifar-10 is great), and its good to understand these methods fall short on ImageNet, this may make sense for a 2 layer as the spatial pooling destroys a lot of structure. It is interesting to see these methods outperform a scattering transform. I enjoyed the rigorous ablations and study of the spectrum of patches. These are very good baseline experiments that make a valuable data point for the community. I also think that doing an ImageNet experiment at the full 224 resolution may be worth it, if that reaches 60% top-1 or above it would be a very big contribution.\n\nFew Questions/Clarifications:\n\n1. You seem to say that the kernel from Shankar et al is an \"End to End\" classifier, but from my understanding from reading that paper and looking at the corresponding code is that they just train a linear classifier on the kernel matrix which is a deterministic function, it has several layers (within in the kernel function), but the only thing thats learned is the weights that multiply the kernel matrix (the last layer), so I think in your characterization is somewhat incorrect, but please do correct me if I am wrong in my understanding of Shankar et al.\n\n\n2. How many patches were used to achieve 88.5? It seems this number is missing in Table 2b.\n\n3. Do you know what accuracy you get when you only do Flip augmentation as opposed to crops + flips, the shankar et al number you compare to only does Flips as I see. CKN seems to do no augmentation.\n\n4. In the related work, what do you mean by \"well-designed linear classifier\"?\n\n5. How does SimplePatch perform without nearest neighbors or visual quantization?\n\n\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the patch-based convolutional kernels for image classification, and finds that making the kernel dependent on data is necessary for designing competitive kernels for image classification. The proposed simple method shows comparable results to those end-to-end deeper architectures on CIFAR-10 and ImageNet datasets. 

All reviewers feel that the paper is interesting, important, and the performance is impressive. During the rebuttal, the authors have addressed most of the questions and concerns raised by the reviewers. In particular, authors have clarified the motivation, discussed the model size of the proposed method (requested by R1), added precise details about the spectrum definition and intrinsic dimension (requested by R4), and taken the suggestions from all reviewers to improve their paper. 

After rebuttal, all reviewers agree on accepting the paper. After checking the discussions between the authors and reviewers, I am convinced that the original concerns of the reviewers are addressed. Hence, I recommend that this paper be accepted.

Decision: Accept (Poster)