Viterbi algorithm

The Viterbi algorithm uses dynamic programming to find the most likely sequence of hidden states or transmitted symbols in a sequence model or trellis.

Dynamic programming: A method for solving problems by combining solutions to overlapping subproblems. Viterbi reuses the best partial path ending in each state instead of enumerating every complete path.
Hidden Markov model: A probabilistic sequence model with hidden states, observed outputs, and state-dependent transition and emission probabilities. The algorithm is a standard way to find the most probable hidden-state path in this model.
Convolutional code: An error-correcting code that represents input bits through a stateful sequence of overlapping computations. Its encoder's trellis lets Viterbi decoding recover likely input bits from noisy code symbols.
Forward algorithm: A dynamic-programming algorithm that sums the probabilities of all paths ending in each state. Unlike Viterbi's maximum, it computes total sequence likelihood by adding competing paths.
Trellis: A layered graph whose nodes represent states at successive time steps and whose edges represent allowed transitions. The algorithm searches this graph for the highest-scoring path.
Markov property: The property that a process's next state depends on its present state rather than its full history. This limited dependence makes the best partial path sufficient to extend at each step.
Speech recognition: The computational identification of spoken words from an audio signal. Hidden-state sequence models have used Viterbi search to align acoustic observations with word or phoneme paths.
Forward-backward algorithm: An algorithm that computes posterior probabilities for hidden states at each sequence position. It yields statewise uncertainty, while Viterbi returns one globally most likely sequence.
Bellman equation: A recursive equation expressing an optimal value in terms of immediate outcomes and optimal future values. The Viterbi recurrence is a max-product form of this optimal-substructure principle.
Transition probability: The probability of moving from one state to another in a stochastic process. Transition probabilities contribute a score whenever a candidate path changes states.

Linked from 2 pages

Dijkstra's algorithmCompared with: It uses related path-minimization ideas but optimizes probabilities over state sequences.