ML Anthology

Discrete Sequence Prediction and Its Applications

Philip D. Laird, Ronald Saul
MLJ 1994 pp. 43-68
doi:10.1007/BF01000408 /mlj/1994/laird1994mlj-discrete/

Abstract

Learning from experience to predict sequences of discrete symbols is a fundamental problem in machine learning with many applications. We present a simple and practical algorithm (TDAG) for discrete sequence prediction. Based on a text-compression method, the TDAG algorithm limits the growth of storage by retaining the most likely prediction contexts and discarding (forgetting) less likely ones. The storage/speed tradeoffs are parameterized so that the algorithm can be used in a variety of applications. Our experiments verify its performance on data compression tasks and show how it applies to two problems: dynamically optimizing Prolog programs for good average-case behavior and maintaining a cache for a database on mass storage.

PDF MLJ Semantic Scholar

Cite

Text

Laird and Saul. "Discrete Sequence Prediction and Its Applications." Machine Learning, 1994. doi:10.1007/BF01000408

Markdown

[Laird and Saul. "Discrete Sequence Prediction and Its Applications." Machine Learning, 1994.](https://mlanthology.org/mlj/1994/laird1994mlj-discrete/) doi:10.1007/BF01000408

BibTeX

@article{laird1994mlj-discrete,
  title     = {{Discrete Sequence Prediction and Its Applications}},
  author    = {Laird, Philip D. and Saul, Ronald},
  journal   = {Machine Learning},
  year      = {1994},
  pages     = {43-68},
  doi       = {10.1007/BF01000408},
  volume    = {15},
  url       = {https://mlanthology.org/mlj/1994/laird1994mlj-discrete/}
}