Counting Regimes, Not Phases: Nonparametric State Discovery Without the Geometric Dwell-Time Tax

Hidden Markov models assume that the chance of leaving a state is the same at every step, no matter how long the system has already been there. As a result, the time spent in any state follows a geometric distribution, and the most likely stay is always a single step. Nonparametric versions of these models let the data decide how many states exist. Our central claim is that they pay for that memoryless assumption with extra states. When a real behavior has a typical length, such as a honeybee waggle that lasts a characteristic number of frames, the cheapest way for the model to fit it is to chain several near-identical states in sequence. A chain of geometric stays sums to a peaked duration distribution. The inferred number of states therefore grows with how regular the durations are, not with how many distinct behaviors exist. A fixed-cardinality model hides this problem by never letting the count float. A nonparametric model exposes it, and then reports the wrong number of regimes.

We propose to make this failure explicit and to fix it in a way that keeps the computational advantages of Markov models. The model separates two kinds of discrete latent units. Regimes are distinct dynamical behaviors, and their number is discovered by a hierarchical Dirichlet process. Phases are ordered sub-steps inside a regime that share its emission or dynamics parameters and exist only to shape how long the regime lasts. Both counts are inferred. Because the phase structure is still a Markov chain, the model gets peaked, minimum-length durations with no maximum-duration cutoff. It can also reuse the scalable variational inference that adds, merges and deletes states, which so far exists only for geometric-duration models.

Core Claim

The claim has two parts. The scientific part is that under geometric dwell times, nonparametric state counts are inflated in a predictable way, by roughly the number of phases needed to approximate each regime's duration shape. This inflation is invisible on benchmarks that report only segmentation accuracy. The method part is that a model with regimes drawn from a hierarchical Dirichlet process, plus a nonparametric number of tied, left-to-right phases per regime, recovers the true regime count. It matches explicit-duration segmentation quality and avoids the cost of explicit-duration message passing over a truncated duration range.

Concretely, regime $k$ has $M_k$ phases. Each phase persists with probability $p_k$ and otherwise advances; leaving the last phase exits the regime. The dwell time $d$ in regime $k$ is then a shifted negative binomial:

$$P(d \mid M_k, p_k) = \binom{d-1}{M_k-1}(1-p_k)^{M_k}\, p_k^{\,d-M_k}, \qquad d \ge M_k.$$

With $M_k=1$ this reduces to the geometric case of the sticky model. With $M_k>1$ it has an interior mode, a hard minimum stay of $M_k$ steps (a refractory period), and unbounded support. Learning $M_k$ per regime is what makes the duration shape adaptive.

Relation to Prior Work

Three nonparametric models attack over-segmentation by adjusting self-transitions, and they motivate the inflation claim. The Sticky HDP-HMM adds a self-transition bonus $\kappa$. Disentangled sticky HDP-HMM gives each state its own stickiness. The Recurrent Sticky HDP-HMM makes stickiness depend on the previous observation. All three keep the dwell time geometric, with its mode at one step. We predict that each of them will spend extra states to fake peaked durations, and we will measure this rather than assume it.

Two models remove the geometric constraint with explicit duration draws, and they are our strongest competitors. The HDP-HSMM draws a stationary Poisson or negative-binomial duration on entering each state. RED-HDP-HMM makes that duration depend on observations and shows that forbidding self-loops removes the "aliasing" between one long stay and repeated re-entries. Both use Gibbs samplers whose message passing scales with a maximum duration $D_{max}$. RED-HDP-HMM's authors name variational inference as the missing piece for scale. Our phase construction differs in two ways: duration support is not truncated, and the transition structure stays Markov.

That second property is what lets us borrow the method of Scalable Adaptation of State Complexity for Nonparametric Hidden Markov Models. That paper uses memoized variational inference with birth, merge and delete moves, grew from 1 to 70 states on 15.4 million chromatin observations, and was derived only for sticky, geometric models. We extend those moves to two levels, regimes and phases. We also borrow from Stochastic Variational Inference for the HDP-HMM for the two-level stick-breaking variational form.

Fixed-cardinality explicit-duration switching models constrain the design rather than compete with it on count recovery. REDSLDS and RED-SDS model durations with continuous latent states but hard-code $K$. RED-SDS also reports a warning we take seriously: on its bouncing-ball task the duration variable went unused because the continuous dynamics explained the bounce. Phases can likewise collapse to $M_k=1$, and we treat that as a legitimate outcome, not a bug. irSLDS discovers states nonparametrically in a switching linear dynamical system (a model where a discrete regime selects which linear dynamics drive a hidden continuous trajectory), but its durations stay geometric. It is the natural target for our second stage.

Research Program

The first stage is the model and inference for autoregressive observations, the same setting as RED-HDP-HMM. The phase transition matrix is block-banded: within a regime it is left-to-right, and only the last phase connects to other regimes. Forward-backward therefore costs about $O(T(\sum_k M_k + K^2))$ instead of scaling with $D_{max}$.

Emission and dynamics parameters are tied across a regime's phases. This tying is the identifiability device. A new regime must earn its place through different dynamics, while a new phase must earn its place through duration shape. It answers directly the ambiguity RED-HDP-HMM leaves open, namely whether persistence is explained by dynamics or by duration.

The variational inference includes four moves. Regime birth and regime merge follow Hughes et al. Phase birth splits the last phase and is accepted if the bound improves. Phase merge is the reverse. Observation-dependent exit from the last phase uses a logistic link with Pólya-Gamma augmentation, as in RS-HDP-HMM, so that durations can depend on context.

