DeepMind, the London-based artificial intelligence (AI) company known for its groundbreaking work in AI game-playing systems, has achieved another remarkable feat. Researchers at DeepMind have developed an AI system called AlphaDev, which has created algorithms capable of sorting data up to three times faster than human-generated versions.
The breakthrough discovery came as a surprise to the DeepMind team, led by computer scientist Daniel Mankowitz. “We were a bit shocked,” Mankowitz admitted. “We didn’t believe it at first.”
The technology behind AlphaDev is based on AlphaZero, an AI system developed by DeepMind for playing complex board games like chess, Go, and shogi. By applying the principles of AlphaZero to the task of building sorting algorithms, DeepMind was able to significantly enhance sorting speeds.
The results of this research are detailed in a paper published in the prestigious scientific journal Nature. The faster algorithms created by AlphaDev have already been incorporated into two standard C++ coding libraries, making them accessible to programmers worldwide. These algorithms are being utilized trillions of times each day, improving the efficiency of various sorting operations.
To develop AlphaDev, the researchers initially focused on sorting numbers by size, starting with small sets of 3, 4, or 5 numbers. Although these may seem trivial, they serve as building blocks for algorithms that sort longer lists. AlphaDev operates at the assembly instruction level, working with code generated by automated compilers from C++ code before it is translated into machine code.
Similar to its predecessor, AlphaZero, AlphaDev operates by combining deliberation and intuition to make strategic moves in board games. Instead of choosing moves, AlphaDev selects instructions to add to a procedure in what DeepMind engineers refer to as AssemblyGame.
Using a combination of deliberation and intuition, AlphaDev considers different decision points, potential moves, and their outcomes, ultimately identifying the most promising instructions. Through neural networks, AlphaDev continually updates its algorithms based on training outcomes and explores various moves to improve its sorting capabilities.
The evaluation process of AlphaDev encompasses correctness as well as speed. The system was trained to consider the total number of instructions or processing time, depending on the processor and the number of values being sorted. The best algorithms created by AlphaDev demonstrated time savings ranging from 4% to 71% compared to human-generated algorithms. However, when these algorithms were applied repeatedly to sort large lists of one-quarter million values, the cumulative time savings were only 1-2% due to other non-optimized code.
In addition to sorting algorithms, AlphaDev was also applied to non-sorting algorithms with impressive results. It reduced the processing time for a data conversion algorithm by 67% and a hashing algorithm by 30% compared to standard versions.
The DeepMind team delved into the algorithms to identify the key factors contributing to AlphaDev’s superior performance. They discovered two new tactics, named the AlphaDev swap move and the AlphaDev copy move, which played a crucial role in achieving faster sorting. Daniel Mankowitz compared these tactics to “Move 37,” a surprising move made by AlphaGo, an earlier version of AlphaZero, against the human Go champion Lee Sedol in 2016.
While the scientific depth may not be groundbreaking, experts acknowledge the remarkable engineering behind DeepMind’s work. Michael Littman, a computer scientist at Brown University, praised DeepMind’s ability to adapt their methods to new problems. DeepMind has previously made modifications to AlphaZero, resulting in the creation of AlphaTensor, a system that enhanced the multiplication of grids of numbers.
Looking ahead, the DeepMind team aims to apply AlphaZero-style algorithms to a wider range of problems, including the design of hardware itself. Mankowitz expressed their ambition to tackle the entire technology stack. With ongoing advancements in AI and machine learning, DeepMind continues to push the boundaries of what is possible, opening new doors for innovation across multiple domains.
Be the first to comment