\section{Introduction}

One of the most significant obstacles to the deployment of Convolutional Neural Networks (CNNs) in safety critical applications is the lack of a prior error models that explain their success. Many theoretical papers have been written about how deep neural networks (DNNs) can overcome the curse of dimensionality (CoD) in different contexts, but there is no experimental evidence, as far as we know, to confirm their applicability in practice. We propose for the first time a simple theoretical model that seems to predict correctly the performance of CNNs on well-known image classification data sets.

The model predicts that the CoD is overcome by the simple mechanism of learning the noisy labels of all the small tiles in the image and averaging the tile-wise predictions. This simple model is easy to analyze and yields testable bounds. As a consequence we claim that the main reasons for being cautious in deploying CNNs can now be overcome.

So our main claim is that CNNs learn to classify images \textit{only} using small tiles. In fact we observe experimentally that CNNs do \textsl{not} require full images to be used during training, but only randomly cropped tiles as inputs, to match (or even surpass) the performance of models trained using full images. Conversely, CNNs trained on full images have similar predictions on small tiles. The proposed simple theoretical model can explain this behavior surprisingly well. For example, on the CIFAR-10 data set, without any data augmentations or pre-trained weights, a ResNet18 model trained only on 16x16 tiles reaches \tildew91\% accuracy on the test set compared to \tildew89\% using the full 32x32 images. We also use this observation to generate \textit{heat maps} for any image to \textit{explain} a given CNN model's (mis)classification of the image. We also discuss how this observation sheds light on the amazing generalizing performance of CNNs while providing a natural regularizing strategy for training CNNs and saving computational costs.

\section{Related work}

Even though there is much published literature explaining the expressive power of deep neural networks in general, to the best of our knowledge, we could not find any prior work that attempts to explain the amazing generalization capabilities of \textsl{convolutional} neural networks in particular, even though the latter are much more successful in practice.

\citet{PoggioMRML16} seems to be the closest to this paper theoretically. They show that deep CNNs can avoid the curse of dimensionality for hierarchically compositional spatially local functions. CNNs definitely fall into this category, but the convolutional nature of the data was not fully exploited in their analysis. In particular knowledge of the right compositional model is needed for their results to be applicable.

Very early work on unsupervised learning by \citet{coates11a} shows that "convolutionally extracted" features achieve good performance on unsupervised tasks because of the similarity between the extracted tiles/features making them easier to cluster using k-means. This correlates well with our theory that the predicted labels from convolutionally extracted features on small tiles gives the CNNs their advantage. However no theoretical models were proposed and this work was before CNNs were introduced.

\citet{sokolic17a} discuss the generalization error of invariant classifiers like CNNs under explicit input transformations and obtain an error bound, but they do not extend the discussion to tiles and how the invariance when applied to the tiles of input images affects the generalization performance of CNNs.



A very closely related paper is \citet{bagnets} which proposes the BagNet architecture. In BagNet a modified ResNet backbone is applied to each $q\times q$ tile of the image and the output is a class heat map. The average of these heat maps is then fed into a linear classifier. The heat maps highlight the tiles which contribute to the network's decision in a straight-forward way because of the \textit{linear} classifier, improving explaininability but at the cost of some accuracy due of the modified architecture. The first main difference with our work is that, during training they consider the output of the linear classifier i.e. the weighted aggregate of the individual decisions on $q \times q$ tiles to be the network's prediction for the image and thus it is not directly evident what the network is considering as the labels for the individual tiles. On the other hand, we train the standard CNNs to classify each tile as belonging to its parent class making it very clear that our heat maps are the network's predictions on individual tiles. We also show using the evidence of heat maps that the CNNs trained using standard training procedures also learn the labels on tiles implicitly, thus providing explainable decisions to traditional CNN architectures without any loss of accuracy. Finally, we provide a theoretical model which explains why such a seemingly handicapped strategy can be a critical element for the success of CNNs. The theory also provides a numerical estimate for the generalization performance which correlates well with the observed test accuracies on popular data sets.


