Clear Filters
Clear Filters

How HMM viterbi algorithm works

19 views (last 30 days)
Nikolas Spiliopoulos
Nikolas Spiliopoulos on 22 Nov 2021
Edited: Aneela on 19 Feb 2024
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

Answers (1)

Aneela
Aneela on 19 Feb 2024
Edited: Aneela on 19 Feb 2024
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

Tags

Products


Release

R2020a

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!