A Unified Gradient-Descent/Clustering Architecture for Finite State Machine Induction

Sreerupa Das, Michael MozerNeurIPS 1993 · OpenReview

TL;DR

Researchers at the University of Colorado developed DOLCE, an architecture that integrates adaptive clustering directly into the training of recurrent neural networks (RNNs). By forcing continuous hidden states to "snap" into discrete clusters during gradient descent, DOLCE significantly improves a network's ability to learn and generalize finite-state machine (FSM) logic from example strings.

The Problem: Continuous Networks vs. Discrete Logic

Recurrent neural networks are powerful tools for sequence processing, but they have a fundamental "personality mismatch" with Finite State Machines (FSMs). While an FSM moves between a finite set of crisp, discrete states (e.g., transitioning cleanly from "State A" to "State B"), an RNN operates in a continuous, high-dimensional space.

In practice, this means that even if an RNN learns to emulate an FSM on short strings, its internal state often "drifts" over time. On longer sequences, this cumulative noise causes the network to lose track of which state it should be in, leading to poor generalization. Previous attempts to fix this either quantized the states after training (which is often too late) or used "rigid" quantization during training that broke gradient descent, making the model nearly impossible to train effectively.

Methods: The DOLCE Architecture

The authors introduce DOLCE (Dynamic On-Line Clustering and State Extraction). The core innovation is a clustering module placed directly after the hidden layer. Instead of just passing the raw hidden activity forward, the module maps the activity to a "true" discrete state before feeding it back into the recurrent loop.

The DOLCE architecture inserts a clustering module directly into the recurrent loop, mapping continuous hidden activity to discrete states.

The paper explores two versions of this module:

  1. Unsupervised (DF): Uses Forgy’s algorithm to partition the state space.
  2. Supervised Mixture Model (DG): This is the more sophisticated approach. It assumes the hidden state is a "true" discrete state corrupted by Gaussian noise.
  3. Soft MAP Estimator: To keep the system differentiable (so gradient descent still works), they use a "soft" Maximum A Posteriori (MAP) estimator.
  4. Annealing: They use a "temperature" parameter tied to the training error. As the network gets better at the task, the "temperature" drops, and the internal representations transition from fuzzy/continuous to crisp/discrete.
  5. Complexity Cost: They include an entropy-based penalty that encourages the model to use the minimum number of states necessary, effectively "pruning" unused clusters.

Key Insights and Ideas

  • Inductive Bias as an Integral Part of Learning: The "aha moment" of this research is that quantization shouldn't be a post-processing step. By making the clustering part of the cost function, the network learns weights that naturally produce clusterable states.
  • The Noise Assumption: Treating the continuous hidden state as a "noisy version" of a discrete state allows the authors to use Bayesian inference (MAP estimation) to recover the intended state.
  • Differentiable Discreteness: By using a soft-max style approach to state selection and gradually increasing the "certainty" (via annealing), they bypass the "flat gradient" problem that usually plagues discrete neural architectures.
Hidden state distributions before and after successful training. The annealing process forces broad, continuous distributions to collapse into sharp, discrete peaks.

Datasets and Evaluation

The primary evaluation uses the Tomita Languages, a classic benchmark set of seven regular languages (e.g., "strings with no odd number of consecutive 1s" or "strings where the difference between the number of 0s and 1s is a multiple of three").

  • Training: 50 to 150 examples per language, with string lengths between 5 and 10.
  • Testing: 3,000 strings per language to test generalization.

The paper also explores a real-world application involving software engineering process data, where the goal is to predict the next operation in a software development lifecycle.

Key Results

  • Superior Generalization: Across all seven Tomita languages, the supervised DOLCE (DG) model outperformed standard RNNs (NC), rigid quantization (RQ), and post-hoc clustering (LQ).
  • Robustness to String Length: Because DOLCE "resets" the state to a cluster center at every step, it doesn't suffer from the state drift that causes standard RNNs to fail on long strings.
  • Real-World Performance: In the software engineering task, DOLCE was three times more accurate than a standard recurrent network, even though the underlying data was noisy and not perfectly described by a simple FSM.

Limitations and Future Work

  • Initial State Count: The user must initialize the model with a maximum number of clusters ($T$). While the complexity cost helps prune unnecessary ones, if $T$ is set too low initially, the model cannot learn the task and must be restarted.
  • Computational Overhead: Adding a Gaussian Mixture Model-based clustering module into the inner loop of backpropagation through time increases the computational cost per training epoch.
  • Scope: While the authors suggest this could apply to feedforward networks, the paper focuses almost exclusively on FSM induction in recurrent architectures. Future work would involve testing DOLCE on more complex, non-regular language tasks or higher-level cognition modeling.

Summary updated

Abstract

Although recurrent neural nets have been moderately successful in learning to emulate finite-state machines (FSMs), the continu(cid:173) ous internal state dynamics of a neural net are not well matched to the discrete behavior of an FSM. We describe an architecture, called DOLCE, that allows discrete states to evolve in a net as learn(cid:173) ing progresses. DOLCE consists of a standard recurrent neural net trained by gradient descent and an adaptive clustering technique that quantizes the state space. DOLCE is based on the assumption that a finite set of discrete internal states is required for the task, and that the actual network state belongs to this set but has been corrupted by noise due to inaccuracy in the weights. DOLCE learns to recover the discrete state with maximum a posteriori probabil(cid:173) ity from the noisy state. Simulations show that DOLCE leads to a significant improvement in generalization performance over earlier neural net approaches to FSM induction.
BibTeX
@inproceedings{das1993unified,
  author = {Sreerupa Das and Michael Mozer},
  title = {{A Unified Gradient-Descent/Clustering Architecture for Finite State Machine Induction}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1993},
  url = {https://openreview.net/forum?id=SyEqU_WOZB},
}
Figure