title: Context-tree modeling of observed symbolic dynamics.
abstract: 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.
authors.affiliation: Institute for Nonlinear Science, University of California, San Diego, La Jolla, California 92093-0402, USA. mkennel@ucsd.edu
authors.forename: Matthew B
authors.initials: MB
authors.lastname: Kennel
authors.forename: Alistair I
authors.initials: AI
authors.lastname: Mees