Learning by Choice of Internal Representations

Tal Grossman, Ronny Meir, Eytan DomanyNeurIPS 1988 · OpenReview

Published in the late 1980s, this paper presents a fascinating alternative to the dominant Back-propagation (BP) paradigm for training neural networks. While BP relies on continuous functions and gradient descent to adjust weights, the authors propose an algorithm called CHIR (Choice of Internal Representations). CHIR treats the states of the hidden layer as the primary variables to be learned, using a discrete search process to find internal representations that make the final classification task easy enough for a simple Perceptron to solve.

Instead of using calculus to nudge weights toward a minimum error, CHIR directly searches for the "correct" binary patterns that hidden layers should form. Once these internal representations are found, the weights are calculated using the classic, biologically plausible Perceptron Learning Rule (PLR). For discrete logic problems, this approach often results in significantly faster training than Back-propagation.

The Credit Assignment Problem

In the 1980s, the "credit assignment problem" was the central hurdle for multi-layer neural networks: when a network makes a mistake, which specific hidden unit or connection is to blame? Back-propagation solved this by using continuous, differentiable activation functions (like sigmoids) to "flow" the error backward.

However, BP has drawbacks: it can be slow, get stuck in local minima, and requires high-precision floating-point math. The authors wanted a way to train networks composed of binary linear threshold elements (units that are strictly +1 or -1). These networks are not differentiable, making standard BP inapplicable. They sought an algorithm that was computationally simpler and potentially more "biologically plausible" than gradient descent.

The CHIR Algorithm

The authors introduce the CHIR algorithm, which breaks the learning process into a cycle of four stages:

  1. SETINREP: Generate a table of current hidden layer states by passing the training data through the existing weights.
  2. LEARN23: Use the Perceptron Learning Rule (PLR) to find weights between the hidden layer and the output layer. If the PLR cannot find a solution for the current hidden states within a set number of sweeps (the "impatience" parameter), it moves on.
  3. INREP: This is the core innovation. If the output is wrong, the algorithm randomly flips bits in the hidden layer's representation of that specific input. If flipping a bit moves the output in the right direction, the change is kept. This creates a new "target" for what the hidden layer should look like.
  4. LEARN12: Use the PLR to update the weights between the input and hidden layers so they produce the new internal representations found in the previous step.

Crucially, the algorithm can be implemented using integer weights, avoiding the round-off errors and hardware complexity associated with floating-point calculations.

Key Insights

  • Representations over Weights: The core realization is that weights are secondary. If you can define what the hidden layer ought to see, the weights can be solved easily using 1960s-era technology (the PLR).
  • Discrete Search: By treating the problem as a search in the space of binary tables rather than a descent on a continuous surface, the algorithm avoids some of the "flat" regions and local minima that plague gradient descent.
  • Impatience as a Feature: The algorithm uses "impatience" parameters to decide when to stop trying to force a set of weights and instead try changing the internal representation. This prevents the model from wasting time on impossible weight configurations.
  • Hardware Friendly: Because it works with binary states and integer weights, this approach is highly suitable for direct hardware implementation (FPGA/ASIC).

Experimental Results

The algorithm was evaluated on four classic Boolean logic predicates that are notoriously difficult for single-layer networks: Contiguity (2 vs. 3 clumps), Symmetry, Parity, and Combined Symmetry-Parity. The authors compared CHIR against Back-propagation and found significant performance gains.

Speed and Scaling: For the "2 vs 3 clumps" problem, CHIR required significantly fewer training sweeps than BP as the number of hidden units increased.

Comparison of median training sweeps for CHIR versus Back-propagation as hidden units increase.

This speed advantage became even more pronounced on the notoriously difficult Parity problem. On the $N=7$ Parity problem, CHIR reached a solution in a median of 30 sweeps, while BP took 800. For $N=8$, CHIR took 150 sweeps compared to BP's 2000.

Performance comparison on the Parity problem showing CHIR requires far fewer sweeps than BP.

Reliability: In the Parity tests, CHIR achieved a 100% success rate in finding a solution within the time limit, whereas BP is known to occasionally fail or get stuck in local minima.

Limitations and Future Directions

While highly effective for these tasks, CHIR has limitations:

  • Memory Overhead: The algorithm requires storing the internal representations for every training pattern. The authors acknowledge this is "biologically implausible" and could be a bottleneck for very large datasets.
  • Architecture Constraints: The primary study focused on two-layer networks (one hidden layer). Extending the bit-flipping search to multiple hidden layers likely increases complexity significantly.
  • Discrete Focus: While excellent for logic and classification, it is not immediately clear how this would translate to continuous-output tasks like regression or image generation.

Future directions suggested by the authors include developing versions that do not require storing all representations and extending the logic to networks with feedback (recurrent networks).

Summary updated

Abstract

We introduce a learning algorithm for multilayer neural net(cid:173) works composed of binary linear threshold elements. Whereas ex(cid:173) isting algorithms reduce the learning process to minimizing a cost function over the weights, our method treats the internal repre(cid:173) sentations as the fundamental entities to be determined. Once a correct set of internal representations is arrived at, the weights are found by the local aild biologically plausible Perceptron Learning Rule (PLR). We tested our learning algorithm on four problems: adjacency, symmetry, parity and combined symmetry-parity.
BibTeX
@inproceedings{grossman1988learning,
  author = {Tal Grossman and Ronny Meir and Eytan Domany},
  title = {{Learning by Choice of Internal Representations}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1988},
  url = {https://openreview.net/forum?id=H1-hcvZuWS},
}

Loading related content...

Figure