Mal├ędiction de la grande dimension

Ce cours montre que l’approximation de fonctions localement régulières nécessite d’avoir un nombre d’exemples qui croit de façon exponentielle avec la dimension des données, ce que l’on appelle la malédiction de la grande dimension. Si la réponse y associée à une donnée x est unique alors c’est une fonction y = f(x). La prédiction de y revient donc à approximer la fonction f(x) en choisissant une approximation dans une classe prédéfinie. Le choix de cette classe ainsi que l’amplitude de l’erreur d’approximation dépend de la régularité de f.

L’algorithme du plus proche voisin approxime f(x) par la valeur f(x’)x’ est l’exemple le plus proche de x. L’approximation est donc une fonction constante par morceaux. On établie le lien entre l’erreur d’approximation, la régularité de f, le nombre d’exemples d’entrainement et la dimension d des données. Le cours se concentre sur l’approximation de fonctions Lipchitz. Sous cette hypothèse de régularité locale, pour que l’erreur soit inférieure à c avec n exemples, il faut que l’espace des données puisse être couvert par n boules de rayon c. On démontre que le nombre n de boules croît comme c^{-d} . Cette croissance exponentielle en d est la malédiction de la grande dimension. Dés que d est plus grand que 10, on n’a typiquement jamais assez d’exemples pour atteindre une précision c petite. Pour pouvoir approximer précisément des fonctions f en grande dimension, il faut que celles-ci aient une régularité globale beaucoup plus forte qu’une régularité Lipchitzienne.