Neural programmer better than Quicksort
1–10 of 132 posts
Re: Neural programmer better than Quicksort
#2Pretty cool.
"We include videos in the supplementary material showing the execution traces of the learned algorithms compared with the teachers, and observe qualitatively different behaviors."
Anyone know where we can find these?
Re: Neural programmer better than Quicksort
#3Pretty cool. "We include videos in the supplementary material showing the execution traces of the learned algorithms compared with the teachers, and observe qualitatively different behaviors." Anyone know where we can find these?
I think it's this one.
https://mobile.twitter.com/liyuajia/status/12812613378307112...
Re: Neural programmer better than Quicksort
#4This 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 using the normal sort algo until it sees a pattern in the input and then skips the sort algo for the pattern output? Or to put it plainly, is it just a smarter (or dumber, depending on the size of the neural network) hash table?
Re: Neural programmer better than Quicksort
#5Some interesting extracts:
“The instruction set together with the input representations jointly determine the class of algorithms that are learnable by the neural controller, and we see this as a fruitful avenue for future research akin to how current instruction sets shaped microprocessors.”
“The generalization or correctness we aim for is mostly about generalization to instances of arbitrary sizes.”
“[...] computing a = f(s) can be more expensive on current CPUs than executing typical computation employed in the algorithms studied here. We thus hope that this research will motivate future CPUs to have “Neural Logic Units” to implement such functions f fast and efficiently, effectively extending their instruction set, and making such approaches feasible.”
Re: Neural programmer better than Quicksort
#6It'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 above bugs are only hit because the programmers who wrote it didn't think about overflow. What is this "neural programmer" assuming about their inputs? We'll never know.
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!
Re: Neural programmer better than Quicksort
#7This 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.
Re: Neural programmer better than Quicksort
#8This 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 model is given the input and a set of instructions (e.g. swap) for producing the output. Essentially, it’s taking a permutation of the instructions that minimise the running time, based on some underlying patterns in the data.
Re: Neural programmer better than Quicksort
#9Better as in lower number of instructions not lower wall clock time.
Re: Neural programmer better than Quicksort
#10This 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.
Exactly, that’s what I thought. Although, they should be able to look at the set of instructions that generated the output, which is basically an algorithm in itself. Then they could try to prove whether that algorithm would really generalise.