On Prediction Using Variable Order Markov Models

Abstract

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 in corpus (14)

• Representing higher-order dependencies in networks
• Bayesian analysis of variable-order, reversible Markov chains
• Identifying Cover Songs Using Information-Theoretic Measures of Similarity
• Fault Injection Analytics: A Novel Approach to Discover Failure Modes in Cloud-Computing Systems
• Enhancing Failure Propagation Analysis in Cloud Computing Systems
• Neuronal functional connectivity among multiple areas of the rat somatosensory system during spontaneous and evoked activities
• Context Tree based Image Contour Coding using A Geometric Prior
• Trajectory Modeling via Random Utility Inverse Reinforcement Learning
• Sequential Complexity as a Descriptor for Musical Similarity
• Run-time Failure Detection via Non-intrusive Event Analysis in a Large-Scale Cloud Computing Platform
• Joint Denoising / Compression of Image Contours via Shape Prior and Context Tree
• Context-Tree-Based Lossy Compression and Its Application to CSI Representation
• Markov Chain Monte Carlo for generating ranked textual data
• Approximate learning of parsimonious Bayesian context trees