# Sifting out the features by pruning:
Are convolutional networks the winning lottery ticket of fully connected ones?

Franco Pellegrini
Laboratoire de Physique de l’École normale supérieure, ENS, Université PSL,
CNRS, Sorbonne Université, Université de Paris — F-75005 Paris, France
<EMAIL_ADDRESS>Giulio Biroli
Laboratoire de Physique de l’École normale supérieure, ENS, Université PSL,
CNRS, Sorbonne Université, Université de Paris — F-75005 Paris, France
<EMAIL_ADDRESS>
###### Abstract

Pruning methods can considerably reduce the size of artificial neural networks
without harming their performance. In some cases, they can even uncover sub-
networks that, when trained in isolation, match or surpass the test accuracy
of their dense counterparts. Here we study the inductive bias that pruning
imprints in such “winning lottery tickets”. Focusing on visual tasks, we
analyze the architecture resulting from iterative magnitude pruning of a
simple fully connected network (FCN). We show that the surviving node
connectivity is local in input space, and organized in patterns reminiscent of
the ones found in convolutional networks (CNN). We investigate the role played
by data and tasks in shaping the architecture of pruned sub-networks. Our
results show that the winning lottery tickets of FCNs display the key features
of CNNs. The ability of such automatic network-simplifying procedure to
recover the key features “hand-crafted” in the design of CNNs suggests
interesting applications to other datasets and tasks, in order to discover new
and efficient architectural inductive biases.

##  1 Introduction

In the last decade deep and over-parametrized neural networks achieved
breakthroughs in a variety of contexts [1, 2, 3, 4, 5]. To keep pushing the
boundaries of their capacity, these networks have grown in size to over
billions of parameters [6]. Network pruning approaches have recently received
renewed attention as effective procedures to counterbalance this growth by
reducing networks size without harming their performance. Several pruning
methods have been introduced [7]: they are all based on the idea of cutting
weights from a trained, or partially trained, network in order to obtain a
sparse sub-network that works at a comparable level of accuracy than the
original one. For applications, pruning is very efficient in improving storage
and computational cost. On the theoretical side, it led to the discovery that
within a randomly-initialized network one can find a sub-network, a winning
lottery ticket, that when trained in isolation can match the test accuracy of
the original network after training for at most the same number of iterations
[8].

The introduction of better network architectures, with geometries more suited
to specific tasks, and which result in faster training and overall better
generalizing properties can also be seen from a similar perspective. For
instance, Convolutional Neural Networks [1, 2, 9, 10, 11] (CNN), which are
very efficient for visual tasks, can be embedded in the Fully Connected
Network (FCN) class. CNNs can therefore be interpreted as sparse and smaller
FCNs trained from very specific initial conditions very well adapted to the
task [12]. Also in this case the size is drastically reduced (with respect to
the FCN counterpart). The difference with pruning is that the main
characteristics of CNNs—local connectivity and weight sharing—do not come from
an automatic procedure but are “hand-designed” features introduced starting
from analogies with the virtual cortex [13, 14], studies of the invariant
properties of natural images [15], and engineering improvements [9]. Pruning
instead proceeds in an agnostic way in order to find smaller and efficient
architectures; it takes advantage of properties which are imprinted in the
network through training and which result from the interplay of data, task and
optimization algorithm. Pruning induces an inductive bias customized to the
learning task at hand, which leads to a network with better training and
generalization properties compared to one of similar size trained from
scratch. It has been actually shown that the same winning lottery ticket
generalizes across training conditions and similar datasets [16]. This implies
that the bias induced by pruning is sufficiently generic to transfer the
pruned networks within the same data domain.

Here, we characterize the nature of such inductive bias in the case of dense
networks trained to classify natural images, and reveal that the winning
lottery tickets of FCNs display the key features of CNNs. We apply iterative
magnitude pruning (IMP) [8] on FCNs trained on a low resolution version of
ImageNet [17]. We show that the sub-network obtained by IMP is characterized
by local connectivity, especially in the first hidden layer, and masks leading
to local features with patterns very reminiscent of the ones of trained CNNs
[18]. Deeper layers are made up of these local features with larger receptive
fields hinting at the hierarchical structure found in CNNs. We study how the
data and the task affect these properties. We show a crossover from a large
dataset regime (large signal-to-noise ratio), where the inductive CNN-like
bias is present, to a small dataset regime in which pruning loses performance
and concomitantly the properties described above disappear. We show that a
similar crossover takes place when going from a meaningful task to one with
low semantic value.

##  2 Related works

Several recent works have studied pruning from the perspective of the lottery
ticket hypothesis [8]: some investigated more general weight reinitializations
[19], whereas others actually questioned its validity on larger nets [20, 21].
Later, Refs. [22, 23] showed that in order to obtain good results for complex
networks, datasets, and tasks it is important to modify the rewinding time
compared to the initial formulation of the hypothesis. Other studies concerned
hyperparameters modifications [24, 25], and concentrated on the
transferability [16, 26] of the pruned networks. To the best of our knowledge,
our work is the first to analyze the internal structure of winning tickets in
order to highlight the inductive bias induced by pruning and relate it to
architectural properties.

Perhaps the most related work is Ref. [27], which addresses the issue of
learning CNN-like inductive bias from data and through training. It shows that
training using a modified $\ell_{1}$ regularization is a way to induce local
masks for visual tasks. This is similar to our results on pruning: enforcing
sparsity during training allows to recover locality. Ref. [12] studies the
role of CNN-like inductive biases by embedding convolutional architectures
within the general FCN class. It shows that enforcing CNN-like features in an
FCN can improve performance even beyond that of its CNN counterpart. Finally,
a manuscript [28] that appeared after the completion of our work shows that by
considering a particular multilayer perceptron architecture, called MLP-mixer,
some of the CNN features can be learned from scratch using a large training
dataset.

##  3 Method, observables and notation

#### Data, networks, and training procedure

Throughout this work our reference dataset, referred to as ImageNet32,
consists of the almost 1.3M images classified in 1000 categories of the
ILSVRC-12 image classification challenge [29], cropped and scaled down to
$32\times 32$ resolution as detailed in [17]. Considering the 3 color channels
(RGB) the input size is $n_{0}=3072$ (we index the input as layer 0). The
validation test contains 10k images. To keep the analysis simple, in the
following we consider a FCN having 3 hidden layers of equal size
$n_{1}=n_{2}=n_{3}=1024$. Generalizations to more general FCN architectures
(more layers and different layer sizes) are presented in the SM A.2. Note that
the aim of our work is to characterize the sub-networks induced by pruning in
the simplest setup which allows a thorough analysis. For this reason, we use a
small and fixed input size, which is useful to have a manageable size for the
FCN, and we do not use any form of augmentation in order to avoid biases
towards translational invariant features (the choice of a large dataset is
important in this sense to obtain good statistics, as shown in Sec. 5). We
apply batch normalization [30] and we use rectified linear unit (ReLU)
nonlinearities for each layer. We denote $w^{l+1}_{ij}$ the weights between
node $i$ of layer $l$ and node $j$ of layer $l+1$. Weights are initialized
from a normal distribution $w^{l+1}\sim\mathcal{N}(0,2/(n_{l}+n_{l+1}))$ [31].
Each node also has a bias $b^{l}_{i}$, initialized at 0. The size of the
output layer equals the number of categories ($n_{4}=1000$ in this first
experiment, 10 in Section 6), which are converted to probabilities to compute
the cross-entropy loss. The reported accuracy is the ratio of correct, most
probable, labels. We train on mini-batches of 1000 images, and minimize
through stochastic gradient descent with learning rate $\alpha=0.1$. Each
training run corresponds to $10^{5}$ steps (around 78 epochs): while this is
not sufficient to fit the training set, it is effective in identifying a
winning lottery ticket [32]. We checked that our results are robust while
changing the optimization procedure, see the SM A.1.

