Predicting the next symbol that a black box outputs

Question

Scenario:

Say we are given a "black box" which simply outputs a symbol once per second.

There are an indefinite number of types of symbols with no way to know any possible upper limit to the number of types. You can imagine them like alphabet characters but where we don't know how many different types there are (could be many more than 26 or many fewer, we don't know).

We know absolutely nothing about the way these symbols are being produced. We have no information at all - we must infer everything by observing the stream of symbols.

---

Problem:

Before the box is switched on (and starts producing symbols), we must come up with an algorithm which best predicts the next symbol at every step. We can assume that we have infinite computing power (i.e. algorithm efficiency is irrelevant).

---

Thoughts:

I think this problem has to do with inductive bias and potentially the "no free lunch" theorem.

In my limited reading on these topics on the internet, people seem to suggest that you can't make any useful predictions without first holding some assumptions about the data stream.

I may very well be mistaken, but it doesn't seem like that's correct. Imagine two algorithms:

1. Guess that the next symbol will be the symbol that has occurred most frequently so far.
2. Guess that the next symbol will be the symbol that has occurred least frequently so far.

Given absolutely no assumptions about the data stream, it's hard to imagine the second algorithm out-performing the first one in general (i.e. across many trials with different black boxes). If this is true, the fact that some algorithms work better than others suggests that there is an "optimal" algorithm for this problem.

As you can tell I've only got vague intuitions about this. Are there some assumptions hiding in my reasoning? Thanks for your help!

Answer 1

If you have a prior distribution on the possible black boxes, this is a simple Bayesian estimation question. So it just comes down to what a reasonable prior is.

Unfortunately, having "no information," if it means anything, certain means that we have no way of judging how reasonable a prior distribution is.

If we assume this is a physical device then we could start out with a prior that says the probability of the sequence having Kolmogorov complexity n is proportional to 1/n. [1]

But of course that just pushes the question back a step, because that takes our human knowledge of physics as a given, when of course our knowledge of physics is already based on our predictions of a black box process: we've seen the sun come up every day for as long as we remember, so we assume -- for no logical reason -- that tomorrow it will not be replaced with a giant papier-mache model of Conway Twitty's head.

---

[1] I should emphasize that, while satisfying in principle, this would be completely impossible to implement in real life.

Answer 2

I discussed this question with a friend and he quickly convinced me that we need to know something about the symbol stream for any particular algorithm to be better than any other. His reasoning is simple:

Without any information about how the stream is generated, no particular sequence of symbols is any more likely than any other sequence.

The two example algorithms that I proposed rely on one "class" of sequence being more likely than another class, and we have no reason to assume that any class of sequences is any more likely than any other class.

---

Edit: I recently stumbled into the wonderful world of data compression and did some more research into information theory.

I'm now convinced that if we assume that the box generates a data stream that isn't completely uniformly random, then some algorithms will work better than others.

If others who come across this question are interested in this, then definitely read up on modern compression algorithms. This "black box" problem is (essentially) 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.