Improved neural network generalization using channel-wise NNK graph constructions

Improved Neural Network Generalization using Channel-Wise NNK Graph Constructions Degree Thesis submitted to the Faculty of the Escola T`ecnica d’Enginyeria de Telecomunicaci´o de Barcelona Universitat Polit`ecnica de Catalunya by David Bonet Sol´e In partial fulfillment of the requirements for the degree in Telecommunications Technologies and Services Engineering Advisors: Antonio Ortega (USC Viterbi) Javier Ruiz-Hidalgo (UPC ETSETB) Sarath Shekkizhar (USC Viterbi) Barcelona, June 2020 Abstract State-of-the-art neural network architectures continue to scale in size and deliver impressive results on unseen data points at the expense of poor interpretability. In the deep layers of these models we often encounter very high dimensional feature spaces, where constructing graphs from intermediate data representations can lead to the well-known curse of dimensionality. We propose a channel-wise graph construction method that works on lower dimensional subspaces and provides a new channel-based perspective that leads to better interpretability of the data and relationship between channels. In addition, we introduce a novel generalization estimate based on the proposed graph construction method with which we perform local polytope interpolation. We show its potential to replace the standard generalization estimate based on validation set performance to perform progressive channel-wise early stopping without requiring a validation set. i Resum Les arquitectures de xarxes neuronals m´es avan¸cades segueixen augmentant la seva mida i oferint resultats impressionants en noves dades a costa d’una escassa interpretabilitat. A les capes profundes d’aquests models ens trobem sovint amb espais de caracter´ıstiques de molt alta dimensi´o, en qu`e la construcci´o de grafs a partir de representacions de dades interm`edies pot portar al conegut curse of dimensionality. Proposem un m`etode de construcci´o de grafs per canal que treballa en subespais de menor dimensi´o i proporciona una nova perspectiva basada en canals, que porta a una millor interpretabilitat de les dades i de la relaci´o entre canals. A m´es, introdu¨ım un nou estimador de generalitzaci´o basat en el m`etode de construcci´o de grafs proposat amb el qual realitzem interpolaci´o local en pol´ıtops. Mostrem el seu potencial per substituir l’estimador de generalitzaci´o est`andard basat en el rendiment en un set de validaci´o independent per a realitzar early stopping progressiu per canals i sense necessitat d’un set de validaci´o. ii Resumen Las arquitecturas de redes neuronales m´as avanzadas siguen aumentando en tama˜no y ofreciendo resultados impresionantes en nuevos datos a costa de una escasa interpretabilidad. En las capas profundas de estos modelos nos encontramos a menudo con espacios de caracter´ısticas de muy alta dimensi´on, en los que la construcci´on de grafos a partir de representaciones de datos intermedias puede llevar al conocido curse of dimensionality. Proponemos un m´etodo de construcci´on de grafos por canal que trabaja en subespacios de menor dimensi´on y proporciona una nueva perspectiva basada en canales, que lleva a una mejor interpretabilidad de los datos y de la relaci´on entre canales. Adem´as, introducimos un nuevo estimador de generalizaci´on basado en el m´etodo de construcci´on de grafos propuesto con el que realizamos interpolaci´on local en politopos. Mostramos su potencial para sustituir el estimador de generalizaci´on est´andar basado en el rendimiento en un set de validaci´on independiente para realizar early stopping progresivo por canales y sin necesidad de un set de validaci´on. iii Acknowledgements First and foremost, I would especially like to thank Prof. Antonio Ortega for his exceptional guidance and advice during this research project. Despite the situation caused by the COVID-19 pandemic, he gave me the opportunity to conduct my thesis in his group, which I am truly grateful for. Special thanks to Prof. Javier Ruiz-Hidalgo and Sarath Shekkizhar for their advice and help during the whole project. Remote work has been a challenge, but all of you have made me feel very welcome and it has been a really enjoyable experience. Finalment, voldria agrair i dedicar aquest treball a la meva fam´ılia i amics, pel seu amor i suport incondicional. Amb especial menci´o als meus pares, per ajudar-me sempre que ho he necessitat, donant-me l’oportunitat de dedicar-me al que m’agrada sense haver de preocupar-me de res m´es. iv Revision history and approval record Revision Date Purpose 0 14/05/2021 Document creation 1 20/06/2021 Document revision 2 21/06/2021 Document approval DOCUMENT DISTRIBUTION LIST Name e-mail David Bonet Sol´e Antonio Ortega Javier Ruiz-Hidalgo Sarath Shekkizhar Written by: Reviewed and approved by: Date 14/05/2021 Date 21/06/2021 Name David Bonet Sol´e Name Javier Ruiz-Hidalgo Position Project Author Position Project Supervisor v Contents List of Figures viii List of Tables x Acronyms xi 1 Introduction 1 1.1 Motivation.................................... 1 1.2 MainContributions............................... 2 1.3 Overview..................................... 2 1.4 Workplan.................................... 3 2 Fundamentals 4 2.1 Graph Signal Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.1.1 Basicdefinitions............................. 4 2.1.2 Similarity-based Graph Construction Methods . . . . . . . . . . . . 5 2.2 Convolutional Neural Networks . . . . . . . . . . . . . . . . . . . . . . . . 7 3 CW-NNK graphs and their aggregation 8 3.1 K-NNanalysis ................................. 9 3.2 NNKanalysis .................................. 11 3.3 Experiments................................... 14 3.3.1 Curse of dimensionality illustration with Distance Ratio . . . . . . 14 3.3.2 NNK neighbors overlap between channels . . . . . . . . . . . . . . . 17 3.3.3 Sufficient Kto construct the NNK polytope . . . . . . . . . . . . . 19 3.3.4 Dimension significance and overall dimensionality reduction effect . 21 3.3.5 Complexity ............................... 22 3.4 Discussion.................................... 23 4 CW-DeepNNK generalization estimate without validation set 24 4.1 Relatedwork .................................. 25 4.2 DeepNNK: generalization estimate using polytope interpolation . . . . . . 25 4.2.1 CW-DeepNNK ............................. 26 4.3 Experiments................................... 27 4.3.1 Interpretation of channel-wise generalization estimates . . . . . . . 28 4.3.2 Relevant channel detection based on NNK polytope local geometry 30 4.3.3 Comparison of generalization estimates for early stopping . . . . . . 31 4.3.4 Complexity ............................... 32 4.4 Discussion.................................... 33 5 Budget 34 6 Conclusions and Future Work 35 vi Bibliography 36 A Experiment Details 40 A.1 Section3.3model................................ 40 A.2 Section4.3model................................ 41 A.3 Hyperparameters ................................ 41 B Nonzero heatmaps of CNN activations 42 vii 1.4 Work plan The work on this thesis was organized according to the following schedule: Phases of the Project 2021 Jan Feb Mar Apr May June Research 100% complete Read literature 100% complete Replicate results Analysis 100% complete Channel graphs Coding 100% complete TensorFlow 100% complete Experiments Writing 100% complete Thesis/Paper Figure 1.1: Gantt diagram of the project. There have been no major changes with respect to the initial planning. The beginning of the project was very exploratory, understanding this new perspective of building channel-wise graphs in depth and analyzing the different paths it could open. At the experimental level, in the last three months we finished defining the final objectives of the project and how we could use this new method to improve interpretability and generalization in neural networks. Finally, the last month has been mostly devoted to writing this thesis report and preparing a paper submission for a signal processing conference. 3 Chapter 2 Fundamentals 2.1 Graph Signal Processing We start by introducing basic concepts and notation of Graph Signal Processing (GSP) [20]. GSP is the study of how to analyze and process data associated with graphs. 2.1.1 Basic definitions Agraph G= (V,E) is a discrete structure that consists of a set of nodes, V={v1, v2, . . . , vN} and a set of edges, E={e1, e2, . . . , eM}. The graph is weighted if real positive weights wij are associated with each edge eij that connects nodes iand j, or unweighted if all edges have weight equal to 1. If two nodes iand jare not connected, then wij = 0. A graph is undirected if eij exists whenever eji exists and wij =wji. Conversely, a graph is directed if eij or eji may not exist and in general wij 6=wji. The adjacency matrix Wof the graph is an N×Nmatrix that captures all connectivity and edge weight information, with Wij =wij. A graph with Nnodes is considered dense if the number of edges per node is close to N, and sparse if the number of edges incident to any node is much smaller than N. The graph signal is composed of Ndata points with feature vectors {x1,x2,...,xN} ∈ RD. Each feature vector xhas dimension Dand can be viewed as the aggregation of S lower-dimensional subvectors xs i∈RDswhere PS s=1 Ds=D: xi=     x1 i x2 i . . . xS i      ∈RD(2.1) In this work, nodes represent data points that are part of a dataset, and the edges represent similarity between data points. In a supervised classification setting, each data point belongs to a category, i.e., it has a label associated to it. The goal is for a model to learn a function that best approximates to which category a new sample of data belongs to. As the feature vectors corresponding to each data point we can use either the features at the input of the model (e.g., original images of the training set) or the learned intermediate representations in convolutional layers, so that the separation of the features into channels is natural and complete. 4 2.1.2 Similarity-based Graph Construction Methods We can define a notion of node similarity based on a pairwise similarity metric, e.g., distance, d(i, j) = kxi−xjk. If good feature vectors have been chosen to represent the data, it is expected that the labels of points that are close to each other are more likely to be the same. This would result in a label signal that is smooth on the similarity graph, i.e., where large wij are generally associated with nodes that fall into the same category, i.e., d(i, j) small. A common method to do this is to define edge weights based on the Gaussian kernel: k(xi,xj) = exp −d(i, j)2 2σ2(2.2) where σis the bandwidth of the Gaussian Kernel. Another option is to use the range normalized cosine kernel: k(xi,xj) = 1 21 + hxi,xji kxikkxjk(2.3) Note that, if we directly select all wij =k(xi,xj), both kernels will produce a complete weighted graph, since it is very unlikely to obtain exactly zero weights. In order to obtain a sparser graph with fewer connections we can apply different optimizations, which we discuss next. Neighborhood optimization Weighted K-Nearest Neighbor (K-NN) graphs [21] and -neighborhood graphs (-graphs) [22] are among the the most commonly used graph construction methods. K-NN graphs are constructed by connecting every node v∈ V to its Kmost similar nodes in V. Thus, only Kpairwise distances d(i, j) are needed. If (2.2) is used as the similarity metric, K and σhave to be chosen. In -graphs we also have to choose the parameter . The choice of parameters usually depends on the dataset distribution or the task at hand. Defining dmin = mini,jkxi−xjk, if σis much larger than dmin, edge weights will collapse to 1. Conversely, if σis much smaller than dmin, most weights will be very small. A common solution is to choose σbased on statistics of local distances (e.g. minimum or average distance for each point in the dataset). For some tasks, the choice of K,σor is usually heuristic or based on a cross-validation strategy to obtain the best performance in a task [23]. A downside of this methods is that they do not consider the possibility of two nodes being redundant. Other approaches such as kernel learning [24] and adaptive edge weighting (AEW) [25] try to optimize the weights of K-NN/-graphs to the data without modifying the connectivity. Alternative techniques described below address this problem by taking into account relative distances. Local linear embedding (LLE) In local linear embedding [10], for each node i, a K-NN search is done and XSis the matrix containing in columns the feature vectors of the Knearest neighbors of xiwhose 5 indices are denoted by set S. Then, LLE solves: min θ:θ≥0kxi−XSθk2 2(2.4) where the solution θcorresponds to the weights of the edges connecting node iand all the nodes in S. If two nodes j, k ∈ S are very close, they may be redundant in terms of linear approximation (2.4), resulting in wij or wik being zero. State-of-the-art graph construction methods [26, 27] also aim to be locality-inducing using explainable regularization techniques. Non Negative Kernel (NNK) regression graphs Positive definite kernels k(xi,xj) such as (2.2) and (2.3) correspond to a transformation of data points in RDto a non linearly transformed feature space Hreferred to as the reproducing kernel Hilbert space [28], such that similarities can be interpreted as dot products in this transformed space (generally known as the kernel trick), i.e., k(xi,xj) = φT iφj, where φ:RD→ H and φirepresents the transformed observation of xi. Non-negative kernel graph construction [11] also starts finding the Knearest neighbors of each node denoted by the set S. Then, the NNK optimization at each node solves: θS= min θ:θ≥0kφi−ΦSθk2 2(2.5) where ΦScontains the transformed neighbors. Using the kernel trick, the NNK problem can be rewritten as: θS= argmin θ:θ≥0 1 2θTKS,Sθ−KT S,iθ(2.6) where Ki,j =k(xi,xj). Finally, the i-th row of the adjacency matrix Wis given by Wi,S=θSand Wi,SC=0. An advantage of NNK over other methods such as K-NN, which select the Klargest inner products φT iφjand can be viewed as a thresholding-based representation, is its robustness to sparsity parameters such as K. NNK also has a geometric interpretation based on the Kernel Ratio Interval (KRI) theorem: In a three-node scenario, for any positive definite kernel with range [0,1], the necessary and sufficient condition for two data points xjand xkto be connected to xiin an NNK graph is Kj,k <Ki,j Ki,k <1 Kj,k (2.7) In words, the interval for both nodes to be connected to iis large if the two nodes, j and k, are dissimilar. But if the two nodes are very similar, the interval for both edges to exist is very small, and only one node of the two will be connected to the query node i. In the case of the Gaussian kernel (2.2), considering the edge θij connecting node i and node j, we can define a hyperplane with normal in the edge direction. As shown in Figure 2.1a this hyperplane divides the space in two, a region Rij that contains xi, and 6 (a) (b) Figure 2.1: (a) KRI hyperplane corresponding to connected neighbor xj. (b) KRI boundary associated to the convex polytope formed by NNK neighbors around xi.From [1], with permission. its complement Rij. Then, the third node kwill be connected to ionly if xk∈Rij. If xk∈Rij in a three-node scenario, θik = 0 and we say that khas been eliminated by the hyperplane created by j. Inductive application of the KRI connects to other points while producing a closed decision boundary around xi, i.e., the NNK optimization at each node constructs a convex polytope around node idisconnecting all the other points outside the polytope, see Figure 2.1b. The resulting set of NNK neighbors for each node is denoted by N. Also note that N ⊆ S. 2.2 Convolutional Neural Networks Convolutional Neural Networks are one of the most popular types of Deep Neural Networks (DNN). They have multiple layers and they are often composed of convolutional layers, non-linearity layers, pooling layers and a fully-connected layer [29]. Input data of the model used usually consists of several channels, with each channel being the observation of a different quantity at some point in space or time [17]. Convolutional layers filter its multi-channel (aggregate of channels) input several times with multiple filters, commonly between 16 and 512, resulting also in a multi-channel output, where each channel captures different features of the input of the layer. Note that in each layer we encounter very high dimensional feature spaces, formed by the aggregation of large numbers of channels. In this work we use the terms ”subvector” and ”channel” interchangeably, since a convolutional channel is a subvector of a convolutional layer. ReLU is the most used non-linear function, both for its function and gradient simplicity. Also for its capability to avoid ”vanishing gradients” and to create sparser representations. Other activations functions such as sigmoid or tanh always obtain non-zero values, while ReLU collapse a lot of dimensions to complete zeros. 7 Chapter 3 CW-NNK graphs and their aggregation Dealing with high dimensional data can lead to the well-known curse of dimensionality [30], which refers to the fact that volume in the space increases very fast with dimension, make available data sparse, unless the amount of data also increases significantly. Under these conditions, distances between points can become meaningless or not very informative [31], e.g., we might find that most of the points appear to be at similar distances with respect to each other. This is a problem to keep in mind when building graphs with edge weights based on node similarity, since if all the weights have similar values and we get a complete graph, it does not give us useful information about the data [20]. However, most state of the art machine learning models work with high dimensional data, and still obtain very competitive results [14]. This is because, in practice, the curse of dimensionality is effectively avoided [32, 33, 34]. The problem in this case is that it is not clear how the dimensionality problem is alleviated. Many theoretical results [35, 36] indicate that the data lies in a low-dimensional manifold and its intrinsic dimension (ID) is much lower than the nominal one, defining ID as the number of ”degrees of freedom” that are necessary to generate the observed data. Other works try to estimate the ID to facilitate understanding and analysis in high dimensional spaces [37, 38, 39]. Nevertheless, we lack a clear understanding of how the manifold can be characterized in such high dimensional spaces. Most works analyze data feature vectors as a whole, i.e., as a single indivisible feature vector. In this work we seek a new perspective where we can understand the feature space as the aggregation of well-defined, low-dimensional feature subspaces. For example, we consider the activations of a convolutional layer of a neural network, where hundreds of outputs from different convolutional filters are aggregated to represent a single input image, as a concatenation of multiple subvectors, each associated with the output of one of the channels in the deep neural network. In this thesis a feature vector corresponds to a complete representation of an item (e.g., an image). Each feature vector contains subvectors, each generated by a distinct computation in the feature extraction (e.g., the output of one of the channels comprising a convolution, non-linearity and pooling operations in a neural network). The feature vectors are contained in a feature space, were we can also refer to the independent subspaces induced by specific subvectors. Shekkizhar and Ortega [11] observed the number of connections resulting from the NNK optimization, where redundant neighboring points are neglected, to be indicative of the ID of the data manifold. Thus, we take the average number of NNK neighbors as a proxy for ID. Constructing channel-wise NNK (CW-NNK) graphs we can study the ID in each subspace, which allows us to develop a better understanding of why the ID is much lower than what would have been predicted based on the overall dimension of the feature 8 vectors. In particular, CW-NNK graphs also allow us to derive overall interrelationships between independent feature subspaces from common neighboring NNK points. The curse of dimensionality also implies a greater difficulty in terms of computation, since nearest neighbor methods can have an exponential dependence on dimensions when executing a search query [23]. We show how solving the NNK optimization per channel and combining the results allows skipping steps in the aggregate problem and reduce complexity. This holds not only in the case of convolutional layers, but in any scenario where we have defined channels or sub-features. In real datasets or data representations not all dimensions have the same importance [40]: some of them play an important role for the specific task, while others are characterized by small variations that may be irrelevant to the analysis. In the specific case of neural networks, ID has been studied for full layer intermediate representations [33, 32]. This work, to the best of our knowledge, is the only one that studies ID by considering each of the channels separately and then aggregating information, to better explain the behaviour in individual channels. show how an in-depth analysis of the subvectors with CW-NNK graphs helps us to determine better the relative importance of the various dimensions, as compared to what can be achieved with a general approach. We analyze how there are dimensions that practically do not contribute to the task and how they imply a direct reduction of the ID. Ultimately, our work tries to explain why even though systems of interest operate in high dimension we do not really suffer a performance penalty due to the curse of dimensionality. 3.1 K-NN analysis From the channel-wise graph construction, we can have a better understanding of how it is possible for the intrinsic dimensionality of the data to be relatively low even in a high dimensional space. A theoretical analysis that builds on the information obtained from the NNK optimization in each of the independent channels allows us to better understand the relationship between the channels. From the sets of nearest neighbors and the NNK neighbors in the subvectors, we can study the relationship between the channels and infer relevant information and properties of the graph that we would obtain in the aggregate high dimensional space. For simplicity, we consider a scenario of two subvectors and their aggregate: xi=x1 i x2 i∈RD xi= (xi(0), xi(1), . . . , xi(D−1))T= (x1 i(0), . . . , x1 i(D1−1), x2 i(0), . . . , x2 i(D2−1))T where x1 i∈RD1and x2 i∈RD2are the two defined subvectors of xiand D1+D2=D, but all the results presented in this section can be extended to the multiple channel case. The first step to build an NNK graph is to find the Knearest neighbors to node i(complexity of the algorithms we describe will be discussed in Section 3.3.5). As an 9 example, in the full space the query is xiand {x1,x2,...,xN} ∈ RDare the training data points, excluding xifrom the training set. Given some norm k·kon RD, let x(1),...,x(K),x(K+1),...,x(N)be a reordering of the training data such that kx(1) −xik ≤ · · · ≤ kx(K)−xik≤kx(K+1) −xik ≤ · · · ≤ kx(N)−xik. Note that kx(1) −xik2≤ · · · ≤ kx(K)−xik2≤ · · · ≤ kx(N)−xik2 can also be written as kx1 (1) −x1 ik2+kx2 (1) −x2 ik2≤ · · · ≤ kx1 (K)−x1 ik2+kx2 (K)−x2 ik2≤ · · · ≤ kx1 (N)−x1 ik2+kx2 (N)−x2 ik2. The indices of the Knearest neighbors to xiin the aggregate space are denoted by set SA, while the the Knearest neighbors to x1 iand x2 iare denoted by S1and S2, respectively. We now analyze which properties of the set SAcan be inferred from the sets S1and S2. Then, we analyze the properties of the set of NNK neighbors NAwe can infer from N1and N2. Assume <instead of ≤for simplicity. Lemma 3.1.1. If j /∈ S1and j /∈ S2then j /∈ SA. Proof. Let us consider the edge case where for the sets S1and S2, we have that x1 k∈ S1 and x2 k∈ S2as the (K)th neighbor in both sets, while x1 j/∈ S1and x2 j/∈ S2is the (K+ 1)th neighbor in both sets: kx1 k−x1 ik2<kx1 j−x1 ik2 kx2 k−x2 ik2<kx2 j−x2 ik2 In the aggregate: kx1 k−x1 ik2+kx2 k−x2 ik2<kx1 j−x1 ik2+kx2 j−x2 ik2 Let kx1 k−x1 ik2=a,kx1 j−x1 ik2=a+γ,kx2 k−x2 ik2=band kx2 j−x2 ik2=b+, a+b<a+γ+b+ γ+ > 0 where γ,  > 0 This result leads to the following corollary. Corollary 3.1.1.1. If the number of neighbors Kis the same for both subvectors and for the aggregate and if S1=S2, then S1=S2=SA. Lemma 3.1.2. If j∈ S1∩ S2,k /∈ S1and k∈ S2, it is possible that j /∈ SAwhile k∈ SA. 10 Proof. Let ibe the query, we know: kx1 j−x1 ik2<kx1 k−x1 ik2 Consider the edge case selecting the last neighbor (Kth neighbor) in SA. If jis selected, k6∈ SA, and vice versa. Since both x2 jand x2 kare in S2, there are two possibilities: if kx2 j−x2 ik2<kx2 k−x2 ik2, xjwill be selected as a neighbor in the aggregate, j∈ SA. But if kx2 j−x2 ik2>kx2 k−x2 ik2, xjwill be selected as a neighbor only if kx1 j−x1 ik2+kx2 j−x2 ik2<kx1 k−x1 ik2+kx2 k− x2 ik2. Corollary 3.1.2.1. Every point j∈ S1∩S2will be selected in the aggregate if kx1 j−x1 ik2+ kx2 j−x2 ik2<kx1 k−x1 ik2+kx2 k−x2 ik2∀k∈ S14S2, where S14S2= (S1∪S2)\(S1∩S2). In words, a point j∈ S1∩S2can be eliminated of SAby other points found in S14S2. If the above condition is satisfied for all points k∈ S14S2, we can be sure that jwill be selected in the aggregate. The main relevance of this result is that the complexity of the K-NN search in the aggregate could be reduced, since those points guaranteed to be selected can be added directly to the aggregate neighborhood. 3.2 NNK analysis Proposition 3.2.1. Gaussian kernel in the aggregate space is the product of Gaussian kernels in the subvectors. Proof. In the aggregate space, Ki,j =k(xi,xj) = exp −kxi−xjk2 2σ2. Where kxi−xjk2= S X s=1 kxs i−xs jk2(3.1) and Sis the number of subvectors. Then, Ki,j = S Y s=1 Kis,js(3.2) In a two-subvector scenario: Ki,j = exp −kx1 i−x1 jk2+kx2 i−x2 jk2 2σ2 Ki,j =Ki1,j1Ki2,j2 (3.3) Theorem 3.2.2. If j∈ N1and j∈ N2then j∈ NA. 11 Proof. Consider a three-node scenario with j,k, and query i. We know that θi1,j1>0 and θi2,j2>0. Based on KRI theorem (2.7): θi1,j1>0⇐⇒ Kj1,k1<Ki1,j1 Ki1,k1 (3.4) θi2,j2>0⇐⇒ Kj2,k2<Ki2,j2 Ki2,k2 (3.5) Then, in the aggregate: θi,j >0⇐⇒ Kj,k <Ki,j Ki,k ∀k∈ SA(3.6) Using Proposition 3.2.1: Kj,k <Ki,j Ki,k can be expressed as Kj1,k1Kj2,k2<Ki1,j1Ki2,j2 Ki1,k1Ki2,k2 .(3.7) Let Kj1,k1=a,Kj2,k2=b,Ki1,j1 Ki1,k1 =a+γand Ki2,j2 Ki2,k2 =b+. Then, we can substitute terms in (3.7): ab < (a+γ)(b+) a +bγ +γ > 0⇐⇒ θi,j >0 where 0 ≤a, b ≤1 and γ,  > 0 considering (3.4) and (3.5). j∈ NA⇐⇒ j∈ N1, j ∈ N2, j ∈ SA(3.8) In words, if jis not eliminated by any other hyperplane created by a third point kin the subvectors (is an NNK neighbor in all subvectors), then j∈ NA(θi,j >0). The only condition in the aggregate is that jhas to be selected in the initial set of neighbors SA. There are no extra conditions for the initial sets of neighbors S1and S2. We know that j∈ S1∩ S2. If a third point k∈ S1and k /∈ S2, but k∈ SA, we want to verify (3.6) for this third point but Kj2,k2is not known. But we know that 0 ≤Ki,j ≤1, and Ki2,k2<Ki2,j2because j∈ S2and k /∈S2. Then, Kj2,k2<Ki2,j2 Ki2,k2 so (3.5) is fulfilled and (3.4) is also fulfilled since k∈ S1, therefore (3.6) is also fulfilled. Also, condition j∈ SAcan be easily met by selecting SA=S1∪ S2 12 3.3.3 Sufficient Kto construct the NNK polytope As described in Section 2.1.2, NNK graphs construct a convex polytope around each query point xiusing the Gaussian kernel (2.2), where the only point in the intersection of all Rij regions is xi. When the decision boundary is closed, no additional points can be connected to xiand we consider the graph construction procedure completed. But there is the possibility that the decision boundary may not be completely closed, due to the hyperplanes created by the edges θij not being sufficient to enclose Rij. In this scenario, the NNK graph could continue to grow if new points were added. Figure 3.6: Number of NNK neighbors as a function of ¯ Ksuf. 20 realizations with 1000 train points per case and per dimension, where xi∈RD∼ N(0,I), except for ”D= 50, ID 50” where there are 5 subvectors with xinit i∈R10 ∼ N(0,I) and each subvector xs i=xinit i+w,w∼ N(0,0.1I). Asufficient K, which we call Ksuf, is the number of initial neighbors with which the number of connections in the NNK graph saturates. That is, when we reach Ksuf, the decision boundary is normally closed if there exist data points in all directions, and even if we increase the initial set of neighbors, the NNK graph will not grow any more. Since Ksuf is specific for each data point, we use ¯ Ksuf as the average Ksuf for a particular set of data points. In Figure 3.6, we show how ¯ Ksuf grows with the ID of the data manifold. Starting with a small Kand increasing it, we reach a point where the number of NNK neighbors converges, reaching ¯ Ksuf. The number of NNK neighbors converges at different ¯ Ksuf for ID ≈5 and ID ≈10. But for ID ≈50, ¯ Ksuf 500, i.e., ¯ Ksuf is related to ID and quantifying ¯ Ksuf can help us estimating ID. In addition, experiments show that even in a high dimensional space, if ID D,¯ Ksuf will be much lower, proportional to the ID. In general, PC c=1 Ksuf,c < Ksuf,A, i.e., we need more neighbors than the union of channel neighbors to build the NNK graph in the aggregate space. As an example, Figure 3.7 shows a specific case where SA=S1∪ S2is not sufficient to build the full NNK graph in the aggregate. Generating synthetic random data where each data point xi∈RD∼ N(0,I), ID ≈D. In Figure 3.8, we can see how the number of NNK neighbors also provides information 19 Figure 3.7: NNK graph on the aggregate using the union of sufficient sets SA=S1∪ S2. Points 1 and 4 are not selected in the subvectors but should be selected in the aggregate to build the full NNK graph. about the ID. To obtain the maximum number of NNK neighbors in each graph construction, we need a large enough K, which is related to the ID as previously described. Otherwise, we obtain a result similar to the cases of K= 50 or K= 100, where we see that the number of NNK neighbors starts to converge to K, since K < ¯ Ksuf and we need more initial neighbors to build the NNK polytope. When Kis large enough, the number of NNK neighbors increases proportionally with the ID. Figure 3.8: Number of NNK neighbors as a function of the ID of the data, for different Kin the initial search of neighbors. 20 realizations per dimension and per K, with 1000 training points xi∈RD∼ N(0,I), where ID ≈D. 20 3.3.4 Dimension significance and overall dimensionality reduction effect The activations of CNN layers are usually high dimensional due to the large number of channels in each layer. Each feature map represents certain features extracted with filtering from the layer input, after going through different nonlinear operations. However, not all dimensions contribute equally to the final output [42, 43]. Only a portion of the activations are constantly contributing to the classification, while the rest of the dimensions are noisy, or are activated in very isolated cases. Figure 3.9: Nonzero heatmaps of the feature maps in the third layer of the CNN. In the first row, all CIFAR-10 test set is used as input, while in the second row we use random examples ∼ U(0,1). Especially in the case of CNNs where the ReLU is commonly used [17], we may find many dimensions that are completely zero, and in certain cases, full zero channels independently of the input, see Figure 3.9. This leads to a direct reduction of the intrinsic dimensionality of the data representations and can be found in a wide variety of models, particularly in overparametrized or non-regularized models. Moreover, this is a special case to take into account when constructing the NNK graph: we find multiple data points that have the same feature vector (full zero) in some channels. In this case, we keep only one data point of these characteristics (it can also be the query), since the rest of the points would not provide information in new orthogonal directions. It has been demonstrated that adversarial examples have activations that are distributed more uniformly among channels, and have higher magnitude [44]. In Figure 3.9 we show that this is true, but only in the significant channels. Note that the artifacts generated on the edges are caused by zero padding. Conversely, in the rest of the dimensions, we see that the results are very similar to those obtained with normal examples: the dimensions fail to activate and undergo very little variation. Nonzero heatmaps for the different CIFAR-10 classes for both regularized and non-regularized models are provided in Appendix B. In Figure 3.10 we show how the NNK dimension (number of connected neighbors) depends on the number of zeros in the activations. One of the main reasons for having fewer NNK neighbors in some cases is that the number of common zeros reduces the dimension of the space. Also, the number of neighbors in the aggregate of channels is very close to the channel-wise case, although the crude dimension of the activation is much larger. This demonstrates that channels are highly dependent and in the overall feature space the ID is very low. 21 Figure 3.10: Average number of NNK neighbors and normalized number of zeros per CIFAR-10 class and per activation in layers 4 and 5 of the model. . 3.3.5 Complexity The NNK graph construction consists of two steps. First, finding the set Sof Knearest neighbors out of Ntraining data points. Although there exist some efficient algorithms that find an approximate solution in O(N1.14) [21], the exact solution can always be found by brute force and it requires O(N2KD) for each query. Second, solving a non-negative kernel regression (2.6) that runs in O(K3). With our proposed CW-NNK graphs method, we could alleviate complexity when constructing the graph in the full space by combining the channel results. For example, we could skip the first step in the aggregate, and use the union of the obtained KNN in the channels as the aggregate neighbor initial set SA. In the full space, the first step is O(N2KAD), and in the channel-wise case O(N2KCDCC). Since DCC=D, the complexity is lower in the channel-wise approach only if KC< KA, i.e. we use a lower K in the individual channels than in the aggregate. As described in Section 3.3.3, we should always select KCKA, since ¯ Ksuf to build the NNK graph is proportional to the ID of the data, which will be higher in the full feature space than in the lower dimensional channels. Therefore, by selecting a suitable K, we can reduce the complexity of NNK graph construction with the channel-wise approach. We also have to ensure that when selecting SAas the union of channel neighbors, |SA|is of the same order of magnitude as ¯ Ksuf for the full space or lower, thus maintaining or reducing the complexity in the second step of NNK (2.6). Also, in a practical application, (e.g., label interpolation from the neighboring nodes, which we will address in the next Chapter) using NNK graphs or related algorithms, we can still get many of the benefits of these methods without having to compute the exact solution, so that much faster approximate approaches can still be very useful. 22 3.4 Discussion We presented a channel-wise graph construction approach as an extension to NNK graphs. To the best of our knowledge, no prior work had formally studied this setting. Although encountering very high dimensional data, we can often divide the feature vectors into subvectors in a consistent and interpretable way, as is the case for the channels in convolutional layers. We studied how properties of the NNK solution in the aggregate can be inferred from the solutions in each of the channels, which leads us to a better understanding of the information relationship between channels. We also analyzed the complexity of the proposed approach, and by doing so we were able to see how we could find an approximate solution in the aggregate from the channels with a lower computational cost. We illustrated the effects of the curse of dimensionality and how it is significantly eased in real data scenarios. From the construction of NNK graphs, we showed that some polytope properties such as the required number of initial neighbors and the number of NNK neighbors are directly related to the intrinsic dimensionality of the data, which is usually much lower than the actual dimension of the vector in real data or deep representations in neural networks. Finally, with the channel-wise graph construction approach we obtain a better estimates of the ID through finding the number of neighbors. 23 Chapter 4 CW-DeepNNK generalization estimate without validation set During the training of a neural network, the goal is to minimize a loss function given a finite training dataset. One of the main challenges in this optimization is for the model to be able to generalize and perform well on unseen data. The problem is that there will come a point in the training where the model may stop generalizing and will start to learn the statistical noise of the finite training dataset, which could lead to decreasing performance on new data, even though the loss function continues to be decreased by additional training [17]. But how can we detect when this happens in order to avoid it, and save the model that generalizes better? The most common approach is to hold out part of the training set (a validation set) with which we will not train, but on which we will evaluate the performance of the model so as to obtain a generalization estimate. Then, we can perform early stopping [18], which consists in stopping the training when we detect that the generalization on the validation set does not improve after some given epochs. Finally, we keep the copy of the model in the iteration where we obtained the best generalization performance. Although these methods are very effective in practice and lead to state-of-the-art results, there are some drawbacks [19]. The choice of validation set size carries with it a trade-off: a small validation set has a large stochastic error and may introduce biases, which can result in a poor generalization estimate. On the other hand, a larger validation set yields a more robust generalization estimate but deprives the model of valuable information by reducing significantly the amount of training data. If there is scarcity of labeled data, the selection of the validation set is critical and its use would be more valuable if all the data could be used to train the model. In addition, while validation strategies can be used in practice, there are still difficulties in achieving a good understanding and interpretation of why large neural networks generalize well in practice [15]. Motivated by the previously proposed DeepNNK approach [1], we introduce a novel approach for channel-wise generalization estimation (CW-DeepNNK) that allows us to perform channel-wise early stopping effectively without the need for a validation set. This method is based on leave one out estimation using local polytope label interpolation. In addition, it can be easily integrated with an existing training setup, replacing the existing generalization estimate, e.g., validation accuracy. We propose a generalization estimate that can be decomposed into multiple estimates, in this case by convolutional channels, rather than having a single metric as in most standard methods, such as performance on a validation set. We also show that the point at which additional training can worsen generalization occurs at different stages in different channels. Thus, when detecting that generalization performance decreases in some channels it is possible to stop training some channels while continuing to train the others. 24 A comparison with other state of the art methods is carried out, showing how this channel-wise monitoring can be equally or more effective in detecting generalization in some scenarios. Finally, we discuss different options for reducing the complexity of our algorithm while maintaining a good estimate of generalization. 4.1 Related work Most successful deep learning models include some kind of regularization in their architectures to ensure a small generalization error [15]. Among them, we find data augmentation, weight decay [45], dropout [46] and batch normalization [47]. Regularization may also be implicit as in the case of early stopping. Many early stopping criteria have been proposed [18, 48, 49, 19], most of which are based on the validation set performance, usually using the loss or accuracy curve. The most used criterion is to stop training the model when the validation performance has not improved over the best one recorded for a given number of epochs, usually called patience. Other stopping conditions focus on an absolute change in performance, an average change over a given number of epochs, or the worsening of performance in consecutive epochs. An alternative is to stop training when the validation performance is under the best one recorded by a given threshold, while the model error on the training set no longer improves much [18]. But again, these are all different stopping criteria that are generally constructed around the performance curve of an independent validation set, which is the state-of-the-art generalization estimator. Other generalization estimates to perform early stopping have been proposed without the need for a validation set. Duvenaud et al. [49] proposed an interpretation of stochastic gradient descent in the variational inference framework. This motivated a generalization estimate that can be used to construct a stopping rule. It is based on estimating the marginal likelihood, by tracking the change in entropy of the posterior distribution of the network parameters at each optimization step. However, this method requires computing the Hessian diagonals, which may be impractical for large neural networks. Mahsereci et al. [19] proposed an estimate based on fast-to-compute local statistics of the computed gradient, aimed at detecting when it represents statistical noise of the finite training set, instead of an informative gradient direction. These two proposed methods for early stopping are based on gradient-related statistics, thus, they are sensitive to hyperparameter selection, e.g., learning rate, batch size or optimizer selection. In addition, they are also sensitive to neural network parameters, i.e., weights and biases, converging at very different speeds during optimization. 4.2 DeepNNK: generalization estimate using polytope interpolation DeepNNK [1] is a non parametric interpolation framework based on local polytopes obtained using NNK graphs [11] on neural network data representations. Other methods 25 such as K-NN-based interpolation can be biased if the data density is different in different directions in space. In contrast, NNK selects only relevant points for interpolation, eliminating redundant points that do not provide new (orthogonal) information. To integrate this interpolation framework with an existing neural network setup, we replace the last classification layer with the DeepNNK interpolator framework, using as input the features of the transformed space of the penultimate layer. We can continue using the loss obtained with the last layer to perform backpropagation, while the framework can be used to evaluate during training or testing. In this way, we perform label interpolation based on the relative positions of the training data in the output transformed space, instead of defining a classification boundary in the space. As previously mentioned, we do not have to set aside part of the training set to create a validation set to evaluate the model during training. Now, the input data xiis transformed by a non linear mapping hdenoting the deep neural network. We can rewrite the Gaussian kernel (2.2) as kDNN(xi,xj) = exp −kh(xi)−h(xj)k2 2σ2(4.1) Given Knearest neighbors of a sample x,S={(x1, y1),(x2, y2). . . (xK, yK)}the unbiased NNK interpolation estimate is defined as ˆη(x) = E(Y|X=x) = ˆ K X i=1 θi Pˆ K j=1 θj yi(4.2) where θare the ˆ Knon zero recomputed NNK weights obtained from the minimization of (2.6). Most of the initial Knearest neighbor weights are set to zero and we end up performing the label interpolation with the stable set of NNK neighbors. In order to evaluate the performance of the estimator, we perform the leave one out (LOO) procedure, which is unbiased and widely used [50]. Given the training data Dtrain ={(x1, y1),(x2, y2). . . (xN, yN)}, the NNK interpolation estimator for xiis based on the set containing all training points except xi, which we denote by Di train. Formally, RLOO(ˆη|Dtrain) = 1 N N X i=1 l(ˆη(xi)|Di train, yi) (4.3) where l(ˆyi, yi) is the error associated in regression or classification. Shekkizhar and Ortega [1] demonstrated that LOO performance can be a better indicator of generalization than the empirical model performance on training data. 4.2.1 CW-DeepNNK The interpolation framework just described aims at estimating generalization error with the LOO procedure. In this work, continuing with the channel-wise spirit of Chapter 3, we formulate the local polytope label interpolation in individual channels (CW-DeepNNK). 26 Instead of using the transformed data representations of the full last convolutional layer hlast(x), which consists of the aggregation of outputs of Cconvolutional channels, we suggest dividing the feature space into channels: hlast(xi) =      h1 last(xi) h2 last(xi) . . . hC last(xi)      ∈RDlast (4.4) which are well defined and have a better interpretability on their own. Then, the first step for the CW-DeepNNK LOO procedure is to perform the K-NN search in each channel, obtaining S1,S2,...,SCfor each train data point xi. The second step is to use the subvectors hc last(xi) to construct the similarity matrix KScwith the Gaussian kernel (4.1), and solve the NNK regression (2.6) obtaining θScin each channel c. Then, we perform the NNK interpolation (4.2) per instance and per channel. Finally, we compute the LOO estimation (4.3) per channel, obtaining the CW-DeepNNK label interpolation errors R1 LOO,R2 LOO,...,RC LOO. By computing the CW-DeepNNK procedure at each training epoch we obtain a CWDeepNNK label interpolation error curve for each channel. Using these curves to monitor the generalization of the model during training, we propose a novel channel-wise early stopping method, which does not require a validation set and the stopping is performed in stages. Starting from the standard patience criterion, we monitor the generalization performance in the last convolutional layer channels and we use a patience parameter in each channel. When a channel stops generalizing we freeze the model parameters of the channel and stop training it. The rest of the model continues learning until each of the channels stops generalizing, where we consider that we have reached the optimal point and the overall generalization of the model no longer improves. Finally, we save the model parameters where the last minimum generalization error is detected. 4.3 Experiments In this section, we focus on binary classification using 2 classes of CIFAR-10: “plane” and “ship”. We use a CNN architecture of 4 conv layers with 5 depth channels, ReLU and max-pooling and a last fully connected layer. Details of the model architecture and implementation are provided in Appendix A. We compare the model performance with the DeepNNK interpolation on train data, using the data representations from the full last convolutional layer or the individual channels. Some channels learn features more valuable than others for the classification task, and we study how this can be detected based on the NNK polytope local geometry and activation patterns. We also analyze the behaviour of the proposed generalization estimate when we do and do not apply explicit regularization to the model. Additionally, we compare the NNK-based generalization estimates with the standard method [18] to perform early stopping and we discuss their complexity. 27 4.3.1 Interpretation of channel-wise generalization estimates A convolutional layer is composed of various channels that are outputs of different filtering operations. Each channel defines a feature subspace where we should be able to quantify how useful the information from that channel is for the classification task, and have a better interpretation of the captured features in each channel. We can assume that each filter captures different features, although they are not completely independent between channels. Figure 4.1: DeepNNK, CW-DeepNNK and model error on the train set during training with no regularization. Figure 4.1 shows a comparison between model error on training data, DeepNNK and CW-DeepNNK label interpolation error with LOO estimation. In this case, the model is trained with no regularization. In the standard case using all channels (full layer), the error gap between the model on train data and LOO DeepNNK increases with the epochs, indicating that the generalization performance is worsening and the model starts to overfit to the train data. We can see how CW-DeepNNK has a much better performance than the model when only a single channel is activated. Note that an error of 0.5 in a binary classification is as bad as doing random classification. We also observe how the interpolation error in the channels soon reaches a minimum, and then the classification error increases again. This minimum may indicate the optimal point of generalization in each channel, from which the learned features begin to fit the training data noise. Although the last fully connected layer of the model is trained to use the full combination of features from all channels, we wanted to see what happens if the model has to perform classification when relying only on partial information. We demonstrate how our method is able to perform much better in each independent channel subspace, and the model is not capable of performing at a decent level when some feature channels are 28 Chapter 6 Conclusions and Future Work The first goal of this project was to tackle the high dimensional graph construction problem while having a better understanding of the intrinsic dimensionality of the data. We achieved this with a channel-wise approach, as an extension of the existing NNK graphs method. We performed an in-depth study of the benefits of this new method and the insights we can extract about the dimensionality of the data from the local geometry of the polytope and the relationship between channels. Secondly, we employed the proposed graph construction method to derive a new generalization estimator in convolutional neural networks, based on channel-wise local polytope interpolation. Then we used it to detect the best generalization performance using only train data, and stop the training before converging to zero train error. We shown how this estimator can replace the standard generalization estimator (i.e. validation set performance) to perform early stopping and thus prevent overfitting. This method may be the preferred in cases of small datasets or small size neural networks where test performance is crucial. Future work should focus on developing new efficient implementations of this generalization estimator, taking full advantage of the information between consecutive epochs and between channels, since on both axes we have detected a great opportunity to reduce complexity while maintaining a good generalization estimate. This could lead our method to standardize in other scenarios of different nature. Future research could also be in the direction of neural network pruning based on the CW-DeepNNK interpolation error, since we have seen that in certain channels we have practically no useful information to perform the interpolation, and those channels could be pruned, resulting in a more compact network with less computational cost. Another line of research could involve a progressive early stopping of the full model, achieving a significant saving of gradient computation and backpropagation throughout the training. It would be interesting to investigate this new approach of improving generalization in stages, and the hypothesis that the low-level features learned in the first layers are very general and are learned quickly in the first few epochs of training, while the higher-level features learned in the deeper layers that are more specific to the training set reach their optimal point later. Obviously, all weights continue to update as a whole throughout training, but excessive training can overfit each group of weights to the training data without realizing it. By performing this progressive early stopping of the full model we could stop at the point of highest generalization each channel of each layer, perhaps thus avoiding the overfitting of the model to the training data in a more dedicated way and with a much better interpretation than the standard black box approach. Finally, the work reported in this thesis reflects the main contributions of a scientific publication under progress that will be submitted to a signal processing conference. 35 Bibliography [1] Sarath Shekkizhar and Antonio Ortega. Deepnnk: Explaining deep models and their generalization using polytope interpolation. arXiv preprint arXiv:2007.10505, 2020. [2] Antonio Ortega, Pascal Frossard, Jelena Kovaˇcevi´c, Jos´e MF Moura, and Pierre Vandergheynst. Graph signal processing: Overview, challenges, and applications. Proceedings of the IEEE, 106(5):808–828, 2018. [3] Davide Bacciu, Federico Errica, Alessio Micheli, and Marco Podda. A gentle introduction to deep learning for graphs. Neural Networks, 2020. [4] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, 20(1):61–80, 2008. [5] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907, 2016. [6] Vincent Gripon, Antonio Ortega, and Benjamin Girault. An inside look at deep neural networks using graph signal processing. In 2018 Information Theory and Applications Workshop (ITA), pages 1–9. IEEE, 2018. [7] Carlos Lassance, Vincent Gripon, and Antonio Ortega. Representing deep neural networks latent space geometries with graphs. Algorithms, 14(2):39, 2021. [8] Carlos Lassance, Myriam Bontonou, Ghouthi Boukli Hacene, Vincent Gripon, Jian Tang, and Antonio Ortega. Deep geometric knowledge distillation with graphs. In ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 8484–8488. IEEE, 2020. [9] Carlos Lassance, Vincent Gripon, and Antonio Ortega. Laplacian networks: Bounding indicator function smoothness for neural networks robustness. APSIPA Transactions on Signal and Information Processing, 10, 2021. [10] Sam T Roweis and Lawrence K Saul. Nonlinear dimensionality reduction by locally linear embedding. science, 290(5500):2323–2326, 2000. [11] Sarath Shekkizhar and Antonio Ortega. Graph construction from data using non negative kernel regression (nnk graphs). arXiv preprint arXiv:1910.09383, 2019. [12] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778, 2016. [13] Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. arXiv preprint arXiv:1605.07146, 2016. [14] Mingxing Tan and Quoc Le. Efficientnet: Rethinking model scaling for convolutional neural networks. In International Conference on Machine Learning, pages 6105–6114. PMLR, 2019. 36 [15] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint arXiv:1611.03530, 2016. [16] Benjamin Recht, Rebecca Roelofs, Ludwig Schmidt, and Vaishaal Shankar. Do cifar10 classifiers generalize to cifar-10? arXiv preprint arXiv:1806.00451, 2018. [17] Ian Goodfellow, Yoshua Bengio, Aaron Courville, and Yoshua Bengio. Deep learning. MIT press Cambridge, 2016. [18] Lutz Prechelt. Early stopping-but when? In Neural Networks: Tricks of the trade, pages 55–69. Springer, 1998. [19] Maren Mahsereci, Lukas Balles, Christoph Lassner, and Philipp Hennig. Early stopping without a validation set. arXiv preprint arXiv:1703.09580, 2017. [20] Antonio Ortega. Introduction to Graph Signal Processing. Cambridge University Press, 2021. [21] Wei Dong, Charikar Moses, and Kai Li. Efficient k-nearest neighbor graph construction for generic similarity measures. In Proceedings of the 20th international conference on World wide web, pages 577–586, 2011. [22] V´aclav Chv´atal and PL Hammer. Aggregations of inequalities. Studies in Integer Programming, Annals of Discrete Mathematics, 1:145–162, 1977. [23] George H Chen, Devavrat Shah, et al. Explaining the success of nearest neighbor methods in prediction. Now Publishers, 2018. [24] Ashish Kapoor, Hyungil Ahn, Yuan Qi, and Rosalind Picard. Hyperparameter and kernel learning for graph based semi-supervised classification. Advances in neural information processing systems, 18:627–634, 2005. [25] Masayuki Karasuyama and Hiroshi Mamitsuka. Adaptive edge weighting for graphbased learning algorithms. Machine Learning, 106(2):307–335, 2017. [26] Vassilis Kalofolias and Nathana¨el Perraudin. Large scale graph learning from smooth signals. arXiv preprint arXiv:1710.05654, 2017. [27] Vassilis Kalofolias. How to learn a graph from smooth signals. In Artificial Intelligence and Statistics, pages 920–929. PMLR, 2016. [28] Nachman Aronszajn. Theory of reproducing kernels. Transactions of the American mathematical society, 68(3):337–404, 1950. [29] Saad Albawi, Tareq Abed Mohammed, and Saad Al-Zawi. Understanding of a convolutional neural network. In 2017 International Conference on Engineering and Technology (ICET), pages 1–6. Ieee, 2017. [30] Richard E Bellman. Adaptive control processes: a guided tour. Princeton university press, 2015. 37 [31] Charu C Aggarwal, Alexander Hinneburg, and Daniel A Keim. On the surprising behavior of distance metrics in high dimensional space. In International conference on database theory, pages 420–434. Springer, 2001. [32] Stefano Recanatesi, Matthew Farrell, Madhu Advani, Timothy Moore, Guillaume Lajoie, and Eric Shea-Brown. Dimensionality compression and expansion in deep neural networks. arXiv preprint arXiv:1906.00443, 2019. [33] Alessio Ansuini, Alessandro Laio, Jakob H Macke, and Davide Zoccolan. Intrinsic dimension of data representations in deep neural networks. arXiv preprint arXiv:1905.12784, 2019. [34] Ryumei Nakada and Masaaki Imaizumi. Adaptive approximation and estimation of deep neural network with intrinsic dimensionality. arXiv preprint arXiv:1907.02177, 2019. [35] Matthias Hein and Markus Maier. Manifold denoising. In NIPS, volume 19, pages 561–568, 2006. [36] Jose A Costa and Alfred O Hero. Determining intrinsic dimension and entropy of high-dimensional shape spaces. In Statistics and Analysis of Shapes, pages 231–252. Springer, 2006. [37] Elizaveta Levina and Peter J Bickel. Maximum likelihood estimation of intrinsic dimension. In Advances in neural information processing systems, pages 777–784, 2005. [38] Claudio Ceruti, Simone Bassis, Alessandro Rozza, Gabriele Lombardi, Elena Casiraghi, and Paola Campadelli. Danco: An intrinsic dimensionality estimator exploiting angle and norm concentration. Pattern recognition, 47(8):2569–2581, 2014. [39] Francesco Camastra and Antonino Staiano. Intrinsic dimension estimation: Advances and open problems. Information Sciences, 328:26–41, 2016. [40] Elena Facco, Maria d’Errico, Alex Rodriguez, and Alessandro Laio. Estimating the intrinsic dimension of datasets by a minimal neighborhood information. Scientific reports, 7(1):1–8, 2017. [41] Kevin Beyer, Jonathan Goldstein, Raghu Ramakrishnan, and Uri Shaft. When is “nearest neighbor” meaningful? In International conference on database theory, pages 217–235. Springer, 1999. [42] Yann LeCun, John S Denker, and Sara A Solla. Optimal brain damage. In Advances in neural information processing systems, pages 598–605, 1990. [43] Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. arXiv preprint arXiv:1803.03635, 2018. [44] Yang Bai, Yuyuan Zeng, Yong Jiang, Shu-Tao Xia, Xingjun Ma, and Yisen Wang. Improving adversarial robustness via channel-wise activation suppressing. arXiv preprint arXiv:2103.08307, 2021. 38 [45] Anders Krogh and John A Hertz. A simple weight decay can improve generalization. In Advances in neural information processing systems, pages 950–957, 1992. [46] Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. The journal of machine learning research, 15(1):1929–1958, 2014. [47] Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference on machine learning, pages 448–456. PMLR, 2015. [48] Justin K Terry, Mario Jayakumar, and Kusal De Alwis. Statistically significant stopping of neural network training. arXiv preprint arXiv:2103.01205, 2021. [49] David Duvenaud, Dougal Maclaurin, and Ryan Adams. Early stopping as nonparametric variational inference. In Artificial Intelligence and Statistics, pages 1070–1077. PMLR, 2016. [50] Andr´e Elisseeff, Massimiliano Pontil, et al. Leave-one-out error and stability of learning algorithms with applications. NATO science series sub series iii computer and systems sciences, 190:111–130, 2003. [51] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In Proceedings of the IEEE international conference on computer vision, pages 1026–1034, 2015. [52] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014. 39 Appendix A Experiment Details A.1 Section 3.3 model Group name Operation Number of filters Filter size Stride size Padding size Output size Input image – – – – 32 ×32 ×3 Layer 0 Convolution ReLU 16 – 3×3×3 – 1×1 – 1×1 – 32 ×32 ×16 32 ×32 ×16 Layer 1 Convolution ReLU Max pooling 16 – 1 3×3×16 – 2×2 1×1 – 2×2 1×1 – 0 32 ×32 ×16 32 ×32 ×16 16 ×16 ×16 Layer 2 Convolution ReLU 16 – 3×3×16 – 1×1 – 1×1 – 16 ×16 ×16 16 ×16 ×16 Layer 3 Convolution ReLU Max pooling 16 – 1 3×3×16 – 2×2 1×1 – 2×2 1×1 – 0 16 ×16 ×16 16 ×16 ×16 8×8×16 Layer 4 Convolution ReLU 16 – 3×3×16 – 1×1 – 1×1 – 8×8×16 8×8×16 Layer 5 Convolution ReLU Max pooling 16 – 1 3×3×16 – 2×2 1×1 – 2×2 1×1 – 0 8×8×16 8×8×16 4×4×16 Output Fully connected Softmax – – – – – – – – No. classes No. classes Table A.1: CNN architecture used in Section 3.3. 40 A.2 Section 4.3 model Group name Operation Number of filters Filter size Stride size Padding size Output size Input image – – – – 32 ×32 ×3 Layer 0 Convolution ReLU 5 – 5×5×3 – 1×1 – 0 – 28 ×28 ×5 28 ×28 ×5 Layer 1 Convolution ReLU Max pooling 5 – 1 5×5×5 – 2×2 1×1 – 2×2 0 – 0 24 ×24 ×5 24 ×24 ×5 12 ×12 ×5 Layer 2 Convolution ReLU 5 – 5×5×5 – 1×1 – 0 – 8×8×5 8×8×5 Layer 3 Convolution ReLU Max pooling 5 – 1 3×3×5 – 2×2 1×1 – 2×2 0 – 0 6×6×5 6×6×5 3×3×5 Output Fully connected Softmax – – – – – – – – No. classes No. classes Table A.2: CNN architecture used in Section 4.3. A.3 Hyperparameters Parameters Description Data split 20% of the train set is held out for validation (only when not using NNK interpolation framework) Weight initialization He uniform [51] Regularization Dropout with rate = 0.2 in each layer (if non-regularized model not stated in experiment) Loss Cross-entropy loss Batch size 50 Epochs 20 (if not stated in experiment) Learning rate 0.001 Optimizer Adam [52] with β1= 0.9, β2= 0.999 Table A.3: Hyperparameters for thesis experiments, using CIFAR-10 dataset. 41 Appendix B Nonzero heatmaps of CNN activations This appendix contains a graphical representation of the behavior of convolutional layers using nonzero heatmaps of their feature maps, both for a regularized model and a nonregularized model, using the same weight initialization and trained for the same epochs as detailed in Appendix A.1. In the regularized case, there is a large proportion of zero dimensions in the activations. But we also see that as expected, the patterns of active dimensions are different between classes. In the non-regularized case, we encounter an extreme binary behaviour: regardless of the input class, certain channels are always active, i.e. non-negative due to ReLU, while other channels are completely deactivated at zero. Figure B.1: Nonzero heatmaps of layer 2 of model A.1 using regularization during training, for the different CIFAR-10 classes. 42 Figure B.2: Nonzero heatmaps of layer 2 of model A.1 using no regularization during training, for the different CIFAR-10 classes. 43