Can artificial intelligence (AI) make its own algorithms to speed up matrix multiplication, one of machine learning’s most fundamental tasks? Today, DeepMind unveiled AlphaTensor, the “first artificial intelligence system for discovering novel, efficient, and provably correct algorithms.” The Google-owned lab said the research “shedding light” on a 50-year old open question in mathematics.
Computer science has been on a quest to surpass the speed of multiplying two matrices since the Strassen algorithm was invented in 1969. While matrix multiplication is one of algebra’s simplest operations taught in high school mathematics, it is also one of the most fundamental computational tasks and, as it turns out, one of today’s neural networks.
Matrix multiplication is used to process smartphone images, understand speech commands, create computer graphics for computer games, data compression, and more. Today, businesses purchase expensive GPU hardware to boost matrix multiplication efficiency, so any additional speed would be game-changing in terms of lowering costs and saving energy.
According to a DeepMind blog post, AlphaTensor builds on AlphaZero, a gamer that has shown exceptional ability on board games like chess and Go. This new work extends the AlphaZero journey, reaching beyond playing games to solving mathematical problems.
DEEPMIND MAKES USE OF ARTIFICIAL INTELLIGENCE TO IMPROVE COMPUTER SCIENCE.
At a press conference, Pushmeet Kohli, the head of Artificial Intelligence at DeepMind, discussed how AI might be utilized to improve computer science itself.
“This has enormous potential because we might be able to go beyond the current algorithms, which might result in enhanced efficiency,” said the author.
This is a particularly difficult task, according to the speaker, because the discovery of new algorithms is so difficult, and automating algorithmic discovery using AI involves a long and complex reasoning process, from forming intuition about the algorithmic problem to proving that the algorithm is correct in certain instances.
“This is a complex set of steps, and AI has not been very good at that so far,” said the speaker.
A’INTRIGUING, MIND-BOGGLING ISSUE’
DeepMind tackled the matrix multiplication challenge because it’s a well-known problem in computation, according to the author.
“It’s also a very interesting, mind-boggling problem because matrix multiplication is something that we studied in high school,” he said. “We’re still working on the best technique to actually multiply these two sets of numbers,” it’s also extremely stimulating for researchers to begin to understand this better.
AlphaTensor discovered algorithms that are more efficient than the state of the art for many matrix sizes and outperform human-designed ones, according to DeepMind.
AlphaTensor starts without knowing what is going on, and then gradually improves over time, according to Kohli, before discovering historic algorithms such as Strassen’s. At some point, it surpasses them and discovers completely new algorithms that are faster than previously.
Kohli said he expects that this paper will inspire others to pursue algorithmic discovery for other fundamental competition tasks. “We think this is a significant step on our journey towards really using AI for algorithmic discovery,” he said.
ALPHATENSOR FROM DEEPMIND USES ALPHAZERO.
AlphaZero, a single-player game, is similar to DeepMind’s staff research engineer, Thomas Hubert. “It is the same algorithm that learned to play chess that was used here for matrix multiplication, but it needed to be extended to handle this infinitely large space,” he said.
DeepMind claims that this game is so complex that “the amount of possible algorithms to consider is greater than the number of atoms in the universe, even for small cases of matrix multiplication.” Compared to Go, which was an AI challenge for decades, the number of possible moves is 30 orders of magnitude greater.
“The game is about basically zeroing out the tensor, with some allowed moves that are actually representing some algorithmic operations,” he added. “This gives us two very important results: one, that if you can decompose the tensor perfectly, you’re guaranteed to have a provably correct algorithm.”
AlphaTensor discovers a vaster range of matrix multiplication algorithms than previously assumed, with thousands of algorithms for every dimension.
According to the blog post, the authors modified AlphaTensor to specifically look for fast algorithms on a given hardware, such as Nvidia V100 GPU and Google TPU v2, which demonstrate AlphaTensor’s flexibility in optimizing arbitrary objectives.
INCREASED IMPACT OF ARTIFICIAL INTELLIGENCE ON SCIENCE AND MATHEMATICS
Researchers showed that DeepMind’s AlphaFold tool could predict the structures of more than 200 million proteins from over a million species, which covered almost every known protein on earth in July. Kohli said that AlphaTensor highlights the potential that AI has not only in science, but also in mathematics.
It’s personally fantastic to see AI exceed human scientists’ expectations for the last 50 years. “It just demonstrates the potential of AI and machine learning.”
Source: list23.com
