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


Este artigo usa material do artigo Wikipedia Complexidade de Rademacher, que é lançado sob o Creative Commons Attribution-Share-Alike License 3.0.