Introduction
In Statistical Learning Theory (SLT), a fundamental goal is ensuring that a model's performance on training data—the empirical risk—accurately reflects its performance on unseen data—the actual risk. The Empirical Risk Minimization Principle (ERMP) provides mathematical bounds for the divergence between these two risks. However, these bounds are critically dependent on the "capacity" of the learning algorithm, a property quantified by the shattering coefficient (or growth function), denoted as $\mathcal{N}(\mathcal{F}, 2n)$.
While shattering is a cornerstone concept, calculating the exact coefficient for specific architectures, such as neural networks with multiple neurons, has historically been a complex task. Researchers often resort to loose upper bounds or the Vapnik-Chervonenkis (VC) dimension, which can lead to overly pessimistic estimates of required sample sizes. This paper addresses this gap by providing a formal proof and a closed-form equation for calculating the shattering coefficient for hyperplane-based classifiers operating in Hilbert spaces.
Theoretical Framework: Deriving the Shattering Coefficient
The authors employ a combinatorial approach to determine how hyperplanes partition a Hilbert space. By analyzing the number of unique labelings (classifications) a hyperplane can induce on a set of points, they derive the coefficient for varying dimensions.
Single Hyperplane Case
The derivation begins by observing point configurations in low-dimensional spaces (0-D to 2-D). As illustrated in Figure 1, the number of ways a hyperplane can separate points is constrained by the dimensionality of the space.
For an $h$-dimensional Hilbert space $\mathcal{H}$ and a sample size $n$, the authors prove the shattering coefficient for a single hyperplane is: $$\mathcal{N}(\mathcal{F}, 2n) = 2 \sum_{i=0}^{h} \binom{n-1}{i}$$
Extension to Multiple Hyperplanes
Modern machine learning models, such as multi-layer perceptrons, utilize multiple "neurons" or hyperplanes. To account for this complexity, the authors extend their formulation. For a model employing $p$ hyperplanes, the shattering coefficient becomes: $$\mathcal{N}(\mathcal{F}, 2n) = 2 \left( \sum_{i=0}^{h} \binom{n-1}{i} \right)^p$$
This formula allows for a precise quantification of the "algorithm bias," where a smaller coefficient implies a more restricted (and thus more biased) model that requires fewer samples to achieve generalization guarantees.
Key Insights: The "Battle" of Terms
The guarantee of generalization hinges on the relationship between the shattering coefficient and a negative exponential term in the risk bound. If the shattering coefficient grows polynomially with $n$, the exponential term eventually dominates, ensuring that the probability of a large divergence between training and test error converges to zero. Conversely, if the model can shatter the entire dataset (exponential growth), no such guarantee is possible.
A critical threshold identified in the paper is the relationship between dimensionality $h$ and sample size $n$. If $h \ge n$, the shattering coefficient reaches its maximum value of $2^n$. In this regime, the model possesses sufficient flexibility to memorize any arbitrary labeling, rendering the ERMP unable to guarantee learning.
Results and Practical Implications
The primary contribution of this work is the closed-form equation for $p$ hyperplanes in $h$ dimensions. To demonstrate its utility, the authors provide a numerical example: for a small neural network with $p=16$ neurons in $h=3$ dimensions, achieving a 99% confidence level ($\delta=0.01$) that the training error is within 5% ($\epsilon=0.05$) of the actual risk requires approximately $1.02 \times 10^6$ samples.
The paper also visualizes how the required error tolerance $\epsilon$ changes with model complexity. As shown in Figure 2, increasing the number of hyperplanes ($p$) significantly raises the required divergence for a fixed sample size, underscoring that more complex models demand substantially more data to maintain theoretical guarantees.
Conclusion and Future Directions
While this work provides a more precise tool for calculating shattering coefficients, it is important to note that VC-style bounds are often "loose" in practice; real-world models frequently generalize better than these theoretical limits suggest. Additionally, the current proofs are tailored to hyperplane-based classifiers.
Future research could extend this framework to explicitly calculate coefficients for non-linear kernels (e.g., RBF) or more complex deep learning architectures. Nonetheless, this paper offers a practical methodology for researchers to determine minimal training set sizes, paving the way for more data-efficient AI design.
Summary updated