Hacker News Reader

Comment by supperburg | Hacker News Reader

Imagine every program that fits within 10TB. It’s a finite number of programs. Inside there is GTP-3, 2 and 1. Every GAN. Tesla FSD. It’s everything. What this entire industry is really about at its core is finding programs in that set that behave in intelligent ways. That’s all. Recently we’ve had success in letting the computer dig through programs automatically until it finds a good one. So overnight we went from testing maybe hundreds per year to billions per month or something like that. So obviously things have been getting weird.

Imagine how many we’ve dug up so far out of the total set. It’s an infinitesimal percentage. We haven’t even scratched the surface.

Imagine the set. What’s inside? Is there something inside that we will regret?

View on HN

While there are those in the AI community who believe scaling laws will unearth such programs, they are deluded. There are problems which scale faster than our computational resources allow, even if hardware scaling continues unabated for millennia to come.

The space of all programs in 10TB is far too large to count, even if we could harness galactic computation. Even within a much smaller search space, there are valid programs which cannot be found by gradient descent. Let BT(n) be the number of distinct binary trees less than or equal to height n. This number scales according to the following recurrence relation:

  BT(n+1)=(BT(n)+2)²−1

Consider the space of all binary trees of height 20 - there fewer atoms in the visible universe. And this is just laying out bits on a hard drive. There are other functions (e.g. Busy beaver and friends) which scale even faster. The space of valid programs in 10TB is too large to enumerate, never mind evaluate.

In case anyone here is interested in learning more about program synthesis, there is a new workshop at NeurIPS 2021 which explores some of these topics. You can check it out here: https://aiplans.github.io/

Yeah

You're not wrong, but the numbers are quite different if you have a strong search heuristic. And that is where neural nets excel. See AlphaGo and derivatives. So this isn't just some random gradient descent exploring the full space; a properly designed and trained neural net will effectively cordon off vast swaths of the search space, and suddenly the problem is probably many orders of magnitude more tractable.

That's really why deep learning shines in technical applications. Solution search heuristics were until recently solely within the domain of biological neural networks; now we have created technology which is capable of extracting superior heuristics over the course of learning. And it's already paying off in industrial science, despite the cries of naysayers, though the applications are still in infancy.

There is a vast chasm of computational complexity between Chess, Go, and protein folding, to program induction. Unlike problems where the configuration space grows exponentially, the space of valid programs is at least super-exponential and depending on the language family, (e.g. context free, context sensitive, recursively enumerable), can often be undecidable. Furthermore, many language induction problems do not have optimal substructure or overlapping subproblems, two important prerequisites for reinforcement learning to work. In these settings, gradient-based heuristics will only get you so far.

If you are interested in learning more about the limits of gradient descent, you should look into the TerpreT problem [1]. There are surprisingly tiny Boolean circuits which can be found using constraint solving, but we have not yet been able to learn despite the success of reinforcement learning in other domains. I'm not saying that program induction is impossible, but it is extremely hard even for relative "simple" languages like source code.

[1]: https://arxiv.org/pdf/1608.04428.pdf

Thank you. I just finished my master's thesis in program synthesis/induction. You're explaining this better than I could.

So what do you think is different about human learning that allows us to learn to find solutions in such large spaces?

There are two answers to your question. One is, humans have simply not found very good solutions in these spaces. We have designed algorithms which barely work on denumerable sets, but are unsuitable in more general spaces. There are many decision problems which are known to be undecidable, i.e., there exists no algorithm that decides first order logic propositions. There are fragments which are decidable, and essentially all useful algorithms in CS fall into this category.

The second answer is that we are exploiting statistical regularities in the data which make these problems effectively regular or context-free in practice. When someone asks you to solve a new programming problem, you are applying some heuristics that have worked on similar problems in the past. Given a truly novel problem, you can either make some assumptions to reduce it into a more tractable form (e.g. 3-SAT), or design some clever search heuristic, but without any prior examples of programs or a distribution over probable inputs, you can do no better than naïve search.

>The second answer is that we are exploiting statistical regularities in the data which make these problems effectively regular or context-free in practice. When someone asks you to solve a new programming problem, you are applying some heuristics that have worked on similar problems in the past. Given a truly novel problem, you can either make some assumptions to reduce it into a more tractable form (e.g. 3-SAT), or design some clever search heuristic, but without any prior examples of programs or a distribution over probable inputs, you can do no better than naïve search.

How is this different from training a neural network on a data set and relying on interpolation for inference? Isn't that exactly what neural nets learn, statistical relationships between inputs? After all, isn't that effectively the mathematical definition for a heuristic? You don't know exactly what the solution is, but there are similarities between past examples you've encountered, and these form priors for your shortcut through the solution space.

