A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition

Deterministic models, which exploit known properties of the signal (a sine wave, a sum of exponentials) and only need parameter values; and statistical models (Gaussian, Poisson, Markov, hidden Markov processes), which characterize only the statistical properties, assuming the signal is a parametric random process.

It is a basis for designing processing systems (e.g. removing noise); it lets us learn about and simulate the source without having it available; and, most importantly, such models often work extremely well in practice for prediction, recognition and identification.

Baum’s theory appeared in mathematical journals engineers didn’t read, and the early speech applications (Baker at CMU, Jelinek’s group at IBM) lacked tutorial material; tutorials like this one filled the gap.

A system in one of \(N\) states that changes state at regular times with probabilities depending only on the current state: \(P[q_t = S_j \mid q_{t-1} = S_i, q_{t-2}, \ldots] = P[q_t = S_j \mid q_{t-1} = S_i] = a_{ij}\), time-independent, with \(a_{ij} \ge 0\), \(\sum_j a_{ij} = 1\).

Its output at each time is the state itself, each state corresponding to a physical, observable event (e.g. rain, cloudy, sunny in Rabiner’s weather example).

Multiply the initial state probability by the transition probabilities along the sequence: \(P(O) = \pi_{q_1} \prod_t a_{q_{t-1} q_t}\). E.g. sunny then sun-sun-rain-rain-sun-cloudy-sun is \(1 \cdot a_{33} a_{33} a_{31} a_{11} a_{13} a_{32} a_{23}\).

Geometric (“exponential”): \(p_i(d) = a_{ii}^{d-1}(1 - a_{ii})\), with expected duration \(\bar{d}_i = \frac{1}{1 - a_{ii}}\). With \(a_{33} = 0.8\), sunny spells last 5 days on average.

A doubly embedded stochastic process: an underlying Markov chain of states that is not observable, seen only through another stochastic process that produces observations as a probabilistic function of the state.

Someone behind a curtain reports only heads and tails. One biased coin (1 parameter), two coins (4 parameters) or three coins (9 parameters) could explain the sequence. Bigger models are more expressive, but practical considerations limit size, and a 3-coin model is inappropriate if only one coin is really tossed.

A genie picks an urn according to a random process, draws a coloured ball, records its colour and replaces it, then picks the next urn depending on the current one. We see only the colours: states are urns, observations are colours.

\(N\) states and \(M\) observation symbols; transition probabilities \(A = \{a_{ij}\}\); emission probabilities \(B = \{b_j(k)\}\), \(b_j(k) = P[v_k \text{ at } t \mid q_t = S_j]\); initial distribution \(\pi_i = P[q_1 = S_i]\).

Choose \(q_1\) from \(\pi\); at each time emit \(O_t\) from \(b_{q_t}\), then move to \(q_{t+1}\) using \(a_{q_t \cdot}\), until \(T\) observations. The same procedure models how a given sequence was generated.

problem	question	solution
1 evaluation	\(P(O \mid \lambda)\)?	forward(–backward) procedure
2 decoding	best state sequence \(Q\) for \(O\)?	Viterbi algorithm
3 training	adjust \(\lambda\) to maximize \(P(O \mid \lambda)\)?	Baum–Welch (EM)

The framing is due to Jack Ferguson (IDA).

Train one HMM per vocabulary word on repetitions of it (Problem 3); segment training sequences into states to understand and refine the models (Problem 2); recognize an unknown word by scoring every word model and picking the highest likelihood (Problem 1).

\(P(O \mid \lambda) = \sum_Q \pi_{q_1} b_{q_1}(O_1) a_{q_1 q_2} b_{q_2}(O_2) \cdots\) sums over \(N^T\) sequences, about \(2T \cdot N^T\) operations: for \(N = 5\), \(T = 100\), around \(10^{72}\).

