This table lists the ai j probabilities for transitioning between the hidden states (part-of-speech tags)

example

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

This mathematical expression defines a function, denoted as $$F$$, whose behavior is determined by a set of parameters, specifically $$\omega$$ and $$\hat{\theta}$$. The subscript parameters modify the function's output. The hat symbol (^) over $$\theta$$ typically indicates that it is an estimated parameter, likely derived from data. The notation $$(\cdot)$$ serves as a placeholder for the function's input argument.

Parameterized Function $$F_{\omega, \hat{\theta}}(\cdot)$$

The Viterbi algorithm is a probabilistic extension of minimum edit distance. It computes the maximum probability alignment of two strings instead of minimum edit distance.

University of Michigan - Ann Arbor

Dynamic programming is an algorithm technique that recursively solves subproblems of a problem and finds the optimal solution from the optimal solution of the subproblems. Some of the algorithms in NLP uses dynamic programming, such as the Viterbi algorithm, CKY algorithm for parsing, and the Minimum Edit Distance Algorithm. 

Dynamic Programming

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

Speech and Language Processing (3rd ed. draft) 

- The minimum edit distance can be computed by using dynamic programming in which the shortest path is stored every time we found it. 
- First, we define the minimum edit distance between two strings $X$ and $Y$ with lengths of n and m respectively. $D[i, j]$ would be defined as the edit distance between $X[1..i]$ and $Y[1..j]$. Then we get that $D[n, m]$ is the edit distance between $X$ and $Y$.

The Minimum Edit Distance Algorithm

2 steps to compute the alignment path:
- The backpointers are stored in each cell by augmenting the minimum edit distance algorithm.
- A backtrace is performed from the last cell to where the pointers are pointing to through the dynamic programming matrix.

Learn Before

Related

Learn After