Nonparametric Discovery of Latent States in Sequential Data

45 concepts36 papers3 proposals

When modeling sequential data—whether tracking the market regimes of financial assets, parsing the phonetic building blocks of speech, or decoding the behavioral states of an animal—we often turn to Hidden Markov Models (HMMs) or Partially Observable Markov Decision Processes (POMDPs). These models assume that the observed data is generated by an underlying system transitioning through a set of discrete, hidden states.

However, classical state-space models harbor a fundamental bottleneck: you must pre-specify the exact number of hidden states ($K$) before training begins. If $K$ is too small, the model underfits, merging distinct behaviors into confusing amalgams. If $K$ is too large, the model overfits, fragmenting meaningful states into redundant sub-states. Traditional workarounds like cross-validation or grid searching over $K$ are computationally grueling and brittle.

Nonparametric state discovery resolves this dilemma by treating the state space as countably infinite. Instead of forcing a practitioner to guess the model's capacity upfront, the data itself dictates the size of the state space, allowing new states to be instantiated or pruned dynamically as the complexity of the data shifts.


The Core Intuition: Infinite State Spaces with a Simplicity Bias

To understand why this works, imagine a sequence of observations. We want to assign each observation to a latent state, but we do not want to cap the total number of possible states.

A natural way to model an unbounded number of categories is the Chinese Restaurant Process (CRP). In a CRP, imagine customers (observations) entering a restaurant one by one and choosing a table (a latent state). A customer chooses an already occupied table with a probability proportional to the number of people currently sitting there, or they choose a brand-new table with a probability governed by a scaling parameter $\alpha$.

This setup provides two crucial properties:

  1. Unbounded Capacity: There is always a non-zero probability of opening a new table.
  2. Rich-Get-Richer Clustering: Popular tables attract more customers, creating a natural power-law distribution that acts as a simplicity bias.

As demonstrated by Sanders et al., this simplicity bias is highly effective for modeling hidden states because it forces the system to exhaustively reuse existing states before incurring the penalty of spawning a new one. Similarly, Stimberg et al. leveraged this mechanism to automatically infer both the timing of abrupt change points and the total number of unique underlying states in dynamical systems.


The Sequential Challenge: Sharing an Infinite Vocabulary

While a standard CRP works beautifully for clustering independent data points, it fails when applied directly to sequential models like HMMs.

In an HMM, every hidden state must possess its own row in a transition matrix. Each row is a probability distribution dictating where the system is likely to go next. If we have an infinite state space, every single state needs an infinite-dimensional distribution over all possible next states.

If we use an independent Dirichlet Process or CRP for each row, a catastrophic problem emerges: the rows will not share the same states. State 1 might transition to a set of newly discovered states $\{A, B, C\}$, while State 2 transitions to a completely different set of newly discovered states $\{D, E, F\}$. The model loses the ability to reuse states across different time steps, destroying the cohesive network structure of the HMM.

To solve this, Jordan et al. introduced the Hierarchical Dirichlet Process (HDP). The HDP solves the sharing problem by establishing a two-level hierarchy:

Global Base Measure (Infinite pool of shared states: {State 1, State 2, State 3, ...})
       ▲
       │ (Each row draws its specific state preferences from the global pool)
       ├───────────────────────────────┐
       │                               │
State 1 Transition Row          State 2 Transition Row
(Infinite distribution over     (Infinite distribution over
 global states)                  global states)

By tying the base distributions of every row to a shared global pool, the HDP ensures that every state draws from the exact same "infinite vocabulary" of latent states.

Applying this to time-series modeling, Beal et al. developed the Infinite Hidden Markov Model (iHMM). In an iHMM, when the system is in a given state, it looks at that state's transition row. It will strongly prefer to transition to globally popular states, but it always retains a small, mathematically bounded probability of transitioning to a brand-new state drawn from the global pool. This allows the state space to expand organically as the sequence grows more complex.


Making Infinite Inference Tractable

Operating over an infinitely large transition matrix sounds computationally impossible. In practice, researchers bypass this infinity using three distinct algorithmic paradigms:

1. Beam Sampling

Traditional Markov Chain Monte Carlo (MCMC) sampling struggles with infinite models because updating a single state at a time is incredibly slow and prone to getting stuck in local modes. To overcome this, Van Gael et al. introduced beam sampling.

Beam sampling combines slice sampling with dynamic programming. At each iteration, the algorithm introduces an auxiliary "slice" variable that filters out states with negligible transition probabilities. This adaptively truncates the infinite state space into a finite, highly relevant subset of active states for that specific time step. This allows the model to use efficient forward-filtering backward-sampling algorithms to update entire state trajectories at once, a strategy also adapted by Zhang et al. to optimize max-margin discriminative variants.

2. Stochastic Variational Inference

While sampling is exact, it does not scale well to massive datasets. To bring nonparametric state discovery to big data, Zhang et al. developed a scalable variational inference framework for the HDP-HMM. By utilizing a two-level stick-breaking construction and deriving a novel local lower bound, the authors enabled closed-form parameter updates that can be computed stochastically over mini-batches, allowing infinite sequence models to scale to massive datasets.

3. Small-Variance Asymptotics

A third paradigm completely bypasses probabilistic formulations in favor of fast, deterministic optimization. By analyzing what happens to nonparametric models as the variance of the emissions approaches zero, Roychowdhury et al. demonstrated that infinite-state models can be optimized using approximate dynamic programming.

This approach instantiates new states on the fly during optimization whenever an observation falls too far from any existing state's centroid—effectively acting as a sequential, self-scaling version of $k$-means clustering. In the context of continuous-time systems, Huggins developed JUMP-Means for Markov jump processes, applying a mathematical penalty to prevent an excessive explosion of categories while maintaining high computational speeds.


Versatility Across Domains

Because nonparametric state discovery removes the guesswork of manual model selection, it has become a foundational framework across a wide variety of domains:

  • Reinforcement Learning: In environments where an agent does not know the underlying map or rules, Doshi-Velez introduced the Infinite Partially Observable Markov Decision Process (iPOMDP). The agent starts with a minimal state representation and dynamically instantiates new states only when its environmental observations cannot be explained by its current world model.
  • Natural Language Processing: For tasks like unsupervised part-of-speech tagging, Van Gael et al. proved that an iHMM can automatically discover the optimal number of syntactic tags directly from raw text corpora, outperforming fixed-capacity models.
  • Neuroscience and Behavior: To capture how brain states evolve and drift over long-term experiments without a predefined category count, Geadah developed the infinite recurrent switching linear dynamical system (irSLDS), allowing discrete behavioral and neural signatures to emerge directly from continuous time-series data.

Key Foundational Work

The Infinite Hidden Markov Model (2001) — contributed 2 concept elements to this direction.
Segmenting Time Series with a Hybrid Neural Networks – Hidden Markov Model (2002) — contributed 2 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_nonparametric_state_discovery_601a2d5d,
  title = {nonparametric state discovery},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/nonparametric-state-discovery/rdr_601a2d5d0d58481e8743bc1ef3248e67},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_nonparametric_state_discovery_601a2d5d_v1,
  title = {nonparametric state discovery},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/nonparametric-state-discovery/rdr_601a2d5d0d58481e8743bc1ef3248e67/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake