Implementation of Viterbi algorithm in Python

Preface

By default, the reader has understood HMM Related content , Also on viterbi Understand the algorithm .

Prerequisite

It is known that state Is the hidden status list ,observation Is a list of observable states ,T It's a transfer matrix , E Is the emission matrix , PI Is the initial state probability matrix ,O It is the currently known three-day algal humidity sequence （ It's directly used here observation The index of indicates , Which is the corresponding ['Dry', 'Damp', 'Soggy'] ）, Let's find out what happened in these three days O Under the circumstances , The most likely sequence of weather conditions .

state = ['Sunny','Cloud','Rainy']
observation = ['Dry', 'Dryish', 'Damp', 'Soggy']
PI = [0.63,0.17,0.20]
T = [[0.5,0.375,0.125],
[0.25,0.125,0.625],
[0.25,0.375,0.375]]
E = [[0.6,0.2,0.15,0.05],
[0.25,0.25,0.25,0.25],
[0.05,0.10,0.35,0.5]]
O = [0,2,3]
 Copy code 

Algorithm implementation

import numpy as np
def viterbi(T ,E, PI, O):
T = np.array(T)
E = np.array(E)
PI = np.array(PI)
row = T.shape[0]
col = len(O)
F = np.zeros((row, col))
F[:, 0] = PI * np.transpose(E[:, O[0]])
for t in range(1, col):
L_max = []
for i in range(row):
L = F[:, t-1] * np.transpose(T[:, i])
L_max.append(max(L))
F[:, t] = np.array(L_max) * np.transpose(E[:, O[t]])
return F
 Copy code 

The key to the algorithm is , The probability of a certain weather yesterday * The transition probability of a certain weather from yesterday to today * Today is the humidity probability of algae under certain weather conditions , But the above code is to speed up the calculation , They are all changed to matrix operations , But the principle is the same .

The last thing the code returns is （ state Number * O Number ） The result matrix of , We have to go through this matrix , Find out the weather conditions corresponding to the maximum probability in each column , In this way, the sequence composed of the weather found in all the columns is the final result .

Code runs

V = viterbi(T, E, PI, O)
print(V)
# [[ 0.378 0.02835 0.00070875]
# [ 0.0425 0.0354375 0.00265781]
# [ 0.01 0.0165375 0.01107422]]
print([state[np.argmax(row)] for row in np.transpose(V)])
# ['Sunny', 'Cloud', 'Rainy']
 Copy code 

From the results, the most likely weather conditions for these three days are ['Sunny', 'Cloud', 'Rainy']

Reference recommendation

Here is an author who has a detailed calculation process for this classic case of vitbit algorithm , You can refer to it , It is helpful to understand the algorithm and code , I don't make wheels anymore , However, it should be noted that his calculated answer is wrong , Just understand the algorithm process , I can push it myself : blog.csdn.net/jeiwt/artic…