Rabiner (1989) A tutorial on hidden Markov models

The renowned article to describe hidden Markov models (HMMs). I may not have enough background knowledge to appreciate the speech recognition part but this is very clear and easy to follow to understand the HMM mechanics.

For some background: A Markov chain is to model an autonomous system with state observable. If we can manipulate the state transition of the system, we have the Markov decision process. HMM is, however, about an autonomous system with unobservable state.

A Markov process is modelled as following: We have set of states \(S=\{1,\cdots,N\}\) which the state at time \(t\) is specified as \(q_t\) (or sequence denoted as \(Q=q_1q_2\cdots q_T\)), and the transition probability is specified by

The hidden Markov model introduces an observation sequence \(O = O_1O_2\cdots O_T\) to the Markov process. We can describe a HMM as follows: There is a set of \(N\) urns and a Markov process of selecting an urn. Then a ball is drawn from the selected urn with replacement, which is of a set of colors \(V=\{1,\cdots,M\}\), i.e. \(O_t\in V\). Only the sequence of ball drawn is observable as \(O\). The observation probability is given by

and the initial probability is given by

The HMM is parameterized by \(\lambda = (A, B, \Pi)\) which \(A=(a_{ij})_{N\times N}\) is the state transition probability matrix, \(B=(b_j(k))_{N\times M}\) is the observation probability matrix, and \(\Pi=(\pi_j)_{N\times 1}\) is the vector of initial probability.

The HMM is usually to solve for one of the following three problems:

1. \(\mathbb{P}[O\mid \lambda]\): Given model \(\lambda\) find the probability of a given observation \(O\).
2. \(Q=\arg\max \mathbb{P}[Q\mid O,\lambda]\): Given observation sequence \(O\) and model \(\lambda\), determine the optimal state sequence \(Q=q_1q_2\cdots q_T\) that correspond to \(O\)
3. \(\lambda=\arg\max\mathbb{P}[O\mid \lambda]\): Given observation \(O\), determine the parameter \(\lambda\)

Below address each of these problems:

Solution to \(\mathbb{P}[O\mid \lambda]\)

Consider a fixed state sequence \(Q=q_1q_2\cdots q_T\),

and

which the last equation above is explained as follows: The multiplication inside summation is \(2T\) terms, which computes the probability that, at \(t=1\), we start at state \(q_1\) with probability \(\pi_{q_1}\); and at state \(q_1\), observation \(O_1\) is generated at probability \(b_{q_1}(O_1)\); and at \(t=2\), the transition from \(q_1\) to \(q_2\) at probability \(a_{q_1q_2}\); and so on until state \(q_T\) observing \(O_T\). Such probability should sum over the \(N^T\) possible state sequences \(Q\).

A naive computation is in the order of \(O(N^T T)\) but we can speed it up to \(O(N^2 T)\) by dynamic programming on a lattice structure through the forward-backward procedure: Defining

Solving recursively, we have

For the convenience of the subsequent discussion we can define the backward counterpart:

and recursively:

Solution to \(Q = \arg\max \mathbb{P}[Q\mid O,\lambda]\)

We can treat each state \(q_t\) separately and find the most likely state at each time step. Then the probability is given by

which the fraction term above is to make \(\sum_{i=1}^N \gamma_t(i)=1\) and this allows us to solve \(q_t\) individually for all \(1\le t\le T\)

This approach, however, maximize the number of correct \(q_t\) in the sequence \(Q\) but not the most probable sequence \(Q\) as a whole. To find the single best sequence \(Q\), we use the Viterbi algorithm:

Define the highest running probability of a sequence as

i.e., this is the highest probability of subsequence \(q_1q_2\cdots q_{t-1}\) given \(q_t=i\) and observation sequence \(O_1O_2\cdots O_t\). Then the next time step is recursively,

and ultimately \(\mathbb{P}[Q\mid O,\lambda]=\max_i\delta_T(i)\). So we have the following algorithm:

Initially we have, for \(1\le i\le N\),

Then in time steps \(2\le t\le T\) and for all states \(1\le j\le N\),

and finally after time step \(T\), we back track the whole sequence \(Q\),

Solution to \(\lambda = \arg\max\mathbb{P}[O\mid\lambda]\)

By local maximization using expectation-maximization (EM) method (Baum-Welch algorithm): Define the probability of transition from \(i\) to \(j\) at time \(t\) to \(t+1\) as

and hence the probability of state at individual time step \(\gamma_t(i)=\sum_j\xi_t(i,j)\) for \(1\le t\le T\). The corresponding expected number of transition from state \(i\in S\) is \(\sum_{t=1}^{T-1}\gamma_t(i)\); and expected number of transition from state \(i\) to state \(j\) is \(\sum_{t=1}^{T-1}\xi_t(i,j)\).

Given we have enough data to train the model, we can estimate the model parameter as follows:

These estimation depends on \(\gamma_t(i)\) and \(\xi_t(i,j)\) which in turn depends on \(\lambda=(A,B,\Pi)\). We recursively apply these estimation formula and update \(\lambda\) until converge. This is the re-estimation procedure and each step will give a greater \(\mathbb{P}[O\mid\lambda]\).

An alternative approach is to solve for the maxima of \(\mathbb{P}[O\mid\lambda]\) by Lagrangian multipliers, which yields this set of formula:

Iterative procedure in Markov decision process

The following formula is based on the notation used in Wikipedia. It turns out the iterative procedure to converge to the solution is common to this sort of problems.

A Markov decision process is modelled as \((S, A, P_a, R_a)\) which \(S\) as the set of states, \(A\) is the set of actions, and

and \(R_a(i,j)\in\mathbb{R}\) are, respectively, the probability of transition given action \(a\) and the reward of the transition given action \(a\).

The MDP is to find a policy function \(\pi: S\mapsto A\) that selects the action \(a\in A\) for the state \(s\in S\). This is a simplified form as the function is time-invariant, which reduces the MDP into a Markov chain, and

becomes the state transition probability matrix. To determine the policy function \(\pi(s)\), we aimed at maximizing the present value of the reward

which \(\gamma = \frac{1}{1+r}\in [0,1]\) is a discount factor. The algorithm is to apply the following until converge:

Bibliographic data

@article{
   title = "A tutorial on hidden Markov models and selected applications in speech recognition",
   author = "Lawrence R. Rabiner",
   journal = "Proceedings of the IEEE",
   volume = "77",
   number = "2",
   month = "Feb",
   year = "1989",
   pages = "257--286",
   doi = "0018-9219/89/0200-0257",
}