Théorie de l'apprentissage computationnel

La théorie de l'apprentissage computationnel étudie quels concepts peuvent être appris efficacement à partir d'exemples, considérant l'apprentissage comme un problème de calcul et de complexité d'échantillonnage.

Definition

La théorie de l'apprentissage computationnel est l'étude des ressources, en données et en calcul, nécessaires pour apprendre des concepts à partir d'exemples ; dans le modèle « probablement approximativement correct » (PAC), une classe de concepts est apprenable si un algorithme peut, à partir d'un nombre polynomial d'échantillons et en temps polynomial, produire une hypothèse précise avec une forte probabilité.

Scope

Ce domaine couvre les modèles formels d'apprenabilité : le modèle « probablement approximativement correct » (PAC) qui se demande quand un concept peut être appris avec une grande précision et une forte probabilité à partir d'un nombre polynomial d'exemples et de calculs, les modèles à borne d'erreur et d'apprentissage en ligne, l'apprenabilité faible versus forte et le boosting, ainsi que les liens avec la complexité computationnelle. Il aborde à la fois la faisabilité statistique et algorithmique de l'apprentissage.

Core questions

• Quelles classes de concepts peuvent être apprises efficacement à partir d'exemples ?
• Quelle quantité de données et de calcul l'apprentissage d'un concept nécessite-t-il ?
• Quelle est la relation entre l'apprenabilité faible et forte ?
• Comment l'apprenabilité est-elle liée à la complexité computationnelle ?

Key theories

Apprentissage probablement approximativement correct

Le modèle de Valiant définit une classe de concepts comme apprenable lorsqu'un algorithme efficace peut produire, avec une forte probabilité, une hypothèse à faible erreur à partir d'un nombre polynomial d'exemples, faisant de l'apprenabilité une question computationnelle précise.

Apprenabilité faible et boosting

Un résultat central montre que toute classe apprenable légèrement mieux que le hasard est également fortement apprenable, ce qui a directement conduit aux algorithmes de boosting qui amplifient les apprenants faibles en apprenants précis.

Limites statistiques et computationnelles

L'apprenabilité est limitée à la fois par la complexité d'échantillonnage, liée aux mesures de capacité, et par la difficulté computationnelle, de sorte que certaines classes sont statistiquement apprenables mais computationnellement intraitables.

Clinical relevance

La théorie de l'apprentissage computationnel fournit les fondements formels de ce que les algorithmes d'apprentissage peuvent et ne peuvent pas accomplir et a directement inspiré des méthodes pratiques, notamment le boosting, qui est né de la question de savoir si des apprenants faibles pouvaient être combinés en des apprenants forts ; elle encadre l'apprentissage comme une discipline computationnelle rigoureuse.

History

Valiant a introduit le modèle « probablement approximativement correct » (PAC) en 1984, donnant à l'apprentissage une définition computationnelle précise et fondant le domaine. Les travaux ultérieurs ont établi des caractérisations de la complexité d'échantillonnage, l'équivalence de l'apprenabilité faible et forte qui a motivé le boosting, et des résultats de difficulté montrant les limites computationnelles de l'apprentissage.

Key figures

• Leslie Valiant
• Michael Kearns
• Robert Schapire

Seminal works

• valiant1984
• kearns1994
• vapnik1995

Frequently asked questions

Que signifie « probablement approximativement correct » ?

Cela signifie qu'avec une forte probabilité sur l'échantillon aléatoire, l'apprenant produit une hypothèse qui est approximativement correcte, c'est-à-dire qui présente une faible erreur sur les données futures. L'apprenabilité exige d'atteindre ce résultat à partir d'un nombre d'exemples et d'une quantité de calcul qui ne croissent que de manière polynomiale.

Comment la théorie de l'apprentissage a-t-elle mené au boosting ?

Les chercheurs se sont demandé si un apprenant à peine meilleur que la supposition aléatoire pouvait être transformé en un apprenant très précis. La preuve que l'apprenabilité faible et forte sont équivalentes était constructive, et cette construction est devenue les algorithmes de boosting largement utilisés en pratique.