Author | Ailleurs
Edit | Chen Caixian
Recently, Cambridge scholars published an article in the Journal of the National Academy of Sciences (PNAS) titled "The Difficulty of Computing Stable and Accurate Neural Networks: On the Barriers of Deep Learning and Smale's 18th Problem", making an interesting finding:
Researchers can demonstrate that neural networks with good approximate quality exist, but not necessarily algorithms that can train (or compute) such neural networks.
Address of the thesis: http://www.damtp.cam.ac.uk/user/mjc249/pdfs/PNAS_Stable_Accurate_NN.pdf
This is similar to Turing's view: regardless of computing power and runtime, a computer may not be able to solve some problems. In other words, even the best neural network may not be able to accurately describe the real world.
However, this does not mean that all neural networks are flawed, but that they can only achieve a stable and accurate state under certain circumstances.
By introducing a classical inverse problem, the research team proposed a classification theory that describes which neural networks can be computed by algorithms, giving a new answer to the historical question of what artificial intelligence can and cannot do.
At the same time, they developed a new model, "Rapid Iterative Restart Networks" (FIRENETs), which can ensure the stability and accuracy of neural networks in application scenarios. On the one hand, the neural network computed by FIRENETs is stable in combating perturbations and can stabilize unstable neural networks; on the other hand, it also achieves high performance and low false positive rate while maintaining stability.
Here's a quick introduction to the job:
1
Research background
Deep learning (DL) has been more successful than ever and is now making its way into scientific computing. However, while general approximation properties guarantee the existence of stable neural networks (NNs), current deep learning methods tend to be unstable. This problem makes the landing of deep learning in real life full of dangers.
Facebook (Meta) and New York University, for example, said at the 2019 FastMRI Challenge that networks that perform well on standard image quality metrics are prone to underreports and cannot reconstruct small but physically relevant image anomalies. The 2020 FastMRI Challenge focused on pathology, noting that "this illusory feature is unacceptable, especially if they simulate normal structures that either don't exist or are actually abnormal, which is very problematic." As the Adversity Research has demonstrated, neural network models can be unstable." A similar example exists in microscopy.
In different application scenarios, the tolerance for false positive rates and false positive rates is different. For scenarios with high error analysis costs, such false positives and false negatives must be avoided. Therefore, in application scenarios such as medical diagnosis, the "hallucination" of artificial intelligence may be very seriously dangerous.
For this problem , the classical approximation theorem shows that continuous functions can be arbitrarily approximated with neural networks well. Therefore, stability problems described by stabilization functions can often be solved stably with neural networks. This raises a fundamental question:
Why have stable and accurate neural networks been shown in some scenarios, and why are there unstable methods and "illusions" generated by AI in deep learning?
To answer this question, the researchers launched a study to determine the limits of what deep learning can reach in inverse problems.
In addition, neural networks in deep learning have a trade-off between stability and accuracy. Poor stability is the Achilles heel of modern artificial intelligence, and there is also a paradox in this regard: despite the existence of stable neural networks, training algorithms can still find unstable neural networks. This fundamental question is related to Steven Smale's 18th mathematical problem on the limits of artificial intelligence in 1998.
It is not difficult to calculate stable neural networks, for example, a zero network is stable, but it is not very accurate and therefore not particularly useful. The biggest question is: How do you compute a neural network that is both stable and accurate? Scientific computing itself is based on stability and accuracy, however, there are often trade-offs between the two, and sometimes accuracy must be sacrificed to ensure stability.
2
Classification theory: Conditions of existence of algorithms that calculate stable NNs
In response to the above problems, the author team proposes a classification theory that describes the sufficient conditions under which a neural network that reaches a certain accuracy (and stability) can be calculated by the algorithm.
They started with the classical inverse problem of a system of underdetermined systems of linear equations:
Here, A∈Cm ×N represents the sampling model (mpan>
Based on theorems 1 and 2 (see the paper for details of the theorems), they point to such a paradoxical problem:
There is a mapping from the training data to the appropriate neural network, but no training algorithm (even a random one) can calculate an approximation of the neural network from the training data.
One of the paper's authors, Hansen, makes an analogy: "There may be a cake, but there is no recipe for making it." He believes that the problem is not the "recipe", but the "tools" necessary to make the cake, it is possible that no matter what blender you use, you will not be able to make the cake you want, but in some cases, it may be that the blender in your own kitchen will be enough.
So under what circumstances? The research team categorized the algorithms for computational neural networks, explaining under what conditions an algorithm for computing neural networks would exist (which can also be compared to which cakes can be made with mixers with physical design possibilities):
Theorem 2
The existence of an algorithm that computes a neural network depends on the desired precision. For any positive integer K> 2 and L, there is a good state problem class, along with the following:
a) There is no random training algorithm (even a random one) that can compute a neural network with K-bit accuracy with more than 50% probability;
b) there is a definitive training algorithm that can compute neural networks with K-1 bit accuracy, but requires a lot of training data;
c) There is a definitive training algorithm that can compute a neural network with K-2 bit accuracy using no more than L training samples.
This suggests that some fundamental, essential obstacle prevents neural networks from being computed by algorithms. This is also why there are stable and accurate neural networks in some scenarios, but deep learning still has "illusions".
3
FIRENETs: Balancing stability with accuracy
There is a trade-off between the stability and accuracy of neural networks, and the performance of a stable neural network in inverse problems is often limited. This is particularly prominent in image reconstruction, where current methods of deep learning reconstructing images are unstable, as evidenced by:
1) A small perturbation in the image or sampling domain may produce serious artifacts in the reconstructed image;
2) A tiny detail in the image domain may be washed out in the reconstructed image (lack of accuracy), resulting in potential false negatives.
This type of linear inverse problem leads to an imbalance between the stability and accuracy of deep learning methods, making it impossible for any image reconstruction method to maintain high stability without sacrificing accuracy, and vice versa.
To solve this problem, the research team introduced a type of "rapid iterative restart network" (FIRENETs). Proven and numerically verified, FIRENETs are very stable. They found that under certain conditions, such as in MRI, there are algorithms that can compute stable neural networks for problems in Equation 1.
Crucially, they demonstrated that FIRENETs are robust to perturbations and can even be used to stabilize unstable neural networks.
FIRENETs are robust to perturbations
In stability testing, the team combined FIRENETs with V. Antun et al. (2020) developed automap networks for comparison. As shown in the upstream of the following figure, the AUTOMAP network reconstruction is very unstable, resulting in complete deformation of the image. The downside is the result of a reconstruction of the network using FIRENETs. Even in the worst reconstruction results, it remained stable.
This proves that the neural network computed by the FIRENETs algorithm is stable in combating perturbations in sparse images in wavelets, while maintaining some accuracy.
Stabilizer action of FIRENETs
At the same time, FIRENETs also act as a stabilizer. For example, in the following figure, the reconstruction from AUTOMAP is input to FIRENETs, and the results show that FIRENETs correct the output of AUTOMAP and stabilize the reconstruction.
Note: Add some FIRENET layers to the end of automap to stabilize it. On the far left is the reconstruction of AUTOMAP. The second from the left is a reconstruction of FIRENET x0 = Ψ( y). The second from the right is a reconstruction of FIRENET at y = Ax + e3. On the far right is a reconstruction of FIRENET after entering the measurements of autoMAP.
FIRENETs combine stability and accuracy
In the following illustration, a U-Net trained on an image containing an ellipse shape is stable, but when you add a detail that was not originally included in the training set, the stability of the U-Net is greatly affected.
Note: Neural networks with limited performance are trained to be stable. Consider three reconstruction networks Φj: Cm CN, j= 1, 2, 3. For each network, a perturbation value wj∈ CN is calculated, designed to simulate the worst effect, and a cropped perturbation image x+wj (rows two to four) is shown in the left column. The middle column (rows 2 through 4) shows the reconstructed image Φj (A(x+wj)) for each network. In the right column, start with "Can u see it?" The text form tests the network's ability to reconstruct h1 for tiny details.
It can be seen that the network trained under noisy measurements remains stable for worst-case perturbations, but not accurately. In contrast, noise-free trained networks are accurate but unstable. FIRENET strikes a balance between the two, and it is still accurate for stable images with sparse wavelets and in the worst case.
But this is not the end of the story, in real-life application scenarios, finding the optimal trade-off between stability and accuracy is the most important, which undoubtedly requires countless different technologies to solve different problems and stability errors.
Reference Links:
https://spectrum.ieee.org/deep-neural-network
http://www.damtp.cam.ac.uk/user/mjc249/pdfs/PNAS_Stable_Accurate_NN.pdf
Leifeng Network