Teoria da Aprendizagem Computacional

A teoria da aprendizagem computacional estuda quais conceitos podem ser aprendidos eficientemente a partir de exemplos, tratando a aprendizagem como um problema de complexidade computacional e de amostra.

Definition

A teoria da aprendizagem computacional é o estudo dos recursos, em dados e computação, necessários para aprender conceitos a partir de exemplos; no modelo provavelmente aproximadamente correto, uma classe de conceitos é aprendível se um algoritmo puder, a partir de um número polinomial de amostras e em tempo polinomial, produzir uma hipótese que seja precisa com alta probabilidade.

Scope

Este tópico abrange modelos formais de aprendibilidade: o modelo provavelmente aproximadamente correto (PAC) que questiona quando um conceito pode ser aprendido com alta precisão e alta probabilidade a partir de um número polinomial de exemplos e computação, os modelos de limite de erro e de aprendizagem online, a aprendibilidade fraca versus forte e o boosting, e as conexões com a complexidade computacional. Aborda tanto a viabilidade estatística quanto a algorítmica da aprendizagem.

Core questions

• Quais classes de conceitos podem ser aprendidas eficientemente a partir de exemplos?
• Quantos dados e computação a aprendizagem de um conceito requer?
• Qual é a relação entre aprendibilidade fraca e forte?
• Como a aprendibilidade se conecta à complexidade computacional?

Key theories

Aprendizagem provavelmente aproximadamente correta

O modelo de Valiant define uma classe de conceitos como aprendível quando um algoritmo eficiente pode produzir, com alta probabilidade, uma hipótese de baixo erro a partir de um número polinomial de exemplos, tornando a aprendibilidade uma questão computacional precisa.

Aprendibilidade fraca e boosting

Um resultado central mostra que qualquer classe aprendível ligeiramente melhor do que o acaso também é fortemente aprendível, o que levou diretamente aos algoritmos de boosting que amplificam aprendizes fracos em aprendizes precisos.

Limites estatísticos e computacionais

A aprendibilidade é limitada tanto pela complexidade da amostra, ligada a medidas de capacidade, quanto pela dificuldade computacional, de modo que algumas classes são estatisticamente aprendíveis, mas computacionalmente intratáveis.

Clinical relevance

A teoria da aprendizagem computacional fornece a base formal para o que os algoritmos de aprendizagem podem e não podem alcançar e inspirou diretamente métodos práticos, notadamente o boosting, que surgiu da questão de saber se aprendizes fracos poderiam ser combinados em aprendizes fortes; ela enquadra a aprendizagem como uma disciplina computacional rigorosa.

History

Valiant introduziu o modelo provavelmente aproximadamente correto em 1984, dando à aprendizagem uma definição computacional precisa e fundando o campo. Trabalhos subsequentes estabeleceram caracterizações da complexidade da amostra, a equivalência da aprendibilidade fraca e forte que motivou o boosting, e resultados de dificuldade que mostram os limites computacionais da aprendizagem.

Key figures

• Leslie Valiant
• Michael Kearns
• Robert Schapire

Seminal works

• valiant1984
• kearns1994
• vapnik1995

Frequently asked questions

O que significa provavelmente aproximadamente correto?

Significa que, com alta probabilidade sobre a amostra aleatória, o aprendiz produz uma hipótese que é aproximadamente correta, ou seja, tem um pequeno erro em dados futuros. A aprendibilidade requer alcançar isso a partir de um número de exemplos e uma quantidade de computação que crescem apenas polinomialmente.

Como a teoria da aprendizagem levou ao boosting?

Pesquisadores questionaram se um aprendiz apenas ligeiramente melhor do que a adivinhação aleatória poderia ser transformado em um altamente preciso. A prova de que a aprendibilidade fraca e forte são equivalentes foi construtiva, e essa construção se tornou os algoritmos de boosting amplamente utilizados na prática.