Competitive Programming with AlphaCode • Hacker News Board

Re: Competitive Programming with AlphaCode

#411

Post by YorkshireSeason » Sun, Feb 06, 2022, 9:00 PM UTC

YeGoblynQueenne wrote: post #408

ahgamut wrote: post #404

Earlier quoted context omitted.

Could you provide some papers/link related to Inductive Logic Programming? I'd like to look at other techniques in this space.

My pleasure! - 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/Proce…

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.

[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...

Re: Competitive Programming with AlphaCode

#412

Post by YeGoblynQueenne » Mon, Feb 07, 2022, 12:00 AM UTC

YorkshireSeason wrote: post #411

YeGoblynQueenne wrote: post #408

Earlier quoted context omitted.

My pleasure! - 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/Proce…

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. [1] Feser et al's Lambda-Learner https://www.cs.utexas.edu/~swarat/pubs/pldi15.pdf [2] S. Katayama's MagicHaskeller http://nautilus.cs.miyaza…

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.

Re: Competitive Programming with AlphaCode

#413

Post by cjbprime » Mon, Feb 07, 2022, 7:29 AM UTC

zwaps wrote: post #266

cjbprime wrote: post #263

Earlier quoted context omitted.

> 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.

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.

Re: Competitive Programming with AlphaCode

#414

Post by YorkshireSeason » Mon, Feb 07, 2022, 12:46 PM UTC

YeGoblynQueenne wrote: post #412

YorkshireSeason wrote: post #411

Earlier quoted context omitted.

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. [1] Feser et al's Lambda-Learner https://www.cs.utexas.edu/~swarat/pubs/pldi15.pdf [2] S. Katayama's MagicHaskeller http://nautilus.cs.miyaza…

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,…

> ILP to order programs by generality

Sorry, naive question: does ILP test candidate programs by increasing or decreasing generality?

Re: Competitive Programming with AlphaCode

#415

Post by YeGoblynQueenne » Mon, Feb 07, 2022, 7:41 PM UTC

YorkshireSeason wrote: post #414

YeGoblynQueenne wrote: post #412

Earlier quoted context omitted.

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,…

> ILP to order programs by generality Sorry, naive question: does ILP test candidate programs by increasing or decreasing generality?

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.