SignalTrace

Viterbi Decoding

John Montgomery4 min read

Viterbi Decoding

The Viterbi algorithm answers the decoding question for a Hidden Markov Model: given a fitted model and an observation sequence, what single sequence of hidden states most probably generated it? It is a dynamic-programming algorithm — proposed by Andrew Viterbi in 1967 to decode convolutional codes over noisy communication links, and since independently rediscovered several times — that builds the answer one observation at a time. At each time step it stores, for every state, the probability of the most probable path ending in that state, together with a back-pointer to the predecessor state on that path. Once the whole sequence is processed, it selects the highest-probability final state and follows the back-pointers in reverse to recover the full path, the “Viterbi path”. It runs in O(T·N²) time — linear in the sequence length T and quadratic in the number of states N — which makes it tractable where brute-force enumeration of all Nᵀ candidate paths is not. In the standard taxonomy (codified in Rabiner’s 1989 HMM tutorial) it is the second of the three canonical HMM problems, distinct from likelihood evaluation (the forward algorithm) and from learning (Baum-Welch Estimation).

As an algorithm Viterbi decoding is exact, deterministic and uncontroversial: given the model, it provably returns the joint-most-probable state path. Like Baum-Welch, it is a solved piece of statistics, and any concern about a regime signal it produces traces back to the model it was handed — which in turn traces to the data — rather than to the decoding step.

The decoding choice that matters for trading is Viterbi versus smoothing (posterior decoding). Smoothing reports, for each date independently, the marginal probability of each state; the date-by-date most-likely states it produces need not form the most probable joint path, and they tend to flicker. Viterbi instead commits to one globally coherent path. This distinction is not cosmetic for a trading system: every regime switch in the decoded sequence is a trade, and every trade pays costs. Bulla et al. 2010 make exactly this point in their five-index Markov-switching study — they Viterbi-decode the most probable state path to forecast the next-day regime, and they note that Viterbi paths produce materially fewer regime switches than smoothing while estimating almost identical conditional variances. Fewer switches mean lower turnover and lower transaction costs, which is decisive for a strategy whose after-cost edge is thin; Bulla et al. additionally apply a median filter on top to suppress the residual short-lived flips. Viterbi decoding therefore appears in this vault as the standard, turnover-aware step that converts a fitted HMM into a tradeable regime signal.

The caveats are, again, properties of the inputs, not of the algorithm. A Viterbi path is only as good as the HMM it decodes: if the model is mis-estimated (HMM Parameter Instability) or the regimes are not genuinely persistent and separable, Viterbi will still return a confident, internally consistent path — it just will not be a path that corresponds to anything tradeable. The algorithm also decodes the whole sequence at once; a live trading system must instead decode incrementally, and Bulla et al. note that regime misclassification rises to roughly 10% at the start and end of each rolling estimation window, precisely where the path has the least future information to lean on. Viterbi decoding is reliable; whether its output is alpha depends entirely on the regime structure and estimation quality of the model upstream of it.

Viterbi Decoding [defines] Hidden Markov Model Regime Detection Baum-Welch Estimation [precedes] Viterbi Decoding Viterbi Decoding [supports] Bulla et al. 2010 Viterbi Decoding [relates] Median Filter Smoothing

Connections

Sources

Graph View

Backlinks