Rabiner 1989 - HMM Types, Continuous Densities and State Duration

Summary

Beyond ergodic HMMs, the paper covers left-right (Bakis) models with $a_{ij}=0$ for $j<i$, continuous mixture emissions with closed-form reestimation, autoregressive HMMs, null transitions, parameter tying, and explicit state-duration densities. Explicit duration fixes the geometric dwell implied by self-transitions but multiplies computation by about $D^2/2$ and adds many parameters. Optimisation criteria beyond ML (MMI, MDI) and an HMM distance measure are also given.

Overview

All Baum-Welch reestimation preserves zeros: a parameter initialised to zero stays zero (see eq. 44), so structural constraints can be imposed by initialisation.

Main Content

Ergodic vs left-right models (eqs 45-48; Fig. 7)

Ergodic (fully connected): every state reachable from every other, all $a_{ij}>0$. Left-right (Bakis): $a_{ij}=0$ for $j<i$ (eq. 45); ${\pi }_i=0$ for $i\ne 1$, ${\pi }_1=1$ (eq. 46); optionally $a_{ij}=0$ for $j>i+\Delta$ (eq. 47; $\Delta =2$ in Fig. 7b). Last state: $a_{NN}=1$, $a_{Ni}=0$ for $i<N$ (eq. 48). States proceed left to right so the model suits signals whose properties change over time. Fig. 7c: 6-state parallel-path left-right model with cross-coupled paths.

Continuous mixture emission (eqs 49-54)

$b_j(\mathbf{O})={\sum }_{m=1}^M{c}_{jm}\mathcal{N}[\mathbf{O},{\mathbf{\mu }}_{jm},U_{jm}]$, ${\sum }_m{c}_{jm}=1$, $c_{jm}\ge 0$, with log-concave or elliptically symmetric component (Gaussian). Reestimation (eqs 52-54): ${\bar{c}}_{jk}=\frac{{\sum }_t{\gamma }_t(j,k)}{{\sum }_t{\sum }_m{\gamma }_t(j,m)}$, ${\bar{\mathbf{\mu }}}_{jk}=\frac{{\sum }_t{\gamma }_t(j,k){\mathbf{O}}_t}{{\sum }_t{\gamma }_t(j,k)}$, ${\bar{U}}_{jk}=\frac{{\sum }_t{\gamma }_t(j,k)({\mathbf{O}}_t-{\mathbf{\mu }}_{jk})({\mathbf{O}}_t-{\mathbf{\mu }}_{jk}{)}^{\prime }}{{\sum }_t{\gamma }_t(j,k)}$ where ${\gamma }_t(j,k)=\left[\frac{{\alpha }_t(j){\beta }_t(j)}{{\sum }_i{\alpha }_t(i){\beta }_t(i)}\right]\left[\frac{c_{jk}\mathcal{N}({\mathbf{O}}_t,{\mathbf{\mu }}_{jk},U_{jk})}{{\sum }_m{c}_{jm}\mathcal{N}({\mathbf{O}}_t,{\mathbf{\mu }}_{jm},U_{jm})}\right]$ is the probability of being in state $j$ with mixture component $k$ at time $t$.

Autoregressive HMM (eqs 55-63)

Within a state, the observation vector $\mathbf{O}=(x_0..x_{K-1})$ follows an autoregression $O_k=-{\sum }_{i=1}^p{a}_i{O}_{k-i}+e_k$ with Gaussian $e_k$ of variance ${\sigma }^2$; for large $K$ the density is $f(\mathbf{O})=(2\pi {\sigma }^2{)}^{-K/2}\exp \{-\frac{1}{2{\sigma }^2}\delta (\mathbf{O},\mathbf{a})\}$ with $\delta (\mathbf{O},\mathbf{a})=r_a(0)r(0)+2{\sum }_{i=1}^p{r}_a(i)r(i)$, where $r$ and $r_a$ are autocorrelations of the observations and of the coefficients. Gain-normalised, mixtures $b_j(\mathbf{O})={\sum }_m{c}_{jm}{b}_{jm}(\mathbf{O})$ with reestimation ${\bar{r}}_{jk}={\sum }_t{\gamma }_t(j,k)r_t/{\sum }_t{\gamma }_t(j,k)$ then solving normal equations for ${\hat{\mathbf{a}}}_{jk}$.

Null transitions and tied states (Sec. IV.C; Fig. 8)

