La notion de « double descente »

La notion de « double descente » post thumbnail image

J’ai tendance à être « blasé » par les déclarations à l’emporte-pièce sur les « nouvelles » méthodes et les « nouveaux » concepts en matière de statistiques et d’apprentissage automatique. La plupart sont des « variations sur un thème ». Cependant, la notion de double descente, qui a pris de l’importance ces dernières années, est quelque chose que je considère comme véritablement nouveau et très pertinent, car elle apporte un éclairage important sur la question centrale de l’overfitting des modèles.

Dans ce billet, je vais expliquer l’idée et l’illustrer en utilisant le code de mon paquetage R regtools. (Voir aussi une discussion connexe, avec un exemple de spline par Daniela Witten).

L’idée elle-même n’est pas nouvelle, mais elle prend une importance particulière ces jours-ci, car elle pourrait faire la lumière sur l’apprentissage profond. Elle semble suggérer une réponse à la question « Pourquoi les réseaux DL fonctionnent-ils souvent bien, même s’ils sont radicalement surparamétrés ? ».

La pensée statistique classique, y compris dans mes propres livres, est que le graphique de la perte L, par exemple le taux de classification erronée, sur de nouvelles données par rapport à la complexité du modèle C, devrait être en forme de U. Lorsque C s’éloigne de 0, la perte est plus élevée. Lorsque C s’éloigne de 0, le biais est fortement réduit tandis que la variance n’augmente que légèrement. La courbe est en descente. Mais dès que C passe un point minimum, la courbe remonte, car la variance finit par dépasser le biais.

(Note technique : le biais est ici la valeur attendue de la différence entre les valeurs prédites des modèles plus riche et plus grossier, sous le modèle le plus riche, et prise sur la distribution des prédicteurs).

Au fur et à mesure que C augmente, nous finissons par atteindre le point de saturation (appelé aujourd’hui interpolation), dans lequel nous avons une erreur d’apprentissage nulle. Un exemple courant est la régression linéaire avec un modèle polynomial dans une seule variable prédictive. Ici, C est le degré du polynôme. Si nous disposons de n = 100 points de données, un polynôme du 99e degré s’adaptera exactement aux données d’apprentissage, mais sera terrible pour prédire les nouvelles données.

Mais que se passe-t-il si nous osons de toute façon ajuster un polynôme de degré supérieur à 99, c’est-à-dire si nous le surajustons délibérément ? Le problème devient alors indéterminé – il n’existe pas de solution unique au problème de la minimisation de la somme des carrés des erreurs. Il existe en fait une infinité de solutions. Mais en fait, cela peut être une vertu ; parmi ces infinies solutions, nous pouvons en choisir une qui est vraiment bonne.

« Bonne » signifierait bien sûr qu’elle est capable de bien prédire les nouveaux cas. Comment pouvons-nous trouver une telle solution ?

Je vais continuer avec l’exemple de la régression linéaire, sans toutefois supposer un modèle polynomial. Tout d’abord, quelques notations. Soit β dénote notre vecteur de coefficient de population, et b son estimation. Soit ||b|| la norme vectorielle de b. Soit p le nombre de variables prédicteurs. Encore une fois, si nous avons p variables prédicteurs, nous obtiendrons un ajustement parfait dans l’ensemble d’apprentissage si p = n-1.

Si vous êtes familier avec le LASSO, vous savez que nous pouvons faire mieux que de calculer b comme étant l’estimation des MCO ; une version réduite des MCO peut faire mieux. Mais quelle version réduite ? Pourquoi pas la solution de la norme minimale ?

Avant le point d’interpolation, notre solution unique de MCO est la fameuse

b = (X’X)-1 X’Y

On peut aussi l’obtenir sous la forme b = X- Y où X- est un inverse généralisé de X. C’est la même formule que la formule classique avant interpolation, mais elle peut aussi être utilisée après le point d’interpolation. Et le point clé est alors qu’une implémentation de ceci, l’inverse de Moore-Penrose, donne la solution de norme minimale.

Cette propriété de norme minimale réduit

ces variance. Ainsi, non seulement le PM nous permettra de dépasser le point d’interpolation, mais il réduira également la variance, ce qui pourrait faire descendre la courbe L-C une deuxième fois ! Nous avons maintenant une double forme en U (il pourrait y en avoir d’autres).

