Infinite State Space Models for Structured Sequences

This direction is merged into another direction: fixed state cardinality. Its last version stays readable and citable here.

Version 1 of 126 papers27 conceptsfrozen 2026-10-04

In traditional probabilistic modeling, we often start by making a rigid assumption: we decide, upfront, how many "types" of things exist in our data. If we are modeling a market, we might assume there are two states: bull and bear. If we are segmenting animal behavior, we might pre-define five specific poses.

However, real-world complexity rarely fits into these fixed boxes. As Max Welling and colleagues argue in Infinite State Bayesian Networks, forcing a model to use a predefined number of latent states limits its ability to adapt as data grows or as new, unforeseen behaviors emerge. The research direction of Infinite State Space Models—often built using Bayesian nonparametric priors—seeks to let the data itself dictate the complexity of the model.

The Problem with Fixed States

Whether using a Hidden Markov Model (HMM) for finance or a Switching Linear Dynamical System (SLDS) for motion tracking, the "state space" is typically a hyperparameter. This creates a fundamental tension:

  1. Underfitting: If you choose too few states, the model merges distinct behaviors (e.g., treating "high volatility" and "market crash" as the same state).
  2. Overfitting: If you choose too many, the model fails to generalize, creating redundant states for noise.
  3. Novelty Blindness: In dynamic systems like crypto markets Koki or neural activity Bian et al., new regimes can appear that were never present in the training set.

The Nonparametric Intuition: The "Infinite" Library

The core idea behind this research is to replace fixed state counts with a "stochastic process" that allows for an unbounded number of states. The most common tool for this is the Dirichlet Process (DP) or its sequential cousin, the Hierarchical Dirichlet Process (HDP).

Think of the model not as a fixed set of bins, but as a library that can grow. When the model encounters a new data point, it faces a choice:

  • Reinforcement: Assign the data to an existing state that explains it well.
  • Innovation: Create a brand-new state because the existing ones are a poor fit.

This mechanism is often visualized through the Chinese Restaurant Process (CRP). Imagine a restaurant with infinite tables. Each new customer (data point) sits at an occupied table with probability proportional to how many people are already there (reinforcement), or starts a new table with a probability controlled by a "concentration" parameter (innovation). Florian Stimberg and colleagues applied this to dynamical systems, allowing the model to automatically infer both the timing of "change points" and the total number of unique regimes the system visits Bayesian Inference for Change Points in Dynamical Systems with Reusable States.

Scaling to Complex Structures

While a simple infinite state model can cluster data, structured sequences require more nuance. Researchers have extended these priors to handle specific temporal and structural challenges:

1. Hierarchical Dynamics

In Nonparametric Bayesian Learning of Switching Linear Dynamical Systems, Emily Fox and Michael Jordan demonstrated how to model systems that switch between different linear behaviors. By using an HDP, the model can discover an arbitrary number of dynamical modes (like "walking," "running," or "turning") without the user specifying them.

2. Feature Sharing

Sometimes, we have multiple related sequences (e.g., different people performing the same set of exercises). We want them to share a common "vocabulary" of behaviors, but each person might only use a subset of them. The BP-AR-HMM Fox et al. uses a Beta Process to act as a global menu of behaviors, where each individual sequence "picks" which behaviors to exhibit Sharing Features among Dynamical Systems with Beta Processes.

3. Observation-Dependent Durations

Standard HMMs assume the time spent in a state follows a geometric distribution, which is often unrealistic. Mikołaj Słupiński and Piotr Lipinski introduced RED-HDP-HMM, which allows the duration of a state to depend on the observations themselves while maintaining an infinite state space RED-HDP-HMM: Observation-Dependent Durations for Bayesian Nonparametric Sequential Models.

Why It Works: The Complexity-Data Balance

The elegance of these models lies in their "Occam’s Razor" property. Because starting a new state is "probabilistically expensive" (controlled by hyperparameters like alpha), the model only adds a new state if the improvement in data fit outweighs the cost of increased complexity.

As shown in work on market volatility Francis et al. and animal behavior Shi et al., this allows for the discovery of "fine-grained motifs"—subtle patterns that a human expert might not have thought to label, but which are statistically significant enough for the model to justify a new state. By removing the ceiling on state counts, these models transition from being mere classifiers to being tools for scientific discovery.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_infinite_state_space_models_for_structur_cf62f2eb,
  title = {Infinite State Space Models for Structured Sequences},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/infinite-state-space-models-for-structured-sequences/rdr_cf62f2eb2b5941598654149b2b478256},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_infinite_state_space_models_for_structur_cf62f2eb_v1,
  title = {Infinite State Space Models for Structured Sequences},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/infinite-state-space-models-for-structured-sequences/rdr_cf62f2eb2b5941598654149b2b478256/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}