Blind Construction of Optimal Nonlinear Recursive Predictors for Discrete Sequences

We present a new method for nonlinear prediction of discrete random sequences under minimal structural assumptions. We give a mathematical construction for optimal predictors of such processes, in the form of hidden Markov models. We then describe an algorithm, CSSR (Causal-State Splitting Reconstruction), which approximates the ideal predictor from data. We discuss the reliability of CSSR, its data requirements, and its performance in simulations. Finally, we compare our approach to existing methods using variable-length Markov models and cross-validated hidden Markov models, and show theoretically and experimentally that our method delivers results superior to the former and at least comparable to the latter.

• Publication year

  2004

• Venue

  Conference on Uncertainty in Artificial Intelligence

• Publication date

  2004-06-06

• Fields of study

  Mathematics, Physics, Computer Science

• Identifiers
  arXiv cs/0406011
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Elements of Information Theory

  2005cited by this paper
• The Elements of Statistical Learning: Data Mining, Inference, and Prediction

  2004cited by this paper
• Variable Length Markov Chains: Methodology, Computing, and Software

  2004cited by this paper
• Predictive State Representations: A New Theory for Modeling Dynamical Systems

  2004cited by this paper
• Learning Predictive State Representations

  2003influential reference
• Context-tree modeling of observed symbolic dynamics.

  2002cited by this paper
• Journal of Machine Learning Research? (2003)?–? Submitted 11/02; Published?/? An Algorithm for Pattern Discovery in Time Series

  2002influential reference
• Causal architecture, complexity and self-organization in time series and cellular automata

  2001cited by this paper
• Predicting the Future of Discrete Sequences from Fractal Representations of the Past

  2001cited by this paper
• The Elements of Statistical Learning: Data Mining, Inference, and Prediction

  2001cited by this paper
• Predictive Representations of State

  2001cited by this paper
• Combinatorial methods in density estimation

  2001cited by this paper
• ! I ! i ! I ! i ! I ! i ! I ! I 138 ! !

  2000cited by this paper
• Observable Operator Models for Discrete Stochastic Time Series

  2000cited by this paper
• Building a dictionary for genomes: identification of presumptive regulatory sites by statistical analysis.

  2000cited by this paper
• Computational Mechanics: Pattern and Prediction, Structure and Simplicity

  1999influential reference
• Theory and algorithms for hidden Markov models and generalized hidden Markov models

  1998influential reference
• Complexity: Hierarchical Structures and Scaling in Physics

  1997cited by this paper
• Elements of the Theory of Computation

  1997cited by this paper
• The power of amnesia: Learning probabilistic automata with variable memory length

  1996cited by this paper
• The context-tree weighting method: basic properties

  1995cited by this paper
• Instance-Based Utile Distinctions for Reinforcement Learning with Hidden State

  1995cited by this paper
• Entropy and the Consistent Estimation of Joint Distributions

  1993cited by this paper
• Inferring statistical complexity.

  1989cited by this paper
• Scientific Explanation and the Causal Structure of the World

  1988cited by this paper
• A universal data compression system

  1983cited by this paper
• A Predictive View of Continuous Time Processes

  1975cited by this paper
• Subshifts of finite type and sofic systems

  1973cited by this paper
• The structure of responses to a sequence of binary events

  1966cited by this paper
• Information Theory and Statistics

  1960cited by this paper
• Causality : Models , Reasoning , and Inference

  year unknowncited by this paper

• Quantifying Bot Impact: An Information-Theoretic Analysis of Complexity and Uncertainty in Online Political Communication Dynamics

  2025cites this paper
• Compression, Regularity, Randomness and Emergent Structure: Rethinking Physical Complexity in the Data-Driven Era

  2025cites this paper
• Symbolic Dynamical Filtering via Variable Length Markov Model and Machine Learning

  2024cites this paper
• A Dynamical Systems Approach to Bots and Online Political Communication

  2024cites this paper
• Software in the natural world: A computational approach to hierarchical emergence

  2024cites this paper
• ProAPT: Projection of APT Threats with Deep Reinforcement Learning

  2022cites this paper
• Simulating Stochastic Processes with Variational Quantum Circuits

  2022cites this paper
• Provable superior accuracy in machine learned quantum models

  2021cites this paper
• Contextualized Behavior Recommendation from Complex Agent-Based Simulations of Disasters

  2021cites this paper
