HMM Route prediction

[reapphil]

Hi there!

I am not totally new to WEKA or classification but far away from calling myself an expert. I would like to make route prediction using HMM similar as presented in:
http://research.microsoft.com/en-us/...distribute.pdf

They build up a "second order markov model" where the prediction of the next segment in a route is only determined by the past two segments. Am I basically right with the assumption that i can use the following format of my observations to be evaluated in weka:

@relation sequence_data


@attribute sequences relational
@attribute x1 {'a','b','c','d','e','f','g','h'}
@end sequences
@attribute class {'a','b','c','d','e','f','g','h'}


@data
"'a'\n'b'",c

=> any observation delivers the next vertex (c) just as combination of the following two vertices (a,b). I have about 10.000 such observations and can sucessfully apply the HMM classifier from weka 3.7.12. on the data (with an accuracy of about 70% with over 100 classes (random guessing would result in 5%). Is it now possible in weka to use such a formulation to also predict the possible next 2 segments...or am I completely wrong with my assumptions? And by the way, why using HMM for such a problem with observations containing only 2 attributes?

Thank you for your help!

[Mark]

As far as I understand the HMM package (which isn't saying a lot :-)), you have the correct data format. I think that if you want to predict the next n segments you'd have to write a small program to "bootstrap" the predictions. I.e, you'd use the segment at t+1 prediction as part of the input for predicting the segment at t+2. This would involve creating an instance to predict programatically - using your example instance above, and assuming that the HMM had predicted c for t+1, you'd construct an instance "'b'\n'c'",?. Of course, you'd also have to write your own evaluation routine for this if you want to see how good these 2-step ahead predictions are.

Cheers,
Mark.