You must have come across matrix multiplication in textbooks. But did you know how relevant it is in all aspects of our daily lives, from processing images on our phones and recognizing voice commands to generating graphics for computer games?
It is at the heart of almost everything computer science.
With the latest version of DeepMind, AlphaTensor, an AI system, researchers have shed light on a fundamental 50-year-old mathematical question of finding the fastest way to multiply two matrices.
“AlphaTensor has discovered better than state-of-the-art algorithms for many matrix sizes. Our AI-designed algorithms outperform human-designed ones, which is a major breakthrough in the field of algorithmic discovery,” DeepMind said in a statement.
Advancement is an extension of AlphaZero, a unique system that mastered board games (chess, go, and shogi) from scratch without human intervention. Additionally, research reveals that AlphaZero is a powerful algorithm that can be extended beyond the realm of traditional games to help solve open-ended math problems.
The problem at hand
Matrix multiplication is one of the simplest forms of mathematics, but it becomes intensely complex when applied in the digital world. Anything that can be solved numerically, from weather forecasting to data compression, usually uses matrices. For example, you can read this article on your screen because its pixels are represented as a grid and they update with new information faster than your eyes can follow.
Despite its ubiquitous nature, the calculus is not very well understood. Also, no one knows a faster method to solve the problem because there are endless ways to do it.
DeepMind’s Game Plan
Breakthroughs in machine learning have helped researchers from creating art to predicting protein structures. Increasingly, researchers are now using algorithms to become their own teacher and fix flaws.
DeepMind researchers did what they do best: making AI champions in games.
The team tackled the matrix multiplication problem by turning it into a single-player 3D board game called “TensorGame”. The game is extremely difficult because the number of possible algorithms, even for small cases of matrix multiplication, is greater than the number of atoms in the universe.
The three-dimensional board represents the multiplication problem and each move represents the next step to solving it. The series of movements performed in the game therefore represents an algorithm.
To play the game, the researchers trained a new version of AlphaZero, called “AlphaTensor.” Instead of learning the best moves to make in Go or chess, the system learned the best steps to take when multiplying the matrices. Then, using DeepMind’s preferred reinforcement learning, the system was rewarded for winning the game in as few moves as possible.
The AI system discovered a way to multiply two 4×4 matrices using just 47 multiplications, instead of the 64 needed if you had to painstakingly multiply each row with each column of its corresponding matrix. It’s also two steps short of the 49 found by Volker Strassen in 1969, whose multiplication method for 4×4 matrices held the record for fastest for over 50 years.
What awaits us?
The discovery could increase some computing speeds by up to 20% on hardware such as an Nvidia V100 graphics processing unit (GPU) and a Google tensor processing unit (TPU) v2, but there is no guarantee that these gains would also be visible on a smartphone or laptop.
DeepMind now plans to use AlphaTensor to research other types of algorithms. “While we’re able to push the boundaries a bit further with this computational approach,” said Gray Ballard, a computer scientist at Wake Forest University in Winston-Salem, North Carolina, “I’m thrilled that researchers Theoreticians are starting to analyze the new algorithms they’ve found to find clues about where to look for the next breakthrough.
#solving #matrix #multiplication #efficiency #important #computer #science