Subgrouping Reduces Complexity and Speeds Up Learning in Recurrent Networks

David ZipserNeurIPS 1989

Training Recurrent Neural Networks (RNNs) has historically been plagued by severe computational bottlenecks. While RNNs are uniquely capable of simulating complex dynamical systems, the algorithms required to train them often suffer from crippling costs as network size increases. In the late 1980s, David Zipser addressed this fundamental limitation by proposing a "subgrouping" strategy for the Real-Time Recurrent Learning (RTRL) algorithm, making large-scale recurrent learning significantly more feasible.

The Problem: Scaling Recurrent Learning

In the early days of connectionism, two primary algorithms dominated recurrent learning: Backpropagation Through Time (BPTT) and Real-Time Recurrent Learning (RTRL). Both approaches had significant drawbacks when scaled.

BPTT works by "unrolling" the network into a massive feedforward stack over time. While mathematically straightforward, this approach consumes enormous amounts of memory, as the entire history of the network's states must be stored for the backward pass.

Backpropagation Through Time (BPTT) unrolls the network over time, requiring significant memory.

RTRL avoids this memory explosion by maintaining a fixed set of parameters (called $p$ values) that record the network's history in real-time. However, RTRL introduces a severe computational scaling problem. To update these $p$ values, the algorithm requires $O(wn^2)$ operations, where $n$ is the number of units and $w$ is the number of weights. Zipser described this scaling as "computationally unpleasant"—as networks grow, the time required to train them quickly becomes prohibitive.

The Solution: Subgrouped RTRL

To overcome RTRL's computational bottleneck, Zipser introduced Subgrouped RTRL, a method that partitions a large recurrent network into smaller, interconnected modules.

The strategy involves the following steps:

  1. Partitioning: A fully recurrent network with $n$ units is divided into $g$ smaller subnets, each containing $n/g$ units.
  2. Connectivity: Within a subnet, units remain fully recurrent. However, between subnets, units receive the "activities" (outputs) of units in other subnets as if they were external inputs.
  3. Localized Gradients: The core innovation is that the algorithm only tracks the sensitivities ($p$ values) for weights within their own subgroup. Because units in other subgroups are treated as external inputs, the network avoids calculating cross-subgroup error gradients.
Comparison of a Fully Recurrent architecture and a Subgrouped architecture, highlighting the use of activity-only connections between subgroups.

This "Activity-Only" shortcut drastically reduces the math required for each step. By ignoring the internal error derivatives of other subgroups, the number of $p$ values tracked per weight drops from $n$ to $n/g$. If the number of groups $g$ is increased in proportion to the total units $n$ (keeping the subnet size constant), the computational complexity drops dramatically from $O(wn^2)$ to potentially $O(w)$.

Experimental Results

The algorithm was tested on a symbolic logic task: training a Turing machine to balance parentheses. The network was fed a "tape" and tasked with producing the same outputs as a hardcoded Turing machine. A small, fully recurrent network with 12 units served as the benchmark.

Key Findings: * Massive Speedup: In the parenthesis-balancing task, Subgrouped RTRL was 10 times faster than standard RTRL. * Consistent Learning Efficiency: All three tested algorithms (BPTT, RTRL, and Subgrouped RTRL) required roughly the same number of learning cycles to master the task. * Success Rates: BPTT proved the most robust, succeeding 80% of the time. Both standard RTRL and Subgrouped RTRL succeeded 50% of the time.

While BPTT was still faster overall than Subgrouped RTRL in this specific, small-scale implementation, the subgrouping method provided a crucial path forward. It allowed RTRL to scale to much larger networks where BPTT's memory requirements would otherwise become the primary bottleneck.

Insights and Limitations

Zipser's work highlights that modularity is not just a biological preference, but a mathematical necessity for scaling learning in complex dynamical systems. You do not always need a global gradient across an entire recurrent architecture to learn effectively.

However, the study noted a few limitations:

  • Local Minima: The lower success rate of RTRL-based methods (50% vs. BPTT's 80%) suggests that the real-time nature of the algorithm may make it more prone to getting stuck in local minima.
  • Scale of Experiments: The tests were conducted on a very small 12-unit network. The paper did not explore how subgrouping affects performance on massive datasets or highly complex dynamical tasks.
  • Optimal Grouping: The research assumed a simple division into equal-sized subnets and did not explore how to determine the optimal number of groups ($g$) or whether specialized connectivity patterns would further improve results.

Despite these limitations, Subgrouped RTRL demonstrated that localized gradient calculations could yield massive computational savings without sacrificing the fundamental capabilities of recurrent learning.

Summary updated

BibTeX
@inproceedings{zipser1989subgrouping,
  author = {David Zipser},
  title = {{Subgrouping Reduces Complexity and Speeds Up Learning in Recurrent Networks}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1989},
}
Figure