3 ms·

I think there are 2 main problems with working on universal prediction: 1. getting all the information to the program in a usable, computational format. 2. De

I think there are 2 main problems with working on universal prediction: 1. getting all the information to the program in a usable, computational format. 2. Defining the requirements (old problem but a good one). How would you actually design an algorithm to predict something completely unknown. ML works well here, as it is fairly narrow and 'easily' definable It certainly is the most interesting problem though, and I'd love to see more research attempted.

QML 8y ago
How would you make an algorithm to predict something unknown? This is essentially the field of sequential decision making, which encompasses everything from reinforcement learning to multi-armed bandits. [1] As an example, let’s pretend we have the task of predicting labels of a size 2 alphabet {0, 1}. These labels are come to us via a stream; so in contrast to classical ML, we are not given access to the full “dataset” beforehand to train our predictor. But instead, each round, a label is given to us; and in between each round, we can only predict the next label with the set of labels previously revealed. Note that we have no model of how the labels are generated — this is what we mean by “predict something unknown”. In general, we can assume two cases: it’s either adversarial or predictable (shaky definitions, I know). In an adversarial case, we assume the labels are generated such that we incur a heavy loss. Say, if we predict 0, the adversary outputs 1; vice versa. It turns out with deterministic strategies and a certain adversarial model, we can always incur loss linear to the amount of rounds; this goes a bit into game theory. To counter this, we can employ a random strategy where we flip a fair coin to decide what to predict. This is somewhat analogous to you, in the classic tie breaking game, of choosing {rock, paper, scissors} with 1/3 probability. But what if the labels weren’t generated adversarially? Remember, we don’t have a model of how the labels were generated. Say, the sequence was 000000... predicting with a fair coin would be a bad strategy then; and instead it’d be better to simply predict 0. A better strategy here would be something like follow-the-leader, where you predict the most frequent label seen so far. But recall, we don’t know how the labels are generated — it could very well alternate between periods of predictability and unpredictability. What we need is a mixed strategy which does well in both cases. One algorithm that turns out to do this is called multiplication weights, which assigns “weights” to each label and increases or decreases them proportionally each round depending on what the label is. There’s a whole lot of other ground that can be covered but I’d recommend reading a book instead of reading it here. One resource is “Prediction, Learning, and Games”—but feel free to find another book since this one assumes a background in probability. [1] Actually the first section of the linked pdf above.
- Xcelerate 8y ago
  > How would you make an algorithm to predict something unknown? Wouldn't AIXI address this? I believe the algorithm is known; the hard part is how to approximate it in a practical (i.e., remotely feasible) way...
taneq 8y ago
If it's universal then 1 shouldn't be an issue, because it's universal. Right?

QML 8y ago

How would you make an algorithm to predict something unknown? This is essentially the field of sequential decision making, which encompasses everything from reinforcement learning to multi-armed bandits. [1] As an example, let’s pretend we have the task of predicting labels of a size 2 alphabet {0, 1}. These labels are come to us via a stream; so in contrast to classical ML, we are not given access to the full “dataset” beforehand to train our predictor. But instead, each round, a label is given to us; and in between each round, we can only predict the next label with the set of labels previously revealed. Note that we have no model of how the labels are generated — this is what we mean by “predict something unknown”. In general, we can assume two cases: it’s either adversarial or predictable (shaky definitions, I know). In an adversarial case, we assume the labels are generated such that we incur a heavy loss. Say, if we predict 0, the adversary outputs 1; vice versa. It turns out with deterministic strategies and a certain adversarial model, we can always incur loss linear to the amount of rounds; this goes a bit into game theory. To counter this, we can employ a random strategy where we flip a fair coin to decide what to predict. This is somewhat analogous to you, in the classic tie breaking game, of choosing {rock, paper, scissors} with 1/3 probability. But what if the labels weren’t generated adversarially? Remember, we don’t have a model of how the labels were generated. Say, the sequence was 000000... predicting with a fair coin would be a bad strategy then; and instead it’d be better to simply predict 0. A better strategy here would be something like follow-the-leader, where you predict the most frequent label seen so far. But recall, we don’t know how the labels are generated — it could very well alternate between periods of predictability and unpredictability. What we need is a mixed strategy which does well in both cases. One algorithm that turns out to do this is called multiplication weights, which assigns “weights” to each label and increases or decreases them proportionally each round depending on what the label is. There’s a whole lot of other ground that can be covered but I’d recommend reading a book instead of reading it here. One resource is “Prediction, Learning, and Games”—but feel free to find another book since this one assumes a background in probability. [1] Actually the first section of the linked pdf above.

Xcelerate 8y ago
> How would you make an algorithm to predict something unknown? Wouldn't AIXI address this? I believe the algorithm is known; the hard part is how to approximate it in a practical (i.e., remotely feasible) way...

taneq 8y ago

If it's universal then 1 shouldn't be an issue, because it's universal. Right?