Technical Report CS-2005-13

Title: Superior Guarantees for Sequential Prediction and Lossless Compression via Alphabet Decomposition
Authors: Ron Begleiter, Ran El-Yaniv
Abstract: We present worst case bounds for the learning rate of a known prediction method that is based on hierarchical applications of binary Context Tree Weighting (CTW) predictors. A heuristic application of this approach that relies on Huffman's alphabet decomposition is known to achieve state-of-the-art performance in prediction and lossless compression benchmarks. We show that our new bound for this heuristic is tighter than the best known performance guarantees for prediction and lossless compression algorithms in various settings. This result substantiates the efficiency of this hierarchical method and provides a compelling explanation for its practical success. In addition, we present the results of a few experiments that examine other possibilities for improving the multi-alphabet prediction performance of CTW-based algorithms.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 2005
To the main CS technical reports page

Computer science department, Technion