En la teoria de l'aprenentatge computacional (aprenentatge automàtic i teoria de la computació), la complexitat de Rademacher, anomenada així per Hans Rademacher, mesura la riquesa d'una classe de conjunts respecte a una distribució de probabilitat. El concepte també es pot estendre a funcions amb valors reals.
La complexitat de Rademacher és una mesura de la riquesa d'una classe de funcions amb valors reals. En aquest sentit, és similar a la dimensió VC. De fet, establirem un límit de desviació uniforme en termes de la complexitat de Rademacher i després utilitzarem aquest resultat per demostrar la desigualtat VC. A diferència de la dimensió VC, però, la complexitat de Rademacher no es limita a les funcions binàries i també serà útil més endavant en l'anàlisi d'altres algoritmes d'aprenentatge com ara els algoritmes basats en nuclis.
L'objectiu final de l'aprenentatge automàtic supervisat passiu és trobar una funció d'hipòtesi basada en un conjunt d'exemples que tingui un petit error respecte a alguna funció objectiu. Aquest objectiu és independent de la majoria dels aspectes de l'entorn d'aprenentatge, és a dir, el mateix objectiu s'aplica tant als problemes de classificació com als de regressió, tant en els casos realitzables com en els agnòstics, per la qual cosa seria bo tenir una manera general de tractar aquest tipus de problema.
Sovint, els nostres intents de controlar les condicions suficients per a l'aprenentatge (sobretot en el model PAC) ens van portar a demostrar resultats coneguts com a límits de convergència uniforme. Aquests límits establien que els errors empírics dels conceptes d'una classe de conceptes H determinada convergeixen uniformement als seus errors reals. En altres paraules, vam delimitar la diferència entre l'error d'entrenament i l'error de generalització per a totes les funcions de H.
Definicions Complexitat de Rademacher d'un conjunt Donat un conjunt , la complexitat de Rademacher d'A es defineix de la següent manera:
on són variables aleatòries independents extretes de la distribució de Rademacher, és a dir, per , i Alguns autors prenen el valor absolut de la suma abans de prendre el suprem, però si és simètric, això no fa cap diferència.
Complexitat de Rademacher d'una classe de funcions Sigui una mostra de punts i consideri una classe de funció de funcions amb valor real sobre Aleshores, la complexitat empírica de Rademacher de donat es defineix com:
Això també es pot escriure utilitzant la definició anterior:
on denota la composició de funcions, és a dir:
El pitjor dels casos de complexitat empírica de Rademacher és Deixa sigui una distribució de probabilitat sobre La complexitat de Rademacher de la classe de funcions respecte a per a la mida de la mostra és:
on l'expectativa anterior es pren sobre una mostra distribuïda de manera idèntica i independent (iid) generat segons .
Intuïció La complexitat de Rademacher s'aplica normalment a una classe de funcions de models que s'utilitzen per a la classificació, amb l'objectiu de mesurar la seva capacitat per classificar punts extrets d'un espai de probabilitat sota etiquetatges arbitràries. Quan la classe de funcions és prou rica, conté funcions que es poden adaptar adequadament a cada disposició d'etiquetes, simulades mitjançant l'extracció aleatòria de sota l'esperança, de manera que aquesta quantitat de la suma es maximitza.
La complexitat de Rademacher d'un conjunt es pot reescriure com
Each term in the summation is the farthest distance of the set
from the origin, along a unit-length direction . The directions are along the vertices of a hypercube. Thus, we can also write it as Here, the set denotes half of the vertices of a hypercube, selected so that each diagonal has exactly one vertex selected. miniatura|Amplada, tal com s'il·lustra amb un triangle de Reuleaux. En paraules, això afirma que és precisament l'amplada mitjana del conjunt al llarg de totes les direccions diagonals d'un hipercub.
Exemples Els conjunts Singleton tenen una amplada 0 en qualsevol direcció, per tant tenen una complexitat Rademacher 0.
Si , aleshores té una amplada mitjana al llarg de les dues direccions diagonals del quadrat, de manera que té complexitat de Rademacher .
El cub unitari té una amplada constant al llarg de les direccions diagonals, de manera que té complexitat de Rademacher De la mateixa manera, el politop creuat unitari té una amplada constant al llarg de les direccions diagonals, de manera que té complexitat de Rademacher .
Ús de la complexitat de Rademacher La complexitat de Rademacher es pot utilitzar per derivar límits superiors dependents de les dades sobre la capacitat d'aprenentatge de les classes de funcions. Intuïtivament, una classe de funcions amb una complexitat de Rademacher més petita és més fàcil d'aprendre.
Delimitant la complexitat de Rademacher Com que una complexitat de Rademacher més petita és millor, és útil tenir límits superiors a la complexitat de Rademacher de diversos conjunts de funcions. Les regles següents es poden utilitzar per posar límits superiors a la complexitat de Rademacher d'un conjunt. .
Si tots els vectors de es tradueixen per un vector constant , aleshores Rad( A) no canvia. Si tots els vectors de es multipliquen per un escalar , aleshores Rad( A) es multiplica per . . (Lema de Kakade i Tewari) Si tots els vectors de són operats per una funció de Lipschitz, aleshores Rad( A) es multiplica (com a màxim) per la constant de Lipschitz de la funció. En particular, si tots els vectors de s'operan mitjançant una aplicació de contracció, aleshores Rad(A) disminueix estrictament. La complexitat de Rademacher de l'embolcall convex de és igual a Rad(A). (Lema de Massart) La complexitat de Rademacher d'un conjunt finit creix logarítmicament amb la mida del conjunt. Formalment, sigui ser un conjunt de vectors en , i deixeu sigui la mitjana dels vectors de . Aleshores:
En particular, si és un conjunt de vectors binaris, la norma és com a màxim , així doncs:
Complexitat gaussiana La complexitat gaussiana és una complexitat similar amb significats físics similars, i es pot obtenir a partir de la complexitat de Rademacher utilitzant les variables aleatòries en lloc de , on són variables aleatòries iid gaussianes amb mitjana zero i variància 1, és a dir, Se sap que les complexitats gaussiana i de Rademacher són equivalents fins a factors logarítmics.
Equivalència entre la complexitat de Rademacher i la de Gauss Donat un conjunt aleshores es compleix que:
On és la complexitat gaussiana d'A. Com a exemple, considereu les complexitats rademacher i gaussiana de la bola L1. La complexitat rademacher ve donada per exactament 1, mentre que la complexitat gaussiana és de l'ordre de (que es pot demostrar aplicant les propietats conegudes del suprem d'un conjunt de variables aleatòries subgaussianes).
Referències
Categoria:Aprenentatge automàtic