Neural programmer better than Quicksort • Hacker News Board

Re: Neural programmer better than Quicksort

#101

Post by xkapastel » Fri, Jul 10, 2020, 6:10 PM UTC

lone-commenter wrote: post #48

ogogmad wrote: post #46

Earlier quoted context omitted.

> 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. How is that "cheating"? The algorithm is still learning how to do a comparison-sort, which has direct applications (assuming it performs well).

So do they feed such information only when training the system?

No, the neural net needs to receive a feature vector before each instruction in order to sort the array. So whenever you want to sort things, you need to create that vector over and over.

Re: Neural programmer better than Quicksort

#102

Post by xkapastel » Fri, Jul 10, 2020, 6:11 PM UTC

ogogmad wrote: post #50

lone-commenter wrote: post #48

Earlier quoted context omitted.

So do they feed such information only when training the system?

You can generate that input only when needed. So whenever the sorting algorithm asks whether A[i] > A[i+1], you can perform the comparison there and then. So the answer to your question is yes.

The input is always needed, the neural net is an iterative algorithm that views the "local information" gathered from the array on every time step. It's asking continuously whether e.g. `A[i] > A[i+1]`.

Re: Neural programmer better than Quicksort

#103

Post by eli_gottlieb » Fri, Jul 10, 2020, 6:11 PM UTC

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…

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

Pfffft, just wait until they get it writing code with its own proofs of correctness in dependent type theory. It'll be correct and twice as unreadable as incorrect human-written code!

Re: Neural programmer better than Quicksort

#104

Post by Der_Einzige » Fri, Jul 10, 2020, 6:24 PM UTC

nardi wrote: post #96

Der_Einzige wrote: post #95

Earlier quoted context omitted.

I don't believe you. Surely, after a few hints, the FAANG canidates must have been able to figure out the classic gotcha of this question (why does this sometimes overflow and how do you fix {high + low / 2}) If they didn't, than I believe you did a poor job of guiding them. I refuse to believe that this is some esoteric, tough question. If you can solve dynamic programming problems, you can easily solve this one.

I interview tons of candidates at a FAANG company, and I can tell you for sure binary search is way too hard to get right on a whiteboard. Even in a proper coding environment I wouldn't ask it. There are lots of better questions with fewer sharp edges.

What else is hard besides converting

(high + low) / 2

To

Low + (high - low) / 2

What else about this problem is a "sharp edge"?

Re: Neural programmer better than Quicksort

#105

Post by nardi » Fri, Jul 10, 2020, 6:38 PM UTC

Der_Einzige wrote: post #104

nardi wrote: post #96

Earlier quoted context omitted.

I interview tons of candidates at a FAANG company, and I can tell you for sure binary search is way too hard to get right on a whiteboard. Even in a proper coding environment I wouldn't ask it. There are lots of better questions with fewer sharp edges.

What else is hard besides converting (high + low) / 2 To Low + (high - low) / 2 What else about this problem is a "sharp edge"?

I may have been a little too harsh. Binary search is close to being a good interview question, especially since the algorithm does, rarely, come up in real code. But I prefer questions that are more like what people will be doing in their day-to-day job, and binary search is just a little too fiddly.

Re: Neural programmer better than Quicksort

#106

Post by FabHK » Fri, Jul 10, 2020, 6:55 PM UTC

UncleOxidant wrote: post #97

diegoperini wrote: post #80

Earlier quoted context omitted.

Today's perfections are yesterday's "good enoughs". Don't be sad for the trend. In 10 years, you will have new perfections to enjoy.

Like the probabilistic bank account balance. "You have between $10 and $1000 with the greatest likelihood being $537 (52% chance)."

There was this thread a while ago with HSBC switching to MongoDB... so, yeah, distinct possibility :-)

https://news.ycombinator.com/item?id=23507197

(The article was very light on details though, and it was probably just one team that consolidated to MongoDB, not the accounts itself... one hopes.)

Re: Neural programmer better than Quicksort

#107

Post by FabHK » Fri, Jul 10, 2020, 7:01 PM UTC

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…

> none of the popular sorting algorithms decide which elements to swap by looking at the whole input at each execution

Yes. In particular, the O(n log n) lower bound holds for comparison sorts, that is algorithms that rely on pairwise comparison only.

Re: Neural programmer better than Quicksort

#108

Post by bokbok8379 » Fri, Jul 10, 2020, 7:18 PM UTC

m3kw9 wrote: post #98

How will you debug this?

With a neural network trained debugger, of course.

Re: Neural programmer better than Quicksort

#109

Post by DaiPlusPlus » Fri, Jul 10, 2020, 7:27 PM UTC

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…

Apparently modern GPUs have sorting-networks implemented in hardware (giving you effectively constant-time sorting for fixed-size input) - which may be preferable for use if you’re processing hostile input which may be contrived to hit QuickSort’s worst-case and the cost of hitting the PCI Express bus is less than the cost of randomizing the input to mitigate QuickSort attacks.

But yes - I agree it’s weird that many standard-libraries (looking at you, .NET!) have only a single `Sort` method oh their vector-types with the details of the implementation buried in the documentation instead of shipping with a first-class sorting-algorithms library.

Re: Neural programmer better than Quicksort

#110

Post by woeirua » Fri, Jul 10, 2020, 7:28 PM UTC

Eh... Look I get that everyone wants to publish exciting results, but to call this unequivocally "better" than quick sort is a big stretch. The profiling results are unconvincing at best. A small, Table 3 is very suspicious too. If they're doing what they claim, then why is Binary Search all of a sudden significantly better than the learned agent for some problem sizes? It really feels like they're running up against some kind of inherent optimization boundary inside their neural network library...