Improvements to the Sequence Memoizer

Jan Gasthaus, Yee Whye TehNeurIPS 2010 · OpenReview

The Sequence Memoizer (SM) is a highly effective Bayesian model for sequence data, achieving state-of-the-art performance in tasks like language modeling and data compression. Its primary advantage lies in its ability to capture long-range dependencies without being restricted by a fixed Markov order. However, despite its predictive power, the standard SM has historically faced significant computational and predictive hurdles.

This paper introduces major upgrades to the Sequence Memoizer, relaxing previous constraints on hyperparameters and introducing a "compact" memory representation. These changes significantly improve the model's predictive accuracy while drastically reducing its memory footprint and inference time.

The Challenges: Overconfidence and Memory Bloat

Before these improvements, the Sequence Memoizer struggled with two primary issues:

  1. Overconfidence: When the model processes a long, unbroken string of the same symbol, it tends to become overly confident that the symbol will repeat indefinitely. When the sequence inevitably changes, the model's predictions suffer heavily.
  2. Memory Bloat: Standard inference algorithms, such as Gibbs sampling, rely on the "Chinese Restaurant Franchise" representation. This requires storing granular details about every "table" and "customer" in a massive hierarchical structure. For large datasets, this state space becomes computationally prohibitive.

To keep the math tractable, previous implementations often fixed certain concentration parameters to zero, which unfortunately limited the model's flexibility and exacerbated the overconfidence problem.

Methodological Innovations

To address these limitations, the authors propose three core technical advancements:

1. Flexible Hyperparameters

The authors derive a mathematical framework that allows for non-zero concentration parameters ($\alpha > 0$) while preserving the crucial "coagulation and fragmentation" properties that make the SM efficient. By setting the concentration of a child node based on its parent's discount factor ($\alpha_u = \alpha_{\sigma(u)}d_u$), the model introduces a form of regularization. This gives more weight to shorter contexts (the "parent" nodes), which are generally less extreme in their predictions, directly mitigating the overconfidence problem.

2. Compact Representation

The paper proves that storing the full seating arrangement of the Chinese Restaurant Franchise is unnecessary. Instead, the model only needs to track the minimal sufficient statistics: the number of customers ($c$) and the number of tables ($t$) for each context/symbol pair. This realization allows for a massive reduction in the state space the algorithm must track.

3. Re-instantiating Sampler

Because the new compact representation makes standard Gibbs sampling difficult (it requires calculating complex generalized Stirling numbers), the authors developed a novel "re-instantiating" sampler. This algorithm temporarily reconstructs the necessary seating arrangement on-the-fly using a forward-backward algorithm, performs a sampling move, and then discards the extra data to conserve memory.

Key Results

The authors evaluated their improvements on two classic benchmarks: the Calgary Corpus (a byte-level model with a small alphabet) and the Brown Corpus (a word-level model with a large alphabet).

  • Improved Accuracy: The introduction of flexible hyperparameters proved highly effective. On the Brown corpus, increasing the concentration parameter $\alpha$ from 0 to 20 improved the average log-loss from 8.45 to 8.32.
  • Memory Efficiency: The compact representation significantly reduced the number of integers that needed to be stored. These savings were especially pronounced in the byte-level model, where many customers share the same context/symbol pairs.
  • Inference Speed: The "re-instantiating" sampler proved to be vastly more efficient than the original Gibbs sampler, avoiding the heavy numerical overhead of computing high-dynamic-range Stirling numbers in the log domain.
Performance and memory scaling of the new Sequence Memoizer representations.

As shown in the figure above, the new methods scale much more gracefully. Subfigures (a) and (b) demonstrate the memory scaling (number of tables vs. context/symbol pairs) for the Calgary and Brown corpora, respectively. Subfigure (c) highlights the dramatic reduction in computational time per iteration achieved by the re-instantiating sampler compared to the original approach.

Limitations and Future Work

While these improvements mark a significant step forward, challenges remain. Even with the re-instantiating sampler, the model relies on generalized Stirling numbers, which are computationally difficult and have a very high dynamic range.

The authors note that the posterior distribution is essentially a Markov network with sum constraints. Because of this, future work could explore alternative inference methods like loopy belief propagation or variational inference, though the large domains of the variables remain a hurdle. Additionally, while the paper demonstrates that a non-zero $\alpha$ improves performance, developing an automated way to learn the optimal $\alpha$ during the inference process is an open area for future research.

Summary updated

Abstract

The sequence memoizer is a model for sequence data with state-of-the-art performance on language modeling and compression. We propose a number of improvements to the model and inference algorithm, including an enlarged range of hyperparameters, a memory-efficient representation, and inference algorithms operating on the new representation. Our derivations are based on precise definitions of the various processes that will also allow us to provide an elementary proof of the mysterious" coagulation and fragmentation properties used in the original paper on the sequence memoizer by Wood et al. (2009). We present some experimental results supporting our improvements."
BibTeX
@inproceedings{gasthaus2010improvements,
  author = {Jan Gasthaus and Yee Whye Teh},
  title = {{Improvements to the Sequence Memoizer}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2010},
  url = {https://openreview.net/forum?id=B1EbbDWdbr},
}

Loading related content...

Figure