Context-tree modeling of observed symbolic dynamics

作     者：Matthew B. Kennel Alistair I. Mees 

作者机构：Centre for Applied Dynamics and Optimization The University of Western Australia Nedlands Perth 6907 Western Australia 

出 版 物：《Physical Review E》 (物理学评论E辑：统计、非线性和软体物理学)

年 卷 期：2002年第66卷第5期

页      面：056209-056209页

核心收录：

学科分类：07[理学] 070203[理学-原子与分子物理] 0702[理学-物理学] 

主　　题：Computational complexity 

摘      要：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.