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

21–30 of 132 posts

Re: Neural programmer better than Quicksort

#21

Post by adrianN »

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.

We suck really hard at proving code correct that was written explicitly with the goal in mind to be formally verified. The techniques there are still quite immature. I wonder how long it will take until we have a reasonably working pipeline of ML+formal verification. Maybe it's just easier to generate correct code from the spec than to learn it from examples and then verifying it with the specification?

Re: Neural programmer better than Quicksort

#22

Post by adrianN »

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 deal with 99% accuracy in humans by designing all our human-based algorithms to be resilient against mistake (and still mistakes in the end result happen very frequently). This is completely different from the way we have designed our computer systems, because it's way easier to do this with flexible agents like humans than with inflexible agents like computers.

Re: Neural programmer better than Quicksort

#23

Post by Random_ernest »

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.

But the problems where we apply human labour are vastly different from the ones where we apply machine labour. In (most) tasks where we apply human labour a few errors are tolerated.

Re: Neural programmer better than Quicksort

#24

Post by malisper »

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…

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

I haven't read this paper, but that strategy was exactly the strategy behind "The Case for Learned Index Structures"[0]. The idea was you could train a model to predict the location of a row based on a primary key. After computing the model, you could then go through every row and compute a bound on how far off the model is from the actual row. To perform a lookup, you start off at the model's guess, then look around based on the bound on the model for a row with the given primary key.

[0] https://arxiv.org/abs/1712.01208

Re: Neural programmer better than Quicksort

#25

Post by [deleted] »

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.

[deleted]

Re: Neural programmer better than Quicksort

#26

Post by sinuhe69 »

me551ah wrote: post #19

According to the limitations stated in the doc. 1. It runs slower on modern CPUs and you need neural logic units to see the speed benefits 2. Model needs the be fined tuned to the data for best performance. While it may be better than quicksort in certain usecases it isn't going to replace it anytime soon.

"Model needs the be fined tuned to the data for best performance." -> typical :D

Re: Neural programmer better than Quicksort

#27

Post by riedel »

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…

Why not check in $n$ on a sorted if the postcondition holds or raise an exception otherwise. You can even generate a nearly sorted list and run a verified bubblesort. Don't see big problems if ML is used carefully.

Re: Neural programmer better than Quicksort

#28

Post by collyw »

xiphias2 wrote: post #18

The code (which is a few percent faster than quicksort) is on the last page: procedure QUICKSORTAGENT(input state) 2: Let i = 1, j = 2, l = 3, h = 4 3: if FunctionID = None then 4: return vh ← Function1(vl ← vl, vh ← vh) 5: else if FunctionID = 1 then . QuickSort 6: if vl vl then 15: return vi ← Function1(vl ← vl, vh ← vi) 16: else 17: return MoveVar(j, +1) 18: end if 19: else if prev = (vi ← Function1(vl ← vl, vh ←…

This reminds me of programming basic on an Acorn Electron. Line numbers and I don't remember indentation, though it was a few decades ago.

Re: Neural programmer better than Quicksort

#29

Post by bryanrasmussen »

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.

what's the promote option in this analogy?

Re: Neural programmer better than Quicksort

#30

Post by misja111 »

collyw wrote: post #28
xiphias2 wrote: post #18

The code (which is a few percent faster than quicksort) is on the last page: procedure QUICKSORTAGENT(input state) 2: Let i = 1, j = 2, l = 3, h = 4 3: if FunctionID = None then 4: return vh ← Function1(vl ← vl, vh ← vh) 5: else if FunctionID = 1 then . QuickSort 6: if vl vl then 15: return vi ← Function1(vl ← vl, vh ← vi) 16: else 17: return MoveVar(j, +1) 18: end if 19: else if prev = (vi ← Function1(vl ← vl, vh ←…

This reminds me of programming basic on an Acorn Electron. Line numbers and I don't remember indentation, though it was a few decades ago.

The source code in the PDF has indentation, it is a bit easier to read.
Post reply on HN