Finding maximum likelihood solution of a continuous state HMM

Question

The likelihood of a hidden Markov model (HMM) for states $x_0, \dots, x_N$ and observations $y_1, \dots, y_N$ can be written as

$$ L = f(x_0) \prod_{i=1}^N f(y_i | x_i) f(x_i | x_{i-1} )$$

where we use $f(\cdot)$ to represent a pdf.

If the states $x_0, \dots, x_N$ can only take values from a discrete set, then we can find the most likely sequence of states using the Viterbi algorithm.

My question is then, what is this the best way to go about the optimisation in the continuous case?

Note

If the states take values on a continuous set, then we could use gradient descent for example to try to estimate the most likely sequence of states.

However if $N$ is very large, it could take a long time to calculate the gradient of $L$. We may be able to perform stochastic gradient descent but I feel we would not want to re-order the observations $i$, as you would between batches of standard gradient descent. Therefore I am unsure how well this would work.

Answer 1

One approach is to make an assumption that your states, i.e., $x_i$ evolve from a Gaussian distribution. For example, \begin{align} x_{i} = F x_{i-1} + e_i \end{align} where $e_i \sim \mathcal{N}(0,Q)$ and $Q$ is a known covariance matrix. Since $x_i$ takes only discrete set, you can make an assumption that the entries of the covariance matrix $Q$ are very small (of the magnitude 1e-12). This implies that $f(x_i|x_{i-1})$ follows a Gaussian distribution. Now, we can write one-step prediction density as \begin{align} x_{i|i-1} &= F x_{i-1|i-1} \\ P_{i|i-1} &= F P_{i-1|i-1} F^T + Q \end{align} where $x_{i|i-1}$ and $P_{i|i-1}$ are the mean and covariance of the prediction density. If you know the likelihood expression of $f(y_i|x_i)$, i.e., $L(x_i|y_i)$, expand it using Taylor series expansion about a point $\hat{x}_i$. For example, \begin{align} L(x_i|y_i) &\approx L(\hat{x}_i|y_i) + L'(\hat{x}_i|y_i)(x_i - \hat{x}_i) + \frac{1}{2} (x_i - \hat{x}_i)^T L''(\hat{x}_i|y_i) (x_i - \hat{x}_i) \\ &= \frac{1}{2}[x_i - \{ \hat{x}_i - (L''(\hat{x}_i|y_i))^{-1}L'(\hat{x}_i|y_i) \}]^T L''(\hat{x}_i|y_i) [x_i - \{ \hat{x}_i - (L''(\hat{x}_i|y_i))^{-1}L'(\hat{x}_i|y_i) \}] \end{align} Therefore, the expression takes the form of a Gaussian distribution where the mean and variance of the posterior density are given as \begin{align} x_{i|i} &= \{ \hat{x}_i - (L''(\hat{x}_i|y_i))^{-1}L'(\hat{x}_i|y_i) \} \\ P_{i|i} &= [L''(\hat{x}_i|y_i)]^{-1} \end{align} Note that in the above formulation we make an assumption that the Hessian is always invertible. The point $\hat{x}_i$ is generally the mean value of the distribution $f(x_i|x_{i-1})$.