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 ${\mathcal {H}}$ de fonctions à valeurs réelles définies sur un espace $Z$, la complexité empirique de Rademacher de ${\mathcal {H}}$ est définie comme :

${\widehat {\mathcal {R}}}_{S}({\mathcal {H}})={\frac {2}{m}}\mathbb {E} \left[\sup _{h\in {\mathcal {H}}}\left|\sum _{i=1}^{m}\sigma _{i}h(z_{i})\right|\ {\bigg |}\ S\right]$

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 ${\mathcal {H}}$ selon $P$ pour des données de taille $m$ est :

${\mathcal {R}}_{m}({\mathcal {H}})=\mathbb {E} \left[{\widehat {\mathcal {R}}}_{S}({\mathcal {H}})\right]$

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 {\mathcal {N}}\left(0,1\right)$.

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