Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Competitive Programming with AlphaCode

deepmind.com

Post reply on HN
Print view View original

401–410 of 415 posts

Re: Competitive Programming with AlphaCode

#401

Post by bglazer »

YeGoblynQueenne wrote: post #368
bglazer wrote: post #328

Earlier quoted context omitted.

That’s not entirely correct, as I know of at least one approach to neural program synthesis that employs self supervised learning. https://arxiv.org/abs/2006.08381 It’s a slightly different, easier problem: generating programs based on example outputs, rather than natural language specifications.

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.

Re: Competitive Programming with AlphaCode

#402

Post by EliasY »

Enginerrrd wrote: post #127
diehunde wrote: post #39

Earlier quoted context omitted.

My bet would be that it will never happen in a reasonable time frame. And also by that logic, writing that "documentation/spec" would just mean learning a new programming language the AI engine can parse making it as useful as a compiler. Anyone who has been writing and designing software for a while knows the cycle is way more complex than take some input and write code. Let me know when the AI engine is able to do…

I agree, from a totally different angle. Let's take something I know better as an example: Structural engineering. Structural engineering should be a "solved problem". It seems, ostensibly, relatively simple compared to a more open ended activity like "programming".(For "technical reasons", it ends up being more similar than you might think.) Still, you are ultimately dealing with the same materials, the same physics…

As a former structural engineer, I completely agree with this sentiment. For every engineering project I was involved in, the automated components were at most 2 to 5% of the rest of the work.

Re: Competitive Programming with AlphaCode

#403

Post by YeGoblynQueenne »

bglazer wrote: post #401
YeGoblynQueenne wrote: post #368

Earlier quoted context omitted.

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

Re: Competitive Programming with AlphaCode

#404

Post by ahgamut »

YeGoblynQueenne wrote: post #403
bglazer wrote: post #401

Earlier quoted context omitted.

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

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

Re: Competitive Programming with AlphaCode

#405

Post by wittycardio »

jdlshore wrote: post #237
wittycardio wrote: post #159

Earlier quoted context omitted.

That's not programming, that's called being a good employee. Any person in any role should be doing that. Programming is about algorithms and math. Now a good employee who's in a technical role should have both.

> Programming is about algorithms and math. You've simply restated your opinion without providing any supporting arguments, and as I already said, I disagree. The vast majority of programming I see (and as a consultant, I see a fairly wide variety) is not about algorithms and math, but instead gluing together systems and expressing domain logic. Now, I suppose you could argue that domain logic is "algorithms and math…

No I'm not talking about programming that requires calculations or programs written to solve mathematical problems. Programming at its core is about defining precise logical relationships between abstract objects and then writing algorithms to understand and modify these objects. This is a mathematical process and you should use mathematical thinking to do this.It may not always seem like it when the objects and relationships appear to be simple but that is the core of programming.

Re: Competitive Programming with AlphaCode

#406

Post by machiaweliczny »

algon33 wrote: post #400
machiaweliczny wrote: post #156

Earlier quoted context omitted.

I am surprised, as recently OpenAI had ~25% of easy problems and ~2% in competitive problems. Seems like DeepMind is ahead in this topic as well. Actually I think Meta AI had some interesting discovery recently that could possibly improve NNs in genral, so probably this as well. I am not in field but wonder if some other approaches like Tsetlin machines would be more useful for programming.

Somehow I have never heard of Tsetlin machines before this. Are you talking about this https://ai.facebook.com/blog/the-first-high-performance-self... result by MetaAI?

Probably not. Tsetlin machines have logic expressions instead of weights in NN, so it's easy to interpret them. I guess some meta algorithm could maybe work on top of them.

https://arxiv.org/abs/2102.10952

EDIT: Missread, I meant this from meta https://arxiv.org/abs/2105.04906 - not sure how much it's productised

Re: Competitive Programming with AlphaCode

#407

Post by nonameiguess »

atleta wrote: post #286
doctor_eval wrote: post #267

I sometimes read these and wonder if I need to retrain. At my age, I’ll struggle to get a job at a similar level in a new industry. And then I remember that the thing I bring to the table is the ability to turn domain knowledge into code. Being able to do competitive coding challenges is impressive, but a very large segment of software engineering is about eliciting what the squishy humans in management actually want…

The thing is that we don't know. What I also have been seeing for a while (like for at least for a decade) that whatever profession seemed to be in danger, whichever profession came out on top on (guess) lists like "these will be replaced by AI soon", each and every one of them thought that it can't happen to them and they all had (and continue to have) explanations, usually involving how that jobs needs human ingenu…

What professions are these? Chat bots didn't eliminate human CSRs. OCR didn't eliminate human data entry. Object detection hasn't eliminated human intelligence analysts. Machine translation hasn't eliminated human translators. Humans still make a living as professional Chess and Go players. Truck drivers were supposed to be on the chopping block a decade ago, yet they're more in demand now than ever. Human radiologists haven't gone anywhere. Even GPT-N hasn't eliminated human writers. Human transcriptionists haven't even been eliminated. We just have a lot more videos that automatically get shitty transcriptions instead of none at all now.

Re: Competitive Programming with AlphaCode

#408

Post by YeGoblynQueenne »

ahgamut wrote: post #404
YeGoblynQueenne wrote: post #403

Earlier quoted context omitted.

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…

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/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 :)

Re: Competitive Programming with AlphaCode

#409

Post by ahgamut »

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…

Thank you so much!

Re: Competitive Programming with AlphaCode

#410

Post by TOMDM »

noduerme wrote: post #353
FiberBundle wrote: post #217

It never ceases to amaze me what you can do with these transformer models. They created millions of potential solutions for each problem, used the provided examples for the problems to filter out 99% of incorrect solutions and then applied some more heuristics and the 10 available submissions to try to find a solution. All these approaches just seem like brute-force approaches: Let's just throw our transformer on thi…

>> filter out 99% of incorrect solutions And next year they can filter out 99.99%. And the year after that, 99.9999%. So literally, an exponentially greater number of monkey/typewriting units. (An AI produced Shakespeare play coming soon). >> we have no clue at all what that actually is and how these model learn This is why I'm super cool-to-cold about the AI/deep learning classes being sold to young people who would…

Surely if your discrimintator gets orders of magnitude better like your describing, we could train the transformer GAN style, and reduce the dependence on generating so many examples to throw away.
Post reply on HN