\section{Numerical Experiments} \label{sec:results}


Here, we study the patterns in CIFAR-10 \citep{krizhevsky2009learning}. Our results on MNIST \citep{lecun1998gradient} are presented in Appendix~\ref{sec:appx_mnist}. 


We first consider two classes of Cat and Dog in the CIFAR-10, because they are two of the most similar classes and make up most of the mistakes by the state of art model \citep{kolesnikov2019large}.

To decompose images, we use the Daubechies-2 wavelet basis. In Appendix~\ref{sec:appx_data}, we explain the reason for this choice. The number of wavelet coefficients we use is $m = 3,000$ in this example, which corresponds to using $\tau = 7\times 10^4$ in Algorithm~\ref{alg:main}.


{\bf Singular values reveal patterns specific to each class.} 
Each $D_i$ has its own set of singular values, $\Sigma_i$. Comparison of singular values in $\Sigma_1$ and $\Sigma_2$ reveals which patterns (i.e., vectors in $V$) are influential for cats and which patterns are influential for dogs. Figure~\ref{fig:cifar_cd_singulars} shows the first 400 singular values for cats and dogs. The ratio of singular values and also the angular distance between them can be insightful in this analysis, as suggested by \cite{bradley2019gsvd}. When two singular values are equal for a particular basis, it means that the basis is equally common for them and not discriminative. But, when a singular value for one class is much larger compared to other classes, it means that the corresponding basis in $V$ is specific to that class. In Figure~\ref{fig:cifar_cd_singulars}, we can see many such cases.

\begin{figure}[H]
  \centering
   \includegraphics[width=0.6\linewidth]{fig_cd_singulars.png}
  \caption{The first 400 singular values of $\Sigma_1$ and $\Sigma_2$. Larger singular value for one class signifies the importance of corresponding right basis for that class. Clearly, there are distinct separations between some of the singular values.}
  \label{fig:cifar_cd_singulars}
\end{figure}

{\bf Reconstructing the patterns back in the pixel space.}
Each column in $V$ corresponds to a pattern and we can reconstruct the patterns back in the pixel space, using the same wavelet basis. Figure~\ref{fig:rightbasis_dog} shows the four most dominant bases for Dogs, in the pixel space. By dominant, we mean these bases have large singular values for the Dog class, but small singular values for Cats. Similarly, Figure~\ref{fig:rightbasis_cat} shows the patterns dominant for cats, back in the pixel space.


\begin{figure}[H]
  \centering
  \begin{subfigure}[b]{0.49\textwidth}
  \centering
  \fbox{
   \includegraphics[width=0.15\linewidth]{fig_cd_right_16.png}
   \includegraphics[width=0.15\linewidth]{fig_cd_right_17.png}
   \includegraphics[width=0.15\linewidth]{fig_cd_right_20.png}
   }
  \caption{Dogs.}
  \label{fig:rightbasis_dog}
  \end{subfigure}
  \hspace{-2cm}
  \begin{subfigure}[b]{0.49\textwidth}
  \centering
  \fbox{
   \includegraphics[width=0.15\linewidth]{fig_cd_right_1.png}
   \includegraphics[width=0.15\linewidth]{fig_cd_right_4.png}
   \includegraphics[width=0.15\linewidth]{fig_cd_right_5.png}
   }
  \caption{Cats.}
  \label{fig:rightbasis_cat}
  \end{subfigure}
  \caption{Images reconstructed in the pixel space from the most dominant right basis columns.}
  \label{fig:rightbasis}
\end{figure}


{\bf Understanding the contribution of each pattern to each image.}
Each of the patterns present in $V$ contribute to each image in the dataset with some coefficient, determined in the left basis. In fact, we can write each image as the summation of the patterns in the pixel space, using Equation~\ref{eq:sum_rank1}. 
Figure~\ref{fig:cifar_cd_pattern_coeff} shows the coefficients of contribution for all images in this data, for the most dominant dog pattern vs the most dominant cat pattern. While a clear separation between the two classes is visible, we can also see a considerable overlap of points near the origin. This overlap corresponds to images that are not getting a noticeable contribution from these two specific patterns, and such images belong to both classes. To summarize, the most dominant dog pattern never contributes significantly to any of the cat images, it contributes significantly to some of the dog images, and it also does not contribute to many of the images in the dog class. Those dog images get their contributions from other dog patterns in $V$.


