Hidden Markov Models - Viterbi Algorithm

viterbi.py

import numpy as np

def viterbi(mood_sequence, priors, transmission_probs, emission_probs):
    n = len(mood_sequence)
    weather_matrix = np.zeros((n, 2))
    history = [(None,None)]
    for i, mood in enumerate(mood_sequence):
        if i==0:
            weather_matrix[i] = priors['s']*emission_probs['s'+mood], priors['r']*emission_probs['r'+mood]
        else:
            ss, sr, rs, rr = transmission_probs['ss'], transmission_probs['sr'], transmission_probs['rs'], transmission_probs['rr']
            s, r = weather_matrix[i-1]
            S_probs, R_probs = np.array([s*ss, r*rs]), np.array([s*sr, r*rr])
            prev_S = np.argmax(S_probs).item()
            prev_R = np.argmax(R_probs).item()
            prev = "SR"[prev_S], "SR"[prev_R]
            history.append(prev)
            prob_S = S_probs.max() * emission_probs['s'+mood]
            prob_R = R_probs.max() * emission_probs['r'+mood]
            weather_matrix[i] = prob_S, prob_R
    final_prob, previous = weather_matrix[-1].max(), "SR"[weather_matrix[-1].argmax()]
    weather_sequence = [previous]
    for i in range(n-2,-1,-1):
        previous = history[i+1]["SR".index(previous)]
        weather_sequence.insert(0,previous)
    return "Most Probale Sequence is {} with probability {}".format(''.join(weather_sequence) ,  final_prob)

def main():
    priors = {'s': 2/3, 'r': 1/3}
    transmission_probs = {'ss': 8/10, 'sr': 2/10, 'rs': 2/5, 'rr': 3/5}
    emission_probs = {'sh': 8/10, 'sg': 2/10, 'rh': 2/5, 'rg': 3/5}
    print(viterbi('hhgggh', priors, transmission_probs, emission_probs))  
  
if __name__=="__main__":
        main()

HMM Logic for this Sunny(S), Rainy(R), Happy(H), Grumpy(G) program is:
Given: 1. Priors: P(S), P(R) 2. Transmission Probabilities: P(S|S), P(S|R), P(R|S), P(R|R) 3. Emission probabilities: P(H|S), P(G|S), P(H|R), P(G|R)
Also given: Mood Sequence of H,G is given as HHGGGH
Find: Most probable weather sequence of S,R
We will calculate a weather matrix where we calculate scores of S,R for each day:

• For 1st day: S = P(S)*P(H|S), R =P(R)*P(H|R)
• For 2nd day onwards; best_previous_state | S = argmax( S * P(S|S) , R * P(S|R) ) and S = P(best_previous_state)*P(mood| S)
• Similarly; best_previous_state | R = argmax( S * P(R|S) , R * P(R|R) ) and R = P(best_previous_state)*P(mood| R)

After making this table, we need to backtrace the best_previous_state at each step from the end to get the most likely sequence