Angluin e Laird ('88) formalizaram o aprendizado com dados corrompidos aleatoriamente no modelo "PAC com ruído de classificação aleatória" (ou ruído barulhento). Esse modelo é semelhante ao aprendizado do PAC , exceto que os rótulos dos exemplos dados ao aluno estão corrompidos (invertidos), independentemente aleatoriamente, com probabilidade .
Para ajudar a caracterizar o que é aprendível no modelo PAC barulhento, Kearns ('93) introduziu o modelo Statistical Query (SQ) para aprendizado. Nesse modelo, um aluno pode consultar um oráculo estatístico em busca de propriedades da distribuição de destino e mostrou que qualquer classe que é aprendida em SQ é aprendida em um PAC barulhento. Kearns também provou que paridades em variáveis não podem ser aprendidas em tempo mais rápido que para alguma constante .
Então Blum et al. ('00) separou o PAC ruidoso do SQ, mostrando que as paridades no primeiro são aprendidas em tempo polinomial no modelo PAC ruidoso, mas não no modelo SQ.
Minha pergunta é esta:
Paridades (nas primeiras variáveis ) são aprendidas no modelo PAC barulhento, mas não no modelo SQ. Existem outras classes específicas, suficientemente diferentes da paridade, conhecidas por serem aprendidas no PAC barulhento, mas não no SQ?
fonte
fonte