Predicting next character based on few previous — how to combine predictions?

Question

I asked this question at math.stackexchange.com first, but nobody answered. Perhaps statisticians can help me.

The question is like this:

I have a signal generator, which each second generates one of the letters 'a', 'b' or 'c'.

I don't know anything else about this signal generator, but I suspect that there are some patterns to it.

The signal generator is started at time 0. Given output of the signal from time 0 to time n, I need to forecast its output at time n+1.

I suspect that there are some patterns to the signal, so I create a frequency table:

For each sub-string (up to length 7) of the first n symbols of the signal generated data, I calculate three values: the number of occurrences of 'a','b', and 'c' after that sub-string.

So, for example for sub-string "abc"(if it exists in the data), I store:

• the number of cases when symbol 'a' comes after string "abc"
• the number of cases when symbol 'b' comes after string "abc"
• the number of cases when symbol 'c' comes after string "abc"

Now that I have all these data, I have 7 predictions as to what the next symbol could be. If for example the last 7 characters of the signal are "acbccba", then:

If I look just at the one-character frequency table, then I will have a certain prediction, which would look like: "Since the last character of the string is 'a', and since coming directly after character 'a' there were 40 cases of letter 'a', 25 cases of letter 'b', and 130 cases of letter 'c', I predict that the next character will be letter 'c'"

Similarly for the last 2-letter ("ba"), 3-letter ("cba"), ... , 7-letter ("acbccba"). So in the end I have 7 predictions.

The question is, how do I find which next character is actually the most probable for this signal generator? Different predictions are based on different sample sizes, so how do I combine them effectively?

Answer 1

Sounds like Hidden Markov model stuff. Like DNA/amino acid sequences, or in more general case, Speech recognition.

Here there are some advises for learning resources.

Answer 2

This may be overkill, but Geoffrey Hinton has been doing something like this using artificial neural networks and backpropagation in time.

He trains his model using blocks of text from wikipedia or NYTimes, the network learns the chained statistical relationships you mention in your question. Then the network can iteratively generate characters from a short prompt.

The sample below was obtained by running the MRNN less than 10 times and selecting the most intriguing sample. The beginning of the paragraph and the parentheses near the end are par- ticularly interesting. The MRNN was initialized with the phrase “The meaning of life is”:

The meaning of life is the tradition of the ancient human reproduction: it is less favorable to the good boy for when to remove her bigger. In the show’s agreement unanimously resurfaced. The wild pasteured with consistent street forests were incorporated by the 15th century BE. In 1996 the primary rapford undergoes an effort that the reserve conditioning, written into Jewish cities, sleepers to incorporate the .St Eurasia that activates the popula- tion. Mar??a Nationale, Kelli, Zedlat-Dukastoe, Florendon, Ptu’s thought is. To adapt in most parts of North America, the dynamic fairy Dan please believes, the free speech are much related to the

The take-home from this paper is that the model was able to learn the fact that characters are organized into words, to learn many of those words, and to learn some of the rules of how words are strung together grammatically. That may be much more structure than the ABC character sequence you had in mind, so I think user4581 's answer is more appropriate. But this one is a lot of fun.

Answer 3

This problem is the basis for many modern compression algorithms. This page has a good discussion of PAQ; an algorithm that is based on prediction using multiple "contexts":

DMC, PPM, and CTW are based on the premise that the longest context for which statistics is available is the best predictor. This is usually true for text but not always the case. For example, in an audio file, a predictor would be better off ignoring the low order bits of the samples in its context because they are mostly noise. For image compression, the best predictors are the neighboring pixels in two dimensions, which do not form a contiguous context. For text, we can improve compression using some contexts that begin on word boundaries and merge upper and lower case letters. In data with fixed length records such as spreadsheets, databases or tables, the column number is a useful context, sometimes in combination with adjacent data in two dimensions. PAQ based compressors may have tens or hundreds of these different models to predict the next input bit.

Rather than selecting just the longest contiguous context as the "winner" which gets to determine the next symbol, context mixing is used in modern prediction algorithms:

Through PAQ3, the weights were fixed and set in an ad-hoc manner. (Order-n contexts had a weight of $n^2$.) Beginning with PAQ4, the weights were adjusted adaptively in the direction that would reduce future errors in the same context set.

...

Mattern (2012) proved that logistic mixing is optimal in the sense of minimizing Kullback-Leibler divergence, or wasted coding space, of the input predictions from the output mix.