On Prediction Using Variable Order Markov Models

Details On Prediction Using Variable Order Markov Models On Prediction Using Variable Order Markov Models

2011-06-30

arxiv.org/abs/1107.0051v1

Journal Of Artificial Intelligence Research, Volume 22, pages 385-421, 2004

Computer Science

Artificial Intelligence

Scientific paper

10.1613/jair.1491

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.

Affiliated with

Also associated with

No associations

Rating

On Prediction Using Variable Order Markov Models does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Prediction Using Variable Order Markov Models, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Prediction Using Variable Order Markov Models will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-480033