room / 3×3 color matrix.
Orrich Lawson / Getty Images
Matrices multiplication has been at the heart of many machine learning hacks and has been sped up by a factor of 2. Last week, DeepMind announced that it had discovered a more efficient way to perform matrix multiplication, smashing a 50-year record. This week, two Austrian researchers at Johannes Kepler University Linz claimed to have broken the new record.
Matrix multiplication, the multiplication of two rectangular arrays of numbers, is commonly at the heart of speech recognition, image recognition, smartphone image processing, compression, and computer graphics creation. GPUs are especially good at matrix multiplication performance due to their massive parallelism. They can break large matrix math problems into many parts and use special algorithms to attack parts of them simultaneously.
In 1969, a German mathematician named Volker Strassen discovered an earlier best algorithm for multiplying 4×4 matrices that reduced the number of steps required to perform matrix calculations. For example, multiplying two 4×4 matrices using traditional class methods requires 64 multiplications, while the Strassen algorithm can perform the same feat of 49 multiplications.
room / Example of DeepMind matrix multiplication with imaginary arcs and colored digital circles.
deep mind
DeepMind has found a way to reduce this number to 47 using a neural network called AlphaTensor.
Going from 49 steps to 47 doesn’t seem like much, but with trillions of matrix computations being done on GPUs every day, the incremental improvements are huge efficiency gains, allowing AI to run faster on existing applications. hardware.
If math is just a game, AI wins
AlphaTensor is descended from AlphaGo (who beat world champion) he goes AlphaZero works on chess and shogi. DeepMind calls AlphaTensor “the first artificial intelligence system to discover new, efficient and correct algorithms for basic tasks such as matrix multiplication.”
To discover more efficient matrix math algorithms, DeepMind defined the problem as a single player game. The company detailed the process in a blog post last week.
In this game, the board is a 3D tensor (array of numbers) that captures how correct the current algorithm is. The player adjusts the tensor and attempts to eliminate its entries through a series of allowed moves according to the algorithm’s instructions. If the player is able to do so, it will result in a provable integer matrix multiplication algorithm for any pair of matrices, the efficiency of which is captured by the number of steps taken for a zero outside the tensor would be
Then DeepMind used reinforcement learning to train AlphaTensor to play this fantasy sports game. This is similar to how AlphaGo learns how to play. he goes— and gradually improved over time, eventually rediscovering and surpassing the work of Strassen and other human mathematicians, according to DeepMind.
As a more complex example, AlphaTensor has discovered a new method that multiplies the 5 x 5 matrix by 96 steps (the old method had 98 steps). This week, Johannes Manuel Kors and Jacob Mössbauer Kepler University in Linz, Austria, has published a research paper claiming to have reduced that number by a factor of 95. It is no coincidence that this new record-breaking algorithm appeared very quickly. Kauers and Moosbauer write in their paper: [DeepMind’s researchers] Apply a series of transformations that lead to a scheme that can eliminate a single multiplication. “
Technological progress stands on its own, and as artificial intelligence searches for new algorithms, the records of old mathematics may soon be lost. Just as computer-aided design (CAD) has made it possible to develop more complex and faster computers, artificial intelligence can help human engineers speed up their deployment.