\begin{figure}
    \centering
    \includegraphics[width=\linewidth]{figures/heatmap_tiles.png}
    \caption{(Top) With each tile as an input to a \texttt{Resnet9}, all the tiles classified as \texttt{truck} are shown as a heat map with the model’s output for that class represented as the color of the heat map. (a) Sample image of \texttt{truck} is from CIFAR-10 test set. Some 8x8 tiles are shown in (b) and 12x12 tiles in (e). \texttt{Resnet9} is trained separately with 8x8 and 12x12 tiles of CIFAR-10 respectively. (Bottom) Example heat maps generated using 64x64 tiles by a \texttt{mobilenet\_v2} \textbf{pre-trained} on Imagenet-1k 224x224 full images and \textbf{without} any additional training with tiles.}
    \label{fig:heatmap_tiles}
\end{figure}

\section{Experiments}

\subsection{Experimental setup} \label{sec:exp_setup}
To only focus on the ability of CNNs in learning the labels of tiles, we fix the training hyper-parameters to be same across all training runs and use the following setup. In all our results, the accuracies are on average within \tildew1-2\% of the reported numbers. We also do not try to match/obtain state-of-the-art accuracy on any data set or model as it is not our intended goal, and hence do not use any data augmentations or strategies like CutMix~\citep{cutmix} or Mixup~\citep{mixup}.

\paragraph{CNN Models.} ResNet9, ResNet18 and ResNet34 without any pre-trained weights. We choose the ResNet \citep{resnet} family because of its ubiquity in practice and smaller number of parameters. To show that our results are robust, we provide similar experimental results on training with tiles using other CNN architectures in Appendix~\ref{ablation_study}.

\paragraph{Data sets.} We use CIFAR-10 \citep{cifar10}, CIFAR-100 \citep{cifar10}, STL-10 \citep{stl10}, Tiny-Imagenet-200 \citep{tinyimagenet} and Imagenet-1k \citep{imagenet} data sets, covering a wide range of variability in number of training samples, number of classes and image resolutions. CIFAR-10 has 10 classes with 5,000 32x32 resolution images per class, whereas CIFAR-100 has the same number of total images but among 100 classes, constraining the training set to only 500 32x32 images per class. STL-10 has 10 classes with 500 training and 800 test images per class which are labelled but these images are of higher resolution (96x96) than CIFAR. Tiny-Imagenet-200 has 200 classes with 100,000 labelled training images of 64x64 resolution. Imagenet-1k has 1.2 million images with varying resolutions from 1,000 classes.

\paragraph{Computational resources} We used a dual 40-core Xeon CPU with 192G RAM and an NVIDIA TITAN RTX 24G GPU and a 24-core Xeon CPU with 64G RAM and an NVIDIA 1080Ti 11G GPU in all our experiments.

\paragraph{Training hyper-parameters.} We train all the models, except those on Imagenet-1k, for 400 epochs using the standard cross-entropy loss and Adam optimizer with a weight decay of 1e-4, a starting learning rate of 0.002, and a multi-step learning rate decay with gamma of 0.5 at milestones at 40, 80, 100, 150, 200, 250 and 300, epochs. We use batch sizes of 128 for CIFAR10 and STL10, and 512 for CIFAR100 and Tiny-Imagenet-200. For Imagenet-1k, due to resource constraints, we follow the training routine suggested by FFCV \citep{ffcv} for faster training. There we use ResNet18 for 100 epochs with a batch size of 1024, cross-entropy loss,  SGD optimizer with momentum of 0.9, weight decay of 5e-5, cyclic learning rate with starting value 0.5. Test time resolution is fixed at 256 for inference on Imagenet-1k.

\paragraph{Image pre-processing.} We only use random horizontal flips for augmentation and zero mean and zero standard deviation normalization as part of the image pre-processing pipeline and no other transformation or augmentation is used.

\paragraph{Generation of tiles.} We produce tiles by random cropping of original image \textsl{without} any padding \textsl{at train time} (for example, by using \texttt{RandomCrop} transform of \texttt{PyTorch} \citep{pytorch} in the \texttt{DataLoader} with desired tile size and \texttt{padding} = 0 as the arguments). Here we take the opportunity to note that our setting of training a CNN model with just the tiles is \textsl{completely} different from common practice of deep learning practitioners using random cropping in their pre-processing pipeline. In the common practice, random cropping is explicitly used as a regularization trick while taking care in selecting padding size and crop size such that the cropped image would still be recognized by a human as belonging to its label class. But in our experiments, we deliberately train with a full range of crop sizes without padding and in the case of very small sizes, the tiles could not be attributed to any class by a human, for example, as shown in Figure~\ref{fig:heatmap_tiles}. We also clarify here that in regards to the labels of tiles, we use the same label as the parent image from which a tile is drawn, even for small tiles that could not be attributed to be of the parent image's class label. In other words, no label transformation is applied when training with tiles.

