Implement Viterbi Learning solved by 133

Sept. 16, 2015, 3 a.m. by Rosalind Team

Topics: HMM

Viterbi learning

Given: A sequence of emitted symbols x = x1 ... xn 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

Please login to solve this problem.