Comment différentes méthodes de validation croisée se comparent-elles en termes de variance et de biais du modèle?

Ma question est en partie motivée par ce fil: nombre optimal de plis en validation croisée de: est leave-one-out CV toujours le meilleur choix? $K$K. La réponse suggérée ici suggère que les modèles appris avec la validation croisée "laissez un test" ont une variance plus grande que ceux appris avec la validation croisée "pli en classique , ce qui rend le choix de CV non laissé un pire.$K$

Cependant, mon intuition me dit que leave-one-out CV on devrait voir la variance relativement plus faible entre les modèles que dans le -fold CV, puisque nous ne changeons un point de données à travers les plis et donc les ensembles de formation entre les plis se chevauchent considérablement.$K$

Ou aller dans l'autre sens, si est faible dans le -fold CV, les ensembles de formation seraient tout à fait différents selon les plis et les modèles qui en résultent sont plus susceptibles d'être différents (donc la variance plus élevée).$K$$K$

Si l'argument ci-dessus est correct, pourquoi les modèles appris avec CV CV sans retrait ont-ils une variance plus élevée?

pourquoi les modèles appris avec le CV sans omission ont-ils une variance plus élevée?

[TL: DR] Résumé des derniers messages et débats (juillet 2018)

Ce sujet a été largement discuté à la fois sur ce site et dans la littérature scientifique, avec des points de vue, des intuitions et des conclusions contradictoires. Retour en 2013 lorsque cette question a été demandé, l'opinion dominante était que LOOCV conduit à plus grande variance de l' erreur de généralisation attendue d'un algorithme de formation produisant des modèles sur des échantillons de taille .$n(K−1)/K$

Ce point de vue, cependant, semble être une généralisation incorrecte d'un cas particulier et je dirais que la réponse correcte est: "ça dépend ..."

En reprenant Yves Grandvalet à l'auteur d'un article de 2004 sur le sujet, je résumerais l'argument intuitif de la manière suivante:

1. Si la validation croisée consistait à faire la moyenne d’estimations indépendantes : on laissait alors un CV, on devrait voir une variance relativement plus faible entre les modèles puisque nous ne décalons qu’un point de données d’un pli à l’autre et que, par conséquent, les ensembles d’entraînement entre plis se chevauchent considérablement.
2. Ce n'est pas vrai lorsque les ensembles d'apprentissage sont fortement corrélés : la corrélation peut augmenter avec K et cette augmentation est responsable de l'augmentation globale de la variance dans le deuxième scénario. Intuitivement, dans cette situation, laisser un CV sur un CV peut être aveugle aux instabilités existantes, mais ne peut pas être déclenché par la modification d'un seul point dans les données d'apprentissage, ce qui le rend très variable pour la réalisation de l'ensemble d'apprentissage.

Des simulations expérimentales de moi-même et d' autres personnes sur ce site, ainsi que celles de chercheurs dans les articles liés ci-dessous vous montreront qu'il n'y a pas de vérité universelle sur le sujet. La plupart des expériences ont en diminuant de façon monotone ou la variance constante avec , mais certains cas particuliers montrent de plus en plus la variance avec .$K$$K$

La suite de cette réponse propose une simulation sur un exemple de jouet et une revue de littérature informelle.

[Mise à jour] Vous pouvez trouver ici une simulation alternative pour un modèle instable en présence de valeurs aberrantes.

Simulations à partir d'un exemple de jouet montrant une variance décroissante / constante

Prenons l'exemple suivant: nous adaptons un polynôme de degré 4 à une courbe sinusoïdale bruyante. Nous nous attendons à ce que ce modèle présente des résultats médiocres pour de petits ensembles de données en raison de la sur-adaptation, comme le montre la courbe d'apprentissage.

Notez que nous traçons 1 - MSE ici pour reproduire l'illustration d'ESLII page 243

 Méthodologie

Vous pouvez trouver le code pour cette simulation ici . L'approche était la suivante:

