\section{Introduction}


Deep learning image classifiers are complex and nonlinear mathematical functions that extract features from images and learn to classify them based on those features. Yet, this mathematical process is not well understood, a major reason why interpretation, adversarial robustness, and generalization of them are all open research problems. By bringing computational methods from the image processing literature, in tandem with spectral methods from the numerical analysis literature, here, we develop computational methods to study the contents of image-classification datasets with the aim to understand the fine level patterns and features of images with respect to classification.

Deep learning functions are formed during training, by the contents of their training sets. Understanding the learning process and generalization, for some data types, may start with direct analysis of the data itself \citep{bahri2020statistical}. However, studying the contents of image-classification datasets is not straightforward \citep{strang2019linear}, because of the typical difficulties in working with visual signals. 


In practice and in research, learning of images is left to the models. From the adversarial point of view, image-classification models are vulnerable and this vulnerability seems inevitable \citep{shafahi2018adversarial} and even at odds with achieving good accuracy \citep{tsipras2018robustness,ilyas2019adversarial}. From the generalization point of view, models are highly over-parameterized and they can fit the contents of their training sets, even when training images are labeled randomly and even if the contents of images get replaced with random noise \citep{zhang2016understanding}. Recent studies have pursued this dilemma by making the distinction between the concepts of learning vs memorization \citep{belkin2018understand,belkin2019does}.

This lack of understanding about the models can partly be explained by our lack of knowledge about fine-grained details of image-classification datasets. Recently, a new line of research has focused on the contents of these datasets, studied the procedures used to gather and label the images, and raised questions about the learning, statistical bias and possible over-fitting of deep classifiers \citep{recht2019imagenet,yadav2019cold,recht2018cifar,engstrom2020identifying}. 
Still, there is a need for specialized computational procedures to analyze these datasets and explain what can make one image associated with one class and not with other classes. What is the essence of each image when it comes to classification?

From the optimization perspective, there are infinite number of global minimizers for training loss of image classification models, many of which would perform very badly on testing data \citep{arora2019fine,neyshabur2019towards}. Studies that focus on training, aim to find the minimizer that performs well on the testing set. But, the way to confirm that one has chosen a good minimizer of training loss is to measure its accuracy on a testing or validation set, and there is not an independent procedure to investigate whether there are specific associations between patterns and classes. Clearly, we would not expect a randomly labeled training set to have such association and that is why when one achieves zero training loss on such data, we consider it \textit{memorization} and not \textit{learning}.

Of course, a human can look at randomly labeled images and confirm the randomness of labels. But, can we devise computational procedures to evaluate that, without using a testing set? We would like such computational procedure to provide us with information such as:

\begin{hangparas}{.4cm}{1}
    1. There are no specific patterns in a dataset, if content of images are random noise.
    
    2. There are patterns in a dataset but not associated with classes, if images are randomly labeled.
    
    3. There are patterns in a dataset and each class is associated with certain patterns, if images are legitimately labeled and there are patterns in the dataset exclusive to individual classes.
\end{hangparas}


We develop a method to analyze image-classification datasets and provide the information above. Our approach can be considered a pattern recognition method which can analyze the datasets and provide {\bf insights about their learnability}. We show that each image can be written as the summation of a finite number of {\bf rank-1 patterns in the wavelet space}; and the main distinguishable patterns in each image can be reconstructed using a relatively small number of those patterns, providing a {\bf low-rank approximation to each image}. We extract the patterns by tensor decomposition of datasets in the wavelet space and then transform the patterns back to the pixel space. We see that when datasets are randomly labeled, some patterns may emerge but they cannot be associated with specific classes.
{"config": "arxiv", "file": "2006.09879/s1-intro.tex"}