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 ${\mathcal {H}}$ de valores reais das funções definidas em um espaço de domínio $Z$, a complexidade empírica de Rademacher  de ${\mathcal {H}}$ é definida como:

${\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]$

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. $\Pr(\sigma _{i}=+1)=\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 ${\mathcal {H}}$ com respeito a $P$ para o tamanho da amostra $m$ é:

${\mathcal {R}}_{m}({\mathcal {H}})=\mathbb {E} \left[{\widehat {\mathcal {R}}}_{S}({\mathcal {H}})\right]$

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 {\mathcal {N}}\left(0,1\right)$.

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