Skip to content

Instantly share code, notes, and snippets.

satomacoto/viterbi.py Last active Apr 28, 2019

 #!/usr/bin/env python # -*- coding:utf-8 -*- # Viterbi algorithm # http://en.wikipedia.org/wiki/Viterbi_algorithm # # > python viterbi.py # 0 1 2 # Rainy: 0.06000 0.03840 0.01344 # Sunny: 0.24000 0.04320 0.00259 # (0.01344, ['Sunny', 'Rainy', 'Rainy']) # HMM states = ('Rainy', 'Sunny') observations = ['walk', 'shop', 'clean'] start_probability = {'Rainy': 0.6, 'Sunny': 0.4} transition_probability = { 'Rainy' : {'Rainy': 0.7, 'Sunny': 0.3}, 'Sunny' : {'Rainy': 0.4, 'Sunny': 0.6}, } emission_probability = { 'Rainy' : {'walk': 0.1, 'shop': 0.4, 'clean': 0.5}, 'Sunny' : {'walk': 0.6, 'shop': 0.3, 'clean': 0.1}, } # Helps visualize the steps of Viterbi. def print_dptable(V): print " ", for i in range(len(V)): print "%7d" % i, print for y in V[0].keys(): print "%.5s: " % y, for t in range(len(V)): print "%.7s" % ("%f" % V[t][y]), print def viterbi(obs, states, start_p, trans_p, emit_p): V = [{}] path = {} # Initialize base cases (t == 0) for y in states: V[0][y] = start_p[y] * emit_p[y][obs[0]] path[y] = [y] # Run Viterbi for t > 0 for t in range(1,len(obs)): V.append({}) newpath = {} for y in states: (prob, state) = max([(V[t-1][y0] * trans_p[y0][y] * emit_p[y][obs[t]], y0) for y0 in states]) V[t][y] = prob newpath[y] = path[state] + [y] # Don't need to remember the old paths path = newpath print_dptable(V) (prob, state) = max([(V[len(obs) - 1][y], y) for y in states]) return (prob, path[state]) print viterbi(observations, states, start_probability, transition_probability, emission_probability)
to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.