Aprendizagem provavelmente correta - Probably approximately correct learning
Parte de uma série sobre |
Aprendizado de máquina e mineração de dados |
---|
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:
- A classe de conceito C pode ser aprendida pelo PAC.
- A dimensão VC de C é finita.
- C é uma classe Glivenko – Cantelli uniforme .
- C é compressível no sentido de Littlestone e Warmuth
Veja também
- Aprendizagem Occam
- Aprendizado de máquina
- Mineração de dados
- Tolerância a erros (aprendizagem PAC)
- Complexidade da amostra
Referências
- ^ L. Valiant. A teoria da aprendizagem. Communications of the ACM, 27, 1984.
- ^ Kearns e Vazirani, pág. 1-12,
- ^ Balas Kausik Natarajan, Machine Learning, A Theoretical Approach, Morgan Kaufmann Publishers, 1991
- ^ 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
- M. Kearns, U. Vazirani. Uma introdução à teoria da aprendizagem computacional . MIT Press, 1994. Um livro didático.
- M. Mohri, A. Rostamizadeh e A. Talwalkar. Fundamentos do aprendizado de máquina . MIT Press, 2018. O Capítulo 2 contém um tratamento detalhado da capacidade de aprendizagem do PAC. Legível por meio de acesso aberto do editor.
- D. Haussler. Visão geral da Estrutura de Aprendizagem Provavelmente Aproximadamente Correta (PAC) . Uma introdução ao tópico.
- L. Valiant. Provavelmente aproximadamente correto. Basic Books, 2013. Em que Valiant argumenta que a aprendizagem PAC descreve como os organismos evoluem e aprendem.