Boosting et ensachage des arbres (XGBoost, LightGBM)

17

Il existe de nombreux articles de blog, vidéos YouTube, etc. sur les idées d' ensachage ou de renforcement des arbres. Ma compréhension générale est que le pseudo-code pour chacun est:

Ensachage:

  1. Prélever N échantillons aléatoires de x% des échantillons et y% des fonctionnalités
  2. Ajustez votre modèle (par exemple, arbre de décision) sur chacun des N
  3. Prédire avec chaque N
  4. Moyenne des prédictions pour obtenir la prédiction finale

Boosting:

  1. Adapter votre modèle (par exemple, arbre de décision) à vos données
  2. Obtenez les résidus
  3. Ajustez votre modèle aux résidus
  4. Passez à 2 pour N rounds de boost
  5. La prédiction finale est une somme pondérée des prédicteurs séquentiels.

Je vais apporter des clarifications à ma compréhension ci-dessus, mais ma question est la suivante:

Les deux XGBoost et LightGBM ont des paramètres qui permettent l'ensachage. L'application n'est pas Bagging OR Boosting (ce dont parlent tous les articles de blog), mais Bagging AND Boosting. Quel est le pseudo-code pour savoir où et quand l'ensachage et le boosting combinés ont lieu?

Je m'attendais à ce qu'il s'agisse de "Boosted Boosted Trees", mais il semble que ce soit "Boosted Bagged Trees". La différence semble substantielle.

Arbres boostés en sac:

  1. Prélever N échantillons aléatoires de x% des échantillons et y% des fonctionnalités
  2. Ajuster les arbres boostés sur chacun des N échantillons
  3. Prédire avec chaque N
  4. Moyenne des prédictions pour obtenir la prédiction finale

Cela semble être la meilleure façon de procéder. Après tout, le risque de suralimentation est le sur-ajustement et le principal avantage de l'ensachage est de réduire le sur-ajustement; ensacher un tas de modèles boostés semble être une excellente idée.