#### Iterative Magnitude Pruning

We prune iteratively the 3 hidden layers. Each time, we remove $p=30\%$ of
previously unpruned weights with the lowest absolute value at the end of
training, per layer, as originally described in [8]. When analyzing the pruned
networks, we denote $u$ the ratio of unpruned weights per layer: after $n$
iterations $u=(1-p)^{n}$. As suggested in [22], we rewind the weights after
each training not to the initial values, but to the ones obtained after 1000
steps of optimization in the first run. Instead of a winning lottery ticket
the resulting network has been called a matching ticket [22] (we have verified
that the main result holds when rewinding to 0, see SM A.3). We iterate the
training and pruning until less than 20% of the nodes in any layer retain any
connection to the previous layer, i.e. until more than 80% of the nodes have
been completely pruned away. More information on the pruning parameters,
including total training time, is presented in SM A.3.

#### Observables

In order to analyze the structure of the subnetwork induced by pruning we
focus on the following observables:

  * •

Masks: for each layer, we define masks by assigning 0 to pruned weights, and 1
to all the others. We indicate with $m^{l}_{ij}$ the mask formed by the
unpruned weights $w^{l}_{ij}$.

  * •

Node connectivity: for each node $j$ in layer $l$ we define the input
connectivity $C^{{\rm in},l}_{j}=\sum_{i}m^{l}_{ij}$ as the number of input
unpruned nodes, and $C^{{\rm out},l}_{j}=\sum_{i}m^{l+1}_{ji}$ the output
connectivity.

  * •

Local distances: in order to asses the locality of the masks, we count the
number of pixels in a given relative position, ${\bf d}$, that are connected
to the same hidden node, as shown schematically in Fig. 2a. More precisely:
two inputs $i$ and $i^{\prime}$ are connected through node $j$ if
$m^{1}_{ij}m^{1}_{i^{\prime}j}=1$. For such inputs we define the displacement
${\bf d}_{ii^{\prime}}$: if input index $i$ identifies a pixel of spatial
position $(x,y)$ and $i^{\prime}$ corresponds to position
$(x^{\prime},y^{\prime})$, we define their displacement ${\bf
d}_{ii^{\prime}}\equiv(x^{\prime}-x,y^{\prime}-y)$. The histogram of connected
pixels at a given displacement is denoted $S({\bf
d})=\sum_{j}\sum_{i,i^{\prime}|{\bf d}_{ii^{\prime}}={\bf
d}}m^{1}_{ij}m^{1}_{i^{\prime}j}$. We consider both the sum over pixels
belonging to the same color channel ($S^{\rm sc}$) and over different color
channels ($S^{\rm dc}$).

##  4 Pruning sifts out local features and recovers CNN-like masks

Figure 1:  a: Highest validation accuracy at different percentage of unpruned
weights. Averages and standard deviations over 4 independent IMP runs. b:
Histograms of the number of $C^{{\rm in},1}$ for three configurations at
different sparsities. The triangles represent the average connections $n_{0}u$
at each sparsity. c: Accuracy with respect to the full network for networks
with a varying number of nodes removed, in increasing or decreasing order of
$C^{{\rm in},1}_{j}$.  Figure 2:  a: Sketch of the displacement and
connectivity considered when computing $S({\bf d})$. b: $S^{\rm sc}$ (top) and
$S^{\rm dc}$ (bottom) for each sparsity considered (columns). Relative
positions are shown with respect to the center of each image (${\bf d}=0$) and
the color scale of each plot goes from 0 to its maximum. For $S^{\rm sc}$, the
single point at ${\bf d}=0$ is removed as it is trivially always connected. c:
Same as b, but for the second hidden layer at the higher sparsity.

Fig. 1a shows the highest (early stop) validation accuracy as a function of
$u$ throughout the IMP procedure. As expected [33], pruning allows to find
sub-networks of considerably smaller sizes that work as well as the original
ones. Actually, as shown in Fig. 1a, IMP leads to a strong improvement in the
accuracy which goes from less than 9% to more than 12% when 99% of the weights
are pruned111The overall accuracy is low compared to the state of the art.
This is due to the fact that we are focusing on a simple (hence fully
analyzable) setup and by choice we avoid improvements that could lead to
biases in the results. Yet, considering the low resolution, lack of
augmentation, and simplicity of the network for a notoriously complex dataset,
the improvement over the random $10^{-3}$ is a clear signal of learning. The
top-5 accuracy is around $26\%$..

#### The pruning-induced masks are local

To characterize these pruned network, we concentrate on 3 sparsity values
close to the maximum accuracy reached by IMP: $u=4\%$, 1%, and 0.3%, as
circled in Fig. 1a. We start by showing the histograms of $C^{{\rm in},1}$,
i.e. the input connectivity per node of the first hidden layer. For a random
pruning, this would be binomially distributed around the value $n_{0}u$, i.e.
123, 31, and 10 respectively for the sparsities considered. Fig. 1b shows that
the distributions obtained after pruning instead have long positive tails,
representing a population of nodes that preserve a large number of unpruned
input weights. Since IMP should preserve “important” connections, it is
interesting to check whether these nodes represent meaningful features that
have been sifted out by the procedure. To this end, we consider the relative
accuracy of the final network when either the nodes with the largest or with
the smallest $C^{{\rm in},1}$ have been completely removed (i.e. we set
$m^{1}_{ik}=0$ for those nodes $k$, without any further training). As shown in
Fig. 1c, the accuracy as a function of number of removed weights drops much
more quickly when removing the highly connected nodes, thus confirming their
relevance.

In order to investigate the emerging local structure of the unpruned weights,
we consider the number of connected pixels in a given relative position
$S({\bf d})$. A 2D map for any possible displacement ${\bf d}$ is shown in
Fig. 2b, for the 3 sparsities considered and for either same color or
different color channels. Remarkably, we find that inputs connected to the
same node are locally close, i.e. their distance is small, both within and
between color channels. Note that the same 2D maps for the unpruned layer or
pruned layers with random connections, are very different and non-local as
shown in the SM B. We also find that straight horizontal and vertical relative
displacements are slightly more likely. As the pruning progresses, the
localization becomes stronger and the anisotropy more apparent. The same 2D
maps are shown by only selecting inputs connected to nodes with a given
connectivity in the SM B.1. Our results show that the locality of the masks
holds for all nodes except the ones with the smallest values of $C^{{\rm
in},1}$. For the larger masks the effect is truly remarkable given their large
number of unpruned weights. The set of results discussed above unveils one key
feature of the matching (and winning) lottery ticket of FCNs: they display
local masks that emerge by pruning.

