The Capacity of a Bump

Gary William FlakeNeurIPS 1995

Introduction

In the early 1990s, researchers observed a curious phenomenon: multilayer perceptrons (MLPs) utilizing Gaussian or "bump-like" activation functions often learned faster and required fewer hidden units than networks relying on standard sigmoidal activations. Despite this empirical success, there was a notable lack of rigorous theoretical work explaining why this architectural choice was so effective.

This paper provides a mathematical explanation for this performance gap by analyzing the theoretical capacity of these networks. By comparing traditional perceptrons to "hyper-ridge" networks, the author demonstrates that while their theoretical capacity is identical in infinite dimensions, hyper-ridge networks can represent significantly more classifications (dichotomies) in practical, finite-dimensional scenarios where the number of data points far exceeds the number of dimensions.

Architectures and Methods

The author tackles the capacity problem by comparing two simple architectures:

  1. The Simple Perceptron: Uses a sigmoidal or step function to split space with a single hyperplane.
  2. The Hyper-Ridge Network: Uses a "bump" or ridge function—specifically $g(h) = \text{sgn}(1 - h^2)$—which effectively partitions space using two parallel hyperplanes.

The core mathematical question is: how many different ways (dichotomies) can these two models partition a set of $p$ points in $d$ dimensions?

To answer this, the paper employs a combinatorial approach to derive the number of possible dichotomies, $D(p, d)$. The general recurrence relationship for hyper-ridges is identical to that of simple perceptrons: $D(p, d) = D(p-1, d) + D(p-1, d-1)$. However, the fundamental difference lies in the base cases. While a 1D perceptron can only split a line into a left and right half, a hyper-ridge can "sandwich" a segment of the line, allowing it to isolate points in the middle. By expanding the recurrence with these new base cases, the author derives a closed-form formula for the capacity of a bump.

Key Insights

The "Sandwich" Advantage

A standard perceptron splits space into two halves. A hyper-ridge splits space into three regions (outside-inside-outside), where the two "outside" regions are grouped into one class. This allows a single hyper-ridge unit to solve linearly inseparable problems like XOR, NEGATE, and SYMMETRY—tasks that are impossible for a single standard perceptron.

Identical VC Dimension

Interestingly, the Vapnik-Chervonenkis (VC) dimension for both architectures is exactly $d$. This suggests that in terms of "worst-case" complexity, they are theoretically identical.

The Limit of Infinity

The paper proves that as the input dimension $d$ approaches infinity, the advantage of the bump disappears, and both models become equivalent in capacity.

Fraction of dichotomies for d=100

Key Results: Practical Superiority

The true "aha moment" comes when looking at the ratio of possible classifications in practical scenarios. The author establishes that for $p > d + 2$, the number of dichotomies for a hyper-ridge is:

$$D_h(p, d) = D_p(p, d) + \binom{p-1}{d+1}$$

where $D_p$ is the capacity of a standard perceptron. For the common practical case where the number of patterns is much larger than the dimensions ($p \gg d$), the ratio of hyper-ridge dichotomies to perceptron dichotomies approaches:

$$\frac{D_h}{D_p} \approx \frac{p}{2(d+1)}$$

Ratio of hyper-ridge to perceptron dichotomies

This linear growth in the ratio means that if you have 60 points in 4 dimensions, a hyper-ridge network can represent roughly six times as many mappings as a standard perceptron. Even though they share the same VC dimension, the hyper-ridge has a vastly higher number of available dichotomies in typical data regimes.

Limitations and Future Work

While the mathematical results are compelling, the author notes a few limitations:

  • The Generalization Trade-off: According to the "No Free Lunch" theorem, higher representation power is excellent for fitting training data but can lead to poorer generalization (overfitting) if not properly regularized.
  • Simplified Model: The analysis focuses on a single "hyper-ridge" unit. While this provides intuition for why Gaussian units help in larger MLPs, it falls short of a full capacity proof for multi-layer networks.
  • Activation Function Specifics: The proof relies on a hard-limit "square" bump. The author argues this is a reasonable proxy for Gaussians, but the exact dynamics of smooth Gaussian curves might differ slightly in practice.

Summary updated

BibTeX
@inproceedings{flake1995capacity,
  author = {Gary William Flake},
  title = {{The Capacity of a Bump}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1995},
}
Figure