Solvable Model for the Linear Separability of Structured Data

Abstract

Linear separability, a core concept in supervised machine learning, refers to whether the labels of a data set can be captured by the simplest possible machine: a linear classifier. In order to quantify linear separability beyond this single bit of information, one needs models of data structure parameterized by interpretable quantities, and tractable analytically. Here, I address one class of models with these properties, and show how a combinatorial method allows for the computation, in a mean field approximation, of two useful descriptors of linear separability, one of which is closely related to the popular concept of storage capacity. I motivate the need for multiple metrics by quantifying linear separability in a simple synthetic data set with controlled correlations between the points and their labels, as well as in the benchmark data set MNIST, where the capacity alone paints an incomplete picture. The analytical results indicate a high degree of “universality”, or robustness with respect to the microscopic parameters controlling data structure.

1. Introduction

Linear classifiers are quintessential models of supervised machine learning. Despite their simplicity, or possibly because of it, they are ubiquitous: they are building blocks of more complex architectures, for instance, in deep learning and support vector machines, and they provide testing grounds of new tools and ideas in learning theory and statistical mechanics, in both the study of artificial neural networks and in neuroscience [1,2,3,4,5,6,7,8,9]. Recently, interest in linear classifiers was rekindled by two outstanding results. First, deep neural networks with wide layers can be well approximated by linear models acting on a well defined feature space, given by what is called “neural tangent kernel” [10,11]. Second, it was discovered that deep linear networks, albeit identical to linear classifiers for what concerns the class of realizable functions, allow it to reproduce and explain complex features of nonlinear learning and gradient flow [12].

In spite of the central role that linear separability plays in our understanding of machine learning, fundamental questions still remain open, notably regarding the predictors of separability in real data sets [13]. How does data complexity affect the performance of linear classifiers? Data sets in supervised machine learning are usually not linearly separable: the relations between the data points and their labels cannot be expressed as linear constraints. The first layers in deep learning architectures learn to perform transformations that enhance the linear separability of the data, thus providing downstream fully-connected layers with data points that are more adapted for linear readout [14,15]. The role of “data structure” in machine learning is a hot topic, involving computer scientists and statistical physicists, and impacting both applications and fundamental research in the field [16,17,18,19,20,21,22].

Before attempting to assess the effects of data specificities on models and algorithms of machine learning, and, in particular, on the simple case of linear classification, one should have available (i) a quantitative notion of linear separability and (ii) interpretable parameterized models of data structure. Recent advances, especially within statistical mechanics, mainly focused on point (ii). Different models of structured data have been introduced to express different properties that are deemed to be relevant. For example, the organization of data as the superposition of elementary features (a well-studied trait of empirical data across different disciplines [23,24,25]) leads to the emergence of a hierarchy in the architecture of Hopfield models [26]. Another example is the “hidden manifold model”, whereby a latent low-dimensional representation of the data is used to generate both the data points and their labels in a way that introduces nontrivial dependence between them [19]. An important class of models assumes that data points are samples of probability distributions that are supported on extended object manifold, which represent all possible variations of an input that should have no effect on its classification (e.g., differences in brightness of a photo, differences in aspect ratio of a handwritten digit) [27]. Recently, a useful parameterization of object manifolds was introduced that is amenable to analytical computations [28]; it will be described in detail below. In a data science perspective, these approaches are motivated by the empirical observation that data sets usually lie on low-dimensional manifolds, whose “intrinsic dimension” is a measure of the number of latent degrees of freedom [29,30,31].

The main aims of this article are two: (i) the discussion of a quantitative measure of linear separability that could be applied to empirical data and generative models alike; and, (ii) the definition of useful models expressing nontrivial data structure, and the analytical computation, within these models, of compact metrics of linear separability. Most works concerned with data structure and object manifolds (in particular, Refs. [8,27,28]) focus on a single descriptor of linear separability, namely the storage capacity ${\alpha }_{\mathrm{c}}$. Informally, the storage capacity measures the maximum number of points that a classifier can reliably classify; in statistical mechanics, it signals the transition, in the thermodynamic limit, between the SAT and UNSAT phases of the random satisfiability problem related to the linear separability of random data [32]. Here, I will present a more complete description of separability than the sole storage capacity (a further motivation is the discovery, within the same model of data structure, of other phenomena lying “beyond the storage capacity” [33]).

2. Linear Classification of Data

Let us first review the standard definition of linear separability for a given data set. In supervised learning, data are given in the form of pairs $({\xi }_{\mu },{\sigma }_{\mu })$, where ${\xi }_{\mu }\in {\mathbb{R}}^n$ is a data point and ${\sigma }_{\mu }=\pm 1$ is a binary label. We focus on dichotomies, i.e., classifications of the data into two subsets (hence, the binary labels); of course, this choice does not exclude datasets with multiple classes of objects, as one can always consider the classification of one particular class versus all the other classes. Given a set of points $X={\left\{{\xi }_{\mu }\right\}}_{\mu =1,\dots ,m}$, a dichotomy is a function $\varphi :X\to {\{-1,+1\}}^m$. A data set ${\left\{({\xi }_{\mu },{\sigma }_{\mu })\right\}}_{\mu =1,\dots ,m}$ is linearly separable (or equivalently the dichotomy $\varphi \left({\xi }_{\mu }\right)={\sigma }_{\mu }$, $\mu =1,\dots ,m$, is linearly realizable) if there exists a vector $w\in {\mathbb{R}}^n$, such that

$$sgn\left(\sum _{i=1}^n{w}_i·{\left({\xi }_{\mu }\right)}_i\right)={\sigma }_{\mu },\mu =1,\dots ,m,$$

(1)

where ${\left({\xi }_{\mu }\right)}_i$ is the ith component of the $\mu$th element of the set. In the following, I will simply write $w·{\xi }_{\mu }$ for the scalar product appearing in the sgn function when it is obvious that w and ${\xi }_{\mu }$ are vectors.

In machine learning, the left hand side of Equation (1) is the definition of a linear classifier, or perceptron. The points x, such that $w·x=0$ define a hyperplane, which is the separating surface, i.e., the boundary between points that are assigned different labels by the perceptron. By viewing the perceptron as a neural network, the vector w is the collection of the synaptic weights. “Learning” in this context refers to the process of adjusting the weight vector w so as to satisfy the m constraints in Equation (1). Because of the fact that the sgn function is invariant under multiplication of its argument by a positive constant, I will always consider normalized vectors, i.e., both the weight vector w and data points $\xi$ will lie on the unit sphere.

A major motivation behind the introduction of the concept of data structure and the combinatorial theory that is related to it (reviewed in Section 5 and Section 6 below) is the fact that the definition of linear separability above is not very powerful per se. Empirically relevant data sets are usually not linearly separable. Knowing whether a data set is linearly separable does not convey much information on its structure: crucially, it does not allow quantifying “how close” to being separable or nonseparable the data set really is. To fix the ideas, let us consider a concrete case: the data set MNIST [34]. MNIST is a collection of handwritten digits, digitized as $28\times 28$ greyscale images, each labelled by the corresponding digit (“0” to “9”). I will use the “training” subset of MNIST, containing 6000 images per digit. To simplify the discussion, I will mainly focus on a single dichotomy within MNIST: that expressed by the labels “3” and “7”. The particular choice of digits is unimportant for this discussion; I will give an example of another dichotomy below, when subtle differences between the digits can be observed.

One may ask the question as to whether the MNIST training set, as a whole, is linearly separable. However, the answer is not particularly informative: the MNIST training set is not linearly separable [34]. But how unexpected is this answer? Can we measure the surprise of finding out a given training set is or is not linearly separable? Intuitively, there are three different properties of a data set that facilitate or hinder its linear separability: size, dimensionality, and structure.

