Implement Viterbi Learning solved by 158

Viterbi learning

Given: A sequence of emitted symbols x = x₁ ... x_n in an alphabet A, generated by a k-state HMM with unknown transition and emission probabilities, initial Transition and Emission matrices and a number of iterations i.

Return: A matrix of transition probabilities Transition and a matrix of emission probabilities Emission that maximizes Pr(x, π) over all possible transition and emission matrices and over all hidden paths π.

Sample Dataset

100
--------
xxxzyzzxxzxyzxzxyxxzyzyzyyyyzzxxxzzxzyzzzxyxzzzxyzzxxxxzzzxyyxzzzzzyzzzxxzzxxxyxyzzyxzxxxyxzyxxyzyxz
--------
x   y   z
--------
A   B
--------
    A   B
A   0.582   0.418
B   0.272   0.728
--------
    x   y   z
A   0.129   0.35    0.52
B   0.422   0.151   0.426

Sample Output

A   B
A   0.875   0.125
B   0.011   0.989
--------
    x   y   z
A   0.0 0.75    0.25
B   0.402   0.174   0.424

Extra Dataset

Click for an extra dataset