Yes, it's the size of the search space for each problem. The search space for arbitrary programs in a language with Universal Turing Machine expressivity is infinite. Even worse, for any programming problem there are an infinite number of candidate programs that may or may not solve it and that differ in only minute ways from each other.
For Go and protein structure prediction from sequences the search space is finite, although obviously not small. So there is a huge difference in the complexity of the problems right there.
Btw, I note yet again that AlphaCode performs abysmally badly on the formal benchmark included in the arxiv preprint (see Section 5.4, and table 10). That makes sense because AlphaCode is a very dumb generate-and-test, brute-force search approach that doesn't even try to be smart and tries to make up for the lack of intelligence with an awesome amount of computational resources. Most work in program synthesis is also basically a search through the space of programs, but people in the field have come up with sophisticated techniques to avoid having to search an infinite number of programs- and to avoid having to generate millions of program candidates, like DeepMind actually brags about:
At evaluation time, we create a massive amount of C++ and Python programs for each problem, orders of magnitude larger than previous work.
They say that as if generating "orders of magnitude more" progams than previous work is a good thing, but it's not. It means their system is extremely bad at generating correct programs. It is orders of magnitude worse than earlier systems, in fact.
(The arxiv paper linked from the article quantifies this "massive" amount as "millions"; see Section 4.4).
Why do you say that? As I understand it, AlphaStar beat pros consistently, including a not widely reported showmatch against Serral when he was BlizzCon champ.
1. First, though I am not sure of this (i.e. this should be verified), I heard that the team working on AlphaStar initially tried to create a Starcraft AI entirely through "self-play," but this was not successful. (Intuitively, in a real-time game, there are too many bad options too early on that even with a LOT of time to learn, if your approach is too "random" you will quickly enter an unwinnable position and not learn anything useful.) As a result, they replaced this approach with an approach which incorporated learning from human games.
2. "including a not widely reported showmatch against Serral when he was BlizzCon champ." is a mischaracterization. It was not a "showmatch," rather there was a setup at Blizzcon where anyone could sit down and play against AlphaStar, and Serral at some point sat down to play AlphaStar there. He went 0-4 vs AlphaStar's protoss and zerg, and 1-0 vs its Terran. However, not only was he not using his own keyboard and mouse, but he could not use any custom hotkeys. If you do not play Starcraft it may not be obvious just how large of a difference this could make. BTW, when Serral played (perhaps an earlier iteration of) AlphaStar's terran on the SC2 ladder, he demolished it.
I remember when seeing the final report, I was a bit disappointed. It seemed like they cut the project off at a strange point, before AlphaStar was clearly better than humans. I feel that if they had continued they could have gotten to that point, but now we will never know.
IIRC you could and Serral did set his own custom keybindings on the machine. The main difference was different keyboard and mouse.
In any case, Serral said this, which you can take as you will:
https://twitter.com/ENCE_Serral/status/1192023800961019904
"It was okay, I doubt i would lose too many games with a proper setup. I think the 6.3-6.4 mmr is pretty accurate, so not bad at all but nothing special at the same time."
On the one hand, surely it doesn't seem surprising that the player who lost, the human, would say the above, and so one may be skeptical of how unbiased Serral's assessment is. On the other hand, I would say that Serral is among the more frank and level-headed players I've seen in the various videogames I've followed, so I wouldn't be too hasty to write off his assessment for this reason.
I think that's most likely the case too, otherwise why would they give up?
Another big issue is that the bot communicated with the game via a custom API, not a via images and clicks. Details of this API are unknown - like how invisible units were handled, but it was much higher level than a human would have (pixels).
If you look at the games, the bot wasn't clever (which was a hope), just fast and precise. And some people far from the top were able to beat it convincingly.
And now the project is gone, even before people had a chance to really play against the bot and find more weaknesses.
https://arxiv.org/abs/2006.08381
It’s a slightly different, easier problem: generating programs based on example outputs, rather than natural language specifications.
________
[1] The structure of the PCFG is hand-crafted, but the weights are trained during learning in a cycle alternating with neural net training. It's pretty cool actually, thought a bit over-engineered if you ask me.
Also, my understanding is that Dreamcoder does some fancy PL theory stuff to factorize blocks of code with identical behavior into functions. Honestly I think that’s the key advance in the paper, more than the wake-sleep algorithm they focus on.
Anyways the point was more that self supervised learning is quite applicable to learning to program. I think the downside is that the model learns its own weird, non-idiomatic conventions, rather than copying github.
Yes, it's possible to apply self-supervised learning to program synthesis, because it's possible to generate programs. It's possible to generate _infinite_ sets of programs. The problem is that if you make a generator with Universal Turing Machine expressivity, you're left with an intractable search over an infinite search space. And if you don't generate an infinite set of programs, then you 're left with an incomplete search over a space that may not include your target program. In the latter case you need to make sure that your generator can generate the programs you're looking for, which is possible, but it limits the approach to only generating certain kinds of programs. In the end, it's the easiest thing to create a generator for progams that you already know how to write- and no others. How useful is that is an open question. So far no artificial system has ever made an algorithmic contribution, to my knowledge, in the sense of coming up with a new algorithm for a problem for which we don't have good algorithms, or coming up with an algorithm for a problem we can't solve at all.
My perception is influenced by my studies, of course, but for me, a more promising approach than the generate-and-test approach exemplified by DreamCoder and AlphaCode etc. is Inductive Programming, which is to say, program synthesis from input-output examples only, without examples of _programs_ (the AlphaCode paper says that is an easier setting but I very disagree). Instead of generating a set of candidate programs and trying to find a program that agrees with the I/O examples, you have an inference procedure that generates _only_ the programs that agree with the I/O examples. In that case you don't need to hand-craft or learn a generator. But you do need to impose an inductive bias on the inference procedure that restricts the hypothesis language, i.e. the form of the programs that can be learned. And then you're back to worrying about infinite vs. incomplete search spaces. But there may be ways around that, ways not available to purely search-based systems.
Anyway program synthesis is a tough nut to crack and I don't think that language models can do the job, just like that. The work described in the article above, despite all the fanfare about "reasoning" and "critical thinking" is only preliminary and its results are not all that impressive. At least not yet. We shall see. After all, DeepMind has deep resources and they may yet surprise me.
- First, some more recent work, mostly overviews.
1. The following is the most recent overview of the field I'm aware of:
Inductive logic programming at 30 (Cropper et al, 2020)
https://www.doc.ic.ac.uk/~shm/Papers/ilp30.pdf
2. And a slightly shorter version of the same paper that summarises new trends:
Turning 30: New Ideas in Inductive Logic Programming (Cropper et al, 2020)
https://www.ijcai.org/Proceedings/2020/0673.pdf
3. Here's a short introduction to the relatively new ILP direction of learning Answer Set Programming:
Inductive Logic Programming in Answer Set Programming (Corapi et al, 2011)
https://link.springer.com/chapter/10.1007/978-3-642-31951-8_...
4. This is an overview of Meta-Interpretive Learning (MIL), a new approach to ILP that overcomes many difficulties of earlier approaches (Full disclosure: my own work is on MIL, though not the article linked):
Meta-Interpretive Learning: achievements and challenges (Stephen Muggleton, 2017)
https://www.doc.ic.ac.uk/~shm/Papers/rulemlabs.pdf
5. And this is a (short vesion) of a paper on δILP, a neural-net based ILP system:
Learning Explanatory Rules from Noisy Data (Evans and Grefenstette, 2018)
https://www.ijcai.org/Proceedings/2018/0792.pdf
- Next, some earlier work that is still relevant:
6. This is the inaugural paper of the field, that first named it (a little heavy reading though):
Inductive Logic Programming (Stephen Muggleton, 1990)
https://www.doc.ic.ac.uk/~shm/Papers/ilp.pdf
7. Here's an early paper on predicate invention, an important technique in ILP (only recently fully realised via MIL):
Predicate Invention in ILP - an Overview (Irene Stahl, 1993)
https://link.springer.com/chapter/10.1007%2F3-540-56602-3_14...
8. And an early overview of learning recursion (and performing predicate invention) that also lists several early ILP systems:
Inductive synthesis of recursive logic programs:achievements and prospects (Flener and Yilmaz, 1999)
https://core.ac.uk/download/pdf/82810434.pdf
That should be enough to get you started. I recommend reading in the order I linked to the various articles. I tried to give links to documents that I know can be read for free.
Unfortunately most of the material on ILP is either in scholarly articles, or, where there are textbooks, they tend to be older. That sounds bad, but there has been much new work recently with several new approaches.
Let me know if you're looking for more specific information. See my signature for contact details- I'm happy to answer emails about ILP :)
[1] Feser et al's Lambda-Learner https://www.cs.utexas.edu/~swarat/pubs/pldi15.pdf
[2] S. Katayama's MagicHaskeller http://nautilus.cs.miyazaki-u.ac.jp/~skata/MagicHaskeller.ht...
To be fair, logic and functional programming languages do have some advantages as target languages for Inductive Programming compared to imperative languages in that they have very simple syntax. For example, Prolog doesn't even have variable declarations. That's very convenient because the learning system only needs to learn the logic of the program, not the syntax of the language also. It's also much simpler to define language bias or program schemata etc constraints on the form of hypotheses in such languages, or even order programs by generality. For instance, Prolog has unification built-in and unification is used in ILP to order programs by generality (by testing for subsumption). All this machinery would have to be implemented from scratch in an imperative language.
Although the reason that logic and functional programming languages are given more weight in IP is probably for historical reasons, because Lisp and Prolog were, for a long time, "the languages of AI".
I'm trying to remember... I think there's been some IP work on imperative languages, maybe even Python. I'll need to check my notes.
Sorry, naive question: does ILP test candidate programs by increasing or decreasing generality?
The "top" and "bottom" terms refer to a lattice of generality between programs, where generality is typically measured by subsumption or entailment etc. Subsumption in particular is a syntactic relation (that implies a semantic one, entailment) so "searching" a space of logic programs ordered by subsumption means in practice that the space of programs is constructed by generalising or specialising some starting program by means of syntactic transformation according to subsumption (e.g. a first order clause can be specialised by adding literals to it: P(x):- Q(x) subsumes P(x):- Q(x), R(x). The simplest intuition is to remember that by adding more conditions to a rule we make it harder to satisfy).
A more general program entails more logical atoms and ILP algorithms are typically trained on both positive and negative example atoms of a target program, so top-down approaches begin with an over-general program that entails all the positive examples and some or all of the negative examples and specialise that program until it entails only the positive examples. Bottom-up approaches start with an over-specialised program that entails none of the positive examples and generalise it until it entails all the positive examples.
The mathematics of generalisation are at the core of ILP theory and practice. It's what sets ILP apart from statistical machine learning which is based on the mathematics of optimisation.