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 :

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 .

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

Cet article utilise du matériel de l'article de Wikipédia Complexité de Rademacher, qui est publié sous le Creative Commons Attribution-Share-Alike License 3.0.