How Deep Neural Networks Learn Compositional Data: The Random Hierarchy
  Model
Deep learning algorithms demonstrate a surprising ability to learn
high-dimensional tasks from limited examples. This is commonly attributed to
the depth of neural networks, enabling them to build a hierarchy of abstract,
low-dimensional data representations. However, how many training examples are
required to learn such representations remains unknown. To quantitatively study
this question, we introduce the Random Hierarchy Model: a family of synthetic
tasks inspired by the hierarchical structure of language and images. The model
is a classification task where each class corresponds to a group of high-level
features, chosen among several equivalent groups associated with the same
class. In turn, each feature corresponds to a group of sub-features chosen
among several equivalent ones and so on, following a hierarchy of composition
rules. We find that deep networks learn the task by developing internal
representations invariant to exchanging equivalent groups. Moreover, the number
of data required corresponds to the point where correlations between low-level
features and classes become detectable. Overall, our results indicate how deep
networks overcome the curse of dimensionality by building invariant
representations, and provide an estimate of the number of data required to
learn a hierarchical task.
Francesco Cagnetta, Leonardo Petrini, Umberto M. Tomasini, Alessandro Favero, Matthieu Wyart
# How Deep Neural Networks Learn Compositional Data:

###### Abstract

Learning generic high-dimensional tasks is notably hard, as it requires a number of training data exponential in the dimension. Yet, deep convolutional neural networks (CNNs) have shown remarkable success in overcoming this challenge. A popular hypothesis is that learnable tasks are highly structured and that CNNs leverage this structure to build a low-dimensional representation of the data. However, little is known about how much training data they require, and how this number depends on the data structure. This paper answers this question for a simple classification task that seeks to capture relevant aspects of real data: the Random Hierarchy Model. In this model, each of the \(n_{c}\) classes corresponds to \(m\) synonymic compositions of high-level features, which are in turn composed of sub-features through an iterative process repeated \(L\) times. We find that the number of training data \(P^{*}\) required by deep CNNs to learn this task _(i)_ grows asymptotically as \(n_{c}m^{L}\), which is only polynomial in the input dimensionality; _(ii)_ coincides with the training set size such that the representation of a trained network becomes invariant to exchanges of synonyms; _(iii)_ corresponds to the number of data at which the correlations between low-level features and classes become detectable. Overall, our results indicate how deep CNNs can overcome the curse of dimensionality by building invariant representations, and provide an estimate of the number of data required to learn a task based on its hierarchically compositional structure.

The achievements of deep learning algorithms [1] are outstanding. These methods exhibit superhuman performances in areas ranging from image recognition [2] to Goplaying [3], and large language models such as GPT4 [4] can generate unexpectedly sophisticated levels of reasoning. However, despite these accomplishments, we still lack a fundamental understanding of the underlying factors. Indeed, Go configurations, images, and patches of text lie in high-dimensional spaces, which are hard to sample due to the _curse of dimensionality_[5]: the distance \(\delta\) between neighboring data points decreases very slowly with their number \(P\), as \(\delta=\mathcal{O}(P^{-1/d})\) where \(d\) is the space dimension. A generic task such as regression of a continuous function [6] requires a small \(\delta\) for high performance, implying that \(P\) must be _exponential_ in the dimension \(d\). Such a number of data is unrealistically large: for example, the benchmark dataset ImageNet [7], whose effective dimension is estimated to be \(\approx 50\)[8], consists of only \(\approx 10^{7}\) data, significantly smaller than \(e^{50}\approx 10^{20}\). This immense difference implies that learnable tasks are not generic, but highly structured. What is then the nature of this structure, and why are deep learning methods able to exploit it? Without a quantitative answer, it is impossible to predict even the order of magnitude _of the order of magnitude_ of the number of data necessary to learn a specific task.

A popular idea attributes the efficacy of deep learning methods to their ability to build a useful representation of the data, which becomes increasingly complex across the layers. In simple terms, neurons closer to the input learn to detect simple features like edges in a picture, whereas those deeper in the network learn to recognize more abstract features, such as faces [9, 10]. Intuitively, if these representations are also invariant to aspects of the data unrelated to the task, such as the exact position of an object in a frame for image classification [11], they may effectively reduce the dimensionality of the problem and make it tractable. This view is supported by several empirical studies of the hidden representations of trained networks. In particular, measures such as _(i)_ the mutual information between such
representations and the input [12, 13], _(ii)_ their intrinsic dimensionality [14, 15], and _(iii)_ their sensitivity toward transformations that do not affect the task (e.g. smooth deformations for image classification [16, 17]), all eventually decay with the layer depth. In some cases, the magnitude of this decay correlates with performance [16]. However, these studies do not indicate how much data is required to learn such representations, and thus the task.