\subsection{Training with only tiles} \label{sec:training_with_tiles}
Table \ref{tab:tile_accuracies} shows the training and test set accuracies of ResNet models when trained on tiles of different sizes and tested on test set images of full resolution of the corresponding datasets. We can see that a model trained with just 16x16 tiles on CIFAR-10 has a \tildew91\% test accuracy whereas the model trained on full 32x32 images has \tildew90\%. Highest test accuracy is observed for model trained with 24x24 tiles. Remarkably, model trained with only 8x8 tiles shows \tildew75\% test accuracy. 

Figure \ref{fig:heatmap_tiles} gives a perspective on how 8x8 tiles may appear to humans taken from a sample CIFAR-10 testset image, so it is extremely surprising that a model trained only on such tiny tiles with very noisy labels, is exhibiting such a high accuracy. Here we remind the reader again that the labels provided for each of these randomly selected tiles is just the label of its parent image, irrespective of whether the tile covers the class subject in it or not. So it is highly likely that during training a lot of inputs are just tiles of the background but paired with labels of the parent image. And the CNNs seem like they do not have any trouble distinguishing between such noisy label tiles and tiles with correct labels (i.e. tiles which cover the class subject), which is evident from (i) the absence of over fitting observed when training with tiles and (ii) observing the heat maps of training set images after the CNNs are trained. We discuss the absence of over fitting aspect in Section \ref{sec:regularization} and the heat maps in Section \ref{sec:heatmaps}.

Similar results are observed for CNNs trained on STL-10 and Tiny-Imagenet-200, each of which has different image resolutions, classes and number of training images. For example, on STL-10, the model trained on 32x32 tiles outperforms the one trained on 96x96 tiles by \tildew7\%. However for CIFAR-100 the highest test accuracy is observed on full sized images, even though the \tildew61\% accuracy of the model trained on 16x16 tiles is comparable to the \tildew68\% for the one trained on full images, especially considering that CIFAR-100 has 100 classes of just 32x32 resolution images with only 500 samples per class available for training. And similarly on Imagenet-1k, ResNet18 trained on 168x168 tiles match the performance of models trained on 256x256 and 224x224 images and remarkably, a ResNet18 trained on 112x112 tiles, which is half the usual input size that Imagenet-1k models are generally trained at, almost matches the performance of models trained on larger images. Given this seemingly wide range of behaviour we show in Section ~\ref{sec:error_bound_disc} that a simple theoretical model can predict all of this behaviour of CNNs over what we call \textsl{convolutional data sets}.