Figure 3:  a: Masks of the 30 nodes with largest $C^{{\rm in},1}_{j}$ for the
best IMP iteration. Binary masks are directly converted to RGB intensities. b:
Masks of 9 sample nodes around half in the $C^{{\rm in},1}_{j}$ ranking
(having 20 connections each). Same iteration and representation as panel a. c:
For a hand-picked selection of the most connected nodes (columns), the top row
reports the mask and the second row represent the masked weights
$w^{1}_{ij}m^{1}_{ij}$ normalized from minimum to maximum and converted to
RGB. The last 3 rows represent the images with highest activation for that
specific node.

#### The local features are CNN-like

We now concentrate on the nodes with the largest $C^{{\rm in},1}_{j}$, which
have been found to be most relevant, and focus on the spatial structure of the
associated masks. Fig. 3a shows the masks of the 30 most connected nodes for
the best IMP iteration ($u\simeq 1\%$): they all present well localized
distributions, either in a single location, symmetric with respect to the
vertical axis, or sometimes around the edges of the images. Several masks also
retain the same pixels through multiple color channels, often with a well
defined pattern (e.g. 2 channels out of 3). Moreover, many of the masks show a
specific preference for vertical and horizontal directions, in line with the
previously observed anisotropy, with some consisting of parallel lines
separated by one or two pixels (the effect is even more pronounced for
stronger pruning, see SM B.2, where we also show a larger sample of masks). A
video of the evolution of first layer masks is linked in SM E. Masks with a
lower number of connections, e.g. the ones positioned around the half of the
$C^{{\rm in},1}_{j}$ ranking, do not show such well defined structures, as
shown in Fig. 3b. In Fig. 3c we select a few nodes within the top 5% most
connected ones to highlight their specific structure: vertical lines,
horizontal lines, oblique lines and complementary patches of color. To clarify
the features selected by these nodes, we show not only the masks, but also the
masks multiplied by the final weights and the 3 images in the validation with
the highest activations over these nodes. The weights highlight further
structure in the localized patches, with alternating positive and negative
weights perpendicular to the preferential direction for long masks, or between
different patches. These are very reminiscent of Gabor filters [34], and very
similar to CNN masks, which respond preferentially to local high contrast
details, e.g. edges in a specific direction or color patches [18]. Moreover,
very comparable filters can be seen at different locations, showing the
emergence of partial translational invariance in the local features even
without data augmentation222Note that images in the training set have a bias
for structure in the center and at the boundary, a characteristic that emerges
also from pruning: features tend to have more connections towards the center
and edges of the image, as shown in SM B.. Lastly, the example images unveil
the response of these nodes also to local features not directly related to the
final classification task. This directly relates to the good transfer
properties of the subnetworks corresponding to the winning tickets [16, 26].
Further experiments highlighting the structure of the masks are presented in
SM D.2, where the images are rotated, in SM D.3, where higher resolution
images are used as input, and in SM D.4, where we restore translational
invariance by considering all possible image translations.

To continue the parallel with CNNs, we now focus on the second hidden layer.
In this case, for a given second layer node $j$, we define the associated
effective mask as $\mu_{ij}=\theta(\sum_{k}m^{1}_{ik}m^{2}_{kj}-1/2)$
($\theta$ being the step function), which equals 1 only if pixel $i$ is
connected to any first hidden layer node connected to $j$, and 0 otherwise. As
done for the first hidden layer, we asses the locality of these masks via the
local displacements, ${\bf d}_{i,i^{\prime}}$, of the input nodes connected to
the same mask. We show the 2D map of these displacements, $S({\bf d})$, in
Fig. 2c for same and different channels for pruning $u=0.3\%$. Since the
network is just 3 layers deep, and the receptive fields are already fairly
large in the first layer, one does not expect the second layer nodes to be
extremely localized. Yet, we find once again fairly local masks which favor
horizontal and vertical directions, thus showing that pruning induces locality
also beyond the first hidden layer. Masks from this layer, and some details on
their composition, are further analyzed in SM B.2.

##  5 The number of data controls pruning performance

Figure 4:  a: Gain in best validation accuracy (difference from the value
corresponding to the unpruned network) as a function of $u$ for training on
different percentages of the original dataset. The lines are averages of 4
independent runs, with the shaded area representing one standard deviation.
The dashed line marks the iteration at $u\simeq 0.5\%$ used in panels c and d.
b: Largest gain in validation accuracy during the IMP procedure for different
dataset sizes (percentage of the whole dataset). c: Histogram of $C^{{\rm
in},1}$ for different dataset sizes (see label at the bottom) at the iteration
$u\simeq 0.5\%$. The dashed lines represent the theoretical binomial
distribution for random pruning. d: $S^{\rm sc}({\bf d})$ for different
dataset sizes at the iteration $u\simeq 0.5\%$. Normalization and color map as
show in Fig. 2.

We now study to what extent the effects found in the previous section depend
on the properties of the dataset, in particular in the following we focus on
the role of the number of data used to train the network. We repeat the
training and the IMP with datasets of progressively smaller size, down to 2%
of the original. While this may seem like an extreme reduction of the dataset,
even just 5% of the data is actually larger than commonly used datasets such
as CIFAR-10/100. What interests us here is the gain in accuracy due to the
IMP, i.e. how much pruning leads to an increase of performance for a given
number of data333Of course, the best validation accuracy decreases as we
decrease the dataset size (to just around 2% for 5% of the data).. In Fig. 4a
we show the difference in accuracy with respect to the value obtained for the
unpruned network during the IMP procedure. When decreasing the size of the
dataset, the benefit of pruning diminishes, until no improvement at all is
visible for the smallest datasets, see panel b, showing the maxima as a
function of the dataset size. Decreasing the number of data used to train the
network also drastically affects the connectivity and locality of the
subnetworks found by pruning. In order to present this result we focus for
each dataset size on an iteration close to the maximum of all curves of panel
a, around $u=0.5\%$. Panels c show that decreasing the dataset size the
connectivity distribution becomes essentially identical to the one
corresponding to pruning weights at random independently of their magnitude
(dashed line). Concomitantly, masks become more and more non-local, as shown
in panels d (note that low connected nodes are affected earlier, see SM B.1).

Our results show that the dataset size clearly plays a major role for pruning.
Our interpretation is that by decreasing the number of data one decreases the
signal to noise ratio, hence effectively increasing random idiosyncratic
fluctuations in the weights. When such fluctuations become of the same order
of magnitude as the ones of the good subnetworks embedded in the original
dense one, it becomes impossible to unveil the matching lottery ticket by
pruning. In consequence, in this regime the subnetworks obtained by IMP are
random, featureless and do not display any local feature. More results on the
disruption of local features due to small dataset sizes are shown in SM B.2.

##  6 The role of the task: the importance of being meaningful

