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
