Deepmind has launched AlphaTensor, the first artificial intelligence (AI) system for developing innovative, efficient, and provably correct algorithms for fundamental tasks like matrix multiplication. The research was published in Nature on October 5, 2022.
AlphaTensor is based on AlphaZero, an agent that has demonstrated superhuman performance in board games like Chess, Go, and Shogi, and this study depicts AlphaZero’s path from playing games to addressing intractable mathematical problems. The study solves a 50-year-old mathematical mystery concerning the quickest way to multiply two matrices. It is a step forward in DeepMind’s ambition to use AI to advance science and solve the most fundamental problems.
For thousands of years, mathematicians have relied on algorithms to perform fundamental operations. The ancient Egyptians devised an algorithm for multiplying two integers without the aid of a multiplication table. At the same time, the Greek mathematician Euclid established an approach for computing the greatest common divisor being used today.
Despite the present familiarity with algorithms – which are used in everything from classroom mathematics to cutting-edge scientific research – the process of inventing new algorithms is exceedingly challenging and illustrates the human mind’s extraordinary reasoning ability.
Matrix Multiplication
Since the Strassen method was released in 1969, computer scientists have been striving to outperform its speed of multiplying two matrices. Matrix multiplication is used to analyze smartphone photos, recognize verbal commands, generate visuals for computer games, execute weather simulations, compress data and films for internet sharing, and much more.
Companies all around the globe invest a lot of effort and money in creating computing hardware that can effectively multiply matrices. As a result, even slight increases in matrix multiplication performance can have a significant impact.
The Process And Progress Of Automating Algorithmic Discovery
First, they turned the task of developing efficient matrix multiplication algorithms into a single-player game.
The board in this game is a three-dimensional tensor (array of integers) representing how far from correct the current method is.
The player attempts to change the tensor and zero out its entries by using a set of allowable movements that correspond with algorithm instructions.
When the player succeeds, the outcome is a valid matrix multiplication method for any pair of matrices. Its efficiency is measured by the number of steps required to zero out the tensor.
Compared to the game of Go, which has long been a challenge for AI, the number of possible moves at each stage of this game is 30 orders of magnitude more (above 1033 for one of the settings we consider).
Exploring The Impact On Future Research And Applications
From a mathematical approach, their findings can help guide future research in complexity theory, which tries to find the quickest techniques for addressing computer problems.
AlphaTensor contributes to understanding the richness of matrix multiplication algorithms by investigating the space of potential algorithms more effectively than earlier attempts.
Understanding this space may lead to new insights into determining the asymptotic complexity of matrix multiplication, one of computer science’s most fundamental unresolved issues.
The research also demonstrates that AlphaZero is a strong algorithm that can be extended well beyond typical games to assist in the solution of open issues in mathematics.
Building on these findings, the researchers intend to inspire a larger body of work – using AI to help society address some of the most pressing difficulties in mathematics and the sciences.
“If we’re able to use AI to find new algorithms for fundamental computational tasks, this has enormous potential because we might be able to go beyond the algorithms that are currently used, which could lead to improved efficiency,”
Pushmeet Kohli, head of AI for science at DeepMind.
