M.Sc Thesis

M.Sc StudentBegleiter Ron
SubjectCan Theory Meet Practice in Sequence Prediction?
DepartmentDepartment of Computer Science
Supervisor PROF. Ran El-Yaniv


This work is concerned with sequential prediction of discrete sequences under log-loss. One question that motivated our research was whether practical evidence of a sequential prediction algorithm can be established via theoretical performance guarantees. For this purpose we conducted an extensive empirical experiment, searching for the best prediction algorithm. The experiment compared a set of prominent well-known prediction algorithms using real life sequences from three different domains: proteins, text and music. In this experiment, two candidate prediction methods stood out with state-of-the-art results. However, neither one of these methods had a compelling theoretical explanation for its success. We focused on one of these practical methods that is based on hierarchical applications of binary Context Tree Weighting (CTW) predictors. We present worst case bounds for the learning rate of this hierarchical method. A heuristic application of this approach that relies on Huffman's alphabet decomposition performed well in our experiments and is also 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.