HMM Procedure

This section is a brief review of the hidden Markov model. For more information, see Rabiner (1989), Krolzig (1997), Frühwirth-Schnatter (2006), and Cappé, Moulines, and Rydén (2010).

The hidden Markov model (HMM) is a bivariate discrete time process , where is a (hidden) Markov chain; conditional on , the observable process is a sequence of independent random variables such that the conditional distribution of depends only on . The is often called the state. In general, the HMM can be expressed in three equations:

Here the initial probability distribution function is the probability distribution function for initial state ; the transition probability distribution function is the probability distribution function of current state conditional on the past state ; the observation probability distribution function is the probability distribution function of current observation conditional on the current state ; and all probability distribution functions might depend on the parameter .

There is no restriction on the dimensionality of and ; that is, they might be scalars, vectors, or matrices.

If the transition probability distribution function is time-independent (that is, the Markov chain is time-homogeneous), then the HMM is called the (time-)homogeneous HMM; otherwise, the HMM is called the (time-)inhomogeneous HMM.

The state could take discrete or continuous values or even a mix of discrete and continuous values.^[7] In the simplest and most popular case, is a scalar and takes finite discrete values; that is, . In this case, the HMM could be called the finite-state-space HMM.

For the finite-state-space HMM, the initial state distribution function can be expressed as a vector , which is called the initial state probability vector (ISPV); that is,

For the finite-state-space and homogeneous HMM, the transition probability distribution function can be expressed as a matrix , which is called the transition probability matrix (TPM), where an element of denotes the probability transitioning from past state i to current state j; that is,

There are six common problems to solve for an HMM:

In most cases, the learning problem is the most difficult one. You might apply the maximum likelihood (ML) method or the maximum a posteriori (MAP) method to get the point estimate of parameter . For more information, see the section Parameter Estimation Methods.

Several algorithms are helpful in solving the problems for the HMMs. Three of them are the forward algorithm, the backward algorithm, and the Viterbi algorithm. They might be generalized to support many types of HMMs. The following sections focus on applying them to the finite-state-space and homogeneous HMM.

Forward Algorithm

The forward algorithm recursively calculates the joint probability distribution of a state at time t, , and all observations up to time t, . First, define as the joint probability of and :

Then, can be recursively calculated by the following steps:

1. Calculate by

   

2. Calculate by

   

You can solve the evaluating problem by

Because the likelihood of all observations, , can be calculated, you can apply the maximum likelihood method to estimate the unknown parameter ; if the prior distribution of the parameter is given, you can also apply the MAP method. That is, you might use the forward algorithm in the learning problem.

You can solve the filtering problem by

When the filtering problem is solved, you can solve the forecast problem, because the h-step-ahead prediction of the state probability can be calculated by

where is the vector with the ith element as , and is the vector with the ith element as :

The distribution of conditional on observations is the following mixture distribution:

Backward Algorithm

To solve the smoothing problem, in addition to the forward algorithm, you also need the backward algorithm. Define as the probability of observing the future observations conditional on the current state :

The backward algorithm recursively calculates as follows:

1. Set .

2. Calculate , , by

   

When you calculate both and , by using the forward algorithm and backward algorithm, the smoothing problem is solved, because you can calculate the probability of state taking value i given all observations as follows:

Viterbi Algorithm

You use the Viterbi algorithm to solve the decoding problem. First, define the highest probability of a single state path ending in state and observations as follows:

To keep track of the best path, for , define

Then, and can be recursively calculated as follows:

1. Calculate by

   

2. Calculate and by

   

Then, the probability of the best path is

Define , and the best state path can be backtracked by

That is, is the best state path. The decoding problem is solved.