Null transitions ($\varphi$) move between states without emitting an observation (used for deletions and arbitrary-length digit grammars). Tying sets equivalence classes of parameters (e.g. identical emission densities in several states) to reduce the number of free parameters when training data are scarce.

Explicit duration HMM (eqs 64-83; Fig. 9)

A standard HMM has $p_i(d)=(a_{ii}{)}^{d-1}(1-a_{ii})$, geometric, inappropriate for many physical signals. In the variable-duration HMM, self-transitions are set to zero and each state draws a duration $d\sim p_i(d)$ (truncated at maximum $D$), emits $d$ observations, then transitions $a_{q_1{q}_2}$ with $a_{ii}=0$. Forward variable (eq. 65): ${\alpha }_t(i)=P(O_1..O_t,S_i\text{ ends at }t\mid \lambda )$, with

$${\alpha }_t(j)=\sum _{i=1}^N\sum _{d=1}^D{\alpha }_{t-d}(i)a_{ij}{p}_j(d)\prod _{s=t-d+1}^t{b}_j(O_s)(\text{eq. 68}).$$

Costs: about $D$ times the storage and $D^2/2$ times the computation of a standard HMM (for $D=25$, a factor of about 300 in compute); many extra parameters; fewer transitions in a finite sample to estimate $p_i(d)$. Parametric alternatives: Gaussian $p_i(d)=\mathcal{N}(d,{\mu }_i,{\sigma }_i^2)$ (eq. 82) or Gamma $p_i(d)={\eta }_i^{{\nu }_i}{d}^{{\nu }_i-1}{e}^{-{\eta }_{i}d}/\Gamma ({\nu }_i)$ (eq. 83, mean ${\nu }_i{\eta }_i^{-1}$, variance ${\nu }_i{\eta }_i^{-2}$). Reestimation formulas (78)-(81) use extra variables ${\alpha }_t^{\ast }(i)$ (state begins at $t+1$), ${\beta }_t(i)$, ${\beta }_t^{\ast }(i)$ (eqs 71-77).

Dwell-time comparison

A state with $a_{ii}=0.9$ has geometric dwell with mean 10 and mode 1, i.e. its most likely duration is a single step. A kinesin dwell that needs two sequential hidden phases (hypoexponential) has a non-monotone density with mode away from 1. A geometric dwell cannot represent it, but a two-phase chain of states can (E59 uses a 2-phase lattice HMM), a cheaper alternative to explicit-duration HMMs.

ML, MMI, MDI criteria and HMM distance (eqs 84-89)

ML: $P_v^{\ast }={\max }_{\lambda }P(O^v\mid {\lambda }_v)$ per model. MMI maximises $I^{\ast }={\max }_{\lambda }\{\log P(O^v\mid {\lambda }_v)-\log {\sum }_{w=1}^{V}P(O^v\mid {\lambda }_w)\}$ summed over training sequences, i.e. separates the correct model from the others; solved by steepest descent (no reestimation formula). MDI minimises the cross-entropy $D(Q\Vert P_{\lambda })=\int q(y)\ln (q(y)/p(y))dy$ between signal and model densities (generalised Baum algorithm). ML, MMI and MDI can all be formulated as MDI. HMM distance: $D({\lambda }_1,{\lambda }_2)=\frac{1}{T}[\log P(O^{(2)}\mid {\lambda }_1)-\log P(O^{(2)}\mid {\lambda }_2)]$ with $O^{(2)}$ generated by ${\lambda }_2$ (eq. 88), symmetrised $D_s=\frac{1}{2}[D({\lambda }_1,{\lambda }_2)+D({\lambda }_2,{\lambda }_1)]$ (eq. 89). Two superficially different HMMs can be statistically equivalent (example with $p=0.6,q=0.7,r=0.2$ giving $s=13/30=0.433$), an identifiability warning relevant to label switching.

Examples (PyMC-style)

A two-state non-homogeneous movement HMM (E24/E48): transition rows are softmax of a covariate linear predictor, emission distributions for step length are gamma, ordered by mean to break label switching (untested sketch in Bayesian HMMs - Label Switching, Non-Homogeneous Transitions and Dwell Times).

Connections

Rabiner 1989 - Problem 3 - Baum-Welch Reestimation supplies the reestimation these formulas extend. Applied use of left-right and duration models: Rabiner 1989 - Speech Recognition Applications and Results.

See Also

Rabiner 1989 - HMM Tutorial - Overview, Model Building with Latent Variables - Animal Movement