Figure 5:  a: 10 sample images for each of the 10 macro classes. Each column
shows a different semantic cluster (rough label at the bottom) where images
can be seen to have similar content, while each row is a different random
cluster, and no structure is visible. b: Gain in best validation accuracy
(difference from the value corresponding to the unpruned network) for the
random and semantic tasks. The lines are averages of 4 independent runs, with
the shaded area representing one standard deviation. Each training was run for
500k steps for the semantic and 300k steps for the random clustering to ensure
convergence. The dashed line marks the iteration at $u\simeq 0.7\%$ used in
panels c and d. c: Histogram of $C^{{\rm in},1}$ for the two cases at the
iteration $u\simeq 0.7\%$. The dashed line is the theoretical binomial
distribution for random pruning. d: $S^{\rm sc}({\bf d})$ for the two cases at
the iteration $u\simeq 0.7\%$. Normalization and color map as shown in Fig. 2.

To further understand the role played by the properties of the dataset we now
modify it in the following way. We cluster the original 1000 classes of the
training set and test set in 10 balanced macro-classes in two different ways:
the first one, called random, groups the original categories in a non-
meaningful way (on the basis of their numerical label in the dataset modulo
10). This produces 10 classes which are all very similar. The second one,
called semantic, clusters together similar original classes, into macro-
categories such as “dog”, “device”, “transport and furnishing”, etc. This
produces 10 classes which characterize the data in a meaningful way. An
example of the difference between these two ways of regrouping the 1000
classes is reported in Fig. 5a, where the rows represent examples from the
“random” classes, and the columns from the “semantic” classes. For more
details, see SM C. After training the accuracy obtained for the random task is
at best 13%, while it surpasses 36% for the semantic one. This difference is
expected since in the former case elements of different classes are very
difficult to be distinguished and training mainly leads to memorization and
not learning.

We now compare the gain in accuracy due to pruning for the semantic and the
random task. Fig. 5b shows that pruning is beneficial for the former but not
for the latter. Moreover, the geometrical properties of the subnetwork induced
by pruning are very different in the two cases. In panel c and panel d we show
respectively the histogram of the connectivities $C^{{\rm in},1}$ and of the
local displacements ${\bf d}_{ii^{\prime}}$. These results reveal that the
subnetwork obtained by pruning displays local features and non-trivial
connectivity distribution for the semantic task only. In the other case, the
subnetwork is essentially featureless, non-local and like one where weights
have been pruned at random. Sample masks for the two tasks are shown in SM B.

These results highlight the role of the task in shaping the properties of the
network obtained by pruning: only for the task that the network can
efficiently learn, and not just memorize, local features emerge. This result
is a direct consequence of the qualitative difference in the network solutions
for the two tasks: features do not simply emerge from the data in an
unsupervised fashion, but they represent structures useful for optimization
with respect to a meaningful loss. If the task is solved in an unstructured
way, e.g. through memorization, the features are simply not selected. In SM
D.1 we provide more evidence by focusing on other tasks in between the
semantic and the random ones.

##  7 Discussion

CNNs are at the heart of modern machine learning for vision. They have been
inspired by our visual system and they have proven their effectiveness in
countless tasks. However, there is no a priori justification for convolutional
architectures, and no reason why other even more effective architectures
should not exist. Indeed, several modification of the original convolutional
idea have proven effective [2, 35, 36], and recently new architectures such as
transformers have challenged the CNN supremacy in vision [37].

It is therefore interesting to see if the CNN architecture, or something with
similar characteristics, could be naturally obtained from data. A recent work
[27] takes a first important step in this direction, with a custom
modification of the LASSO technique [38], and working on a small but highly
augmented dataset, it shows the emergence in training of local and sparse
nonzero weights. In this work, we have followed a different perspective. With
the aim of characterizing the inductive bias induced by pruning, we have
limited ourselves to the original inputs, and we have applied iterative
magnitude pruning. This approach has two benefits: it naturally leads to
masks, i.e. it irreversibly changes the architecture of the original network,
and it leads to a final model that can be trained from scratch to the final
accuracy (i.e. from the original initialization values, although these are
still correlated with the masks). In combination with the lack of
augmentation, this makes features selected from this procedure the natural
structure emerging from the dataset and task at hand.

We have presented a thorough analysis of the architecture thus found: the
pruning procedure does not affect all nodes equally, but a small number of
them retains a disproportionate amount of inputs. These nodes are particularly
important for the performance of the network and they correspond to input
masks that are local in space and color channels, with a preference for
specific patterns, found throughout the image (although for these images some
features are clearly more likely to appear at some specific position than
others). At visual inspection, these features bear a strong resemblance to
those found in CNNs [18], the visual cortex [34, 39] and obtained with
$\beta-$LASSO [27]. At high pruning, the features become more local and
sparse, and they are combined in the next layer with a preference for similar
patterns and close location.

All these characteristics align well with the design choices of CNNs:
selecting local features and combining them locally is the natural structure
emerging from the image classification task—it represents the winning ticket
that can be more easily trained. While other features like weight sharing
simply cannot be reproduced in this model, the presence of similar masks at
different locations is a sign of translational invariance (or the closest
version of it available in these mostly centered images, an experiment with
complete translational invariance is presented in SM D.4). In this sense, this
procedure could suggest network structures even better aligned with the data
from a real dataset, leading to more effective architectures. For instance the
sparse sampling, even at this low image resolution, is reminiscent of dilated
convolutions [36].

As could be expected, only training on a large enough dataset leads to the
emergence of these features. Interestingly, the success of the IMP itself
seems to be related to their presence, hinting at the different structure of
the solution, in line with recent findings about generalization and
prunability [40]. In the same direction, we have shown that locality and
defined features disappear when we replace the task with a more vague one,
where IMP is also ineffective. Features are thus not a simple consequence of
the dataset, but depend on the structure imposed by the task.

There are several directions which are worth exploring in future works. More
complex starting architectures and larger or augmented training sets could be
explored, to obtain even closer approximations to CNNs or other more effective
architectures. The dependence of the architectural properties induced by
pruning on the optimization protocol is another interesting aspect. For
instance, we have found that just training until the beginning of overfitting
is sufficient to obtain these features (see SM A.3). We have also noticed that
precursors are already visible at the early stages of pruning (see video link
in SM E), suggesting the possibility of their early identification and more
refined search strategies. In addition, it would be interesting to study more
advanced pruning algorithms such as [41, 42], especially iterative or
inherently sparse ones that could explore structures corresponding to
prohibitively large networks. Finally, repeating our analysis for tasks
different from visual ones, e.g. for audio [43] and time series [44], and
study the architectural bias induced by pruning is certainly an interesting
direction for future research. This approach could also highlight useful
architectures in fields that are still using more standard FCNs such as
material modeling [45].

In conclusion, our work underlines the effectiveness of pruning as a tool to
uncover not only more efficient networks, but also specific architectural
properties associated to the structure of the data and relevant for the
training task. From this point of view, pruning schemes could offer a way to
uncover effective new architectures for a wide category of problems.

## Acknowledgments and Disclosure of Funding

