On Tue, Nov 25, 2014 at 2:59 PM, Jim Bromer <[email protected]> wrote: > On Mon, Nov 24, 2014 at 2:15 PM, Jim Bromer <[email protected]> wrote: > An algorithm that could 'predict' bits in arbitrary sequences which it > had never been exposed to can hardly be called a 'learning algorithm'. > > On Mon, Nov 24, 2014 at 8:24 PM, Matt Mahoney via AGI <[email protected]> > wrote: > Yes it is. Are you familiar with AIXI? > -- Matt Mahoney, [email protected] > > I remember you and other people talking about it. I find it > interesting that you did not dodge my fundamental criticism. So that > is probably where our disagreement is situated. Before you go on let > me say one thing. A human calculator does not have to be exposed to > every possible resultant that he could calculate in order to > understand the method. But that method is not a 'learning algorithm'. > It might be called a learned algorithm or something.
Since you are unfamiliar with AIXI, I will explain how it relates prediction and learning. The reason that prediction is possible at all is because by some miracle we live in a universe where agents receive compressible input sequences. For example, if you are receiving a sequence of bits and you see 1000 zero bits in a row, you could guess that the next bit will be zero and you would probably be right. What we call "learning" is guessing a theory or description or program that explains your observations. For example, the theory could be "always output 0", or equivalently, it could be a short program that outputs 0 forever in a loop. In either case, your theory or program or description can be written in less than 1000 bits. That is what I mean when I say that the sequence is compressible. Occam's Razor says that we should prefer simpler (shorter) theories to longer ones. This guideline has proven true in every branch of science since Occam said it over 500 years ago. The simplest theory that fits the observations makes the best predictions. You could have chosen a description like "output 0 1000 times followed by 1", but that is longer than "output 0 forever". Solomonoff, Kolmogorov, and Levin independently formalized Occam's Razor in the 1960's. A program or description of length n bits should be weighted by 1/2^n. Thus, there is a universal probability distribution (sometimes called a Solomonoff distribution) over all possible strings of bits (or other alphabets), which is the weighted sum of all programs that output the string. This probability is dominated by the shortest program. The length of this program is called its Kolmogorov complexity. We say that a string is random if its Kolmogorov complexity is not any shorter. Even though the vast majority of possible strings are random, most strings we observe in practice, such as the neural spikes from your senses, are compressible. Kolmogorov complexity depends on the language used to describe your strings, but he proved that was so only up to a small constant that depended only on the language. Any string described in one language can be described in any other language by appending a fixed sized translator. (You could argue that a translator between, say, C++ and English would be very large. But there are also very simple languages with small translators that can usually describe strings that have short descriptions in English). This brings us to the AIXI model described by Hutter. He and Legg proposed that universal intelligence is a measure of expected utility or accumulated reward when an agent interacts with a Solomonoff distribution of possible environments. Smarter agents are better at being rewarded wherever they are, for example, by gaining more energy or more money or more offspring or whatever else they want. AIXI is a mathematical model of an agent interacting with an environment. Both the agent and the environment are modeled as programs. At each time step, the agent outputs a symbol (1 or more bits) to the environment, and the environment outputs a symbol and a reward signal back to the agent. The utility function is modeled as part of the environment because the agent has no control over its goals. You can't decide not to be hungry, for example. What Hutter proved is that the best strategy for an agent is to guess that the program modeling the environment is the shortest program consistent with all of the interaction so far. Once it has made this guess, it can run a simulation proposing various outputs to see how much reward it will gain. Then it picks the best one. I think that you can see that the first step is exactly the same problem as predicting a sequence of bits. Given enough computing power, running the simulation is just a mechanical process, so the better it is at guessing the environment, the more it will be rewarded. This is the crux of the problem. Alas, AIXI (and therefore the general problem of learning and intelligence) is not computable, even with unlimited computing power. There is no general procedure that takes a string as input and outputs its Kolmogorov complexity. So we can never know if an agent's guess is the best one possible, or whether it should keep looking. I should mention Kolmogorov's proof, only because it is so elegant. Suppose that such a procedure existed. Then I could describe some rule for ordering strings and "the first string that can't be described in a million bits", even though I just did. Of course we can still write good predictors for AGI, even if they are not optimal. But it will take a lot of software to do so. This is a consequence of Legg's theorem that good predictors (learners) are necessarily complex. I'll repeat the proof, only because it is so elegant. Suppose you have a simple (short) yet powerful program that predicts bits. Then I have a simple program that can output a sequence that your program can't predict. My program runs your program and outputs the opposite of whatever it guesses. The rest is just DNA and dollars. -- -- Matt Mahoney, [email protected] ------------------------------------------- AGI Archives: https://www.listbox.com/member/archive/303/=now RSS Feed: https://www.listbox.com/member/archive/rss/303/21088071-f452e424 Modify Your Subscription: https://www.listbox.com/member/?member_id=21088071&id_secret=21088071-58d57657 Powered by Listbox: http://www.listbox.com