Et si nous avons de la chance, dans cette deuxième forme en U, nous pourrons atteindre un minimum plus bas que celui de la première forme. Si c’est le cas, le surajustement aura été payant !

Il y a quelques subtilités ici. La norme minimale signifie le minimum parmi toutes les solutions pour un p fixe. Au fur et à mesure que p augmente, l’espace sur lequel nous minimisons devient plus riche, donc plus de possibilités de minimiser la norme. D’autre part, la variance de cette solution de norme minimale augmente avec p. Pendant ce temps, le biais reste vraisemblablement constant, puisque toutes les solutions ont une erreur de 0 dans l’ensemble d’apprentissage. Ainsi, la dynamique sous-jacente à ce deuxième U semble être différente de celle du premier.

Maintenant, quelles sont les implications pour l’apprentissage profond ? Le calcul de l’apprentissage profond utilise généralement la descente de gradient stochastique, et des travaux théoriques et empiriques indiquent que la descente de gradient stochastique tend à se stabiliser sur une solution à norme minimale. Cela peut expliquer les exemples de réussite de l’apprentissage profond en dépit d’un surajustement.

Illustration empirique :

Ici, je vais travailler avec le jeu de données Million Song. Il se compose de 90 mesures audio effectuées sur environ 500 000 chansons (pas un million) de 1922 à 2011. L’objectif est de prédire l’année de sortie à partir de l’audio.

J’ai pris les p premiers prédicteurs, en faisant varier p de 2 à 30, et j’ai ajusté un modèle quadratique, avec O(p2) prédicteurs résultants.

L’une des nouvelles caractéristiques de regtools est sa série de fonctions qe* (« Quick and Easy »). Elles sont extrêmement simples à utiliser, toutes ayant le format d’appel qeX(d, ‘yname’), pour prédire le Y spécifié dans le cadre de données d. Encore une fois, l’accent est mis sur la simplicité ; l’appel ci-dessus est tout ce dont on a besoin, donc par exemple il n’y a pas de code préliminaire pour définir un modèle. Toutes ces fonctions sont des wrappers pour les fonctions standard du paquetage Ra, et sont associées à des wrappers predict() et plot().

Actuellement, il y a 9 algorithmes d’apprentissage automatique différents disponibles, par exemple qeSVM() et qeRF(), pour les SVM et les forêts aléatoires. Ici, nous utiliserons qePoly(), qui enveloppe notre paquetage polyreg. Notez au passage que ce dernier gère correctement les variables fictives (par exemple, aucune puissance d’une variable fictive n’est formée). Notez également que qePoly() calcule l’inverse de Moore-Penrose si nous avons dépassé l’interpolation, en utilisant la fonction ginv() du paquetage MASS.

Encore une fois, pour faire cette expérience à une échelle significative, j’ai généré des ensembles d’entraînement aléatoires de taille n = 250, et pris le reste des données comme ensemble de test. J’ai utilisé de 2 à 30 variables prédictives, et j’ai utilisé l’erreur absolue moyenne de prédiction comme critère de précision. Le

point d’interpolation se situe entre 22 et 23 prédicteurs (il n’y a pas de configuration « intermédiaire »), où il y a 265 paramètres, ce qui surajuste notre n = 250.

Hélas, le minimum dans le second U n’est pas inférieur à celui du premier, donc l’overfitting n’a pas été payant ici. Mais cela illustre bien le concept de double-descente.

Code :

overfit <- function(nreps,n,maxP) { load(‘YearData.save’) nas <- rep(NA,nreps*(maxP-1)) outdf <- data.frame(p=nas,mape=nas) rownum <- 0 for (i in 1:nreps) { idxs <- sample(1:nrow(yr),n) trn <- yr[idxs,] tst <- yr[-idxs,] for (p in 2 :maxP) { rownum <- rownum + 1 out<-qePoly(trn[,1:p+1)],
‘V1’,2,holdout=NULL) preds <- predict(out,tst[,-1]) mape <- mean(abs(preds – tst[,1])) outdf[rownum,1] <- p outdf[rownum,2] <- mape print(outdf[rownum,]) } } outdf #exécution par tapply() pour le graphique }

Comme ceci :

Comme le chargement

Related

Source :