\begin{figure}[h]
  \centering
   \includegraphics[width=0.5\linewidth]{fig_cd_pattern_coeff.png}
  \caption{Contribution of most dominant dog pattern vs the most dominant cat pattern to all images in the dataset. There is a clear separation between classes, but there is also a considerable overlap near the origin (i.e., some images do not get considerable contributions from these two patterns.}
  \label{fig:cifar_cd_pattern_coeff}
\end{figure}


{\bf Low rank approximation constructs image major structure, recognizable by deep neural nets.} Each image is the summation of $m$ patterns, and each of those patterns has rank-1 in the wavelet space. Therefore, we can reconstruct low rank approximation of each image, using a relatively small number of those patterns. Figure~\ref{fig_reconstruction_tr1} shows the evolution of one cat image as $j$ moves from 1 to $m$. For example, the image at the far left of this Figure, is the result of $\sum_{j=1}^{100} \sigma_j U_i(:,j) V_i(j,:)$ and the image at the far right is the result of $\sum_{j=1}^{3000} \sigma_j U_i(:,j) V_i(j,:)$.


\begin{figure}[H]
  \centering
   \includegraphics[width=0.1\linewidth]{fig_cd_tr1_100.png}
   \includegraphics[width=0.1\linewidth]{fig_cd_tr1_200.png}
   \includegraphics[width=0.1\linewidth]{fig_cd_tr1_300.png}
   \includegraphics[width=0.1\linewidth]{fig_cd_tr1_500.png}
   \includegraphics[width=0.1\linewidth]{fig_cd_tr1_1000.png}
   \includegraphics[width=0.1\linewidth]{fig_cd_tr1_1500.png}
   \includegraphics[width=0.1\linewidth]{fig_cd_tr1_2000.png}
   \includegraphics[width=0.1\linewidth]{fig_cd_tr1_3000.png}
  \caption{Images reconstructed by cumulatively adding rank-1 patterns in $V$. We see that for many images, the main structure and its distinctive features are obtained by adding a relatively small portion of patterns in the wavelet space. This is the first training image of Cat class.} 
  \label{fig_reconstruction_tr1}
\end{figure}

Figure~\ref{fig_residual_tr1} shows the change in the residual, where the residual is the Frobenius norm between the original image and the reconstructed image from the wavelet space, during the process of adding rank-1 images. We present similar results for more images in Appendix~\ref{sec:appx_rank1}.

\begin{figure}[H]
  \centering
   \includegraphics[width=0.5\linewidth]{fig_cd_tr1_residual.png}
  \caption{Residual of reconstructed image from the wavelet coefficients as we add more rank-1 patterns to it. The residual usually decreases during the process, implying that most rank-1 patterns are individually a useful contribution to the original image.
}
  \label{fig_residual_tr1}
\end{figure}


{\bf Complexity of images interpreted via the left basis.}

The left basis $U_i$ determines how the right basis vectors of $V$ should be put together in order to obtain the image. Each row of $U_i$ corresponds to one image in $D_i$. The rows of $U$ that have smaller norms correspond to images that are simpler, i.e., made of fewer components, e.g., Figure~\ref{fig_simple}. The rows of $U$ with larger norm correspond to images with more components, e.g., Figure~\ref{fig_notsimple}. Additionally, one can investigate the sparsity of rows of the left basis, which we leave in favor of brevity.

\begin{figure}[H]
  \centering
  \begin{subfigure}[b]{0.495\textwidth}
  \centering
  \fbox{
   \includegraphics[width=0.15\linewidth]{cd_train_simple_2431.png}
   \includegraphics[width=0.15\linewidth]{cd_train_simple_1960.png}
   \includegraphics[width=0.15\linewidth]{cd_train_simple_3922.png}
   \includegraphics[width=0.15\linewidth]{cd_train_simple_6453.png}
   \includegraphics[width=0.15\linewidth]{cd_train_simple_1770.png}
   \includegraphics[width=0.15\linewidth]{cd_train_simple_6350.png}
   }
  \caption{Images with smaller norm in left basis}
  \label{fig_simple}
  \end{subfigure}
   \begin{subfigure}[b]{0.495\textwidth}
   \centering
   \fbox{
   \includegraphics[width=0.15\linewidth]{cd_train_simple_9115.png}
   \includegraphics[width=0.15\linewidth]{cd_train_simple_7879.png}
   \includegraphics[width=0.15\linewidth]{cd_train_simple_6754.png}
   \includegraphics[width=0.15\linewidth]{cd_train_simple_3579.png}
   \includegraphics[width=0.15\linewidth]{cd_train_simple_3135.png}
   \includegraphics[width=0.15\linewidth]{cd_train_simple_7502.png}
   }
   \caption{Images with higher norm in left basis}
  \label{fig_notsimple}
  \end{subfigure}
  \caption{Complexity of images reflected through the left basis. \textbf{(a)} Images with smaller norm in left basis look simpler and have fewer distinctive features; \textbf{(b)} images with higher norm in left basis do not look simple and have several distinctive features.}
\end{figure}


{\bf Distinctive Patterns Discovered for All classes of CIFAR-10.} 

As we saw previously, one of the important aspects of our interpretation is to associate the patterns to specific classes, which is done by comparing the singular values. When we repeat this analysis for all 10 classes of this dataset, we see that patterns emerge that are associated with more than 1 class.

Figure~\ref{fig:cifar_all_singulars} shows the log of 1,000 singular values obtained for this dataset. Clearly, classes of Truck and Automobile have the highest singular values for many of the patterns, which makes them distinguishable from the others, but not so helpful to distinguish each class from all other classes. This suggests that our approach could be useful in a hierarchical setting where classes are grouped and then analyzed further. Alternatively, one could consider using our method for pairwise comparison of classes as in Siamese networks \citep{bertinetto2016fully}. We next make the labels random to see how it affects the learnability of dataset.


\begin{figure}[H]
     \centering
     \begin{subfigure}[b]{0.42\textwidth}
        \centering
        \includegraphics[width=.8\linewidth]{fig_all_singulars.png}
         \caption{Correct labels}
         \label{fig:cifar_all_singulars_correct}
     \end{subfigure}
     \hspace{-1.5cm}
     \begin{subfigure}[b]{0.52\textwidth}
        \centering
       \includegraphics[width=.8\linewidth]{fig_all_singulars_rand.png}
         \caption{Random labels}
         \label{fig:cifar_all_singulars_random}
     \end{subfigure}
        \caption{The first 1,000 singular values of $\Sigma_i$'s for all 10 classes of CIFAR-10 dataset. Note that we have used logarithmic transformation in this figure. Any association between patterns and classes fades away, when we make the labels random.}
        \label{fig:cifar_all_singulars}
\end{figure}


{\bf Labeling the images randomly to diminish learn-ability.}
We repeat the spectral analysis to see if patterns will be associated with classes or not, when labels are random. We know that deep learning models can achieve perfect accuracy on this training set, even when all the images are labeled randomly, and one would not be able to detect the randomness of labels just by training a model. We show that our method reveals whether there is {\bf learnable classification information} present in the training set, useful in practice, and also useful for studying the concept of {\bf memorization vs learning}. 

When we make the labels random for all images, the decomposition we obtain is very different and ambiguous. Specifically, the singular values become uniform across classes, as shown in Figure~\ref{fig:cifar_all_singulars_random}.

To demonstrate this effect more clearly, we measure the angular distance between the singular values of two classes of Ship and Truck, with the correct labels (Figure~\ref{fig:cifar_all_singulars_correct}) and with random labels (Figure~\ref{fig:cifar_all_singulars_random}). As shown in Figure~\ref{fig:cifar_angular}, in the correct label case, singular values are discriminitive between the two classes, i.e., for many patterns, the angular distance is noticeable (\textcolor{blue}{blue} line). However, in the random label case, the angular distance between singular values are close to zero for almost all the patterns (\textcolor{red}{red} line).

If we limit the portion of randomly labeled data, for example, to 20\% and keep the correct labels for the rest of images, we see that the obtained results are not very different from the results we obtained for the correctly labeled data. Repeating this with different portions of random labels shows that the disassociation between patterns and labels is directly related to the portion of random labels.

\begin{figure}[H]
  \centering
   \includegraphics[width=0.6\linewidth]{fig_cifar_angular.png}
  \caption{Angular distance (absolute value) between singular values of classes Ship and Truck, when labels are correct (\textcolor{blue}{blue}) and when labels are random (\textcolor{red}{red}). Randomizing the labels leads to collapse of angular distances and makes the patterns disassociated from the classes.}
  \label{fig:cifar_angular}
\end{figure}
{"config": "arxiv", "file": "2006.09879/s5-experiments.tex"}