Aprendizagem provavelmente correta - Probably approximately correct learning

Em teoria da aprendizagem computacional , provavelmente aproximadamente correta ( PAC ) a aprendizagem é um quadro de análise matemática de aprendizagem de máquina . Foi proposto em 1984 por Leslie Valiant .

Nessa estrutura, o aluno recebe amostras e deve selecionar uma função de generalização (chamada de hipótese ) de uma determinada classe de funções possíveis. O objetivo é que, com alta probabilidade (a parte "provável"), a função selecionada terá baixo erro de generalização (a parte "aproximadamente correta"). O aluno deve ser capaz de aprender o conceito dada qualquer razão de aproximação arbitrária, probabilidade de sucesso ou distribuição das amostras .

O modelo foi posteriormente estendido para tratar o ruído (amostras classificadas incorretamente).

Uma inovação importante da estrutura do PAC é a introdução dos conceitos da teoria da complexidade computacional ao aprendizado de máquina. Em particular, espera-se que o aluno encontre funções eficientes (requisitos de tempo e espaço limitados a um polinômio do tamanho do exemplo), e o próprio aluno deve implementar um procedimento eficiente (exigindo uma contagem de exemplo limitada a um polinômio do tamanho do conceito, modificado pelos limites de aproximação e probabilidade ).

Definições e terminologia

Para dar a definição de algo que pode ser aprendido com o PAC, primeiro temos que introduzir alguma terminologia.

Para as seguintes definições, serão usados ​​dois exemplos. O primeiro é o problema de reconhecimento de caracteres dado um array de bits que codifica uma imagem de valor binário. O outro exemplo é o problema de encontrar um intervalo que classifique corretamente os pontos dentro do intervalo como positivos e os pontos fora do intervalo como negativos.

Let Ser um conjunto chamado de espaço de instância ou a codificação de todas as amostras. No problema de reconhecimento de caracteres, o espaço da instância é . No problema de intervalo, o espaço da instância,, é o conjunto de todos os intervalos limitados em , onde denota o conjunto de todos os números reais .

Um conceito é um subconjunto . Um conceito é o conjunto de todos os padrões de bits que codificam uma imagem da letra "P". Um conceito de exemplo do segundo exemplo é o conjunto de intervalos abertos , cada um dos quais contém apenas os pontos positivos. Uma classe de conceito é uma coleção de conceitos acabados . Este poderia ser o conjunto de todos os subconjuntos da matriz de bits que são esqueletizados em 4 conectores (a largura da fonte é 1).

Seja um procedimento que desenhe um exemplo, usando uma distribuição de probabilidade e dê o rótulo correto , que é 1 se e 0 caso contrário.

Agora, dado , suponha que haja um algoritmo e um polinômio em (e outros parâmetros relevantes da classe ) de tal forma que, dada uma amostra de tamanho desenhada de acordo com , então, com probabilidade de pelo menos , gera uma hipótese que tem um erro médio menor ou igual a on com a mesma distribuição . Além disso, se a declaração acima para o algoritmo é verdadeiro para cada conceito e para cada distribuição mais , e para todos , então é (eficiente) PAC aprendida (ou learnable PAC de distribuição gratuita ). Também podemos dizer que é um algoritmo de aprendizagem do PAC para .

Equivalência

Sob algumas condições de regularidade, essas condições são equivalentes:

  1. A classe de conceito C pode ser aprendida pelo PAC.
  2. A dimensão VC de C é finita.
  3. C é uma classe Glivenko – Cantelli uniforme .
  4. C é compressível no sentido de Littlestone e Warmuth

Veja também

Referências

  1. ^ L. Valiant. A teoria da aprendizagem. Communications of the ACM, 27, 1984.
  2. ^ Kearns e Vazirani, pág. 1-12,
  3. ^ Balas Kausik Natarajan, Machine Learning, A Theoretical Approach, Morgan Kaufmann Publishers, 1991
  4. ^ Blumer, Anselm; Ehrenfeucht, Andrzej; David, Haussler; Manfred, Warmuth (outubro de 1989). "Aprendizagem e a dimensão Vapnik-Chervonenkis". Journal of the Association for Computing Machinery . 36 (4): 929–965. doi : 10.1145 / 76359.76371 . S2CID  1138467 .

https://users.soe.ucsc.edu/~manfred/pubs/lrnk-olivier.pdf

Moran, Shay; Yehudayoff, Amir (2015). "Exemplos de esquemas de compressão para classes VC". arXiv : 1503.06960 [ cs.LG ].

Leitura adicional