Alguma classe de hipótese diferente da paridade no PAC ruidoso, mas não no SQ?

11

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 .η<1/2

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 .n2n/cc

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.(registro(n)registroregistro(n))

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?(registro(n)registroregistro(n))

Lev Reyzin
fonte

Respostas:

6

d/ϵ21/ϵ

Aaron Roth
fonte
Obrigado, Aaron - esse também era meu entendimento do estado das coisas, mas eu não tinha certeza. Se ninguém me der um exemplo em breve, vou marcar o seu como a resposta aceita.
Lev Reyzin
6

1/2-n-ϵ

Vitaly
fonte
Sim, é isso mesmo, quero uma técnica de separação diferente, e não algo que dependa do BKW. Sua pergunta adicional sobre separação pura também é interessante.
Lev Reyzin