Here we study this question for tasks which are hierarchically compositional--arguably a key property for the learnability of real data [18, 19, 20, 21, 22, 23, 24, 25]. To provide a concrete example, consider the picture of a dog (see Fig. 1). The image consists of several high-level features like head, body, and limbs, each composed of sub-features like ears, mouth, eyes, and nose for the head. These sub-features can be further thought of as combinations of low-level features such as edges. Recent studies have revealed that: _(i)_ deep networks represent hierarchically compositional tasks more efficiently than shallow networks [21]; _(ii)_ the minimal number of data that contains enough information to reconstruct such tasks is polynomial in the input dimension [24], although extracting this information remains impractical with standard optimization algorithms; _(iii)_ correlations between the input data and the task are critical for learning [19, 26] and can be exploited by algorithms based on the iteration of clustering methods [27, 22]. While these seminal works offer important insights, they do not directly address practical settings, specifically deep convolutional neural networks (CNNs) trained using gradient descent. Consequently, we currently don't know how the hierarchically compositional structure of the task influences the _sample complexity_, i.e., the number of data necessary to learn the task.

In this work, we adopt the physicist's approach [28, 29, 30, 31] of introducing a simplified model of data, which we then investigate quantitatively via a combination of theoretical arguments and numerical experiments. The task we consider, introduced in Section 1, is a multinomial classification where the class label is determined by the hierarchical composition of input features into progressively higher-level features (see Fig. 1). This model belongs to the class of generative models introduced in [27, 22], corresponding to the specific choice of random composition rules. More specifically, we consider a classification problem with \(n_{c}\) classes, where the class label is expressed as a hierarchy of \(L\)_randomly-chosen_ composition rules. In each rule, \(m\) distinct tuples of \(s\) adjacent low-level features are grouped together and assigned the same high-level feature taken from a finite vocabulary of size \(v\) (see Fig. 1). Then, in Section 3, we show empirically that the sample complexity \(P^{*}\) of deep CNNs trained with gradient descent scales as \(n_{c}m^{L}\). Furthermore, we find that \(P^{*}\) coincides with both _a)_ the number of data that allows for learning a representation that is invariant to exchanging the \(m\) semantically equivalent low-level features (subsection 3.1) and _b)_ the size of the training set for which the correlations between low-level features and class label become detectable (Section 4). Via _b)_, \(P^{*}\) can be derived under our assumption on the randomness of the composition rules.

## 1 The Random Hierarchy Model

In this section, we introduce our model task, which is a multinomial classification problem with \(n_{c}\) classes, where the input-output relation is _compositional_, _hierarchical_, and _local_. To build the dataset, we let each class label \(\alpha\!=\!1,\ldots,n_{c}\) generate the set of input data with label \(\alpha\) as follows.

1. Each label generates \(m\) distinct representations consisting of \(s\)-tuples of _high-level features_ (see Fig. 2 for an example with \(s\!=\!2\) and \(m\!=\!n_{c}\!=\!3\)). Each of these features belongs to a finite vocabulary of size \(v\) (\(v\!=\!3\) in the figure), so that there are \(v^{s}\) possible representations and \(n_{c}m\!\leq\!v^{s}\). We call the assignment of \(m\) distinct \(s\)-tuples to each label a _composition rule_;1 Footnote 1: Composition rules are called _production rules_ in formal language theory [32].
2. Each of the \(v\) high-level feature (level-\(L\)) generates \(m\) distinct representations of \(s\) sub-features (level-(\(L\!-\!1\))), out of the \(v^{s}\) possible ones. Thus, \(m\leq v^{s-1}\). After two generations, labels are represented as \(s^{2}\)-tuples and there are \(m\times m^{s}\) data per class;
3. The input data are obtained after \(L\) generations (level-1 representation) so that each datum \(\mathbf{x}\) consists of \(d\!=\!s^{L}\) input features \(x_{j}\). We apply one-hot encoding to the input features: each of the \(x_{j}\)'s is a \(v\)-dimensional sequence with one element set to 1 and the others to 0, the index of the non-zero component representing the encoded feature. The number of data per class is \[m\times m^{s}\times\cdots\times m^{s^{L-1}}=m^{\sum_{i=0}^{L-1}s^{i}}=m^{\frac{ L-1}{s-1}},\] (1) hence the total number of data \(P_{\text{max}}\) reads \[P_{\text{max}}\equiv n_{c}m^{\frac{L-1}{s-1}}=n_{c}m^{\frac{d-1}{s-1}}.\] (2) A generic classification task is thus specified by \(L\) composition rules and can be represented as a \(s\)-ary tree--an example with \(s\!=\!2\) and \(L\!=\!3\) is shown in Fig. 1(c) as a binary tree. The tree representation highlights that the class label \(\alpha(\mathbf{x})\) of a datum \(\mathbf{x}\) can be written as a hierarchical composition of \(L\) local functions of \(s\) variables [20, 21]. For instance, with \(s\!=\!L\!=\!2\) (\(\mathbf{x}\!=\!(x_{1},x_{2},x_{3},x_{4})\)),

\[\alpha(x_{1},\ldots,x_{4})=g_{2}\left(g_{1}(x_{1},x_{2}),g_{1}(x_{3},x_{4}) \right), \tag{3}\]
where \(g_{1}\) and \(g_{2}\) represent the 2 composition rules.