\(\alpha_t(i) = P(O_1 \ldots O_t, q_t = S_i \mid \lambda)\). Initialization \(\alpha_1(i) = \pi_i b_i(O_1)\); induction \(\alpha_{t+1}(j) = \big[\sum_i \alpha_t(i) a_{ij}\big] b_j(O_{t+1})\); termination \(P(O \mid \lambda) = \sum_i \alpha_T(i)\). Cost about \(N^2 T\) (about 3000 operations for \(N = 5\), \(T = 100\)).

Because of the lattice (trellis): there are only \(N\) states per time slot, so however long the sequence, all paths re-merge into these \(N\) nodes, and each node needs only the \(N\) values of the previous slot.

\(\beta_t(i) = P(O_{t+1} \ldots O_T \mid q_t = S_i, \lambda)\), with \(\beta_T(i) = 1\) and \(\beta_t(i) = \sum_j a_{ij} b_j(O_{t+1}) \beta_{t+1}(j)\). Not needed for Problem 1, but used for Problems 2 and 3.

Except for degenerate models there is no “correct” state sequence, only sequences optimal under some criterion, and the right criterion depends on the use (learning model structure, continuous speech recognition, state statistics…).

Choose \(q_t = \arg\max_i \gamma_t(i)\), where \(\gamma_t(i) = \frac{\alpha_t(i)\beta_t(i)}{P(O \mid \lambda)}\), maximizing the expected number of correct states. But the resulting sequence may be invalid (use a transition with \(a_{ij} = 0\)), since it ignores the probability of state sequences.

Find the single best path: \(\delta_t(i)\) is the highest probability of a path ending in \(S_i\) at time \(t\); \(\delta_{t+1}(j) = \big[\max_i \delta_t(i) a_{ij}\big] b_j(O_{t+1})\), keeping back-pointers \(\psi_{t+1}(j) = \arg\max_i\); at the end take \(\arg\max_i \delta_T(i)\) and backtrack.

It is the same lattice computation with maximization over previous states in place of summation, plus backtracking to recover the path.

No: there is no known analytic solution, and for finite training data no optimal way of estimating them. Iterative methods (Baum–Welch/EM, or gradient techniques) find local maxima.

\(\xi_t(i, j) = P(q_t = S_i, q_{t+1} = S_j \mid O, \lambda) = \frac{\alpha_t(i) a_{ij} b_j(O_{t+1}) \beta_{t+1}(j)}{P(O \mid \lambda)}\), and \(\gamma_t(i) = \sum_j \xi_t(i, j)\). Summed over \(t\), they give expected numbers of transitions from \(S_i\) to \(S_j\) and from \(S_i\).

\(\bar{\pi}_i = \gamma_1(i)\); \(\bar{a}_{ij} = \frac{\sum_t \xi_t(i, j)}{\sum_t \gamma_t(i)}\) (expected transitions \(i \to j\) / expected transitions from \(i\)); \(\bar{b}_j(k) = \frac{\sum_{t: O_t = v_k} \gamma_t(j)}{\sum_t \gamma_t(j)}\) (expected times in \(j\) seeing \(v_k\) / expected times in \(j\)).

Either the current model is a critical point of the likelihood (and re-estimation leaves it unchanged), or the re-estimated model is strictly more likely: \(P(O \mid \bar\lambda) > P(O \mid \lambda)\). Iterating converges to a local maximum, often one of many.

It is EM for this problem: the E step computes Baum’s auxiliary function \(Q(\lambda, \bar\lambda) = \sum_Q P(Q \mid O, \lambda) \log P(O, Q \mid \bar\lambda)\), the M step maximizes it; the stochastic constraints on the parameters are satisfied automatically.

Ergodic: every state reachable from every other (all \(a_{ij} > 0\) if fully connected). Left-right: the state index never decreases (\(a_{ij} = 0\) for \(j < i\)), starting in state 1 and ending in \(N\), often limiting jumps (\(a_{ij} = 0\) for \(j > i + \Delta\)); suited to signals whose properties change over time, like speech.

