9
$\begingroup$

Question: Is the set-up below a sensible implementation of a Hidden Markov model?

I have a data set of 108,000 observations (taken over the course of 100 days) and approximately 2000 events throughout the whole observation time-span. The data looks like the figure below where the observed variable can take 3 discrete values $[1,2,3]$ and the red columns highlight event times, i.e. $t_E$'s:

enter image description here

As shown with red rectangles in the figure, I have dissected {$t_E$ to $t_{E-5}$} for each event, effectively treating these as "pre-event windows".

HMM Training: I plan to train a Hidden Markov Model (HMM) based on all "pre-event windows", using the multiple observation sequences methodology as suggested on Pg. 273 of Rabiner's paper. Hopefully, this will allow me to train an HMM that captures the sequence patterns which lead to an event.

HMM Prediction: Then I plan to use this HMM to predict $log[P(Observations|HMM)]$ on a new day, where $Observations$ will be a sliding window vector, updated in real-time to contain the observations between the current time $t$ and $t-5$ as the day goes on.

I expect to see $log[P(Observations|HMM)]$ increase for $Observations$ that resemble the "pre-event windows". This should in effect allow me to predict the events before they happen.

$\endgroup$
  • $\begingroup$ You can split your data to build a model (say 0.7), then test your model on the remaining data. Just a thought, i'm not a specialist on this area. $\endgroup$ – Fernando Oct 14 '13 at 15:41
  • $\begingroup$ Yes, thank you. It is more the suitability of HMMs for the task that I am unsure about. $\endgroup$ – Zhubarb Oct 14 '13 at 15:59
  • $\begingroup$ @Zhubarb I'm dealing with a similar problem and would like to follow your HMM approach. Where you successful doing this? Or did you finally recurred to logistic regression / SVM, etc? $\endgroup$ – Javierfdr May 4 '16 at 10:49
  • $\begingroup$ @Javierfdr, I ended up not implementing it due to difficulty of implementation and the concerns that alto highlights in his answer. Essentially, HMM's come with the burden of having to build an extensive generative model, whereas my gut feeling now is for the problem at hand, one can more easily get away with a discriminatory model (SVM, Neural Net, etc.) as you suggest. $\endgroup$ – Zhubarb May 5 '16 at 13:42
3
$\begingroup$

One problem with the approach you've described is you will need to define what kind of increase in $P(O)$ is meaningful, which may be difficult as $P(O)$ will always be very small in general. It may be better to train two HMMs, say HMM1 for observation sequences where the event of interest occurs and HMM2 for observation sequences where the event doesn't occur. Then given an observation sequence $O$ you have $$ \begin{align*} P(HHM1|O) &= \frac{P(O|HMM1)P(HMM1)}{P(O)} \\ &\varpropto P(O|HMM1)P(HMM1) \end{align*} $$ and likewise for HMM2. Then you can predict the event will occur if $$ \begin{align*} P(HMM1|O) &> P(HMM2|O) \\ \implies \frac{P(HMM1)P(O|HMM1)}{P(O)} &> \frac{P(HMM2)P(O|HMM2)}{P(O)} \\ \implies P(HMM1)P(O|HMM1) &> P(HMM2)P(O|HMM2). \end{align*} $$

Disclaimer: What follows is based on my own personal experience, so take it for what it is. One of the nice things about HMMs is they allow you to deal with variable length sequences and variable order effects (thanks to the hidden states). Sometimes this is necessary (like in lots of NLP applications). However, it seems like you have a priori assumed that only the last 5 observations are relevant for predicting the event of interest. If this assumption is realistic then you may have significantly more luck using traditional techniques (logistic regression, naive bayes, SVM, etc) and simply using the last 5 observations as features/independent variables. Typically these types of models will be easier to train and (in my experience) produce better results.

$\endgroup$
  • $\begingroup$ @ alto, thank you. As you say, I will be looking at $p = log(P(O|hmm))$, and values like $p_1 =-2504, p_2 = -2403, p_3= -2450$, etc. so spotting a significant increase in $p$ may be problematic. In the meantime, I think training HMM2 will be hard. The number of points I have for HMM2 (no event) will be much higher and there may be no patter but only noise. What do you think? P.S: I chose 5 in as my window size arbitrarily, it is likely to be longer than that in an actual implementation. $\endgroup$ – Zhubarb Oct 15 '13 at 7:13
  • 1
    $\begingroup$ @Berkan I don't think either issue you mention (more no event sequences than event sequences and just noise for no event) should rule out the 2 HMM approach. If you took the prior $P(HMM1)$ into account (I've update my original answer in this regard) then you may need to adjust for the unbalanced class distribution (more no events than events), but there are lots of ways to deal with this. See this answer I gave for example. $\endgroup$ – alto Oct 16 '13 at 14:03
  • $\begingroup$ @Berkan As for the window size, based on my own personal experience I expect what I've said in this matter will hold for any fixed window size. Obviously all of the things I've said will need to be tested empirically for your particular problem. $\endgroup$ – alto Oct 16 '13 at 14:14
  • $\begingroup$ thanks for updating your answer, it is a lot clearer now. Since I will be working with logarithms, I will be making the comparison: $log(P(HMM1))+log(P(O|HMM1)) >? log(P(HMM2))+log(P(O|HMM2)) $. Now, $log(P(HMM1))$ is calculated using the forward algorithm, how do I calculate $log(P(HMM1))$? Is ti just a prior that I appoint? $\endgroup$ – Zhubarb Oct 16 '13 at 14:17
  • $\begingroup$ thanks for updating your answer, it is a lot clearer now. Since I will be working with logarithms, I will be making the comparison: $log(P(HMM1))+log(P(O|HMM1))>?log(P(HMM2))+log(P(O|HMM2))$. Now, $log(P(HMM1))$ is calculated using the forward algorithm. Do I calculate log(P(HMM1)) using simple MLE based on frequencies? i.e. for the given case, $HMM1 = (5 * 2,000) / 108,000$ where the numerator is the number of points that fall under HMM1 and denominators is the size of the data set. $\endgroup$ – Zhubarb Oct 16 '13 at 15:23

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.