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 , 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 .

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 au lieu de , où sont des variables aléatoires gaussiennes centrées réduites et i.i.d, i.e. .

Bibliographie

  • 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 est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.