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

Neural programmer better than Quicksort

arxiv.org

Post reply on HN
Print view View original

61–70 of 132 posts

Re: Neural programmer better than Quicksort

#61

Post by rightbyte »

MichaelBurge wrote: post #20
rightbyte wrote: post #14

Quite dull research wrapped in fancy words. Essentially they generate functions that map a program state to another program state and counts those function calls and compares with e.g. the number of function calls in quick sort. They "cheat" by feeding how all elements compares the their neighbours at each step. Like, if you give the algorithm that input for free what's the point. Notably, none of the popular sorting…

"all" of a constant number k of such inputs, not "all" of the entire input. It's not possible to feed a neural network an arbitrarily-large number of inputs in one batch.

My error it seemed to be a reference implementation with all. Is it correct that they feed a vector of 68 such comparisons in the window inferface?

Re: Neural programmer better than Quicksort

#62

Post by pX0r »

rightbyte wrote: post #60
pX0r wrote: post #57

Earlier quoted context omitted.

Was this "discovered" by their system or was it hand-crafted by the authors from their custom instruction set elements ?

As I understand it they designed quicksort like that to be able to train with it. It is quite clear from the video where it is called "quick sort agent" compared to the model one and function1 and function2 is in the stack trace. "We found adding the previously executed action to the input state st is sufficient to handle dis-ambiguation for this quick sort implementation. Alg. 8 shows the converted quick sort script…

Right! I was hoping to see the body of one of their system induced algorithms. They don't seem to have included any - or maybe I am mistaken and their system is opaque and does not allow a generated algo. to be read out...

Re: Neural programmer better than Quicksort

#63

Post by chrisandchips »

adrianN wrote: post #55
infinity0 wrote: post #54

Earlier quoted context omitted.

Automatic proof checkers still have bugs in them. However, one nice characteristic is that, since its algorithms are so general, i.e. about the language rather than about the problem you're solving (e.g. sorting), any bugs in the checker are either so common they hit every problem solution and are easily discovered and fixed, or so rare that it affects no real-world problem solutions.

The kernel of an automatic proof checker is much easier to test and verify than the programs you verify using a proof checker though.

+1 verification tends to be the easy part.

Re: Neural programmer better than Quicksort

#64

Post by bufferoverflow »

nardi wrote: post #12
ghj wrote: post #6

It's really hard to write correct code. Sorting was broken in java and nobody noticed for a long time: http://envisage-project.eu/wp-content/uploads/2015/02/sortin... The same was true for java's binary search: https://ai.googleblog.com/2006/06/extra-extra-read-all-about... So I am not sure I will ever trust an ML algorithm trained on inputs/outputs only (which is what I think "neural program induction" means). The a…

Next step is to prove the ML-produced algorithm is correct. I can see a world where we generate algorithms and then automatically prove they're correct based on a formal description of the problem being solved.

It doesn't need to be 100% correct. There's a place for fast sorting algorithms which are correct most of the time - basically anything non-critical, like sorting comments by upvotes.

According to the article, they couldn't find a case where it wasn't correct.

Re: Neural programmer better than Quicksort

#65

Post by bufferoverflow »

ukj wrote: post #15
rusticpenn wrote: post #13

Earlier quoted context omitted.

Well designed ML techniques are always correct 99% of the time. Its the 1% that is the problem.

99% of the time it works all of the time. Like humans. How do we deal with problematic humans? Retraining or replacement.

No, we don't do anything against the humans who are 99% correct. 99% is good enough in most real world cases.

Re: Neural programmer better than Quicksort

#66

Post by rightbyte »

EchoAce wrote: post #53
rightbyte wrote: post #14

Quite dull research wrapped in fancy words. Essentially they generate functions that map a program state to another program state and counts those function calls and compares with e.g. the number of function calls in quick sort. They "cheat" by feeding how all elements compares the their neighbours at each step. Like, if you give the algorithm that input for free what's the point. Notably, none of the popular sorting…

This is absolutely not cheating; every hand designed algorithm can access and compare everything in the array! The real point of what they’re saying in your italicized quote is actually that giving the net full access hinders efficiency, so they actually restrict it. Almost like the opposite of cheating.

It is not a pointer to an array I'm concerned about but the "neighbour diff vector" or what you should call it that provided by the "environment". See A.1.2.

Doing so many comparisons and storing them has a cost. Also the model can't decide if it is done so at each step the array has to be iterated to see if it is sorted by the "environment". Are they only counting function calls? I guess so. The paper is really hard to follow and the pseudocode syntax is quite madding.

If I understand the paper correctly of course I could be wrong.

If so, "our approach can learn to outperform custom-written solutions for a variety of problems", is bogus.

Re: Neural programmer better than Quicksort

#67

Post by rusticpenn »

ukj wrote: post #15
rusticpenn wrote: post #13

Earlier quoted context omitted.

Well designed ML techniques are always correct 99% of the time. Its the 1% that is the problem.

99% of the time it works all of the time. Like humans. How do we deal with problematic humans? Retraining or replacement.

That is not practical when you expect the system to be correct 100% of the time and make decisions based on that. There are many situations where this is critical. You would never want your car's safety system to be correct only 99% of the time.

Re: Neural programmer better than Quicksort

#68

Post by algo_trader »

exdsq wrote: post #41
Cthulhu_ wrote: post #33

Earlier quoted context omitted.

Call me naive but, wouldn't feeding it random input and expected output sorted by existing and proven (but slower) sorting algorithms do the trick?

This is done! The existing correct algorithm is called the oracle and it’s used to validate the generated algorithm. There’s some cool work on using neural program induction in compilers to try generate faster implementations based off the ‘oracle’ program that’s being compiled.

> neural program induction in compilers to try generate faster implementations

Can u provide more details?

I am familiar with garden-variety ML-optimization-of-combinatorical-space in compilers.

How would u even "measure" the expected performance unless these are gradual greedy changes

Re: Neural programmer better than Quicksort

#69

Post by eru »

ghj wrote: post #6

It's really hard to write correct code. Sorting was broken in java and nobody noticed for a long time: http://envisage-project.eu/wp-content/uploads/2015/02/sortin... The same was true for java's binary search: https://ai.googleblog.com/2006/06/extra-extra-read-all-about... So I am not sure I will ever trust an ML algorithm trained on inputs/outputs only (which is what I think "neural program induction" means). The a…

> If this thing can efficiently almost-correctly-sort because it's better at these types of pattern matching, we can just run a final pass of insertion sort to make it useful!

Depends on what kinds of mistakes the almost-correct approach makes. If it just puts elements in the wrong order, your suggestion works. But if it makes mistakes like duplicating elements, or dropping them, or completely making up new entries, no post-processing will help.

> OTOH the standard library sort can be improved if you know the distribution of the numbers you're sorting (e.g., small numbers can bucket sort, small lists can use a sorting network, etc).

Even better: the standard library sort usually assumes only comparison. For special cases like sorting on integer keys you can conceivably do better.

Re: Neural programmer better than Quicksort

#70

Post by eru »

hutzlibu wrote: post #58
louthy wrote: post #56

Earlier quoted context omitted.

> So I rather do lots of testing, for all known test cases. How is this any different? You can still make mistakes in your test code, test data, omit cases that would fail, etc. I think I'd be less confident in a set of unit tests than I would with an automated proof checker.

Tests are simple to unterstand. Complicated proofs I do not understand, without much effort. And I surely know that you can make mistakes with test cases as well. So I surely do not claim my way to be superior. But it works way better for me.

Test cases are not necessarily simple to understand.

Especially the test cases needed to trigger some deep bug.

Post reply on HN