DeepMind AI invents fast algorithms to solve tough math puzzles | Tech Rasta

An example from DeepMind AI of a math grid in gray and green with white numbers.

AlphaTensor is designed to perform matrix multiplications, but the same approach can be used to solve other mathematical challenges.Credit: DeepMind

Researchers at DeepMind in London have shown that artificial intelligence (AI) can find shortcuts in a basic type of mathematical calculation by turning a problem into a game, and then leveraging machine-learning techniques used by another of the company’s AI to beat human players. In games like Go and Chess.

The AI ​​has discovered algorithms that break decades-old records for computational efficiency, and the team’s findings were published on October 5 the nature1It could open new avenues for faster computing in some fields.

“It’s very impressive,” says Martina Seidl, a computer scientist at Johannes Kepler University in Linz, Austria. “This work demonstrates the potential of using machine learning to solve complex mathematical problems.”

Algorithms chasing algorithms

Advances in machine learning have allowed researchers to develop AIs that can produce language and predict the structures of proteins.2 Or identify hackers. Scientists are turning the technology back on itself to improve its own underlying algorithms using machine learning.

The AI ​​developed by DeepMind — called AlphaTensor — is designed to perform a type of calculation called matrix multiplication. It involves multiplying numbers — or matrices — arranged in grids that represent sets of pixels in images, wind conditions in a weather model, or the inner workings of an artificial neural network. To multiply two matrices together, the mathematician must multiply the individual numbers and add them in specific ways to produce the new matrix. In 1969, mathematician Volker Strassen discovered a way to multiply a pair of 2 × 2 matrices using seven multiplications.3Apart from eight, it prompts other researchers to search for more such tricks.

DeepMind’s approach uses a form of machine learning called reinforcement learning, in which an AI ‘agent’ (often a neural network) learns to interact with its environment to achieve a multi-step goal, such as winning a board game. If it does well, the agent is reinforced – its internal parameters are updated for future success.

AlphaTensor also includes a game-playing method called tree search, in which the AI ​​explores the results of branching possibilities as it plans its next move. In choosing which paths to prioritize during tree search, it asks the neural network to predict the most promising actions at each step. While the agent is still learning, it uses the results of its games as feedback to improve the neural network, which further refines the tree search, yielding more wins for learning.

Each game is a one-player puzzle that begins with a 3D tensor – a grid of numbers – filled in correctly. An alphatensor chooses from a collection of allowable moves and aims to bring all numbers to zero in the shortest steps. Each move, when inverted, represents a computation that combines the entries from the first two matrices to create an entry in the output matrix. The game is difficult because at each stage the agent has to choose from trillions of moves. “Designing the space of algorithmic discovery is very complex,” co-author Hussain Fauzi, a computer scientist at DeepMind, said in a press briefing, but “even more difficult is how we navigate this space”.

To give AlphaTensor a leg up during training, the researchers showed some examples of successful games so it wouldn’t have to start from scratch. And since the order of actions doesn’t matter, when it finds a successful sequence of moves, they also provide that sequence of moves as an example to learn from.

Efficient calculations

The researchers tested the system on input matrices up to 5 × 5. In many cases, the alphatensor rediscovered shortcuts devised by Strassen and other mathematicians, but in others it broke new ground. When multiplying a 4 × 5 matrix by a 5 × 5 matrix, for example, the previous best algorithm required 80 individual multiplications. AlphaTensor found an algorithm that only needed 76.

Pushmeet Kohli, Computer Scientist at DeepMind, said during a press briefing, “It’s amazingly intuitive to play these games. Fauzi said the nature “AlphaTensor does not incorporate human intuition about matrix multiplication”, so “the agent must in some sense form its own knowledge of the problem from scratch”.

The researchers tackled large matrix multiplications by creating a meta-algorithm that first broke the problems into smaller ones. When crossing the 11 × 12 and 12 × 12 matrix, their method reduced the number of required multiplications from 1,022 to 990.

AlphaTensor can also optimize matrix multiplication for specific hardware. The team trained the agent on two different processors, making it stronger not only when it took fewer steps but also when the runtime was reduced. In many cases, the AI ​​made matrix multiplications several percent faster than previous algorithms. And sometimes the fastest algorithms on one processor are not the fastest on another.

The same general approach has applications in other types of mathematical operations, such as decomposing complex waves or other mathematical objects into simpler ones. “It would be very exciting if this development could be used in practice,” said Virginia Wasilewska Williams, a computer scientist at the Massachusetts Institute of Technology in Cambridge. “A boost in performance will improve most applications.”

Gray Ballard, a computer scientist at Wake Forest University in Winston-Salem, North Carolina, sees the potential for future human-computer collaborations. “With this computational approach we’re able to push the boundaries a little further,” he said, “and I’m excited that theoretical researchers are starting to analyze the new algorithms they’ve discovered, where to look for the next breakthrough.”

Source link