I'm not sure if neural nets can extrapolate (which would imply searching outside of the training space, i.e. innovating) but if they are truly universal function approximators, I don't see why not. Especially if the solution space is smooth and continuous in the extrapolation range...whatever that means in high D space.

To your first point, it seems you are saying that neither humans or neural networks can solve these intractable problems. It would not surprise me if a massive, well tuned neural net, possibly with yet to be developed components, could discover better heuristics than even an intelligent and experienced human for problems in this class. But that might be optimistic.

> How is this different from training a neural network on a data set and relying on interpolation for inference? Isn't that exactly what neural nets learn, statistical relationships between inputs?

The huge difference is that humans has a rational part of the brain which determines if examples are important to train on or not, doing extremely efficient problem space pruning. And then it trains the neural network in real time using that rational part as guidance. We can't program without the rational part, so computers likely wont able to program without it either. We can read sentences and detect objects in images without the rational parts so ML AI can do that.

We have no idea at all how to build that rational part, without something replacing its role the current methods will just give us extremely primitive parts of human thinking such as image recognition.

AlphaGO actually got a rational part, the code they used to play through the game and see if moves leads to a win. That means that AlphaGO has the full human capability, but for a very limited domain, just GO, the rational part of GO doesn't generalize well to more interesting problems.

And don’t forget that we haven’t even really begun to search the areas that resemble aspects of human neural anatomy. The ultimate heuristic.

Like most anti-AGI arguments, this one disproves humans, and is therefore wrong.

Do humans fit in 10TB? Do humans fit in our computational model at all? Neurons aren't simple callback closures or matrices, and neurons don't even form the full picture.

A lot of the brain is for unrelated things. Imagine how many neurons you eliminate by excluding the cerebellum or the brain stem. And if you carved away the brain until only the intellect remained, distilling its digital equivalent could reduce its size even more. And if it were just the algorithm, I think 10TB would be enough.

>> Do humans fit in 10TB?

> If it were just the algorithm, I think 10TB would be enough

Just thinking about it makes me shiver. I had been assuming that AGI or strong AI needed enormous advances in hardware like quantum computing or numerous iterations of Moore's Law. Would it be correct to say that the right 10TB bit pattern might give us strong AI on today's commodity hardware -- at least in theory?

It’s such a fascinating question. Given some domestic computer, what is the most intelligent program it might be able to run in something like real-time? My intuition is that domestic computers could achieve a sparse intellect but maybe not a rich sensory relationship with the physical world.

With every year we expand our vast collective computational resources. It’s like a powder keg. It’s sitting dormant just waiting for a good program to be stumbled upon. I hope I’m not alive when that happens

Human intelligence is about more than just the brain. How intelligent would you be if you grew up in a sensory deprivation tank? If you didn't need to eat, if you didn't crave social interactions. Without family or community. If you met a human who grew up this way, they might not seem particularly intelligent either.

> more than just the brain

This is objectively wrong

This isn't an anti-AGI argument and it doesn't disprove humans. Humans have the same problem. It's harder to write a program to do a thing than it is to just do the thing.

It's appealing to think we can just make a program that learns programs and then use that to learn to do anything computable. But this is a well studied field and it turns out that when you generalize a learning problem that way you make the learning problem a lot harder.

The space of programs that could possibly.identify dogs in images is much much much larger than the space of images that contain dogs. The images are bounded by the number of pixels in the image times the color depth. What is the space of programs bounded by? 10TB? That's roughly 256^10000000000 programs. That's just a stupidly large number.

Obviously not every 10TB string is a valid program. You can reduce that number. But what current research in program synthesis tells us is that you can't reduce it as much as you might hope.

So the point is that, just like for humans, it's easier to learn to do a thing than it is to learn to write a program to do a thing.

> This isn't an anti-AGI argument and it doesn't disprove humans.

You're saying you can't find intelligent programs this way because the search space is large. That's an anti-AGI argument, and it's fallacious because humans evolved.

Yes, you can only search an infinitesimal subset of the search space. The same is true for DNA. The argument is clearly invalid without at least reference to properties that gradient descent has, or that evolution has but it does not, which you have not done. It is wrong for the same reasons the watchmaker analogy is.

Somewhat off topic, and I ask out of genuine curiosity - when did the “this computation will take sifting through more combinations than there are visible atoms in the universe” meme emerge?

I’ve never quite understood why that’s an important metric for considering processing. Does it have an actual impact on the computability of something, or is it just a visualisation to help human minds scale the grasp of something?

