Viterbi algorithm

viterby.py

def viterbi(states,observations,stateM,transM,observM,observSeq):
    probab = [{}]
    path = {}

    # Initialize states 
    for s in states:
        # first probability is the initial state times the
        # first observation
        probab[0][s] = stateM[s] * observM[s][observSeq[0]]
        path[s] = [s] # first destination

    # for every observation
    for t in range(1,len(observSeq)):
        
        probab.append({})
        
        #temporary dictionary so we can use and not have to edit path
        temppath = {}

        # compute all possible paths from t-1 to t and store
        # only the best ones
        for s in states:
            # compute forward algorithm (previous state probability * transition probability
            # * probability that the current observation was emitted by that state)
            # and store only the best path + its probability

            p = 0
            state = ""

            for i in states:
                val = probab[t-1][i] * transM[i][s] * observM[s][observSeq[t]]
                if val > p:
                    p = val
                    state = i
                        
            probab[t][s] = p # store probability
            temppath[s] = path[state] + [s] # old path + new move

        path = temppath.copy() # copy back

    # if there is only one observation, the max is simply
    # the first probability
    n = 0 if len(observSeq) <= 1 else t

    # get final state with best probability
    (p,state) = max((probab[n][i],i) for i in states)

    # return its path and its probability
    return (p,path[state])
        
states = ("Sad","Happy")
observations = ("Crying","Laughing","Eating")

stateM = {'Sad': 0.3, 'Happy': 0.7}
transM = {'Sad': {'Sad': 0.3, 'Happy': 0.7}, 'Happy': {'Sad': 0.4, 'Happy': 0.6}}
observM = {'Sad': {'Crying': 0.7, 'Laughing': 0.1, 'Eating': 0.2}, 'Happy': {'Crying': 0.1, 'Laughing': 0.6, 'Eating': 0.3}}

observSeq = ["Laughing","Crying","Eating","Crying"]

print(viterbi(states,observations,stateM,transM,observM,observSeq))