Solved – Predict observation using Hidden Markov Models

hidden markov modelmachine learningprediction

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.

Best Answer

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.

Related Question