Any parameter initially set to zero stays zero throughout Baum–Welch re-estimation, so the topology is preserved automatically.

Quantizing continuous signals (vectors) through a codebook can seriously degrade them. The usual form is a finite mixture per state, \(b_j(O) = \sum_m c_{jm} \mathcal{N}(O; \mu_{jm}, U_{jm})\), which can approximate any finite continuous density arbitrarily closely.

Using \(\gamma_t(j, k)\), the probability of being in state \(j\) at time \(t\) with mixture component \(k\) accounting for \(O_t\): \(\bar{c}_{jk}\) = expected times in \(j\) using \(k\) / expected times in \(j\); \(\bar{\mu}_{jk}\) is the \(\gamma\)-weighted average of the observations, and similarly for covariances.

Transitions that produce no observation (in arc-emitting HMMs like IBM’s). They allow skipping states, compactly encode alternative pronunciations (deletions) in word networks, and let a digit grammar loop back to produce digit strings of any length.

Setting up an equivalence between parameters of different states (e.g. the same observation density for several states), which reduces the number of independent parameters; especially useful when training data is insufficient.

Modeling state duration: the implied duration density is geometric, inappropriate for most physical signals. A variable-duration (semi-Markov) HMM sets self-transitions to zero and draws an explicit duration \(p_i(d)\) for each state visit.

About \(D\) times the storage and \(D^2/2\) times the computation (a factor of about 300 for \(D = 25\)), many more parameters per state, and less data per parameter. Parametric durations (Gaussian, Gamma) or uniform ranges with constrained Viterbi help.

Maximum mutual information: design all word models together to maximize their discrimination power, i.e. each model’s ability to distinguish sequences from its own class from those of competing models, rather than fitting each model separately.

Each \(\alpha_t(i)\) is a sum of products of many probabilities below 1, so it heads exponentially to zero; for \(t\) around 100 it underflows even in double precision.

Normalize the \(\alpha_t(i)\) at each \(t\) by \(c_t = 1 / \sum_i \alpha_t(i)\), scale the \(\beta\)s with the same factors (which cancel in the re-estimation formulas), and compute \(\log P(O \mid \lambda) = -\sum_t \log c_t\).

Work with logarithms: \(\phi_t(j) = \max_i [\phi_{t-1}(i) + \log a_{ij}] + \log b_j(O_t)\), which needs no scaling; the log terms can be precomputed.

Each state sees only a few observations before moving on, so one sequence gives too little data. Re-estimation sums the expected counts over all independent sequences (each with its own scaling).

Random or uniform initial \(\pi\) and \(A\) usually suffice; good initial \(B\) estimates help for discrete symbols and are essential for continuous mixtures, e.g. from manual segmentation, maximum-likelihood segmentation, or segmental k-means.

More data, a smaller model, or interpolating the full model with a reduced (tied) model, \(\bar\lambda = \epsilon\lambda + (1 - \epsilon)\lambda'\), with \(\epsilon\) estimated by forward–backward on held-out data (deleted interpolation, Jelinek and Mercer).

Compute spectral (e.g. LPC) feature vectors, map each to the nearest codebook vector by vector quantization, train one left-right HMM per word, and recognize by choosing the word whose model gives the highest likelihood (forward or Viterbi score).

Iteratively segment training sequences into states with the Viterbi algorithm under the current model, re-estimate each state’s parameters from the observations assigned to it (clustering them, for mixtures), and repeat until convergence; it gives good initial estimates for Baum–Welch.

By concatenating single-word HMMs and using level building, a dynamic-programming search that finds the best sequence of word models (one per “level”) to match the whole utterance, without segmenting it first.

Successive observations (frames) are assumed independent given the states; observation distributions are assumed to be mixtures of Gaussian or autoregressive densities; and the first-order Markov assumption ignores dependencies spanning several states. Despite this they work extremely well.