Some AI Systems May Be Impossible to Compute

Deep neural networks are increasingly helping to design microchips, predict how proteins fold, and outperform people at complex games. However, researchers have now discovered there are fundamental theoretical limits to how stable and accurate these AI systems can actually get.

These findings might help shed light on what is and is not actually possible with AI, the scientists add.

In artificial neural networks, components dubbed “neurons” are fed data and cooperate to solve a problem, such as recognizing images. The neural net repeatedly adjusts the links between its neurons and sees if the resulting patterns of behavior are better at finding a solution. Over time, the network discovers which patterns are best at computing results. It then adopts these as defaults, mimicking the process of learning in the human brain. A neural network is dubbed “deep” if it possesses multiple layers of neurons.

Although deep neural networks are being used for increasingly practical applications such as analyzing medical scans and empowering autonomous vehicles, there is now overwhelming evidence that they can often prove unstable—that is, a slight alteration in the data they receive can lead to a wild change in outcomes. For example, previous research found that changing a single pixel on an image can make an AI think a horse is a frog, and medical images can get modified in a way that’s imperceptible to the human eye and causes an AI to misdiagnose cancer 100 percent of the time.

Previous research suggested there is mathematical proof that stable, accurate neural networks exist for a wide variety of problems. However, in a new study, researchers now find that although stable, accurate neural networks may theoretically exist for many problems, there may paradoxically be no algorithm that can actually successfully compute them.

“Theoretically, there are very few limitations on what neural networks can achieve,” says study co-lead author Matthew Colbrook, a mathematician at the University of Cambridge, in England. The problem emerges when trying to compute those neural networks. “A digital computer can only compute certain specific neural networks,” says study co-lead author Vegard Antun, a mathematician at the University of Oslo, in Norway. “Sometimes computing a desirable neural network is impossible.”

These new findings might sound confusing, as if one stated that a kind of cake may exist but that no recipe exists to create it.

“We would say that it is not the recipe that is the problem. Instead, it is the tools you have to make the cake that is the problem,” says study senior author Anders Hansen, a mathematician at the University of Cambridge. “We are saying that there might be a recipe for the cake, but regardless of the mixers you have available, you may not be able to make the desired cake. Moreover, when you try to make the cake with your mixer in the kitchen, you will end up with a completely different cake.”

In addition, to continue the analogy, “it can even be the case that you cannot tell whether the cake is incorrect until you try it, and then it is too late,” Colbrook says. “There are, however, certain cases when your mixer is sufficient to make the cake you want, or at least a good approximation of that cake.”

These new findings on the limitations of neural networks echo previous research on the limitations of mathematics from mathematician Kurt Gödel and on the limitations of computation from computer scientist Alan Turing. Roughly, they revealed “that there are mathematical statements that can never be proven or disproven and that there are basic computational problems that a computer cannot solve,” Antun says.

The new study finds that an algorithm may not be able to compute a stable, accurate neural network for a given problem no matter how much data it can access or the accuracy of that data. This is similar to Turing’s argument that there are problems that a computer may not solve regardless of computing power and run time, Hansen says.

“There are inherent limitations on what computers can achieve, and these limitations will show up in AI as well,” Colbrook says. “This means that theoretical results on the existence of neural networks with great properties may not yield an accurate description of what is possible in reality.” [READ MORE]