• Size. The number of elements m of a data set is a simple indication of its complexity. While a few data points are likely linearly separable, they convey little information on the “ground truth”, the underlying process that generated the data set. On the contrary, larger data sets are more difficult to classify, but the information that is stored in the weights after learning is expected to be more faithful to the ground truth (this is related to the concept of “sample complexity” in machine learning [35]).
• Dimensionality. There are two complementary aspects when considering dimensionality in a data oriented framework. First, the embedding dimension is the number of variables that a single data point comprises. For instance, MNIST points are embedded in ${\mathbb{R}}^{784}$, i.e., each of them is represented by 784 real numbers. The embedding dimension is n in Equation (1); therefore, n is also the number of degrees of freedom that a linear classifier can adjust to find a separating hyperplane. Hence, one expects that a large embedding dimension promotes linear separability. Second, the data set itself does not usually uniformly occupy the embedding space. Rather, points lie on a lower-dimensional manifold, whose dimension d is called the intrinsic dimension of the data set. The concept of general position discussed below is related to the intrinsic dimension; however, beyond that, I will not explicitly consider this type of data complexity in this article (for analytical results on the linear separability of manifolds of varying intrinsic dimension, see [27]).
• Structure. As I will show in a moment, the effects of size and dimensionality on linear separability are easily quantified in a simple null model. Data structure, on the other hand, has proved more challenging, and it is the main focus of the theory described here. There is no single definition of data structure; different definitions are useful in different contexts. A common characterization can be given like this: data have structure whenever the data points ${\xi }_{\mu }$ and their labels ${\sigma }_{\mu }$ are not independent variables. I will specify a more precise definition in Section 5. Intuitively, the data structure can both promote or preclude linear separability. If points that are close to one another tend to have the same label then linear separability is improved; if, instead, there are many differently labeled points in a small region of space, then linear separability is obstructed.

Let us get back to the question “how surprising is it that MNIST is not linearly separable?”. This question should be answered by at least taking into account the first two properties described above, the size of the data set and its dimensionality, which are readily computed from the raw data. In fact, the surprise, i.e., the divergence from what is expected based on size and dimensionality, may be interpreted as a beacon of the third property: data structure. I will show in the next section that the answer to our question is “exceedingly unsurprising”. Yet, a slightly modified question will reveal that MNIST, albeit unremarkable in it not being linearly separable, is exceptionally structured.

3. Null Model of Linear Separability

Let us consider a null model of data that fixes the dimension n and the size p. I use a different letter (p instead of m), because it will be useful below to have two different symbols for the size of the whole data set (m) and for the size of its subsets. Consider a data set $Z_p={\left\{({\xi }_{\mu },{\sigma }_{\mu })\right\}}_{\mu =1,\dots ,p}$, where the vectors ${\xi }_{\mu }$ are random independent variables that are uniformly distributed on the unit sphere, and the labels ${\sigma }_{\mu }$ are independent Bernoulli random variables (also independent from every ${\xi }_{\mu }$). These choices are suggested by a maximum entropy principle, when only the parameters m and n are fixed. What is the probability that a data set generated by this model is linearly separable? This problem was addressed and solved more than half a century ago [36,37,38]; In Section 6 I will describe an analytical technique that allows this computation. The fraction of dichotomies of a random data set that are linearly realizable is

$$c_{n,p}=2^{1-p}\sum _{i=0}^{n-1}\left(\genfrac{}{}{0pt}{}{p-1}{i}\right),$$

(2)

where $\left(\genfrac{}{}{0pt}{}{·}{·}\right)$ is the binomial coefficient. Thus, a random (uniform) dichotomy has probability $c_{n,p}$ of being linearly realizable. In this article, I will refer to the probability $c_{n,p}$ as the separability, or probability of separation. A related quantity is the number of dichotomies $C_{n,p}=2^p{c}_{n,p}$ (here, $2^p$ is the total number of dichotomies of p points).

Figure 1 shows the sigmoidal shape of $c_{n,p}$ as a function of p at fixed n. The separability is exactly equal to 1 up to $p=n$ (which pinpoints what is known as the Vapnik–Chervonenkis dimension in statistical learning theory [35]), and it stays close to 1 up to a critical value $p_{\mathrm{c}}$, which increases with n. At $p_{\mathrm{c}}$, the curve steeply drops to asymptotically vanishing values, the more abruptly the larger is n. Rescaling the number of points p with the dimension n yields the load $\alpha =p/n$. As a function of $\alpha$, the probability of separation has the remarkable property of being equal to $1/2$ at the critical value (that is known as the storage capacity) ${\alpha }_{\mathrm{c}}=p_{\mathrm{c}}/n=2$, independently of n. Such an absence of finite size corrections to the location of the critical point is an unusual feature, which will be lost when we consider structured data below. In the large-n limit, $c_{n,\alpha n}$ converges to a step function that transitions from 1 to 0 at ${\alpha }_{\mathrm{c}}$.

How large is the probability of separation $c_{n,m}$ that is given by Equation (2) when one substitutes the sample size m = 12,000 and the dimensionality $n=784$, i.e., those of the dichotomy “3”/“7” in the data set MNIST? The probability, as anticipated, is utterly small, less than ${10}^{-2000}$: it should be no surprise that MNIST is not linearly separable. This comparison is not completely fair, because of the assumption, underlying Equation (2), of general position. The concept of general position is an extension of that of linear independence, which is useful for sets larger than the dimension of the vector space. A set X of vectors in ${\mathbb{R}}^n$ is in a general position if there is no linearly dependent subset $X^{\prime }\subseteq X$ of cardinality less than or equal to n. MNIST is quite possibly not in general position. To make sure that it is, I downscaled each image to $10\times 10$ pixels and only considered 1000 images per class (to allow for faster numerical computations), and applied mild multiplicative random noise, by flipping $5\%$ of the pixels around the middle grey value (see Figure 2); I will refer to this modified dataset as “rescaled MNIST”. Running the standard perceptron algorithm on rescaled MNIST did not show signs of convergence after ${10}^5$ iterations, which indicated that the data set is likely not linearly separable. For $m=2000$ and $n=100$, the separability $c_{n,m}$ is less than ${10}^{-400}$.

The null model provides a simple concise interpretation of the linear separability of a given data set, given its size m and dimensionality n, in terms of 5 possible outcomes (see Figure 1, bottom panel):

• The set is linearly separable and it lies in the region where $c_{n,m}\approx 1$. Separability here is trivial: almost all data sets are separable in this region, provided that the points are in general position.
• The set is not linearly separable and it lies in the region where $c_{n,m}\approx 1$. The only way this can happen for $m\le n$ is if the points are not in a general position. For $m>n$, but still in this region, the lack of separability could also be attributed to a non-trivial data structure.
• The set is not linearly separable and it lies in the region where $c_{n,m}\approx 0$. Almost no dichotomy is linearly realizable in this region; therefore, the lack of separability is trivial here.
• The set is linearly separable and it lies in the region where $c_{n,m}\approx 0$. This situation is the hallmark of data structure. The fact that the data set happens to represent one of the few dichotomies that are linearly realizable in this region indicates a non-null dependence between the labels and the points in the data set.
• The set lies in the region where $c_{n,m}$ is significantly different from 0 and 1. Here, knowing that a data set is linearly separable or not is unsurprising either way. The location and the width of this “transition region” are the two main parameters that summarize the shape of the separability curve. In Section 6 I will show how to compute these quantities within a more general model that includes data structure.

4. Quantifying Linear Separability via Relative Entropy

In order to make a step further in the characterization of the linear separability of (rescaled) MNIST, we can consider its subsets. While there is only one subset with $m=2000$ points (focusing on the dichotomy “3”/“7”), and only one yes/no answer to the question of its linear separability, there are many subsets of size $p<m$, which can provide more detailed information. To quantify such information, let us formulate a more precise notion of surprise with respect to a model expressing prior expectation [39]. Let us again fix an empirical data set $Z_m={\left\{({\xi }_{\mu },{\sigma }_{\mu })\right\}}_{\mu =1,\dots ,m}$ and fix $p\le m$. Now, consider the set $N_p$ of all subsets $\nu =\{{\nu }_1,\dots ,{\nu }_p\}$ of p indices ${\nu }_i\in \{1,\dots ,m\}$, with ${\nu }_i\ne {\nu }_j$ for $i\ne j$. Additionally, consider the set ${\Sigma }_p={\{-1,+1\}}^p$ of all dichotomies $\widehat{\sigma }=\{{\widehat{\sigma }}_1,\dots ,{\widehat{\sigma }}_p\}$ of p elements. (I use curly braces for both sets and indexed families.) For each pair $\left(\nu \in N_p,\widehat{\sigma }\in {\Sigma }_p\right)$, we can construct the corresponding synthetic dataset

$$Z(\nu ,\widehat{\sigma })={\left\{({\xi }_{{\nu }_i},{\widehat{\sigma }}_i)\right\}}_{i=1,\dots ,p};$$

(3)

similarly, for each $\nu \in N_p$, we can construct the corresponding subset $Z_{\mathrm{emp}}\left(\nu \right)$ of the empirical data set $Z_m$:

$$Z_{\mathrm{emp}}\left(\nu \right)={\left\{({\xi }_{{\nu }_i},{\sigma }_{{\nu }_i})\right\}}_{i=1,\dots ,p}.$$

(4)

