",b_df)b = b_df.
valuesWe get:Simulated Observations: Obs_code Obs_seq0 1 Hot1 1 Hot2 0 Cold3 1 Hot4 0 Cold5 0 Cold6 1 Hot7 0 Cold8 1 Hot9 1 Hot10 0 Cold11 0 Cold12 0 Cold13 1 Hot HMM matrix: Snow Rain SunshineSnow 0.
3 0.
3 0.
4Rain 0.
1 0.
45 0.
45Sunshine 0.
2 0.
3 0.
5 Observable layer matrix: Cold HotSnow 0 1Rain 0.
2 0.
8Sunshine 0.
7 0.
3Now let’s use the algorithm:path, delta, phi = viterbi(pi, a, b, obs)state_map = {0:'Snow', 1:'Rain', 2:'Sunshine'}state_path = [state_map[v] for v in path]pd.
DataFrame().
assign(Observation=obs_seq).
assign(Best_Path=state_path)We get:Start Walk Forwards=0 and t=1: phi[0, 1] = 2.
0s=1 and t=1: phi[1, 1] = 1.
0s=2 and t=1: phi[2, 1] = 2.
0s=0 and t=2: phi[0, 2] = 0.
0s=1 and t=2: phi[1, 2] = 1.
0s=2 and t=2: phi[2, 2] = 1.
0s=0 and t=3: phi[0, 3] = 2.
0s=1 and t=3: phi[1, 3] = 2.
0s=2 and t=3: phi[2, 3] = 2.
0s=0 and t=4: phi[0, 4] = 0.
0s=1 and t=4: phi[1, 4] = 1.
0s=2 and t=4: phi[2, 4] = 1.
0s=0 and t=5: phi[0, 5] = 2.
0s=1 and t=5: phi[1, 5] = 2.
0s=2 and t=5: phi[2, 5] = 2.
0s=0 and t=6: phi[0, 6] = 2.
0s=1 and t=6: phi[1, 6] = 2.
0s=2 and t=6: phi[2, 6] = 2.
0s=0 and t=7: phi[0, 7] = 0.
0s=1 and t=7: phi[1, 7] = 1.
0s=2 and t=7: phi[2, 7] = 1.
0s=0 and t=8: phi[0, 8] = 2.
0s=1 and t=8: phi[1, 8] = 2.
0s=2 and t=8: phi[2, 8] = 2.
0s=0 and t=9: phi[0, 9] = 0.
0s=1 and t=9: phi[1, 9] = 1.
0s=2 and t=9: phi[2, 9] = 1.
0s=0 and t=10: phi[0, 10] = 0.
0s=1 and t=10: phi[1, 10] = 1.
0s=2 and t=10: phi[2, 10] = 1.
0s=0 and t=11: phi[0, 11] = 2.
0s=1 and t=11: phi[1, 11] = 2.
0s=2 and t=11: phi[2, 11] = 2.
0s=0 and t=12: phi[0, 12] = 2.
0s=1 and t=12: phi[1, 12] = 2.
0s=2 and t=12: phi[2, 12] = 2.
0s=0 and t=13: phi[0, 13] = 2.
0s=1 and t=13: phi[1, 13] = 2.
0s=2 and t=13: phi[2, 13] = 2.
0————————————————–Start Backtracepath[12] = 2path[11] = 2path[10] = 2path[9] = 1path[8] = 1path[7] = 2path[6] = 1path[5] = 2path[4] = 2path[3] = 1path[2] = 2path[1] = 1path[0] = 1Which leads to the output:We used the following implementation, based on [2]:def viterbi(pi, a, b, obs): nStates = np.
shape(b)[0] T = np.
shape(obs)[0] # init blank path path = path = np.
zeros(T,dtype=int) # delta –> highest probability of any path that reaches state i delta = np.
zeros((nStates, T)) # phi –> argmax by time step for each state phi = np.
zeros((nStates, T)) # init delta and phi delta[:, 0] = pi * b[:, obs[0]] phi[:, 0] = 0 print('.Start Walk Forward.') # the forward algorithm extension for t in range(1, T): for s in range(nStates): delta[s, t] = np.
max(delta[:, t-1] * a[:, s]) * b[s, obs[t]] phi[s, t] = np.
argmax(delta[:, t-1] * a[:, s]) print('s={s} and t={t}: phi[{s}, {t}] = {phi}'.
format(s=s, t=t, phi=phi[s, t])) # find optimal path print('-'*50) print('Start Backtrace.') path[T-1] = np.
argmax(delta[:, T-1]) for t in range(T-2, -1, -1): path[t] = phi[path[t+1], [t+1]] print('path[{}] = {}'.
format(t, path[t])) return path, delta, phiLearning and the Baum-Welch AlgorithmA similar approach to the one above can be used for parameter learning of the HMM model.
We have some dataset, and we want to find the parameters which fit the HMM model best.
The Baum-Welch Algorithm is an iterative process which finds a (local) maximum of the probability of the observations P(O|M), where M denotes the model (with the parameters we want to fit).
Since we know P(M|O) by the model, we can use a Bayesian approach to find P(M|O) and converge to an optimum.
HMM have various applications, from character recognition to financial forecasts (detecting regimes in markets).
References[1] https://cse.
buffalo.
edu/~jcorso/t/CSE555/files/lecture_hmm.
pdf[2] http://www.
blackarbs.
com/blog/introduction-hidden-markov-models-python-networkx-sklearn/2/9/2017.