J’ai tendance à être « blasé » par les affirmations à l’emporte-pièce de « nouvelles » méthodes et de « nouveaux » concepts en statistique et en apprentissage automatique. La plupart sont des « variations sur un thème ». Cependant, la notion de double descente, qui a pris de l’importance ces dernières années, est quelque chose que je considère comme véritablement nouveau et très pertinent, car elle apporte un éclairage important sur la question centrale de l’overfitting des modèles.

Dans ce billet, je vais expliquer l’idée et l’illustrer en utilisant le code de mon paquetage R regtools. (Voir aussi une discussion connexe, avec un exemple de spline par Daniela Witten).

L’idée elle-même n’est pas nouvelle, mais elle prend une importance particulière ces jours-ci, car elle pourrait faire la lumière sur l’apprentissage profond. Elle semble suggérer une réponse à la question « Pourquoi les réseaux DL fonctionnent-ils souvent bien, même s’ils sont radicalement surparamétrés ? ».

La pensée statistique classique, y compris dans mes propres livres, est que le graphique de la perte L, par exemple le taux de classification erronée, sur de nouvelles données par rapport à la complexité du modèle C, devrait être en forme de U. Lorsque C s’éloigne de 0, la perte est plus élevée. Lorsque C s’éloigne de 0, le biais est fortement réduit tandis que la variance n’augmente que légèrement. La courbe est en descente. Mais dès que C passe un point minimum, la courbe remonte, car la variance finit par dépasser le biais.

(Note technique : le biais est ici la valeur attendue de la différence entre les valeurs prédites des modèles plus riche et plus grossier, sous le modèle le plus riche, et prise sur la distribution des prédicteurs).

Au fur et à mesure que C augmente, nous finissons par atteindre le point de saturation (appelé aujourd’hui interpolation), dans lequel nous avons une erreur d’apprentissage nulle. Un exemple courant est la régression linéaire avec un modèle polynomial dans une seule variable prédictive. Ici, C est le degré du polynôme. Si nous disposons de n = 100 points de données, un polynôme du 99e degré s’adaptera exactement aux données d’apprentissage, mais sera terrible pour prédire les nouvelles données.

Mais que se passe-t-il si nous osons de toute façon ajuster un polynôme de degré supérieur à 99, c’est-à-dire si nous le surajustons délibérément ? Le problème devient alors indéterminé – il n’existe pas de solution unique au problème de la minimisation de la somme des carrés des erreurs. Il existe en fait une infinité de solutions. Mais en fait, cela peut être une vertu ; parmi ces infinies solutions, nous pouvons en choisir une qui est vraiment bonne.

« Bonne » signifierait bien sûr qu’elle est capable de bien prédire les nouveaux cas. Comment pouvons-nous trouver une telle solution ?

Je vais continuer avec l’exemple de la régression linéaire, sans toutefois supposer un modèle polynomial. Tout d’abord, quelques notations. Soit β dénote notre vecteur de coefficient de population, et b son estimation. Soit ||b|| la norme vectorielle de b. Soit p le nombre de variables prédicteurs. Encore une fois, si nous avons p variables prédicteurs, nous obtiendrons un ajustement parfait dans l’ensemble d’apprentissage si p = n-1.

Si vous êtes familier avec le LASSO, vous savez que nous pouvons faire mieux que de calculer b comme étant l’estimation des MCO ; une version réduite des MCO peut faire mieux. Mais quelle version réduite ? Pourquoi pas la solution de la norme minimale ?

Avant le point d’interpolation, notre solution unique de MCO est la fameuse

b = (X’X)-1 X’Y

On peut aussi l’obtenir

comme b = X- Y où X- est un inverse généralisé de X. C’est la même formule que la formule classique avant interpolation, mais elle peut aussi être utilisée après le point d’interpolation. Et le point clé est alors qu’une implémentation de ceci, l’inverse de Moore-Penrose

, donne la solution de norme minimale.

Cette propriété de norme minimale réduit la variance. Donc, non seulement MP nous permettra de dépasser le point d’interpolation, mais il réduira également la variance, ce qui pourrait faire descendre la courbe L-C une deuxième fois ! Nous avons maintenant une double forme en U (il pourrait y en avoir d’autres).