\begin{table}[bt]
    \centering
    \resizebox{\columnwidth}{!}{
    \begin{tabular}{llll|llll|llll|llll|lll}
   
      \multicolumn{4}{c}{CIFAR-10} &
      \multicolumn{4}{c}{CIFAR-100} &
      \multicolumn{4}{c}{Tiny-Imagenet-200} &
      \multicolumn{4}{c}{STL-10} &
      \multicolumn{3}{c}{Imagenet-1k}
      \\ 
    
      \multicolumn{4}{c}{$N$=50k, $K$=10, $H$x$W$=32x32} &
      \multicolumn{4}{c}{$N$=50k, $K$=100, $H$x$W$=32x32} &
      \multicolumn{4}{c}{$N$=100k, $K$=200, $H$x$W$=64x64} &
      \multicolumn{4}{c}{$N$=5k, $K$=10, $H$x$W$=96x96} &
      \multicolumn{3}{c}{$N$=1.2M, $K$=1k}
      \\ 
      
      \midrule
      Tile & Train & Final & Test & Tile & Train & Final & Test  & Tile & Train & Final & Test & Tile & Train & Final & Test & Tile & Test & Test \\
      Size &   & Train &  & Size &  & Train &  & Size & & Train & & Size &  & Train &  & Size & Top-1 & Top-5\\
      \midrule
      32 & \textbf{99} & \textbf{100} & 90 & 32 & \textbf{99} & \textbf{99} & \textbf{68} & 64 & \textbf{99} & \textbf{99} & 51 & 96 & \textbf{99} & \textbf{99} & 71 & 256 & 69 & 89\\
      24 & 99 & 99 & \textbf{92} & 24 & 99 & 99 & 68 & 56 & 95 &   -   & 57 & 64 & 99 & 99 & 79 & 224 & 70 & 89\\
      18 & 94 & 94 & 90 & 18 & 81 & 88 & 49 & 48 & 92 & 99 & \textbf{57} & 56 & 98 & 98 & 80 & 196 & \textbf{71} & \textbf{89} \\
      16 & 88 & 89 & 91 & 16 & 71 & 79 & 61 & 32 & 59 & 68 & 57 & 48 & 94 & 95 & \textbf{80} & 168 & 70 & 89\\
      12 & 70 & 70 & 87 & 12 & 53 & 54 & 55 & 24 & 38 & 39 & 47 & 32 & 74 & 75 & 79 & 112 & 63 & 85\\
      8  & 50 & 50 & 75 & 8  & 23 & 31 & 20 & 16 & 16 & 21 & 21 & 24 & 59 & 59 & 68 & 56 & 32 & 57\\
         &       &       &       &    &       &       &       &    &       &       &       & 16 & 36 & 44 & 53 &  & \\
         &       &       &       &    &       &       &       &    &       &       &       & 8  & 26 & 29 & 24 &  & \\
    \end{tabular}
    }
    \caption{Training and test accuracies with ResNet models for different tile sizes on different image classification data sets. The data sets differ in number of training samples ($N$), classes ($K$) and image resolution ($H$x$W$). ``Final Train'' corresponds to the training set accuracy observed at the end of 400 epochs; Train and Test correspond to (tiled) training set and (regular) test set accuracies observed when the test accuracy is highest. CIFAR-10 and CIFAR-100 are trained using ResNet9, STL-10 and Imagenet-1k using ResNet18 and Tiny-Imagenet-200 using ResNet34.}
    \label{tab:tile_accuracies}
\end{table}

\subsection{Implicit regularization when training with tiles} \label{sec:regularization}

When training with smaller tiles, we observe that the CNNs \textbf{do not} over fit on the input tiles during training and the training accuracy saturates at much less than 100\%, as measured on the training tiles. This can be seen from the ``Final Train'' column of Table~\ref{tab:tile_accuracies} for each data set. Figure~\ref{fig:losses_accs} also shows that the models trained on smaller tiles are better regularized than the model with full images as inputs during training. Moreover, the accuracy of each model on full sized training set images, as reported in Table~\ref{tab:gen_gap}, shows that the models trained on smaller tiles have better generalization gap (difference between training error and test error). In fact, the generalization gap continuously decreases as the tile size is decreased, even showing negative values for models trained on 8x8 tiles of CIFAR-10, and 8x8 and 16x16 tiles of STL-10; i.e., a better performance on the test set than on the train set!

When we look closely at the model's predictions on tiles of training set images using the heat maps (see Section \ref{sec:heatmaps}), we find that during training, CNNs learn which tiles correspond to the distinguishing regions for a given class, while tending to discard tiles that do not have any information regarding its class label. \textsl{This crucial observation, combined with another important observation that the models trained on full images produce identical looking heat maps as the ones trained on tiles, we conjecture that the over fitting that is apparent in models trained on full images is only the over fitting of individual tile decisions into a single decision for an image, which is explicitly controlled when training with tiles, thus making them implicitly regularized}.


\begin{figure}
    \centering
    \includegraphics[width=\linewidth]{figures/losses_accs.png}
    \caption{Training loss and Test accuracy measured during training with tiles of different sizes on CIFAR-10 and STL-10. Models trained on smaller tiles show implicit regularization.}
    \label{fig:losses_accs}
\end{figure}

