AdaBoost est-il moins ou plus sujet au sur-ajustement?

20

J'ai lu diverses déclarations (apparemment) contradictoires, que AdaBoost (ou d'autres techniques de boosting) soient ou non sujettes à un sur-ajustement par rapport à d'autres méthodes d'apprentissage.

Y a-t-il de bonnes raisons de croire l'un ou l'autre? Si cela dépend, de quoi dépend-il? Quelles sont les raisons pour lesquelles AdaBoost est moins / plus enclin à sur-équiper?

blubb
la source
1
Mon intuition est qu'elle est plus sujette au sur-ajustement qu'une forêt aléatoire. Cependant, l'algorithme est conçu pour éviter le sur-ajustement, et il ne semble généralement pas être un problème. Je n'ai aucune référence pour sauvegarder cela, mais vous pouvez utiliser le caretpackage pour effectuer une validation croisée adaboost, et j'ai trouvé qu'il se généralise généralement bien.
Zach

Réponses:

17

Comme vous le dites, beaucoup de choses ont été discutées à ce sujet, et il y a une théorie assez lourde qui va avec et que je dois admettre que je n'ai jamais complètement comprise. Dans mon expérience pratique, AdaBoost est assez robuste au sur-ajustement, et LPBoost (Linear Programming Boosting) encore plus (car la fonction objectif nécessite une combinaison clairsemée d'apprenants faibles, qui est une forme de contrôle de la capacité). Les principaux facteurs qui l'influencent sont:

  • La «force» des apprenants «faibles»: si vous utilisez des apprenants faibles très simples, comme les souches de décision (arbres de décision à 1 niveau), les algorithmes sont beaucoup moins sujets au surapprentissage. Chaque fois que j'ai essayé d'utiliser des apprenants faibles plus compliqués (tels que des arbres de décision ou même des hyperplans), j'ai constaté que le surapprentissage se produit beaucoup plus rapidement

  • Le niveau de bruit dans les données: AdaBoost est particulièrement enclin à sur-ajuster les jeux de données bruyants. Dans ce cadre, les formulaires régularisés (RegBoost, AdaBoostReg, LPBoost, QPBoost) sont préférables

  • La dimensionnalité des données: Nous savons qu'en général, nous avons davantage de surapprentissage dans les espaces de grande dimension ("la malédiction de la dimensionnalité"), et AdaBoost peut également souffrir à cet égard, car il s'agit simplement d'une combinaison linéaire de classificateurs qui eux-mêmes souffrent du problème. Il est difficile de déterminer s'il est aussi sujet que d'autres classificateurs.

k

tdc
la source
9

Je suis d'accord avec la plupart des points mentionnés dans les commentaires de tdc. cependant, je dois ajouter et corriger peu de choses.

  • Comme le montre L2Boost de Peter Bühlmann, à mesure que le nombre d'apprenants faibles (cycles de boosting) augmente, le biais converge exponentiellement rapidement tandis que la variance augmente de magnitudes géométriquement décroissantes, ce qui signifie: il s'adapte beaucoup plus lentement que la plupart des autres méthodes.
  • Il a été mentionné à tort dans le commentaire de Zach qu'il vaut mieux que la forêt aléatoire en termes de surcapacité. C'est complètement faux. En fait, selon la théorie (regardez le papier original sur les forêts aléatoires de Breiman), Random Forest est absolument immunisé contre le surajustement tant que ses classificateurs faibles ne sont pas trop adaptés aux données.
  • Contrairement à ce qui est mentionné dans le commentaire tdc, la plupart des méthodes de boosting sont très sensibles au bruit d'étiquetage et peuvent facilement s'adapter en présence de bruit d'étiquetage.
  • Dans les ensembles de données où les taux d'erreur de Bayes sont loin de 0 (c'est-à-dire que les caractéristiques ne sont pas suffisamment discriminantes), les méthodes de boosting peuvent également facilement s'adapter. Parce qu'ils essaient de réduire l'erreur d'apprentissage à zéro alors qu'en réalité même le classificateur optimal, c'est-à-dire que le classificateur Bayes peut atteindre un taux d'erreur de 40%, disons.
  • enfin, et cela n'a été publié nulle part (à ma connaissance) il y a une sorte de sur-ajustement dans lequel l'erreur de généralisation n'augmente pas à mesure que les rounds de boost augmentent mais ne diminue pas non plus. Cela signifie que l'algorithme est coincé dans un optima local. Dans cette situation, l'erreur d'apprentissage diminue constamment tandis que l'erreur de test reste presque constante. Jusqu'à présent, nous n'avons jamais considéré ce phénomène comme une indication de surapprentissage, mais je pense que c'est un signe de surapprentissage et en utilisant des apprenants faibles plus complexes, (étrange!), Nous pouvons en fait aller contre (ce dernier point doit être considéré avec prudence :RÉ)
TNM
la source
1
Il vaut la peine d'ajouter à cette réponse que j'aurais peut-être connu ce dernier type de sur-ajustement aujourd'hui, avec AdaBoost et Random Forest. En validation croisée, l'erreur hors pli a convergé vers une constante avec seulement 20 estimateurs de base, puis a rebondi autour de cette constante avec une variance élevée. Ma suspicion était exactement la même: les algorithmes gourmands se sont coincés dans une sorte d'optimum local. Ce n'est pas une confirmation de ce qui s'est passé, mais c'est agréable de savoir que quelqu'un d'autre a eu la même pensée.
shadowtalker
@ssdecontrol Pouvez-vous partager ce que vous avez fait? Je veux reproduire les résultats pour avoir une meilleure compréhension
saurabh agarwal
@saurabhagarwal Je pense que je travaillais sur le projet Kaggle Titanic
shadowtalker