Une théorie de l'apprentissage

Les humains semblent être capables d'apprendre de nouveaux concepts sans avoir besoin d'être programmés explicitement dans un sens conventionnel. Dans cet article, nous considérons l'apprentissage comme le phénomène d'acquisition de connaissances en l'absence de programmation explicite. Nous proposons une méthodologie précise pour étudier ce phénomène d'un point de vue computationnel. Cela consiste à choisir un mécanisme de collecte d'informations approprié, le protocole d'apprentissage, et à explorer la classe de concepts qui peuvent être appris en un nombre raisonnable (polynomial) de étapes. Bien que la complexité algorithmique inhérente semble poser des limites sérieuses à la gamme de concepts pouvant être appris, nous montrons qu'il existe certaines classes non triviales importantes de concepts propositionnels qui peuvent être appris dans un sens réaliste.