É sabido que, para uma classe conceitual com a dimensão VC , basta obter exemplos rotulados para o PAC learn . Não está claro para mim se o algoritmo de aprendizado do PAC (que usa essas muitas amostras) é adequado ou impróprio? Nos livros de Kearns e Vazirani, bem como Anthony e Biggs, parece que o algoritmo de aprendizado do PAC é inadequado (ou seja, a hipótese de saída não está em ) d O ( dCC
Alguém poderia esclarecer se um limite superior semelhante também é válido para a configuração adequada de aprendizado do PAC? Em caso afirmativo, você poderia me dar uma referência onde isso é explicitamente mencionado e também contém uma prova independente?
Recentemente, Hanneke aprimorou esse limite fator . Alguém poderia esclarecer se é conhecido que o é removível para a configuração de aprendizado do PAC adequado? Ou ainda é uma questão em aberto?log ( 1 / ε )
Respostas:
Agradeço a Aryeh por trazer esta questão à minha atenção.
Como já mencionado, a resposta para (1) é Sim , e o método simples de Minimização Empírica de Riscos em atinge a complexidade da amostra ( ver Vapnik e Chervonenkis, 1974; Blumer, Ehrenfeucht, Haussler e Warmuth, 1989).C O((d/ε)log(1/ε))
Quanto a (2), sabe-se de fato que existem espaços que nenhum algoritmo de aprendizado adequado alcança melhor que a complexidade da amostra e portanto, o aprendizado adequado não pode alcançar a complexidade amostra de . Que eu saiba, esse fato nunca foi realmente publicado, mas está enraizado em um argumento relacionado de Daniely e Shalev-Shwartz (COLT 2014) (originalmente formulado para uma pergunta diferente, mas relacionada, na aprendizagem em várias classes).C Ω((d/ε)log(1/ε)) O(d/ε)
Consideremos o caso simplesd=1 , e colocar o espaço X como {1,2,...,1/ε} e C são singletons fz(x):=I[x=z],z∈X : ou seja, cada classificador em C classifica exatamente um ponto de X como 1 e os outros como 0 . Para o limite inferior, ter a função alvo como um Singleton aleatória fx∗ , onde x∗∼Uniform(X) , e P , a distribuição marginal de X , é uniforme sobre X∖{x∗} . Agora, o aluno nunca vê nenhum exemplo rotulado como 1 , mas deve escolher um ponto z para adivinhar que é rotulado como 1 (importante, a função `` todo zero '' não está em C , De modo que qualquer aluno adequada deve adivinhar alguns z ), e desde que tenha visto todos os pontos em X∖{x∗} que tem pelo menos 1/2 probabilidade de adivinhar errada (ou seja, a probabilidade posterior da sua fz tendo z≠x∗ é de pelo menos 1/2 ). O argumento do coletor de cupom implica que exigiria Ω((1/ε)log(1/ε)) amostras para ver todos os pontos em X∖{x∗} . Portanto, isso prova um limite inferior de Ω((1/ε)log(1/ε)) para todos os alunos apropriados.
Para gerald>1 , tomamos X como {1,2,...,d/(4ε)} , tome C como classificador IA para os conjuntos A⊂X de tamanho exatamente d , escolha a função de destino aleatoriamente a partir de C e leve P novamente como uniforme apenas nos pontos que a função de destino classifica 0 ( para que o aluno nunca veja um ponto rotulado como 1 ) Então uma generalização do argumento do coletor de cupons implica que precisamos de amostras de Ω((d/ε)log(1/ε)) para ver pelo menos |X|−2d pontos distintos de X , e sem ver este muitos pontos distintos qualquer aluno adequada tem pelo menos 1/3 chance de conseguir maior do que d/4 de seu palpite A dos d pontos de errado em sua hipótese escolhida hA , significando que sua taxa de erro é maior que ε . Portanto, neste caso, não há aprendiz adequado com complexidade de amostra menor que Ω((d/ε)log(1/ε)) , o que significa que nenhum aprendiz adequado atinge a complexidade ideal da amostra O(d/ε) .
Observe que o resultado é bastante específico para o espaçoC construído. Existem espaços C que os alunos apropriados podem atingir a complexidade ideal da amostra O(d/ε) e, de fato, até a expressão completa exata O((d/ε)+(1/ε)log(1/δ)) de ( Hanneke, 2016a). Alguns limites superior e inferior para aprendizes gerais de ERM foram desenvolvidos em (Hanneke, 2016b), quantificados em termos de propriedades do espaço C , além de discutir alguns casos mais especializados em que alunos apropriados específicos às vezes podem alcançar a complexidade ideal da amostra.
Referências:
Vapnik e Chervonenkis (1974). Teoria do reconhecimento de padrões. Nauka, Moscou, 1974.
Blumer, Ehrenfeucht, Haussler e Warmuth (1989). Aprendizagem e a dimensão Vapnik-Chervonenkis. Jornal da Association for Computing Machinery, 36 (4): 929–965.
Daniely e Shalev-Shwartz (2014). Alunos ideais para problemas multiclasses. Em Anais da 27ª Conferência sobre Teoria da Aprendizagem.
Hanneke (2016a). A complexidade ideal da amostra do aprendizado do PAC. Journal of Machine Learning Research, v. 17 (38), p. 1-15.
Hanneke (2016b). Limites de erro refinados para vários algoritmos de aprendizado. Journal of Machine Learning Research, v. 17 (135), p. 1-55.
fonte
Suas perguntas (1) e (2) estão relacionadas. Primeiro, vamos falar sobre o aprendizado adequado do PAC. Sabe-se que existem aprendizes do PAC adequados que atingem zero erro de amostra e ainda exigem exemplos. Para uma prova simples doεdependência, considere a classe conceito de intervalos[a,b]⊆[0,1]sob a distribuição uniforme. Se escolhermos omenorintervalo consistente, obteremos uma complexidade de amostra deO(1/ϵ). Suponha, no entanto, que escolhamos omaiorintervalo consistente e o conceito de destino seja um intervalo de pontos como[0,0]Ω(dϵlog1ϵ) ϵ [a,b]⊆[0,1] O(1/ϵ) [0,0] . Então, um argumento simples de coletor de cupons mostra que, a menos que recebamos aproximadamente exemplos, seremos enganados pelo espaçamento entre os exemplos negativos (o único tipo que veremos) - que possui comportamento característico de1/[tamanho da amostra] sob a distribuição uniforme. Limites inferiores mais gerais desse tipo são dados em1ϵlog1ϵ 1/
P. Auer, R. Ortner. Um novo PAC destinado a classes de conceito fechadas por interseção. Machine Learning 66 (2-3): 151-163 (2007) http://personal.unileoben.ac.at/rortner/Pubs/PAC-intclosed.pdf
O problema do PAC adequado é que, para resultados positivos no caso abstrato, não se pode especificar um algoritmo além do ERM, que diz "encontre um conceito consistente com a amostra rotulada". Quando você possui uma estrutura adicional, como intervalos, pode examinar dois algoritmos diferentes de ERM, como acima: um segmento consistente mínimo vs. máximo. E estes têm diferentes complexidades de amostra!
O poder do PAC inadequado é que você possa criar vários esquemas de votação (o resultado da Hanneke) - e essa estrutura adicional permite provar taxas aprimoradas. (A história é mais simples para o PAC agnóstico, em que o ERM fornece a melhor taxa de pior caso possível, até constantes.)
Editar. Ocorre-me agora que a estratégia de previsão do gráfico de 1 inclusão de D. Haussler, N. Littlestone, Md K. Warmuth. Previsão de funções {0,1} em pontos sorteados aleatoriamente. Inf. Comput. 115 (2): 248-292 (1994) pode ser um candidato natural para o aprendiz universal adequado de PAC.O(d/ϵ)
fonte
Para adicionar à resposta atualmente aceita:
Sim. O limite superior da complexidade da amostra também é válido para o aprendizado adequado do PAC(embora seja importante observar que ele pode não levar a um algoritmo de aprendizado computacionalmente eficiente. O que é normal, pois, a menos queNP=RPseja conhecido que algumas classes são não pode ser aprendido com eficiência no PAC, por exemplo, o Teorema 1.3 do livro de Kearns-Vazirani que você mencionou). Esta é realmente mostrado no livro de Kearns-Vazirani (Teorema 3.3), uma vez queGnão é um localizador hipótese consistente com a hipótese de classeH=C. Veja também [1].
Desconhecido. O algoritmo de Hanneke [2] é um algoritmo de aprendizado inadequado. Se esse fator extra de na complexidade da amostra pode ser removido para o aprendizado adequado do PAC (informações teoricamente, isto é, deixando de lado qualquer requisito de eficiência computacional) ainda é uma questão em aberto. Cf. as perguntas abertas no final de [3]:log(1/ε)
(Nota de rodapé 1 no mesmo artigo também é relevante)
[1] A. Blumer, A. Ehrenfeucht, D. Haussler e MK Warmuth. Aprendizagem e a dimensão Vapnik-Chervonenkis. Journal of the ACM, 36 (4): 929–965, 1989.
[2] S. Hanneke. A complexidade ideal da amostra do aprendizado do PAC. J. Mach. Aprender. Res. 17, 1, 1319-1333, 2016.
[3] S. Arunachalam e R. de Wolf. Complexidade ideal de amostras quânticas de algoritmos de aprendizado. Em Anais da 32ª Conferência de Complexidade Computacional (CCC), 2017.
fonte