Comment prouver formellement que l'erreur OOB dans une forêt aléatoire n'est pas biaisée?

8

J'ai lu cette déclaration plusieurs fois mais je n'ai jamais trouvé de preuve. Je voudrais essayer d'en produire un moi-même mais je ne sais même pas quelle notation utiliser. Est-ce que quelqu'un peut m'aider avec ça?

mathematical-statistics random-forest unbiased-estimator proof JEquihua
la source
1
OOB n'est pas sans parti pris. La seule - souvent: la plus importante - composante du biais qui est supprimé par OOB est «l'optimisme» dont souffre un ajustement dans l'échantillon. Par exemple, OOB est biaisé de façon pessimiste en ce qu'il est basé sur les prévisions moyennes de seulement≈36.8%d'arbres dans la forêt. EDIT: comme indiqué dans la réponse de @cbeleites ci-dessous.
Jim

Réponses:

4

Je ne sais pas si c'est la réponse finale, mais ces choses ne peuvent pas correspondre à un commentaire.

La déclaration selon laquelle les erreurs OOB ne sont pas biaisées est souvent utilisée, mais je n'ai jamais vu de démonstration. Après de nombreuses recherches, j'ai finalement donné après avoir lu attentivement la page bien connue de Breiman pour la section RF : L'estimation d'erreur hors du sac (oob) . Au cas où vous ne l'auriez pas remarqué (comme je l'ai raté pendant un certain temps), la dernière proposition est la plus importante: celle- ci s'est avérée impartiale dans de nombreux tests . Donc, aucun signe de dérivation formelle.

Plus que cela, il semble être prouvé que dans le cas où vous avez plus de variables que d'instances, cet estimateur est biaisé. Voyez ici .

Pour l'erreur dans le sac, il existe une dérivation formelle. L'erreur dans le sac est l'erreur de bootstrap et il y a beaucoup de littérature commençant par "An Introduction to the Bootsrap, par Efron et Tibshirani". Cependant, la démonstration la plus propre que j'ai vue est ici .

Si vous voulez commencer à trouver une preuve, je pense qu'un bon point de départ est la comparaison de cette estimation avec une validation croisée N fois. En ESTL , il y a une identité dans la limite, car le nombre d'échantillons va à l'infini.

rapaio
la source
1
J'ai jeté un rapide coup d'œil au journal Mitchell, et jusqu'à présent je ne l'aime pas particulièrement (je pense n≪pest en quelque sorte une coïncidence: même les forêts aléatoires ne sont pas une solution miracle contre trop peu de cas. À un moment donné, leurs performances tombent également en panne et je suppose que c'est la cause sous-jacente des observations rapportées). Cependant, les observations d'un biais pessimiste ne m'étonnent pas, voir ma réponse. En fait, je pense que les réflexions que j'expose dans ma réponse peuvent offrir une explication conceptuellement assez simple de ce qui se passe là-bas.
cbeleites mécontents de SX
3

Pourquoi vous attendez-vous à ce que l'erreur oob soit impartiale?

  • Il y a (au moins) 1 cas de formation de moins disponible pour les arbres utilisés dans la forêt de substitution par rapport à la forêt "d'origine". Je m'attendrais à ce que cela conduise à un petit biais pessimiste à peu près comparable à la validation croisée avec omission.

  • Il y a à peu près 1e≈13du nombre d'arbres de la forêt "d'origine" dans la forêt de substitution qui est effectivement évalué avec le cas laissé de côté. Ainsi, je m'attendrais à une variance plus élevée dans la prédiction, ce qui entraînera un biais pessimiste supplémentaire.

Les deux réflexions sont étroitement liées à la courbe d'apprentissage du classificateur et de l'application / des données en question: la première à la performance moyenne en fonction de la taille de l'échantillon d'apprentissage et la seconde à la variance autour de cette courbe moyenne.

Dans l'ensemble, je m'attends à ce que vous puissiez tout au plus montrer formellement que oob est un estimateur non biaisé des performances des forêts aléatoires contenant 1e≈13 du nombre d’arbres de la forêt «originelle» et d’être formés sur n−1 cas des données de formation originales.

Notez également que Breiman utilise «impartial» pour le bootstrap de la même manière qu'il l'utilise pour la validation croisée, où nous avons également un (petit) biais pessimiste. Venant d'un domaine expérimental, je suis d'accord pour dire que les deux sont pratiquement impartiaux car le biais est généralement beaucoup moins problématique que la variance (vous n'utilisez probablement pas de forêts aléatoires si vous avez le luxe d'avoir beaucoup de cas) .

cbeleites mécontents de SX
la source
3
Je ne m'attendais pas à ce que ce soit. Il est mentionné par des gens à de nombreux endroits, donc je l'ai juste accepté. Maintenant que j'y pense, c'est pourquoi je voulais le prouver. J'aime votre réponse, laissez-moi jouer un peu avec vos informations pour voir ce que je peux conclure.
JEquihua
@JEquihua: Je serais certainement intéressé par le résultat.
cbeleites mécontents de SX
1
La forêt d'oob représente environ 1/3 de celle d'origine, pas 2/3 (donc plus de raisons pour que l'erreur d'oob soit pessimiste!). La probabilité de cueillir un arbre donné T pour la forêt d'oob d'une observation donnée (x, y) est la probabilité que (x, y) ne soit pas dans T, c'est-à-dire ((N-1) / N) ^ N = ( 1 + (-1) / N) ^ N -> exp (-1) = ~ 1/3. Ainsi, la taille attendue de la forêt d'oob pour (x, y) est d'environ B / 3, si B est la taille de la forêt d'origine.
memeplex
@memeplex: bien sûr - merci pour le repérage. A corrigé.
cbeleites mécontents de SX