Variance des estimations de validation croisée multipliées par sous la forme : quel est le rôle de la «stabilité»?

37

TL, DR: Il semble que, contrairement aux conseils répétés, la validation croisée "une fois (LOO-CV)" (laissez-passer une fois) - c’est-à-direun CVfois, avec(le nombre de plis) égal à(le d’observations d’entraînement) - fournit des estimations de l’erreur de généralisation qui sont la moindre variable pour tout, et non la plus variable, en supposant une certainecondition de stabilité sur le modèle / l’algorithme, le jeu de données ou les deux (je ne suis pas sûr (e)). est correct car je ne comprends pas vraiment cette condition de stabilité).KKKNK

  • Quelqu'un peut-il expliquer clairement en quoi consiste exactement cette condition de stabilité?
  • Est-il vrai que la régression linéaire est l'un de ces algorithmes "stables", ce qui implique que LOO-CV est strictement le meilleur choix de CV en ce qui concerne le biais et la variance des estimations de l'erreur de généralisation?

La sagesse conventionnelle est que le choix de dans CV CV suit un compromis biais-variance, de telles valeurs inférieures de (approchant 2) conduisent à des estimations de l'erreur de généralisation qui ont un biais plus pessimiste, mais une variance inférieure, alors que des valeurs plus élevées de (approchant ) conduisent à des estimations moins biaisées, mais avec une variance plus grande. L'explication conventionnelle de ce phénomène d'augmentation de la variance avec est peut-être plus évidente dans Les éléments d'apprentissage statistique (section 7.10.1):KKKKNK

Avec K = N, l'estimateur de validation croisée est approximativement sans biais pour l'erreur de prédiction vraie (attendue), mais peut avoir une variance élevée du fait que les N "ensembles d'apprentissage" sont si similaires les uns aux autres.

L'implication étant que les erreurs de validation sont plus fortement corrélées, de sorte que leur somme est plus variable. Ce raisonnement a été répété dans de nombreuses réponses sur ce site (par exemple, ici , ici , ici , ici , ici , ici et ici ) ainsi que sur divers blogs, etc. Mais une analyse détaillée n’est pratiquement jamais fournie. seulement une intuition ou un bref aperçu de ce à quoi une analyse pourrait ressembler.N

On peut cependant trouver des déclarations contradictoires, citant généralement une certaine condition de "stabilité" que je ne comprends pas vraiment. Par exemple, cette réponse contradictoire cite quelques paragraphes d'un article de 2015 qui indique notamment: "Pour les modèles / procédures de modélisation avec une faible instabilité , LOO présente souvent la plus faible variabilité" (non souligné dans l'original). Cet article (section 5.2) semble convenir que LOO représente le choix le moins variable de tant que le modèle / algorithme est "stable". Prenant même une autre position sur la question, il y a aussi ce papier (corollaire 2), qui dit: "La variance de la validation croisée du pli [...] dépend pas dek kKkk, "citant encore une certaine condition de" stabilité ".

L'explication de la raison pour laquelle LOO pourrait être le CV à fold le plus variable est suffisamment intuitive, mais il existe une contre-intuition. L'estimation finale du cv de l'erreur quadratique moyenne (MSE) est la moyenne des estimations de la MSE dans chaque pli. Ainsi, lorsque augmente jusqu'à , l'estimation du CV est la moyenne d'un nombre croissant de variables aléatoires. Et nous savons que la variance d'une moyenne diminue avec le nombre de variables dont la moyenne est calculée. Ainsi, pour que LOO soit le CV le plus variable , il faudrait que l’augmentation de la variance due à la corrélation accrue entre les estimations de l’EMS l'emporte sur la diminution de la variance due au plus grand nombre de plisKKNK. Et il n’est pas du tout évident que cela soit vrai.

Devenue complètement confuse après avoir réfléchi à tout cela, j'ai décidé de lancer une petite simulation pour le cas de régression linéaire. Je simulé 10.000 jeux de données avec = 50 et 3 prédicteurs non corrélées, chaque fois que l' estimation de l'erreur de généralisation en utilisant CV de avec = 2, 5, 10, ou 50 = . Le code R est ici. Voici les moyennes et les variances résultantes des estimations de CV sur les 10 000 jeux de données (en unités MSE):K K NNKKN

         k = 2 k = 5 k = 10 k = n = 50
mean     1.187 1.108  1.094      1.087
variance 0.094 0.058  0.053      0.051

Ces résultats montrent la tendance attendue selon laquelle des valeurs plus élevées de conduisent à un biais moins pessimiste, mais semblent également confirmer que la variance des estimations de CV est la plus faible, et non la plus élevée, dans le cas de la LOO.K

