On Multi-Layered Connectionist Models: Adding Layers vs. Increasing Width

Chung-Jen HoIJCAI 1989

Abstract: This theoretical study from 1987 investigates the fundamental trade-offs between depth and width in neural network architectures. By analyzing "Layered Connectionist Machines" composed of binary threshold units, the research quantifies how representational capacity grows under different scaling strategies. The findings suggest that for these specific models, expanding the width of a shallow network is significantly more efficient than adding layers to a deep network, both in terms of the variety of solvable problems and computational time complexity.

Introduction: The Scaling Dilemma

In the late 1980s, as the connectionist movement sought to overcome the limitations of single-layer perceptrons, a critical design question emerged: how should a network be expanded to handle more complex tasks? Given a fixed resource budget, should an architect add more layers (increasing depth) or more neurons per layer (increasing width)?

A multi-layered connectionist machine architecture showing layers 0 through 4.

This paper addresses this dilemma by formalizing the "problem-solving power" of a network as the total number of Boolean functions it can represent. It compares the growth of this power when adding a single layer to a fixed-width network versus adding a single unit to the hidden layer of a two-layer network.

Defining the Connectionist Machine

The study utilizes "Layered Connectionist Machines," which are networks of binary neurons. Each neuron operates on a simple threshold logic: it outputs a 1 if the weighted sum of its inputs meets or exceeds a predefined threshold, and 0 otherwise.

A single binary threshold neuron with five inputs, specific weights, and a threshold of 2.

Mathematically, the output $y$ is defined by: $y = 1$ if $\sum w_i x_i \geq \text{threshold}$, else $y = 0$.

By stacking these units into layers, the author creates a framework to analyze how information propagates and how complexity is built.

Key Insights: Why Width Wins

The core of the paper's argument lies in the disparity between scaling rates:

  • The Power of the Second Layer: The author reinforces that a two-layer network (one hidden layer) acts as a universal approximator for Boolean functions, provided the hidden layer is sufficiently wide.
  • Growth Rates: The mathematical proofs reveal a massive difference in efficiency. Adding one layer to a network of fixed width $n$ increases the number of solvable problems by a factor of $O(n^3)$. In contrast, adding just one unit to the width of a two-layer network increases the number of solvable problems by a factor of $O(n^n)$.
  • Time Complexity: In these models, "time" is synonymous with the number of layers (the steps required for signal propagation). A wide two-layer model can solve complex problems in constant time (2 steps), whereas a deep, narrow model might require time steps proportional to the number of layers, which can grow exponentially relative to input size for certain functions.

Conclusion and Modern Context

The primary conclusion is that "increasing width is better than adding layers" for extending the capabilities of these binary threshold models. While both deep and shallow architectures can theoretically represent any function given enough total neurons—specifically $\Omega(2^n/n^2)$ for an input of size $n$—the shallow, wide architecture does so with much lower latency.

However, it is important to note the limitations of this 1987 perspective. Modern deep learning utilizes continuous activation functions and gradient-based optimization. While a wide, shallow network may have the representational capacity to solve a problem, depth is often preferred in practice because it creates a hierarchical feature space that is significantly easier to learn via backpropagation. This paper remains a foundational theoretical touchstone for understanding the raw computational limits of layered architectures.

Summary updated

BibTeX
@inproceedings{ho1989multi,
  author = {Chung-Jen Ho},
  title = {{On Multi-Layered Connectionist Models: Adding Layers vs. Increasing Width}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1989},
}
Figure