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

31–40 of 132 posts

Re: Neural programmer better than Quicksort

#31

Post by collyw »

radicalbyte wrote: post #7
spyckie2 wrote: post #4

This is pretty cool, pardon my limited understanding, trying to see if I get this correctly: 1) they train a model to do sorting, it actually sorts correctly. 2) they optimize the model on efficiency and it becomes better than many custom sort functions? If I remember correctly from school, you can basically speed up any kind of sorting by using more space (basically by using a hash table). Is the neural network just…

The question is how does the algorithm perform on average, what are the pathological cases and how slow are they? How do you prove that with an algorithm that no human can reason about? Basically this paper looks like they've found an algorithm which is efficient for given sets or given classes of sets. Whether that generalizes is a different problem. It's basically a cool automatic heuristic generator.

> How do you prove that with an algorithm that no human can reason about?

This is something I see becoming a problem in the future for machine learning.

Re: Neural programmer better than Quicksort

#33

Post by Cthulhu_ »

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.

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?

Re: Neural programmer better than Quicksort

#34

Post by fiblye »

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.

With humans, we can ask what went wrong and fix the problem.

With black box algorithms, we throw in some new training data and just hope it's enough.

Re: Neural programmer better than Quicksort

#36

Post by Scea91 »

Cthulhu_ wrote: post #33
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.

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?

For an exact proof of correctness no, because that would only show the algorithm is correct for a selected set of input-output pairs.

However, it is true that validating it for a very large number of inputs and outputs has value. This is not uncommon even in mathematics. For example, Goldbach's Conjecture (https://www.wikiwand.com/en/Goldbach%27s_conjecture) has not been proven but has been shown to hold for all integers less than 4 × 10^18

Re: Neural programmer better than Quicksort

#37

Post by pansa2 »

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…

> I am not sure I will ever trust an ML algorithm trained on inputs/outputs only

It’s doing TDD!

Re: Neural programmer better than Quicksort

#38

Post by ogogmad »

ultrablack wrote: post #32

There are sorting methods faster than quicksort though. O(n loglog n) for instance. Or for randomized its O(n sqrt log log n).

Omega(n log n) is the fastest possible for a comparison sort, by a simple decision tree argument. This is true even for the average case.

Their algorithm is a comparison sort, as they make clear on page 5.

Re: Neural programmer better than Quicksort

#40

Post by andybak »

fiblye wrote: post #34
ukj wrote: post #15

Earlier quoted context omitted.

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

With humans, we can ask what went wrong and fix the problem. With black box algorithms, we throw in some new training data and just hope it's enough.

> With humans, we can ask what went wrong and just hope we've fixed the problem.

> With black box algorithms, we throw in some new training data and just hope it's enough.

A small wording change and they're equivalent again.

To some extent human beings are also a black box - with some very peculiar failure conditions and side-channel weaknesses.

Post reply on HN