\begin{table}[bt]
    \begin{minipage}{.49\linewidth}
        \centering
        \resizebox{\columnwidth}{!}{
        \begin{tabular}{llll|llll}
       
          \multicolumn{4}{c}{CIFAR-10} &
          \multicolumn{4}{c}{STL-10}
          \\ 
          \midrule
          Tile & Train & Test & Gen. & Tile & Train & Test & Gen.  \\
          Size &   &  & Gap  & Size &  &  & Gap  \\
          \midrule
          32 & \textbf{100} & 90 & 9  & 96 & \textbf{99} & 71 & 28\\
          24 & 99 & \textbf{92} & 7  & 48 & 99 & \textbf{80} & 18\\
          18 & 98 & 90 & 7  & 32 & 93 & 79 & 14\\
          16 & 97 & 91 & 5  & 24 & 77 & 68 & 9 \\
          12 & 90 & 87 & 3  & 16 & 49 & 53 & -4\\
          8  & 66 & 75 & \textbf{-8} & 8  & 19 & 24 & \textbf{-5}
        \end{tabular}
        }
        \caption{Accuracies on full sized images of training and test sets of CIFAR-10 and STL-10 for models trained on different sizes of tiles. Models trained on smaller tiles have smaller (even negative) generalization gaps.}
        \label{tab:gen_gap}
    \end{minipage}%
    \hfill
    \begin{minipage}{.49\linewidth}
        \centering
        \resizebox{\columnwidth}{!}{
        \begin{tabular}{lll|lll}
       
          \multicolumn{3}{c}{CIFAR-10} &
          \multicolumn{3}{c}{STL-10}
          \\ 
          \midrule
          Tile & ResNet9 & ResNet18 & Tile & ResNet9 & ResNet18  \\
          Size &  &    & Size &  &    \\
          \midrule
          32 & 90 & 89 & 96 & \textbf{80} & 71 \\
          30 & 89 & 92 & 56 & 80 & 80 \\
          24 & \textbf{92} & \textbf{93} & 48 & 78 & \textbf{80} \\
          18 & 90 & 92 & 32 & 71 & 79 \\
          16 & 91 & 91 & 24 & 65 & 68 \\
          12 & 87 & 85 & 16 & 52 & 53 \\
          8  & 75 & 60 & 8  & 38 & 24
        \end{tabular}
        }
        \caption{Test accuracy on CIFAR-10 and STL-10 for ResNet9 and ResNet18 models showing the effect of depth of CNNs when trained on tiles of different sizes.}
        \label{tab:resnets}
    \end{minipage}%
\end{table}





\subsection{Computational advantages of training with tiles}

A single full pass of one 224x224 image through a ResNet18 model uses 1.81 GFlops, whereas a 168x168 image uses 1.11 GFlops, and 112x112 image uses only 0.48 GFlops. On the memory side, a full pass of one batch of 1024 224x224 images through ResNet18 needs 23.5 GB of GPU memory, whereas a batch of 1024 168x168 images requires 14.6 GB, and 112x112 images require only 7.1 GB of GPU memory. So the advantages of training on tiles is also pretty clear from the computational point of view especially if there is no drop in generalization performance. Moreover, using small tile sizes may even enable one to switch to a smaller CNN with reduced depth without significantly dropping the accuracy, as was the case for CIFAR10 and STL10 (see Table~\ref{tab:resnets}).

\section{Generalization error bound for convolutional data sets} \label{sec:error_bound_disc}

We now turn our attention to explaining this observed behavior of CNNs using a simple theoretical model. We argue that CNNs are able to generalize extremely well to unseen \textsl{tiles} owing to the mitigation of the curse of dimensionality (CoD) which often plagues the function approximations in high dimensions. Given our experimental observations that CNNs actually learn the labels of tiles of images, rather than those of whole images, we can now see that this brings down the effect of CoD in two ways -- i) by reducing input dimensions as number of pixels in tiles is much smaller than that of full image, and ii) by increasing the number of samples available during training because for each image of size $(H,H)$, there are $(H-T_{m}+1)^{2}$ tiles that are of size $(T_{m},T_{m})$, which grows quadratically for smaller tile sizes. However, there are some caveats: i) the noise in the labels of tiles increases rapidly as we go to smaller and smaller tile sizes, ending in fully noisy labels at the pixel level, and ii) the label function on tiles becomes rougher on smaller tile sizes. Taking into account all these effects, we propose the following upper bound on the generalization error for models trained on tiles for a classification problem:
\begin{align}
    \| f(z) - F(z) \| & \lesssim 
    \frac{1}{\sqrt{T_{\text{eff}}}} \left(
    \left( \frac{1}{N T_{\text{eff}}} \right) ^{\frac{1}{T_{m}^{2}}}  \left( \frac{H}{T_{m}} \right) ^ {\frac{1}{3 T_{m}^{2}}}
    - \frac{1}{2} \sqrt{K} \, \log \left( \frac{T_{m}} {H} \right)\right), \label{eqn:finge_simple}
