3 ms·

I always thought better sequence prediction was the natural prerequisite to AGI, given that it’s kind of the whole foundation of algorithmic information theory

I always thought better sequence prediction was the natural prerequisite to AGI, given that it’s kind of the whole foundation of algorithmic information theory (specifically, the upper limit to prediction is a prefix-free universal Turing machine that maximally compresses an input sequence and is allowed to continue running once it has reproduced the given input sequence). It’s kind of funny to me that the general public seems to be recognizing this in a backward fashion — “oh hey LLMs can be used for other stuff too!” I would be extremely surprised if any LLM researcher hasn’t heard of Solomonoff induction though.

cubefox 3y ago
I don't think maximal (lossless) compression is an ideal for AI. Sense data (our eyes basically provide video feeds) are very noisy and compress extremely badly if you try to do it losslessly. I don't think the Kolmogorov complexity of Oppenheimer would be much shorter than its gzip length. Usually, when we try to make predictions about unseen data from given data (induction), we make a trade-off between the complexity of a hypothesis and how well it "predicts" the available data. Solomonoff induction doesn't make this trade-off. Being based on lossless compression, it always demands perfect "prediction" of the available data, even if this means that the complexity of the "hypothesis" (~its Kolmogorov complexity) is very high and perhaps hardly smaller than the length of the uncompressed available data. Such greedy strategies usually tend to extreme overfitting and terrible generalization to new unseen data. What you really want is to accept some lossiness in predicting the available data for a much simpler hypothesis (better compression ratio). An optimal AI would always make the perfect such trade-off.
- Xcelerate 3y ago
  > I don't think the Kolmogorov complexity of Oppenheimer would be much shorter than its gzip length. I think the conditional Kolmogorov complexity of Oppenheimer given all real world data we could collect [K(Oppenheimer|earth)] would be massively shorter than its gzip length. I agree that by using just the universal distribution alone this might not be the case. Consider an input tape that consists of all real world data we are able to collect, concatenated with the input data of interest. Now consider the set of all prefix-free universal Turing machines that generate the full sequence on the tape. We then consider a normalized probability distribution based on this set where each program’s output beyond the reproduction of the input tape is weighted by 2^-[length of program]. Roughly speaking (glossing over some details), you can’t do better at predicting the future than this probability distribution assuming the physical Church-Turing thesis. An optimal AGI must incorporate optimal prediction. At this point, you can now develop an agent that utilizes reinforcement learning based upon this probability distribution, but my guess is that this part won’t be nearly as difficult as the prediction step. The particulars of the actual objective function for the agent are kind of irrelevant (could be something along the lines of “maximize whatever the p99 of humans consider AGI to be”), but whatever is chosen, there cannot be a general algorithmic process that would perform better.
  - cubefox 3y ago
    > I think the conditional Kolmogorov complexity of Oppenheimer given all real world data we could collect [K(Oppenheimer|earth)] would be massively shorter than its gzip length. To predict Oppenheimer perfectly, pixel for pixel, we would need at least Laplace's Demon with knowledge of both the laws and the complete initial state of the universe. And we need to assume the evolution of the universe is even deterministic and computable, otherwise this wouldn't work in the first place. And even if we have the laws and the complete initial state of the universe, and its evolution is computable: if we live in some form of multiverse (or extremely large repeating universe, which is not unlikely, since many physicists assume the universe is infinitely large), it would still not work. There may be countless copies of Earth which are indistinguishable given (i.e. underdetermined by[1]) the data we can collect on Earth, but where each version of Oppenheimer has a completely different pixel noise pattern, and consequently different Kolmogorov complexity. So the "compressed" UTM input string would have to hardcode basically our entire Earth Oppenheimer in order to perfectly and uniquely determine the movie, resulting in a terrible compression ratio. And even if the universe is in fact small and not a multiverse, our data available to us on Earth is probably not enough to uniquely retrodict the initial state (and laws) of our universe, since there are countless possible but non-actual universes which are consistent with our Earth data, but which all differ in initial state and laws in a way such that they again predict different versions of Oppenheimer, and so again the "compression" has to hardcode basically everything. Underdetermination strikes again, be it uncertainty about location in a multiverse or uncertainty about which merely possible universe the the actual one. > Roughly speaking (glossing over some details), you can’t do better at predicting the future than this probability distribution assuming the physical Church-Turing thesis. That only holds if you restrict yourself to perfect predictions, not prediction in general. (And of course ignore that Solomonoff induction is uncomputable even if the universe itself is computable.) The issue is that we don't care about just maximizing the probability of perfectly accurate predictions, because, given underdetermination, the best perfect prediction would still be highly unlikely to be true, because it would be dominated by overfitting on tons of hardcoded noise and not by real high level patterns in the data. What we really want for an "optimal" prediction is the prediction with the best "expected accuracy", the best expected "goodness of fit", expected "closeness to the truth" etc. The best such prediction may be perfectly accurate with probability 0% (most good predictions make unrealistic simplifying assumptions where we already know they are strictly speaking false), but that doesn't matter when the prediction is likely very accurate, very close to the truth. An ideal prediction algorithm would probably minimize something like the quantity (complexity of hypothesis + inverse of goodness of fit to the given data). And it would be computable, since uncomputability is a rather non-ideal property of an algorithm. [1] https://en.m.wikipedia.org/wiki/Underdetermination https://en.m.wikipedia.org/wiki/Underdetermination

