room / 3 × 3 color matrix.
Orrich Lawson / Getty Images
Matrix multiplication has been the focus of many machine learning hacks and has been accelerated by a factor of 2. Last week, DeepMind announced that it has discovered a more efficient way to perform matrix multiplication, breaking a 50-year record. . This week, two Austrian researchers from Johannes Kepler University in 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 particularly good at matrix multiplication performance due to their massive parallelism. They can break down large matrix math problems into many parts and use special algorithms to attack parts of them at the same time.
In 1969, a German mathematician named Volker Strassen discovered an earlier better 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 Strassen’s algorithm can perform the same feat of 49 multiplications.
room / Example of multiplying DeepMind matrices with imaginary arcs and colored digital circles.
deep mind
DeepMind 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 calculations done every day on GPUs, 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 descends from AlphaGo (who beat the 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 his entries through a series of allowed moves according to the instructions of the algorithm. If the player is able to do this, it will result in a demonstrable integer matrix multiplication algorithm for any pair of matrices, whose efficiency is captured by the number of steps taken for a zero outside the tensor would be
So DeepMind used reinforcement learning to train AlphaTensor to play this fantasy sports game. This is similar to how AlphaGo learns to play. he goes– and gradually improved over time, rediscovering and surpassing the work of Strassen and other human mathematicians, according to DeepMind.
As a more complex example, AlphaTensor 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 published a research paper in which it claims to have reduced that number by a factor of 95. It is no coincidence that this record breaking new algorithm appeared very quickly. Kauers and Moosbauer write in their article: [DeepMind’s researchers] Apply a series of transformations that lead to a pattern that can eliminate a single multiplication. “
Technological advancement stands on its own, and as artificial intelligence searches for new algorithms, the records of old math 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 accelerate their implementation.
