Algoritmos de modelo de consulta estatística?

13

Fiz essa pergunta em perguntas e respostas cruzadas validadas, mas parece que ela está relacionada ao CS muito mais que o Statistics.

Você pode me dar exemplos de algoritmos de aprendizado de máquina que aprendem com as propriedades estatísticas do conjunto de dados e não com as próprias observações individuais, ou seja, empregam o modelo de consulta estatística ?

Deyaa
fonte
1
qual é o modelo de consulta estatística?
perfil completo de Suresh Venkat
de Kearns paper portal.acm.org/citation.cfm?doid=293347.293351 : "neste modelo, um algoritmo de aprendizado é proibido para examinar exemplos individuais da função de destino desconhecida, mas recebe acesso a um oráculo que fornece estimativas de probabilidades sobre a amostra espaço de exemplos aleatórios ". desculpe se não é óbvio, eu atualizei a minha pergunta com o link para o papel
Deyaa

Respostas:

14

Quase todos os algoritmos que funcionam no modelo PAC (com exceção dos algoritmos de aprendizado de paridade) podem funcionar no modelo SQ. Veja, por exemplo, este artigo de Blum et al. em que vários algoritmos populares são traduzidos em seus equivalentes SQ ( Privacidade prática: a estrutura SuLQ ). O artigo está em princípio relacionado à "privacidade", mas você pode ignorar isso - na verdade, é apenas implementar algoritmos com consultas SQ.

O aprendizado agnóstico, por outro lado, é muito mais difícil no modelo SQ: além de questões computacionais (embora sejam importantes), a complexidade da amostra necessária para o aprendizado agnóstico é aproximadamente a mesma que a exigida para o aprendizado exato, se você realmente tiver acesso a os pontos de dados. Por outro lado, o aprendizado agnóstico se torna muito mais difícil no modelo SQ - você geralmente precisará fazer muitas consultas superpolinomialmente, mesmo para classes tão simples quanto disjunções monótonas. Veja este artigo de Feldman ( Uma caracterização completa do aprendizado de consultas estatísticas com aplicações para a capacidade de evolução ) ou este artigo recente de Gupta et al. ( Lançamento privado de conjunções e barreira de consulta estatística )

Aaron Roth
fonte
realmente agradável resposta Aaron :) muito obrigado :)
Deyaa
7

O modelo SQ foi criado para analisar o aprendizado tolerante a ruído - ou seja, um algoritmo que funciona fazendo consultas estatísticas funcionará sob o ruído de classificação. Como Aaron disse, a maioria dos algoritmos PAC que possuímos equivalentes no modelo SQ. A única exceção é a eliminação gaussiana, usada em paridades de aprendizado (pode-se até usar uma aplicação inteligente dela)aprender paridades de log (n) loglog (n) no modelo de ruído de classificação). Também sabemos que paridades não podem ser aprendidas com consultas estatísticas, e as classes mais interessantes, como árvores de decisão, podem simular funções de paridade. Portanto, em nossa busca por obter algoritmos de aprendizado do PAC para muitas classes interessantes (como árvores de decisão, DNF etc.), sabemos que precisamos fundamentalmente de novos algoritmos de aprendizado que não funcionem no modelo de consulta estatística.

Lev Reyzin
fonte
Interessante. Você tem uma referência de que paridades não podem ser aprendidas no modelo SQ?
M. Alaggan
1
foi comprovado por Kearns em seu artigo original, definindo o modelo: portal.acm.org/citation.cfm?doid=293347.293351 e depois mostrado novamente por Blum et al, onde definiram a dimensão SQ de uma classe portal.acm.org/citation .cfm? id = 195058.195147 . Basicamente, o argumento é o seguinte: paridades são "independentes por pares" na distribuição uniforme, então você precisa adivinhar a paridade correta para aprender qualquer coisa, e há muitas paridades possíveis ...
Lev Reyzin
5

Eu gostaria de esclarecer um pouco a resposta de Aaron. Quase todo algoritmo agnóstico (mais uma vez, exceto por qualquer coisa que use a eliminação gaussiana) pode ser feito para funcionar no modelo SQ. Naturalmente, o aprendizado agnóstico é mais difícil que o aprendizado não-agnóstico, mas essa é uma questão independente.

user5591
fonte
/ϵ2