Bayesian Structural Inference for Hidden Processes

Abstract

We introduce a Bayesian approach to discovering patterns in structurally complex processes. The proposed method of Bayesian Structural Inference (BSI) relies on a set of candidate unifilar HMM (uHMM) topologies for inference of process structure from a data series. We employ a recently developed exact enumeration of topological epsilon-machines. (A sequel then removes the topological restriction.) This subset of the uHMM topologies has the added benefit that inferred models are guaranteed to be epsilon-machines, irrespective of estimated transition probabilities. Properties of epsilon-machines and uHMMs allow for the derivation of analytic expressions for estimating transition probabilities, inferring start states, and comparing the posterior probability of candidate model topologies, despite process internal structure being only indirectly present in data. We demonstrate BSI's effectiveness in estimating a process's randomness, as reflected by the Shannon entropy rate, and its structure, as quantified by the statistical complexity. We also compare using the posterior distribution over candidate models and the single, maximum a posteriori model for point estimation and show that the former more accurately reflects uncertainty in estimated values. We apply BSI to in-class examples of finite- and infinite-order Markov processes, as well to an out-of-class, infinite-state hidden process.

20 pages, 11 figures, 1 table; supplementary materials, 15 pages, 11 figures, 6 tables; http://csc.ucdavis.edu/~cmg/compmech/pubs/bsihp.htm

References in corpus (1)

• Inferring Markov Chains: Bayesian Estimation, Model Comparison, Entropy Rate, and Out-of-class Modeling

Cited by in corpus (23)

• A practical, unitary simulator for non-Markovian complex processes
• Computational Mechanics of Input-Output Processes: Structured transformations and the $\epsilon$-transducer
• What did Erwin Mean? The Physics of Information from the Materials Genomics of Aperiodic Crystals and Water to Molecular Information Catalysts and Life
• A new method for choosing parameters in delay reconstruction-based forecast strategies
• Informational and Causal Architecture of Discrete-Time Renewal Processes
• Multiplex decomposition of non-Markovian dynamics and the hidden layer reconstruction problem
• Nearly Maximally Predictive Features and Their Dimensions
• Information Anatomy of Stochastic Equilibria
• Local Causal States and Discrete Coherent Structures
• Spectral Simplicity of Apparent Complexity, Part II: Exact Complexities and Complexity Spectra
• Robust inference of memory structure for efficient quantum modelling of stochastic processes
• Discovering Causal Structure with Reproducing-Kernel Hilbert Space $\epsilon$-Machines
• Measuring the rationality in evacuation behavior with deep learning
• Circumventing the Curse of Dimensionality in Prediction: Causal Rate-Distortion for Infinite-Order Markov Processes
• The Origins of Computational Mechanics: A Brief Intellectual History and Several Clarifications
• What Is a Pattern in Statistical Mechanics? Formalizing Structure and Patterns in One-Dimensional Spin Lattice Models with Computational Mechanics
• Enhancing quantum models of stochastic processes with error mitigation
• Exploring Predictive States via Cantor Embeddings and Wasserstein Distance
• Inference, Prediction, and Entropy-Rate Estimation of Continuous-time, Discrete-event Processes
• The Ambiguity of Simplicity
• Minimum Probabilistic Finite State Learning Problem on Finite Data Sets: Complexity, Solution and Approximations
• Finitary Process Evolution I: Information Geometry of Configuration Space and the Process-Replicator Dynamics
• Understanding and Designing Complex Systems: Response to "A framework for optimal high-level descriptions in science and engineering---preliminary report"