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.

本研究探究了使用变量阶马尔可夫模型进行离散序列预测的算法，并比较了六种著名的预测算法和它们在三个不同领域的表现情况。研究结果表明，在序列预测任务中，一种名为“decomposed” CTW的变种和PPM算法表现最佳，而在蛋白质分类问题中一种名为Lempel-Ziv压缩算法的修改版显著胜出。

使用可变阶数马尔可夫模型进行预测