A hidden Markov model (HMM) describes a time series as one hidden "regime" variable that jumps between a fixed number of values. That breaks down when the data are produced by several partly independent processes running at once, such as two dancers, several weather systems, or several overlapping voices. A product of HMMs fixes this. Several small HMMs, called experts, each score the whole sequence, and their scores are multiplied together. Because the combination is undirected, each expert's hidden path can be inferred exactly and independently once the data are observed. Trained with contrastive divergence (a cheap learning rule that compares data with samples from a few steps of Markov chain sampling started at the data), these experts were found to split the work among themselves without supervision: on Brazilian rainfall data, one expert captured north/south effects and another captured coastal effects (Products of Hidden Markov Models: It Takes N>1 to Tango). The number of experts, however, is chosen by hand.
We propose to make the number of experts a latent variable that is sampled during training. The experts are placed in an order, and switching on expert $m$ costs a growing energy penalty. Whenever the sampler asks for one more expert than currently exists, a blank expert is created. This is the ordered-penalty device of the Infinite RBM, moved from single hidden units on static images to whole temporal experts on sequences. The scientific question is sharper than "can we grow it." Short-run contrastive divergence is known to be biased, because its chains do not explore far from the data. We want to know whether that bias produces spurious expert births, or whether the local mismatch it measures is exactly the signal that says a new expert is needed. Separately, we want to know whether growth beats the obvious alternative of starting large and pruning.
Core Claim
An ordered product of HMMs trained with a growth-aware form of contrastive divergence will do three things. It will recover the number of independent processes in factorial sequence data. It will add experts when a new regime appears in a data stream. It will keep the unsupervised specialization reported for fixed products, without the load-balancing losses or annealing schedules that mixture-of-experts and winner-takes-all methods need to avoid collapse. The claim is falsifiable on three fronts. Births may track the number of sampling steps $k$ rather than the data. An oversized product with a group-sparsity penalty may match growth even in the streaming setting. Specialization may degrade once experts are ordered.
Model and Learning Rule
Let $x_{1:T}$ be an observed sequence and $s^{(m)}_{1:T}$ the hidden path of expert $m$. Let $\phi_m(x, s^{(m)})$ be expert $m$'s unnormalized HMM score: the product of its nonnegative transition and emission potentials. A freshly created expert has all potentials equal to one. Let $z$ be the number of active experts. The joint energy is
$$E(x, s, z) = \sum_{m=1}^{z} \left[ -\log \phi_m(x, s^{(m)}) + \beta_m \right],$$
where $\beta_m$ is the activation penalty for expert $m$ and increases geometrically in $m$. Following the argument of An Infinite Restricted Boltzmann Machine, the normalizer stays finite as the number of potential experts goes to infinity, provided the potentials are kept within a bounded range relative to the growth of $\beta_m$. A blank expert adds zero energy apart from its penalty, so it changes nothing until it is trained.
Given $x$, the number of active experts has the conditional distribution
$$p(z \mid x) \propto \exp\left( \sum_{m=1}^{z} \left[ \log \Phi_m(x) - \beta_m \right] \right),$$
where $\Phi_m(x)=\sum_{s^{(m)}} \phi_m(x,s^{(m)})$ is obtained with one forward pass per expert. This is what an undirected product makes possible. In the directed alternative, The Infinite Factorial Hidden Markov Model, observing $x$ couples all chains and forces slice sampling. Here each expert's path is drawn exactly by forward-filtering backward-sampling, independently of the others.
One contrastive divergence step proceeds as follows. We sample $z$ from the expression above, then sample each active expert's path, then sample a "fantasy" sequence. Given all the paths, the fantasy sequence factorizes over time into renormalized products of emissions. Finally we resample $z$ and the paths for the fantasy. As in the Infinite RBM, the gradient is a hybrid. The data-side term is computed exactly over $z$ for the instantiated experts plus one blank. The fantasy-side term is sampled. A new expert is instantiated whenever a sampled $z$ exceeds the current count, and experts beyond the largest $z$ seen recently are removed.
The ordering also breaks the symmetry between experts. We therefore expect a coarse-to-fine allocation, with early experts capturing dominant processes and later ones capturing residual structure. Whether that ordering helps or hurts specialization is tested directly.
Research Program
The work has three parts.
The first is building the sampler and checking it on synthetic factorial data, where the true number of chains is known.
The second studies how bias interacts with growth. Training uses contrastive divergence with $k \in \{1, 5, 25\}$ steps and a persistent-chain variant. We record the birth rate, the final expert count, and the held-out likelihood. On the Convergence Properties of Contrastive Divergence shows that the update is not the gradient of any objective. Training RBMs based on the signs of the CD approximation of the log-likelihood derivatives attributes the bias to unexplored distant modes. Together they predict one failure mode: a short chain that cannot cross energy barriers will keep "asking" for capacity. The opposite prediction comes from the observation that biased stochastic updates still find good basins in practice (Learning Algorithms for the Classification Restricted Boltzmann Machine). On that view, $k=1$ suffices. The final count's dependence on $k$ is the measurement that decides between them.
The third part quantifies specialization. We measure how well each expert's hidden path predicts known ground-truth factors: weather stations' regions, which dancer, which speaker. We do this with no auxiliary balancing loss, in contrast to the controller-plus-Viterbi-EM machinery of Modular Networks: Learning to Decompose Neural Computation and the relaxation and annealing of Multiple Choice Learning of Low-Rank Adapters for Language Modeling.
Baselines
Do-nothing reference. The naive reference is a single HMM trained by Baum-Welch, with its state count chosen on validation data. Its role is to show the cost of the single-regime bottleneck. The fixed-product paper reports that such HMMs "struggled" on salsa motion capture, but no reported number was found on Lacuna for that comparison or for rainfall. We therefore rerun it ourselves on the same splits.
Fixed product of HMMs. The strongest same-family competitor is the fixed product of HMMs of Products of Hidden Markov Models: It Takes N>1 to Tango, swept over expert counts, with the winner chosen by held-out likelihood estimated by annealed importance sampling. For fairness, the total training compute of the whole sweep is counted against the single growing run. The same estimator, data, and per-expert state count are used, and each sweep point gets the same tuning budget as our run. Beating it means matching its best held-out likelihood within the estimator's error at a fraction of the sweep's compute, and selecting the same count.
Oversized-and-pruned product. This is the ablation that isolates our key ingredient. It is an oversized product with a group penalty on each expert's log-potentials, which drives unneeded experts to the blank state, in the spirit of the rank-penalized dynamical systems of A Regularized Linear Dynamical System Framework for Multivariate Time Series Analysis. It is trained by the same contrastive divergence code with the same number of updates. Its penalty strength is tuned with the same budget as our $\beta$ schedule. A second ablation keeps the ordering but freezes $z$ at its maximum, which separates the effect of ordering from the effect of growth.
Directed nonparametric model. The strongest existing method that infers the number of processes is The Infinite Factorial Hidden Markov Model. On the Speech Separation Challenge it reports mutual information of 0.296 with 10 microphones and 0.091 with 3 microphones, and it recovers exactly 5 speakers where infinite ICA found 9. We rerun it under the same wall-clock budget on our other datasets. On audio we compare against its published figures. Because audio mixing is additive, that benchmark is home ground for a directed model. Matching it would be a strong result, and losing there would not by itself refute the claim.
Single-chain state discovery and monolithic motion model. For single-chain nonparametric state discovery we include the birth/merge/delete variational HDP-HMM of Scalable Adaptation of State Complexity for Nonparametric Hidden Markov Models. For motion we include the conditional RBM of Modeling Human Motion Using Binary Latent Variables, which reports missing-leg imputation MSE of 8.78 and upper-body imputation MSE of 20.52 with 200 hidden units.
Why not just…?
Why not just sweep the number of experts and pick by likelihood? In a static setting this may well be as accurate, and we accept that. Its weaknesses are two. Each sweep point needs its own annealed importance sampling run. A sweep also cannot react when a new regime appears partway through a stream, which is the open-world limitation highlighted in Multi-intention Inverse Q-learning for Interpretable Behavior Representation. The compute-matched comparison and the streaming experiment settle which matters. If growth only ties the sweep on accuracy and compute in the static case, we will report that honestly.
Why not just start with many experts and prune with a sparsity penalty? This is the most serious threat. The rank-penalized dynamical system recovered a true rank of 10 from 30 initial dimensions (A Regularized Linear Dynamical System Framework for Multivariate Time Series Analysis), so pruning can work. Our hypothesis is that pruning fails in streams: the penalty kills spare experts before the new regime arrives, and they do not revive. We also expect symmetric unordered experts to duplicate one another more often. If the pruned model matches growth in the streaming experiment, the growth mechanism is unnecessary. The contribution would then shrink to the bias analysis and the ordering ablation.
Why not just use the directed infinite factorial HMM? It already infers the number of chains. However, it needs slice sampling over coupled chains because of explaining away, and it combines chains additively rather than as a product. We compare under matched wall-clock time. We expect it to win on additive audio and to lose on rainfall and motion, where products fit the structure.
Why not just widen a monolithic conditional RBM or a single HMM? A single HMM needs exponentially many states for independent factors (Factorial Hidden Markov Models). A wide conditional RBM shares one hidden layer across all styles and yields no per-expert factors to inspect. The specialization metric and the imputation numbers test whether that matters beyond interpretability.
Proposed Experiments
The experiments use five datasets. Synthetic binary factorial sequences with 2 to 8 known independent chains form the controlled test. The Ceará rainfall data are binary and multi-station. Salsa and CMU/MIT motion capture are used with Gaussian emissions; products of Gaussians stay normalizable when precisions are positive. The Speech Separation Challenge mixtures complete the set.
The first decisive check is count recovery on synthetic data across $k$ and the persistent variant. If the final count rises with smaller $k$ while held-out likelihood falls, contrastive divergence bias is driving births, and the method needs persistent chains.
The second check is a stream. Motion styles are revealed one at a time (walking, then running, then a held-back style). The new style should cause births within a bounded number of updates, without forgetting earlier styles, measured by held-out likelihood per style. The pruned ablation is run on the same stream.
The third check measures whether expert paths predict geographic region on rainfall, dancer identity on salsa, and speaker identity on audio, with and without ordering. On motion we also report imputation MSE against the conditional RBM's 8.78 and 20.52, and on audio mutual information against the infinite factorial HMM's 0.296 and 0.091. All likelihoods are estimated with annealed importance sampling, with variance reported across runs.
References
- Products of Hidden Markov Models: It Takes N>1 to Tango
- An Infinite Restricted Boltzmann Machine
- The Infinite Factorial Hidden Markov Model
- On the Convergence Properties of Contrastive Divergence
- Training RBMs based on the signs of the CD approximation of the log-likelihood derivatives
- Learning Algorithms for the Classification Restricted Boltzmann Machine
- Modular Networks: Learning to Decompose Neural Computation
- Multiple Choice Learning of Low-Rank Adapters for Language Modeling
- A Regularized Linear Dynamical System Framework for Multivariate Time Series Analysis
- Scalable Adaptation of State Complexity for Nonparametric Hidden Markov Models
- Modeling Human Motion Using Binary Latent Variables
- Multi-intention Inverse Q-learning for Interpretable Behavior Representation
- Factorial Hidden Markov Models