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

371–380 of 415 posts

Re: Competitive Programming with AlphaCode

#371

Post by YeGoblynQueenne »

Mehdi2277 wrote: post #363
YeGoblynQueenne wrote: post #362

Earlier quoted context omitted.

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…

Well, I'm not surprised because I know that large language models can learn smooth approximations of natural language. They can generate very grammatical natural English, so why not grammatical source code, which is easier? Of course, once you have a generator for code, finding a program that satisfies a specification is just a matter of searching -and assuming the generated code includes such a program. But it seems like that isn't really the case with AlphaCode, because its performance is very poor.

I have to say that usually I'm the one speaking out against an over-reliance on machine learning benchmarks and against expecting a new approach to beat the state of the art before it can be taken seriously, but this is not a new approach, and that's the problem I have here. It's nothing new, repackaged as something new and sold as something it isn't ("reasoning" and "critical thinking" and other nonsense like that).

I agree that future work must get smarter, and incorporate some better inductive biases (knowledge, something). Or perhaps it's a matter of searching more intelligently because given they can generate millions of programs I'd have thought they'd be able to find more programs that approximate a solution.

Re: Competitive Programming with AlphaCode

#372

Post by nsikorr »

I suspect these code generating AIs will bring the singularity at some point in the future. Even if we don’t manage to create an artificial general intelligence, they will. I imagine they will learn to code on super human levels through self play just like AlphaGo and AlphaZero did. This will be awesome.

Re: Competitive Programming with AlphaCode

#373

Post by Veedrac »

YeGoblynQueenne wrote: post #359
Veedrac wrote: post #332

Earlier quoted context omitted.

Your comment is an excuse, not mine: “ignore how good the advertised model is, because a different, much smaller version without all the techniques merely does pretty well on an extremely tough problem set.” > Any claims to the contrary need very strong evidence to support them and there's typically no such thing in papers like the AlphaCode one. This is the opposite of how burden of proof works. You are the one maki…

>> “ignore how good the advertised model is, because a different, much smaller version without all the techniques merely does pretty well on an extremely tough problem set.” Where is that quote from? Why are you quoting it? Am I supposed to reply to it? >> You are the one making a claim with certainty based off of guesswork, not me. I'm not talking about you. I'm talking about the paper, the team behind it and work o…

I was paraphrasing your argument. AFAICT, it remains faithful to what you are saying.

> Accordingly, there is no doubt that neural nets can only represent what is in their training set.

This is not true. If it were true that there was no doubt, the paper wouldn't have challenged it and claimed it false. If you assume your conclusion well obviously your conclusion follows trivially.

> And, yet again, the performance of the model is crap.

It isn't.

Re: Competitive Programming with AlphaCode

#374

Post by YeGoblynQueenne »

baobabKoodaa wrote: post #352
YeGoblynQueenne wrote: post #277

Earlier quoted context omitted.

>> To clarify, this is a HUGE leap in AI and computing in general. I don't mean to play it down. Sorry, but it's nothing of the sort. The approach is primitive, obsolete, and its results are very poor. I've posted this three times already but the arxiv preprint includes an evaluation against a formal benchmark dataset, APPS. On that more objective measure of performance, the best performing variant of AlphaCode teste…

