On Prediction Using Variable Order Markov Models

By Ron Begleiter, Ran El-Yaniv, Golan Yona. Journal of Artificial Intelligence Research, 2004

461 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Information Systems, Molecular Biology

View Paper: https://www.semanticscholar.org/paper/b31147832cf46357edb96f0276011c1ee3112e24

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Le Song
2. Hanjun Dai
3. Yun Raymond Fu
4. Kai Liu
5. Jin Zhang
6. Fei Cheng
7. Wenwen Ding
8. Rakshit S. Trivedi

In Information Systems

1. Manuel Gomez-Rodriguez
2. Le Song
3. Nan Du
4. Kai Liu
5. Hanjun Dai
6. Daniel Struck
7. Yun Raymond Fu
8. J. L. Boudec

In Molecular Biology

1. Manuel Gomez-Rodriguez
2. Le Song
3. Nan Du
4. Jie Hu
5. Kang Li
6. Hanjun Dai
7. Yun Raymond Fu
8. J. L. Boudec

Citations in the corpus

• Attentive State-Space Modeling of Disease Progression (2019, unknown): “We compare our model with 4 baselines: a vanilla RNN and an LSTM trained for sequence prediction, a state-of-the-art predictive model for healthcare data known as RETAIN [16, 14], and an HMM.”
• Modeling Complex Temporal Composition of Actionlets for Activity Prediction (2012, background): “Variable order Markov Model (VMM) [20] is a category of algorithms for prediction of discrete sequences.”
• Sequence-Aware Recommender Systems (2018, unknown): “11See [11] for a comprehensive analysis of algorithms for learning VMMs.”
• Recurrent Marked Temporal Point Processes: Embedding Event History to Vector (2016, background): “Existing studies in literature attempt to approach this problem mainly in two ways: first, classic varying-order Markov models [4] formulate the problem as a discrete-time”
• Prediction of Human Activity by Discovering Temporal Sequence Patterns (2014, background): “Markov model [5] is a category of algorithms for prediction of discrete sequences.”
• Generative Predictive Codes by Multiplexed Hippocampal Neuronal Tuplets. (2018, unknown): “, neuronal dependency on activity of 2 other neurons) or a variable-order Markov model (Begleiter et al., 2004) for the Pre-Run sleep could also reveal a generative predictive model for the future Runs.”
• COMET: adaptive context-based modeling for ultrafast HIV-1 subtype identification (2014, methodology): “The approach of COMET is inspired by the Prediction by Partial Matching compression algorithm (31), which has repeatedly and independently been shown to provide high classification accuracy for biological sequences (32,33).”
• Predicting User-Cell Association in Cellular Networks from Tracked Data (2009, methodology): “in [13] studied the performance of a number of prominent algorithms for prediction of discrete sequences over a finite alphabet, using variable order Markov models.”
• Learning hierarchical spatio-temporal pattern for human activity prediction (2016, methodology): “With the help of the context and a Variable order Markov Model (VMM) [12], the probability of the next possible actionlet or the whole action can be predicted.”