Which Algorithms can model a sequence and predict the next value of this sequence

Question

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.

Answer 1

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.