How HMM viterbi algorithm works

Hi al,

I am new in using HMM so I have created a simple example, where a random sequence is generated and then the states are updated through viterbi algorithm (https://www.mathworks.com/help/stats/hmmviterbi.html).

However, from my understanding it seems that viterbi updates the states for a given sequence!

So it means that the sequence remains the same and only the states are updated? If you have any good reference example besides the one on the matlab website, it would b really helpful.

thanks in advance,

Nikolas

Answer 1

[Aneela]

Hi Nikolas Spiliopoulos,

The Viterbi algorithm generates the most likely sequence of the hidden states (Viterbi States) in “HMM (Hidden Markov Models)”.

• The algorithm begins by determining the initial likelihoods for each state, based on the first observation.
• For each subsequent observation, the algorithm calculates the probability of being in each state by using the new observation and the previous state probabilities.
• This is done by using the emission probability of the observed value and the transition probability from the previous state.
• After all observations have been processed, and the final state is reached, it finds the probability of the most likely sequence or the path.
• Finally, using backtracking from the final state, the most likely sequence of the hidden states (Viterbi states) is found.

As a result, only the states (Viterbi states) get updated, the given sequence of the observations remains same.

Here's a reference example.

obs_seq = {'Play','Home','Home','Play','Home','Play','Home'};
[seq, prob] = viterbi(obs_seq);
disp(['Most likely sequence of states: ', strjoin(seq, ' -> ')]);
disp(['Probability of the sequence: ', num2str(prob)]);

function [seq, prob] = viterbi(obs_seq)
    % Define the HMM parameters
    states = {'Rainy', 'Sunny'};
    observations = {'Play', 'Home'};
    
    % Initial probabilities
    pi = [0.6, 0.4];
    
    % Transition probabilities
    A = [0.7, 0.3; 
         0.4, 0.6];
    
    % Emission probabilities
    B = [0.1, 0.9; 
         0.6, 0.4];
    
    % Map each observation to its index
    obs_indices = arrayfun(@(x) find(strcmp(x, observations)), obs_seq);
    
    % Initialization
    len_obs = length(obs_seq);
    num_states = length(states);
    %T1 stores the highest probability of any path that reaches state i 
    T1 = zeros(num_states, len_obs);
    %T2 stores the state that achieved maximum probability in  T1
    T2 = zeros(num_states, len_obs);
    
    % Fill in first column of T1 and T2
    for state = 1:num_states
        T1(state, 1) = pi(state) * B(state, obs_indices(1));
        T2(state, 1) = 0;
    end
    
    % Iterate through the observation sequence
    for t = 2:len_obs
        for s = 1:num_states
            [max_val, max_state] = max(T1(:, t-1) .* A(:, s));
            T1(s, t) = max_val * B(s, obs_indices(t));
            T2(s, t) = max_state;
        end
    end
    
    % Backtracking
    seq = cell(1, len_obs);
    [prob, last_state] = max(T1(:, len_obs));
    seq{len_obs} = states{last_state};
    
    for t = len_obs-1:-1:1
        last_state = T2(last_state, t+1);
        seq{t} = states{last_state};
    end
end