The Power of Amnesia

Dana Ron, Yoram Singer, Naftali TishbyNeurIPS 1993

TL;DR

This paper introduces an efficient algorithm for learning variable-length Markov processes using Prediction Suffix Trees (PSTs). By adaptively deciding which parts of a history are worth remembering and which can be "forgotten," the model captures long-range dependencies in data (like language or DNA) without the exponential state-space explosion of traditional fixed-order Markov models.

What Problem Does This Paper Address?

In sequence modeling, we often use Markov models to predict the next symbol based on the previous $k$ symbols. However, researchers face a "Goldilocks" dilemma:

  • Short memory (Low $k$): The model is computationally cheap but "dumb," failing to capture syntactic or semantic structures that span many tokens.
  • Long memory (High $k$): The model becomes more powerful but suffers from the curse of dimensionality. For an alphabet of size $|\Sigma|$, a $k$-order model requires $|\Sigma|^k$ states. Even for a small alphabet and $k=10$, this number is astronomically larger than any available dataset.

The authors argue that natural sequences (like English text) have multiple temporal scales. Some patterns are short-range (like the letter 'u' following 'q'), while others are long-range (like the phrase "there was"). We need a model that has "deep" memory only where it actually provides predictive value and "amnesia" everywhere else.

Methods

The authors propose a learning algorithm for Prediction Suffix Trees (PSTs). Unlike a standard Markov chain that always looks back $k$ steps, a PST is a tree where each node represents a variable-length suffix of the past.

The Core Algorithm:

  1. Iterative Expansion: The algorithm starts with a single root node (zero memory). It then tests potential suffixes (histories) level-by-level.
  2. The "Surprise" Metric: A new node (a longer history) is added to the tree only if it is statistically different from its parent (the shorter history).
  3. Weighted KL Divergence: To measure this difference, the authors use the Kullback-Leibler (KL) divergence between the probability distributions of the next symbol given the long vs. short history. Crucially, they weigh this "surprise" by the probability of the history occurring in the first place. This prevents the model from over-fitting to rare, long strings that don't significantly impact overall prediction error.
  4. Conversion to Automata: Once the PST is built, it can be transformed into a Probabilistic Finite Automaton (PFA) for efficient, real-time sequence generation or prediction.

Datasets

The paper evaluates the algorithm on three distinct types of data:

  • Synthetic "Toy" Data: A 1000-symbol sequence generated by a known automaton to verify if the algorithm can recover the original structure.
  • Natural Language (The Bible): Used to model English text. The alphabet included 26 letters plus a blank space ($|\Sigma|=27$).
  • Genetics (E. coli DNA): Specifically, intergenic regions of the E. coli genome, using the four-letter DNA alphabet (A, C, T, G).

Key Insights and Ideas

  • Selective Memory is Efficiency: By only keeping "informative" suffixes, the model stays compact. For the Bible dataset, setting a maximum depth of $L=30$ resulted in fewer than 3,000 states. A full 30th-order Markov model would have required $27^{30}$ states—a physical impossibility.
  • Capturing Multi-Scale Structure: The resulting model naturally mixed very short states (2 characters like 'qu') with long ones (8-9 characters like "shall be"), mirroring how humans actually process language.
  • PSTs vs. HMMs: While Hidden Markov Models (HMMs) are powerful, they often require manual tuning of their architecture (number of states, transitions). The PST approach is more "plug-and-play," automatically discovering the necessary structure from the data.

Key Results

  • Spelling Correction: The authors tested the model's ability to "clean" corrupted text. Even with 20% noise (randomly altered letters) and additional noise where spaces were replaced by random letters, the model successfully reconstructed the original text using dynamic programming (finding the most probable state sequence).
  • DNA Prediction: On E. coli DNA, the PST model achieved a normalized log-likelihood (NLL) comparable to state-of-the-art HMM-based methods. It achieved this with only 80 states, demonstrating that DNA sequences contain significant variable-length statistical dependencies.
  • Computational Efficiency: The algorithm runs in polynomial time relative to the parameters of the problem, making it far more scalable than exhaustive search methods.

Limitations and Future Work

  • Length Distributions: The authors note that their model performed slightly worse than HMMs on DNA because HMMs can explicitly model the length of segments (e.g., how long an intergenic region typically is), whereas PSTs are purely transition-based.
  • Recursive Structure: While PSTs handle variable lengths, they are still finite-state. They cannot capture truly recursive or context-free grammars (like nested parentheses) that exist in complex languages.
  • Future Directions: The authors suggest investigating hierarchical models based on these automata to capture even larger-scale correlations in natural language.

Summary updated

BibTeX
@inproceedings{ron1993power,
  author = {Dana Ron and Yoram Singer and Naftali Tishby},
  title = {{The Power of Amnesia}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1993},
}
Figure