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 $S=(z_1,z_2,\dots ,z_m)\in Z^m$, et une classe $\mathscr{H}$ de fonctions à valeurs réelles définies sur un espace $Z$, la complexité empirique de Rademacher de $\mathscr{H}$ est définie comme :

${\widehat{ℛ}}_S(\mathscr{H})=\frac{2}{m}𝔼\left[\underset{h\in \mathscr{H}}{\sup }|\sum _{i=1}^m{\sigma }_{i}h(z_i)|\right|S]$

où ${\sigma }_1,{\sigma }_2,\dots ,{\sigma }_m$ sont des variables aléatoires indépendantes, tirées selon la loi de Rademacher i.e. $\mathbb{P}({\sigma }_i=+1)=\mathbb{P}({\sigma }_i=-1)=1/2$ pour $i=1,2,\dots ,m$.

Complexité de Rademacher

Soit $P$, la distribution de probabilité sur $Z$. La complexité de Rademacher de la classe de fonction $\mathscr{H}$ selon $P$ pour des données de taille $m$ est :

${ℛ}_m(\mathscr{H})=𝔼[{\widehat{ℛ}}_S(\mathscr{H})]$

où les espérances, ci-dessus, sont calculées selon des observations indépendantes et identiquement distribuées (i.i.d.) $S=(z_1,z_2,\dots ,z_m)$ générées selon $P$.

Propriétés

On peut montrer qu'il existe une constante $C$, telle que n'importe quelle classe de fonctions indicatrices sur $\{0,1\}$ avec la dimension de Vapnik-Chervonenkis $d$ a la complexité de Rademacher majorée par $C\sqrt{\frac{d}{m}}$.

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 $g_i$ au lieu de ${\sigma }_i$, où $g_i$ sont des variables aléatoires gaussiennes centrées réduites et i.i.d, i.e. $g_i\sim 𝒩(0,1)$.

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