Cours 3 : Les réseaux de neurones comme approximateurs

Limites des méthodes d'approximation linéaires

1. Introduction et Contexte

L'objectif de ce chapitre est de démontrer que les méthodes d'approximation linéaires souffrent du fléau de la dimension lorsqu'elles sont appliquées à certaines classes de fonctions régulières. Ce résultat motive l'utilisation de méthodes non-linéaires (réseaux de neurones) qui atteignent de meilleurs taux de convergence.

Remarque : Un réseau de neurones avec N neurones peut être beaucoup plus performant pour approximer une fonction de d variables qu'un sous-espace de dimension N préfixé (polynômes, ondelettes, etc.).

2. Cadre Mathématique

2.1 La classe de fonctions `\mathcal{F}_C`

Définition — Classe de régularité $\mathcal{F}_C$

Soit C > 0. On définit \mathcal{F}_C comme l'ensemble des fonctions f \in L^2([0,1]^d) dont la transformée de Fourier F(\vec{\omega}) vérifie :

\mathcal{F}_C = \left\{ f \;\middle|\; f(\vec{x}) = \int_{\mathbb{R}^d} F(\vec{\omega})\, e^{2\pi i \vec{\omega} \cdot \vec{x}}\, d\vec{\omega} \;\text{ et }\; \int_{\mathbb{R}^d} \|\vec{\omega}\|_1\, |F(\vec{\omega})|\, d\vec{\omega} \le C \right\}

où \|\vec{\omega}\|_1 = \sum_{j=1}^d |\omega_j|.

2.2 Écart de Kolmogorov

Définition — Écart de Kolmogorov

Pour une classe K \subset L^2([0,1]^d), l'écart de dimension $N$ est :

w_N(K) = \inf_{H_N,\, \dim(H_N) \le N} \sup_{f \in K} \|f - \text{proj}_{H_N} f\|_{L^2}

C'est l'erreur d'approximation minimale atteignable par n'importe quel sous-espace linéaire de dimension au plus N.

3. Résultat Principal : Fléau de la Dimension

Théorème

Il existe \kappa > 0 tel que pour tout N \ge 1 et d \ge 1 :

w_N(\mathcal{F}_C) \ge \kappa\, \frac{C}{d}\, \frac{1}{N^{1/d}}

Ce résultat montre que pour toute méthode d'approximation linéaire, l'erreur décroît comme N^{-1/d} : plus la dimension d est grande, plus la convergence est lente.

4. Preuve du Théorème

Étape 1 : Fonctions de test

Soient \{\vec{k}_j\}_{j=1}^{2N} \subset \mathbb{N}^d, ordonnés par \|\vec{k}_1\|_1 \le \dots \le \|\vec{k}_{2N}\|_1. On définit :

h_j^*(\vec{x}) = \cos(2\pi\, \vec{k}_j \cdot \vec{x}), \quad j = 1, \dots, 2N

Étape 2 : Normalisation

Lemme : La fonction f_{\vec{k}}(\vec{x}) = \frac{C}{2\|\vec{k}\|_1}\cos(2\pi\, \vec{k} \cdot \vec{x}) appartient à \mathcal{F}_C.

Preuve : La transformée de Fourier de \cos(2\pi\, \vec{k} \cdot \vec{x}) est \frac{1}{2}(\delta_{\vec{k}} + \delta_{-\vec{k}}). Ainsi :

\int \|\vec{\omega}\|_1 |F_{f_{\vec{k}}}(\vec{\omega})|\, d\vec{\omega} = \frac{C}{4\|\vec{k}\|_1}\left(\|\vec{k}\|_1 + \|-\vec{k}\|_1\right) = \frac{C}{2} \le C \quad \square

Étape 3 : Borne sur l'erreur

Pour tout sous-espace H_N de dimension N, il existe une combinaison des 2N fonctions de test qui est orthogonale à H_N. L'erreur est alors minorée par :

w_N(\mathcal{F}_C) \ge \min_{j \in \{1, \dots, 2N\}} \frac{C}{2\sqrt{2}\,\|\vec{k}_j\|_1} = \frac{C}{2\sqrt{2}\,\|\vec{k}_{2N}\|_1}

Étape 4 : Argument combinatoire

Le nombre de vecteurs \vec{k} \in \mathbb{N}^d tels que \|\vec{k}\|_1 \le m est \binom{m+d}{d}. On cherche m tel que \binom{m+d}{d} \ge 2N.

En utilisant l'inégalité \binom{m+d}{d} \ge \left(\frac{m}{d}\right)^d, la condition est satisfaite si m \ge d\,(2N)^{1/d}.

Étape 5 : Conclusion

En substituant dans la borne de l'étape 3 :

w_N(\mathcal{F}_C) \ge \frac{C}{2\sqrt{2} \cdot d\,(2N)^{1/d}} \ge \kappa\, \frac{C}{d}\, \frac{1}{N^{1/d}}

Ceci démontre que pour les méthodes linéaires, l'erreur décroît de plus en plus lentement à mesure que d augmente — c'est le fléau de la dimension.

3.8 KiB Raw Permalink Blame History