We thank S. d’Ascoli, S. Goldt, M. Refinetti and L. Sagun for useful
discussions. FP would especially like to thank E. Küçükbenli for insightful
ideas.

We acknowledge funding from the French government under management of Agence
Nationale de la Recherche as part of the “Investissements d’avenir” program,
reference ANR-19-P3IA-0001 (PRAIRIE 3IA Institute) and from the Simons
Foundation collaboration “Cracking the Glass Problem” (No. 454935 to G.
Biroli).

## References

  * Krizhevsky et al. [2012] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  In F. Pereira, C. J. C. Burges, L. Bottou, and K. Q. Weinberger, editors, _Advances in Neural Information Processing Systems_ , volume 25. Curran Associates, Inc., 2012.
  * He et al. [2016] 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 (CVPR)_ , June 2016.
  * Vaswani et al. [2017] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  _arXiv preprint 1706.03762_ , 2017.
  * Brown et al. [2020] Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei.  Language models are few-shot learners.  _arXiv preprint 2005.14165_ , 2020.
  * Silver et al. [2017] David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy Lillicrap, Karen Simonyan, and Demis Hassabis.  Mastering chess and shogi by self-play with a general reinforcement learning algorithm.  _arXiv preprint 1712.01815_ , 2017.
  * Tan and Le [2020] Mingxing Tan and Quoc V. Le.  Efficientnet: Rethinking model scaling for convolutional neural networks.  _arXiv preprint 1905.11946_ , 2020.
  * Hoefler et al. [2021] Torsten Hoefler, Dan Alistarh, Tal Ben-Nun, Nikoli Dryden, and Alexandra Peste.  Sparsity in deep learning: Pruning and growth for efficient inference and training in neural networks.  _arXiv preprint 2102.00554_ , 2021.
  * Frankle and Carbin [2019] Jonathan Frankle and Michael Carbin.  The lottery ticket hypothesis: Finding sparse, trainable neural networks.  In _ICLR_. OpenReview.net, 2019.
  * LeCun et al. [1989] Y. LeCun, B. Boser, J. S. Denker, D. Henderson, R. E. Howard, W. Hubbard, and L. D. Jackel.  Backpropagation applied to handwritten zip code recognition.  _Neural Computation_ , 1(4):541–551, 1989.  doi: 10.1162/neco.1989.1.4.541.
  * Simonyan and Zisserman [2015] Karen Simonyan and Andrew Zisserman.  Very deep convolutional networks for large-scale image recognition.  _arXiv preprint 1409.1556_ , 2015.
  * Szegedy et al. [2015] Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Dumitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich.  Going deeper with convolutions.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , June 2015.
  * d’Ascoli et al. [2019] Stéphane d’Ascoli, Levent Sagun, Giulio Biroli, and Joan Bruna.  Finding the needle in the haystack with convolutions: on the benefits of architectural bias.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d’Alché Buc, E. Fox, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc., 2019.
  * Hubel and Wiesel [1962] D. H. Hubel and T. N. Wiesel.  Receptive fields, binocular interaction and functional architecture in the cat’s visual cortex.  _The Journal of physiology_ , 160(1):106–154, Jan 1962.  doi: 10.1113/jphysiol.1962.sp006837.
  * Fukushima [1980] Kunihiko Fukushima.  Neocognitron: A self-organizing neural network model for a mechanism of pattern recognition unaffected by shift in position.  _Biological Cybernetics_ , 36(4):193–202, April 1980.  doi: 10.1007/bf00344251.
  * Ruderman [1994] Daniel L Ruderman.  The statistics of natural images.  _Network: Computation in Neural Systems_ , 5(4):517–548, 1994.  doi: 10.1088/0954-898X\\_5\\_4\\_006.
  * Morcos et al. [2019] Ari S. Morcos, Haonan Yu, Michela Paganini, and Yuandong Tian.  One ticket to win them all: generalizing lottery ticket initializations across datasets and optimizers.  _arXiv preprint 1906.02773_ , 2019.
  * Chrabaszcz et al. [2017] Patryk Chrabaszcz, Ilya Loshchilov, and Frank Hutter.  A downsampled variant of imagenet as an alternative to the CIFAR datasets.  _arXiv preprint 1707.08819_ , 2017.
  * Zeiler and Fergus [2014] Matthew D. Zeiler and Rob Fergus.  Visualizing and understanding convolutional networks.  In David Fleet, Tomas Pajdla, Bernt Schiele, and Tinne Tuytelaars, editors, _Computer Vision – ECCV 2014_ , pages 818–833, Cham, 2014. Springer International Publishing.  ISBN 978-3-319-10590-1.
  * Zhou et al. [2019] Hattie Zhou, Janice Lan, Rosanne Liu, and Jason Yosinski.  Deconstructing lottery tickets: Zeros, signs, and the supermask.  _arXiv preprint 1905.01067_ , 2019.
  * Liu et al. [2019] Zhuang Liu, Mingjie Sun, Tinghui Zhou, Gao Huang, and Trevor Darrell.  Rethinking the value of network pruning.  _arXiv preprint 1810.05270_ , 2019.
  * Gale et al. [2019] Trevor Gale, Erich Elsen, and Sara Hooker.  The state of sparsity in deep neural networks.  _arXiv preprint 1902.09574_ , 2019.
  * Frankle et al. [2019] Jonathan Frankle, Gintare Karolina Dziugaite, Daniel M. Roy, and Michael Carbin.  Linear mode connectivity and the lottery ticket hypothesis.  _arXiv preprint 1912.05671_ , 2019.
  * Frankle et al. [2020a] Jonathan Frankle, Gintare Karolina Dziugaite, Daniel M. Roy, and Michael Carbin.  Stabilizing the lottery ticket hypothesis.  _arXiv preprint 1903.01611_ , 2020a.
  * Frankle et al. [2020b] Jonathan Frankle, David J. Schwab, and Ari S. Morcos.  The early phase of neural network training.  _arXiv preprint 2002.10365_ , 2020b.
  * Renda et al. [2020] Alex Renda, Jonathan Frankle, and Michael Carbin.  Comparing rewinding and fine-tuning in neural network pruning.  _arXiv preprint 2003.02389_ , 2020.
  * Sabatelli et al. [2020] Matthia Sabatelli, Mike Kestemont, and Pierre Geurts.  On the transferability of winning tickets in non-natural image datasets.  _arXiv preprint 2005.05232_ , 2020.
  * Neyshabur [2020] Behnam Neyshabur.  Towards learning convolutions from scratch.  _arXiv preprint 2007.13657_ , 2020.
  * Tolstikhin et al. [2021] Ilya Tolstikhin, Neil Houlsby, Alexander Kolesnikov, Lucas Beyer, Xiaohua Zhai, Thomas Unterthiner, Jessica Yung, Daniel Keysers, Jakob Uszkoreit, Mario Lucic, et al.  Mlp-mixer: An all-mlp architecture for vision.  _arXiv preprint arXiv:2105.01601_ , 2021.
  * Russakovsky et al. [2015] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei.  ImageNet Large Scale Visual Recognition Challenge.  _International Journal of Computer Vision (IJCV)_ , 115(3):211–252, 2015.  doi: 10.1007/s11263-015-0816-y.
  * Ioffe and Szegedy [2015] Sergey Ioffe and Christian Szegedy.  Batch normalization: Accelerating deep network training by reducing internal covariate shift.  In Francis Bach and David Blei, editors, _Proceedings of the 32nd International Conference on Machine Learning_ , volume 37 of _Proceedings of Machine Learning Research_ , pages 448–456, Lille, France, 07–09 Jul 2015. PMLR.
  * Glorot and Bengio [2010] Xavier Glorot and Yoshua Bengio.  Understanding the difficulty of training deep feedforward neural networks.  In Yee Whye Teh and Mike Titterington, editors, _Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics_ , volume 9 of _Proceedings of Machine Learning Research_ , pages 249–256, Chia Laguna Resort, Sardinia, Italy, 13–15 May 2010. PMLR.
  * You et al. [2020] Haoran You, Chaojian Li, Pengfei Xu, Yonggan Fu, Yue Wang, Xiaohan Chen, Richard G. Baraniuk, Zhangyang Wang, and Yingyan Lin.  Drawing early-bird tickets: Towards more efficient training of deep networks.  _arXiv preprint 1909.11957_ , 2020.
  * Blalock et al. [2020] Davis Blalock, Jose Javier Gonzalez Ortiz, Jonathan Frankle, and John Guttag.  What is the state of neural network pruning?  _arXiv preprint arXiv:2003.03033_ , 2020.
  * Marĉelja [1980] S. Marĉelja.  Mathematical description of the responses of simple cortical cells$\ast$.  _J. Opt. Soc. Am._ , 70(11):1297–1300, Nov 1980\.  doi: 10.1364/JOSA.70.001297.
  * Szegedy et al. [2016] Christian Szegedy, Vincent Vanhoucke, Sergey Ioffe, Jon Shlens, and Zbigniew Wojna.  Rethinking the inception architecture for computer vision.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , June 2016.
  * Yu and Koltun [2016] Fisher Yu and Vladlen Koltun.  Multi-scale context aggregation by dilated convolutions, 2016.
  * Dosovitskiy et al. [2020] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby.  An image is worth 16x16 words: Transformers for image recognition at scale.  _arXiv preprint 2010.11929_ , 2020.
  * Tibshirani [1996] Robert Tibshirani.  Regression shrinkage and selection via the lasso.  _Journal of the Royal Statistical Society: Series B (Methodological)_ , 58(1):267–288, 1996.  doi: https://doi.org/10.1111/j.2517-6161.1996.tb02080.x.
  * Wolf et al. [2005] L. Wolf, T. Serre, and T. Poggio.  Object recognition with features inspired by visual cortex.  In _Proceedings. 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition_ , volume 3, pages 994–1000, Los Alamitos, CA, USA, jun 2005. IEEE Computer Society.  doi: 10.1109/CVPR.2005.254.
  * Kuhn et al. [2021] Lorenz Kuhn, Clare Lyle, Aidan N. Gomez, Jonas Rothfuss, and Yarin Gal.  Robustness to pruning predicts generalization in deep neural networks.  _arXiv preprint 2103.06002_ , 2021.
  * Evci et al. [2020] Utku Evci, Trevor Gale, Jacob Menick, Pablo Samuel Castro, and Erich Elsen.  Rigging the lottery: Making all tickets winners.  In _Proceedings of the 37th International Conference on Machine Learning_ , pages 471–481, 2020.
  * Lin et al. [2020] Tao Lin, Sebastian U. Stich, Luis Barba, Daniil Dmitriev, and Martin Jaggi.  Dynamic model pruning with feedback.  _arXiv preprint 2006.07253_ , 2020.
  * van den Oord et al. [2016] Aaron van den Oord, Sander Dieleman, Heiga Zen, Karen Simonyan, Oriol Vinyals, Alex Graves, Nal Kalchbrenner, Andrew Senior, and Koray Kavukcuoglu.  Wavenet: A generative model for raw audio.  _arXiv preprint 1609.03499_ , 2016.
  * Gamboa [2017] John Cristian Borges Gamboa.  Deep learning for time-series analysis.  _arXiv preprint 1701.01887_ , 2017.
  * Behler [2016] Jörg Behler.  Perspective: Machine learning potentials for atomistic simulations.  _The Journal of Chemical Physics_ , 145(17):170901, 2016.  doi: 10.1063/1.4966192.
  * Kingma and Ba [2014] Diederik P. Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  _arXiv preprint 1412.6980_ , 2014.

