- 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.
How HMM viterbi algorithm works
11 views (last 30 days)
Show older comments
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
0 Comments
Answers (1)
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)”.
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
0 Comments
See Also
Categories
Find more on Error Detection and Correction in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!