Alexis BAYLET
d35d4c964b
- Introduced Chapter 0: Introduction to Statistical Estimation with foundational concepts and methods. - Added Chapter 1: Non-Parametric Density Estimation covering kernel methods and performance analysis. - Included Chapter 2: Theory of Regression focusing on non-parametric methods and regularization techniques. - Implemented Chapter 3: Neural Networks as Approximators discussing the limitations of linear approximation methods. - Added corresponding PDF files for each chapter.
119 lines
No EOL
4.5 KiB
TeX
119 lines
No EOL
4.5 KiB
TeX
\documentclass[11pt]{article}
|
|
\usepackage[utf8]{inputenc}
|
|
\usepackage[T1]{fontenc}
|
|
\usepackage[french]{babel}
|
|
\usepackage{amsmath, amssymb, amsthm}
|
|
\usepackage{geometry}
|
|
\geometry{a4paper, margin=2.5cm}
|
|
|
|
% Définition des environnements
|
|
\newtheorem{theorem}{Théorème}
|
|
\newtheorem{lemma}[theorem]{Lemme}
|
|
\newtheorem{definition}{Définition}
|
|
\newtheorem{remark}{Remarque}
|
|
|
|
% Commandes mathématiques
|
|
\newcommand{\R}{\mathbb{R}}
|
|
\newcommand{\N}{\mathbb{N}}
|
|
\newcommand{\Fcal}{\mathcal{F}}
|
|
\newcommand{\norm}[1]{\left\|#1\right\|}
|
|
\newcommand{\abs}[1]{\left|#1\right|}
|
|
\newcommand{\ud}{\mathrm{d}}
|
|
\newcommand{\dx}{\ud \vec{x}}
|
|
\newcommand{\dw}{\ud \vec{\omega}}
|
|
\newcommand{\x}{\vec{x}}
|
|
\newcommand{\w}{\vec{\omega}}
|
|
\newcommand{\kvec}{\vec{k}}
|
|
\newcommand{\proj}{\text{proj}}
|
|
\newcommand{\spanvec}{\text{span}}
|
|
|
|
\title{Cours 3 : Les réseaux de neurones comme approximateurs \\ \large Limites des méthodes d'approximation linéaires}
|
|
\author{}
|
|
\date{}
|
|
|
|
\begin{document}
|
|
|
|
\maketitle
|
|
|
|
\section{Introduction et Contexte}
|
|
|
|
L'objectif de ce chapitre est de démontrer que les méthodes d'approximation linéaires souffrent du \textbf{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.
|
|
|
|
\begin{remark}
|
|
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é (comme les polynômes ou les ondelettes).
|
|
\end{remark}
|
|
|
|
\section{Cadre Mathématique}
|
|
|
|
\subsection{La classe de fonctions $\Fcal_C$}
|
|
|
|
\begin{definition}[Classe de régularité $\Fcal_C$]
|
|
Soit $C > 0$. On définit la classe $\Fcal_C$ comme l'ensemble des fonctions $f \in L^2([0,1]^d)$ dont la transformée de Fourier $F(\vec{\omega})$ vérifie :
|
|
\begin{equation}
|
|
\Fcal_C = \left\{ f \mid f(\vec{x}) = \int_{\R^d} F(\vec{\omega}) e^{2\pi i \vec{\omega} \cdot \vec{x}} \dw \text{ et } \int_{\R^d} \|\vec{\omega}\|_1 |F(\vec{\omega})| \dw \le C \right\}
|
|
\end{equation}
|
|
où $\|\vec{\omega}\|_1 = \sum_{j=1}^d |\omega_j|$.
|
|
\end{definition}
|
|
|
|
\subsection{Écart de Kolmogorov}
|
|
|
|
\begin{definition}[Écart de Kolmogorov]
|
|
Pour une classe $K \subset L^2([0,1]^d)$, l'écart de dimension $N$ est :
|
|
\begin{equation}
|
|
w_N(K) = \inf_{H_N, \dim(H_N) \le N} \sup_{f \in K} \norm{f - \proj_{H_N}f}_{L^2}
|
|
\end{equation}
|
|
\end{definition}
|
|
|
|
\section{Résultat Principal : Fléau de la Dimension}
|
|
|
|
\begin{theorem}
|
|
Il existe $\kappa > 0$ tel que pour tout $N \ge 1$ et $d \ge 1$ :
|
|
\begin{equation}
|
|
\label{eq:lower_bound}
|
|
w_N(\Fcal_C) \ge \kappa \frac{C}{d} \frac{1}{N^{1/d}}
|
|
\end{equation}
|
|
\end{theorem}
|
|
|
|
[Image of curse of dimensionality in function approximation]
|
|
|
|
\section{Preuve du Théorème}
|
|
|
|
\subsection{Étape 1 : Fonctions de test}
|
|
Soient $\{\kvec_j\}_{j=1}^{2N} \subset \N^d$, ordonnés par $\|\kvec_1\|_1 \le \dots \le \|\kvec_{2N}\|_1$. On définit :
|
|
\[ h_j^*(\x) = \cos(2\pi \kvec_j \cdot \x), \quad j=1, \dots, 2N \]
|
|
|
|
\subsection{Étape 2 : Normalisation}
|
|
\begin{lemma}
|
|
La fonction $f_{\kvec}(\x) = \frac{C}{2\|\kvec\|_1} \cos(2\pi \kvec \cdot \x)$ appartient à $\Fcal_C$.
|
|
\end{lemma}
|
|
\begin{proof}
|
|
La transformée de Fourier de $\cos(2\pi \kvec \cdot \x)$ est $\frac{1}{2} (\delta_{\kvec} + \delta_{-\kvec})$. Ainsi :
|
|
\[ \int \|\w\|_1 |F_{f_{\kvec}}(\w)| \dw = \frac{C}{4\|\kvec\|_1} (\|\kvec\|_1 + \|-\kvec\|_1) = \frac{C}{2} \le C \]
|
|
\end{proof}
|
|
|
|
\subsection{É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 :
|
|
\begin{equation}
|
|
\label{eq:gen_bound}
|
|
w_N(\Fcal_C) \ge \min_{j \in \{1, \dots, 2N\}} \frac{C}{2\sqrt{2}\|\kvec_j\|_1} = \frac{C}{2\sqrt{2}\|\kvec_{2N}\|_1}
|
|
\end{equation}
|
|
|
|
\subsection{Étape 4 : Combinatoire}
|
|
Le nombre de vecteurs $\kvec \in \N^d$ tels que $\|\kvec\|_1 \le m$ est $\binom{m+d}{d}$. On cherche $m$ tel que :
|
|
\begin{equation}
|
|
\label{eq:comb_condition}
|
|
\binom{m+d}{d} \ge 2N
|
|
\end{equation}
|
|
En utilisant l'inégalité $\binom{m+d}{d} \ge (\frac{m}{d})^d$, la condition est satisfaite si :
|
|
\begin{equation}
|
|
\label{eq:m_choice}
|
|
m \ge d (2N)^{1/d}
|
|
\end{equation}
|
|
|
|
\subsection{Étape 5 : Conclusion}
|
|
En injectant \eqref{eq:m_choice} dans \eqref{eq:gen_bound}, on obtient :
|
|
\begin{equation}
|
|
w_N(\Fcal_C) \ge \frac{C}{2\sqrt{2} \cdot d (2N)^{1/d}} \ge \kappa \frac{C}{d} \frac{1}{N^{1/d}}
|
|
\end{equation}
|
|
Ceci démontre que pour les méthodes linéaires, l'erreur décroît de plus en plus lentement à mesure que $d$ augmente.
|
|
\end{document} |