Ask HN: Would ML algorithms be able to generate newithbetter sorting algorithms?

2 pointsnanospeck9y ago2 comments

I am feeling curious about the impact of ML in discovering new knowledge. I know ML learns from tons of training data and then later can come up with much better solutions. Would it be possible to design ML that looks into some training data of how sorting happens and then later come up by itself with with all the sorting algorithms like Bubble Sort, Quick Sort and may be even new ones that humans have not thought of? Is anything of that sort possible?

2 comments

2 comments · 2 top-level

nostrademons9y ago

In theory, yes. Joel Spolsky has a quote from 2005 where he says "Google uses Bayesian filtering the way Microsoft uses the if statement." [1] What a lot of developers don't realize is that this isn't metaphorical. The output of a classifier is a binary yes or no, based on the examples fed into it, and it's perfectly suited for use as the test in an if statement. Several of the more interesting AI results come from using machine-learning as a building block for more traditional algorithms, eg. a lot of natural language parsing is done this way.

I'd be somewhat doubtful that it could improve on the current state-of-the-art for sorting, though. There's a theoretical result that no comparison-based sort can achieve better than O(N log N) runtime, and mergesort/quicksort/heapsort are already there. You could perhaps get better real-world performance (the way TimSort can beat quicksort/mergesort on nearly-sorted data), but TimSort is already very tightly tuned, and it's likely you would improve performance on some datasets but reduce it on others.

[1] http://www.joelonsoftware.com/items/2005/10/17.html

brudgers9y ago

Only one way to find out.

Good luck.

j / k navigate · click thread line to collapse