OCTOBER 6, 2022 by Bob Yirka , Tech Xplore
A team of researchers at Google’s DeepMind, London, has found that AI can find faster algorithms to solve matrix multiplication problems. In their paper published in the journal Nature, the group describes using reinforcement learning to improve math-based algorithms. A Research Briefing has also been published in the same journal issue summarizing the work by the team in London.
Math comes up quite often in computer programming, generally as a means for describing and then manipulating representations of real-world phenomena. For example, it is used to represent pixels on a computer screen, weather conditions or nodes in an artificial network. One of the major ways that math is used in such instances is to perform calculations on matrices. When programing games, for example, matrices describe possible movement options. For such movements to be realized, matrices are often multiplied or added together—sometimes both actions are needed. This requires a lot of work, especially as the matrices grow larger, which is why computer scientists have spent a lot of time and energy developing more and more efficient algorithms to get the job done. In 1969, for example, mathematician Volker Strassen figured out a way to multiply two 2×2 matrices using just seven multiplication operations rather than the eight that had been the standard.
In this new effort, the researchers at DeepMind wondered if it might be possible to use a reinforcement-learning-based AI system to create new algorithms with fewer steps than those now in use. To find out, they looked to gaming systems for inspiration, noting that most are based on reinforcement learning. After building some preliminary systems, the team turned its focus to tree searching, which is also used in game programming. It is a means for a system to look at various scenarios given a particular situation. When applied to multiplying matrices, the researchers found that converting an AI system to a game allowed for searching for the most efficient way to get to a desired outcome—a mathematical result.
The researchers tested their system by allowing it to search for, review and then use existing algorithms, using rewards as an enticement to pick the one that was most efficient. The system learned about the factors that contribute to matrix multiplication efficiency. Next, the researchers allowed the system to create its own algorithm, again looking to improve efficiency. The researchers found that in many instances, the algorithms chosen by the system were better than those that had been created by their human predecessors.
More information: Alhussein Fawzi et al, Discovering faster matrix multiplication algorithms with reinforcement learning, Nature (2022). DOI: 10.1038/s41586-022-05172-4
Artificial intelligence finds faster algorithms for multiplying matrices, Nature (2022). DOI: 10.1038/d41586-022-03023-w
Journal information: Nature
Leave a Reply