Learning in Networks of Nondeterministic Adaptive Logic Elements

Richard C. WindeckerNeurIPS 1987

Introduction

In the late 1980s, a central challenge in neural network research was the "credit assignment problem." When a large network produces an output and receives a single, global "good" or "bad" signal from its environment, how does the system determine which specific internal neurons contributed to that success or failure?

While contemporary models like early backpropagation solved this by calculating precise error gradients for every connection, biological systems often learn from general, non-specific reinforcement (such as dopamine release). This paper bridges that gap by introducing Nondeterministic Adaptive Threshold-logic gates (NATs)—simple processing elements that use stochasticity to successfully learn non-linear logic and temporal strategies using only a single, global reinforcement signal.

The NAT Model

The author proposes the NAT as a probabilistic alternative to standard fixed-output logic gates. The model is built on several key principles:

  • Stochastic Output: A NAT calculates a weighted sum of its inputs. However, instead of a hard cutoff, it uses a normal distribution to determine the probability of outputting a $+1$ or a $-1$. This "noise" acts as a feature, allowing the network to naturally explore different state combinations.
  • Global Reinforcement: When the network receives a reinforcement signal ($R = +1, -1, \text{or } 0$), every NAT updates its weights using the same signal. Weights are incremented to make the recent output more likely if $R=+1$, or less likely if $R=-1$. Positive and negative reinforcement are treated symmetrically to prevent weights from drifting infinitely.
  • Timing Discipline: To handle complex architectures, NATs are organized into layers. Signals flow sequentially, and reinforcement is applied only after the final output is produced.
  • Training Strategies: The author employs early forms of curriculum learning. If a network gets "stuck" in a suboptimal state, the trainer temporarily focuses reinforcement on specific underperforming elements to nudge them toward correct behavior.

Experimental Results

The paper evaluates NAT networks on synthetic benchmarks designed to test specific computational capabilities, yielding strong results compared to contemporary methods.

Pattern Production and Scaling

In a pattern production task, a network was tasked with generating specific bit strings. The author demonstrated that training time scales remarkably well. Moving from a single NAT to a 16-element network only increased the average training time from 13 to 115 trials, highlighting the efficiency of the model's two-stage training strategy.

Training trials for pattern production scaling from 1 to 16 NATs.

Solving Non-Linear Logic (XOR)

The XOR (Exclusive OR) problem is a classic non-linearly separable task that requires at least one hidden layer to solve. The paper provides an "existence proof" that hidden units can be trained effectively using only a global reward signal, provided the units are stochastic. The NAT network learned the XOR function in an average of 681 trials, significantly outperforming contemporary models by Barto (~3500 trials) and Rumelhart (2232 trials).

Comparison of average trials required to learn the XOR function against contemporary models.

Temporal Memory

In a sequential "Matching Pennies" game, the network had to predict an opponent's move based on past behavior. A sequential NAT-net learned to exploit an opponent's strategy (repeating a move from two turns ago) in 98 out of 100 sessions, averaging 468 plays to reach mastery.

Discussion and Limitations

Windecker's work demonstrates that a simple stochastic model paired with a smart training strategy can outperform more complex deterministic models with poor training regimes. By relying on nondeterminism, the network naturally explores until a correct combination is "locked in" by global reinforcement.

However, the model has limitations. NATs are based on threshold logic, meaning individual nodes can only learn linearly separable functions; complex mappings require many layers. Furthermore, the "training strategies" used to prevent the network from getting stuck were manually designed by the author, lacking a generalized algorithm for arbitrary tasks. Finally, while inspired by biological nondeterminism, the author notes there is no strict one-to-one correspondence between NATs and physiological neurons. Future work, the author suggests, should focus on characterizing exactly how and why networks get "stuck" as a function of their environment.

Summary updated

BibTeX
@inproceedings{windecker1987learning,
  author = {Richard C. Windecker},
  title = {{Learning in Networks of Nondeterministic Adaptive Logic Elements}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1987},
}
Figure