1. Génère 10 000 points à partir de la distribution où la variance vraie de est connue$sin(x) + \epsilon$$\epsilon$
2. Itérer fois (par exemple 100 ou 200 fois). À chaque itération, modifiez le jeu de données en rééchantillonnant points de la distribution d'origine.$i$$N$
3. Pour chaque ensemble de données : $i$
   • Effectuer une validation croisée des plis K pour une valeur de$K$
   • Stocker l'erreur quadratique moyenne (MSE) moyenne sur les plis K
4. Une fois que la boucle sur est terminée, calculez la moyenne et l'écart type de la MSE sur les jeux de données pour la même valeur dei $i$$i$$K$
5. Répétez les étapes ci-dessus pour tous les dans la plage jusqu'à ce que vous laissiez un CV (LOOCV){ 5 , . . . , N $K$$\{ 5,...,N\}$

Impact de sur le biais et la variance de la MSE dans jeux de données.$K$$i$

Côté gauche : Kfolds pour 200 points de données, Côté droit : Kfolds pour 40 points de données

Écart-type de MSE (parmi les ensembles de données i) par rapport à Kfolds

De cette simulation, il semble que:

• Pour un petit nombre points de données, augmenter jusqu'à ce que améliore sensiblement le biais et la variance. Pour un plus grand il n'y a aucun effet sur le biais ou la variance.K K = 10 $N = 40$$K$$K=10$$K$
• L’intuition est que, pour une taille d’entraînement efficace trop petite, le modèle polynomial est très instable, en particulier pour$K \leq 5$
• Pour un plus grand - croissant n'a pas d'impact particulier sur le biais et la variance.$N = 200$$K$

Une revue de littérature informelle

Les trois articles suivants étudient le biais et la variance de la validation croisée

• Ron Kohavi (1995)
• Yves Grandvalet et Yoshua Bengio (2004)
• Zhang et Yang (2015)

Kohavi 1995

Ce document est souvent considéré comme la source de l'argument selon lequel LOOC a une variance plus élevée. Dans la section 1:

"Par exemple, laisser-one-out est presque sans biais, mais sa variance est grande, ce qui conduit à des estimations peu fiables (Efron, 1983)"

Cette déclaration est source de beaucoup de confusion, car elle semble provenir d’Efron en 1983 et non de Kohavi. Les arguments théoriques de Kohavi et les résultats expérimentaux vont à l’ encontre de cette affirmation:

Corollaire 2 (Variance en CV)

Étant donné un ensemble de données et un inducteur. Si l'inducteur est stable sous les perturbations causées par la suppression des occurrences de test pour les plis dans le pli k-pli pour différentes valeurs de , la variance de l'estimation sera la même.$k$

