Threshold Network Learning in the Presence of Equivalences

John Shawe-TaylorNeurIPS 1991 · OpenReview

Introduction: The Sample Complexity Problem

In the early 1990s, researchers grappled with the "sample complexity" of neural networks: determining exactly how many training examples ($m$) are required to guarantee that a network performing well on training data will also generalize to unseen data. This challenge is the core of Probably Approximately Correct (PAC) learning.

While foundational work by Baum and Haussler provided sample complexity bounds for standard feedforward networks, many practical architectures—such as Time Delay Neural Networks (TDNNs) and Convolutional Neural Networks (CNNs)—utilized "weight sharing." By constraining groups of weights to share the same value, these networks intuitively required less data to train and generalized better. However, existing mathematical bounds failed to fully capture this structural advantage. This paper bridges that gap by providing a formal framework and tighter theoretical bounds for networks with symmetries and equivalences.

Theoretical Framework: Equivalence Networks

To analyze these architectures, the author introduces the concept of an Equivalence Network. This is defined as a threshold network where both the weights and the computational nodes are partitioned into equivalence classes. This abstraction is notably broader and more flexible than "Symmetry Networks," which rely on strict group theory and geometric transformations.

The core of the mathematical proof involves bounding the growth function—a measure of how many different ways a network can classify a set of $m$ points. Using combinatorial proofs and properties of convex functions (specifically $f(x) = x \log x$), the author demonstrates that the complexity of these networks is dominated by the number of unique weight classes ($W$) and the number of computational nodes ($N$), rather than the raw total of individual weights.

Key Insights and Mathematical Results

The most significant insight from this work is the formal proof that for generalization, the number of unique weights (weight classes) matters far more than the total number of connections. If a network possesses a million connections but only ten unique weight values, its flexibility—and consequently its risk of overfitting—is drastically lower than that of a standard fully connected network.

By plugging the new growth function bounds into general PAC theorems, the author proves that the Vapnik-Chervonenkis (VC) dimension of an equivalence network is bounded by $2W \log_2(eN)$. This represents a major improvement over previous bounds.

This leads to two primary theorems for the required sample size $m$ to achieve an error rate less than $\epsilon$ with confidence $1-\delta$:

  • Zero Training Error (Theorem 2.5): For a network that correctly classifies the entire training set, the required sample size is bounded by: $$m \ge \frac{1}{\epsilon(1 - \sqrt{\epsilon})} \left[ \log \left( \frac{1.3}{\delta} \right) + 2W \log \left( \frac{6\sqrt{N}}{\epsilon} \right) \right]$$
  • Low Training Error (Theorem 2.6): For a network that correctly classifies a large fraction of the training set, the bound is slightly more complex but maintains a similar logarithmic relationship with $W$ and $N$.

Remarkably, the resulting formula is structurally consistent with the bound for standard networks. The primary modification is the replacement of the total weight count with the number of weight classes ($W$), while the number of nodes ($N$) remains a factor due to the network's internal state transitions.

Limitations and Future Directions

As a purely theoretical work, the paper does not rely on empirical datasets but rather provides mathematical proofs applicable to any probability distribution. However, several limitations and areas for future work remain:

  • Threshold Units: The results are specifically derived for linear threshold units (nodes that output strictly 0 or 1). While standard at the time, modern deep learning relies on continuous activation functions like ReLU or Sigmoid. Though the core principles translate, the specific constants in the bounds would differ.
  • The $\log N$ Factor: The author conjectures that the $\log eN$ factor in the VC dimension bound is "real" and cannot be removed. Future work is suggested to find specific "high growth" functions to prove whether this factor is a fundamental requirement or merely an artifact of the proof techniques.
  • Conservative Bounds: While these bounds are significantly tighter than previous iterations, PAC bounds are notoriously conservative, often suggesting data requirements far larger than what is needed in practice. Refining these bounds remains an ongoing pursuit in learning theory.

Summary updated

Abstract

This paper applies the theory of Probably Approximately Correct (PAC) learning to multiple output feedforward threshold networks in which the weights conform to certain equivalences. It is shown that the sample size for reliable learning can be bounded above by a formula similar to that required for single output networks with no equivalences. The best previ(cid:173) ously obtained bounds are improved for all cases.
BibTeX
@inproceedings{shawetaylor1991threshold,
  author = {John Shawe-Taylor},
  title = {{Threshold Network Learning in the Presence of Equivalences}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1991},
  url = {https://openreview.net/forum?id=B1Vg1KW_WH},
}
Figure