The second stage replaces direct observations with a continuous latent trajectory, giving a switching linear dynamical system. This is the extension RED-HDP-HMM lists as future work. Because the discrete chain is still Markov, standard Kalman-plus-discrete alternating updates apply without semi-Markov bookkeeping.

Baselines

The naive reference is the plain HDP-HMM with no stickiness. It shows how badly unconstrained discovery over-counts. On NIST meetings, the non-sticky model's diarization error rate is 23.91%, against 17.84% for the sticky model (A sticky HDP-HMM with application to speaker diarization).

The persistence baselines are the sticky, disentangled sticky and recurrent sticky HDP-HMMs. They are the strongest competitors on cost because they keep Markov message passing. All three will be run with weak-limit Gibbs sampling at the same truncation level, on the same features and with the same number of hyperparameter configurations as our model.

The strongest existing method is RED-HDP-HMM. It reports 0.899 accuracy on the honeybee dance, against 0.873 for the sticky HDP-HMM and 0.853 for RS-HDP-HMM. It also reports gains of 4.5 to 10.4 percentage points over sticky models on C. elegans calcium imaging. We will run it with its own sampler and the $D_{max}$ its paper uses, and we will match wall-clock budget. Beating it on accuracy is not required. Our success criterion is accuracy within noise of 0.899 on bees, regime count closer to the true three, and lower time per effective sample as $D_{max}$ would need to grow. For the HDP-HSMM the reference figure is roughly 0.4 normalized Hamming error in under 200 iterations on NIST.

In the latent-state setting, the strongest fixed-count competitor is REDSLDS, at about 0.85 bee accuracy versus about 0.37 for the recurrent switching linear dynamical system. It will be run at its reported $K$ and also across a sweep of $K$ selected by the Bayesian information criterion (BIC). The sweep counts toward total compute.

Two ablations isolate our key ingredient. The first fixes $M_k=1$, which reduces the model to a disentangled-sticky model with our variational inference. The second fixes $M_k$ to a single shared constant, which amounts to a parametric negative-binomial embedding with no phase discovery.

Why not just…?

Why not just use the sticky or disentangled sticky HDP-HMM, which is cheaper? Its dwell time is geometric whatever $\kappa$ is, so it cannot impose a minimum stay. The evidence in the file is accuracy gaps: 0.873 versus 0.899 on bees, and 4.5 to 10.4 points on C. elegans. Our synthetic experiment will test a sharper prediction. Its inferred state count should rise as the true durations become more regular, while ours should stay flat. If it does not rise, our inflation claim is wrong, and we would report that.

Why not just use HDP-HSMM or RED-HDP-HMM with negative-binomial durations? This is the real threat to the accuracy story, and we expect to tie on mid-length benchmarks. What separates the approaches is cost and scale. Their message passing grows with $D_{max}$, and they rely on Gibbs samplers, with variational inference named as open future work. Our Markov embedding lets birth and merge variational inference run on the 15.4M-point chromatin data, where their samplers have not been shown to run. If RED-HDP-HMM proves feasible there within our budget and matches our count recovery, the contribution narrows to adaptive phase counts, and we would say so.

Why not just run a sticky model and merge states with similar emissions afterward? That post-hoc merge ignores ordering. It cannot tell a true left-to-right phase chain from two regimes with similar emissions that alternate. Morse code is exactly this case: the HDP-HSMM separated dot from dash, which share a frequency, while the HDP-HMM found only two states. A post-hoc emission merge would collapse dot and dash into one regime. Our model can keep them apart as regimes with different $M_k$. We will include the post-hoc merge as an explicit baseline.

Why not just fit a fixed-K explicit-duration model and choose K by BIC? Every candidate $K$ is a separate expensive fit. Such a model also cannot add a regime when the dynamics change, as irSLDS showed on Extended NASCAR. We include the BIC sweep and charge its full compute to it.

Proposed Experiments and Decisive Checks

The decisive synthetic test generates data with three regimes whose durations are drawn from negative binomials of increasing shape, from 1 to 8. We then plot inferred regime count against shape for each model. Our prediction is that the sticky-family count rises roughly with shape while ours stays near three, with inferred $M_k$ tracking the true shape. If the sticky count stays flat, the core claim fails.

On Morse spectrograms, success means three regimes with tone-regime $M_k$ matching pulse width. On honeybee dance we measure accuracy and adjusted Rand index (agreement between inferred and true segment labels, corrected for chance), with the reference figures 0.899 for RED-HDP-HMM and 0.53 adjusted Rand index for RED-SDS versus 0.10 for SNLDS, as cited in Baselines. On NASCAR and Extended NASCAR we measure accuracy and whether a regime, rather than a phase, is added at the switch point. On NIST diarization we measure diarization error rate and inferred speaker count; RED-HDP-HMM reports no NIST result that we found on Lacuna. On C. elegans we compare segmentation accuracy against RED-HDP-HMM's reported range.

For scale, we run on CD4T chromatin and plot wall-clock time against the effective duration range, with RED-HDP-HMM at increasing $D_{max}$. The test is whether its cost curve grows while ours stays flat.

A final check addresses collapse. On RED-SDS's bouncing-ball-style data, where continuous dynamics alone explain persistence, the model should settle on $M_k=1$ rather than invent phases.