86 lines
3.8 KiB
Markdown
86 lines
3.8 KiB
Markdown
|
# 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**.
|