What do encrypted messages, recognizing speech commands and running simulations to predict the weather have in common? They all rely on matrix multiplication for accurate calculations. DeepMind, an artificial intelligence company, recently developed a faster algorithm to conduct matrix multiplications based on deep reinforcement learning. This recent auto-discovery of an efficient algorithm in mathematics by another machine learning algorithm expands the purview of the uses and applications of machine learning.
Alhussein Fawzi, staff research scientist at DeepMind, and his team are responsible for the DRL algorithm that made the discovery. He expressed his excitement over the discovery and its importance in the field.
“What I found very surprising was that we still do not know what’s the optimal way of multiplying small matrices (as small as 3x3),” Fawzi wrote in an email to the Daily. “So I felt from the very beginning that Machine Learning could help a lot in this field, by finding the best patterns (i.e., which entries to combine in the matrices, and how to combine them) to get the right result … [We] saw the system starting from scratch to re-discovering algorithms … and eventually surpassing these algorithms. The first time we saw that we were able to improve over existing known algorithms was very exciting!”
According to Fawzi, the discovery was made by the agent AlphaTensor, which is based on the DRL algorithm, AlphaZero. DRL algorithms such as these are stimulated to learn from their previous actions, very similar to how humans learn from experience.
Fawzi’s team analyzed the problem of matrix multiplication as a single-player game. According to Fawzi, the AlphaTensor agent they used relies on two major components: the actors and the learners. The game would start with the actor playing numerous matrix multiplication games. These games are then sent to the learner, who then watches how the actor played the game and designs a neural network that tries to imitate the moves performed. This neural network is then sent back to the actors, who try to improve upon the decisions made by the neural network. This creates a self-reinforcement loop which results in a constant improvement of the neural network in playing the game.
Fawzi explained the novelty of AlphaTensor, and how it is able to improve over time despite no knowledge on existing algorithms at the start. The algorithm is able to re-discover older matrix multiplication algorithms and improve upon its own to discover newer and faster algorithms.
“AlphaTensor is the first AI system for discovering novel, efficient, and provably correct algorithms for fundamental tasks such as matrix multiplication,” Fawzi wrote. “By provably correct, I mean that the resulting algorithm is guaranteed to be correct on any instance.”
This discovery opens up the field of mathematics and computer science to explore numerous other possibilities for computers to find more efficient algorithms than those currently developed by humans.
“AlphaTensor provides an important proof of concept that with machine learning, we can go beyond existing state-of-the-art algorithms, and therefore that machine learning will play a fundamental role in the field of algorithmic discovery going forward,” Fawzi wrote. “I believe that in the next few years, many new algorithms for fundamental computational tasks that we use every day will be discovered with the help of Machine Learning.”