Expérience Dans son expérience, Kohavi compare deux algorithmes: un arbre de décision C4.5 et un classifieur Naive Bayes sur plusieurs jeux de données du référentiel UC Irvine. Ses résultats sont ci-dessous: LHS est la précision par rapport aux plis (c'est-à-dire le biais) et RHS est la déviation standard par rapport aux plis

En fait, seul l’arbre décisionnel de trois ensembles de données présente clairement une variance plus élevée lorsque K augmente, tandis que d’autres résultats indiquent une variance décroissante ou constante.

Enfin, bien que la conclusion puisse être formulée plus fermement, rien ne permet de penser que LOO a une variance plus élevée, bien au contraire. De la section 6. Résumé

"La validation croisée du pli k avec des valeurs modérées de k (10-20) réduit la variance ... Lorsque k-diminue (2-5) et que les échantillons deviennent plus petits, il existe une variance due à l'instabilité des ensembles d'apprentissage eux-mêmes.

Zhang et Yang

Les auteurs ont une position forte sur ce sujet et indiquent clairement dans la section 7.1

En fait, dans la régression linéaire par la méthode des moindres carrés, Burman (1989) montre que parmi les CV à plis k, lors de l'estimation de l'erreur de prédiction, LOO (c.-à-d. Un CV à n plis) présente le plus faible biais et variance asymptotique. ...

... Ensuite, un calcul théorique ( Lu , 2007) montre que LOO a le plus petit biais et la variance à la fois parmi tous les CV delete-n avec toutes les suppressions n_v possibles considérées

Résultats expérimentaux De même, les expériences de Zhang vont dans le sens d'une variance décroissante avec K, comme indiqué ci-dessous pour le modèle True et le modèle incorrect pour la Figure 3 et la Figure 5.

La seule expérience pour laquelle la variance augmente avec concerne les modèles de Lasso et SCAD. Ceci est expliqué comme suit à la page 31:$K$

Toutefois, si la sélection du modèle est impliquée, la variabilité de la LOO se dégrade d'autant plus que l'incertitude liée à la sélection du modèle augmente en raison de l'espace disponible dans le modèle, des coefficients de pénalité faibles et / ou de l'utilisation de coefficients de pénalité basés sur les données.

Dans la validation croisée multipliée par nous partitionnons un ensemble de données en sous-ensembles taille égale, ne se chevauchant pas . Pour chaque pli , un modèle est formé sur , qui est ensuite évalué sur . L'estimateur de validation croisée, par exemple l'erreur de prédiction, est défini comme la moyenne des erreurs de prédiction obtenues sur chaque pli.$k$$k$$S$$S_i$$S \setminus S_i$$S_i$

Bien qu'il n'y ait pas de chevauchement entre les ensembles de tests sur lesquels les modèles sont évalués, il existe un chevauchement entre les ensembles d'apprentissage pour tout . Le chevauchement est le plus important pour la validation croisée "laissez un test". Cela signifie que les modèles appris sont corrélés, c'est-à-dire dépendants, et que la variance de la somme des variables corrélées augmente avec la quantité de covariance ( voir wikipedia ):$k>2$

Par conséquent, la validation croisée "laissez passer un test" a une grande variance par rapport à CV avec un plus petit .$k$

Cependant, notez que bien que la validation croisée en deux étapes ne pose pas le problème du chevauchement des ensembles d’entraînement, elle varie souvent beaucoup car les ensembles d’entraînement ne représentent que la moitié de la taille de l’échantillon initial. Un bon compromis est la validation croisée par dix.

Quelques articles intéressants qui abordent ce sujet (parmi tant d'autres):

• Une étude de validation croisée et de bootstrap pour l'estimation de la précision et la sélection de modèle par Ron Kohavi
• Estimateur sans biais de la variance de la validation croisée des k-fold par Yoshua Bengio et Yves Grandvalet

[...] mon intuition me dit que dans un de leave-one-out CV devrait voir la variance relativement plus faible entre les modèles que dans le -fold CV, puisque nous modifions un seul point de données à travers les plis et donc les ensembles de formation entre les plis se chevauchent sensiblement.$K$

Je pense que votre intuition est raisonnable si vous réfléchissez aux prédictions faites par les modèles de chaque repli d'abandons. Ils sont basés sur des données corrélées / très similaires (l'ensemble de données complet moins un point de données) et feront donc des prédictions similaires, c'est-à-dire une faible variabilité.

La source de confusion est que lorsque les gens parlent de LOOCV entraînant une forte variabilité, ils ne parlent pas des prédictions faites par les nombreux modèles construits au cours de cette boucle de validation croisée sur les ensembles de réserve. Au lieu de cela, ils parlent de la variabilité que votre modèle final choisi (celui choisi via LOOCV) aurait si vous entraîniez ce modèle / ces paramètres exacts sur de nouveaux ensembles d'entraînement - des ensembles d'entraînement que votre modèle n'avait pas vus auparavant. Dans ce cas, la variabilité serait élevée.

Pourquoi la variabilité serait-elle élevée? Simplifions cela un peu. Imaginez qu'au lieu d'utiliser LOOCV pour choisir un modèle, vous ne disposiez que d'un seul jeu d'apprentissage, puis vous testiez un modèle construit à l'aide de ces données d'apprentissage, par exemple 100 fois sur 100 points de données de test simples (les points de données ne font pas partie de l'ensemble d'apprentissage). . Si vous choisissez le modèle et le jeu de paramètres qui répondent le mieux à ces 100 tests, vous en choisirez un qui permette à cet ensemble d’entraînement particulier de vraiment bien prédire les données de test. Vous pouvez éventuellement choisir un modèle qui capture 100% des associations entre cet ensemble de données de formation particulier et les données en attente. Malheureusement, une partie de ces associations entre les ensembles de données d'apprentissage et de test sera constituée d'associations de bruit ou de parasites car, bien que l'ensemble de test ait changé et que vous puissiez identifier le bruit de ce côté, le jeu de données d'apprentissage ne le fait pas et vous ne pouvez pas déterminer la variance expliquée due au bruit. En d'autres termes, cela signifie que vos prédictions ont été surajustées à cet ensemble de données d'entraînement particulier.

Maintenant, si vous deviez ré-entraîner ce modèle avec les mêmes paramètres plusieurs fois sur de nouveaux ensembles d’entraînement, que se passerait-il? Eh bien, un modèle surajusté à un ensemble particulier de données d’entraînement entraînera une variabilité dans ses prédictions lorsque l’entraînement changera (c’est-à-dire qu'il modifiera légèrement l’entraînement et que le modèle modifiera considérablement ses prédictions).

Comme tous les replis du LOOCV sont fortement corrélés, il est semblable au cas ci-dessus (même ensemble d’entraînement, points de test différents). En d’autres termes, si cet ensemble d’entraînement particulier présente une corrélation fallacieuse avec ces points de test, votre modèle aura des difficultés à déterminer les corrélations réelles et les réalités fallacieuses, car même si l’ensemble de tests change, l’entraînement ne change pas.

En revanche, des plis d'apprentissage moins corrélés signifient que le modèle sera adapté à plusieurs jeux de données uniques. Ainsi, dans cette situation, si vous réentraînez le modèle sur un autre nouvel ensemble de données, cela conduira à une prédiction similaire (c.-à-d. Une faible variabilité).

Bien que cette question soit plutôt ancienne, je voudrais ajouter une réponse supplémentaire car j'estime qu'il convient de clarifier cela un peu plus.

Ma question est en partie motivée par ce fil de discussion: nombre optimal de plis dans la validation croisée des plis en K: le CV sans relâche est-il toujours le meilleur choix? . La réponse suggérée ici suggère que les modèles appris avec la validation croisée "laissez un test" ont une variance plus grande que ceux appris avec la validation croisée du pli "K" régulier, ce qui rend le choix du CV "laissez un test" plus difficile.

Cette réponse ne suggère pas cela, et elle ne devrait pas. Passons en revue la réponse fournie ici:

En règle générale, la validation croisée "laissez-passer" ne conduit pas à de meilleures performances que le pli-K, elle risque davantage d'être pire, car la variance est relativement élevée (c'est-à-dire que sa valeur change davantage pour différents échantillons de données que la valeur pour validation croisée des k-fold).

Il parle de performance . Ici, la performance doit être comprise comme la performance de l'estimateur d'erreur de modèle . Ce que vous estimez avec k-fold ou LOOCV est la performance du modèle, à la fois lorsque vous utilisez ces techniques pour choisir le modèle et pour fournir une estimation d'erreur en soi. Ce n'est PAS la variance du modèle, c'est la variance de l'estimateur de l'erreur (du modèle). Voir l' exemple (*) ci-dessous.

Cependant, mon intuition me dit que, dans le CV non mémorisé, il devrait y avoir une variance relativement plus faible entre les modèles que dans le CV au pli K, car nous ne décalons qu'un point de données entre les plis et, par conséquent, les ensembles d’entraînement entre plis se chevauchent sensiblement.

En effet, la variance entre les modèles est plus faible. Ils sont formés à des jeux de données qui ont observations en commun! À mesure que augmente, ils deviennent pratiquement le même modèle (en supposant qu'il n'y a pas de stochasticité).$n-2$$n$

C’est précisément cette variance plus faible et cette corrélation plus élevée entre les modèles qui font que l’estimateur dont je viens de parler a plus de variance, parce que cet estimateur est la moyenne de ces quantités corrélées et que la variance de la moyenne des données corrélées est supérieure à celle des données non corrélées. . On montre ici pourquoi: la variance de la moyenne des données corrélées et non corrélées .

Ou bien, dans l'autre sens, si K est faible dans le K-fold CV, les ensembles d'apprentissage seraient très différents d'un pli à l'autre et les modèles résultants seraient plus susceptibles d'être différents (donc une variance supérieure).

En effet.

Si l'argument ci-dessus est correct, pourquoi les modèles appris avec CV CV sans retrait ont-ils une variance plus élevée?

L'argument ci-dessus est correct. Maintenant, la question est fausse. La variance du modèle est un sujet complètement différent. Il y a une variance où il y a une variable aléatoire. En apprentissage machine, vous traitez avec beaucoup de variables aléatoires, en particulier et non limitées à: chaque observation est une variable aléatoire; l'échantillon est une variable aléatoire; le modèle, puisqu'il est formé à partir d'une variable aléatoire, est une variable aléatoire; L'estimateur de l'erreur que votre modèle produira face à la population est une variable aléatoire. et enfin, l'erreur du modèle est une variable aléatoire, car il est probable qu'il y ait du bruit dans la population (on parle d'erreur irréductible). Il peut également y avoir plus d’aléatoire s’il existe une stochasticité dans le processus d’apprentissage du modèle. Il est primordial de faire la distinction entre toutes ces variables.

(*) Exemple : supposons que vous ayez un modèle avec une erreur réelle , où vous devriez comprendre comme l'erreur que le modèle produit sur toute la population. Comme vous avez un échantillon tiré de cette population, vous utilisez des techniques de validation croisée sur cet échantillon pour calculer une estimation de , que nous pouvons nommer . Comme tout estimateur, est une variable aléatoire, ce qui signifie qu'il a sa propre variance, , et son propre biais, . est précisément ce qui est le plus élevé lorsque vous utilisez LOOCV. Bien que LOOCV soit un estimateur moins biaisé que le avec$err$$err$$E$$\tilde{err}$$\tilde{err}$$var(\tilde{err})$$E(\tilde{err}-err)$$var(\tilde{err})$$k-fold$$k < n$ , il a plus de variance. Pour mieux comprendre pourquoi un compromis entre biais et variance est souhaité , supposons que et que vous ayez deux estimateurs: et . Le premier produit cette sortie$err = 10$$\tilde{err}_1$$\tilde{err}_2$

Le dernier, même s'il a plus de biais, devrait être préféré, car il a beaucoup moins de variance et un biais acceptable , c'est-à-dire un compromis ( compromis biais-variance ). Veuillez noter que vous ne voulez pas non plus une très faible variance si cela entraîne un biais important!

Note complémentaire : dans cette réponse, j'essaie de clarifier (ce que je pense être) les idées fausses qui entourent ce sujet et, en particulier, j'essaie de répondre point par point et précisément les doutes du demandeur. En particulier, j'essaie de clarifier de quel écart nous parlons , et c'est ce qui est demandé ici essentiellement. C'est-à-dire que j'explique la réponse qui est liée par le PO.

Cela étant dit, bien que j'expose le raisonnement théorique à la base de cette affirmation, nous n'avons pas encore trouvé de preuves empiriques concluantes à l'appui. Alors s'il vous plaît soyez très prudent.

Idéalement, vous devriez commencer par lire ce message, puis consulter la réponse de Xavier Bourret Sicotte, qui propose une discussion approfondie sur les aspects empiriques.

Enfin, il faut prendre en compte un autre élément: même si la variance augmente, reste plat (comme nous n’avons pas prouvé le contraire), le avec suffisamment petit permet la répétition ( répétition du k-fold ), ce qui devrait absolument être fait, par exemple, . Cela réduit efficacement la variance et n’est pas une option lors de l’exécution de LOOCV.$k$$k-fold$$k$10 × 10 - f o l d$10 \ \times \ 10-fold$

Les problèmes sont en effet subtils. Mais ce n'est certainement pas vrai que le LOOCV a une plus grande variance en général. Un article récent aborde certains aspects clés et aborde plusieurs idées fausses apparemment répandues sur la validation croisée.

Yongli Zhang et Yuhong Yang (2015). Validation croisée pour la sélection d'une procédure de sélection de modèle. Journal of Econometrics, vol. 187, 95-112.

Les idées fausses suivantes sont fréquemment observées dans la littérature, même jusqu'à maintenant:

"Le CV sans affectation (LOO) a un biais plus petit mais une variance plus grande que le CV sans sortie plus"

Cette vue est assez populaire. Kohavi (1995, Section 1), par exemple, a déclaré: "Par exemple, le laisser-aller est presque sans biais, mais la variance est grande, ce qui conduit à des estimations peu fiables". La déclaration, cependant, n'est généralement pas vraie.

Plus en détail:

Dans la littérature, même en incluant les publications récentes, les recommandations sont trop nombreuses. La suggestion générale de Kohavi (1995) d'utiliser un CV multiplié par 10 a été largement acceptée. Par exemple, Krstajic et al (2014, page 11) déclarent: «Kohavi [6] et Hastie et al [4] montrent de manière empirique que la validation croisée au pli en V par rapport à la validation croisée à sortie unique présente une variance inférieure». Ils prennent donc la recommandation d'un CV 10 fois (avec répétition) pour toutes leurs investigations numériques. À notre avis, une telle pratique peut être trompeuse. Premièrement, il ne devrait y avoir aucune recommandation générale qui ne tienne pas compte de l'objectif de l'utilisation du CV. En particulier, l'examen du biais et de la variance de l'estimation de la précision du CV d'un modèle candidat / d'une procédure de modélisation peut être très différent de la sélection du modèle optimal (l'un des deux objectifs de la sélection du modèle étant indiqué plus haut). Deuxièmement, même limité au contexte d'estimation de l'exactitude, l'énoncé n'est généralement pas correct. Pour les modèles / procédures de modélisation à faible instabilité, LOO présente souvent la plus faible variabilité. Nous avons également démontré que pour les procédures très instables (par exemple, LASSO avec pn beaucoup plus grand que n), les CV de 10 ou 5 fois, tout en réduisant la variabilité, peuvent avoir une MSE considérablement plus grande que LOO en raison d'une augmentation encore plus importante du biais. Pour les modèles / procédures de modélisation à faible instabilité, LOO présente souvent la plus faible variabilité. Nous avons également démontré que pour les procédures très instables (par exemple, LASSO avec pn beaucoup plus grand que n), les CV de 10 ou 5 fois, tout en réduisant la variabilité, peuvent avoir une MSE considérablement plus grande que LOO en raison d'une augmentation encore plus importante du biais. Pour les modèles / procédures de modélisation à faible instabilité, LOO présente souvent la plus faible variabilité. Nous avons également démontré que pour les procédures très instables (par exemple, LASSO avec pn beaucoup plus grand que n), les CV de 10 ou 5 fois, tout en réduisant la variabilité, peuvent avoir une MSE considérablement plus grande que LOO en raison d'une augmentation encore plus importante du biais.

Globalement, d'après les figures 3-4, LOO et les CV répétés de 50 et 20 fois sont les meilleurs ici, 10 fois est nettement pire et k ≤ 5 est clairement mauvais. Pour l’estimation prédictive des performances, nous avons tendance à penser que LOO est généralement le meilleur ou l’un des meilleurs pour un modèle fixe ou une procédure de modélisation très stable (telle que BIC dans notre contexte), à ​​la fois en biais et en variance, ou assez proche des meilleurs en termes de performances. MSE pour une procédure plus instable (telle que AIC ou même LASSO avec p ≫ n). Bien qu'un CV multiplié par 10 (avec répétitions) puisse certainement être le meilleur parfois, mais plus fréquemment, il se trouve dans une position inconfortable: il est plus risqué que LOO (en raison du problème de biais) pour l'estimation de l'erreur de prédiction et il est généralement pire que le supprimer. -n / 2 CV pour identifier le meilleur candidat.

Avant de discuter de biais et de variance, la première question est:

Qu'est-ce qui est estimé par validation croisée?

$K$$n(K-1)/K$$K$$K$

$K$

$K$

$K$

Je pense qu'il y a une réponse plus simple. Si vous augmentez k, les ensembles de tests deviennent de plus en plus petits. Étant donné que les plis sont échantillonnés de manière aléatoire, il peut arriver que de petits ensembles de tests, mais pas aussi souvent avec des plus grands, ne soient pas représentatifs d'un mélange aléatoire. Un ensemble de tests pourrait contenir tous les enregistrements difficiles à prédire et un autre, tous les plus faciles. Par conséquent, la variance est élevée lorsque vous prédisez de très petits ensembles de tests par fois.