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 32: Viterbi Decoder for the Graz Weather Model



[Points: 8; Issued: 2005/06/03; Deadline: 2005/06/22; Tutor: Pham Van Tuan; Infohour: 2005/06/21, 12:00-13:00, HS i11; Einsichtnahme: 2005/06/28, 12:00-13:00, HS i11; Download: pdf; ps.gz]





Each team should send the matlab code of the viterbi function for generating the results to the tutor (v.t.pham@tugraz.at) with the subject CI. Please provide the Name and Matrikelnummer of each team member in the scripts and in the body of the email.

  • Make an ``umbrella sequence'' of length $ 5$ using the MATLAB commands
        >> rand('state',YOUR_MATRIKELNUMMER);
        >> x = 0.5+0.5*sign(rand(5,1)-0.5);
    
    Take the numbers in vector x as time sequence according to $ x_n = 0$ for ``no umbrella'' at day $ n$, and $ x_n = 1$ for ``umbrella'' at day $ n$.
  • Manually find the most likely ``weather sequence'' for the five days based on the HMM weather model in the tutorial Hidden Markov Models:
    $\displaystyle A$ $\displaystyle = \left( \begin{array}{ccc} 0.8 & 0.05 & 0.15 \\ 0.2 & 0.6 & 0.2 \\ 0.2 & 0.3 & 0.5 \\ \end{array} \right),$    
    $\displaystyle B$ $\displaystyle = \left( \begin{array}{cc} 0.9 & 0.1 \\ 0.2 & 0.8 \\ 0.7 & 0.3 \\ \end{array} \right),$   and    
    $\displaystyle \mathbf{\pi}$ $\displaystyle = \left( 1/3, 1/3, 1/3 \right)^{\mathsf{T}},$    


    using the Viterbi algorithm.

    Present your Viterbi decoding of the weather sequence graphically, using trellis plots as figs. 5-7 in the HMM tutorial. State the values for the variables $ \psi_n(i)$ and $ \delta_n(i)$ used in the Viterbi algorithm for $ 1\langle i \langle 3$ and $ 1\langle n\langle 5$.

  • Write a MATLAB function for the Viterbi decoding of the weather sequence from your umbrella sequence. This Viterbi decoder is for discrete emission probabilities (``no umbrella'' or ``umbrella''). You may relate to the Viterbi decoder function (with continuous emission probabilities) requested in homework ``Hidden Markov Models''.

    Verify your result for the most likely weather sequence found above.