6
$\begingroup$

I have a sequence of observations e.g. ["Click","Scroll","Hover","Zoom","Select"]. I need to predict the next value of this observation sequence but not the next hidden state.

I know that there are three fundamental problems for HMMs: a)Given the model parameters and observed data, we can estimate the optimal sequence of hidden states. b)Given the model parameters and observed data, we can calculate the likelihood of the data. c)Given just the observed data, we can estimate the model parameters.

So, for solutions to my kind of problem:

  • I thought by referencing to b) that if I make conditional sequences of data each of them ending with one of the possible values that could stand for the next observation and calculating the likelihood of each of them given the model, then can this be considered as prediction?

To be more specific, in my example (if I know that the possible observations can only be Click/Scroll/Hover/Zoom/Select) I will simulate the following sequences

["Click","Scroll","Hover","Zoom","Select","Scroll"]

["Click","Scroll","Hover","Zoom","Select","Click"]

["Click","Scroll","Hover","Zoom","Select","Select"]

["Click","Scroll","Hover","Zoom","Select","Hover"]

["Click","Scroll","Hover","Zoom","Select","Zoom"]

and the sequence that gives higher probability is "the predicted", so eventually I also have the predicted next observation, which will be the last observation of the sequence that gives higher likelihod. Is this correct?

  • Another way as it is referred in this link would be to predict the most likely hidden-state-sequence based on a) and then through the emission distribution of the last hidden state to calculate the mean of this distribution? The above link was never verified and I am wondering if anyone could verify it.

  • Other way would be to get the sum of the likelihoods of all states each of them multiplied with the mean of the state's distribution. Is it correct?

Thank you in advance for any feedback you can give me.

$\endgroup$
  • $\begingroup$ Is this a home work? Because this doesn't sound like a real problem. $\endgroup$ – Aksakal Jul 30 '14 at 20:47
  • $\begingroup$ Do you need to predict just the next observation or a sequence of observations? $\endgroup$ – Enrique Jul 30 '14 at 21:53
  • $\begingroup$ @Aksakal I have updated my question with the real problem and some more details. Thank you. $\endgroup$ – mart Jul 31 '14 at 6:15
  • $\begingroup$ @Enrique I need to predict the next observation. $\endgroup$ – mart Jul 31 '14 at 6:16
  • 1
    $\begingroup$ Given a sequence of $N$ observations $y_{1:N}$ and the model parameters $\Theta$ you want to find $y_{N+1} = \arg max P(y_{N+1}|y_{1:N},\Theta)$, is that right? $\endgroup$ – Ufuk Can Bicici Jul 31 '14 at 6:38
6
$\begingroup$

From your question, I understood (hopefully correctly) that you want to estimate the next observation, given the observations up to now. Let $y_{1:N} = Y$ the N observations you have seen until now and let $\Theta$ be the parameters of the HMM. Then you want to infer the probability of the next observation given the already observed data, which can be expressed as:

$$ P(y_{N+1}|y_{1:N}=Y,\Theta)$$

If this is what you want, the above conditional expression is equal to : $$ P(y_{N+1}|y_{1:N}=Y,\Theta) = \dfrac{P(y_{1:N}=Y, y_{N+1}|\Theta)}{P(y_{1:N}=Y|\Theta)}$$

Note that the denominator is independent from $y_{N+1}$. So, it is:

$$ P(y_{N+1}|y_{1:N}=Y,\Theta) \propto P(y_{1:N}=Y, y_{N+1}|\Theta)$$

A brute force approach is the following:

For each of your possible observations, $y_{N+1}=Click, y_{N+1}=Scroll$ etc, calculate the likelihood of the sequences $y_{1:N+1}$. So what you need to calculate is $P(y_{N+1}=Click,y_{1:N}=Y|\Theta)$ , $P(y_{N+1}=Scroll,y_{1:N}=Y|\Theta)$, etc. for each of your possible observation sequences. Then the $y_{N+1}$ which gives the maximum likelihood can be estimated as the best guess for the next observation. Note that each of these likelihood calculations is a straightforward application of the forward pass algorithm, which corresponds to one of the three problems of HMMs: The calculation of the likelihood of a observation sequence. You have stated this in b) in your question.

Hope this helps.

$\endgroup$
  • $\begingroup$ Thank you very much for your answer. I've got it! So, it seems that with your answer you verify the first approach of my question. Do you have any idea for the next two approaches/solutions that I tried to describe? $\endgroup$ – mart Jul 31 '14 at 7:15
  • 1
    $\begingroup$ The first approach, in which you find the most likely sequence and then the most likely emission of the last hidden state seems not to be a good solution for me. In this case, you condition on a state sequence as if it was known exactly to be true. This is not the case: There is a $1- P(Viterbi State Sequence|\Theta)$ probability that the emissions you observe are generated by different state sequences and you omit these by using this approach. $\endgroup$ – Ufuk Can Bicici Jul 31 '14 at 7:28
  • $\begingroup$ I did not exactly understand the second approach. You seem to have a discrete state and emission space. If you have Gaussians as the state transitions and emissions, then you get a Kalman Filter, which is not very appropriate where you have a discrete state and emission space. $\endgroup$ – Ufuk Can Bicici Jul 31 '14 at 7:31
  • $\begingroup$ @UfukCanBicici The forward algorithm takes as one of its inputs $b_{t} = p(x_{t} | z_{t})$ (local evidence vectors). If we use the forward algorithm to uncover the distribution for $y_{N+1}$ as you suggest then we need to expand b to include $p(x_{t+1} | z_{t+1})$. Is this still possible given that we're only conditioning on $y_{1:N}$? $\endgroup$ – Omar Haque Mar 14 '18 at 15:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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