Related Experiment Videos
Context-tree modeling of observed symbolic dynamics.
Matthew B Kennel1, Alistair I Mees
1Institute for Nonlinear Science, University of California, San Diego, La Jolla, California 92093-0402, USA. mkennel@ucsd.edu
Summary
Automated algorithms for data compression and symbolic dynamics modeling offer efficient methods. Context-tree weighting and maximizing techniques provide reliable entropy estimations and can replace traditional analysis in data science.
Area of Science:
- Information Theory
- Computational Linguistics
- Data Compression
Background:
- Symbolic dynamics modeling traditionally faces technical challenges in analysis.
- Existing methods for empirical symbolic analysis often rely on fixed-order word lengths.
Purpose of the Study:
- To demonstrate the link between coding and modeling, supporting the minimum description length (MDL) principle.
- To introduce and demonstrate context-tree weighting and context-tree maximizing algorithms for symbolic dynamics.
- To offer reliable entropy estimations and improved data analysis techniques.
Main Methods:
- Utilizing modern data compression techniques for automated modeling of symbolic dynamics.
- Applying context-tree weighting and context-tree maximizing algorithms.
- Representing the symbol generating process as a finite-state automaton with probabilistic emission probabilities.
Main Results:
- Context-tree weighting and maximizing algorithms provide efficient and automated modeling.
- Symbolic models yield reliable entropy estimations, overcoming traditional MDL analysis difficulties.
- Resimulations of MDL-selected tree models demonstrate faithfulness to original data.
Conclusions:
- Automated context-tree model construction can replace fixed-order word lengths in empirical symbolic analysis.
- The presented algorithms offer a robust framework for symbolic dynamics modeling and entropy estimation.
- Pseudocode for implementation and conversion to Markov chains is provided.