An implementation of the Viterbi algorithm for HMM in Python can be as short as 10 lines of code like this:

def Decode(self, obs):
trellis = np.zeros((self.N, len(obs)))
backpt = np.ones((self.N, len(obs)), 'int32') * -1
trellis[:, 0] = np.squeeze(self.initialProb * self.Obs(obs[0]))
for t in xrange(1, len(obs)):
trellis[:, t] = (trellis[:, t-1, None].dot(self.Obs(obs[t]).T) * self.transProb).max(0)
backpt[:, t] = (np.tile(trellis[:, t-1, None], [1, self.N]) * self.transProb).argmax(0)
tokens = [trellis[:, -1].argmax()]
for i in xrange(len(obs)-1, 0, -1):
tokens.append(backpt[tokens[-1], i])
return tokens[::-1]

This is the implementation of Viterbi I’ve completed recently. Holy python, how sweet it is! The code is even shorter than the pseudo-code, which is taken from this book.

It takes no more than 30 lines for the complete class:

import numpy as np
class Decoder(object):
def __init__(self, initialProb, transProb, obsProb):
self.N = initialProb.shape[0]
self.initialProb = initialProb
self.transProb = transProb
self.obsProb = obsProb
assert self.initialProb.shape == (self.N, 1)
assert self.transProb.shape == (self.N, self.N)
assert self.obsProb.shape[0] == self.N
def Obs(self, obs):
return self.obsProb[:, obs, None]
def Decode(self, obs):
trellis = np.zeros((self.N, len(obs)))
backpt = np.ones((self.N, len(obs)), 'int32') * -1
# initialization
trellis[:, 0] = np.squeeze(self.initialProb * self.Obs(obs[0]))
for t in xrange(1, len(obs)):
trellis[:, t] = (trellis[:, t-1, None].dot(self.Obs(obs[t]).T) * self.transProb).max(0)
backpt[:, t] = (np.tile(trellis[:, t-1, None], [1, self.N]) * self.transProb).argmax(0)
# termination
tokens = [trellis[:, -1].argmax()]
for i in xrange(len(obs)-1, 0, -1):
tokens.append(backpt[tokens[-1], i])
return tokens[::-1]

The full source code and a simple test case, as always, can be found on github.

### Like this:

Like Loading...

*Related*

I don’t know you but i love you already for this beautiful code. Although i didn’t fully understand it but replicating and running the code made my evening. Thank you. do you have any other resources that could help me understand it better or perhaps some other source code that will be great for me to lay my hands on?

Thank you, I am glad you find it useful 🙂

I think the book mentioned above explains it very well. You might also find some other lectures on the web explaining this, unfortunately I don’t have any handy source.

I also find this explanation to be quite intuitive: http://www.cs.toronto.edu/~sengels/tutorials/viterbi.html

well i am unable to implement it. can you please help me out

please explain by giving a example

Good implementation. Can you please describe the parameters in more detail. Particularly the obs parameter. What is it’s type and are the observations raw observations or matrices from an HMM model. Please let me know. This will help me implement the algorithm much more smoothly.