Michael Brenndoerfer | Data & AI, Private Equity, Technology

Michael Brenndoerfer

Viterbi Algorithm (1967) › The Solution: Dynamic Programming Through Time

Michael BrenndoerferApril 14, 20253 min read

History of Language AIAll chapters

Part 1 of 9Signals & Symbols

Chapter 8Viterbi Algorithm (1967) › The Solution: Dynamic Programming Through Time

Reading section 3 of 11 · The Solution: Dynamic Programming Through Time · 3 minSection 3 of 11 · 3 min

Section 3 of 11 · 3 min read

Viterbi Algorithm (1967) › The Solution: Dynamic Programming Through TimeOne section · Sections in this chapter3 / 11 ↓

Sections in this chapter11

Reading tools Definitions & inline links

Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.

Article links

Make inline references clickable

The Viterbi algorithm solves the sequence decoding problem using dynamic programming, a technique that builds up solutions to complex problems by combining solutions to simpler subproblems. Instead of considering all possible sequences simultaneously, the algorithm processes the observations sequentially, maintaining for each state at each time step the probability of the most likely path ending in that state, along with a pointer to the previous state in that optimal path.

Formally, if we let $v_t(j)$ represent the probability of the most likely sequence of states ending in state $j$ at time $t$ , the algorithm computes these values recursively. To compute $v_t(j)$ , we consider all possible previous states $i$ and find which transition maximizes the combined probability:

v_t(j) = \max_i [v_{t-1}(i) \times a_{ij} \times b_j(o_t)]

where $a_{ij}$ is the transition probability from state $i$ to state $j$ , and $b_j(o_t)$ is the probability of observing $o_t$ given that we're in state $j$ . The algorithm also maintains backpointers $\text{ptr}_t(j)$ that record which previous state $i$ achieved this maximum, allowing reconstruction of the optimal sequence once all observations have been processed.

The algorithm begins by initializing $v_1(j)$ for all states $j$ using the initial state probabilities and the first observation's emission probabilities. Then it iterates forward through time, computing $v_t(j)$ for all states at each time step. After processing all observations, it finds the state $j^*$ that maximizes $v_T(j)$ and uses the backpointers to trace backwards through time, reconstructing the optimal state sequence.

The Efficiency Gain

The key efficiency of the Viterbi algorithm comes from pruning. At each time step, for each state, we keep only the single best path leading to that state. All other paths are discarded because they cannot become optimal later. This pruning reduces the computational complexity from $O(N^T)$ (exponential) to $O(T \times N^2)$ (polynomial). For $N = 50$ states and $T = 20$ observations, this reduces the computation from $50^{20}$ to approximately $20,000$ operations.a reduction by a factor of roughly $10^{29}$ .

The algorithm's correctness relies on the optimal substructure property: if the optimal sequence passes through state $j$ at time $t$ , then the optimal path from the start to state $j$ at time $t$ is part of the globally optimal sequence. This means we can safely discard all non-optimal paths to state $j$ at time $t$ , confident that they cannot contribute to an optimal solution. This property holds because of the Markov assumption.future states depend only on the current state, not on the path taken to reach it.