Re:Neural programmer better than Quicksort
by Cthulhu_ on Friday July 10, 2020 @03:51AM
(#23789175)
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?
[ Parent
| on HN ]
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
This is done! The existing correct algorithm is called the oracle and it’s used to validate the generated algorithm.
There’s some cool work on using neural program induction in compilers to try generate faster implementations based off the ‘oracle’ program that’s being compiled.
Re:Neural programmer better than Quicksort
by algo_trader on Friday July 10, 2020 @08:02AM
(#23790635)
> neural program induction in compilers to try generate faster implementations
Can u provide more details?
I am familiar with garden-variety ML-optimization-of-combinatorical-space in compilers.
How would u even "measure" the expected performance unless these are gradual greedy changes