Résumé
Ce cours introduit le fonctionnement d’un algorithme d’apprentissage et le compromis entre le biais et la variance des estimateurs de prédiction. Un algorithme d’apprentissage prend en entrée une donnée x à partir de laquelle il prédit une approximation de la réponse y. Un tel algorithme inclut des paramètres internes qui sont optimisés grâce aux exemples d’entraînement, de façon à ce que la prédiction soit précise sur ces exemples. Le but est que la précision de la prédiction se généralise à d’autres données de « même type » que les exemples d’entraînement. On parle alors d’erreur de généralisation. L’algorithme d’apprentissage supervisé calcule la prédiction avec une fonction sélectionnée parmi une classe de fonctions possibles, par exemple en minimisant l’erreur moyenne obtenue sur les exemples d’entraînement. Cette erreur est le risque statistique. L’information a priori sur le problème permet de spécifier la classe d’approximation et le calcul du risque.
Le cours commence par une présentation des algorithmes de classification linéaire qui divisent l’espace des donnés en deux parties séparées par un hyperplan. Celui-ci est optimisé afin de minimiser l’erreur de classification. Ces algorithmes s’étendent par un changement de variable qui remplace x par une nouvelle représentation. Un enjeu central est de choisir ce changement de variable afin de minimiser le risque de généralisation.
Le risque de généralisation comporte deux termes. Une erreur d’approximation due au fait que l’on approxime la réponse sur une classe limitée de fonctions. C’est le terme de biais. Le biais augmente lorsque l’on réduit la classe d’approximation. Le second terme d’erreur est dû au fait que l’algorithme minimise l’erreur sur des exemples d’entraînement et non pas sur toutes les données possibles. Cela induit une fluctuation aléatoire qui dépend du choix des exemples d’entraînement, et dont on veut contrôler l’amplitude maximum. Ce terme de variabilité dépend de la complexité de la classe d’approximation. Il diminue lorsque l’on réduit la taille de cette classe d’approximation. L’optimisation de la classe d’approximation résulte donc d’un compromis entre le biais et la variabilité du risque.
Le cadre statistique d’approximation PAC (probablement approximativement correcte) consiste à établir des conditions pour avoir un risque de généralisation qui devienne arbitrairement petit. Lorsque la classe est de taille finie, on peut calculer une borne supérieure de la fluctuation maximum du risque, en fonction du cardinal de la classe d’approximation, avec une probabilité arbitrairement proche de 1. Cela permet d’établir des conditions pour que l’algorithme d’apprentissage soit probablement approximativement correct.
