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

${\displaystyle {\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ù ${\displaystyle \sigma _{1},\sigma _{2},\dots ,\sigma _{m}}$ sont des variables aléatoires indépendantes, tirées selon la loi de Rademacher i.e. ${\displaystyle \mathbb {P} (\sigma _{i}=+1)=\mathbb {P} (\sigma _{i}=-1)=1/2}$ pour ${\displaystyle i=1,2,\dots ,m}$.

Complexité de Rademacher

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

${\displaystyle {\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.) ${\displaystyle S=(z_{1},z_{2},\dots ,z_{m})}$ générées selon ${\displaystyle P}$.

Propriétés

On peut montrer qu'il existe une constante ${\displaystyle C}$, telle que n'importe quelle classe de fonctions indicatrices sur ${\displaystyle \{0,1\}}$ avec la dimension de Vapnik-Chervonenkis ${\displaystyle d}$ a la complexité de Rademacher majorée par ${\displaystyle 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 ${\displaystyle g_{i}}$ au lieu de ${\displaystyle \sigma _{i}}$, où ${\displaystyle g_{i}}$ sont des variables aléatoires gaussiennes centrées réduites et i.i.d, i.e. ${\displaystyle 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

• Portail de l'informatique théorique