\end{align}
for a $(H,H)$ sized test image $z$ whose class label is given by $f(z)$, and $F(z)$ is the predicted label, where $N$ is the number of $(H,H)$ training image samples in the data set with $K$ classes. Here $T_{m}$ is the size of tiles that is used by the model whose labels are assumed to be same as that of the parent image from which the tiles are drawn from. $T_{\text{eff}}$ is the number of essentially distinct (uncorrelated) tiles present in a single image and is taken to be $(\frac{H-T_{m}}{S}+1)^{2}$, where $S$ is a \texttt{stride} like parameter. When $S=1$ all the tiles available in an image are considered to be distinct. This is an important parameter that is specific to each data set. For example, for data sets with very large resolutions like 256x256, correlation between neighboring tiles obtained by a shift of one pixel ($S=1$) is most likely very high and considering such tiles as distinct inputs to the CNN might not be a good idea. In such cases, a larger $S$ value is chosen and for data sets with small resolutions like 32x32 such as CIFAR-10, lower $S$ might be preferred. For the full reasoning behind the above bound and our modeling assumptions, refer to Appendix~\ref{sec:bound_deriv}.

We say a data set is \textsl{convolutional} if the label for the image can be transferred to its tiles at fairly small sizes in a meaningful way. The degree to which this transfer can be achieved will depend on the data set and the associated labels. For example if the labels are counting the number of objects of a particular class in an image (one cow, two cows, three sheep, etc.), then it is unlikely that such data sets are very convolutional.

\begin{figure}
    \centering
    \includegraphics[width=\linewidth]{figures/curves3.png}
    \caption{Predicted generalization error from our theoretical upper bound compared with the observed test set errors for different tile sizes on multiple data sets. Predicted error at each tile size is only considering that single tile size in its error estimate, whereas CNNs trained on tiles of size $T_{m}$ have access to all the tiles $\leq T_{m}$.}
    \label{fig:curves}
\end{figure}

We plot the right hand side of the error bound~\ref{eqn:finge_simple} for each of the image classification data sets as a function of input tile size $T_{m}$ along with our reported test accuracies from Section~\ref{sec:training_with_tiles} in Figure~\ref{fig:curves}. In all these plots it should be noted that the generalization error predicted by the error bound assumes CNN inputs as only tiles of \textsl{single} size, given by the corresponding x-axis value. CNN models in practice, however, have access to tiles of all sizes that are $\leq T_{m}$ when fed with the input tiles of size $T_{m}$. This is because of how the convolutional layers are constructed with 3x3 kernels of deeper layers stacked on top of those of shallow layers with each layer's weights operating on tiles of sizes that correspond to the receptive-field of that layer. Due to this, a model trained with larger tiles, also enjoys the advantages of smaller tile training described earlier and shows a test error that is lower than that is predicted by the error bound. So in effect, we should actually be comparing the observed test errors with minimum of the right hand side of inequality~\ref{eqn:finge_simple} across all tiles sizes smaller than $T_{m}$. However, we believe just plotting the per tile size upper bound is more meaningful as the ``optimal'' tile size is more readily apparent this way. So beware that the (near) monotonicity of the actual error curve versus the cup-shape of the theoretical curve is due to this choice and not a sign of a flaw in the model.

In all the plots, the error increases exponentially at tile sizes near zero, since the labels at that scale are completely random. And when the inputs are of full resolution i.e. towards far right of the plots, the error increases again due to CoD. The true generalization power of CNNs is realized in those intermediate tile sizes as we have also seen from the results of Section~\ref{sec:training_with_tiles}. The data sets used in the plots span a wide range of parameters present in the error bound, thereby revealing the interplay between them for different combinations, while at the same time being familiar to most deep learning practitioners.

