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

361–370 of 415 posts

Re: Competitive Programming with AlphaCode

#361

Post by machiaweliczny »

sibeshk96 wrote: post #249
pedrosorio wrote: post #245

Earlier quoted context omitted.

> Suppose the models were trained only on greedy algorithms and then I provided a dynamic programming problem in the test set, (how) would the model solve it? How many human beings do you personally know who were able to solve a dynamic programming problem at first sight without ever having seen anything but greedy algorithms? Deepmind is not claiming they have a machine capable of performing original research here.…

> that is AI above and beyond what many humans can do, which is "awesome" no matter how you put it. That's not the point being made. The point OP is making is that it is not possible to understand how impressive at "generalizing" to uncertainty a model is if you don't know how different the training set is from the test set. If they are extremely similar to each other, then the model generalizes weakly (this is also…

I guess weaker generalisation is why it's better though. It converges slower but in the end it knowledge is more subtle. So my bet is more compute and programing and math is "solved" - not in research sense but very helpful "copilot".

The real fun will begin once someone discovers how to make any problem differentiable so try/error method isn't needed. I suggest watching recent Yann Le Cun interview. This will solve researching as well.

Re: Competitive Programming with AlphaCode

#362

Post by YeGoblynQueenne »

Mehdi2277 wrote: post #360
YeGoblynQueenne wrote: post #258

Earlier quoted context omitted.

Program synthesis from natural language specifications has existed for many years, also. It's not my specialty (neither am I particularly interested in it), but here's a paper I found from 2017, with a quick search: https://www.semanticscholar.org/paper/Program-Synthesis-from... AlphaCode is not particularly good at it, either. In the arxiv preprint, besides the subjetive and pretty meaningless "evaluation" against h…

I've also worked in the area and published research in it a couple years ago. I almost worked for a company focused on neural program synthesis but they did a large pivot and gave up a couple years ago working on much simpler problems and decided that current research was not good enough to do well on problems like this. I had a paper accepted that translated between toy programming languages 3ish years ago. Toy here…

I don't agree. I don't know your work, but the approach in AlphaCode and Copilot (or the Codex model behind it) is a step backwards for neural program synthesis, and for program synthesis in general. The idea is to train a large language model to generate code. The trained language model has no way to direct its generation towards code that satisfies a specification. It can only complete source code from some initial prompt. The code generated is remarkably grammatical (in the context of a programming language grammar) which is certainly an advance for language representation, but some kind of additional mechanism is required to ensure that the generated code is relevant to the specification. In Copilot, that mechanism is the user's eyballs. In AlphaCode the mechanism is to test against the few I/O examples of the programming problems. In either case, the whole thing is just hit-and-miss. The language model generates mostly garbage -DeepMind brags that AlphaCode generates "orders of magnitude" more code than previous work, but that's just to say that it's even more random, and its generation misses the target even more than previous work! Even filtering on I/O examples is not enough to control the excessive over-generation and so additional measures are needed (clustering and ranking of programs etc).

All this could be done 40 years ago with a dumb DSL, or perhaps a more sophisticated system like a PCFG for programs, with a verifier bolted on [1]. It's nothing new. What's new is that it's done with a large language model trained with a Transformer, which is all the rage these days, and of course that it's done at the scale and with the amount of processing power available to DeepMind. Which I'm going to assume you didn't have back when you published your work.

Honestly, this is just an archaic, regressive approach, that can only work because of very big computers and very big datasets.

___________

[1] Which btw, is straightforard to do "by hand" and is something that people do all the time. In the AlphaCode work, the large language model simply replaces a hand-crafted program generator with a lot of data, but there is no reason to do that. This is the quintessential problem where a machine learning solution is not necessary because a hand-crafted solution is available, and easier to control.

Re: Competitive Programming with AlphaCode

#363

Post by Mehdi2277 »

YeGoblynQueenne wrote: post #362
Mehdi2277 wrote: post #360

Earlier quoted context omitted.

I've also worked in the area and published research in it a couple years ago. I almost worked for a company focused on neural program synthesis but they did a large pivot and gave up a couple years ago working on much simpler problems and decided that current research was not good enough to do well on problems like this. I had a paper accepted that translated between toy programming languages 3ish years ago. Toy here…

I don't agree. I don't know your work, but the approach in AlphaCode and Copilot (or the Codex model behind it) is a step backwards for neural program synthesis, and for program synthesis in general. The idea is to train a large language model to generate code. The trained language model has no way to direct its generation towards code that satisfies a specification. It can only complete source code from some initial…

I agree the approach itself is quite brute force heavy. There is a lot of information that could be used and I’d hope is helpful like grammar or language, traces/simulations of behavior, etc.

But when I say alpha code/copilot is good I’m referring solely to the difficulty of problems they are doing. There are many papers including mine that worked on simpler problems with more structure used to work on them.

I expect follow up work will include actually incorporating other knowledge more heavily to the model. My work was mainly on restricting tree like models to only make predictions following grammar of the language. Does that parallelize/fit well with a transformer? Unsure, but I would expect some language information/genuine problem constraints to be incorporated in future work.

Honestly I am pretty surprised how far pure brute force with large model is going. I would not have expected gpt3 level language modeling from more scale on a transformer and little else.

Re: Competitive Programming with AlphaCode

#364

Post by hnfong »

noduerme wrote: post #354
Vetch wrote: post #305

Earlier quoted context omitted.

> Imagine if real programmer needed to write a solution a hundred times To be fair, a lot of creative work requires plenty of trial and error. And since no problems are solved from scratch, all things considered, the most immediate contributors to your result and you might have iterated through tens of dozens of possibilities. My advantage as a human is I can often tell you why I am eliminating this branch of the sea…

>> While lots of commenters seem concerned about jobs, I look forward to having the dataset oliphaunt and ship computer from Fire Upon Deep someday soon. I think this is more worthy of debate than anything about DSL models or current limits to problem spaces. I'm not concerned about my job, but I am concerned about a world where corporate money starts shifting toward managing AIs as beasts rather than coding clever s…

"Understanding the code" might not be that big of a deal as you might think -- we have this problem today already. A talented coder might leave the company and the employer may not be able to hire a replacement who's as good. Now they have to deal with some magic in the codebase. I don't hear people giving advice not to hire smart people.

At least with AI, you can (presumably) replicate the results if you re-run everything from the same state.

There's also a very interesting paragraph in the paper (I'm in no position to judge whether it's valid or not) that touches on this subject, but with a positive twist :

Interpretability. One major advantage of code generation models is that code itself is relatively interpretable. Understanding the behavior of neural networks is challenging, but the code that code generation models output is human readable and can be analysed by traditional methods (and is therefore easier to trust). Proving a sorting algorithm is correct is usually easier than proving a network will sort numbers correctly in all cases. Interpretability makes code generation safer for real-world environments and for fairer machine learning. We can examine code written by a human-readable code generation system for bias, and understand the decisions it makes.

Re: Competitive Programming with AlphaCode

#365

Post by sireat »

baobabKoodaa wrote: post #351
zbobet2012 wrote: post #348

Earlier quoted context omitted.

They used the tests. The specification being very approximate is fine, because they had a prebuilt way to "check" if their result was good.

Wait what, they cheated to get this result? Only pretests are available to competitors before submitting. If they had access to the full test suite, then they had a HUGE advantage over actual competitors, and this result is way less impressive than claimed. Can you provide a source for this claim? I don't want to read the full paper.

If AlphaCode had access to full test suite then the result is not surprising at all.

You can fit anything given enough parameters.

https://fermatslibrary.com/s/drawing-an-elephant-with-four-c...

Re: Competitive Programming with AlphaCode

#366

Post by HeavyStorm »

GuB-42 wrote: post #304
atleta wrote: post #286

Earlier quoted context omitted.

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…

I think programmers are relatively "safe" from AI for the simple reason they are the ones who talk to AI. The job of programmers is to have machines do stuff so that humans don't have to, and of course, they do it for themselves too. Scripts, libraries, compilers, they are just tools to avoid flipping bits by hand. If something like copilot is not embraced by all programmers, it is that it is often less than helpful,…

Problem is, to "talk with AI", most developers would need to 'retrain' (to use GP's word).

Writing and training a neural network is very different from writing a common program.

Re: Competitive Programming with AlphaCode

#367

Post by hnfong »

briga wrote: post #336
Vetch wrote: post #305

Earlier quoted context omitted.

> Imagine if real programmer needed to write a solution a hundred times To be fair, a lot of creative work requires plenty of trial and error. And since no problems are solved from scratch, all things considered, the most immediate contributors to your result and you might have iterated through tens of dozens of possibilities. My advantage as a human is I can often tell you why I am eliminating this branch of the sea…

>The limitations to GPT3 codex and AlphaCode seems to be they're relatively weak at selection This really does seem like the key here--the knowledge apparently is all in the language model, we just haven't found the best ways to extract that knowledge in a consistent and coherent manner. Right now it's just: generate a bunch of examples and cherry pick the good ones.

The way you put it sounds so like the P?=NP problem:

If it's easy to tell whether a solution is valid, is it also easy to generate it?

Re: Competitive Programming with AlphaCode

#368

Post by YeGoblynQueenne »

bglazer wrote: post #328
FiberBundle wrote: post #242

Earlier quoted context omitted.

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…

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.

Re: Competitive Programming with AlphaCode

#369

Post by hnfong »

gavagai691 wrote: post #315
fuy wrote: post #303

Earlier quoted context omitted.

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

Apologies, I don't quite follow your reasoning.

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?

Re: Competitive Programming with AlphaCode

#370

Post by usrbinbash »

pedrosorio wrote: post #227
ahgamut wrote: post #206

I find almost every new advance in deep learning is accompanied by contrasting comments: it's either "AI will soon automate programming/ ", or "let me know when AI can actually do ". There are many views on this spectrum, but these two are sure to be present in every comment section. IIUC, AlphaCode was trained on Github code to solve competitive programming challenges on Codeforces, some of which are "difficult for…

> Suppose AlphaCode was trained on Github code that contains the entire set of solutions on Codeforces, is it actually doing anything "difficult"? They tested it on problems from recent contests. The implication being: the statements and solutions to these problems were not available when the Github training set was collected. From the paper [0]: "Our pre-training dataset is based on a snapshot of selected public Git…

> The implication being: the statements and solutions to these problems were not available when the Github training set was collected.

But similar ones were, because the amount of code puzzles suitable for such contests is finite. There are differences, but when you have seen a few string-compare problems, you have a pretty good grasp of what they look like, what common paths to solutions are, etc.

Post reply on HN