Neural network approximations and regularity

Abstract

A neural network transforms input data x by a cascade of linear operators represented by matrices of coefficients, followed by pointwise nonlinearities such as sigmoids or rectifiers. This implements a class of functions that is parameterized by the matrices used to calculate the successive layers. Learning optimizes these parameters to minimize the approximation error of a function y = f (x). This error is evaluated on training examples. We face two types of problem. The approximation problem consists in showing that there exists a function in the class of neural network functions, which precisely approximates f(x). The second problem is to optimize the network parameters in order to calculate the best approximation that minimizes the approximation error. This optimization is performed using a gradient descent algorithm that progressively adjusts the parameters to reduce the error at each iteration. This lecture focuses on the approximation problem.

The approximation error typically depends on the regularity of the function f(x) being approximated. If this function is Lipchitz, it is shown that to reach an error e requires a number of examples that grows exponentially as ^e-d. This is the curse of high dimension d. To avoid this curse, the function f(x) must be much more regular, and the network must be able to use this underlying regularity. A mathematical challenge is to understand the nature of the regularity that is exploited by deep neural networks.

In high dimensions, it is necessary to use global regularity constraints. This regularity can be captured by the symmetry group of f(x). A symmetry is an operator g that does not change the value of f : f (g.x) = f (x) for all x. The set of symmetries has a group structure. We often have a priori information about these symmetries. For example, many image recognition problems are invariant by translation, certain rotations or certain deformations. For sound, these symmetries include frequency transpositions or deformations in the time-frequency plane.

The architecture of a convolutional neural network incorporates information about these symmetries by imposing that the weights of the network are translationally invariant. Numerical experiments show that neural networks reproduce other symmetries by calculating coefficients that are increasingly invariant as the depth of the network increases. An important question is to understand the link between the coefficients learned by the network and the groups of symmetries.

The existence of scale separation is another important source of regularity. In physics, the interaction of d particles can often be approximated by interactions of groups of particles of varying sizes, allowing us to go from d variables to O(log d) variables, which represent each of the groups. These scale-separation properties can be found in most applications, including image and sound recognition, language analysis and physics. In the simplest cases, they can be expressed by hierarchical relationships that can be represented by trees. However, these structures are often too rigid to explain the complexity of interactions across scales. The mathematics used to represent such interactions is based on the wavelet transform. In neural networks, the separation of scales is observed in the hierarchical structure of computations across layers.

A third source of regularity is captured by the notion of parsimony. This involves understanding whether there are " prototypes " of shapes that play an important role in the value taken by f(x). This can be formalized by a parsimonious approximation in a dictionary of vectors. This parsimony is found at the output of a network's neurons, whose responses are often zero. The aim is to understand whether a neural network has the ability to learn from dictionaries, and whether it approximates the function f(x) from a parsimonious representation in a dictionary.

The mathematical challenge is to relate these notions of regularities to the optimization capabilities of neural networks, and to understand the properties of classes of functions that are well approximated by such a network.

Neural network approximations and regularity

Abstract

Speaker(s)

Stéphane Mallat

Events

Introduction to deep neural networks

Introducing 7 data challenges 2019 (1)

Applications of deep neural networks

Introducing 7 data challenges 2019 (2)

Neural network approximations and regularity

Presentation of the 2018 challenge winners

The origins : cybernetics and the perceptron

Weakly supervised learning for visual recognition

Universal single-layer hidden network approximation

Natural language

Approximation error with a hidden layer and regularity

Automatic video analysis

Maximum likelihood network optimization

Deep reinforcement learning

Gradient descent and gradient backpropagation

Convergence of stochastic gradient descent

See also