A Connectionist Symbol Manipulator that Discovers the Structure of Context-Free Languages

Michael Mozer, Sreerupa DasNeurIPS 1992 · OpenReview

TL;DR

This paper introduces a neural network architecture that learns to "parse" context-free languages by discovering their underlying symbolic rewrite rules. By utilizing a continuous, differentiable stack, the model bridges the gap between connectionist learning (backpropagation) and symbolic manipulation, successfully inducing grammars for tasks like balanced parentheses and natural language fragments.

Introduction

Hierarchical and recursive structures are fundamental to human cognition—think of the nested clauses in a sentence or the repeating patterns in music. While traditional symbolic AI handles these structures easily using parsers and grammars, standard neural networks of the early 90s struggled with deep recursion and long-distance dependencies.

The authors aim to solve the "structure discovery" problem: Can a neural network look at a bunch of strings (some grammatical, some not) and figure out the hierarchical rules that govern them? Specifically, they target Context-Free Languages (CFLs), which require a memory mechanism (like a stack) to process.

Methods

The authors propose a "Demon Model" inspired by blackboard architectures, designed to learn hierarchical reductions.

The Demon Architecture

The model consists of "demon" units that watch the top of a stack. Each demon is trained to recognize a specific pattern of symbols. When a demon "fires," it pops those symbols and pushes its own "identity" (a new symbol representing a reduced description) back onto the stack.

The Demon Architecture

Continuous Stack

To make the system trainable via backpropagation, the authors replaced the discrete stack with a continuous one. Symbols on the stack have a "thickness" (a value between 0 and 1). This allows for "partial" pushes and pops, making the entire operation differentiable.

Continuous Stack with Thickness

Template Matching and Training

Demon units compute the distance between their weights and the current stack symbols. Using a normalized exponential transform (similar to modern Softmax), the demons compete to see which one matches the current stack state best.

The model is trained using Backpropagation Through Time (BPTT). It is fed positive and negative examples of a grammar. The objective function rewards the model if the stack contains only the "Start" symbol ($S$) after processing a valid string, and anything else for an invalid one.

Datasets

The authors evaluated the model on four synthetic grammars of increasing complexity:

  1. $a^n b^n$: The classic "count and match" CFL.
  2. Parenthesis Balancing: Ensuring every '(' has a matching ')'.
  3. Postfix Notation: Mathematical expressions like a b +.
  4. Pseudo Natural Language: A small grammar involving Noun Phrases (NP), Verb Phrases (VP), determiners, and nouns (e.g., "the dog chased the cat").

These datasets were generated by hand, typically featuring 3-5 times as many negative examples as positive ones to provide a robust training signal.

Key Insights

  • Symbolic Reduction as Neural Learning: The most striking insight is that a single layer of modifiable weights can represent symbolic rewrite rules. Because the architecture is so constrained, the learned weights are directly interpretable as grammar rules (e.g., "If you see an 'a' and a 'b', replace them with 'S'").
  • Differentiable Memory: By treating the stack as a collection of items with "thickness," the authors created a way to "unfold" a stack-based machine in time. This pre-dates more modern differentiable data structures like the Neural Turing Machine.
  • LR(0) Parsing: The model effectively learns to perform LR(0) parsing—reading strings from left to right and reducing them without needing to "look ahead" at future symbols.

Key Results

  • Perfect Generalization: On the first three grammars ($a^n b^n$, parentheses, and postfix), the model achieved 100% generalization accuracy on longer strings than those seen during training.
  • Interpretable Weights: The authors show that the weights clearly map to the intended rewrite rules of the grammar.
  • Superiority over Automata Models: The "Demon Model" successfully learned the pseudo-natural language grammar, a task that previous state-of-the-art connectionist models (which tried to learn the dynamics of a pushdown automaton directly) failed to solve.

Limitations and Future Work

  • Pre-specified Capacities: The user must specify the number of demon units and their "identities" (the symbols they represent) before training. The model doesn't yet "spawn" new symbols on its own.
  • LR(0) Constraint: The current version cannot handle grammars that require "look-ahead" (LR(n) grammars), though the authors suggest this could be fixed by connecting the input queue directly to the demon units.
  • Scalability: While it works for small, clean grammars, it is unclear how the model would handle the noisy, ambiguous, and massive grammars found in real-world natural language processing.

Summary updated

Abstract

We present a neural net architecture that can discover hierarchical and re(cid:173) cursive structure in symbol strings. To detect structure at multiple levels, the architecture has the capability of reducing symbols substrings to single symbols, and makes use of an external stack memory. In terms of formal languages, the architecture can learn to parse strings in an LR(O) context(cid:173) free grammar. Given training sets of positive and negative exemplars, the architecture has been trained to recognize many different grammars. The architecture has only one layer of modifiable weights, allowing for a straightforward interpretation of its behavior. Many cognitive domains involve complex sequences that contain hierarchical or recursive structure, e.g., music, natural language parsing, event perception. To il(cid:173) lustrate, "the spider that ate the hairy fly" is a noun phrase containing the embed(cid:173) ded noun phrase "the hairy fly." Understanding such multilevel structures requires forming reduced descriptions (Hinton, 1988) in which a string of symbols or states ("the hairy fly") is reduced to a single symbolic entity (a noun phrase). We present a neural net architecture that learns to encode the structure of symbol strings via such red uction transformations. The difficult problem of extracting multilevel structure from complex, extended sequences has been studied by Mozer (1992), Ring (1993), Rohwer (1990), and Schmidhuber (1992), among others. While these previous efforts have made some
BibTeX
@inproceedings{mozer1992connectionist,
  author = {Michael Mozer and Sreerupa Das},
  title = {{A Connectionist Symbol Manipulator that Discovers the Structure of Context-Free Languages}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1992},
  url = {https://openreview.net/forum?id=rkVd1KWdWB},
}
Figure