Compact Prediction Tree: A Lossless Model for Accurate Sequence Prediction

Abstract. Predicting the next item of a sequence over a finite alphabet has important applications in many domains. In this paper, we present a novel prediction model named CPT (Compact Prediction T ree) which losslessly compress the training data so that all relevant information is available for each prediction. Our approach is incremental, offers a low time complexity for its training phase and is easily adaptable for differ-ent applications and contexts. We compared the performance of CPT with state of the art techniques, namely PPM (Prediction by Partial M atching), DG (Dependency Graph) and All-K-th-Order Markov. Re-sults show that CPT yield higher accuracy on most datasets (up to 12% more than the second best approach), has better training time than DG and PPM, and is considerably smaller than All-K-th-Order Markov