5 ms·
Learning Universal Predictors
- QuadmasterXLII 3y agoEverybody gangster until Deepmind starts saying mid-2010s LessWrong words
- Vecr 3y agoMarcus Hutter invented AIXI (Hutter 2000), the theoretically optimal AI system. It's not computable though, and the computable version is hilariously inefficient. Yes it uses Solomonoff induction.
- shmageggy 3y agoI think you've got it backwards: LessWrong was saying these author's words. Hutter has been publishing about this topic for almost 25 years.
- cubefox 3y agoInteresting that they combine assumptions from highly idealized abstractions (universal Turing machines, Solomonoff induction) with realistic neural network architectures.
- sanxiyn 3y agoThey have been doing this forever. Here is a paper by some of the same authors: A Monte Carlo AIXI Approximation (2009). https://arxiv.org/abs/0909.0801 https://arxiv.org/abs/0909.0801
- optimalsolver 3y agoI see your universal predictor and raise you one non-halting program (in a language of your choice).
- Vecr 3y agoYes that's why it would be something like a Gödel machine[0]. Ignore everything it can't prove is not malicious (won't halt, runs too long, takes too many resources, etc.). [0]: https://en.wikipedia.org/wiki/G%C3%B6del_machine https://en.wikipedia.org/wiki/G%C3%B6del_machine
- riku_iki 3y agois halting program something can happen in infinite space? If space is finite, you can just memorize all processed internal states of the program, there are two options: - program gets into infinite loop, which will be detected by checking that internal program state was observed in the past already - program will actually halt
- Xcelerate 3y agoI see your pathological proof of existence and raise you an asymptotic probability of one: “The halting problem for Turing machines is perhaps the canonical undecidable set. Nevertheless, we prove that there is an algorithm deciding almost all instances of it.” https://arxiv.org/pdf/math/0504351.pdf https://arxiv.org/pdf/math/0504351.pdf
- tripplyons 3y agoThis sentence was fun to read: "For our BrainPhoque language (that we use in our experiments later) it increases the yield of ‘interesting’ programs by a factor of 137"
- Xcelerate 3y agoReally exciting article from Hutter et al. I feel like I’m beating a dead horse with how much I comment about Solomonoff induction on here, but I am constantly both amazed and perplexed that we don’t have thousands of research labs going about AGI via a top-down, theory-first approach—i.e., starting with the upper bound of what is possible and working down to the nearest resource-constrained physical approximation to it. Can we bootstrap our way to basic AGI by tinkering with neural network architectures and scaling up the hardware? Maybe. After all, the human brain sort of echos that approach. But at some point, in order to sustain continued improvement toward optimal AGI, there will have be a strong algorithmic component to sequence prediction that is based upon a very deep understanding of what is computable (assuming the physical Church-Turing thesis). I don’t really see a way around that, because the foundational principles of algorithmic and computational complexity ultimately determine the upper limit of our ability to predict the future, which is kind of mind-blowing to me (and even more so considering that much of the theory was developed over half a century ago). But wait! What about the halting problem, NP hardness, the NFL theorem, Gödel’s incompleteness theorems, Blum’s speedup theorem, ..., [insert your favorite pessimistic no-go theorem]? Yeah, so what? Most of these nonstarters apply to “almost all” valid problems, which ironically happen to overlap with “almost none” of the problems we care about, because the distribution of real world problems does not coincide with the distribution of problems randomly sampled from a formal language. If that were the case, then nothing would be predictable at all because prediction-making beings could not exist in such an environment (in other words, real world problems tend to exhibit Kolmogorov-compressibility in the form of mathematical substructure that leads to heuristic solvers that are particularly effective beyond what average-case complexity would imply).
- jsenn 3y agoI also find this stuff fascinating, but I'm not sure Kolmogorov complexity (and therefore Solomonoff Induction) are useful models of any form of intelligence that matters in the real world. The main issue I see is that Komogorov Complexity is dominated by noise. The majority of bits in the smallest program that generates a given sequence will be devoted to reproducing arbitrary/accidental features of the sequence, rather than its computational structure. For example, if a Solomonoff Induction machine sees a data stream produced by someone flipping a coin, its model of that process will be... the data stream itself. To me, that's not intelligent behaviour. I would like an intelligent agent to "average out" the noise and say "this data stream is produced by sampling from a Bernoulli process with p = 0.5". This is why I like Crutchfield's Epsilon Machine formalism[1]. He factorizes Kolmogorov Complexity into a noise part (Shannon Entropy) and a "computational part", which measures the structural complexity of the smallest probabilistic finite state machine that is an optimal predictor of the data sequence, under some coarse-graining. If the size of the optimal machine gets bigger and bigger the more fine-grained your measurement, then there's no finite representation of the sequence as a FSM, so you "jump up one level" to a stack machine and try again. In the coin-flipping example above, the epsilon machine will correctly factor out all of the noise in the sequence, leaving you with a simple probabilistic model of a coin-flip process. This procedure is also computable, and even practical: you can implement the FSM-only algorithm in a couple hundred lines of code. [1]: https://csc.ucdavis.edu/~cmg/compmech/pubs/CalcEmergTitlePage.htm https://csc.ucdavis.edu/~cmg/compmech/pubs/CalcEmergTitlePag...
- drdeca 3y agoSo, how good are these results? Are these impressive?
- Vecr 3y agoI actually don't know. They say in the paper they can't figure out a better way to approximate Solomonoff induction in the UTM (universal Turing machine) section, so they just guess some reasonable value (based on knowledge of the program that generates the sequence).