Complexidade de Rademacher

Na teoria da aprendizagem computacional (aprendizado de máquina e teoria da computação), Complexidade de Rademacher, em homenagem a Hans Rademacher, mede a riqueza de uma classe com funções de valores reais, com respeito a uma distribuição de probabilidade.

Dada uma amostra de treinamento $S=(z_1,z_2,\dots ,z_m)\in Z^m$, e uma classe $\mathscr{H}$ de valores reais das funções definidas em um espaço de domínio $Z$, a complexidade empírica de Rademacher  de $\mathscr{H}$ é definida como:

${\widehat{ℛ}}_S(\mathscr{H})=\frac{2}{m}𝔼\left[\underset{h\in \mathscr{H}}{\sup }|\sum _{i=1}^m{\sigma }_{i}h(z_i)|\right|S]$

onde ${\sigma }_1,{\sigma }_2,\dots ,{\sigma }_m$ são variáveis aleatórias independentes extraídas a partir da distribuição de Rademacher i.e. $\mathrm{Pr}({\sigma }_i=+1)=\mathrm{Pr}({\sigma }_i=-1)=1/2$ para $i=1,2,\dots ,m$.

Seja $P$ uma distribuição de probabilidade sobre $Z$. A complexidade de Rademacher da classe de funções $\mathscr{H}$ com respeito a $P$ para o tamanho da amostra $m$ é:

${ℛ}_m(\mathscr{H})=𝔼[{\widehat{ℛ}}_S(\mathscr{H})]$

onde a expectância acima é tomada de mais de uma amostra idêntica e independentemente distribuída (i.i.d.) $S=(z_1,z_2,\dots ,z_m)$ gerada de acordo com $P$.

Pode-se mostrar, por exemplo, que existe uma constante $C$, tal que qualquer classe de funções $\{0,1\}$-indicadoras com a dimensão de Vapnik-Chervonenkis $d$ tem a complexidade de Radamacher superiormente delimitada por $C\sqrt{\frac{d}{m}}$.

Complexidade Gaussiana

Complexidade Gaussiana é uma complexidade semelhante com significados físicos parecidos, e pode ser obtido a partir da complexidade anterior utilizando as variáveis aleatórias $g_i$ em vez de ${\sigma }_i$, onde $g_i$ são variáveis aleatórias Gaussianas i.i.d. com média zero e variância 1, i.e. $g_i\sim 𝒩(0,1)$.

Referências

• 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