6 ms·

I'm honestly surprised there's not more research / funding on universal prediction. It seems like a top down approach for true AI (start from theory and work b

I'm honestly surprised there's not more research / funding on universal prediction. It seems like a top down approach for true AI (start from theory and work backwards to something feasible/practical) as opposed to the current engineering mindset (start with something that works, i.e., neural networks, and try to do more with them). The ideas related to universal prediction were initially developed in the 1960s by Chaitin, Solomonoff, and Kolmogorov, but little has been done with the concept since, partly due to the fact that computers weren't very powerful back then and partly due to the fact that a lot of their theorems ran up against barriers of uncomputability. Marcus Hutter and Shane Legg come to mind as people who have done some work in this area, but I'm not sure if Shane has continued investigating this approach separately from his work with neural networks at DeepMind.

throwawayjava 8y ago
Huh. My impression was always that "universal prediction" got replaced by various branches of statistics, ML theory, and probability theory, each considering more specific questions that used to fall under a single umbrella? Perhaps a best comparison is "cybernetics", which doesn't get funding these days except, of course, for the billions upon billions of dollars thrown at robotics, self-driving, factory automation, and so on.
deleted 8y ago
[deleted]
acutesoftware 8y ago
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...

throwawayjava 8y ago

Huh. My impression was always that "universal prediction" got replaced by various branches of statistics, ML theory, and probability theory, each considering more specific questions that used to fall under a single umbrella? Perhaps a best comparison is "cybernetics", which doesn't get funding these days except, of course, for the billions upon billions of dollars thrown at robotics, self-driving, factory automation, and so on.

deleted 8y ago

[deleted]

acutesoftware 8y ago

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...