##  Appendix A Convergence tests

In this section we report the result of modifying different hyperparameters of
the training or the pruning procedure, to show the robustness of the results
presented in the main text.

###  A.1 Minimization

Fig. 6 shows the best validation and training curves when modifying the
optimization procedure either by changing the learning rate or by employing a
more advanced minimizer (Adam [46]). While there are small differences in the
absolute accuracy, the main behavior is robust with respect to the
minimization procedure. Although the value $0.5$ for the learning rate leads
to slightly better accuracy, we have employed a more conservative $0.1$
throughout all experiments in the main text, as the final accuracy is not the
main scope of this work.

Figure 6:  a: Best validation accuracy as a function of $u$ for different
minimizers: stochastic gradient descent with varying learning rate (SGD in the
legend, followed by the learning rate) and Adam with standard parameters and
learning rate $0.01$. b: Training error (left) and validation error (right)
for the initial dense iteration for all minimizers. c: Training error (left)
and validation error (right) for the best iteration of each minimizer (square
in panel a). While training is much slower, all models are able to reach
stationary validation within $10^{5}$ steps, apart from learning rate 0.02
that barely reaches it.  Figure 7:  a: Best validation accuracy as a function
of $u$ for different architectures (see legend and text for notation). b:
Training error (left) and validation error (right) for the initial dense
iteration for all architectures. c: Training error (left) and validation error
(right) for the best iteration of each architecture (square in panel a). d:
$S^{\rm sc}$ (see Fig. 2 for details) and histograms of $C^{{\rm in},1}$ for
the best iteration of each architecture (square in panel a).

###  A.2 Other architectures

In this section, we modify the network architecture from the original 3 hidden
layers of size 1024 (3l, 1k): we deepen the network with 4 (4l, 1k) or 5 (5l,
1k) layers of the same size, or we change the width of each layer (uniformly)
to wider 2048 (3l, 2k) and 4096 (3l, 4k), or smaller 512 (3l, 512) and 256
(3l, 256). All training parameters are kept the same in all these experiments,
although better results could be achieved with better minimization and at
least the smallest (3l, 256) network could benefit from longer training.

Fig. 7a-c shows the best validation and training curves for each architecture.
We see that, at least with these parameters, deepening the network does not
have a big effect. For the width: a moderately narrower network is as
effective, but larger ones are slightly worse. This might be due to the
training procedure, but the difference in performance is already present for
the dense networks, and the first pruning steps are not as effective in this
case, so these networks might be too overparametrized, leading to a
qualitatively different solution. Panel d shows the locality and connection
histogram for the first layer of each network at the best step, indicating
that the features discussed in the main text (locality and excess connections
nodes) are present in all the cases.

