HMCM vs Viterbi algorithm for calculating most likely path of an HMM My expertise in machine learning and statistics is probably at a sophomore level. But anyway, my question is this:
Given a Hidden Markov Model returned over a sequence of events with some states, how do you find the most likely path over the states given only the information to create this HMM?
There are 2 things I've learned about in my research: the Viterbi Algorithm and Markov Chain Monte Carlo. As far as I can tell, the Viterbi algorithm is an analytical approach applying some math over the transition matrix of the HMM to find the most likely sequence of future states. And a MCMC is an empirical approach using a stochastic method over the transition matrix to find the most likely path over the states.
I'm wondering if the previous paragraph I wrote is correct. And, if paragraph is correct, in what situations would I use one method over the other?
 A: Given an HMM $(X_i, Y_i)$ where $X_i$ are the hidden states and $Y_i$ are the observables, the Viterbi algorithm finds the most likely sequence of hidden states $X_{1:n}$ given the sequence of observables $Y_{1:n}$, namely it finds the sequence $X_{1:n}$ which maximizes the conditional distribution $P(\{X_i\}|\{Y_i\}, \theta)$ where $\theta$ is the set of parameters defining the model. In particular, the Viterbi algorithm provides a pointwise estimate in that it requires knowledge of the model parameters $\theta$ (usually estimated from the data as ${\hat \theta}$, for example using the EM algorithm, or Baum-Welch for HMM) and in that it provides a single best estimate for the most likely state rather some posterior distribution. The Viterbi algorithm is fast because the full joint probability distribution of an HMM factorized into a tree structure, therefore the maximization problem can be cast in an efficient dynamic programming form comprising two phases:


*

*a forward pass, maximizing the forward probabilities $P(X_{1:i}, Y_{1:i}|\theta)$ and keeping track of the maximizing states for all possible paths;

*a backward tracking pass, reconstructing the maximizing sequence of states tracing back from $n$ to $1$.


MCMC offers a machinery to move away from a pointwise estimate (frequentist) approach as given above and make inference in an HMM in a Bayesian way, providing instead estimates for for the posterior distributions of all variables in the model, including the set of parameter $\theta$. Typically this is done by introducing priors and defining conditional probabilities for all parameters, and then running a Gibbs sampler.
Details can be easily found around the web, see for example this nice tutorial from Rabiner and this recent article from Rydén comparing EM and MCMC approaches for HMM.
