Learning Universal Predictors
arxiv.org
arxiv.org
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).
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/CalcEmergTitlePag...
There is actually more at stake here than machine learning. This gets to the root of "bias" in the scientific method. Imagine what horrors, what risks, what chaos would be ours if a truly objective information criterion for causal model selection were to exist! Why, virtually every "sociologist" would be hauled to Hume's Guillotine in a Reign of Terror!
https://github.com/jabowery/HumesGuillotine
But to be clear, Marcus and I have a disagreement about pragmatics of such an approach to dispute processing in the natural sciences. He believes, for example, that the dispute over climate change should be handled by the standard processes in place with academia. My approach differs, based on my hard won experience with reforming institutional incentives:
https://jimbowery.blogspot.com/2018/04/necessity-and-incenti...
When it comes to multi-trillion dollar scientific questions, the conflicts of interest become so intense that you really need to apply a gold standard for objectivity and that is the single number: How big is your executable archive of the data in evidence.
While I understand the machine learning world looms as a rival for "unbiased" academic research, it nevertheless remains true that even in this emerging "marketplace of ideas", there is no formal definition of "bias" that disciplines discourse and thereby guides development at the institutional, let alone technical level. Everyone is weighing in with their fuzzy notions of "bias" that betray intense motivations when there has been, for over 50 years, a very clear and present mathematical definition.
But isn’t there already a blackbox measure of overfiting one that focus on how well the model generalizes to new, unseen data, rather than on the model’s complexity. Like Cross-Validation, hold-out validation or bootstrap method.
"For our BrainPhoque language (that we use in our experiments later) it increases the yield of ‘interesting’ programs by a factor of 137"
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
“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.”