Pac aprendendo vs. aprendendo sobre distribuição uniforme

Question

a classe de função $ \ mathcal {f} $ é pac-learnable se existe um algoritmo $ a $ tal que para qualquer distribuição $ D $ , qualquer função desconhecida $ F $ e qualquer $ \ epsilon, \ delta $ mantém que existe $ m $ que em uma entrada de $ m $ amostras Iid $ (x, f (x)) $ onde < span class="recipiente de matemática"> $ x \ sim d $ , $ a $ retorna, com probabilidade maior que $ 1- \ Delta $ , uma função que é $ \ epsilon $ -close para $ f $ (com relação à $ D $ ). A turma $ \ Mathcal {f} $ é eficientemente pacificamente aprendido se é o PAC learno, e $ a $ corre no tempo $ {poly} (1 / \ epsilon, 1 / \ delta, n) $ (onde $ | x |= n $ ) e a descrição de $ F $ .

Existe um caso em que uma classe $ \ mathcal {f} $ não é eficientemente pacotável, mas é eficientemente aprendível na distribuição uniforme?

Answer 1

.

Existe um caso em que uma classe $ \ mathcal {f} $ não é eficientemente pacotável, mas é eficientemente aprendível na distribuição uniforme?

Isto foi perguntado em Tcs.se . Parece que a resposta curta é sim - Aaron Roth dá o exemplo de largura- $ k $ conjunções para $ k \ gg \ log n $ . E nos comentários, o avrim Blum é citado como dando a resposta de $ 2 $ -term dnf.

Eu não entendo totalmente os exemplos lá - deve demorar um pouco mais de trabalho para realmente derivar o resultado (vou atualizar esta resposta se eu encontrar uma prova autônoma). Mas o problema geral aqui com a distribuição uniforme é que, se a função de destino $ F $ é "esparso", o que significa que rótulos no máximo uma matemática $ \ delta $ fração da distribuição de entrada com $ 1 $ , então é fácil aprender simplesmente adivinhando $ 0 $ .

---

.

Além da aprendizagem pacífica (polinomial) apenas eficiente, existem outros exemplos em que a distribuição uniforme parece ajudar. Por exemplo, um problema difícil clássico para o APRENDIMENTO PAC é DNF, um problema que é conjecturado para não ser o PAC learno e bastante difícil. Por outro lado, o DNF sobre a distribuição uniforme é quase pacífico: nós temos um algoritmo de tempo polinomial QAUSI para ele. Ver estas notas e Estas notas .

Em resumo, parece haver muito trabalho sobre a aprendizagem sob a distribuição uniforme (busca "APRENDENDO PAC sob distribuição uniforme" para referências adicionais). E parece que esse problema é mais fácil do que estudar o aprendizado do PAC, onde não somos capazes de provar muito. Citando as notas de Ryan O'Donnell acima:

.

General Pac-Learning insiste que um algoritmo funciona simultaneamente para todas as distribuições. De fato, a comunidade de aprendizado de máquina interessada em aplicativos do mundo real encontra a configuração uniforme questionável: "Eles vão te dar um soco no nariz se você tentar contar sobre algoritmos neste framework. "--ryan. Mas, em uma estrutura mais geral, ninguém pode realmente provar nada.