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

71–80 of 132 posts

Re: Neural programmer better than Quicksort

#71

Post by eru »

mkl wrote: post #59
KajMagnus wrote: post #44

Earlier quoted context omitted.

> "just run a final pass of insertion sort to make it useful!" (And if this insertion sort won't complete in O(n), say <= 3n, then, fallback to Quicksort, so won't turn into O(n^2) just because the ML alg hit a corner case)

Possibly better would be Timsort (used in Python, Java, V8, etc.), as it's "designed to take advantage of runs of consecutive ordered elements that already exist": https://en.wikipedia.org/wiki/Timsort

Haskell's standard library sort, a variant of merge sort, also makes use of runs.

It runs in O(n log (number of runs)). It's quite a lot simpler than Timsort.

Re: Neural programmer better than Quicksort

#72

Post by AlphENsign_Tech »

rusticpenn wrote: post #13
nardi wrote: post #12

Earlier quoted context omitted.

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.

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

from the volumetric standpoint, the 99% is their huge specially curated training and test data.

Re: Neural programmer better than Quicksort

#73

Post by mabbo »

> As highlights, our learned model can perform sorting perfectly on any input data size we tested on

I'm not going to drop something into my production code that works on just the inputs you tested with. As ghj pointed out- Java's highly analyzed sort method had a bug for years and we didn't notice.

It's neat research and I won't discourage it at all, but give me some proofs of correctness.

Re: Neural programmer better than Quicksort

#74

Post by infinity0 »

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.

Sure, not all bugs are kernel bugs though.

Re: Neural programmer better than Quicksort

#76

Post by jcelerier »

bufferoverflow wrote: post #64
nardi wrote: post #12

Earlier quoted context omitted.

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.

> There's a place for fast sorting algorithms which are correct most of the time - basically anything non-critical, like sorting comments by upvotes.

Nothing saddens me more than this trend of the modern web where everything works semi-probabilistically (even if it's likely for "good" technical reasons, such as, "we wrote our server backend in Ruby which is slow as molasses so now we need 230 CDN and 800 databases instances around the whole world and transformed our simple centralized problem into an horrendous decentralized one).

The central reason for me to use computers is that they are (or at least were) deterministic to a much higher degree that normal life, and so many things in the 10 last years becoming much more non-deterministic in particular on social websites is something that frustrates me every single day as it just makes the whole experience and process of using computers & the web very unreliable compared to what it used to be.

Re: Neural programmer better than Quicksort

#77

Post by [deleted] »

bufferoverflow wrote: post #64
nardi wrote: post #12

Earlier quoted context omitted.

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.

[deleted]

Re: Neural programmer better than Quicksort

#78

Post by im3w1l-alt »

eru wrote: post #69
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,…

If you let the number of objects to sort go to infinity while keeping size of objects in bits capped, then they will behave like integers.

Re: Neural programmer better than Quicksort

#79

Post by eru »

im3w1l-alt wrote: post #78
eru wrote: post #69

Earlier quoted context omitted.

> 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,…

If you let the number of objects to sort go to infinity while keeping size of objects in bits capped, then they will behave like integers.

I thought more of being able to do bit manipulation or hashing etc on your keys. Those things don't necessarily require a fixed key length. (And in some languages, even integers don't have a fixed length.)

You are right in some sense, but you'd still have trouble implementing something like bucket sort in your setting, if all you have are comparisons.

Re: Neural programmer better than Quicksort

#80

Post by diegoperini »

jcelerier wrote: post #76
bufferoverflow wrote: post #64

Earlier quoted context omitted.

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.

> There's a place for fast sorting algorithms which are correct most of the time - basically anything non-critical, like sorting comments by upvotes. Nothing saddens me more than this trend of the modern web where everything works semi-probabilistically (even if it's likely for "good" technical reasons, such as, "we wrote our server backend in Ruby which is slow as molasses so now we need 230 CDN and 800 databases in…

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.
Post reply on HN