Complexité de Rademacher
La complexité de Rademacher est un concept d'informatique théorique ; il se situe plus précisément à l'intersection de théorie de apprentissage automatique et de la théorie de la complexité. La complexité de Rademacher mesure la richesse d'une classe de fonctions à valeur réelle, selon une distribution de probabilité. Elle porte le nom de Hans Rademacher.
Définition
Complexité empirique
Étant donné des observations , et une classe de fonctions à valeurs réelles définies sur un espace , la complexité empirique de Rademacher de est définie comme :
où sont des variables aléatoires indépendantes, tirées selon la loi de Rademacher i.e. pour .
Complexité de Rademacher
Soit , la distribution de probabilité sur . La complexité de Rademacher de la classe de fonction selon pour des données de taille est :
où les espérances, ci-dessus, sont calculées selon des observations indépendantes et identiquement distribuées (i.i.d.) générées selon .
Propriétés
On peut montrer qu'il existe une constante , telle que n'importe quelle classe de fonctions indicatrices sur avec la dimension de Vapnik-Chervonenkis a la complexité de Rademacher majorée par .
Mesure similaire : la complexité gaussienne
La complexité gaussienne est une mesure de complexité similaire, avec des interprétations physiques similaires. Elle peut être obtenue à partir de la complexité précédente en utilisant les variables aléatoires au lieu de , où sont des variables aléatoires gaussiennes centrées réduites et i.i.d, i.e. .
Bibliographie
- Peter L. Bartlett, Shahar Mendelson (2002) Rademacher and Gaussian Complexities: Risk Bounds and Structural Results. Journal of Machine Learning Research 3 463-482
- Giorgio Gnecco, Marcello Sanguineti (2008) Approximation Error Bounds via Rademacher's Complexity. Applied Mathematical Sciences, Vol. 2, 2008, no. 4, 153 - 176
- Portail de l'informatique théorique