Résumé
Ce cours montre que l’approximation de fonctions localement régulières nécessite d’avoir un nombre d’exemples qui croît 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’) où x’ est l’exemple le plus proche de x. L’approximation est donc une fonction constante par morceaux. On établit le lien entre l’erreur d’approximation, la régularité de f, le nombre d’exemples d’entraînement 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.
