5
$\begingroup$

I am reading up on Hidden Markov Models (HMMs) for my research and would like to know if it is applicable to the problem I wish to tackle.

My problem is to detect/estimate the next value of a sequence of observations that comes from a finite alphabet. I think I can model the observations as coming from an HMM, as in I believe it is possible to devise a Markov chain where the probability distribution of the observation is only dependent on the current state and at each state a new observation is derived.

Now, supposing I formulate such an HMM, is it now possible to make use of the tools available for HMMs to predict the next observation or is it only useful to predict the next (hidden) state?

$\endgroup$

2 Answers 2

3
$\begingroup$

A HMM is usually comprised of a transition model $p(z_i|z_{i-1})$ and an observation model $p(x_i|z_i)$. It should be fairly easy to take the predictive distribution for hidden state $z_i$ and feed it through the observation model to get a distribution for the observation $x_i$.

For example, if $z_i$ were discrete and you'd found yourself a distribution $p(z_i)$ over the $i$th hidden variable, the $i$th observation would be distributed as

$$p(x_i) = \sum_k p(x_i|z_i = k )p(z_i = k)$$

This is called marginalization.

$\endgroup$
2
  • $\begingroup$ Hi, thanks for the information. Can you elaborate as to how one can obtain the distribution $p(z_i)$? Is it possible to use available techniques in HMMs to get that? $\endgroup$ Commented Feb 9, 2015 at 23:21
  • $\begingroup$ If you've got observations $x_1, \dotsc, x_n$ and you want to figure out $p(z_i|x_1, \dotsc, x_n)$, you want the forward-backward algorithm. If you want to figure out $p(z_i|x_1, \dotsc, x_i)$, you want the forward algorithm. Finally, if you want to deduce the parameters as well as the hidden states, you (probably) want the Baum-Welch algorithm. $\endgroup$
    – Andy Jones
    Commented Feb 10, 2015 at 20:24
0
$\begingroup$

Suppose you want to predict the observation at time $T$: $O_T$, from $o_1,\dots,o_{T-1}$. Further suppose that the observation is discrete (You may readily generalize to continuous case if you'd like). You'd have two options.

  • Option I: pick the point estimation $o_T = \arg\max_o P(O_T=o \mid o_1,\dots,o_{T-1})$.
  • Option II: estimate the prediction with the conditional expectation: $\mathbb E[O_T \mid o_1,\dots,o_{T-1}]$.

Point estimation

$$ \begin{aligned} o_T &= \arg\max_o P(O_T=o \mid o_1,\dots,o_{T-1})\\ &= \arg\max_o \frac{P(o_1,\dots,o_{T-1}, O_T=o)}{P(o_1,\dots,o_{T-1})}\\ &= \arg\max_o P(o_1,\dots,o_{T-1}, O_T=o) \end{aligned} $$

To compute the the likelihood $P(o_1,\dots,o_{T-1},O_T=o)$, you'll need to use forward variable $\alpha_j^t = \sum_i \alpha_i^{t-1} a_{ij} b_j(o_t)$ (see forward-backward algorithm mentioned by @Andy Jones) where $a_{ij}$ is the transition probability from state $i$ to state $j$, and $b_j(o_t)$ is the emission probability of $o_t$ from state $j$. And $P(o_1,\dots,o_{T-1},O_T=o) = \sum_i \alpha_i^T$ with $O_T=o$ plugged in.

Conditional expectation

$$ \begin{aligned} \mathbb E[O_T \mid o_1,\dots,o_{T-1}] &= \sum_o o P(O_T=o \mid o_1,\dots,o_{T-1})\\ &= \frac{\sum_o o P(o_1,\dots,o_{T-1},O_T=o)}{P(o_1,\dots,o_{T-1})}\\ \end{aligned} $$

Then you'll need to use the forward variables mentioned above to compute the likelihoods in the numerator and the denominator.


EDIT:

It's worthy to mention that you may want to compute the log likelihood rather than the likelihood directly, as it may underflow when $T$ is large.

$\endgroup$

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.