Une introduction à la théorie de l'apprentissage computationnel

Michael Kearns et Umesh Vazirani, en mettant l'accent sur les questions d'efficacité computationnelle, introduisent un certain nombre de sujets centraux en théorie de l'apprentissage computationnel pour les chercheurs et les étudiants en intelligence artificielle, réseaux neuronaux, informatique théorique et statistiques. La théorie de l'apprentissage computationnel est un domaine de recherche nouveau et en pleine expansion qui examine les modèles formels d'induction dans le but de découvrir les méthodes communes sous-jacentes aux algorithmes d'apprentissage efficaces et d'identifier les obstacles computationnels à l'apprentissage.

Chaque sujet du livre a été choisi pour élucider un principe général, qui est exploré dans un cadre formel précis. L'intuition a été privilégiée dans la présentation pour rendre le matériel accessible au non-théoricien tout en fournissant des arguments précis pour le spécialiste. Cet équilibre est le résultat de nouvelles démonstrations de théorèmes établis et de nouvelles présentations des démonstrations standard.

Les sujets abordés comprennent la motivation, les définitions et les résultats fondamentaux, à la fois positifs et négatifs, pour le modèle de Valiant d'apprentissage probablement approximativement correct largement étudié ; le rasoir d'Occam, qui formalise une relation entre l'apprentissage et la compression de données ; la dimension de Vapnik-Chervonenkis ; l'équivalence de l'apprentissage faible et fort ; l'apprentissage efficace en présence de bruit par la méthode des requêtes statistiques ; les relations entre l'apprentissage et la cryptographie, et les limitations computationnelles qui en résultent sur l'apprentissage efficace ; la réductibilité entre les problèmes d'apprentissage ; et les algorithmes pour l'apprentissage des automates finis à partir d'expérimentations actives.