cubefox 3y ago

I don't think maximal (lossless) compression is an ideal for AI. Sense data (our eyes basically provide video feeds) are very noisy and compress extremely badly if you try to do it losslessly. I don't think the Kolmogorov complexity of Oppenheimer would be much shorter than its gzip length. Usually, when we try to make predictions about unseen data from given data (induction), we make a trade-off between the complexity of a hypothesis and how well it "predicts" the available data. Solomonoff induction doesn't make this trade-off. Being based on lossless compression, it always demands perfect "prediction" of the available data, even if this means that the complexity of the "hypothesis" (~its Kolmogorov complexity) is very high and perhaps hardly smaller than the length of the uncompressed available data. Such greedy strategies usually tend to extreme overfitting and terrible generalization to new unseen data. What you really want is to accept some lossiness in predicting the available data for a much simpler hypothesis (better compression ratio). An optimal AI would always make the perfect such trade-off.

Xcelerate 3y ago
> I don't think the Kolmogorov complexity of Oppenheimer would be much shorter than its gzip length. I think the conditional Kolmogorov complexity of Oppenheimer given all real world data we could collect [K(Oppenheimer|earth)] would be massively shorter than its gzip length. I agree that by using just the universal distribution alone this might not be the case. Consider an input tape that consists of all real world data we are able to collect, concatenated with the input data of interest. Now consider the set of all prefix-free universal Turing machines that generate the full sequence on the tape. We then consider a normalized probability distribution based on this set where each program’s output beyond the reproduction of the input tape is weighted by 2^-[length of program]. Roughly speaking (glossing over some details), you can’t do better at predicting the future than this probability distribution assuming the physical Church-Turing thesis. An optimal AGI must incorporate optimal prediction. At this point, you can now develop an agent that utilizes reinforcement learning based upon this probability distribution, but my guess is that this part won’t be nearly as difficult as the prediction step. The particulars of the actual objective function for the agent are kind of irrelevant (could be something along the lines of “maximize whatever the p99 of humans consider AGI to be”), but whatever is chosen, there cannot be a general algorithmic process that would perform better.
- cubefox 3y ago
  > I think the conditional Kolmogorov complexity of Oppenheimer given all real world data we could collect [K(Oppenheimer|earth)] would be massively shorter than its gzip length. To predict Oppenheimer perfectly, pixel for pixel, we would need at least Laplace's Demon with knowledge of both the laws and the complete initial state of the universe. And we need to assume the evolution of the universe is even deterministic and computable, otherwise this wouldn't work in the first place. And even if we have the laws and the complete initial state of the universe, and its evolution is computable: if we live in some form of multiverse (or extremely large repeating universe, which is not unlikely, since many physicists assume the universe is infinitely large), it would still not work. There may be countless copies of Earth which are indistinguishable given (i.e. underdetermined by[1]) the data we can collect on Earth, but where each version of Oppenheimer has a completely different pixel noise pattern, and consequently different Kolmogorov complexity. So the "compressed" UTM input string would have to hardcode basically our entire Earth Oppenheimer in order to perfectly and uniquely determine the movie, resulting in a terrible compression ratio. And even if the universe is in fact small and not a multiverse, our data available to us on Earth is probably not enough to uniquely retrodict the initial state (and laws) of our universe, since there are countless possible but non-actual universes which are consistent with our Earth data, but which all differ in initial state and laws in a way such that they again predict different versions of Oppenheimer, and so again the "compression" has to hardcode basically everything. Underdetermination strikes again, be it uncertainty about location in a multiverse or uncertainty about which merely possible universe the the actual one. > Roughly speaking (glossing over some details), you can’t do better at predicting the future than this probability distribution assuming the physical Church-Turing thesis. That only holds if you restrict yourself to perfect predictions, not prediction in general. (And of course ignore that Solomonoff induction is uncomputable even if the universe itself is computable.) The issue is that we don't care about just maximizing the probability of perfectly accurate predictions, because, given underdetermination, the best perfect prediction would still be highly unlikely to be true, because it would be dominated by overfitting on tons of hardcoded noise and not by real high level patterns in the data. What we really want for an "optimal" prediction is the prediction with the best "expected accuracy", the best expected "goodness of fit", expected "closeness to the truth" etc. The best such prediction may be perfectly accurate with probability 0% (most good predictions make unrealistic simplifying assumptions where we already know they are strictly speaking false), but that doesn't matter when the prediction is likely very accurate, very close to the truth. An ideal prediction algorithm would probably minimize something like the quantity (complexity of hypothesis + inverse of goodness of fit to the given data). And it would be computable, since uncomputability is a rather non-ideal property of an algorithm. [1] https://en.m.wikipedia.org/wiki/Underdetermination https://en.m.wikipedia.org/wiki/Underdetermination