Rademacher complexity

rdf:langString Complexidade de Rademacher

rdf:langString 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 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 tem a complexidade de Radamacher superiormente delimitada por .