2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I believe there is no closed formula from looking into it, but I could be wrong. The prior and transition distributions are multivariate normal (which is nice), however the observation distribution is essentially a neural network with a softmax output layer. As I said, I couldn't find a closed-form expression for the smoothing density, however all the distributions are differentiable and so is the likelihood and log likelihood. $\endgroup$
    – rwolst
    Commented Sep 18, 2018 at 14:22

1 Answer 1

2
$\begingroup$

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})$.

$\endgroup$
3
  • $\begingroup$ Very interestingly, the update equations you gave are the way I've been currently been doing things, although I came about them a slightly different way. The issue is that I believe for my problem the Taylor series approximation may not be very good and the given method compounds this at each time step. This is why I was asking about a continuous optimisation approach to finding the maximum likelihood states. $\endgroup$
    – rwolst
    Commented Sep 18, 2018 at 16:18
  • $\begingroup$ How about drawing the state from a mixture of Gaussian distributions where the weights of the distribution are to be found by minimizing a cost function (perhaps, a LASSO-like cost function, which applies sparsity on the weights). $\endgroup$
    – Maxtron
    Commented Sep 18, 2018 at 22:21
  • $\begingroup$ I'm not sure I entirely understand, do you mean approximating the posterior at each time step by a mixture of Gaussians instead of just a single Gaussian distribution? $\endgroup$
    – rwolst
    Commented Sep 20, 2018 at 10:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.