The main tool for defining the surprise will be probability distributions on a space ${\mathsf{\Omega }}_p$, which is defined as the union of all synthetic data sets:

$${\mathsf{\Omega }}_p=\bigcup _{\left(\nu ,\widehat{\sigma }\right)\in N_p\times {\Sigma }_p}Z(\nu ,\widehat{\sigma }).$$

(5)

The empirical space ${\mathsf{\Omega }}_p^{\mathrm{emp}}\subseteq {\mathsf{\Omega }}_p$ can be defined similarly:

$${\mathsf{\Omega }}_p^{\mathrm{emp}}=\bigcup _{\nu \in N_p}{Z}_{\mathrm{emp}}\left(\nu \right).$$

(6)

Essentially, ${\mathsf{\Omega }}_p^{\mathrm{emp}}$ contains all collections of p point/label pairs in the data set $Z_m$, while ${\mathsf{\Omega }}_p$ contains all the collections of p point/label pairs where the p points are chosen among the ones in the data set and the labels are all possible $2^p$ combinations on those p points. Notice that ${\mathsf{\Omega }}_p$ and ${\mathsf{\Omega }}_p^{\mathrm{emp}}$ have different cardinalities: $|{\mathsf{\Omega }}_p^{\mathrm{emp}}|=M_p$ and $|{\mathsf{\Omega }}_p|=2^p{M}_p$, where $M_p=\left(\genfrac{}{}{0pt}{}{m}{p}\right)$ is the number of subsets of size p in the data set.

Interpreted as a probability distribution on ${\mathsf{\Omega }}_p$, the empirical data are uniform distributed on ${\mathsf{\Omega }}_p^{\mathrm{emp}}$; likewise, the null model defined above induces, by conditioning on the points $\left\{{\xi }_{\mu }\right\}$, the uniform distribution on the whole ${\mathsf{\Omega }}_p$. In general, not every data set in ${\mathsf{\Omega }}_p$ (nor in ${\mathsf{\Omega }}_p^{\mathrm{emp}}$) is linearly separable. Let us define the subsets for which this property holds:

$$\begin{array}{cc}\hfill & {\widehat{\mathsf{\Omega }}}_p=\left\{Z\in {\mathsf{\Omega }}_p:Z \mathrm{is} \mathrm{linearly} \mathrm{separable}\right\}\hfill \\ \hfill & {\widehat{\mathsf{\Omega }}}_p^{\mathrm{emp}}=\left\{Z\in {\mathsf{\Omega }}_p^{\mathrm{emp}}:Z \mathrm{is} \mathrm{linearly} \mathrm{separable}\right\}.\hfill \end{array}$$

(7)

Let us call $Q_p$ and $Q_p^{\mathrm{emp}}$ the uniform probability distributions on ${\widehat{\mathsf{\Omega }}}_p$ and ${\widehat{\mathsf{\Omega }}}_p^{\mathrm{emp}}$, respectively. The Kullback–Leibler (KL) divergence $D_{\mathrm{KL}}\left(Q_p^{\mathrm{emp}}\left|\right|Q_p\right)$ from $Q_p$ to $Q_p^{\mathrm{emp}}$ (or relative entropy)

$$D_{\mathrm{KL}}\left(Q_p^{\mathrm{emp}}\left|\right|Q_p\right)=\sum _{z\in {\mathsf{\Omega }}_p}{Q}_p^{\mathrm{emp}}log\frac{Q_p^{\mathrm{emp}}}{Q_p}$$

(8)

then measures the surprise carried by the data with respect to the prior belief regarding its linear separability expressed by $Q_p$. Because $Q_p$ and $Q_p^{\mathrm{emp}}$ are defined on sets (${\mathsf{\Omega }}_p$ and ${\mathsf{\Omega }}_p^{\mathrm{emp}}$) of different cardinality, I define the (signed) surprise ${\mathcal{S}}_p$ by subtracting the reference KL divergence between the uniform distributions on these spaces:

$$\begin{array}{cc}\hfill {\mathcal{S}}_p& =D_{\mathrm{KL}}\left(Q_p^{\mathrm{emp}}\left|\right|Q_p\right)-log\left(\left|{\mathsf{\Omega }}_p\right|/\left|{\mathsf{\Omega }}_p^{\mathrm{emp}}\right|\right)\hfill \\ \hfill & =D_{\mathrm{KL}}\left(Q_p^{\mathrm{emp}}\left|\right|Q_p\right)-plog2.\hfill \end{array}$$

(9)

Notice that the summand in the definition of KL divergence, Equation (8), is only nonzero for $z\in {\widehat{\mathsf{\Omega }}}_p^{\mathrm{emp}}$; one then obtains

$$\begin{array}{cc}\hfill {\mathcal{S}}_p& =\sum _{z\in {\widehat{\mathsf{\Omega }}}_p^{\mathrm{emp}}}\frac{1}{|{\widehat{\mathsf{\Omega }}}_p^{\mathrm{emp}}|}log\frac{|{\widehat{\mathsf{\Omega }}}_p|}{|{\widehat{\mathsf{\Omega }}}_p^{\mathrm{emp}}|}-plog2\hfill \\ \hfill & =log\frac{|{\widehat{\mathsf{\Omega }}}_p|}{|{\widehat{\mathsf{\Omega }}}_p^{\mathrm{emp}}|}-plog2\hfill \\ \hfill & =log\frac{c_{n,p}{M}_p{2}^p}{|{\widehat{\mathsf{\Omega }}}_p^{\mathrm{emp}}|}-plog2\hfill \\ \hfill & =log{c}_{n,p}-log{c}_{n,p}^{\mathrm{emp}},\hfill \end{array}$$

(10)

where I have defined the empirical separability $c_{n,p}^{\mathrm{emp}}$ as the fraction of linearly separable subsets of size p in $Z_m$:

$$c_{n,p}^{\mathrm{emp}}=\frac{|{\widehat{\mathsf{\Omega }}}_p^{\mathrm{emp}}|}{M_p}.$$

(11)

The signed surprise ${\mathcal{S}}_p$ is positive (respectively negative) when the fraction of linearly separable subsets of size p is smaller (respectively larger) than expected in the null model.

Separability in a Synthetic Data Set and in MNIST

The discussion above encourages the use of the empirical separability $c_{n,p}^{\mathrm{emp}}$ as a detailed description of the linear separability of a data set in an information theoretic framework. Despite being one of the simplest benchmark data sets used in machine learning, MNIST is already rather complex; its classes are known to have small intrinsic dimensions and varied geometries [15]. Therefore, before turning to MNIST, let us consider a simple controlled experiment, where the data are extracted from a simple one-parameter mixture distribution, defined, as follows. Let $\sigma \in \{-1,+1\}$ be a Bernoulli random variable with parameter $1/2$, which generates the labels. The data points $\xi \in {\mathbb{R}}^n$ are extracted from a multivariate normal distribution with $\sigma$-dependent mean. The joint probability distribution of each point-label pair is

$$P\left(\{\xi ,\sigma \}\right)=\frac{1}{2}{f}_{\mathcal{N}\left(\mu \left(\sigma \right),\mathbb{I}\right)}\left(\xi \right),\mu \left(\sigma \right)=\left(\sigma \frac{\delta }{2},0,\dots ,0\right),$$

(12)

where $f_{\mathcal{N}(\mu ,\mathbb{I})}$ is the probability density function of the multivariate normal distribution with mean $\mu$ and identity covariance matrix. The parameter $\delta$ measures the distance between the two means: $\delta =∥\mu (\sigma =+1)-\mu (\sigma =-1)∥$. Figure 2 shows the empirical separability $c_{n,p}^{\mathrm{emp}}$, as a function of the size p of the subsets, for such a data set containing $m=200$ data points in $n=20$ dimensions. When $\delta =0$, all of the data points are extracted from the same distribution, regardless of their labels: the data have no structure and the separability follows the null model, as in Equation (2). While $\delta$ increases, equally labelled points start to cluster, and the separability at any given $p>n$ increases, as expected from the qualitative discussion in Section 2. It is interesting to note that the width of the transition region ($\Delta p$ in Figure 1) is also an increasing function of $\delta$. This dependence was not expected a priori; In Section 7, I will show that the theory of structured data presented below allows for explaining this behavior.