• How Complexity and Uncertainty Grew with Algorithmic Trading

  2020cites this paper
• Discrete Information Dynamics with Confidence via the Computational Mechanics Bootstrap: Confidence Sets and Significance Tests for Information-Dynamic Measures

  2020cites this paper
• Determinação de Modelo Markoviano para Canal Sem Fio Empregando Aprendizado de Máquina

  2020cites this paper
• Dynamic phenotypic heterogeneity generated by delayed genetic oscillations

  2020cites this paper
• Information Theory for Human and Social Processes

  2020cites this paper
• The high forecasting complexity of stochastically perturbed periodic orbits limits the ability to distinguish them from chaos

  2020influential citation
• Large-Scale Communication is More Complex and Unpredictable with Automated Bots

  2020cites this paper
• Discovering Causal Structure with Reproducing-Kernel Hilbert Space ε-Machines

  2020cites this paper
• Letting the Computers Take Over: Using AI to Solve Marketing Problems

  2019cites this paper
• Emergence and computability

  2019cites this paper
• Simulation Analytics for Social and Behavioral Modeling

  2019cites this paper
• Learning Causal State Representations of Partially Observable Environments

  2019cites this paper
• Influence of Inter- and Intra-Synaptic Factors on Information Processing in the Brain

  2019cites this paper
• Survey of Protocol Reverse Engineering Algorithms: Decomposition of Tools for Static Traffic Analysis

  2019influential citation
• Markov Modeling of Time Series via Spectral Analysis for Detection of Combustion Instabilities

  2018cites this paper
• Data Driven Models of Short-Term Synaptic Plasticity

  2018influential citation
• Handbook of Dynamic Data Driven Applications Systems

  2018cites this paper
• Computational landscape of user behavior on social media

  2018influential citation
• Equations of mind: Data science for inferring nonlinear dynamics of socio-cognitive systems

  2018cites this paper
• Understanding real-world phenomena from human-generated sensor data

  2018cites this paper
• Effect of Neuromodulation of Short-term Plasticity on Information Processing in Hippocampal Interneuron Synapses

  2018cites this paper
• Finitary Process Evolution I: Information Geometry of Configuration Space and the Process-Replicator Dynamics

  2018cites this paper
• Prediction of Elevated Activity in Online Social Media Using Aggregated and Individualized Models

  2017cites this paper
• Some comments on computational mechanics, complexity measures, and all that

  2017cites this paper
• Behavior Modeling and Analytics for Urban Computing: A Synthetic Information-based Approach

  2017influential citation
• Making and Improving Predictions of Interest Using an MDP Model

  2017cites this paper
• Enhanced Prediction of Network Attacks Using Incomplete Data

  2017cites this paper
• Simulating and reconstructing neurodynamics with Epsilon-automata applied to electroencephalography (EEG) Microstate Sequences

  2017influential citation
• Information Fusion of Passive Sensors for Detection of Moving Targets in Dynamic Environments

  2017cites this paper
• Version Other version Link to publication record in King ' s Research Portal

  2017influential citation
• Linking Twitter Events With Stock Market Jitters

  2017cites this paper
• Symbolic analysis-based reduced order Markov modeling of time series data

  2017cites this paper
• Predictive State Smoothing (PRESS): Scalable non-parametric regression for high-dimensional data with variable selection

  2017cites this paper
• Optimal Prediction

  2017cites this paper
• On Quitting: Performance and Practice in Online Game Play

  2017cites this paper
• Estudio de técnicas de análisis y tratamiento de información en P300: Aproximaciones hacia la clasificación adaptativa

  2016cites this paper
• Models and people: An alternative view of the emergent properties of computational models

  2016cites this paper
• Culturomics as a data playground for tests of selection: Mathematical approaches to detecting selection in word use.

  2016cites this paper
• Deriving an optimally deceptive policy in two-player iterated games

  2016cites this paper
• Summarizing Simulation Results Using Causally-Relevant States

  2016influential citation
• Sequential Learning and Variable Length Markov Chains

  2016cites this paper
• Simulation Summarization: (Extended Abstract)

  2016cites this paper
• Efficient inference of hidden Markov models from large observation sequences

  2016cites this paper
• Evaluation of Complexity in Product Development

  2016cites this paper
• Learning Probability Distributions Generated by Finite-State Machines

  2016cites this paper