> It generates millions of candidate programs and then it "filters" them by running them against input-output examples of the target programs taken from the problem descriptions. The filtering still leaves thousands of candidate programs (because there are very few I/O examples and the almost random generation can generate too many programs that pass the tests, but still don't solve the problem) so there's an additio…

To clarify, which part of my comment do you think is "almost certainly untrue"? What I describe above is how their approach works. It's summarised in the paper. See Section 4. ("Approach"):

1. Pre-train a transformer-based language model on GitHub code with standard language modelling objectives. This model can reasonably represent the space of human coding, which greatly reduces the problem search space.

2. Fine-tune the model on our dataset of competitive programming data, using GOLD (Pang and He, 2020) with tempering (Dabre and Fujita, 2020) as the training objective. This further reduces the search space, and compensates for the small amount of competitive programming data by leveraging pre-training.

3. Generate a very large number of samples from our models for each problem.

4. Filter the samples to obtain a small set of candidate submissions (at most 10), to be evaluated on the hidden test cases, by using the example tests and clustering to pick samples based on program behaviour.

>> Since you're claiming this feat by Alphacode is comparable in difficulty to writing bubblesort (which you could write in 5 minutes), it shouldn't take you a lot of effort to produce something comparable.

What I meant was that the way they announced AlphaCode is like claiming that bubblesort is a novel approach to sorting lists. Not that the effort needed to create their system is comparable to bubblesort. I think if you read my comment again more carefully you will find that this is the first interpretation that comes to mind. Otherwise, I apologise if my comment was unclear.

Re: Competitive Programming with AlphaCode

#375

Post by Veedrac »

rfoo wrote: post #346
Veedrac wrote: post #292

Earlier quoted context omitted.

It does not. Really the strings just never get long enough that O(n²) would be catastrophic; the maximum possible length is 2e5.

2e5 is enough for making a naive O(n^2) solution to get TLE. This is likely due to the fact that in AlphaCode's solution the "inner O(n) loop" is actually a memmove(), which is optimized to be insanely fast.

> AlphaCode's solution the "inner O(n) loop" is actually a memmove(), which is optimized to be insanely fast.

Again, it is not. CPython does not do these things.

The web page says, and this is corroborated in the paper,

> Solutions were selected randomly, keeping at most one correct (passes all test cases in our dataset) and one incorrect sample per problem and language. Note that since our dataset only has a limited number of test cases, passing all tests we have cannot completely rule out false positives (~4%), or solutions that are correct but inefficient (~46%).

The “54th percentile” measure did use estimated time penalties, which you can see discussed in Table 4 in the paper, but 1553D was not part of that.

Re: Competitive Programming with AlphaCode

#376

Post by YeGoblynQueenne »

Veedrac wrote: post #373
YeGoblynQueenne wrote: post #359

Earlier quoted context omitted.

>> “ignore how good the advertised model is, because a different, much smaller version without all the techniques merely does pretty well on an extremely tough problem set.” Where is that quote from? Why are you quoting it? Am I supposed to reply to it? >> You are the one making a claim with certainty based off of guesswork, not me. I'm not talking about you. I'm talking about the paper, the team behind it and work o…

I was paraphrasing your argument. AFAICT, it remains faithful to what you are saying. > Accordingly, there is no doubt that neural nets can only represent what is in their training set. This is not true. If it were true that there was no doubt, the paper wouldn't have challenged it and claimed it false. If you assume your conclusion well obviously your conclusion follows trivially. > And, yet again, the performance o…

>> I was paraphrasing your argument. AFAICT, it remains faithful to what you are saying.

No, it remains faithful to your interpretation of what I said, which is designed to support your opinion rather than mine.

Also, basic manners: if you're not quoting, don't use quotes.

>> It isn't.

Is too!

We could do that all day. Or, we could look at the reported results which are, well, crap.

Re: Competitive Programming with AlphaCode

#377

Post by qayxc »

mirrorlake wrote: post #88

I've been wondering this for a while: In the future, code-writing AI could be tasked with generating the most reliable and/or optimized code to pass your unit tests. Human programmers will decide what we want the software to do, make sure that we find all the edge cases and define as many unit tests as possible, and let the AI write significant portions of the product. Not only that, but you could include benchmarks…

> Is this a naive fantasy on my part, or actually possible?

Possible, yes, desirable, no.

The issue I have with all these end-to-end models is that they're a massive regression. Practitioners fought tooth and nails to get programmers to acknowledge correctness and security aspects.

Mathematicians and computer scientists developed theorem solvers to tackle the correctness part. Practitioners proposed methodologies like BDD and "Clean Code" to help with stability and reliability (in terms of actually matching requirements now and in the future).

AI systems throw all this out of the window by just throwing a black box onto the wall and scraping up whatever sticks. Unit tests will never be proof for correctness - they can only show the presence of errors, not their absence.

You'd only shift the burden from implementation (i.e. the program) to the tests. What you actually want is a theorem prover that proofs the functional correctness in conjunction with integration tests that demonstrate the runtime behaviour if need be (i.e. profiling) and references that link implementation to requirements.

The danger lies in the fact that we already have a hard time getting security issues and bugs under control with software that we should be able to understand (i.e. fellow humans wrote and designed it). Imagine trying to locate and fix a bug in software that was synthesised by some elaborate black box that emitted inscrutable code in absence of any documentation and without references to requirements.

Re: Competitive Programming with AlphaCode

#378

Post by YeGoblynQueenne »

diehunde wrote: post #39
hmate9 wrote: post #2

Between this and OpenAI's Github Copilot "programming" will slowly start dying probably. What I mean by that is that sure, you have to learn how to program, but our time will be spent much more on just the design part and writing detailed documentation/specs and then we just have one of these AIs generate the code. It's the next step. Binary code Historically its always been about abstracting and writing less code to…

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…

Possibly interesting trivium: automated debugging was first described in 1982, in Ehud Shapiro's PhD thesis titled "Algorithmic Program Debugging" (it's what it sounds like and it can also generate programs by "correcting" an empty program):

https://en.wikipedia.org/wiki/Algorithmic_program_debugging

Of course all this targeted only Prolog programs so it's not well-known at all.

Re: Competitive Programming with AlphaCode

#380

Post by qayxc »

blt wrote: post #52

I am always surprised by the amount of skepticism towards deep learning on HN. When I joined the field around 10 years ago, image classification was considered a grand challenge problem (e.g. https://xkcd.com/1425/ ). 5 years ago, only singularity enthusiast types were envisioning things like GPT-3 and Copilot in the short term. I think many people are uncomfortable with the idea that their own "intelligent" behavior…

This scepticism shouldn't surprise you. Not being sceptical is just an indicator that you've not been in the field for long enough.

30 years ago, the end of programming was prophesised, because 5th generation languages (5GL) and visual programming would enable everybody to design and build software.

20 years ago, low-code and application builders were said to revolutionise the industry and allow people in business roles to build their applications using just a few clicks. End-to-end model-driven design and development (e.g. using Rational Rose and friends) were to put an end to bugs and maintenance problems.

10 years ago it was new programming languages (e.g. Rust, Go, Swift, ...) and a shift to functional programming that was advertised as being "the future".

Today it's back to "no code", e.g. tool-(AI-)driven development that's all the rage.

It's not so much being "uncomfortable" or clinging to the exceptionalism of the human mind. It's just experience. Every decade saw its great big hype and technological breakthrough, but the lofty promises didn't hold water.

Note that this doesn't mean nothing changed - model driven development still has its niche, visual programming is widely used in video production, rendering and game development. Features of functional programming have been added to many "legacy" languages and many of the newly introduced programming languages have become mainstream.

The same will happen with AI generated software. There a large portion of the "mechanical" process of programming will be done by AI. Large and complex software systems with changing requirements, however, will still be designed and implemented primarily by people.

Programming is a conversation between humans and machines. AI will in many cases shift the conversation closer to the human side, but fundamentally it'll still be the same thing.

I like to think of it as the difference between writing your program in assembly and writing it in Haskell; different approaches, same basic activity.

Post reply on HN