Let us now compute $c_{n,p}^{\mathrm{emp}}$ for the rescaled MNIST data set. Figure 2 shows the results of three numerical experiments, as compared with the null model prediction (2), and elicits four observations. (i) MNIST data are significantly more separable than the null model. For instance, the signed surprise, with respect to the null model, of the empirical dichotomies separating the digits “3” and “7” takes the values $S_{400}\approx -55$, $S_{500}\approx -100$, $S_{600}\approx -150$. (ii) Even within the same data set, different classifications can have different probabilities of separation; the dichotomy separating the digits “4” and “9” in rescaled MNIST is closer to the null model than the dichotomy of “3” and “7” (e.g., $S_{400}\approx -48$). (iii) Destroying the structure by random reshuffling of the labels makes the separability collapse onto that of the null model; the surprise $S_p$ in this case is, at most, of order ${10}^{-1}$ for all p. (iv) Similarly to what happens in the more controlled experiment with the synthetic data above, the separability curve of the “3”/“7” dichotomy, which has its transition point at a larger value of p than the “3”/“9” dichotomy, also has a wider transition region.

This analysis shows that, contrary to what appeared by looking solely at the whole data set, the dichotomies of rescaled MNIST are much more likely to be realized by a linear separator than random ones. In relation to the separability as a function of p, the null model has a single parameter, the dimension n. Is it possible to interpret the empirical curves as those of the null model with an effective dimension $n_{\mathrm{eff}}$? Increasing n has the effect of increasing proportionally the value $p_{\mathrm{c}}$ because the storage capacity is fixed to ${\alpha }_{\mathrm{c}}=2$. However, while fixing $n_{\mathrm{eff}}\approx 280$ indeed aligns the critical number of points $p_{\mathrm{c}}$ with the empirical one, it yields a much smaller width of the transition region ($\Delta p\approx 80$ for the null model and $\Delta p\approx 300$ in the data). Furthermore, notice that the values of the surprise for the “3”-vs.-“7” and “4”-vs.-“9” experiments are not very different. The reason is the ingenuousness of the null model, which hardly captures the properties of the empirical sets, and whose term $c_{n,p}$ therefore dominates in $S_p$. These observations, together with the motivations that are discussed above, are a spur for the definition of a more nuanced and versatile model of the separability of structured data.

5. Parameterized Model of Structured Data

Fixing a model of data structure in this context means fixing a generative model of data. Here, I use the model first introduced in [28]. This should not be considered to be a realistic model of real data sets. It is useful as an effective or phenomenological parameterization of data structure. It has two main advantages: (i) it allows the analytical computation, within a mean field approximation, of the probability of separation $c_{n,p}$; and, (ii) it naturally points out the relevant geometric-probabilistic parameters that control the linear separability.

The model is expressed in the form of constraints between the points and the labels. The synthetic data set is constructed as a collection of q “multiplets”, i.e., subsets of k points $\{{\xi }_{\mu }^1,\dots ,{\xi }_{\mu }^k\}$ with prescribed geometric relations between them, and such that the labels are constant within each multiplet:

$$\begin{array}{cc}\hfill Z_q=& \left\{\left({\xi }_1^1,{\sigma }_1\right),\cdots ,\left({\xi }_1^k,{\sigma }_1\right),\right.\hfill \\ \hfill & \phantom{\{}\left({\xi }_2^1,{\sigma }_2\right),\cdots ,\left({\xi }_2^k,{\sigma }_2\right),\hfill \\ \hfill & \phantom{\{\left({\xi }_2^1,{\sigma }_2\right),}⋮\hfill \\ \hfill & \phantom{\{}\left.\left({\xi }_q^1,{\sigma }_q\right),\cdots ,\left({\xi }_q^k,{\sigma }_q\right)\right\}.\hfill \end{array}$$

(13)

The total number of point/label pairs is $p=qk$. Observe that, if one considers the set of all points $X=\left\{{\xi }_{\mu }^i\right\}$, not every dichotomy of X is admitted by the parameterization of $Z_q$ in Equation (13). If a dichotomy assigns different labels to two elements of the same multiplet, it cannot be written in this form. The dichotomies that agree with the parameterization of Equation (13) are termed as admissible.

The relations between the points ${\xi }_{\mu }^i$ within each multiplet can be fixed, for instance, by prescribing that the $k(k-1)/2$ overlaps ${\rho }_{i,j}={\xi }_{\mu }^i·{\xi }_{\mu }^j$ be fixed and independent of $\mu$ (remember that $|{\xi }_{\mu }^i|=1$). The statistical ensemble for $Z_q$, as specified by the probability density $\mathrm{d}p\left(Z_q\right)$, is chosen in accordance with the maximum entropy principle: it is the uniform probability distribution on the points and the labels independently, given the constraints:

$$\mathrm{d}p\left(Z_q\right)=\frac{1}{\mathcal{Z}\left(n,q,\left\{{\rho }_{i,j}\right\}\right)}\prod _{\begin{array}{c}\mu =1,\dots ,q\\ i=1,\dots ,k\end{array}}\mathrm{d}{\xi }_{\mu }^i\delta \left(\left|{\xi }_{\mu }^i\right|-1\right)\prod _{a>b=1,\dots ,k}\delta \left({\rho }_{a,b}-{\xi }_{\mu }^a·{\xi }_{\mu }^b\right),$$

(14)

where $\mathcal{Z}\left(n,q,\left\{{\rho }_{i,j}\right\}\right)$ is the partition function, fixed by the normalization condition

$$\sum _{\left\{{\sigma }_{\mu }\right\}}{\int }_{{\mathbb{R}}^{nqk}}\mathrm{d}p\left(Z_q\right)=1.$$

(15)

The null (unstructured) model of Section 3 is recovered in this parameterization in two different limits. First, if $k=1$ each multiplet is composed of a single point, and no contraints are imposed other than the normalization. Second, for any k, if all overlaps are fixed to 1, then all points in each overlap coincide, ${\xi }_{\mu }^1={\xi }_{\mu }^2=\cdots ={\xi }_{\mu }^k$, and the model is equivalent to the null model with $p=q$.

The theory that will be described below depends on a natural set of parameters ${\psi }_m$, with $m=2,\dots ,k$. These quantities are conditional probabilities of geometric events that are related to single multiplets. They characterize the properties of the multiplets that are relevant for the linear separability of the whole set. Consider a multiplet $X=\{{\xi }^1,\dots ,{\xi }^k\}$. ${\psi }_m$ is a measure of the likelihood that a subset $X^{\prime }\subseteq X$ of $m\le k$ points is classified coherently by a random weight vector. More precisely, ${\psi }_m$ is the probability that the scalar product $w·\xi$ has the same sign for all $\xi \in X^{\prime }$, being conditioned on the event that $w·\xi$ has the same sign for all $\xi \in X\backslash \left\{{\xi }_{🟉}\right\}$. This probability is computed in the ensemble where the vector w is uniformly distributed on the unit sphere $S^{n-1}$, $X^{\prime }$ is uniformly distributed on the subsets of X of m points, and ${\xi }_{🟉}$ is uniformly distributed on the elements of $X^{\prime }$. This is coherent with the mean field nature of the combinatorial theory, which assumes uniformly distributed and uncorrelated quantities (see below).

In a few cases, ${\psi }_m$ can be computed explicitly. For instance, for a doublet $\{\xi ,\overline{\xi }\}$ at fixed overlap $\rho =\xi ·\overline{\xi }$,

$${\psi }_2\left(\rho \right)=\frac{2}{\pi }arctan\sqrt{\frac{1+\rho }{1-\rho }}.$$

(16)

This is the probability that a random hyperplane does not intersect the segment that connects two points at overlap $\rho$. It is an increasing function of $\rho$, from ${\psi }_2(-1)=0$ to ${\psi }_2\left(1\right)=1$. If $k>2$, then the quantity that enters the equations will be the mean of ${\psi }_2\left(\rho \right)$ over all the pairs in the multiplet. It can be shown that ${\psi }_m$, as a function of the overlaps ${\rho }_{i,j}$, does not explicitly depend on the dimensionality n [28]; this property greatly simplifies the analytical computations.

In summary, the parameters of the model are the following: the dimensionality n, the multiplicity k, and the $k-2$ probabilities ${\psi }_m$. Actually, only two special combinations of the parameters ${\psi }_m$ emerge as relevant from the theory that is presented in the next sections:

$$\begin{array}{cc}\hfill {\mathsf{\Psi }}_1& =\sum _{r=2}^k{\psi }_r,\hfill \end{array}$$

(17)

$$\begin{array}{cc}\hfill {\mathsf{\Psi }}_2& =\sum _{r=2}^k\sum _{l=2}^{r-1}{\psi }_r{\psi }_l.\hfill \end{array}$$

(18)

I will call them structure parameters. Other functions of the probabilities ${\psi }_m$ are relevant for other purposes, for instance, when considering the large-p asymptotics of $c_{n,p}$, which relates to the generalization properties of the linear separator [32].

6. Combinatorial Computation of the Separability for Structured Data

Cover popularized a powerful combinatorial technique to compute the number of linearly realizable dichotomies in an old and highly cited paper [38]. Despite its appeal, the combinatorial approach (while certainly not extraneous to contemporary statistical physics, both theoretical and applied [40,41,42,43]) remained somewhat confined to very few papers in discrete mathematics, and it was only very recently extended to more modern questions, when it was used to obtain an equation for $C_{n,q}$, the number of admissible dichotomies of q multiplets, for structured data of the type that is defined in the previous section. Ref. [28] first presented the arguments and computations leading to this equation. To make this article as self-contained as possible, I repeat most of the derivation here.

6.1. Exact Approach for Unstructured Data (k = 1 Points per Multiplet)

First, I recall the classic computation for unstructured data ($k=1$ in our notation). The idea is to write a recurrence relation for the number of linearly realizable dichotomies $C_{n,p}$ and, consequently, for the probability $c_{n,p}$, by considering the addition of the $(p+1)$th element ${\xi }_{p+1}$ to the set $X_p=\{{\xi }_1,\dots ,{\xi }_p\}$ that was composed of the first p elements.

Consider one of the dichotomies of $X_p$, let us call it ${\varphi }_p$; how many linearly realizable dichotomies of $X_{p+1}=\{{\xi }_1,\dots ,{\xi }_p,{\xi }_{p+1}\}$ agree with ${\varphi }_p$ (i.e., take the same values) on the points of $X_p$? When the point ${\xi }_{p+1}$ is added to the set, two different things can happen: (i) $sgn(w·{\xi }_{p+1})$ is the same for all possible weight vectors w that realize ${\varphi }_p$; and, (ii) there is at least one weight vector $\widehat{w}$ realizing ${\varphi }_p$, such that $\widehat{w}·{\xi }_{p+1}=0$. These two cases lead to different contributions to $C_{n,p+1}$. In the first case, there is only one dichotomy of $X_{p+1}$ agreeing with ${\varphi }_p$, as the value that is assigned to ${\xi }_{p+1}$ is fixed. In the second case, the value that is assigned to ${\xi }_{p+1}$ can be either $+1$ or $-1$; therefore, the number of dichotomies of $X_{p+1}$ agreeing with ${\varphi }_p$ is 2.

Let us call $M_{n,p}$ the number of those dichotomies, among the $C_{n,p}$ dichotomies of $X_p$, such that (ii) holds for the new point; the number of those satisfying (i) will be $C_{n,p}-M_{n,p}$. The reasoning above then leads to $C_{n,p+1}=(C_{n,p}-M_{n,p})+2M_{n,p}=C_{n,p}+M_{n,p}$. Here lies the keystone that allows for the closure of the recurrence equation: $M_{n,p}$ is the number of dichotomies conditioned to satisfy a linear constraint; therefore, it is equal to the number of dichotomies, of the same number of points p, in $n-1$ dimensions: $M_{n,p}=C_{n-1,p}$. Finally, the recurrence relation is $C_{n,p+1}=C_{n,p}+C_{n-1,p}$, which translates into the following equation for the probability $c_{n,p}$:

$$c_{n,p+1}=\frac{1}{2}\left(c_{n,p}+c_{n-1,p}\right).$$

(19)

The boundary conditions of the recurrence (19) are

$$\begin{array}{cc}\hfill & c_{n>0,1}=1,\hfill \\ \hfill & c_{n\le 0,p}=0\left[\Rightarrow c_{1,p}=2^{1-p}\right],\hfill \end{array}$$

(20)

which come from the conditions $C_{1,p>0}=2$ (there are only two normalized weight vectors in one dimension) and $C_{n>0,1}=2$ (there is always a weight vector w, such that $\pm w·\xi =\pm 1$). The solution of Equation (19) is Equation (2), as can be checked directly. However, the more complicated equations that are satisfied by the probabilities for structured data are not as easily solvable. For this reason, in Section 7, below, I will show a method to compute useful quantities that are related to the shape of $c_{n,p}$ directly from the recurrence relations, with no need for a closed solution.

6.2. Mean-Field Approach for Pairs of Points (k = 2 Points per Multiplet)

The simplest non-trivial extension of Cover’s computation to structured data is $k=2$. From here on I will use ${\widehat{c}}_{n,q}$ and ${\widehat{C}}_{n,q}$ to denote the fraction and number of linearly realizable admissible dichotomies of q multiplets because the symbols $c_{n,p}$ and $C_{n,p}$ were reserved to denote the fraction and number of linearly realizable dichotomies of p points.

Notice that all the quantities appearing above are notated with no explicit dependence on the points $\xi$. This is because the unstructured case enjoys a strong universality property (as proved in [38]): $C_{n,p}$ is independent of the points of $X_p$, as long as they are in a general position. Such generality breaks down for structured data. In this case, the recurrence equations that will be obtained are not valid for all sets $X_p$; rather, they are satisfied by the ensemble averages of ${\widehat{C}}_{n,q}$ and ${\widehat{c}}_{n,q}$, in the spirit of the mean-field approximation of statistical physics.

The set of points is now $X_q\cup {\overline{X}}_q$, where $X_q$ is a set of q points $\{{\xi }_1,\dots ,{\xi }_q\}$ and ${\overline{X}}_q$ is a set of partners $\{{\overline{\xi }}_1,\dots ,{\overline{\xi }}_q\}$, where ${\xi }_{\mu }·{\overline{\xi }}_{\mu }=\rho$ for all $\mu =1,\dots ,q$ (remember that all of the points are on the unit sphere). Consider the addition of the points ${\xi }_{q+1}$ and ${\overline{\xi }}_{q+1}$ to $X_q$ and ${\overline{X}}_q$, respectively. By repeating the reasoning described above for $k=1$ with respect to the point ${\overline{\xi }}_{q+1}$, one finds a formula for the number $Q_{n,q}$ of dichotomies of the set $\{{\xi }_1,{\overline{\xi }}_1,\dots ,{\xi }_q,{\overline{\xi }}_q,{\overline{\xi }}_{q+1}\}$ that are admissible on the first q pairs (and are unconstrained on ${\overline{\xi }}_{q+1}$): $Q_{n,q}={\widehat{C}}_{n,q}+{\widehat{C}}_{n-1,q}$. These dichotomies can be separated into two classes, similarly to the two cases (i) and (ii) above: those that can be realized by a weight vector orthogonal to ${\xi }_{q+1}$ (let us denote their number by $R_{n,q}$) and those that cannot (their number is then $Q_{n,q}-R_{n,q}$). For each dichotomy $\varphi$ of the first class, there exists one and only one admissible dichotomy of the full set $X_{q+1}\cup {\overline{X}}_{q+1}$ that agrees with $\varphi$ and can be realized linearly. In fact, thanks to the orthogonality constraint, there is always, among the weight vectors realizing $\varphi$, one vector w, such that

$$sgn(w·{\xi }_{q+1})=\varphi \left({\overline{\xi }}_{q+1}\right),$$

(21)

thus satisfying the admissibility condition on the pair $\{{\xi }_{q+1},{\overline{\xi }}_{q+1}\}$. The remaining $Q_{n,q}-R_{n,q}$ dichotomies do not allow this freedom. How many of them are realized by weight vectors w, such that the admissibility condition (21) is satisfied can be estimated at the mean field level by the probability that, given a random weight vector w chosen uniformly on the unit sphere, the scalar products $w·{\xi }_{q+1}$ and $w·{\overline{\xi }}_{q+1}$ have the same sign. This probability does not depend on the actual points, but only on their overlap $\rho$, and it is exactly the quantity ${\psi }_2\left(\rho \right)$ that is defined in the previous section, Equation (16). I will denote it by ${\psi }_2$ in the following, with the dependence on $\rho$ being understood.

The foregoing argument brings the following equation:

$${\widehat{C}}_{n,q+1}=R_{n,q}+{\psi }_2\left({\widehat{C}}_{n,q}+{\widehat{C}}_{n-1,q}-R_{n,q}\right)$$

(22)

Similarly to what happens in the unstructured case, the unknown term $R_{n,q}$ can be expressed in terms of variables ${\widehat{C}}_{•,q}$ by considering the same problem in a lower dimension. In fact, remember that $Q_{n,q}$ above was computed by applying Cover’s argument for $k=1$, because it counts how the number of dichotomies is affected when the single point ${\overline{\xi }}_{q+1}$ is added to the set. $R_{n,q}$ must be computed in the same way, since it, again, counts the number of dichotomies that are admissible on the first q pairs and free on ${\overline{\xi }}_{q+1}$. However, these dichotomies must satisfy the additional linear constraint $w·{\xi }_{q+1}=0$; therefore, the whole argument must be applied in $n-1$ dimensions. This leads to

$$R_{n,q}={\widehat{C}}_{n-1,q}+{\widehat{C}}_{n-2,q}.$$

(23)

Finally, substituting this expression of $R_{n,q}$ into Equation (22) yields

$${\widehat{C}}_{n,q+1}={\psi }_2{\widehat{C}}_{n,q}+{\widehat{C}}_{n-1,q}+\left(1-{\psi }_2\right){\widehat{C}}_{n-2,q}.$$

(24)

As above, this translates to a similar equation for the probability ${\widehat{c}}_{n,q}$:

$${\widehat{c}}_{n,q+1}=\frac{{\psi }_2}{2}{\widehat{c}}_{n,q}+\frac{1}{2}{\widehat{c}}_{n-1,q}+\frac{1-{\psi }_2}{2}{\widehat{c}}_{n-2,q}.$$

(25)

The boundary conditions of this recurrence are slightly different than for $k=1$. They are discussed in the Appendix A, together with those for the general case.

6.3. General Case Parameterized by k

It is possible to extend the method that is described above to all k. I will only sketch the derivation; the details can be found in [28]. Just as the case $k=2$ can be treated by making use of the recurrence formula for $k=1$, the idea here is to construct the case k recursively by using the formula (yet to be found) for $k-1$, therefore obtaining a recurrence relation in k as well as in n and q. To this aim, the $(q+1)$th multiplet $\{{\xi }_{q+1}^1,\dots ,{\xi }_{q+1}^k\}$ is split into the two subsets $\left\{{\xi }_{q+1}^1\right\}$ and ${\overline{\xi }}_{q+1}=\{{\xi }_{q+1}^2,\dots ,{\xi }_{q+1}^k\}$. The formula for $k-1$ allows for applying the argument to the set ${\overline{\xi }}_{q+1}$, thus obtaining the number $Q_{n,q}$ of dichotomies of the set $X_q\backslash \left\{{\xi }_{q+1}^1\right\}$ that are admissible on the first q complete multiplets and are admissible on the $(q+1)$th incomplete multiplet ${\overline{\xi }}_{q+1}$. More formally, $Q_{n,q}$ is the number of linearly realizable dichotomies $\varphi$, such that

$$\begin{array}{cc}\hfill & \varphi \left({\xi }_{\mu }^i\right)=\varphi \left({\xi }_{\mu }^j\right)i,j=1,\dots ,k;\mu =1,\dots ,q\hfill \\ \hfill & \varphi \left({\xi }_{q+1}^i\right)=\varphi \left({\xi }_{q+1}^j\right)i,j=2,\dots ,k.\hfill \end{array}$$

(26)

Now the argument goes exactly as for the case $k=2$: some of these $Q_{n,q}$ dichotomies (their number being $R_{n,q}$) can be realized by a weight vector orthogonal to the point ${\xi }_{q+1}^1$; therefore, each of them contributes a single admissible dichotomy of the whole set $X_{q+1}$; the remaining $Q_{n,q}-R_{n,q}$ contribute with probability ${\psi }_k$. Again, $R_{n,q}$ can be expressed by applying the same argument in $n-1$ dimensions.

Finally, one finds that the probability ${\widehat{c}}_{n,q}$ satisfies a recurrence equation in n and q:

$${\widehat{c}}_{n,q+1}=\sum _{l=0}^k{\theta }_l^k{c}_{n-l,q},$$

(27)

where the coefficients ${\theta }_l^k$ are constants (independent of n and q) satisfying a recurrence equation in k and l:

$${\theta }_l^k={\psi }_k{\theta }_l^{k-1}+(1-{\psi }_k){\theta }_{l-1}^{k-1}.$$

(28)

The boundary conditions for Equation (28) are

$$\begin{array}{cc}\hfill & {\theta }_0^1={\theta }_1^1=\frac{1}{2}\hfill \\ \hfill & {\theta }_{l<0}^k={\theta }_{l>k}^k=0;\hfill \end{array}$$

(29)

the conditions at $k=1$ are those that reproduce Equation (19).

7. Computation of Compact Metrics of Linear Separability

The model of data structure leading to the foregoing equations is very detailed, in that it allows for the independent specification of a large number of parameters. However, the influence of each parameter on the separability ${\widehat{c}}_{n,q}$ is not equal, with some combinations of parameters being more relevant than others. In this section, I compute two main descriptors of the shape of ${\widehat{c}}_{n,q}$ as a function of q at n fixed: the transition point $p_{\mathrm{c}}$ (equivalently, the capacity ${\alpha }_{\mathrm{c}}$) and the width $\Delta p$ of the transition region; they are defined more precisely below. We will see that only the structure parameters ${\mathsf{\Psi }}_1$ and ${\mathsf{\Psi }}_2$, the special combinations defined in Section 5, are needed to fix $p_{\mathrm{c}}$ and $\Delta p$.

7.1. Diagonalization of the Recurrence Relation

Notice that, while the quantity ${\widehat{c}}_{n,q}$ that is given by the theory is expressed as a function of the number of multiplets q, the definition of separability that is discussed in Section 5 is given in terms of the number of points $p=kq$. This is not really a problem in the thermodynamic limit

$$\begin{array}{cc}\hfill & n\to \infty \hfill \\ \hfill & p\to \infty \hfill \\ \hfill & \alpha =\frac{p}{n}\mathrm{fixed}\hfill \\ \hfill & k\mathrm{fixed},\hfill \end{array}$$

(30)

whereby the separability is expressed as a function of the load $\alpha$. In the following, I will define the location $q_{\mathrm{c}}$ and the width $\Delta q$ of the transition region in the parameterization by the number of multiplets q; the corresponding quantities that are parameterized by p are obtained by rescaling:

$$p_{\mathrm{c}}=k{q}_{\mathrm{c}},\Delta p=k\Delta q.$$

(31)

Let us consider the discrete derivative of ${\widehat{c}}_{n,q}$ with respect to n:

$${\gamma }_{n,q}={\Delta }_n{\widehat{c}}_{n,q}\equiv {\widehat{c}}_{n+1,q}-{\widehat{c}}_{n,q}.$$

(32)

As will be clear momentarily, working with ${\gamma }_{n,q}$ is convenient because it is normalized, as I will prove below. ${\gamma }_{n,q}$ satisfies the same recurrence relation as ${\widehat{c}}_{n,q}$:

$${\gamma }_{n,q+1}=\sum _{l=0}^k{\theta }_l^k{\gamma }_{n-l,q}.$$

(33)

The boundary conditions, in accordance with (20), are

$$\begin{array}{cc}\hfill & {\gamma }_{n,1}={\delta }_{n,0},\hfill \\ \hfill & {\gamma }_{n<0,q}=0.\hfill \end{array}$$

(34)

The right hand side of Equation (33) has the form of a discrete convolution between ${\theta }_{•}^k$ and ${\gamma }_{•,q}$:

$$c_{•,q+1}={\theta }_{•}^k\ast c_{•,q}.$$

(35)

The convolution is diagonalized in Fourier space, by defining the characteristic functions

$$\begin{array}{cc}\hfill {\tilde{\gamma }}_q\left(t\right)=& \sum _{n=0}^{\infty }{\gamma }_{n,q}{e}^{\mathrm{i}nt},\hfill \end{array}$$

(36)

$$\begin{array}{cc}\hfill {\tilde{\theta }}_k\left(t\right)=& \sum _{n=0}^{\infty }{\theta }_n^k{e}^{\mathrm{i}nt}.\hfill \end{array}$$

(37)

Multiplying both sides of Equation (35) by $e^{\mathrm{i}nt}$ and summing over n yields

$${\tilde{\gamma }}_{q+1}\left(t\right)={\tilde{\theta }}_k\left(t\right){\tilde{\gamma }}_q\left(t\right).$$

(38)

From the definition (36) and boundary conditions (34), one gets ${\tilde{\gamma }}_1\left(t\right)=1$; hence, the solution of the recurrence equation is

$${\tilde{\gamma }}_q\left(t\right)={\left[{\tilde{\theta }}_k\left(t\right)\right]}^{q-1}.$$

(39)

7.2. Defining the Location and Width of the Transition Region

As mentioned above, ${\gamma }_{n,q}$ is normalized, which means that

$$\sum _{n=0}^{\infty }{\gamma }_{n,q}=1,$$

(40)

or, equivalently, ${\tilde{\gamma }}_q\left(0\right)=1$. To prove this, it suffices to show that ${\tilde{\theta }}_k\left(0\right)=1$, i.e., that ${\theta }_n^k$ is normalized. Summing both sides of Equation (28) in l from 0 to ∞ shows that ${\tilde{\theta }}_k\left(0\right)$ is constant in k, therefore

$${\tilde{\theta }}_k\left(0\right)={\tilde{\theta }}_1\left(0\right)=1,$$

(41)

as can be computed from the boundary conditions (29).

Because it is normalized, ${\gamma }_{•,q}$ can be interpreted as a probability distribution, whose cumulative distribution function is ${\widehat{c}}_{•,q}$. The ath moment of the distribution is

$$\begin{array}{cc}\hfill {〈n^a〉}_q& =\sum _{n=0}^{\infty }{n}^a{\gamma }_{n,q}\hfill \\ \hfill & ={\mathrm{i}}^{-a}{\left.\frac{{\mathrm{d}}^a}{\mathrm{d}{t}^a}{\tilde{\gamma }}_q\left(t\right)\right|}_{t=0}.\hfill \end{array}$$

(42)

The same holds for ${\theta }_{•}^k$, whose moments ${〈{\theta }^a〉}_k$ can be obtained from its characteristic function ${\tilde{\theta }}_k\left(t\right)$. Let us focus on the mean ${\mu }_q$ and the variance ${\sigma }_q$,

$${\mu }_q={〈n〉}_q,{\sigma }_q^2={〈n^2〉}_q-{〈n〉}_q^2.$$

(43)

Equation (39) allows for expressing these quantities in terms of the mean ${\mu }_{\theta }={〈\theta 〉}_k$ and variance ${\sigma }_{\theta }^2={〈{\theta }^2〉}_k-{〈\theta 〉}_k^2$ of ${\theta }_{•}^k$:

$${\mu }_q=(q-1){\mu }_{\theta },{\sigma }_q^2=(q-1){\sigma }_{\theta }^2,$$

(44)

as can be checked by using Equation (42).

We can now define the two main descriptors, $q_{\mathrm{c}}$ and $\Delta q$, which summarize the separability as a function of q:

$$\begin{array}{cc}\hfill q_{\mathrm{c}}:& {\mu }_{q_{\mathrm{c}}}=n,\hfill \end{array}$$

(45)

$$\begin{array}{cc}\hfill q_{\pm }:& {\mu }_{q_{\pm }}\mp {\sigma }_{q_{\pm }}=n,\hfill \end{array}$$

(46)

$$\begin{array}{cc}\hfill \Delta q:& \Delta q=q_{+}-q_{-}.\hfill \end{array}$$

(47)

7.3. Expression in Terms of the Structure Parameters

To compute these quantities, all we need is ${\mu }_{\theta }$ and ${\sigma }_{\theta }$, or ${〈\theta 〉}_k$ and ${〈{\theta }^2〉}_k$. Solving Equation (45) for $q_{\mathrm{c}}$ gives

$$q_{\mathrm{c}}=n{\mu }_{\theta }^{-1}+1.$$

(48)

Solving Equations (46) and (47) for $\Delta q$ gives

$$\Delta q=\frac{1}{{\mu }_{\theta }^2}\sqrt{{\sigma }_{\theta }^2\left({\sigma }_{\theta }^2+4{\mu }_{\theta }n\right)}.$$

(49)

The corresponding expressions to leading order in n are the following

$$\begin{array}{cc}\hfill q_{\mathrm{c}}& =n{\mu }_{\theta }^{-1}+O\left(1\right),\hfill \\ \hfill \Delta q& =2{\sigma }_{\theta }{\mu }_{\theta }^{-3/2}{n}^{1/2}+O\left(n^{-1/2}\right).\hfill \end{array}$$

(50)

The moments of ${\theta }_{•}^k$ satisfy the following equation, which can be obtained by multiplying both sides of Equation (28) by $l^a$ and summing over l:

$$\begin{array}{cc}\hfill {〈{\theta }^a〉}_k=& {\psi }_k{〈{\theta }^a〉}_{k-1}+\left(1-{\psi }_k\right)\sum _{l=0}^{\infty }{(l+1)}^a{\theta }_l^{k-1}\hfill \\ \hfill =& {〈{\theta }^a〉}_{k-1}+\left(1-{\psi }_k\right)\sum _{s=0}^{a-1}\left(\genfrac{}{}{0pt}{}{a}{s}\right){〈{\theta }^s〉}_{k-1}.\hfill \end{array}$$

(51)

The boundary conditions are ${〈{\theta }^0〉}_k=1$ (computed above) and ${〈{\theta }^a〉}_1=1/2$, as given by Equation (29). In particular, for $a=1$, we obtain

$${〈\theta 〉}_k={〈\theta 〉}_{k-1}+\left(1-{\psi }_k\right),$$

(52)

whose solution is

$${〈\theta 〉}_k=k-\frac{1}{2}-{\mathsf{\Psi }}_1,$$

(53)

where the structure parameter ${\mathsf{\Psi }}_1$, as defined in Equation (17), implicitly depends on k. For $a=2$, the recurrence Equation (51) becomes

$${〈{\theta }^2〉}_k={〈{\theta }^2〉}_{k-1}+\left(1-{\psi }_k\right)\left(2{〈\theta 〉}_{k-1}+1\right).$$

(54)

By substituting ${〈\theta 〉}_{k-1}$ given by Equation (53) and solving the recurrence we obtain, after some algebra,

$${〈{\theta }^2〉}_k=k^2-k+\frac{1}{2}-2(k-1){\mathsf{\Psi }}_1+2{\mathsf{\Psi }}_2,$$

(55)

where ${\mathsf{\Psi }}_2$ is the second structure parameter that is defined in Equation (18). Finally, by combining the leading order expansions (50) and the moments (53) and (55), and by rescaling, as in Equation (31), we have the following explicit expressions for the two main metrics of separability as functions of the multiplicity k and the structure parameters ${\mathsf{\Psi }}_1$ and ${\mathsf{\Psi }}_2$:

$$\begin{array}{cc}\hfill & \frac{p_{\mathrm{c}}}{n}={\left(1-\frac{1}{2k}-\frac{{\mathsf{\Psi }}_1}{k}\right)}^{-1},\hfill \end{array}$$

(56)

$$\begin{array}{cc}\hfill & \frac{\Delta p}{\sqrt{n}}=2k{\left(k-\frac{1}{2}-{\mathsf{\Psi }}_1\right)}^{-\frac{3}{2}}{\left(\frac{1}{4}+{\mathsf{\Psi }}_1-{\mathsf{\Psi }}_1^2+2{\mathsf{\Psi }}_2\right)}^{\frac{1}{2}}.\hfill \end{array}$$

(57)

For data that are structured as pairs of points, $k=2$, Equation (56) gives the storage capacity of an ensemble of segments; this special result was first obtained, by means of replica calculations, in [44], and it was then rediscovered in other contexts in [8,45].

7.4. Dependence on the Structure Parameters and Scaling

The two structure parameters ${\mathsf{\Psi }}_1$ and ${\mathsf{\Psi }}_2$, which control the two main metrics of linear separability, belong to k-dependent ranges:

$${\mathsf{\Psi }}_1\in [0,k-1],{\mathsf{\Psi }}_2\in [0,(k-1)(k-2)/2].$$

(58)

The two quantities are not independent, since they are constructed from the same set of $k-1$ quantities ${\psi }_m\in [0,1]$. When conditioned on a fixed value of ${\mathsf{\Psi }}_1$, ${\mathsf{\Psi }}_2$ has a lower bound ${\mathsf{\Psi }}_2^{-}$ and an upper bound ${\mathsf{\Psi }}_2^{+}$ that can be computed by considering the two following extreme cases. First, the supremum of ${\mathsf{\Psi }}_2$ is realized in the maximum entropy case, where the value of ${\mathsf{\Psi }}_1$ is uniformly distributed among the ${\psi }_m$. Second, the infimum of ${\mathsf{\Psi }}_2$ corresponds to the minimum entropy case, where ${\mathsf{\Psi }}_1$ is distributed on the fewest possible ${\psi }_m$’s. Explicitly,

$$\begin{array}{cc}\hfill sup:& \left\{{\psi }_m\right\}=\left\{\frac{{\mathsf{\Psi }}_1}{k-1},\cdots ,\frac{{\mathsf{\Psi }}_1}{k-1}\right\},\hfill \end{array}$$

(59)

$$\begin{array}{cc}\hfill inf:& \left\{{\psi }_m\right\}=\{\underset{\lfloor {\mathsf{\Psi }}_1\rfloor }{\underbrace{1,\cdots ,1}},{\mathsf{\Psi }}_1-\lfloor {\mathsf{\Psi }}_1\rfloor ,0,\cdots ,0\}.\hfill \end{array}$$

(60)

The definition of ${\mathsf{\Psi }}_2$, Equation (18), can be rewritten, as follows:

$${\mathsf{\Psi }}_2=\frac{1}{2}{\mathsf{\Psi }}_1^2-\frac{1}{2}\sum _{m=2}^k{\psi }_m^2.$$

(61)

Substituting (59) and (60) into (61), we obtain

$$\begin{array}{cc}\hfill {\mathsf{\Psi }}_2^{+}& =sup{\mathsf{\Psi }}_2=\frac{{\mathsf{\Psi }}_1^2}{2}\left(1-\frac{1}{k-1}\right),\hfill \end{array}$$

(62)

$$\begin{array}{cc}\hfill {\mathsf{\Psi }}_2^{-}& =inf{\mathsf{\Psi }}_2={\mathsf{\Psi }}_1\lfloor {\mathsf{\Psi }}_1\rfloor -\frac{1}{2}\left({\lfloor {\mathsf{\Psi }}_1\rfloor }^2+\lfloor {\mathsf{\Psi }}_1\rfloor \right).\hfill \end{array}$$

(63)

Figure 3 shows the location of the transition, $p_{\mathrm{c}}$, and the width of the region, $\Delta p$, as functions of ${\mathsf{\Psi }}_1$ and ${\mathsf{\Psi }}_2$ for a few values of k. Notice that the range of $\Delta p$ at fixed k and ${\mathsf{\Psi }}_1$ is itself bounded because of the limited range $[{\mathsf{\Psi }}_2^{-},{\mathsf{\Psi }}_2^{+}]$ of ${\mathsf{\Psi }}_2$.

There is an interesting observation to be made on a semi-quantitative level. At fixed k and n, $p_{\mathrm{c}}$ is an increasing function of ${\mathsf{\Psi }}_1$. The width $\Delta p$ depends on both structure parameters, but, since the range of ${\mathsf{\Psi }}_2$ at fixed ${\mathsf{\Psi }}_1$ is so limited, one expects that, in practice, $\Delta p$ will be approximately an increasing function of ${\mathsf{\Psi }}_1$. Therefore, $\Delta p$ will be, in most cases, an increasing function of $p_{\mathrm{c}}$. This is exactly the phenomenology that is observed in Figure 2, in both the synthetic data and MNIST.

The rescaled location of the transition $p_{\mathrm{c}}/n$, Equation (56), does not depend on ${\mathsf{\Psi }}_2$, and it depends on ${\mathsf{\Psi }}_1$ only through the rescaled value ${\mathsf{\Psi }}_1/k$. For large k, it takes the scaling form

$$\frac{p_{\mathrm{c}}}{n}\sim f_{p_{\mathrm{c}}}\left(\frac{{\mathsf{\Psi }}_1}{k}\right),f_{p_{\mathrm{c}}}\left(x\right)=\frac{1}{1-x}.$$

(64)

The width $\Delta p$, on the contrary, depends on both ${\mathsf{\Psi }}_1$ and ${\mathsf{\Psi }}_2$. Because it is a monotonically increasing function of ${\mathsf{\Psi }}_2$, its upper bound $\Delta p^{+}$ and lower bound $\Delta p^{-}$ at fixed ${\mathsf{\Psi }}_1$ can be obtained by substituting (62) and (63) in Equation (57). Expressing $\Delta p^{+}$ again as a function of the rescaled parameter ${\mathsf{\Psi }}_1/k$, and only keeping the leading term in $k\to \infty$, one obtains the scaling form

$$\frac{\Delta p^{+}}{\sqrt{n}}\sim f_{\Delta p^{+}}\left(\frac{{\mathsf{\Psi }}_1}{k}\right),f_{\Delta p^{+}}\left(x\right)=2\frac{\sqrt{x}}{1-x}.$$

(65)

Doing the same for $\Delta p^{-}$ yields a complicated function, which is plotted in Figure 3. A simpler expression for the bound can be obtained by observing that ${\mathsf{\Psi }}_2^{-}\ge ({\mathsf{\Psi }}_1^2-{\mathsf{\Psi }}_1)/2$; using this more regular bound yields, at leading order in k,

$$\frac{\Delta p^{-}}{\sqrt{n}}\sim k^{-\frac{1}{2}}{f}_{\Delta p^{-}}\left(\frac{{\mathsf{\Psi }}_1}{k}\right),f_{\Delta p^{-}}\left(x\right)={(1-x)}^{-\frac{3}{2}}.$$

(66)

Figure 3 shows the large-k scaling behavior of $p_{\mathrm{c}}$, $\Delta p^{+}$, and $\Delta p^{-}$.

The two metrics are insensitive on most of the microscopic parameters of the theory, and they only depend on the two structure parameters, as shown analytically above. In addition, they display a large degree of robustness, even as functions of ${\mathsf{\Psi }}_1$ and ${\mathsf{\Psi }}_2$: measuring $p_{\mathrm{c}}/n$ from the data fixes (up to corrections in k) the quantity ${\mathsf{\Psi }}_1/k$, which, in turn, significantly narrows down the range of values that are attainable by $\Delta p$, the more so the smaller is k.

8. Discussion

The discussion above focused on the quantification of linear separability within a model that encodes simple relations between data points and their labels, in the form of constraints. Such a model has the advantage of being analytically tractable and allows the explicit expression of $p_{\mathrm{c}}$ and $\Delta p$ in terms of model parameters. Moreover, the parameters appearing in the theory have direct interpretations as probabilities of geometric events, thus suggesting routes for further generalization.

In the face of its convenience for theoretical investigations, the definition of data structure used here does not aim at a realistic description of any specific data set. It must be interpreted as a phenomenological or effective parameterization of basic features of data structure that have a distinct effect on linear separability. The limited numerical experiments on MNIST data reported above are a proof of concept, showing a real data set with unexpectedly high linear separability, and they serve as a notable motivation for the investigation of data structure. The main goal of this article is the theoretical analysis; therefore, I postpone any comparison of theory and data. Moreover, MNIST is a relatively simple and clean data set. The numerical analysis signals the highly constrained nature of these data, where points that are close with respect to the Euclidean distance in ${\mathbb{R}}^n$ are more likely to have the same label. However, more complex data sets, such as ImageNET, are expected to be less constrained at the level of raw data, due to the higher variability within each category, and due to what are referred to as “nuisances”, i.e., elements that are present, but do not contribute to the classification. Yet, even in these cases, the aggregation of equally-labelled points emerges in the feature spaces towards the last layers of deep neural networks, which improves the efficacy of the linear readout downstream, as empirically observed [14,15].

An interesting, and perhaps unexpected, outcome of the theory concerns the universal properties of the probability of separation $c_{n,p}$. Here, I use the term “universality” in a much weaker sense than what is usually intended in statistical mechanics: I use it to denote (i) the qualitative robustness of the sigmoidal shape of the separability curve on the details of the model, and (ii) the quantitative insensitivity of the separability metrics on all but a few special combinations of parameters [46]. Importantly, the two metrics of data structure that are computed for the model, $p_{\mathrm{c}}$ and $\Delta p$, are the only two important parameters that fix $c_{n,p}$ in the thermodynamic limit, apart from the rescaling by k. The central limit theorem suggests this universality property. In fact, ${\gamma }_{n,q}$ is the probability distribution of the sum of $p-1$ independent and identically distributed variables, as expressed by Equation (39). Therefore, ${\gamma }_{n,q}$ will converge to a Gaussian distribution with linearly increasing mean and variance. This indicates that ${\mu }_q$ and ${\sigma }_q$ are the only two nonzero cumulants in the thermodynamic limit and, thus, $q_{\mathrm{c}}$ and $\Delta q$ are the only two nontrivial metrics that are related to ${\widehat{c}}_{n,q}$. This does not, by any means, imply that the model of data structure itself can be reduced to only two degrees of freedom. In fact, the phenomenology is richer if one considers the combinatorial quantity $C_{n,q}$ instead of the intensive one ${\widehat{c}}_{n,q}$, see [32]; still, regarding the probability of separation, the relevant metrics are the location and width of the transition region.