Skip to content

Instantly share code, notes, and snippets.

@nkt1546789
Last active March 18, 2017 10:56
Show Gist options
  • Save nkt1546789/fa238a168c2c2f84babce71f9f5d5ccd to your computer and use it in GitHub Desktop.
Save nkt1546789/fa238a168c2c2f84babce71f9f5d5ccd to your computer and use it in GitHub Desktop.
Viterbi algorithm on Python.
def viterbi(P, A):
"""
P: log probability matrix (n_samples by n_states)
A: log transition probability matrix (n_states by n_states)
"""
n_samples = P.shape[0]
states = np.arange(P.shape[1])
V = np.zeros((n_samples, 2))
S = np.zeros((n_samples, 2), dtype=int)
V[0] = P[0]
for t in range(1, n_samples):
values = V[t-1] + A
S[t-1] = np.argmax(values, axis=1)
V[t] = P[t] + np.max(values, axis=1)
y = np.zeros(n_samples, dtype=int)
y[-1] = V[-1].argmax()
for t in range(2, n_samples+1):
y[-t] = S[-t, y[-t+1]]
return y
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment