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 :
![{\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]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9b499e69969ba10d67e61f66b079f4ee22b6fd99)
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 :
![{\displaystyle {\mathcal {R}}_{m}({\mathcal {H}})=\mathbb {E} \left[{\widehat {\mathcal {R}}}_{S}({\mathcal {H}})\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4bd0ac6c6e32431180a90b14d6f624b68b417dae)
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
.
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