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 ${\displaystyle S=(z_{1},z_{2},\dots ,z_{m})\in Z^{m}}$, e uma classe ${\displaystyle {\mathcal {H}}}$ de valores reais das funções definidas em um espaço de domínio ${\displaystyle Z}$, a complexidade empírica de Rademacher  de ${\displaystyle {\mathcal {H}}}$ é definida como:

${\displaystyle {\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 ${\displaystyle \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. ${\displaystyle \Pr(\sigma _{i}=+1)=\Pr(\sigma _{i}=-1)=1/2}$ para ${\displaystyle i=1,2,\dots ,m}$.

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

${\displaystyle {\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.) ${\displaystyle S=(z_{1},z_{2},\dots ,z_{m})}$ gerada de acordo com ${\displaystyle P}$.

Pode-se mostrar, por exemplo, que existe uma constante ${\displaystyle C}$, tal que qualquer classe de funções ${\displaystyle \{0,1\}}$-indicadoras com a dimensão de Vapnik-Chervonenkis ${\displaystyle d}$ tem a complexidade de Radamacher superiormente delimitada por ${\displaystyle 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 ${\displaystyle g_{i}}$ em vez de ${\displaystyle \sigma _{i}}$, onde ${\displaystyle g_{i}}$ são variáveis aleatórias Gaussianas i.i.d. com média zero e variância 1, i.e. ${\displaystyle 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