Well with respect to Go the fundamental difference afaict is that you can apply self-supervised learning, which is an incredibly powerful approach (But note e.g. that even this approach wasn't successful in "solving" Starcraft). Unfortunately it's extremely difficult to frame real-world problems in that setting. I don't know anything about protein-folding and don't know what Deepmind uses to try to solve that problem, so I cannot comment on that.
> this approach wasn't successful in "solving" Starcraft)
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.
"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"
What if that's why they cut it off..
I think the GP means that the AlphaStar team stopped working on the project because they felt it was reaching a dead end and unlikely to produce further results, or at least other ventures might have been more promising.
I think that's most likely the case too, otherwise why would they give up?
I guess I feel that there is a big discontinuous jump between "not clearly better than humans" and "clearly better than humans," where the latter is much, much more significant than the former. It seems like going on a hike and stopping before the summit.
I looked into this again and the hotkey situation seems more unclear than I suggested. You could not log into your Battle.net account, so it would have been somewhat time consuming to change all of your settings manually. If I had to guess, I might wager that Serral changed some of the more important ones manually but not the others, but this is just conjecture and maybe he changed all of them. I don't know if anyone but Serral would know this, however.
In any case, Serral said this, which you can take as you will:
"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.
Not once humans adapted to it afaik. AlphaStar got to top grandmaster level and then that was it, as people found ways to beat it. Now, it may be that the team considered the project complete and stopped training it. But technically - as it stands - Starcraft is still the one game where humans beat AI.
No, the version which played on ladder was much weaker than the later version which played against pros and was at BlizzCon -- the later version was at professional level of play.
There were numerous issues. First one (somewhat mitigated lately) was extremely large number of actions per minute and (most importantly) extremely fast reaction speed.
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.
The difference is that DreamCoder has a hand-crafted PCFG [1] that is used to generate programs, rather than a large language model. So the difference is in how programs are generated.
________
[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.
Right, I think it’s a bit crazy not to use a grammar as part of the generation process when you have one. My guess is that constraining LLM generation with a grammar would make it way more efficient. But that’s more complicated than just throwing GPT3 at all of Github.
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.
I guess you're right. The sleep-wake cycle is like a kind of roundabout and
overcomplicated EM process. I've read the paper carefully but theirs is a
complicated approach and I'm not sure what its contributions are exactly. I
guess I should read it again.
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.
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)
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 :)
It should be emphasised that inductive programming is not tied to logic programming, and works for every other programming paradigm as well, e.g.
functional programming [1, 2]. We could also do IP for imperative programming, although, as far as I am aware, nobody has done this.
That's absolutely true! But the OP asked about ILP in particular.
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.
Not naive at all! One common categorisation of ILP approaches is by whether they search for programs from the most to the least general (least general is more specific), or from the least to the most general. Some approaches do a little bit of both. Approaches that search from general to specific are known as "top-down" and approaches that search from specific to general are known as "bottom-up".
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.
