In the history of science and technology, mathematics has provided a theoretical basis for engineering technology and guided its future development direction; in turn, engineering technology has presented new challenges to mathematics and promoted the development of mathematical theory. Deep learning and optimal transmission theory have once again verified this historical development model.
The sociological bottleneck of deep learning
Deep learning has achieved great success in the field of engineering technology. The intrinsic reason is that natural data sets have inherent laws: the manifold distribution law, that is, a type of natural data can be regarded as a probability distribution on a low-dimensional data manifold embedded in a high-dimensional background space. Deep learning algorithms can be decoupled into learning manifold structures and learning probability distributions. In deep learning algorithms, the manifold structure is represented as encoding mapping and decoding mapping, that is, the local parameterization of the data manifold; the probability distribution can be represented as a Gibbs potential energy function, or an optimal transmission mapping. Optimal transmission mapping maps white noise (Gaussian or uniform distribution) into data distribution. All mappings, encoding, decoding, transmission mapping, etc. are approximated by deep neural networks.
Based on the geometric approximation theory, we reconstruct the data manifold from a set of discrete sampling points in order to ensure that the reconstructed manifold is consistent with the initial data manifold. Here, the so-called consistency has different meanings, usually from weak to strong, referring to the consistency of topology, Hausdorff distance, Riemannian metric and differential operators, which require different sampling requirements. For example, areas with high curvature, areas with small injective radius, and areas with high data distribution density require denser sampling. It can be seen that in order to train a deep learning model, we need dense sampling points on the data manifold, and the distribution of sampling points faithfully reflects the distribution of real data. Therefore, we need a lot of training data.
However, a lot of big data is related to personal privacy and is highly sensitive, and cannot be directly publicly provided for use by all walks of life. This has become a bottleneck in the sociology of deep learning in the future. Generative models are a powerful technical method to break through bottlenecks and achieve data desensitization. For example, face image data sets leak face information and invade personal privacy; but for deep learning face recognition algorithms, we need a large number of face images for training and improving model performance. At this time, we can apply the generative model to generate a large number of face pictures. These pictures look the same as real people, but do not exist in real life, so they will not infringe on anyone's privacy, and they can also help the face recognition model improve the performance.
Figure 0. The generated face image has no sociological significance and reflects the statistical characteristics of real data.
The theoretical explanation of this method is as follows: If we accurately grasp the information of the data manifold and the distribution of the data, we use number theory methods to generate pseudo-random variables that satisfy uniform distribution, and use optimal transmission mapping and decoding mapping to transform them into random variables on the data manifold that satisfy the data distribution. In this way, we obtain the generated samples, which are the generated face images. According to the geometric measure theory, the data manifold is a continuum and the training data set is a discrete point set, so the probability of the generated sample falling on the training data set is zero. (In the actual algorithm, restrictions can also be added to prevent the generated samples from falling within the training set.) Even if the encoding, decoding mapping and optimal transmission mapping are fully disclosed, the user can trace back the generated face image to the computer-generated random number, but this random number has no sociological significance. Uniformly distributed information entropy is the largest and information leakage is the least.
At the same time, this method maintains the statistical properties of the data set and the generated data set conforms to the real data distribution. Therefore, for practical applications based on statistical properties, the generated data perfectly answers the questions they are concerned about. For example, a clothing design company needs the distribution of various human body shapes among the population to determine the production ratio of clothing of various sizes. This information can be calculated by statistically generating data. It can be seen that as people pay more and more attention to data security and privacy protection, the application of generative models will become more extensive and in-depth.
Algorithmic bottlenecks of deep learning
One of the main algorithm bottlenecks of deep learning is the so-called mode collapse problem, which is manifested in that the model is too sensitive to hyperparameters, training convergence is difficult, and the error fluctuates for a long time; if the data distribution has multiple modes, the generated data will lose some modes, or the generated data will cover all modes, but at the same time generate distorted data outside the mode.
The internal reasons for mode collapse can be analyzed as follows: all mappings in deep learning are approximated by deep neural networks, but deep networks can only express continuous mappings; however, the transfer transformation between probability distributions may be discontinuous transformations. This essential contradiction leads to model collapse. So under what circumstances is the optimal transmission mapping discontinuous? This needs to be answered by the optimal transport mapping regularity theory. Although optimal transmission theory has been developed for more than two hundred years, traditional mathematicians only care about continuous optimal transmission mappings and do not have much research on non-continuous singular sets. Therefore, the theory of optimal transmission mapping singular sets has been at a stage that has not yet been deeply explored. The rise of deep learning will ignite great enthusiasm among mathematicians, and the development of this field will usher in a leap.
optimal transmission theoryLet's recall the classic optimal transmission theory. The given distribution is defined on the open set, and the sum distribution on , satisfies the equilibrium condition. A mapping is said to be measure-guaranteed if it exists for all Borel sets. Given a transmission cost function, the Monge problem searches for the minimum total transmission cost among all measure-preserving mappings.
The solution to Monge's problem is called the optimal transport map.
Brenier theory shows that in a more general case, there is a convex function defined on , which is called the Brenier potential energy function, and its gradient map gives the optimal transmission map. By the measure-guaranteed condition, we can get the Monge-Ampere equation. Assuming that the density function is and, we have
|
|
|
Figure 1. If the source region and target region are both convex sets and the density function is smooth, then the Brenier potential energy is smooth.
The classic Monge-Ampere equation regularity theory assumes that sum is a convex set. For example, the density function satisfies the smoothness condition. At this time, the Brenier potential energy function and the optimal transmission map are smooth, and there are no singular sets. As shown in Figure 1, and are both unit disks, the Brenier potential energy function is smooth, the optimal transmission map is continuous, and there is no singular set.
|
|
|
|
Figure 2. If the target region is non-convex, the optimal transmission map is non-continuous and the Brenier potential energy is non-smooth.
As shown in Figure 2, we calculate the optimal transmission mapping between the uniform distribution on the unit disk to the distribution area on the hippocampus area (bottom row), then the Brenier potential energy function (top row) is globally continuous, but not differentiable along the red curve. On the unit disk, the projection of the red curve is a black curve, which is called a singular set. The optimal transmission map is discontinuous on the singular set. Therefore, the transport map is a non-contiguous map. If the target region is close to a convex set, then it is possible that the optimal transmission map is still continuous.
A natural question is: What are the necessary and sufficient conditions for the existence of singular sets? The answer to this question is essentially related to mode collapse in deep learning. Here we use the curvature of the region boundary to give a sufficient condition, the so-called "walking the dog" theorem.
"Walking the dog" theorem
As shown in the left frame of Figure 3, suppose there is a friend walking his dog. The friend's trajectory on the plane is a closed curve, and the dog's trajectory is another closed curve. Both people and dogs walk counterclockwise. At any moment, they always face forward on their respective tracks and never look back (but after walking in a circle, they will return to the starting point as a whole).
Figure 3. Among various dog walking methods, the shortest dog leash length is equal to the Frechet distance between curves.
Frechet distanceThere is a corresponding relationship between the positions of people and dogs at the same time, which naturally gives a homeomorphic mapping between orbits. Equivalently, we use parameters to represent it. From the assumption that neither man nor dog looks back, we naturally have the same for any time. Then different dog walking methods correspond to different homeomorphism mappings. If a dog walking method is fixed, the length of the dog leash should not be less than the maximum distance between the person and the dog at any time. Of all possible ways to walk your dog, the shortest leash length is equal to
We define the shortest possible leash length as the Frechet distance of and .
In computational geometry, people have fully studied the algorithm of Frechet distance. As shown in the right frame of Figure 3, we use the horizontal axis to represent the parameters and the vertical axis to represent the parameters. Any homeomorphic map can be expressed as a curve connecting diagonal points, and the curve is monotonic in both horizontal and vertical directions. Given a, for any point within the square, if, we draw it red, otherwise it is white. Then the white area is the free area and the red area is the forbidden area. If there is a horizontal and vertical monotonic curve in the white area connecting the diagonal points, the Frechet distance between the two curves is less than . In actual calculations, we can use the bisection method to search and find the Frechet distance.
Normal Frechet distanceSimilarly, if and are well regularized, i.e. they are smooth, then the normal vectors along the curve are well defined. From this we can define the normal Frechet distance: we replace the distance between the location of the person and the dog with the distance between the external normal vector of the location of the person and the dog, and the formula is written as
Here is the geodesic distance on the unit circle.
tilt conditionsGiven the optimal transmission mapping between plane areas, the boundary curve sum is second-order smooth and satisfies certain smoothness conditions. Then the optimal transmission mapping can be extended to the boundary, and satisfies the so-called obliqueness condition (Obliqueness Condition), that is, given a point on the boundary,
That is, the angle between the normal vector of the boundary point and the normal vector of the corresponding image point is less than or equal to a right angle.
dog walking theorem Assume that the probability distribution defined on the plane area is known, and , where the probability density function satisfies a relatively broad regularity condition, and the boundary curve sum is second-order smooth; if the normal Frechet distance of and is greater than, the optimal transmission map is discontinuous and there is a singular set.If there is no singular set in the optimal transmission map and the Brenier potential energy function is globally differentiable, it can be extended to the boundary, and the limit on the boundary is homeomorphism and satisfies the tilt condition, so the normal Frechet distance of and is not greater than a right angle, which is a contradiction. So we conclude that there are singular sets, and the optimal transmission map is discontinuous on singular sets.
Figure 4. Curvature conditions for the existence of singular sets.
curvature conditionAccording to the dog-walking theorem, we can give some curvature conditions for the existence of singular points in some optimal transmission maps. As shown in the left frame of Figure 4, if there is a section of curve with a total curvature less than that, it exists,
is a convex set, then the optimal transmission mapping must have a singular set. As shown in the right frame of Figure 4, the horizontal axis is and the vertical axis is. Both curves take arc length parameters. For any point, if the angle between the normal vector at and the normal vector at is greater than , we will draw it in red, otherwise it will be green. The green area is the free area. The starting point is , and the end point is , which corresponds to the bottom edge and the top edge of the right rectangle. The green areas on the bottom and top sides are exactly complementary, so there is no monotonous curve in the green area along both the horizontal and vertical directions. This means that the normal Frechet distance of and must be greater than , there must be a singular set, and the optimal transmission map is discontinuous on the singular set. In this case, the optimal transmission mapping cannot be directly represented by a deep neural network.
Promotion and Outlook
Optimal transport mapping in high dimensions is more complex than optimal transport mapping in the plane, but the same idea can be generalized. For example, in the three-dimensional case, assuming it is a region in three-dimensional space, its boundary sum is a smooth surface, and its normal Frechet distance is defined as:
If the normal Frechet distance is greater than , then there is a singular set of optimal transmission maps. The dog-walking theorem gives sufficient conditions for the existence of singular sets, but the necessary conditions are not yet clear. There are still many open problems in the topological characterization of singular sets. These basic questions require answers from basic mathematicians.
In deep learning, the data distribution support in the latent space often has complex topology and is not geometrically convex. Singular sets inevitably exist in transmission mapping, so deep neural networks cannot express this discontinuous mapping. In order to avoid mode collapse, we can use a neural network to express the Brenier potential energy function, or use a specific numerical approximation method. On the other hand, the Monge-Ampere equation is strongly nonlinear, and the high-dimensional optimal transmission mapping has high computational complexity. How to design more efficient algorithms and hardware more suitable for solving problems also poses a challenge to computer scientists.
We believe that the regularity theory of optimal transmission mapping will be further developed in the future, which can provide profound insights and characterizations of singular sets, thereby better guiding the statistical theory of deep learning. We also believe that more models based on optimal transmission theory will be proposed and explored in depth in the field of deep learning, fundamentally overcoming bottleneck problems such as mode collapse, and making the black box transparent.
The next time you walk the dog, I hope your friends can think deeply about the model collapse problem of deep learning, and also think about how to "walk an eagle" on the entire earth's surface, so as to experience the high-dimensional Frechet distance.
Machine-translated from the Chinese original 深度学习的“瓶颈”与“遛狗”定理 (published 2021-06-02). WeChat original ↗