A Neural Network Classifier Based on Coding Theory

Tzi-Dar Chiueh, Rodney M. GoodmanNeurIPS 1987

This 1988 paper from the California Institute of Technology presents a clever bridge between two fields that, at the time, were often treated separately: neural networks and error-correction coding theory. By reframing the act of "recognizing a pattern" as "decoding a noisy signal," the authors developed a classifier that significantly outperformed the then-dominant Hopfield network models.

The Problem with Hopfield Networks

In the late 1980s, the Hopfield network was the standard for associative memory, but it had a major flaw: capacity. A Hopfield network with $N$ neurons could only reliably store about $0.15N$ patterns. If you tried to store more, the "crosstalk" between memories would cause the system to fail.

Furthermore, Hopfield networks rely on iterative feedback loops to converge on a memory, which can be slow and computationally expensive. The authors sought a way to build a classifier where the number of classes ($M$) scales linearly with $N$ and remains stable even when the input is heavily corrupted by noise.

The Core Concept: Classification as Decoding

The "aha moment" of the paper is realizing that a noisy input is essentially a "corrupted codeword." By using codes designed for deep-space communication or telecommunications, neural networks can leverage inherent error-correction properties to become far more robust.

Mapping from irregular feature space to uniform code space.

In a standard feature space, classes might have irregular, overlapping boundaries with varying "attraction radii"—meaning some memories might have a wider reach and overwhelm others. By mapping these features into a structured "code space" using mathematically structured codewords (like Hadamard matrix codes or Maximal Length Sequence PN codes), the model ensures that every class has a fair and uniform "territory." These pseudo-orthogonal codes keep every codeword roughly the same distance from every other codeword.

Architecture and Methods

The authors introduce a two-stage feedforward architecture to execute this transformation and classification, moving away from the iterative feedback of Hopfield nets.

The two-stage feedforward architecture mapping features to code space and decoding the class.
  1. The Transform ($\mathcal{L}$): The input feature vector is mapped to an internal representation in the code space using a single-layer feedforward network. The authors tested two ways to calculate the connection weights: an Outer Product (Hebbian-style) approach, and a Pseudo-inverse method. The Pseudo-inverse method proved essential for real-world data because it mathematically "untangles" highly correlated input patterns.
  2. The Decoder: The second layer correlates the noisy internal codeword with the known set of valid codewords. It uses a simple thresholding logic (a "maximum-picking" or winner-take-all circuit) to pick the closest match, effectively performing error correction to identify the correct class.

Datasets and Results

The paper evaluates the model using synthetic random vectors (to measure attraction radius and capacity) and a practical character recognition task using $9 \times 7$ pixel arrays. The character dataset is particularly challenging because letters like 'E' and 'F' are highly correlated.

  • Massive Capacity Increase: For a network with $N=63$ neurons, the Hopfield model could only store about 5 classes reliably. The new coding-theory-based classifier stored 47 classes under the same conditions.
  • Superior Noise Tolerance: At a noise level where 8 bits of the input were flipped (roughly 12% noise), the Hopfield model could only handle 4 classes, while the new model successfully handled 27.
  • Efficiency: The feedforward structure requires fewer neurons and connection weights than the iterative Hopfield alternative, making it faster and easier to implement in VLSI hardware.

Limitations and Future Directions

While the network is simpler than a Hopfield net, the "maximum-picking" circuit at the end requires specific hardware considerations, such as high dynamic range weights. Additionally, the system is designed for a pre-defined set of classes; the paper does not discuss how the system might adapt or learn new classes "on the fly" without recalculating the transform matrices. Finally, the authors note that using higher-rate codes (like BCH codes) might increase efficiency but could decrease the "minimum distance" between classes, potentially making the system more sensitive to noise.

Summary updated

BibTeX
@inproceedings{chiueh1987neural,
  author = {Tzi-Dar Chiueh and Rodney M. Goodman},
  title = {{A Neural Network Classifier Based on Coding Theory}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1987},
}
Figure