The Storage Capacity of a Fully-Connected Committee Machine

Yuansheng Xiong, Chulan Kwon, Jong-Hoon OhNeurIPS 1997

Introduction

In the late 1980s and early 1990s, Elizabeth Gardner pioneered the use of statistical mechanics to determine the "storage capacity" of neural networks—essentially, the maximum number of random patterns a network can memorize. While this approach worked beautifully for single-layer perceptrons, multi-layer networks proved much trickier to analyze.

This paper provides a theoretical breakthrough in understanding the storage capacity of a committee machine, a simple multi-layer neural network where several hidden units "vote" to produce a single output. By utilizing a sophisticated statistical mechanics formalism to analyze the internal representations of hidden nodes, the authors derive a storage capacity that finally aligns with rigorous mathematical bounds, correcting previous models that suggested impossible results.

The Challenge of the Committee Machine

The specific challenge addressed in this work is the "fully-connected" or "overlapping receptive field" (ORF) architecture, where every input is connected to every hidden unit.

Previous attempts to calculate the capacity of ORF architectures using standard "replica-symmetric" (RS) methods resulted in a value that violated the Mitchison-Durbin (MD) bound, a rigorous mathematical limit. Essentially, the older physics models predicted that these networks could store more information than was mathematically possible. This paper aims to resolve that discrepancy.

A New Methodological Approach

Because this is a theoretical physics paper, it does not evaluate empirical datasets like ImageNet or MNIST. Instead, it measures the network's capacity to store random input-output mappings. The "data" consists of $P$ random input vectors and their corresponding target outputs, with results expressed as the ratio $\alpha = P/N$ (where $N$ is the number of input units).

To solve the capacity paradox, the authors move away from the conventional Gardner approach and adopt a formalism proposed by Monasson and O'Kane. Key technical innovations include:

  • Internal Representation Analysis: Instead of looking at the total volume of valid weights (the "version space"), the authors decompose this volume into "elementary cells." Each cell corresponds to a specific set of internal states (the outputs of the hidden nodes) for all training patterns.
  • Replica Symmetry (RS) Ansatz: They introduce five distinct order parameters ($q^*, q, c, d^*, d$) to describe the overlaps between different weight configurations across different replicas and hidden units.
  • Entropy Calculation: They calculate the entropy ($N_D$) of these elementary volumes. The storage capacity is defined as the point where this entropy vanishes—meaning there is no longer any valid weight configuration that can satisfy the required internal representations.
  • Asymptotic Analysis: They examine the behavior of these parameters in the limit of a very large number of hidden nodes ($K \to \infty$).

Key Insights: Specialization and Symmetry Breaking

By shifting the analytical lens, the authors uncover several fascinating dynamics within the committee machine:

  • The "Fine Structure" Matters: The standard Gardner method treats the weight space as one large, continuous volume. This paper demonstrates that by analyzing the "fine structure"—how that space is partitioned by internal representations—we obtain a much more accurate picture of the network's limits.
  • Antiferromagnetic Correlations: The authors found that the order parameters representing overlaps between different hidden units are negative. This implies "antiferromagnetic" behavior: each hidden unit "tries" to specialize in different patterns to maximize the overall storage efficiency of the committee.
  • Permutation Symmetry Breaking (PSB): For fully-connected machines, a PSB phase occurs. As more patterns are added to the network, the hidden units stop being interchangeable and begin taking on highly specialized roles.

Main Results: Restoring Mathematical Harmony

The most significant contribution of this paper is deriving a storage capacity that respects known mathematical limits.

  • Correct Scaling: The storage capacity $\alpha_c$ is found to be proportional to $K \sqrt{\ln K}$ for large $K$.
  • Bound Satisfaction: Specifically, the capacity is derived as: $$\alpha_c \sim \frac{16}{\pi - 2} K \sqrt{\ln K}$$ This result is crucial because it satisfies the rigorous MD bound (which scales as $\sim \ln K$). Previous conventional RS results scaled as $\sqrt{K}$, which grows too fast and violates the bound.

  • Comparison with NRF: The authors also show that fully-connected machines actually possess a higher storage capacity than non-overlapping (tree-like) architectures, a benefit driven by the small negative correlations between hidden unit weights.

Limitations and Future Directions

While this work successfully resolves the bound violation, it leaves a few open questions for future research:

  • RS vs. RSB: The authors acknowledge that their "new" RS calculation might still be an approximation. A full "Replica Symmetry Breaking" (RSB) calculation could yield even greater accuracy, though it is significantly more mathematically complex.
  • Numerical Prefactors: There remains a slight discrepancy (a factor of $\sqrt{2}$) between this method and a recent one-step RSB calculation using the older Gardner method. It is still unclear which approach provides the "truer" coefficient.
  • Parity Machines: The authors suggest their findings could likely be extended to "parity machines" (where the output is the product of hidden unit signs), hypothesizing that they too would follow the $K \ln K$ scaling. This extension is left for future publication.

Summary updated

BibTeX
@inproceedings{xiong1997storage,
  author = {Yuansheng Xiong and Chulan Kwon and Jong-Hoon Oh},
  title = {{The Storage Capacity of a Fully-Connected Committee Machine}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1997},
}
Figure