The first plot shows the error curves for CIFAR-10 and CIFAR-100 data sets (32x32 images), where we have chosen $S$ to be 1 and 2 respectively. Between these two data sets, the error model correctly estimates the difficulty in generalization when the number of classes is increased or the number of training samples available per class is decreased for a given resolution. STL-10 and Tiny-Imagenet-200, which have larger resolutions than CIFAR but smaller number of training samples per class, also follow the curve predicted by the bound very closely. We chose $S=5$ for STL-10 and $S=3$ for Tiny-Imagenet-200 which have input resolutions of 96 and 64 respectively. Finally, for Imagenet-1k which has 1.2M images of varying resolutions with 1000 classes, our error model predicts the generalization error that is remarkably close to the observed test error. For Imagenet-1k we chose $S=4$. In the same plot we also plot our model's predicted generalization error if the input images were of 512x512 resolution instead of 256x256. We did not have the compute resources to check the test error in that setting, but we welcome other experimentalists to verify our prediction/conjecture. In summary, our error model does an excellent job in predicting the generalization error of CNN models on various standard image classification data sets, and shows that simple classical approximation theory ideas (suitably extended) might be useful in understanding CNNs.

\section{Heat maps} \label{sec:heatmaps}
The process of generating heat maps is very straightforward. We send every $T \times T$ patch of the input image with a stride of 1 and appropriate padding, as input to a trained model and note the predicted class and model's output value for that predicted class. To get the heatmap for a given class, we then superimpose the output values on the original image such that each pixel of the original image is nearly at the center of the corresponding tile patch. Padding is done with zeros on image edges to generate the same number of tiles as the number of pixels. Thus we can generate heat maps on images of any resolution using tiles of any size (with appropriate padding) and compare their quality across different models. To avoid confusion, we denote the tile size that is used to generate the heat maps by $T_{g}$, and the tile size that is used to train a model by $T_{m}$ i.e. the random crop size applied during the training preprocessing to generate training tiles.

\begin{figure}
    \centering
    \includegraphics[width=\linewidth]{figures/heatmap_grid_1.png}
    \caption{Heat maps for a sample dog image from STL-10 with ResNet18 models that were trained on different tile sizes $T_{m}$ on y-axis, generated using tiles of sizes $T_{g}$ on x-axis.}
    \label{fig:heatmap_grid_1}
\end{figure}