###  A.3 IMP parameters

We now consider the parameters related to the IMP procedure. In particular, we
act separately on 3 fronts: decreasing the pruning ratio per step ($p=0.2$),
decreasing the rewind time for the weights (500, 100 or 0) and varying the
total training time per iteration, i.e. the time at which we consider the
weights for updating the pruning mask ($5\cdot 10^{5}$, $10^{4}$ and $5\cdot
10^{3}$).

Fig. 8a shows the best validation for each of these experiments (train time,
rewind time, $p$ in legend). We can see that most curves lead to the same
accuracy, apart from training times shorter than the validation minimum $\sim
2\cdot 10^{4}$, which is unsurprising. This justifies our practice of stopping
training before complete training set overfitting, since the longer run does
not offer any benefit. The pruning ratio and rewind time are also clearly
converged, we have decided to keep a nonzero rewind time to be more
conservative for the other experiments, which could be more brittle.

The other panels of the same figure show dense and best iteration training
curves and locality and connectivity plots. The only cases showing a deviation
from the main text results are once again the very short trains.
Interestingly, some of the feature seem to survive even for these cases where
the network is not even allowed to reach the best validation in each run,
suggesting that some of the relevant features are already present in the early
stages of training.

Figure 8:  a: Best validation accuracy as a function of $u$ for different IMP
parameters (train time, rewind time, $p$ in legend). b: Training error (left)
and validation error (right) for the initial dense iteration for experiments
of different total steps. c: Training error (left) and validation error
(right) for the best iteration of each experiments (square in panel a). d:
$S^{\rm sc}$ (see Fig. 2 for details) and histograms of $C^{{\rm in},1}$ for
the best iteration of each experiments (square in panel a).

##  Appendix B More connectivity plots

In this section we present more specific plots of $S^{\rm sc}({\bf d})$ and
masks for more experiments. As a reference, Fig. 9 presents the $S^{\rm sc}$
plot for single nodes pruned at random at different sparsity levels. Even for
a fully connected node, the finite size of the image makes local connections
more likely than farther connections, but with a decay clearly slower than
what shown for localized nodes. For higher sparsity, we see more and more
delocalized patterns appearing (of course this is true for single nodes, while
the sum of many random sparse nodes would eventually approximate the fully
connected one).

Figure 9:  $S^{\rm sc}$ for single nodes randomly pruned at a given $u$
(number of surviving connection in parenthesis, see Fig. 2 for visualization
details).

Another interesting quantity, shown in Fig. 10 for different networks, is the
plot of $C^{{\rm out},0}$, i.e. the amount of connections surviving to each
pixel. We can see that for well performing networks the connectivity is higher
to the center of the image, with some extra connections to the edges and
corners, while less effective networks tend to have more uniform connectivity.

Figure 10:  $C^{{\rm out},0}$ for different experiments proposed in the main
text, at $u\sim 1\%$.

###  B.1 Locality per number of connections

Fig. 11 presents plots of $S^{\rm sc}$ when we restrict the computation to
first hidden layer nodes having values of $C^{{\rm in},1}_{j}$ in a given
range. This can give us further insight on whether the locality of a network
is due to many close pixels in the more pruned nodes, or few localized
clusters in the more connected ones. We present graphs for the standard
network, one trained on 30% of the data and the two versions (semantic and
random) of the experiments on 10 classes. All networks are at the same level
of pruning $u\sim 1\%$.

For the initial network, we see most bins showing some form of locality, more
apparent in the most connected bins (some of the later bins contain only a few
nodes, strongly affecting the shape of the distance plot). But for the smaller
dataset, we see that only some of the bins with more connections seem to show
proper locality, with the less connected ones no better than random. A similar
behavior is seen in the network trained on 10 semantic classes. In both these
cases features are still partially visible, but we can see that the structure
is not preserved in all nodes. Finally, the network trained on 10 random
classes does not show any locality at any scale.

Figure 11:  $S^{\rm sc}$ of connections to nodes with different values of
$C^{{\rm in},1}$. From top to bottom: standard network, training on 30% data,
training on 10 semantic classes and training on 10 random classes. All
networks are taken at $u\sim 1\%$ Each plot represents the sum of all nodes in
an interval of $C^{{\rm in},1}$ shown below the image, with the number of
nodes falling in the bin in parenthesis. Intervals are of 10, 5, 5, and 3 bins
respectively, to cover the range of connectivity of each network. The last bin
covers all remaining nodes.

###  B.2 Highly connected masks

We show here a larger sample of masks of the most connected nodes. Fig. 12
covers the original network of Fig. 1: for the best sparsity $u\sim 1\%$ we
show the top 120 most connected layer 1 nodes, showing the variety of features
sifted out, and the top 30 effective masks $\mu_{ij}$ of layer 2, showing how
they cover most of the image. For the higher sparsity $u\sim 0.3\%$ we show
the 60 most connected of the first layer, highlighting how features are
preserved, although more local and with higher sparsity. We also show the
effective masks of layer 2, partially local, and of layer 3, covering most of
the image.

Figure 12:  Masks of the most connected nodes for different layers and
sparsity of the original network (same representation as Fig. 3).

For the same network, at $u\sim 0.3\%$, Fig. 13 shows a more in depth analysis
of the masks $\mu_{ij}$ for the most connected nodes of the second hidden
layer. The masks are shown in the center of the image and below them are the 3
images of the validation set that activate the nodes the most. For 3 sample
nodes, the top of the image shows explicitly all the first hidden layer nodes
connected to them: they have rather uniform features and a specific local
spatial distribution. Although not as clean as in a real CNN, we can see how
the first layer highlights local features, that are aggregated in a larger but
still localized fashion in the second layer, often aggregating similar
features at different position, like convolutions preferring a specific
channel.

Figure 13:  Masks of the second layer from input
$\mu_{ij}=\theta(\sum_{k}m^{1}_{ik}m^{2}_{kj}-1/2)$ with most nonzero element
(center, marked “Layer 2”), images with the largest activation on them (below,
marked “Input”) and for 3 of them masks in the first layer connected to them
(top, marked “Layer 1”), showing the masked weights $w^{1}_{ij}m^{1}_{ij}$ as
detailed in Fig. 3.

Fig. 14 shows the 30 most connected masks in the first layer for other
networks: trained on 50% of the data, 30% of the data, 10 semantic classes or
10 random classes. We can see more and more featureless masks among the most
connected as we shrink the dataset. For the semantic classes, we still find
local structures, although less clear than the original task, while the random
classes show no structure at all.

