MATLAB: Hidden Markov Models

We can model things with Markov Chains. But sometimes we don’t have access to the full information.

For instance, we observe the movements of a stock price. Price changes follow some trends of the economy, but we don’t get to see the state of the economy, which is too big and complicated.

In a Hidden Markov Model, we have a first order stationary process

  • These can be in a finite number of spaces
  • These have transition probabilities

On top of this, there is a mechanism that produces variables , which are observable - variables are hidden.

In other words, only is impacted by other variables through

Use cases of Hidden Markov Models

Speech Recognition

Assuming a sound recording. We want to recover the text from the sounds. Now, text follows a Markov Chain very closely.

Speech can be thought of as emissions from text. We can easily find the parameters of this Markov Chain

Join Distribution

Here is a Hidden Markov Chain with:

  • Hidden states
  • Transition probabilities
  • Emission probabilities (found from the emission matrix )

we calcuate the probability of join state as:

Filtering

Filtering problems are about finding the final states of the HMM.

Suppose we have the following observations:

We want to find the following probability for all states :

Naive Approach

To do this, we just sum over all paths that end in

But if there are states, then there are paths in the chain. So there is actually a better way of doing this.

Alpha

We are interested in the probability alpha, which is:

Now for each alpha we need operations and there are values of alpha - much better than !

This sort of trick goes under the name of dynamic programming (=optimisation).

MATLAB Implementation

function a = alpha_dynamic(M,p,B,v)
% ALPHA DYNAMIC(M,p,B,v) calculates the matrix of alpha's the
% hmm with transition matrix M, emission matrix B, and initial
% probabilities p, given the observations v

    [np, ~]     = size(p);
    [N, ~]      = size(M);
    T           = length(v);
    %initialise alphas
    a           = zeros(N,T);
    % making sure p is a column
    if np == 1
        p = p'; 
    end
    % alpha 1 from initial probability
    a(:,1) = p.*B(:,v(1));
    %subsequent alphas
    for t = 2:T
        a(:,t) = M' * a(:,t-1) .* B(:,v(t));
    end
end

Example

Observations in the sequence:

Output