7
$\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
7
$\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
  • $\begingroup$ @mart A quick question, For predicting next item in the sequence, essentially we will have to first learn HMM with "Baum–Welch algorithm" and then calculate likelihood of all sequences (different next items at end of given sequence) using "forward-backward" algorithm? I am right? $\endgroup$ – A.B Jul 9 '20 at 9:44
0
$\begingroup$

You can solve this problem with 2 way.

  • You can set new observations to your HMM model and run forward probabilities.Once you have you should focus on last column of probabilities because the forward algorithm efficiently sums over all the probabilities of all possible paths to each state for each observation in each sequence. The end result is that the log-likelihood values in the final observation columns represent the likelihood over all possible paths through the HMM.Once you find most likely state then just need to find new observation from emission matrix. And for the second observation you should look transition matrix for next state and once you sample next state you should calculate 2nd observation from emission matrix...

  • Second option to find max likelihood of new observations from all possible observations in forward probabilities. As you mentioned you need to run all observations and same as first method you just need to calculate likelihood for last column.(I mentioned the reason already).Once you find the maximum likely observation you can set it and can calculate for the 2nd observation with same way.

for the seqHMM package

1st option

model$transition_probs[,apply(fb$forward_probs[, , 1], 2, which.max)[column_number]]

2nd option

fb_<-forward_backward(model_,forward_only = TRUE)
fb_<-data.frame(fb_$forward_probs)
last_probs<-fb_[,ncol(fb_)]
print(logSumExp(last_probs))
$\endgroup$

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.