We don't have the words to describe how quickly these nonlinear recurrence relations grow. Many program synthesis problems are essentially super-exponential. Look at the Ackermann function, which describes the complexity of many decidable algorithms as you increase problem size -- it's a different kind of scaling altogether.

It’s a pretty useful concept when you consider cryptography. The idea that enumeration is mathematically infeasible for some set is the basis for many cryptographic functions.

But basically yeah it’s just an illustration of the difficulty. Obviously we’ll never have a supercomputer’s worth of computing power for every atom.

I prefer "sifting through more combinations than there are elementary particles in the universe times the universe's age in picoseconds"; it's a fairly reliable indicator that exhaustive search is not a viable way to solve the problem, not just today but, with classical computing, ever, because it's very unlikely that we can make a working computer out of less than a single elementary particle, try more than one guess per picosecond (per computer), or wait longer than the current age of the universe for an answer. I've seen such calculations at least since the 01990s.

It might turn out to be wrong (for example, elementary particles or black holes might have exploitable structure, a picosecond is pretty long compared to the Planck time, or closed timelike curves in spacetime might allow you to spend an unboundedly long time computing something), but at the very least it's a strong suggestion that exhaustive search will not be fruitful.

For more immediate purposes I prefer the dollar cost of carrying out the computation with currently available hardware.

Quantum computing, when it becomes practical, will give you only a quadratic speedup, as far as we know. So the relevant problem size then expands to the square of the number above.

I definitely like the metric as better fitting, once multiplied by time! Thanks for sharing!

That's a very interesting way of thinking about things, but I think unfortunately the search techniques we are using (gradient descent with certain datasets/self-supervision tasks) limit us to exploring a very small subset of that 10TB of possible programs. A search strategy that could actually find the optimal 10TB program to accomplish some task would actually be a superintelligence beyond anything we have ever thought of creating using present day AI techniques.

Maybe one of the lesser search strategies will find a better search strategy? Isn't that how humans came around after all?

Evolution used an entire planet and billions of years to come up with us.

> find the optimal 10TB program to accomplish some task would actually be a superintelligence

I am having a difficult time understanding what the operative meaning of "intelligence" here is. "AI" doesn't transcend the Turing machine. Intelligence doesn't mean more computer cycles per unit time either and compute cycles don't transcend the TM. What makes intelligence intelligence is what it can in principle do; speed is irrelevant. There is no essential difference between AI and non-AI.

But we want our search strategy to limit us to the infinitesimal fraction of programs that does useful work.

99.99% of possible bit arrangements in that 10TB will not do anything good, or useful, or even anything at all.

The number possible bit arrangements in 10TB is 2 raised to the power of 80 trillion.

This comes out to 3.1 × 10^24082399653118

To emphasize the size of that search space- let us measure the diameter of the observable universe in planck lengths, the shortest possible length. We would need over 24 trillion digits to write the number of universes we would need for the quantity of planck lengths to equal the number of possible programs.

That 99.99% number is missing several billion additional 9s.

Isn’t it incredible then that we have already found so many surprising programs in that set?

We are fortunately not searching that space with brute force.

Meh. Imagine the set of 10k x 10k pixel RGB images. The mona lisa is in there, as are images from your worst nightmares.

But almost all of the images in that set look like grey fuzz. On average there's nothing interesting there.

https://en.wikipedia.org/wiki/The_Library_of_Babel

Sorry I dont follow at all.

Are you stating that you have a corpus of 10TB of software source and you are frankenstiening it with interesting results? I find that hard to believe.. Surely its like Monkeys and typewriters, 10TB in that context wouldnt be nearly enough.

Parent is not talking about a 10TB corpus of software but the corpus/set of all possible software weighing 10TB (or less I guess, specially if you take the lottery ticket hypothesis into consideration).

A sibling post shows this, it presents the concept very well: https://en.wikipedia.org/wiki/The_Library_of_Babel

>Is there something inside that we will regret?

Unambiguously yes. 10TB is a lot of space. That's large enough for a program that does nothing but show 8 hours of HD footage of your kids being tortured and eaten.

It's also more than enough to define a program that would reliably precipitate a global thermonuclear war if connected to the Internet.

In order to search that space you have to have a specification language for the behavior of the target program. Things like copilot/GPT-3 currently take natural language as input, but that cannot be used for anything that needs to be verifiable or have correctness. Maybe start by having the nets generate implementations of the IETF RFCs in a variety of languages given the text of the RFC as input? Not easy.

Reply on news.ycombinator.com