Faster sorting algorithms: New algorithms will transform the foundations of computing

[erek]

Impressive by AlphaDev of DeepMind

"Faster sorting algorithms discovered using deep reinforcement learning: Fundamental algorithms such as sorting or hashing are used trillions of times on any given day1. As demand for computation grows, it has become critical for these algorithms to be as performant as possible. Whereas remarkable progress has been achieved in the past2, making further improvements on the efficiency of these routines has proved challenging for both human scientists and computational approaches. Here we show how artificial intelligence can go beyond the current state of the art by discovering hitherto unknown routines. To realize this, we formulated the task of finding a better sorting routine as a single-player game. We then trained a new deep reinforcement learning agent, AlphaDev, to play this game. AlphaDev discovered small sorting algorithms from scratch that outperformed previously known human benchmarks. These algorithms have been integrated into the LLVM standard C++ sort library3. This change to this part of the sort library represents the replacement of a component with an algorithm that has been automatically discovered using reinforcement learning. We also present results in extra domains, showcasing the generality of the approach."

Source: https://www.deepmind.com/blog/alphadev-discovers-faster-sorting-algorithms

 

[westrock2000]

Is this actual intelligence or is this iterating over large numbers of possibilities to find the most efficient method?

“The assembly game is incredibly hard because AlphaDev has to efficiently search through an enormous number of possible combinations of instructions to find an algorithm that can sort, and is faster than the current best one.”

This sounds like computers doing what computers do, but calling it intelligence. AI is becoming a catch all term for computing.

 

[LukeTbk]

Is this actual intelligence or is this iterating over large numbers of possibilities to find the most efficient method?

it is machine learning running on tensor (it is google deepmind) and was called AI from the start more than a decade ago.

Computer intelligence does not work (very often) at all like human, it is artificial, the end result is intelligent, you found a faster algo, played a chess move, transcribed voice in a sound file into text, the way it is done can be done in what look like intelligence (in the past often you would have a program with the rules, algorithm and the intelligence would all come from the programmer work, using compute power as a tool), it can be raw strength machine learning that test many possible, find the best, take them and tweak them, mix them and so on and feedback to itself result to learn, search in a way not predicted by the programmers with unknown in advance result and in some case creating a black box impossible to understand at the end or in this very limited case of very few perimeters an answer.

Computer has been doing this for a while, the bit of intelligence is that it does more than generate all the possible (or a giant amount of possible) test all of them and pick the best, it feedback loop what change lead to better or worst result, mix some of the best together and build what is more probable to be faster from what was "learn" by the first x thousands try and so on.

People sometime skip too much the word Artificial in Artificial Intelligence, a lot of it does not work at all like non-artificial one and require a lot of raw power because of it.