Competition-Level Code Generation with AlphaCode (Paper Review)

#ai #alphacode #deepmind
AlphaCode is an automated system that can solve competitive programing exercises. The authors found an interesting combination of language models, large-scale sampling, and clever techniques to filter and subsequently cluster the resulting programs, which lets the system perform on the level of an average competitor in real competitions. In this video, we take a deep dive into AlphaCode's design, architecture, and experimental evaluation. The paper is very well structured and the empirical results are super interesting!
OUTLINE:
0:00 - Intro
2:10 - Paper Overview
3:30 - An example problem from competitive programming
8:00 - AlphaCode system overview
14:00 - Filtering out wrong solutions
17:15 - Clustering equivalent generated programs
21:50 - Model configurations & engineering choices
24:30 - Adding privileged information to the input & more tricks
28:15 - Experimental Results (very interesting!)
Paper: storage.googleapis.com/deepmi...
Code: github.com/deepmind/code_cont...
Abstract: Programming is a powerful and ubiquitous problem-solving tool. Developing systems that can assist programmers or even generate programs independently could make programming more productive and accessible, yet so far incorporating innovations in AI has proven challenging. Recent large-scale language models have demonstrated an impressive ability to generate code, and are now able to complete simple programming tasks. However, these models still perform poorly when evaluated on more complex, unseen problems that require problem-solving skills beyond simply translating instructions into code. For example, competitive programming problems which require an understanding of algorithms and complex natural language remain extremely challenging. To address this gap, we introduce AlphaCode, a system for code generation that can create novel solutions to these problems that require deeper reasoning. Evaluated on recent programming competitions on the Codeforces platform, AlphaCode achieved on average a ranking of top 54.3% in programming competitions with more than 5,000 participants. We found that three key components were critical to achieve good and reliable performance: (1) an extensive and clean competitive programming dataset for training and evaluation, (2) large and efficient-to-sample transformer-based architectures, and (3) large-scale model sampling to explore the search space, followed by filtering based on program behavior to a small set of submissions.
Authors: Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, Rémi Leblond, Tom Eccles, James Keeling, Felix Gimeno, Agustin Dal Lago, Thomas Hubert, Peter Choy, Cyprien de Masson d’Autume, Igor Babuschkin, Xinyun Chen, Po-Sen Huang, Johannes Welbl, Sven Gowal, Alexey Cherepanov, James Molloy, Daniel J. Mankowitz, Esme Sutherland Robson, Pushmeet Kohli, Nando de Freitas, Koray Kavukcuoglu and Oriol Vinyals
Links:
Merch: store.ykilcher.com
TabNine Code Completion (Referral): bit.ly/tabnine-yannick
KZbin: / yannickilcher
Twitter: / ykilcher
Discord: / discord
BitChute: www.bitchute.com/channel/yann...
LinkedIn: / ykilcher
BiliBili: space.bilibili.com/2017636191
If you want to support me, the best thing to do is to share out the content :)
If you want to support me financially (completely optional and voluntary, but a lot of people have asked for this):
SubscribeStar: www.subscribestar.com/yannick...
Patreon: / yannickilcher
Bitcoin (BTC): bc1q49lsw3q325tr58ygf8sudx2dqfguclvngvy2cq
Ethereum (ETH): 0x7ad3513E3B8f66799f507Aa7874b1B0eBC7F85e2
Litecoin (LTC): LQW2TRyKYetVC8WjFkhpPhtpbDM4Vw7r9m
Monero (XMR): 4ACL8AGrEo5hAir8A9CeVrW8pEauWvnp1WnSDZxW7tziCDLhZAGsgzhRQABDnFy8yuM9fWJDviJPHKRjV4FWt19CJZN9D4n

[@fireclub493]

Love this new format. I missed the longer paper reviews!!

[@p-51d95]

Yannic, these paper reviews along with the authors' interviews are gold! Incredible time savings in that they filter for some of the most important ML papers and provide a great intro to understanding the paper as well. The authors' interviews provide additional insight. Thanks!!!

[@brandonheaton6197]

Fantastic adding the correction with nuanced discussion. If professors were willing to do that with their video lectures the quality of Academia would improve. Great example