Et si nous avons de la chance, dans cette deuxième forme en U, nous pourrons atteindre un minimum plus bas que celui de la première forme. Si c’est le cas, le surajustement aura été payant !

Il y a quelques subtilités ici. La norme minimale signifie le minimum parmi toutes les solutions pour un p fixe. Au fur et à mesure que p augmente, l’espace sur lequel nous minimisons devient plus riche, donc plus de possibilités de minimiser la norme. D’autre part, la variance de cette solution de norme minimale augmente avec p. Pendant ce temps, le biais reste vraisemblablement constant, puisque toutes les solutions ont une erreur de 0 dans l’ensemble d’apprentissage. Ainsi, la dynamique sous-jacente à ce deuxième U semble être différente de celle du premier.

Maintenant, quelles sont les implications pour l’apprentissage profond ? Le calcul de l’apprentissage profond utilise généralement la descente de gradient stochastique, et des travaux théoriques et empiriques indiquent que la descente de gradient stochastique tend à se stabiliser sur une solution à norme minimale. Cela peut expliquer les exemples de réussite de l’apprentissage profond malgré le surajustement.

Illustration empirique :

Ici, je vais travailler avec le jeu de données Million Song. Il se compose de 90 mesures audio effectuées sur environ 500 000 chansons (pas un million) de 1922 à 2011. L’objectif est de prédire l’année de sortie à partir de l’audio.

J’ai pris les p premiers prédicteurs, en faisant varier p de 2 à 30, et j’ai ajusté un modèle quadratique, avec O(p2) prédicteurs résultants.

L’une des nouvelles caractéristiques de regtools est sa série de fonctions qe* (« Quick and Easy »). Elles sont extrêmement simples à utiliser, toutes ayant le format d’appel qeX(d, ‘yname’), pour prédire le Y spécifié dans le cadre de données d. Encore une fois, l’accent est mis sur la simplicité ; l’appel ci-dessus est tout ce dont on a besoin, donc par exemple il n’y a pas de code préliminaire pour définir un modèle. Toutes ces fonctions sont des wrappers pour les fonctions standard du paquetage Ra, et sont associées à des wrappers predict() et plot().

Actuellement, il y a 9 algorithmes d’apprentissage automatique différents disponibles, par exemple qeSVM() et qeRF(), pour les SVM et les forêts aléatoires. Ici, nous utiliserons qePoly(), qui enveloppe notre paquetage polyreg. Notez au passage que ce dernier gère correctement les variables fictives (par exemple, aucune puissance d’une variable fictive n’est formée). Notez également que qePoly() calcule l’inverse de Moore-Penrose si nous avons dépassé l’interpolation, en utilisant la fonction ginv() du paquetage MASS.

Encore une fois, pour faire cette expérience à une échelle significative, j’ai généré des ensembles d’entraînement aléatoires de taille n = 250, et pris le reste des données comme ensemble de test. J’ai utilisé de 2 à 30 variables prédictives, et j’ai utilisé l’erreur absolue moyenne de prédiction comme critère de précision. Le

point d’interpolation se situe entre 22 et 23 prédicteurs (il n’y a pas de configuration « intermédiaire »), où il y a 265 paramètres, ce qui surajuste notre n = 250.

Hélas, le minimum dans le second U n’est pas inférieur à celui du premier, donc l’overfitting n’a pas été payant ici. Mais cela illustre bien le concept de double-descente.

Code :

overfit <- function(nreps,n,maxP) { load(‘YearData.save’) nas <- rep(NA,nreps*(maxP-1)) outdf <- data.frame(p=nas,mape=nas) rownum <- 0 for (i in 1:nreps) { idxs <- sample(1:nrow(yr),n) trn <- yr[idxs,] tst <- yr[-idxs,] for (p in 2:maxP) { rownum <- rownum + 1 out<-qePoly(trn[,1 :p+1)],
‘V1’,2,holdout=NULL) preds <- predict(out,tst[,-1]) mape <- mean(abs(preds – tst[,1])) outdf[rownum,1] <- p outdf[rownum,2] <- mape print(outdf[rownum,]) } } outdf #exécution par tapply() pour le graphique }

Comme ceci :

Comme le chargement

Related


Continuer la lecture : https://matloff.wordpress.com/2020/11/11/the-notion-of-double-descent/

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée.

Related Post