4
$\begingroup$

I have a repeating sequence like the following, with occasionally random values (maybe noise): ABCDABCEDABCDABCD

What could be an algorithm to model the sequence and predict a following value at a certain time. For example I had ABC and no it should say D (of course it can only give a percentage since it is not always D following ABC).

First I wanted to try HMMs, but I think there is no hidden state, since i ABC are my states and can be observed. My second thought would be markov chains, but I am not quite sure if there is an good way to learn the probabilities and give me a prediction given one or two (for a second degree markov model) of the following value.

I also wanted to look into RNNs, but it would be great if someone with experience could tell me in advance if they are a good way for this task or if I should focus on more promising ways.

$\endgroup$
  • $\begingroup$ Did you have a look at time series models for categorical data? $\endgroup$ – Michael M May 28 '17 at 10:18
4
$\begingroup$

The answer depends on whether you want to perform your predictions and the according adjustments to the model online or you want to be able to make several passes over data that is completely available all the time.

In case you do want to do online learning and you do not have any more information on the sequence (e.g. distribution probabilities for its elements), your best bet should be a order-n Markov predictor.

As your data seems to be discrete, this can be implemented easily with a transition table that stores the number of transitions from the last n elements to the current one. If you normalize the number of transitions for particular n elements you get an estimate for the conditional probability distribution of possible successors.

An alternative, although much more demanding in terms of implementation and run-time complexity, are recurrent neural networks like, for example, LSTM.

If you do not need/want to perform online learning, then there is a plethora of possible approaches. A helpful introduction and overview is this.

| cite | improve this answer | |
$\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.