Il apparaît donc que la régression linéaire est l’un des cas "stables" mentionnés dans les documents ci-dessus, où l’augmentation de est associée à une variance décroissante plutôt qu’augmentant dans les estimations de CV. Mais ce que je ne comprends toujours pas, c'est:K

  • Quelle est précisément cette condition de "stabilité"? Est-ce que cela s'applique aux modèles / algorithmes, aux jeux de données ou aux deux dans une certaine mesure?
  • Existe-t-il une façon intuitive de penser à cette stabilité?
  • Quels sont d'autres exemples de modèles / algorithmes ou d'ensembles de données stables et instables?
  • Est-il relativement sûr de supposer que la plupart des modèles / algorithmes ou jeux de données sont "stables" et que, par conséquent, devrait généralement être choisi aussi haut que possible du point de vue des calculs?K
Jake Westfall
la source
1
+1 Quelle est exactement la "moyenne" dans vos résultats de simulation? Estimation du CV moyen de l'erreur de généralisation (moyenne sur 10 000 jeux de données)? Mais à quoi devrions-nous le comparer? Il serait plus utile de montrer le biais, c’est-à-dire l’écart racine-carré-par rapport à la véritable erreur de généralisation. En outre, quelle est "vraie erreur de généralisation" dans ce cas? Vraie erreur de généralisation de l'estimation sur un jeu de données N = 100 donné? Ou valeur attendue de la vraie erreur de généralisation (valeur attendue pour tous les jeux de données N = 100)? Ou autre chose?
amibe dit de réintégrer Monica
3
+1 Après un bref aperçu de fr.wikipedia.org/wiki/, il semble que dans ce contexte, la stabilité signifie qu'un algorithme produit des résultats similaires sur un ensemble d'apprentissage avec des exemples et . Où similaire signifie différence par rapport à une fonction de perte liée par une valeur faibleN - 1NN1
Łukasz Grad
1
En dehors de cela, j'en ai récemment parlé avec @DikranMarsupial (qui est probablement l'un de nos principaux experts en validation croisée ici sur CV) dans les commentaires - il a suggéré de lire le document de Kohavi de 1995 . Dikran parlait aussi de stabilité. Malheureusement, je n'ai pas suivi depuis.
amibe dit de réintégrer Monica
2
Je ne pense pas, @Jake. Ce que j’ai écrit invalide votre "contre-intuition", mais la principale "intuition" (des modèles fortement dépendants de modèles différents) peut encore tenir.
amibe dit de réintégrer Monica
1
Une autre simulation corrobore vos conclusions selon lesquelles la variance diminue avec : stats.stackexchange.com/a/357749/28666 . K
Amibe dit Réintégrer Monica

Réponses:

15

Cette réponse fait suite à ma réponse dans Biais et variance dans la validation croisée avec un pli laissé par un pli vers le K, qui explique pourquoi LOOCV ne conduit pas toujours à une variance plus élevée. En suivant une approche similaire, je tenterai de mettre en évidence un cas où LOOCV entraîne une variance plus élevée de la présence de valeurs aberrantes et un "modèle instable".

