Computational Intelligence, SS08
2 VO 442.070 + 1 RU 708.070 last updated:
General
Course Notes (Skriptum)
Online Tutorials
Practical Course Slides
Homework
Assignments
Scores
Guidelines
Archive
Exams
Animated Algorithms
Interactive Tests
Key Definitions
Downloads
Literature and Links
News
mailto:webmaster

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)

    etc.

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

    etc.



    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 , ');' ]);
      end;
    end;
    
    You can find the maximum value of each row of the matrix with the MATLAB function max:
    for i=1:4;
        [v,index]=max(logProb(i,:));
        disp (['X',num2str(i),' -> HMM',num2str(index)]);
    end
    
    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

    model
    X1          
    X2          
    X3          
    X4          
  • 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

    model
    X1          
    X2          
    X3          
    X4          



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



    Sequence HMM1 HMM2 HMM3 HMM4
    X1        
    X2        
    X3        
    X4        

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