The viterbi model can be bidirectional.
For example, the tagger can be run twice, once left-to-right and once right-to-left. In Viterbi decoding, the labeler would choose the higher scoring of the two sequences.


University of Colorado at Boulder

The Viterbi algorithm first sets up a probability matrix, with one column for each observation $o_t$ and one row for each state in the state graph. Each column thus has a cell for each state $q_i$ in the single combined automaton. Each cell of the matrix is given by:
$$v_t(j) = \max_{q_1, ..., q_{t-1}} P(q_1...q{t-1}, o_1, ..., o_t, q_t = j|\lambda)$$

For a given state $q_j$ at time $t$, we compute the value $v_t(j)$ as:
$$v_t(j) = \max_{i=1}^N v_{t-1}(i)a_{ij}b_j(o_t)$$
where:
- $v_{t-1}(i)$ is the previous Viterbi path probability from the previous time step
- $a_{ij}$ is transition probability from previous state $q_i$ to current state $q_j$
- $b_j(o_t)$ is the state observation likelihood of the observation symbol $o_t$ given the current state $j$

Details of the Viterbi Algorithm

An on-going but a helpful book resource about NLP
https://web.stanford.edu/~jurafsky/slp3/

Learn Before

Related