Cependant, en parcourant, par exemple le scikit-learn gradient_boosting.py (qui fait un échantillonnage d'ensachage, mais pas la sélection de fonctionnalités aléatoires), et en bricolant quelques petits pépites à travers les publications sur LightGBM et XGBoost, il semble que XGBoost et LightGBM fonctionnent comme suit:

Arbres en sac boostés:

  1. Adapter un arbre de décision à vos données
  2. Pour les tours de boost i in N:
    • Obtenez les résidus
    • si je modifie bag_frequency == 0 (c.-à-d., sac tous les 5 tours):
      • Prélevez un seul échantillon aléatoire de x% des échantillons et y% des caractéristiques; utiliser cet échantillon aléatoire à l'avenir
    • adapter l'arbre aux résidus
  3. La prédiction finale est une somme pondérée des prédicteurs séquentiels.

Veuillez corriger ma compréhension ici et remplir les détails. Boosted Bagged Tree (avec seulement 1 arbre aléatoire par bag_frequency) ne semble pas aussi puissant que Bagged Boosted Tree.

Jonathan
la source
2
+1 pour une question intéressante et très bien formulée. Et bienvenue sur le site.
mkt - Réintégrer Monica
vous avez besoin d'un "calcul de l'erreur" pour votre boost. Fait mal qui s'effondre. Les poids sont essentiels pour adaboost. Ce n'est pas un résidu brut. ... Nous ne parlons pas du gradient stochastique comme nécessaire dans le boost, bien qu'il accélère les choses.
EngrStudent
Voici le boosted-bagged. Au lieu d'un nouvel arbre pour chaque étape de la série, vous obtenez une nouvelle forêt avec une sortie moyenne. Eugene Tuv et Kari Torkkola. jmlr.org/papers/volume10/tuv09a/tuv09a.pdf
Reinstate Monica
le boosté en sac va faire une forêt d'ensembles de séries, et prendre la sortie moyenne. Cela pourrait engager le sur-ajustement qu'un ensemble en série (boosté) peut faire et donner une sortie plus robuste, mais le gain ne sera pas énorme.
EngrStudent

Réponses:

13

Ensachage: prenez N échantillons aléatoires de x% des échantillons et y% des caractéristiques

Les instances sont sous-échantillonnées à plusieurs reprises dans Bagging , mais pas dans les fonctionnalités. ( RandomForests , XGBoost et CatBoost font les deux):

Given dataset D of size N.
For m in n_models:
    Create new dataset D_i of size N by sampling with replacement from D.
    Train model on D_i (and then predict)
Combine predictions with equal weight 

Incluez une étape d'initialisation dans votre pseudo-code Boosting pour vous débarrasser de la redondance:

Init data with equal weights (1/N).
For m in n_model:
    Train model on weighted data (and then predict)
    Update weights according to misclassification rate.
    Renormalize weights
Combine confidence weighted predictions

Bagged Boosted Trees (comme vous l'appelez) est certainement une approche raisonnable, mais différente de XGBoost ou CatBoost :

Given dataset D of size N.
For m in n_models:
    Create new dataset D_i of size N by sampling with replacement from D.
    (Insert Boosting pseudo code here (on D_i))
Combine predictions with equal weight 

XGBoost et CatBoost sont tous deux basés sur Boosting et utilisent l'intégralité des données d'entraînement. Ils implémentent également l'ensachage par sous-échantillonnage une fois à chaque itération de boosting:

Init data with equal weights (1/N).
For m in n_model:
    Train model on weighted bootstrap sample (and then predict)
    Update weights according to misclassification rate.
    Renormalize weights
Combine confidence weighted predictions

Si vous voulez vous en tenir à "ajuster le modèle aux résidus", cela équivaudrait à "ajuster le modèle aux résidus de données dans l' échantillon de bootstrap ".


Remarques supplémentaires :

Il n'y a pas de " meilleure façon de le faire " comme vous le suggérez (pas de théorème du déjeuner gratuit). "Bagged Boosted Trees" pourrait surpasser XGBoost sur certains ensembles de données.

Prélever un seul échantillon aléatoire de x% des échantillons

Cette ligne prête à confusion. D'où tenez-vous cela?

si je modifie bag_frequency == 0 (c'est-à-dire, sac tous les 5 tours):

Cela ne doit pas être mentionné dans votre pseudo-code. Surtout quand il reste d'autres paramètres plus importants (comme le taux d'apprentissage en boosting).

Laksan Nathan
la source
(+1) Belle réponse! Pour clarifier: l'OP est-il incorrect en déclarant que " XGBoost et LightGBM ont des paramètres qui permettent l'ensachage "?
mkt
Les deux permettent l'ensachage: bagging_fraction dans LightGBM et sous - échantillon dans XGBoost . Je ne sais pas pourquoi j'ai fait référence à CatBoost tout le temps. Mais ils fonctionnent tous de la même manière en ce qui concerne la question.
Laksan Nathan
Mon erreur, j'ai raté la ligne dans votre réponse qui le mentionne. Pourriez-vous expliquer "le sous-échantillonnage une fois à chaque itération de boosting "? Voulez-vous dire que dans chaque itération de boosting, de nombreux sous-échantillons sont pris, les arbres sont adaptés à chaque sous-échantillon, puis le taux de classification erronée est calculé sur la base des arbres ensachés, et enfin les poids mis à jour? Si oui, pourriez-vous clarifier cela dans votre pseudocode?
mkt
Pas beaucoup de sous-échantillons sont dessinés, un seul: au lieu d'adapter le modèle à toutes les instances pondérées, le modèle est formé sur un échantillon bootstrap.
Laksan Nathan
Concernant "Prélever un seul échantillon aléatoire de x% des échantillons"; mieux serait de "prendre un seul échantillon de x% des lignes". Je l'ai eu d' ici .
Jonathan