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:
- Unbounded Capacity: There is always a non-zero probability of opening a new table.
- 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.