Taille de l'arbre dans le boosting d'arbre dégradé

10

L'amplification des arbres à gradient comme proposé par Friedman utilise des arbres de décision avec Jdes nœuds terminaux (= feuilles) comme apprenants de base. Il existe un certain nombre de façons de faire pousser un arbre avec exactement des Jnœuds, par exemple, on peut faire pousser l'arbre en premier lieu en profondeur ou en premier en largeur, ...

Existe-t-il un moyen établi de faire pousser des arbres avec Jdes nœuds exactement terminaux pour augmenter le gradient d'arbres?

J'ai examiné la procédure d'arborescence du gbmpackage de R et il semble qu'il développe l'arbre en profondeur et utilise une heuristique basée sur l'amélioration des erreurs pour choisir d'étendre le nœud enfant gauche ou droit - est-ce correct?

r cart boosting Peter Prettenhofer
la source
2
gbm utilise CART pour construire les arbres, un algorithme bien connu des années 80. L'heuristique est appelée impureté gini, un choix assez standard pour la régression avec perte quadratique.
2
L'impureté Afaik gini est utilisée pour les problèmes de classification. Néanmoins, la question se réfère à la taille des arbres.
Peter Prettenhofer
Il ajoute une branche à la fois. Je serais surpris si chaque prochaine scission est la meilleure des candidats scindés restants dans l'arbre, pas seulement la branche. Il y a des moments où les données ne prennent pas en charge un nombre exact - comme lorsque les données sont trop petites pour «J».
EngrStudent
Comme l'a dit @EngrStudent, vous ne pouvez pas forcer un nombre précis de nœuds. Cependant, vous avez un certain contrôle sur une limite supérieure du nombre de nœuds. gbma un paramètre n.minobsinnodequi contrôle le nombre minimum d'objets par nœud. Bien sûr, alors le nombre de nœuds est inférieur ou égal à NumberOfPoints / n.minobsinnode
G5W
Si je cherchais des feuilles «J», je construirais entièrement l'arbre, puis, en supposant qu'il y aurait plus de feuilles J, je taillerais en J. Cela me donnerait des nœuds «J», et ce seraient les plus fractionnements informatifs - ce serait le modèle CART le plus sain qu'il pourrait être. S'il n'y a pas assez de divisions, je pourrais simplement me répartir au hasard dans les domaines pour obtenir «J», mais ils seraient faux et quelque peu triviaux. Je pourrais examiner la distribution des valeurs au sein de la feuille et utiliser une aproximation basée sur le CDF, mais cela s'écarterait du modèle moyenne par feuille.
EngrStudent

Réponses:

2

La solution dans les R gbmn'est pas typique.

D'autres paquets, comme scikit-learnou LightGBMutilisent ce qu'on appelle (dans scikit-learn) BestFirstTreeBuilder, lorsque le nombre de feuilles est restreint. Il prend en charge une file d'attente prioritaire de toutes les feuilles et à chaque itération divise la feuille qui apporte la meilleure diminution d'impureté. Ce n'est donc ni la profondeur d'abord ni la largeur d'abord, mais un troisième algorithme, basé sur des calculs dans les feuilles.

Dans un certain sens, cette approche est plus optimale que de diviser aveuglément toutes les feuilles à son tour. Cependant, c'est toujours une heuristique gourmande, car le choix de diviser le ième nœud dépend maintenant uniquement de la première division de et non des éventuelles divisions successives qui peuvent diminuer l'impureté beaucoup plus que la division actuelle.ii

David Dale
la source