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 , e uma classe de valores reais das funções definidas em um espaço de domínio , a complexidade empírica de Rademacher  de é definida como:

onde são variáveis aleatórias independentes extraídas a partir da distribuição de Rademacher i.e. para .

Seja uma distribuição de probabilidade sobre . A complexidade de Rademacher da classe de funções  com respeito a  para o tamanho da amostra é:

onde a expectância acima é tomada de mais de uma amostra idêntica e independentemente distribuída (i.i.d.) gerada de acordo com .

Pode-se mostrar, por exemplo, que existe uma constante , tal que qualquer classe de funções -indicadoras com a dimensão de Vapnik-Chervonenkis  tem a complexidade de Radamacher superiormente delimitada por .

Complexidade GaussianaEditar

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   em vez de  , onde   são variáveis aleatórias Gaussianas i.i.d. com média zero e variância 1, i.e.  .

ReferênciasEditar

  • 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