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
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 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 , 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).

» % 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 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 along the best paths with respect to each model . 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 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 ?