[@TheGodSaw]

Reeeaaally like this format.

[@sanjayvenkat8443]

Paper + interviews one after the other is an awesome format.

[@alexandrei1176]

This format is great!

[@mgostIH]

18:00 Sounds like we need a machine learning approach for graph isomorphism too 😎

[@SLAM2977]

Back in top shape!!:)

[@hannesstark5024]

Nice!

[@quadmasterXLII]

Curious to see the distribution of programmers among which this ai got 55th percentile. If it's like any distribution of programmers I've ever met, 55th percentile is "can usually fizzbuzz"

[@timothy-ul9wp]

The idea of ranking solutions reminds me of the DreamCoder paper, where the NN is used for guiding heuristic search This (coding problem) could be an interesting comparison between the (semi?) symbolic approach and full encoder-decoder

[@asnaeb2]

Crazy to think AI can reverse linked lists now.

[@brandomiranda6703]

val loss increasing is a very typical well-known behaviour (nothing to do with overfitting) if your using cross-entropy like losses. Check paper by Nathan serebro or some of mine perhaps we discuss it somewhere. But if your train error is zero already and you have a mistake in the val, your model to make the train loss zero will increase the weight size and that is reflected in the val loss.

[@OwenIngraham]

quick question: are the programming variable names abstract to the model? if not, then using a specialized data prep might help this a lot: rename all variables to a small set like i, j, k, l etc. to laser focus training on logic

[@jahcane3711]

Please ask the authors what they meant by a lot of effort/time and find out for us how long solutions take to generate etc?

[@ashish54713]

9:14 Not entirely true, in my experience Codex has been able to solve a well defined problem with one or two examples, even really complex ones like DP and graph related stuff, often you need more than one iteration to get a good result and changing the temperature parameter helps out

[@nonamehere9658]

18:00 - wait a second, how did you arrive from code/program isomorphism to graph isomorphism? Also, it seems that (at least in general case) program isomorphism is intractable, e.g. if we had on oracle Isomorphic(X, Y) for any two X, Y We'd be able to tell if Halts(P(input)) by calling this oracle Isomorphic(P(input); cleanTuringMachineTapeAfterP, noop);

[@HappyMathDad]

I think there has to be some work in decomposition. We shall see.

[@shengyaozhuang3748]

Im more looking forward to interview part this time. So why not release the review and interview videos at the same time?

[@daniellawson9894]

I think he said that the authors watch the video he uploads before they do the interview but I guess he could just privately share them the video and upload both at once.

[@jabowery]

"Write the shortest program that outputs this data set..."

[@gr8ape111]

Fourth?

[@silberlinie]

Hello Yannic, I have a (perhaps stupid) question about NNs. The question concerns memorization of unknown events in the inference phase. An NN is trained on a dataset (and I don't mean a specific NN). After that, in the inference, it is out in the wild. This NN cannot learn anything new. Let's say classify an animal not shown to it in the training phase. Correct? And it is that after training, this NN can not keep something new it is presentet with. Let's say it is confronted with my name 100 times in the inference, anyway it has no way of keeping my name and integrating it into its knowledge. Correct? So the question is, does this apply to every type of NN today?

[@YannicKilcher]

there are systems that do continuous learning, but yes, most systems are frozen at inference and will not remember inference inputs.

[@silberlinie]

@@YannicKilcher Yes, I mean somthing like long-term memory consolidation and retrieval. For what I know right now continual acquisition of information generally leads to catastrophic forgetting or interference. At least from my understanding of todays state-of-the-art deep neural network models. So which model are you referring to with your '... there are systems ...'?

[@laurenpinschannels]

look up continuous learning, lifelong learning, etc

[@silberlinie]

@@laurenpinschannels Thanks for your comment Lauren. Which NN architecture do you think would come closest?

[@marcosrodriguez2496]

Gary Marcus has left the chat.

[@LouisChiaki]

Do you think this is still a brute force search algorithm but with Transformer?

[@carlotonydaristotile7420]

I need to buy more Google stock.

[@doyourealise]

first

[@CheapDeath96]

2nd