Stabilité algorithmique (théorie de l'apprentissage)

Le sujet de la stabilité algorithmique est récent et plusieurs résultats classiques et infuentiels ont été prouvés au cours des 20 dernières années. Voici quelques articles souvent cités

La meilleure page pour comprendre est certainement la page wikipedia, qui fournit un excellent résumé écrit par un utilisateur vraisemblablement très compétent.

Définition intuitive de la stabilité

Intuitivement, un algorithme stable en est un pour lequel la prédiction ne change pas beaucoup lorsque les données d'apprentissage sont légèrement modifiées.

Officiellement, il existe une demi-douzaine de versions de la stabilité, liées entre elles par des conditions techniques et des hiérarchies. Voir ce graphique à partir d’ ici pour exemple:

entrez la description de l'image ici

L’objectif est cependant simple, nous voulons obtenir des limites précises sur l’erreur de généralisation d’un algorithme d’apprentissage spécifique, lorsque cet algorithme satisfait au critère de stabilité. Comme on pouvait s'y attendre, plus le critère de stabilité est restrictif, plus la limite correspondante sera étroite.

Notation

La notation suivante est tirée de l'article de wikipedia, qui reproduit lui-même les papiers de Bousquet et Elisseef:

  • L'ensemble d'apprentissage est tiré de la distribution inconnue DS={z1=(x1,y1),...,zm=(xm,ym)}
  • La fonction de perte d'une hypothèse par rapport à un exemple est définie parf z V ( f , z )VfzV(f,z)
  • Nous modifions l'ensemble d'apprentissage en supprimant le ième élément:iS|i={z1,...,zi1,zi+1,...,zm}
  • Ou en remplaçant le ième élément:iSi={z1,...,zi1,zi,zi+1,...,zm}

Définitions formelles

Peut-être la notion la plus forte de stabilité à laquelle on pourrait s’attendre à ce qu’un algorithme d’apprentissage intéressant obéisse est celle de stabilité uniforme :

Stabilité uniforme Un algorithme a une stabilité uniforme rapport à la fonction de perte si:βV

SZm  i{1,...,m},  sup|V(fs,z)V(fS|i,z)|  β

Considéré en fonction de , le terme peut s’écrire comme . Nous disons que l'algorithme est stable lorsque diminue avec . Une forme de stabilité légèrement plus faible est:mββmβm1m

Stabilité de l'hypothèse

i{1,...,m},  E[ |V(fs,z)V(fS|i,z)| ] β

Si un point est supprimé, la différence dans le résultat de l'algorithme d'apprentissage est mesurée par la différence absolue moyenne des pertes ( norme ). Intuitivement: de petits changements dans l'échantillon peuvent uniquement amener l'algorithme à passer aux hypothèses proches.L1

L'avantage de ces formes de stabilité est qu'elles fournissent des limites pour le biais et la variance des algorithmes stables. Bousquet a notamment prouvé ces limites pour la stabilité uniforme et hypothétique en 2002. Depuis lors, de nombreux travaux ont été réalisés pour tenter d'assouplir les conditions de stabilité et de généraliser les limites, par exemple en 2011, Kale, Kumar, Vassilvitskii soutiennent que la stabilité carrée moyenne fournit de meilleures limites de réduction de variance quantitative.

Quelques exemples d'algorithmes stables

Les algorithmes suivants se sont avérés stables et ont des limites de généralisation éprouvées:

  • Régression des moindres carrés régularisée (avec un préalable approprié)
  • Classificateur KNN avec fonction de perte 0-1
  • SVM avec noyau borné et grande constante de régularisation
  • Marge souple SVM
  • Algorithme d'entropie relative minimale pour la classification
  • Une version des régulariseurs d'ensachage

Une simulation expérimentale

En répétant l'expérience du thread précédent ( voir ici ), nous introduisons maintenant un certain rapport de valeurs aberrantes dans l'ensemble de données. En particulier:

  • 97% des données présentent un bruit uniforme[.5,.5]
  • 3% des données avec bruit uniforme[20,20]

Comme le modèle polynomial à ordres n'est pas régularisé, il sera fortement influencé par la présence de quelques valeurs aberrantes pour de petits ensembles de données. Pour les ensembles de données plus volumineux ou lorsqu'il y a plus de valeurs aberrantes, leur effet est moindre car elles ont tendance à s'annuler. Voir ci-dessous deux modèles pour 60 et 200 points de données.3

entrez la description de l'image ici

Effectuer la simulation comme précédemment et tracer la MSE moyenne résultante et la variance de la MSE donne des résultats très similaires à ceux de l'expérience 2 du document Bengio & Grandvalet 2004 .

Côté gauche : pas de valeurs aberrantes. Côté droit : 3% de valeurs aberrantes.

entrez la description de l'image ici

entrez la description de l'image ici

(voir le document lié pour l'explication du dernier chiffre)

Des explications

Citant la réponse d’Yves Grandvalet à l’autre fil:

Intuitivement, [dans la situation des algorithmes instables], 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 du test. ensemble de formation.

En pratique, il est assez difficile de simuler une augmentation de la variance due au LOOCV. Cela nécessite une combinaison particulière d'instabilité, quelques valeurs aberrantes mais pas trop nombreuses, et un grand nombre d'itérations. Cela est peut-être attendu, car il a été démontré que la régression linéaire est relativement stable. Une expérience intéressante consisterait à répéter cette opération pour des données de dimension supérieure et un algorithme plus instable (arbre de décision, par exemple).

Xavier Bourret Sicotte
la source
+1, mais j'espère que ce fil pourra éventuellement être fermé en tant que duplicata de celui qui est lié (j'attendrais que la période de prime soit terminée et que les discussions se soumettent et que la réponse soit finalement acceptée). Je commenterai plus tard.
amibe dit de réintégrer Monica le
Je ne suis pas vraiment convaincu que la question est un doublon. Ma question utilise la variance de la question LOO principalement comme moyen de cadrer les questions principales, qui consistent à essayer d'obtenir une explication accessible de ce que signifie "stabilité" - voir les questions pointillées en haut et en bas du PO. En parlant de cela, bien que cette réponse soit utile (+1), je ne vois pas que vous ayez tenté de répondre aux questions sur la stabilité ... vous utilisez le terme plusieurs fois, mais vous semblez le faire de manière à suppose que le lecteur sait déjà ce que cela signifie. Pas sûr que je puisse accepter la réponse dans sa forme actuelle.
Jake Westfall
1
@JakeWestfall Quand j'ai écrit que j'espérais que ce fil de discussion pourrait éventuellement être fermé en tant que duplicata, je voulais dire que j'espère qu'une réponse acceptée dans ce fil de discussion sera finalement suffisamment grande pour couvrir les choses que vous avez demandées :) Examinez l'article 2 de Bengio & Grandvalet. Ils montrent qu'en utilisant la régression linéaire et les données gaussiennes, ils obtiennent une variance minimale pour LOOCV (c'est aussi votre résultat), mais si les données contiennent une fraction des valeurs aberrantes, la variance est supérieure à LOOCV. plier ou si. Je pense que cela indique à quoi correspond la "stabilité" pertinente.
amibe dit de réintégrer Monica le
3
J'adore @XavierBourretSicotte. Merci de faire un si bon travail sur cette réponse.
Jake Westfall
1
Oui, en citant cet article: pdfs.semanticscholar.org/bf83/… : "Un algorithme stable a la propriété de remplacer un élément dans son ensemble d'apprentissage ne change pas grand-chose de son résultat. En conséquence, l'erreur empirique, si elle est considérée comme une Les algorithmes stables peuvent alors être de bons candidats pour que leur erreur empirique soit proche de leur erreur de généralisation
Xavier Bourret Sicotte
2

Je vais donner ma réponse dans le contexte du paragraphe que vous citez:

Avec K = N, l'estimateur de validation croisée est approximativement sans biais pour l'erreur de prédiction vraie (attendue), mais peut avoir une variance élevée du fait que les N "ensembles d'apprentissage" sont si similaires les uns aux autres.

L'estimateur de cv de l'erreur de prédiction réelle (attendue) est basé sur un exemple d'ensemble d'apprentissage, de sorte qu'ici, les attentes sont supérieures aux échantillons d'ensemble d'apprentissage, lorsque je comprends bien.

Ainsi, ce paragraphe relatif à la "variance élevée" indique ensuite qu'il existe une différence "élevée" entre l'erreur attendue et l'erreur estimée par CV (qui est ici, la moyenne sur les plis).

Cela a du sens parce que le modèle est adapté à un ensemble d’entraînement particulier et que tous les plis d’entraînement sont très similaires entre eux. Cependant, bien que les plis d’entraînement soient très similaires au sein d’un tour de CV, l’estimation diffère probablement beaucoup si nous échangeons des échantillons d’entraînement pour le CV. Dans le CV k-fold, puisque nous "diversifions" les plis d’entraînement, nous avons un effet de moyennage et, à travers les plis k, les estimations varient alors moins.

Autrement dit, l’estimateur de CV sans omission (One-Out) est quasiment une méthode de calcul automatique si vous ne faites pas pivoter les plis et ne basez votre estimation d’erreur sur un seul ensemble de validation. Là encore, par rapport aux exemples d’entraînement, il y aura une forte variance par rapport aux estimations de k-fold, où vous faites la moyenne des plis en formant déjà des modèles quelque l'erreur via k-fold ne variera probablement pas beaucoup).

MODIFIER:

Lorsque je lis quelques réponses ici sur la validation croisée et Internet en général, je pense qu'il semble y avoir une certaine confusion à l’estimateur auquel nous faisons référence. Je pense que certaines personnes se réfèrent à un modèle ayant une variance élevée (avec le langage ML pour la perte ayant une composante de variance dominante) par rapport à la variance élevée de l'estimateur de CV à plis k. Et un autre ensemble de réponses fait référence à la variance en tant que variance d'échantillon concernant les plis quand quelqu'un dit "le k-fold a une variance élevée". Je suggère donc d’être précis, car les réponses sont différentes dans les deux cas.


la source
Lorsque je discute de variance, je suppose que nous parlons de la variance de l’estimateur de cv sur l’entraînement D défini ici: stats.stackexchange.com/questions/365224/… et ici: stats.stackexchange.com/questions/325123/… . Yves Grandvalet et Bengio soutiennent dans leur article de 2004 que le CV estime l’erreur de prédiction attendue. Vous pouvez voir sa réponse ici: stats.stackexchange.com/a/358138/192854
Xavier Bourret Sicotte
Si vous voulez fonder votre réponse sur différentes définitions de la variance, je pense qu’il serait utile d’ajouter les définitions et formules formelles. Je devrais peut-être le faire aussi dans mes réponses.
Xavier Bourret Sicotte
Oui, je dois revoir un peu la littérature et ajouter quelques formules à la réponse. La citation tirée de la publication Les éléments de l’apprentissage statistique reste tout de même intuitive, à savoir que LOOCV a une variance élevée si le modèle a une variance élevée, car c’est une moyenne sur les plis. Si un modèle présente un biais élevé, à la fois les estimateurs LOOCV et tous les k-fold doivent présenter une variance faible (indépendante du biais) car les prédictions ne varieront pas autant. Mais le point dans le paragraphe était prob. que le LOOCV par rapport au k-fold dans la plupart des cas
Il a été démontré que la citation était incorrecte - du moins à titre de généralisation - voir les multiples articles cités dans mes réponses
Xavier Bourret Sicotte
1

Nous avons déjà vécu cela auparavant - vous devenez trop mathématique à propos d'un cheval mort. Voir l'article classique de Ron Kohavi (Stanford-Univ) sur le CV et le dilemme biais-variance ici . Quand vous aurez fini de lire ceci, vous ne voudrez plus faire de LOOCV, et vous serez probablement attiré par un CV multiplié par 10 et / ou par un CV non biaisé.

Vous devez également penser aux grands ensembles de données, pour lesquels LOOCV est beaucoup trop coûteux en calcul. À l'heure actuelle, LOOCV n'est pas vraiment une option dans les flux de travail / pipelines de la plupart des groupes.

Quelle est précisément cette condition de "stabilité"? Est-ce que cela s'applique aux modèles / algorithmes, aux jeux de données ou aux deux dans une certaine mesure?

Dans l'univers de toutes les fonctions de coût et dans celui de tous les jeux de fonctionnalités, je ne supposerais pas qu'il existe un indice de "stabilité" global, car il ne serait pas inadmissible et serait trop enclin à s'effondrer sous un ensemble infiniment grand de conditions. Fondamentalement, est approprié lorsque les paramètres df et / ou # sont si grands que davantage de données d'apprentissage sont nécessaires. Le biais sera également plus grand pour , car davantage de données sont utilisées, et la variance serait artificiellement nulle, car les jeux de données d'apprentissage sont trop similaires les uns aux autres. Vous apprendrez également plus de bruit dans les données lorsque . k=nk=nk=n

LREG en tant que classificateur fonctionnerait lorsque les données seraient séparables linéairement, mais en moyenne, son biais serait trop élevé, car de nombreux jeux de données ne sont pas séparables linéairement.

Existe-t-il une façon intuitive de penser à cette stabilité?

Pas à mon avis - puisqu'il n'y a pas de règle générale sur la stabilité.

Quels sont d'autres exemples de modèles / algorithmes ou d'ensembles de données stables et instables?

C’est une question ouverte et trop large, puisqu’un nombre infiniment grand de réponses peut être mis en place, ce qui ne serait pas utile.

Est-il relativement sûr de supposer que la plupart des modèles / algorithmes ou jeux de données sont "stables" et que, par conséquent, devrait généralement être choisi aussi haut que possible du point de vue des calculs?K

Ne vous fiez qu'à suppose que vous croyez les données. Un exemple est Random Forests, pour lequel il n'y a vraiment pas de . Bien qu'environ 37% des données soient utilisées pour les tests (en moyenne, 37% des objets ne sont pas sélectionnés lors de l'échantillonnage avec remplacement), il existe par exemple 5 000 jeux de données différents (bootstraps), chacun étant divisé en formation / test de manière différente. Votre exemple tiré d’exposés supposait que chaque jeu de données utilisé constituait une véritable réalisation des données - ce qui est une hypothèse erronée. kk

Étant donné l'amorce, la règle de stabilité entourant est admissible, car l'échantillon de données utilisé pour une approche de CV simple impliquant n'est pas une vraie réalisation de l'univers de toutes les données à partir desquelles l'échantillon a été obtenu. kk

JoleT
la source
Merci pour vos commentaires, mais cela ne semble pas répondre à la question.
Jake Westfall
Voir la réponse jointe au PO.
JoleT
3
Ils ont seulement écrémé l'article, mais ils semblent vraiment prétendre que 10 fois mieux serait sur un terrain extrêmement fragile. Je ne peux pas croire que cela a 7k citations. Cela dit, il semble y avoir de bonnes raisons de croire que plus de 10 fois plus d’avantages. Fera une lecture plus approfondie quand j'ai une chance.
Cliff AB