Figure 14:  Masks of the most connected nodes for different experiments: original task on 50% and 30% of the data, and task modified to 10 super-classes either semantically or randomly grouped.  # |  Class composition (rough) | #Classes |  #Elements
---|---|---|---
0 |  Dog | 118 | 147873
1 |  Mammal\Dog | 100 | 129728
2 |  Bird, Reptile | 95 | 122895
3 |  Fish, Amphibian, Invertebrate | 85 | 110034
4 |  Device\Musical instrument | 104 | 131965
5 |  Covering, Musical instrument | 111 | 142423
6 |  Container\Vehicle, Appliance, Equipment | 99 | 126603
7 |  Transport, Furnishing | 95 | 122661
8 |  Plant, Fungus, Food, Vegetable, Fruit, Implement | 96 | 122701
9 |  Construction, Miscellaneous | 97 | 124282
|  Total | 1000 | 1281167
Table 1:  Proposed 10 aggregated ImageNet classes: for each class we give a
rough definition of the class in terms of macro-categories, the number of
original ImageNet classes and single images in those classes that fall into
this class (the symbol A\B indicates all classes that fall in the macro class
A but not in B).

##  Appendix C Class clustering

We give here more details about the construction of 10 semantic super-classes.
Our goal was to design 10 classes that would: include all the original 1000,
be similarly sized, and be easily identified in terms of larger WordNet
categories.

The details of the final classes constructed are summarized in Table 1. The
animals are divided into 4 categories (the large amount of dogs naturally
falls into a slightly larger category). Objects make up most of the remaining
6 classes roughly based on sub-categories of “artifacts”: device, covering
(mostly clothes), container (excluding vehicles), transport and furnishing,
implement and construction. Class 8 also contains all plant-derived categories
and food. Class 9 also includes all categories not included in one of the
previous macro categories, listed as miscellaneous (including e.g. some
natural formations). A few classes (21) are included in more than 1 macro
class by this division, and they were arbitrarily assigned to a single one.
The specific attribution of each of the original classes is available in the
code repository specified in E.

##  Appendix D Modified tasks

We report here some experiments on modified datasets, that reinforce some of
the statements of the main text

###  D.1 More super-classes

We consider more ways of creating 10 macro classes from the original one. To
create a task in between the “semantic” and “random” ones of Sec. 6, we
consider 2 options: one we call “5 semantic/5 random”, where the first 5
classes are the ones described in Sec. D.1, while the other ones are random
groupings of the remaining categories. The other we call “partial semantic”
where each of our super-classes is composed of half (around 50) of the
categories of the “semantic” classes and the other half picked at random
between the remaining categories.

To gauge the complexity of the task, Fig. 15b reports the unpruned and best
accuracy for each of these experiments, confirming that they are in between
the two extremes, the one with 5 “fully meaningful” classes being simpler than
the other. The full best validation curves (minus the unpruned values)
reported in panel a and the locality and connectivity plots in panels c and d
support the idea of a gradual progression between a network characterized by
local structures and one where the task is performed in a different way.
Lastly, the most connected first layer masks in panel e highlight the
progressive disappearance of features.

Figure 15:  a: Gain in best validation accuracy (difference from the value
corresponding to the unpruned network) for tasks from semantic to random. b:
Best validation accuracy for the unpruned network (empty dots) and best IMP
iteration (full dots) for the different tasks. c: $S^{\rm sc}({\bf d})$ for
the four tasks at the iteration $u\simeq 0.5\%$. Normalization and color map
as shown in Fig. 2. c: Histogram of $C^{{\rm in},1}$ for the four tasks at the
iteration $u\simeq 0.5\%$. The dashed line is the theoretical binomial
distribution for random pruning. e: Most connected first layer masks for the
four tasks.

###  D.2 Rotated images

We rotate all images 20 degrees counterclockwise, and crop to obtain new
$32\times 32$ images (we mask out the pixels not corresponding to any original
pixels). This is done to verify that the vertical and horizontal directions
have nothing to do with the discretization of the images. The overall training
is similar to the original one, with slightly lower accuracy. Fig. 16 shows
$S({\bf d})$ and masks at the best iteration. As expected, the preferred
directions are rotated and masks tend to follow the new horizontal and
vertical alignment.

Figure 16:  a: $S^{\rm sc}$ and $S^{\rm dc}$ for the best iteration of the
experiment on rotated images. b: masks of the 48 most connected layer 1 nodes
for the same iteration.

###  D.3 ImageNet64

We train a network on the $64\times 64$ pixels, higher resolution ImageNet
downsampling from the same source: ImageNet64 [17]. We use exactly the same
parameters of our main experiment, and obtain only slightly lower accuracy and
a similar IMP curve as the lower resolution version, as shown in Fig. 17a. We
analyze the best iteration at $u\sim 0.3$: locality is still preserved as
shown in panel b, with the main axes being preferred even more sharply. The 90
most connected layer 1 masks (panel c) show similar features to the ones found
elsewhere, with even clearer preference for sparse sampling and separated
lines along the main orientations.

Figure 17:  a: Best validation accuracy as a function of $u$ for ImageNet64
dataset. b: $S^{\rm sc}$ and $S^{\rm dc}$ (see Fig. 2 for details) for the
best iteration at $u\sim 0.3\%$ (square in panel a). c: 90 most connected
layer 1 masks for the same iteration.

###  D.4 Translated images

For this experiment, we enforce complete translational invariance by
translating each image vertically and horizontally by a random amount (in
$[0,31]$) modified every time a mini-batch is created, and wrapping the image
in both axes (periodic boundary conditions). This clearly causes the
appearance of unrealistic boundaries in the image, but achieves the goal of
this experiment or rendering each pixel is equivalent, on average. We validate
this network on the original, untranslated images, achieving lower accuracy
then the original network, as might be expected since the training dataset is
much larger and not matching the validation dataset (we also do not re-
optimize the training parameters, and just run long trainings of 500k steps).
The IMP validation curve in Fig. 18a shows a peak at lower sparsity ($u\sim
8\%$), consistent with the modified dataset. Analyzing this best iteration,
the $S^{\rm sc}$ map in panel b indicates local connectivity, with a stronger
bias towards the horizontal and vertical directions. The large variety of maps
in panel c (and their weightd counterparts in panel d) show surviving features
in the shape of stripes and patches patterns with different orientations and
periodicity. Despite the synthetic nature of this dataset, it is interesting
to observe these patterns emerge from a translationally invariant dataset.
Moreover, the combination of these features with the spatial focus of the
original dataset (also visible in Fig. 10) helps explain the emergence of
Gabor-like filters.

Figure 18:  a: Best validation accuracy as a function of $u$ for randomly
translated dataset. b: $S^{\rm sc}$ (see Fig. 2 for details) for the best
iteration at $u\sim 8\%$ (square in panel a). c: 200 most connected layer 1
masks for the same iteration. d: The same masks, multiplied by the relative
weights (see Fig. 3 for details).

##  Appendix E External resources

A repository with all the code required to reproduce the results of this paper
is available at https://github.com/phiandark/SiftingFeatures. The main code is
written in Python and based on tensorflow (1.xx). Input files are provided to
reproduce our experiments and a jupyter notebook is available to post-process
the data and recreate the figures of this work.

The same repository hosts a text file with the attribution of each ImageNet
category to one of the 10 macro-class in our semantic clustering experiment.

Videos are also available in the same location, showing the evolution of the
most connected masks and their weighted versions during IMP for the main task
of this work.