In the _Random Hierarchy Model_ (RHM) the \(L\) composition rules are chosen uniformly at random over all the possible assignments of \(m\) low-level representations to each high-level feature. As sketched in Fig. 2, the random choice induces correlations between low- and high-level features. In simple terms, each of the high-level features--1, 2 or 3 in the figure--is more likely to be represented with a certain low-level feature in a given position--blue on the left for 1, yellow for 2 and green for 3. These correlations are crucial for our predictions and are analyzed in detail in Appendix B.

Let us remark that the \(L\) composition rules can be chosen such that the low-level features are homogeneously distributed across high-level features for all positions, as sketched in Fig. 3. We refer to this choice as the _Homogeneous Features Model_. In this model, none of the low-level features is predictive of the high-level feature. With \(s\!=\!2\) and Boolean features \(v=m=2\), the Homogeneous Features Model reduces to the problem of learning a parity function [33].

Finally, note that we only consider the case where the parameters \(s\), \(m\) and \(v\) are constant through the hierarchy levels for clarity of exposition. It is straightforward to extend the model, together with the ensuing conclusions, to the case where all the levels of the hierarchy have different parameters.

Figure 1: Illustrating the hierarchical structure of real-world and artificial data. (a) An example of the hierarchical structure of images: the class (dog) consists of high-level features (head, paws), that in turn can be represented as sets of lower-level features (eyes, nose, mouth, and ear for the head). Notice that, at each level, there can be multiple combinations of low-level features giving rise to the same high-level feature. (b) A similar hierarchical structure can be found in natural language: a sentence is made of clauses, each having different parts such as subject and predicate, which in turn may consist of several words. (c) An illustration of the artificial data structure we propose. The samples reported here were drawn from an instance of the Random Hierarchy Model for depth \(L=3\) and tuple length \(s=2\). Different features are shown in different colors.

Figure 2: Label to lower-level features mapping in the Random Hierarchy Model (RHM). Each of the \(n_{c}\!=\!3\) classes (numbered boxes at the top) corresponds to \(m\!=\!3\) distinct couples (unnumbered boxes at the bottom) of features. These features belong to a finite vocabulary (blue, orange and green, with size \(v\!=\!3\)). Iterating this mapping \(L\) times with the lower-level features as high-level features of the next step yields the full dataset. Notice that some features appear more often in the representation of a certain class than in those of the others, e.g. blue on the left appears twice in class 1, once in class 2 and never in class 3. As a result, low-level features are generally correlated with the label.
## 2 Characteristic Sample Sizes

The main focus of our work is the answer to the following question:

**Q:**: _How much data is required to learn a typical instance of the Random Hierarchy Model?_

In this section, we first discuss two characteristic scales of the number of training data for an RHM with \(n_{c}\) classes, vocabulary size \(v\), multiplicity \(m\), depth \(L\), and tuple size \(s\). The first, related to the curse of dimensionality, represents the sample complexity of methods that are not able to learn the hierarchical structure of the data. The second, which comes from information-theoretic considerations, represents the minimal number of data necessary to reconstruct an instance of the RHM. These two sample sizes can be thought of as an upper and lower bound to the sample complexity of deep CNNs, which indeed lies between the two bounds (cf. Section 3).

### Curse of Dimensionality (\(P_{\max}\))

Let us recall that the curse of dimensionality predicts an exponential growth of the sample complexity with the input dimension \(d\!=\!s^{L}\). Fig. 4 shows the test error of a one-hidden-layer fully-connected network trained on instances of the RHM while varying the number of training data \(P\) (see methods for details of the training procedure) in the maximal \(m\) case, \(m\!=\!v^{s-1}\). The bottom panel demonstrates that the sample complexity is proportional to the total dataset size \(P_{\max}\). Since, from Eq. 2, \(P_{\max}\) grows exponentially with \(d\), we conclude that shallow fully-connected networks suffer from the curse of dimensionality. By contrast, we will see that using CNNs results in a much gentler growth (i.e. polynomial) of the sample complexity with \(d\).

### Information-Theoretic Limit (\(P_{\min}\))

An algorithm with full prior knowledge of the generative model can reconstruct an instance of the RHM with a number of points \(P_{\min}\!\ll\!P_{\max}\). For instance, we can consider an extensive search within the hypothesis class of all possible hierarchical models with fixed \(n_{c}\), \(m\), \(v\), and \(L\). Then, if \(n_{c}\!=\!v\) and \(m\!=\!v^{s-1}\), so that the model generates all possible input data, we can use a classical result of the PAC (Probably Approximately Correct) framework of statistical learning theory [34] to relate \(P_{\min}\) with the logarithm of the cardinality of the hypothesis class, that is the number of possible instances of the hierarchical model. The number of possible composition rules equals the number of ways of allocating \(v^{s-1}\) of \(v^{s}\) possible tuples to each

Figure 4: **Sample complexity for one-hidden-layer fully-connected networks, \(v\!=\!n_{c}\!=\!m\) and \(s\!=\!2\). Top: Test error vs. the number of training data. Different colors correspond to different vocabulary sizes \(v\). Bottom: number of data corresponding to test error \(\epsilon\!=\!0.7\) as a function of \(P_{\max}\). The black dashed line indicates a linear relationship: one-hidden-layer fully-connected networks achieve a small test error only when trained on a finite fraction of the whole dataset, thus their sample complexity grows exponentially with the input dimension.**

