Computational Intelligence, SS08
2 VO 442.070 + 1 RU 708.070 last updated:
Course Notes (Skriptum)
Online Tutorials
Practical Course Slides
Animated Algorithms
Interactive Tests
Key Definitions
Literature and Links

Homework 10: Markov Models

[Points: 10; Issued: 2003/05/23; Deadline: 2003/06/06; Tutor: Christoph Krall; Infohour: 2003/06/04, 13:00-14:00, Seminarraum IGI; Einsichtnahme: 2003/06/25, 13:00-14:00, Seminarraum IGI; Download: pdf; ps.gz]

  • Load the HMM's and make a sketch of each of the models with the transition probabilities. The parameters of the densities and of the Markov models are stored in the file data.mat (Use: load data). A Markov model named, e.g., hmm1 is stored as an object with fields hmm1.means, hmm1.vars, hmm1.trans,hmm1.pi. The means fields contains a matrix of mean vectors, where each column of the matrix corresponds to one state of the HMM (e.g to access the second state from hmm1 use: hmm1.means(:,2); the vars field contains a 3 dimensional array of variance matrices, where the third dimension corresponds to the state (e.g to access $ \Sigma_{/a/}$ from state 1 use hmm1.vars(:,:,1);the trans field contains the transition matrix, and the pi field the prior probabilities. hmm1.
  • Generate samples coming from the HMM's (hmm1, hmm2, hmm3, hmm4) and plot them with plotseq and plotseq2. Use the functions plotseq and plotseq2 to picture the obtained 2-dimensional data. In the resulting views, the obtained sequences are represented by a yellow line where each point is overlaid with a colored dot. The different colors indicate the state from which any particular point has been drawn.

    » %Example:generate sample from HMM1 of length T

    » [X,ST]=sample_ghmm(hmm1,T)

    » plotseq(X,ST) % View of both dimensions as separate sequences

    » plotseq2(X,ST,hmm1) %2D view with location of gaussian states

    Draw several samples with the same parameters and compare. Compare the MATLAB figures with your sketch of the model.

    What is the effect of the different transition matrices of the HMMs on the sequences obtained during the current experiment? Hence, what is the role of the transition probabilities in the HMM?

  • Pattern recognition with HMM's: Classify the sequences $ X_1, X_2, X_3,X_4$, given in the file Xdata.mat, in a maximum likelihood sense with respect to the four Markov models. Use the function loglik_ghmm to compute the likelihood of a sequence with respect to a HMM. Store the results in a matrix (they will be used in the next section).

    » load Xdata

    » % Example:

    » logProb(1,1) = loglik_ghmm(X1,hmm1)

    » logProb(1,2) = loglik_ghmm(X1,hmm2)


    » logProb(3,2) = loglik_ghmm(X3,hmm2)


    Filling the logProb matrix can be done automatically with the help of loops:

    >> for i=1:4,
         for j=1:4,
          stri = num2str(i);
          strj = num2str(j);
        eval([ 'logProb(' , stri , ',' , strj , ')=...
                loglik_ghmm(X' , stri , ',hmm' , strj , ');' ]);
    You can find the maximum value of each row of the matrix with the MATLAB function max:
    for i=1:4;
        disp (['X',num2str(i),' -> HMM',num2str(index)]);
    Sequence $ \log p(X\vert\Theta_1)$ $ \log p(X\vert\Theta_2)$ $ \log p(X\vert\Theta_3)$ $ \log p(X\vert\Theta_4)$ Most likely

  • Write a MATLAB function to implement the Viterbi algorithm for HMM's with gaussian emissions (see Tutorial).
    [loglik ,path] = vit_ghmm(data,HMM)
    % Compute the path and the log likelihood of a given model and
    % observation sequence
    % INPUT
    %      data ... containing a sequence of observation
    %         size(data)=[Number of features of each obs., length of sequence]
    %      HMM is an object of the
    %       HMM.means = MEANS;
    %       HMM.vars = VARS;
    %       HMM.trans = TRANSITIONS;
    %       HMM.pi = PRIORS;
    % OUTPUT
    %       loglik ... log likelihood of the most likely path for the data
    %       path ... most likely path
    Use the function mk_ghmm_obs_lik to calculate the observation likelihood matrix for a given sequence.
  • Use the function vit_ghmm to compute the probabilities of the sequences $ X_1, \cdots X_4$ along the best paths with respect to each model $ \Theta_1, \cdots \Theta_4$. Note your results below. Compare with the log-likelihoods obtained in the previous section with the forward procedure (loglik_ghmm(...)).

    » diffL=logProb-logProbViterbi

    Likelihoods along the best path:

    Sequence $ \log p^*(X\vert\Theta_1)$ $ \log p^*(X\vert\Theta_2)$ $ \log p^*(X\vert\Theta_3)$ $ \log p^*(X\vert\Theta_4)$ Most likely


    Difference between log-likelihoods and likelihoods along the best path:

    Sequence HMM1 HMM2 HMM3 HMM4

    Is the likelihood along the best path a good approximation of the real likelihood of a sequence given a model ?