On Prediction Using Variable Order Markov Models
R. Begleiter, R. El-Yaniv, Golan Yona · Journal of Artificial Intelligence Research · 2004
This paper is concerned with algorithms for prediction of discrete sequences over a finite alphabet, using variable order Markov models. The class of such algorithms is large and in principle includes any lossless compression algorithm. We focus on six prominent prediction algorithms, including Context Tree Weighting (CTW), Prediction by Partial Match (PPM) and Probabilistic Suffix Trees (PSTs). We discuss the properties of these algorithms and compare their performance using real life sequences from three domains: proteins, English text and music pieces. The comparison is made with respect to prediction quality as measured by the average log-loss. We also compare classification algorithms based on these predictors with respect to a number of large protein classification tasks. Our results indicate that a ``decomposed'' CTW (a variant of the CTW algorithm) and PPM outperform all other algorithms in sequence prediction tasks. Somewhat surprisingly, a different algorithm, which is a modification of the Lempel-Ziv compression algorithm, significantly outperforms all algorithms on the protein classification problems.
Cited by 258 works. doi:10.1613/jair.1491 Open-access PDF
Authors
References
- A tutorial on hidden Markov models and selected applications in speech recognition
- SCOP: A structural classification of proteins database for the investigation of sequences and structures
- Compression of individual sequences via variable-rate coding
- A Block-sorting Lossless Data Compression Algorithm
- Maximum Entropy Markov Models for Information Extraction and Segmentation
- Pfam: A comprehensive database of protein domain families based on seed alignments
- Data Compression Using Adaptive Coding and Partial String Matching
- Universal coding, information, prediction, and estimation
- The zero-frequency problem: estimating the probabilities of novel events in adaptive text compression
- The context-tree weighting method: basic properties