Figure 3: Label to lower-level features mapping in the Homogeneous Feature Model with \(v\!=\!m\!=\!n_{c}\!=\!3\) and \(s\!=\!2\). In contrast with the case illustrated in Fig. 2, this mapping is such that each of the 3 possible low-level features appears exactly once in each of the 2 elements of the representation of each class. In maths, denoting with \(N_{i}(\mu;\alpha)\) the number of times that the low-level feature \(\mu\) appears in the \(i\)-th position of the representation of class \(\alpha\), one has that \(N_{i}(\mu;\alpha)\!=\!1\) for all \(i\!=\!1\), 2, for all \(\mu\!=\!\text{green}\), blue, orange and for all \(\alpha\!=\!1\), 2, 3.
of the \(v\) classes/features, i.e., a multinomial coefficient,

\[\#\left\{\text{rules}\right\}=\frac{(v^{s})!}{((v^{s-1})!)^{v}} \tag{4}\]

Since an instance consists of \(L\) independently chosen composition rules, we have

\[\#\left\{\text{instances}\right\}=\left(\#\left\{\text{rules}\right\}\right)^{L} \left(\frac{1}{v!}\right)^{L-1} \tag{5}\]

where the additional multiplicative factor \((v!)^{1-L}\) takes into account that the input-label mapping is invariant for relabeling of the features of the \(L-1\) internal representations. Upon taking the logarithm and approximating the factorials for large \(v\) via Stirling's formula,

\[P_{\text{min}}=\log\left(\#\left\{\text{instances}\right\}\right)\xrightarrow{ v\gg 1}Lv^{s}, \tag{6}\]

Intuitively, the problem boils down to understanding the \(L\) composition rules, each needing \(m\times v\) examples (\(v^{s}\) for \(m\!=\!v^{s-1}\)). \(P_{\text{min}}\) grows only linearly with the depth \(L\)--hence logarithmically in \(d\)--whereas \(P_{\text{max}}\) is exponential in \(d\). Having used full knowledge of the generative model, \(P_{\text{min}}\) can be thought of as a lower bound for the sample complexity of a generic supervised learning algorithm which is agnostic of the data structure.

## 3 Sample Complexity of Deep CNNs

In this section, we focus on deep learning methods. In particular, we ask

**Q:**: _How much data is required to learn a typical instance of the Random Hierarchy Model with a deep CNN?_

Thus, after generating an instance of the RHM with fixed parameters \(n_{c}\), \(s\), \(m\), \(v\), and \(L\), we train a deep CNN with \(L\) hidden layers, filter size and stride equal to \(s\) (see Fig. 5 for an illustration) with stochastic gradient descent (SGD) on \(P\) training points selected at random among the RHM data. Further details of the training are in _Materials and Methods_.

By looking at the test error of trained networks as a function of the training set size (top panels of Fig. 6 and Fig. 7, see also Fig. 15 in G for a study with varying \(n_{c}\)), we notice the existence of a characteristic value of \(P\) where the error decreases dramatically, thus the task is learned. In order to study the behavior of this threshold with the parameters of the RHM, we define the sample complexity as the smallest \(P\) such that the test error \(\epsilon(P)\) is smaller than \(\epsilon_{\text{rand}}/10\), with \(\epsilon_{\text{rand}}\!=\!1-n_{c}^{-1}\) denoting the average error when choosing the label uniformly at random. The bottom panels of Fig. 6 (for the case \(n_{c}\!=\!m\!=\!v\)) and Fig. 7 (with \(m\!<\!v\), see G for varying \(n_{c}\)) show that the sample complexity scales as

\[P^{\star}=n_{c}m^{L}\Leftrightarrow\frac{P^{\star}}{n_{c}}=d^{\ln(m)/\ln(s)}, \tag{7}\]

independently of the vocabulary size \(v\). 7 shows that deep CNNs only require a number of samples that scales as a power of the input dimension \(d\!=\!s^{L}\) to learn the RHM: the curse of dimensionality is beaten. This evidences the ability of CNNs to harness the hierarchical compositionality inherent to the task. The question then becomes: what mechanisms do these networks employ to achieve this feat?

### Emergence of Synonymic Invariance in Deep CNNs

A natural approach to learning the RHM would be to identifying the sets of \(s\)-tuples of input features that correspond to the same higher-level feature. Examples include the pairs of low-level features in Fig. 2 and Fig. 3 which belong to the same column. In general, we refer to \(s\)-tuples that share the same higher-level representation as _synonyms_. Identifying synonyms at the first level would allow us to replace each \(s\)-dimensional patch of the input with a single symbol, reducing the dimensionality of the problem from \(s^{L}\) to \(s^{L-1}\). Repeating this procedure \(L\) times would lead to the class labels and, consequently, to the solution of the task.

In order to test if deep CNNs trained on the RHM resort to a similar solution, we introduce the _synonymic sensitivity_, which is a measure of the invariance of any given function of the input with respect to the exchange of synonymic \(s\)-tuples. We define \(S_{k,l}\) as the sensitivity of the \(k\)-th layer representation of a trained network with respect to exchanges of synonymous tuples of level-\(l\) features.

Figure 5: Neural network architecture that matches the RHM hierarchy. This is a deep CNN with \(L\) hidden layers, and stride and filter size equal to the tuple length \(s\). Filters that act on different input patches are the same (weight sharing). The number of input channels equals \(v\) and the output is a vector of size \(n_{c}\).
Namely,

\[S_{k,l}=\frac{\langle\|f_{k}(x)-f_{k}(P_{l}x)\|^{2}\rangle_{x,P_{l}}}{\langle\|f_ {k}(x)-f_{k}(z)\|^{2}\rangle_{x,z}}, \tag{8}\]

where: \(f_{k}\) is the vector of the activations of the \(k\)-th layer in the network; \(P_{l}\) is an operator that replaces all the level-\(l\) tuples with synonyms selected uniformly at random; \(\langle\cdot\rangle\) with subscripts \(x,z\) denote an average over all the inputs in an instance of the RHM; the subscript \(P_{l}\) denotes average over all the exchanges of synonyms.

In particular, \(S_{k,1}\) quantifies the invariance of the hidden representations learned by the network at layer \(k\) with respect to exchanges of synonym tuples of input features. Fig. 8 reports \(S_{2,1}\) as a function of the training set size \(P\) for different combinations of the model parameters. We focused on \(S_{2,1}\)--the sensitivity of the second layer of the deep CNN to permutations at the first level of the hierarchy--since synonymic invariance can generally be achieved at all layers \(k\) starting from \(k=l+1\), and not before 2 Notice that all curves display a sigmoidal shape, signaling the existence of a characteristic sample size which marks the emergence of synonymic sensitivity in the learned representations. Remarkably, by rescaling the \(x\)-axis by the sample complexity of Eq. 7 (bottom panel), curves corresponding to different parameters collapse. We conclude that the generalization ability of a network relies on the synonymic invariance of its hidden representations.

Footnote 2: To illustrate this, consider a hierarchy of depth \(L=2\), \(s=2\), and a two-hidden-layers CNN. In the general case, synonymic invariance to permutations at level one, cannot be achieved at the first layer of the network. This is because, say a level-\(1\) feature can be represented at the input as \((\alpha,\beta)\), \((\alpha,\alpha)\) and \((\beta,\alpha)\), but not as \((\beta,\beta)\). Then, it is impossible to build a neuron that would have the same response to the first three pairs but not the fourth. Instead, a simple solution exists for layer \(2\) to become invariant to exchanges at level \(1\). This consists in building \(v^{2}\) neurons at the first layer \(k=1\), each responding to one input pair. Clearly, the representation at \(k=1\) is not invariant to the substitution of synonyms. The second layer, though, can assign identical weights to all the \(v\) neurons that encode for the same feature, hence becoming invariant to permutations at \(l=1\).

Measures of the synonymic sensitivity \(S_{k,1}\) for different layers \(k\) are reported in Fig. 9 (blue lines), showing indeed that small values of \(S_{k,1}\) are achieved for \(k\!\geq\!2\). Fig. 9 also shows the sensitivities to exchanges of synonyms in the higher-level representations of the RHM: all levels are learned together as \(P\) increases, and invariance to level-\(l\) exchanges is achieved at layer \(k=l+1\), as expected. The figure displays the test error too (gray dashed), to further emphasize its correlation with synonymic invariance.

Figure 6: **Sample complexity for deep CNNs, \(m=n_{c}=v\) and \(s=2\). Top: Test error vs number of training points. Different colors correspond to different vocabulary sizes \(v\). Markers to hierarchy depths \(L\). Deep CNNs are able to achieve zero generalization error when enough training points are provided. Bottom: sample complexity \(P^{*}\) corresponding to a test error \(\epsilon^{*}=0.1\). Remarkably, the neural networks can generalize with a number of samples \(P^{*}=v^{L+1}\ll P_{\text{max}}\).**

Figure 7: **Sample complexity for deep CNNs, \(m<v\), \(n_{c}=v\) and \(s=2\). Top: Test error vs number of training points. Different colors correspond to different vocabulary sizes \(v\). Markers to hierarchy depths \(L\). Bottom: sample complexity \(P^{*}\) corresponding to a test error \(\epsilon^{*}=0.1\). Similarly to the previous plot, this confirms that the sample complexity of deep CNNs scales as \(P^{*}=n_{c}m^{L}\).**
## 4 Correlations Govern Synonymic Invariance

We now provide a theoretical argument for understanding the scaling of \(P^{*}\) of Eq. 7 with the parameters of the RHM. First, we compute a third characteristic sample size \(P_{c}\), defined as the size of the training set for which the _local_ correlation between any of the input patches and the label becomes detectable. Remarkably, \(P_{c}\) coincides with \(P^{*}\) of Eq. 7. Secondly, we demonstrate how a one-hidden-layer neural network acting on a single patch can use such correlations to build a synonymic invariant representation in a single step of gradient descent, so that \(P_{c}\) and \(P^{*}\) also correspond to the emergence of an invariant representation.

### Identify Synonyms by Counting

The invariance of the RHM labels with respect to exchanges of synonymous input patches can be inferred by counting the occurrences of such patches in all the data belonging to a given class \(\alpha\). Intuitively, tuples of features that appear with identical frequencies are likely synonyms. More specifically, let us denote an \(s\)-dimensional input patch with \(\mathbf{x}_{j}\) for \(j\) in \(1,\ldots,s^{L-1}\), a \(s\)-tuple of input features with \(\mathbf{\mu}\!=\!(\mu_{1},\ldots,\mu_{s})\), and the number of data in class \(\alpha\) which display \(\mathbf{\mu}\) in the \(j\)-th patch with \(N_{j}(\mathbf{\mu};\alpha)\). Normalizing this number by \(N_{j}(\mathbf{\mu})\!=\!\sum_{\alpha}N_{j}(\mathbf{\mu};\alpha)\) yields the conditional probability \(f_{j}(\alpha|\mathbf{\mu})\) for a datum to belong to class \(\alpha\) conditioned on displaying the \(s\)-tuple \(\mathbf{\mu}\) in the \(j\)-th input patch,

\[f_{j}(\alpha|\mathbf{\mu}):=\Pr\left\{\mathbf{x}\in\alpha|\mathbf{x}_{j}=\mathbf{\mu}\right\}= \frac{N_{j}(\mathbf{\mu};\alpha)}{N_{j}(\mathbf{\mu})}.\lx@note{footnote}{The notation $\mathbf{x}_{j}\!=\!\mathbf{\mu}$ means that the elements of the patch $\mathbf{x}_{j}$ encode the tuple of features $\mathbf{\mu}$}\]

If the low-level features are homogeneously spread across classes, as in the Homogeneous Features Model of Fig. 3, then \(f\!=\!n_{c}^{-1}\), independently of and \(\alpha\), \(\mathbf{\mu}\) and \(j\). In contrast, due to the aforementioned correlations, the probabilities of the RHM are all different from \(n_{c}^{-1}\) (see Fig. 2). We refer to this difference as _signal_.4 Distinct level-1 tuples \(\mathbf{\mu}\) and \(\mathbf{\nu}\) yield a different \(f\) (and thus a different signal) with high probability unless they share the same level-2 representation. Therefore, this signal can be used to identify synonymous level-1 tuples.

Footnote 4: Cases in which all features are homogeneously spread across classes can also appear in the RHM, but with vanishing probability in the limit of large \(n_{c}\) and \(m\), see Appendix E.

### Signal vs. Sampling Noise

When measuring the conditional class probabilities with only \(P\) training data, the occurrences in the right-hand side

Figure 8: Sensitivity \(S_{2,1}\) of the second layer of a deep CNN to permutations in the first level of the RHM with \(L=2,3\), \(s=2\), \(n_{c}=m=v\), as a function of the training set size (top) and after rescaling by \(P^{*}=n_{c}m^{L}\) (bottom). Sensitivity decreases from 1 to approximately zero, i.e. deep CNNs are able to learn synonymic invariance with enough training points. The collapse after rescaling highlights that this can be done with \(P^{*}\) training points.

Figure 9: Permutation sensitivity \(S_{k,l}\) of the layers of a deep CNN trained on the RHM with \(L=3\), \(s=2\), \(n_{c}=m=v=8\), as a function of the training set size \(P\). The permutation of synonyms is performed at different levels, as indicated in colors. The different panels correspond to the sensitivity of different layers’ activations, indicated by the gray box. Synonymic invariance is learned at the same time for all layers, and most of the invariance to level \(l\) is obtained at layer \(k=l+1\).
of Eq. 24 are replaced with empirical occurrences, which induce a sampling _noise_ on the \(f\)'s. For the identification of synonyms to be possible, this noise must be smaller in magnitude than the aforementioned signal--a visual representation of the comparison between signal and noise is depicted in Fig. 10.

The magnitude of the signal can be computed as the ratio between the standard deviation and mean of \(f_{j}(\alpha|\mathbf{\mu})\) over realizations of the RHM. The full calculation is presented in Appendix B: here we present a simplified argument based on an additional independence assumption. Given a class \(\alpha\), the tuple \(\mathbf{\mu}\) appearing in the \(j\)-th input patch is determined by a sequence of \(L\) choices--one choice per level of the hierarchy--of one among \(m\) possible lower-level representations. These \(m^{L}\) possibilities lead to all the \(mv\) distinct \(s\)-tuples. \(N_{j}(\mathbf{\mu};\alpha)\) is proportional to how often the tuple \(\mathbf{\mu}\) is chosen--\(m^{L}/(mv)\) times on average. Under the assumption of independence of the \(m^{L}\) choices, the fluctuations of \(N_{j}(\mathbf{\mu};\alpha)\) relative to its mean are given by the central limit theorem and read \((m^{L}/(mv))^{-1/2}\) in the limit of large \(m\). If \(n_{c}\) is sufficiently large, the fluctuations of \(N_{j}(\mathbf{\mu})\) are negligible in comparison. Therefore, the relative fluctuations of \(f_{j}\) are the same as those of \(N_{j}(\mathbf{\mu};\alpha)\): the size of the signal is \((m^{L}/(mv))^{-1/2}\).

The magnitude of the noise is given by the ratio between the standard deviation and mean, over independent samplings of a training set of fixed size \(P\), of the empirical conditional probabilities \(\hat{f}_{j}(\alpha|\mathbf{\mu})\). Only \(P/(n_{c}mv)\) of the training points will, on average, belong to class \(\alpha\) while displaying feature \(\mu\) in the \(j\)-th patch. Therefore, by the convergence of the empirical measure to the true probability, the sampling fluctuations of \(\hat{f}\) relative to the mean are of order \([P/(n_{c}mv)]^{-1/2}\)--see Appendix B for details. Balancing signal and noise yields the characteristic \(P_{c}\) for the emergence of correlations. For large \(m\), \(n_{c}\) and \(P\),

\[P_{c}=n_{c}m^{L}, \tag{10}\]

which coincides with the empirical sample complexity of deep CNNs discussed in Section 3.

### Learning Synonymic Invariance by the Gradients

To complete the argument, we consider a simplified one-step gradient descent setting [35, 36], where \(P_{c}\) marks the number of training examples required to learn a synonymic invariant representation. In this setting (details presented in Appendix C), we train a one-hidden layer fully-connected network on the first \(s\)-dimensional patches of the data. This network cannot fit data which have the same features on the first patch while belonging to different classes. Nevertheless, the hidden representation of the network can become invariant to exchanges of synonymous patches.

More specifically, as we show in Appendix C, with identical initialization of the hidden weights and orthogonalized inputs, the update of the hidden representation \(f_{h}(\mathbf{\mu})\) of the \(s\)-tuple of low-level features \(\mathbf{\mu}\) after one step of gradient descent follows

\[\Delta f_{h}(\mathbf{\mu})=\frac{1}{P}\sum_{\alpha=1}^{n_{c}}a_{h, \alpha}\left(\hat{N}_{1}(\mathbf{\mu};\alpha)-\frac{1}{n_{c}}\sum_{\beta=1}^{n_{c }}\hat{N}_{1}(\mathbf{\mu};\beta)\right), \tag{11}\]

where \(f_{h}(\mathbf{\mu})\) coincides the pre-activation of the \(h\)-th neuron and \(\mathbf{a}_{h}\!=\!(a_{h,1},\ldots,a_{h,n_{c}})\) denotes the associated \(n_{c}\) dimensional readout weight. \(\hat{N}_{1}\) is used to denote the empirical estimate of the occurrences in the first input patch. Hence, by the result of the previous section, the hidden representation becomes insensitive to the exchange of synonymic features for \(P\!\gg\!P_{c}\).

This prediction is confirmed empirically in Fig. 11, which shows the sensitivity \(S_{1,1}\) of the hidden representation of shallow fully-connected networks trained in the setting of this section, as a function of the number \(P\) of training data for different combinations of the model parameters. The bottom panel, in particular, highlights that the sensitivity is close to 1 for \(P\!\ll\!P_{c}\) and close to 0 for \(P\!\gg\!P_{c}\). In addition, notice that the collapse of the pre-activations of synonymic tuples onto the same, synonymic invariant value, implies that the rank of the hidden weights matrix tends to \(v\)--the vocabulary size of higher-level features. This low-rank structure is typical in the weights of deep networks trained on image classification [37, 38, 39, 40].

Using all patches via weight sharing.Notice that using a one-hidden-layer CNN which looks at all patches via

Figure 10: **Signal vs. noise illustration.** The dashed function represents the distribution of \(f(\alpha|\mathbf{\mu})\) resulting from the random sampling of the RHM rules. The solid dots illustrate the _true_ frequencies \(f(\alpha|\mathbf{\mu})\) sampled from this distribution, with different colors corresponding to different groups of synonyms. The typical spacing between the solid dots, given by the width of the distribution, represents the _signal_. Transparent dots represent the empirical frequencies \(\hat{f}_{j}(\alpha|\mathbf{\mu})\), with dots of the same color corresponding to synonymous features. The spread of transparent dots of the same color, which is due to the finiteness of the training set, represents the _noise_.
weight sharing and global average pooling would yield the same result since the average over patches reduces both the signal and the noise by the same factor-see subsection C.1 for details.

Improved Performance via Clustering.Note that our signal-vs-noise argument is based on a single class \(\alpha\), as it considers the scalar quantity \(\hat{f}(\alpha|\mathbf{\mu})\). However, an observer seeking to identify synonyms could in principle use the information from all classes, represented by the \(n_{c}\)-dimensional vector of empirical frequencies \((\hat{f}(\alpha|\mathbf{\mu}))_{\alpha=1,\dots,n_{c}}\). Following this idea, one can devise a layer-wise algorithm where the representations of each layer are first updated with a single step of gradient descent (as in Eq. 82), then clustered into synonymic groups [22, 27]. Such an algorithm can solve the RHM with less than \(n_{c}m^{L}\) training points--\(\sqrt{n_{c}}m^{L}\) in the maximal dataset case \(n_{c}\!=\!v\) and \(m\!=\!v^{s-1}\), as we show empirically and justify theoretically in Appendix D. Notably, the dependence on the dimensionality \(m^{L}\) is unaffected by the change of algorithm, although the prefactor reveals the advantage of the dedicated clustering algorithm over standard CNNs.

## 5 Conclusions

We have introduced a hierarchical model of classification task, where each class is identified by a number of equivalent high-level features (synonyms), themselves consisting of a number of equivalent sub-features according to a hierarchy of random composition rules. First, we established via a combination of extensive experiments and theoretical arguments that the sample complexity of deep CNNs is a simple function of the number of classes \(n_{c}\), the number of synonymic features \(m\) and the depth of the hierarchy \(L\). This result provides a rule of thumb for estimating the order of magnitude of the sample complexity of real datasets. In the case of CIFAR10 [41], for instance, having 10 classes, taking reasonable values for the RHM parameters such as \(m\in[5,15]\) and \(L=3\), yields \(P^{*}\in[10^{3},3\times 10^{4}]\),comparable with the sample complexity of modern architectures (see Fig. 16 in Appendix G).

Secondly, our results indicate a separation between shallow networks, which are cursed by the input dimensionality, and sufficiently deep CNNs, which are not. We thus complement previous analyses based on expressivity [21] or information-theoretical considerations [24] with a generalization result.

Last but not least, we proposed to characterize the quality of internal representations with their sensitivity toward transformations of the data which leave the task invariant. This analysis bypasses the issues of previous characterizations. For example, approaches based on mutual information [12] that is ill-defined when the network representations are deterministic functions of the input [13]. Approaches based on intrinsic dimension [14, 15] can display counter-intuitive results, refer to Appendix F for a more in-depth discussion on the intrinsic dimension, and on how this quantity behaves in our setup. Interestingly, our approach supports that performance should strongly correlate with the invariance toward synonyms of the internal representation. This prediction could in principle be tested in natural language processing models, but also for image data sets by performing discrete changes to images that leave the class unchanged.

Looking forward, the Random Hierarchy Model is a rich but minimal model where open questions in the theory of deep learning could be clarified. For instance, a formidable challenge such as the description of the gradient descent dynamics of deep networks, becomes significantly simpler for the RHM, owing to the simple structure of the target representations. Other important questions, including the ability of fully-connected networks to learn

Figure 11: Synonymic sensitivity of the hidden representation vs \(P\) for a one-hidden-layer fully-connected network trained on the first patch of the inputs of an RHM with \(s\!=\!2\) and \(m\!=\!v\), for several values of \(L\), \(v\), and \(n_{c}\!\leq\!v\). The top panel shows the bare curves whereas, in the bottom panel, the x-axis is rescaled by \(P_{c}=n_{c}m^{L}\). The collapse of the rescaled curves highlights that \(P_{c}\) coincides with the threshold number of training data for building a synonymic invariant representation.
local connections [30, 42, 43], the benefits of residual connections [44] or the advantages of deep learning over kernel methods [45, 46, 25, 47] can be studied quantitatively within this model, as functions of the multiple parameters that define the hierarchical structure of the task.

## Materials and Methods

### Experimental Setup

The experiments are performed using the PyTorch deep learning framework [48]. The code used for the experiments is available online at [https://github.com/pcsl-epfl/hierarchy-learning](https://github.com/pcsl-epfl/hierarchy-learning).

### RHM implementation

The code implementing the RHM is available online at [https://github.com/pcsl-epfl/hierarchy-learning/blob/master/datasets/hierarchical.py](https://github.com/pcsl-epfl/hierarchy-learning/blob/master/datasets/hierarchical.py). The inputs sampled from the RHM are represented as a one-hot encoding of low-level features. This makes each input of size \(s^{L}\times v\). The inputs are whitened so that the average pixel value over channels is equal to zero.

### Model Architecture

One-hidden-layer fully-connected networks have input dimension equal to \(s^{L}\times v\), \(H=10^{4}\) hidden neurons, and \(n_{c}\) outputs. The deep convolutional neural networks (CNNs) have weight sharing, stride equal to filter size equal to \(s\) and \(L\) hidden layers. In this case, we set the width \(H\) to be larger than the number of possible \(s\)-tuples that can exist at a given layer, \(H\gg v^{s}\).

### Training Procedure

Neural networks are trained using stochastic gradient descent (SGD) on the cross-entropy loss, with a batch size of 128 and a learning rate equal to 0.3. Training is stopped when the training loss decreases below a certain threshold fixed to \(10^{-3}\).

### Measurements

The performance of the models is measured as the percentage error on a test set. The test set size is chosen to be \(\min(P_{\max}-P,\,20^{\prime}000)\). Synonymic sensitivity, as defined in Eq. 8, is measured on a test set of size \(\min(P_{\max}-P,\,1^{\prime}000)\). Reported results for a given value of RHM parameters are averaged over 10 jointly different instances of the RHM and network initializations.
