Boules unité en dimension élevée

L'objectif est de découvrir la malédiction de la dimension pour la régression.

La régression classiquement s'intéresse à la minimisation d'une norme L2 pour l'approximation d'un ensemble de points par une fonction. Nous allons donc essayer de voir comment se comportent les distances en fonction de l'augmentation de la dimension.

Cet article explique que pour la norme p, tirer aléatoirement uniformément un point dans la boule de rayon 1 en dimension d peut se faire par :
  • Générer Formula : $ x_1,\ldots, x_d$ selon une densité proportionnelle à Formula : $e^{-|x|^p}$
  • Générer y selon une loi exponentielle de moyenne 1
  • alors le vecteur de dimension d de ième composante :
    Formula : $$\frac{x_i}{\left(y+\sum_{i=1}^d |x_i|^p\right)^{\frac1p}} $$
    est tiré uniformément dans la boule Lp de dimension d.

Dans le cas de la dimension d et avec la norme euclidienne (L2, celle utilisée pour les moindres carrés) cela signifie que l'on peut générer un point uniformément au hasard dans la boule unité par

draw_in_ball <- function(d) {
	x <- rnorm( d, 0, 1/sqrt(2) )
	y <- rexp(1)
	return (x / sqrt(y+sum(x^2))) 
	}

Notons que pour d=100 la norme du vecteur ainsi généré est très souvent proche de 1. Cela signifie que la majorité du volume de la boule se situe à proximité de la sphère unité. Voici l'histogramme des normes pour 1000 tirages :

R plot

L'on peut aussi s'intéresser à la distibution des distances pour deux points choisis aléatoirement dans la boule unité.

Pour d=1

R plot

Pour d=2

R plot

Pour d=100

R plot

L'on se doute déjà qu'utiliser la distance L2 comme critère pour faire une régression en dimension élevée risque de se révéler problématique. A poursuivre…

Design selector