The greedy per-step choice is not the best path: a state that looks
good now can be unreachable from what follows. Viterbi carries, for
every state, the best path ending there, collapsing an exponential
search to O(T K^2). Log space, because a product of a thousand
probabilities underflows before the path is decided.
Usage
Viterb(obs, trans, emit, init = NULL)
Arguments
- obs
Zero-based observation symbols.
- trans
Transition probabilities.
- emit
Emission probabilities.
- init
Initial state distribution; uniform by default.
Value
List with path, estimate, T, K.
Details
Formula:
delta_t(j) = max_i [delta_{t-1}(i) + log A_ij] + log B_j(o_t).
References
Viterbi, A. J. (1967). IEEE Trans Inform Theory
13:260-269.
Examples
trans <- matrix(c(0.7, 0.3, 0.4, 0.6), 2, byrow = TRUE)
emit <- matrix(c(0.9, 0.1, 0.2, 0.8), 2, byrow = TRUE)
Viterb(obs = c(0, 0, 1, 1, 0), trans = trans, emit = emit)$path
#> [1] 0 0 1 1 0
