PAC adequado para aprender limites de dimensão de VC

11

É 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 ( dCdCCO(dεlog1ε)CC

  1. 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?

  2. 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 / ε )log(1/ε)log(1/ε)

Anônimo
fonte
A qual artigo da Hanneke você está se referindo?
gradstudent
11
@gradstudent arxiv.org/abs/1507.00473
Clement c

Respostas:

9

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).CO((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 simples d=1 , e colocar o espaço X como {1,2,...,1/ε} e C são singletons fz(x):=I[x=z],zX : 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 xUniform(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 zx é 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 geral d>1 , tomamos X como {1,2,...,d/(4ε)} , tome C como classificador IA para os conjuntos AX 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ço C 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.

S. Hanneke
fonte
Interessante ... Existe uma caracterização combinatória das classes para as quais o aprendizado adequado do PAC é ideal para a amostra? Ou pelo menos condições suficientes (fechamento sob interseção, união?)C
Clement C.
2
@ClementC. Não se conhece a caracterização completa de quais classes têm taxas ótimas alcançáveis ​​pelos alunos apropriados em geral. O artigo referenciado "Limites de erro refinados ..." fornece uma caracterização combinatória de quais classes admitem taxas ideais para todos os alunos de ERM (Corolário 14). A quantidade relevante é o "número da estrela": o maior número de pontos, de modo que um possa inverter o rótulo de qualquer ponto único sem alterar os outros (Definição 9). As classes fechadas para interseção têm um aprendiz adequado ideal: o alg de "fechamento" (Teorema 5 no artigo, e também comprovado por Darnstädt, 2015).
31519 S. Hanneke
Obrigado!
Clement C.
6

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/ϵ)

Aryeh
fonte
Obrigado! Ok, então se eu entendi direito, a complexidade da amostra do aprendizado inadequado do PAC é e, para o aprendizado adequado do PAC, é Θ ( d / ϵ log ( 1 / ϵ ) ) , o limite inferior para o último sendo alcançado para o exemplo que você dá. Isso está certo? Θ(d/ϵ)Θ(d/ϵlog(1/ϵ))
Annonymous
Sim, com a pequena reserva de que, para um PAC inadequado, você precisa usar um algoritmo específico (da Hanneke) - não apenas qualquer ERM antigo. Sinta-se à vontade para aceitar a resposta :) #
306 Aryeh
Estou atrasado para a festa, mas o limite inferior do PAC adequado acima mencionado não é um limite inferior da complexidade da amostra para um algoritmo de aprendizado específico (ou classe restrita)? Quero dizer, sem essa restrição, não há informações - teoricamente, não há separação entre o PAC adequado e o impróprio, certo? (E, assim, sem separação, sem hipóteses computacionais, tais como ou semelhante))?NPRP
Clement c
11
A definição usual de capacidade de aprendizado do PAC pede algoritmos de tempo poligonal. Meus pontos são: (i) relaxar que, apropriados e impróprios, tenham a mesma complexidade de amostra; (ii) com esse requisito, não podemos provar uma separação incondicional entre o adequado e o impróprio (pois isso essencialmente provaria algo como NP diferente de RP). (Podemos provar limites inferiores da complexidade amostra de específicos algoritmos de aprendizagem adequados, porém, que, tanto quanto eu entendo é o que a referência de Aryeh faz.)
Clement C.
11
@ClementC. Em um de seus comentários anteriores, que você mencionou após executar um algoritmo de PAC inadequado, um aluno obtém uma hipótese possivelmente imprópria e o aluno pode encontrar a hipótese apropriada mais próxima da classe conceitual (sem mais amostras). Mas como o aluno poderia fazer isso sem conhecer a distribuição sob a qual está recebendo amostras? O mais próximo não está sendo medido de acordo com uma distribuição desconhecida?
Annonymous 14/02
5

Para adicionar à resposta atualmente aceita:

  1. 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].

    O(dεlog1ε)
    NP=RPLH=C
  2. 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/ε)

    Classicamente, ainda é uma questão em aberto se o fator no limite superior de [1] para a aprendizagem adequada do PAC ( ε , δ ) é necessário.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.

Clemente C.
fonte
Supõe-se que o gráfico de 1 inclusão de Haussler et al. é um aluno ideal para o PAC?
Aryeh
@Aryeh não tenho certeza. Pelo que pude encontrar, Warmuth conjeturou isso em 2004. Não sei mais do que isso.
Clement c