dm.cs.tu-dortmund.de/mlbits/sequential-models-hmm-algorithms/
Algorithms for HMM – Lecture Notes
77, 2 (1989), 257–286. DOI: 10.1109/5.18626
[Vite67]
Viterbi, A.J. 1967. Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. IEEE Trans. Information Theory . 13, 2 (1967) [...] =(A^*, B^*, \pi^*)\)
Beam Search: Approximating Viterbi
The runtime complexity of Viterbi is \(O(|S|^2{\cdot}T)\) (number of states \(\times\) number of steps).
If we have many states, this becomes very …