• Identification of the battery state-of-health parameter from input–output pairs of time series data

  2015cites this paper
• Forecasting high tide: Predicting times of elevated activity in online social media

  2015cites this paper
• Multi-Level Cause-Effect Systems

  2015cites this paper
• Statistical Methods for Analyzing Time Series Data Drawn from Complex Social Systems

  2015influential citation
• Identi fi cation of the battery state-of-health parameter from input e output pairs of time series data

  2015cites this paper
• The LICORS cabinet: Nonparametric light cone methods for spatio-temporal modeling

  2015cites this paper
• Dynamic data-driven identification of battery state-of-charge via symbolic analysis of input–output pairs

  2015cites this paper
• The LICORS Cabinet: Nonparametric Algorithms for Spatio-temporal Prediction

  2015cites this paper
• Predictability Bounds of Electronic Health Records

  2015cites this paper
• Bayesian Nonparametric Methods for Partially-Observable Reinforcement Learning

  2015cites this paper
• The Impact Analysis of Modeling Errors for projecting cyber attacks

  2015influential citation
• Dynamic Data-Driven Prediction of Lean Blowout in a Swirl-Stabilized Combustor

  2015cites this paper
• Dynamic data-driven identification of battery state-of-charge via symbolic analysis of input – output pairs q

  2015cites this paper
• Complexity-Regularized Regression for Serially-Correlated Residuals with Applications to Stock Market Data

  2014cites this paper
• Pattern discovery in continuous speech using Block Diagonal Infinite HMM

  2014cites this paper
• Information driven self-organization of agents and agent collectives

  2014influential citation
• State splitting and merging in probabilistic finite state automata for signal representation and analysis

  2014cites this paper
• A reference based analysis framework for understanding anomaly detection techniques for symbolic sequences

  2014cites this paper
• Identifying Cover Songs Using Information-Theoretic Measures of Similarity

  2014cites this paper
• Information-theoretic measures of predictability for music content analysis

  2014cites this paper
• Attack Projection

  2014cites this paper
• Minimum Probabilistic Finite State Learning Problem on Finite Data Sets: Complexity, Solution and Approximations

  2014influential citation
• STUDY ON INFORMATION THEORY: CONNECTION TO CONTROL THEORY, APPROACH AND ANALYSIS FOR COMPUTATION by WANCHAT THEERANAEW

  2014cites this paper
• Computational Complexity of the Minimum State Probabilistic Finite State Learning Problem on Finite Data Sets

  2014influential citation
• Picking up the pieces: Causal states in noisy data, and how to recover them

  2013influential citation
• The observer's observer's paradox

  2013cites this paper
• In : Fault Detection : Classification , Techniques and Role inIndustrial Systems

  2013cites this paper
• Bayesian Nonparametric Methods for Partially-Observable Reinforcement Learning.

  2013influential citation
• Probabilistic Sequence Models with Speech and Language Applications

  2013cites this paper
• Predictability of User Behavior in Social Media: Bottom-Up v. Top-Down Modeling

  2013cites this paper
• Adaptive pattern classification for symbolic dynamic systems

  2013cites this paper
• Access network traffic models for energy efficient architectures

  2013influential citation
• Encoding Through Patterns: Regression Tree–Based Neuronal Population Models

  2013cites this paper
• ON THE ASSESSMENT OF MANUFACTURING SYSTEMS COMPLEXITY

  2013cites this paper
• Efficient Methods to Compute Optimal Tree Approximations of Directed Information Graphs

  2013cites this paper
• Understanding the Predictive Power of Computational Mechanics and Echo State Networks in Social Media

  2013cites this paper
• Hilbert space formulation of symbolic systems for signal representation and analysis

  2013cites this paper
• Abductive learning of quantized stochastic processes with probabilistic finite automata

  2013influential citation
• a linear integer program for the causal state splitting and reconstruction algorithm

  2013cites this paper
• Network Traffic Analysis Using Stochastic Grammars

  2012cites this paper
• Transistor scaled HPC application performance

  2012cites this paper
• Symbolic transient time-series analysis for fault detection in aircraft gas turbine engines

  2012cites this paper
• Maritime Domain Awareness

  2012cites this paper
• Adaptation in symbolic dynamic systems for pattern classification

  2012cites this paper
• Statistical Complexity of Low- and High-Dimensional Systems

  2012influential citation
• A unified framework for supervised learning of semantic models

  2012cites this paper