Context-tree modeling of observed symbolic dynamics
Matthew B. Kennel, Alistair Mees · Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics · 2002
Modern techniques invented for data compression provide efficient automated algorithms for the modeling of the observed symbolic dynamics. We demonstrate the relationship between coding and modeling, motivating the well-known minimum description length (MDL) principle, and give concrete demonstrations of the "context-tree weighting" and "context-tree maximizing" algorithms. The predictive modeling technique obviates many of the technical difficulties traditionally associated with the correct MDL analyses. These symbolic models, representing the symbol generating process as a finite-state automaton with probabilistic emission probabilities, provide excellent and reliable entropy estimations. The resimulations of estimated tree models satisfying the MDL model-selection criterion are faithful to the original in a number of measures. The modeling suggests that the automated context-tree model construction could replace fixed-order word lengths in many traditional forms of empirical symbolic analysis of the data. We provide an explicit pseudocode for implementation of the context-tree weighting and maximizing algorithms, as well as for the conversion to an equivalent Markov chain.