In our experiments, we compare the heat maps generated using different tile sizes ($T_{g}$) by models trained on different tile sizes ($T_{m}$) and also models which have been trained normally using common training practices i.e. pretrained and available to download via packages like \texttt{PyTorch} \citep{pytorch} and \texttt{TensorFlow} \citep{tensorflow} without any additional training. Figure \ref{fig:heatmap_grid_1} shows the heat maps of ResNet18 models that were trained on tiles of sizes 16x16, 56x56 and on full images of 96x96 of STL-10 dataset, generated using tiles of sizes 16, 24, 32, 48, 56 and 64 on a sample image. (Figure \ref{fig:gradcam_comp} in Appendix~\ref{sec:gradcam} shows the heatmap on a randomly downloaded image generated with 64x64 tiles using a \texttt{mobilenet\_v2} pretrained on Imagenet-1k model downloaded using \texttt{PyTorch}'s model zoo and without any additional retraining.) These heat maps show that CNNs learn to classify on small tiles whether they were explicitly trained on tiles or not, leading us to theorize that CNNs are only learning the labels of tiles and in general \textsl{do not} care about the global structure of the image, aided by the mitigation of curse of dimensionality, as discussed in Section~\ref{sec:error_bound_disc}. For a more comprehensive comparison of heat maps of Figure~\ref{fig:heatmap_grid_1} see the Appendix.

\subsection{Explaining model predictions} \label{sec:heatmap_explain}
Heat maps also help us understand the predictions of CNNs. From our discussion so far, if all that CNNs do is just predict labels on tiles, we should expect that similar tiles have similar labels across all images and we indeed observe the same. Figure~\ref{fig:plane_car_hm} shows heat maps for two such examples taken from STL-10 data set. For the \textit{plane} class, tiles from the sky background form the activating tiles instead of the planes themselves. This makes sense for obvious reasons that in most of the plane images, sky is the common attribute whereas the orientations, colors and sizes of planes vary. Similarly, for the \textit{car} class, wheels form the primary attribute and are accordingly highlighted in the heat maps.

This characteristic of CNNs to only focus on tiles can backfire if foreground tiles of one class are present as background tiles in an image belonging to another class. Figure~\ref{fig:birds_hm} shows exactly that for sample \textit{bird} images from STL-10. Here instead of a heat map, we color code each 16x16 tile based on its predicted class and assign it to the corresponding center pixel in the full image. For the first two samples, even though the \textit{bird} tiles are correctly classified, the overall prediction on the image is negatively influenced by the background sky tiles which are classified as \textit{plane}. Conversely, in the third sample, the green background tiles are classified as \textit{bird} but the tiles belonging to \textit{bird} are falsely classified as \textit{cat}, ultimately influencing its final prediction on the whole image. 

These heat maps can thus help to understand CNN models before deploying them to real world applications. If the heat maps generated by the model on sample images do not conform to human visual understanding of the image, the model is probably not going to be reliable in practice. This can be especially useful in medical applications where now the decisions by CNNs can be cross-checked by trained medical professionals. The heat maps can also suggest remedies for appropriate new training images with appropriate combinations of background and foreground tiles.

\begin{figure}
    \centering
    \includegraphics[width=\linewidth]{figures/plane_car_hm.png}
    \caption{Heat maps of images from STL-10 data set showing the activating tiles for \textit{plane} class as tiles of sky and for \textit{car} class as the tiles of wheels.}
    \label{fig:plane_car_hm}
\end{figure}

\begin{figure}
    \centering
    \includegraphics[width=\linewidth]{figures/birds_hm.png}
    \caption{Tiles color coded according to their predicted classes explaining the failure cases of few \textit{bird} class images from STL-10. First two sets of images show that background sky tiles predicted as \textit{plane} class influence the wrong decisions whereas the foreground feather tiles classified as \textit{cat} influence the wrong decision for the third sample.}
    \label{fig:birds_hm}
\end{figure}

\subsection{Effect of image resolution} \label{sec:heatmap_diff_res}

In Figure \ref{fig:diff_resolution} we show the heat maps generated by models that were trained with different resolution images from the same dataset, STL-10. For this we downsampled all the images in the dataset from 96x96 to 32x32 and trained ResNet9 models with tiles of sizes 8x8, 16x16 and 32x32 (regular training with full images) generated from these downsampled images. We compare these models with another set of ResNet9 models that are trained (using different tile sizes) on original 96x96 images, by looking at their corresponding full image test accuracies, at respective resolutions and at each of the tile sizes and also using the predicted generalization error for such a change in resolution. As our model predicts, the test error just shifts towards smaller tile sizes without much change in the test performance. This is also supported by the heat maps in Figure~\ref{fig:diff_resolution} which show that models trained on lower resolution and using tiles of smaller sizes, produces identical heat maps irrespective of the input resolution. For more examples of heat maps between images of different resolutions, refer the Appendix.

\begin{figure}
    \centering
    \includegraphics[width=\linewidth]{figures/diff_resolutions2.png}
    \caption{Comparison of heat maps and generalization error of models trained with tiles generated from different resolutions of STL-10 data set. Heat maps titled "label" correspond to the heat map of label class and those titled "predicted" correspond to the heat map of predicted class.}
    \label{fig:diff_resolution}
\end{figure}

\section{Conclusion}

We have shown experimental evidence for our claim that CNNs only learn labels of tiles when applied to image classification problems, and provided a simple theoretical model that can explain their generalization performance by mitigating the curse of dimensionality and obtained an upper bound for the generalization error. We also showed that this estimated generalization error closely matches the observed generalization performance of CNNs on various standard image classification data sets. We also provided a diagnostic tool in the form of \textsl{heat maps}, which is a natural application of our theory, that can be of practical use to deep learning practitioners in analysing their models and data sets. Moreover, as discussed in Section~\ref{sec:heatmap_explain}, our theory can help in designing better training sets, verifying models for deployment, as well as in new architecture design. Our theory also provides new insights into various unexplained behaviors of deep neural networks such as unsupervised learning, transfer learning, adversarial robustness and object detection. These and other matters will be presented elsewhere.

\begin{ack}
We would like to thank Lucas Beyer (Twitter user @giffmana), Andrew Brown, Jason Bunk, Aidan Chandrasekaran, Hirish Chandrasekaran, Jason Dunne, B.S.Manjunath, Hrushikesh Mhaskar and Abhejit Rajagopal, for useful discussions and valuable feedback.
\end{ack}

{
\small

