sujets-avances-data – Introduction aux méthodes ensemblistes

1 Sujets avancés: traitement des données pendant l’entraînement

1.1 Le traitement des variables continues: l’utilisation des histogrammes

L’algorithme de détermination des critères de partition (split-finding algorithm) est un enjeu de performance essentiel dans les méthodes ensemblistes. En effet, l’algorithme le plus simple qui consiste à énumérer tous les critères de partition possibles (en balayant toutes les valeurs de toutes les variables) s’avère très coûteux à utiliser dès lors que les données contiennent soit un grand nombre de variables, soit des variables continues prenant un grand nombre de valeurs. C’est pourquoi cet algorithme a fait l’objet de multiples améliorations et optimisations visant à réduire leur coût computationnel sans dégrader la qualité des critères de partition.

L’utilisation d’histogrammes (histogram-based algorithms) est une approche efficace qui permet de réduire de manière significative le coût computationnel lié à la recherche des splits optimaux en discrétisant les variables continues. Elle est proposée par toutes les implémentations courantes du gradient boosting (XGBoost, LightGBM, CatBoost et scikit-learn), mais pas par les implémentations des forêts aléatoires (scikit-learn et ranger). Elle comprend deux caractéristiques principales:

Discrétisation: avant le début de l’entraînement, chaque variable continue est discrétisée en un nombre limité d’intervalles (bins), construits le plus souvent à partir de ses quantiles. Ce processus est appelé binning. Par exemple, une variable continue uniformément distribuée de 0 à 100 peut être divisée en dix intervalles (\([0, 10), [10, 20), \dots, [90, 100)\)). Le nombre maximal de bins est un hyperparamètre qui peut parfois jouer un rôle important.
Énumération restreinte: l’algorithme de détermination des critères de partition ne considère que les bornes des intervalles précédemment définies (10, 20, 30, etc. dans l’exemple précédent) et non l’ensemble des valeurs prises par les variables continues. Cette modification se traduit par une nette accélération de l’entraînement, dans la mesure où le nombre de bins est en général beaucoup plus faible que le nombre de valeurs uniques des variables continues¹. Elle est en revanche sans effet notable sur les performances prédictives dans la plupart des cas.

1.2 Le traitement des variables catégorielles

Le traitement des variables catégorielles est l’un des points les plus délicats et les plus complexes dans les méthodes ensemblistes. Cette section présente les approches possibles et récapitule quelles approches sont proposées par chaque implémentation.

1.2.1 Une diversité d’approches

A l’origine, les arbres CART ont été conçus pour partitionner l’espace en utilisant exclusivement des variables numériques, et ne pouvaient pas mobiliser les variables catégorielles sans un retraitement préalable. Plusieurs méthodes d’encodage (one-hot-encoding, ordinal encoding, target encoding) ont donc été développées pour surmonter ce problème en transformant les variables catégorielles en variables numériques; elles ne sont d’ailleurs pas spécifiques aux méthodes ensemblistes à base d’arbres. Depuis le milieu des années 2010, une nouvelle approche efficace et spécifique aux méthodes ensemblistes a été introduite dans les implémentations du gradient boosting (native support for categorical features). Ce paragraphe présente ces différentes approches des variables catégorielles, et précise quelle approche est proposée par les différentes implémentations.

Les trois approches d’encodage les plus courantes sont les suivantes:

Le one-hot encoding consiste à transformer une variable catégorielle en une série de variables binaires qui représentent chacune une modalité de la variable; pour chaque observation, seule la colonne correspondant à la modalité de la variable catégorielle aura la valeur 1, et toutes les autres auront la valeur 0. Cette approche permet de représenter des catégories de manière numérique de façon très simple et sans leur attribuer un ordre. Toutefois, le one-hot encoding augmente fortement la dimensionnalité des données (ce qui ralentit l’entraînement et augmente les besoins en mémoire), et est inutilisable lorsque les variables catégorielles présentent un nombre élevé de modalités².
L’ordinal encoding consiste à attribuer un entier unique à chaque modalité d’une variable catégorielle. Par exemple, la catégorie “Sans diplôme” sera encodée par la valeur 0, la catégorie “Baccalauréat ou moins” sera encodée par 1, etc. Simple à mettre en œuvre, cette approche permet de remplacer la variable catégorielle par une unique variable numérique et est donc utile pour traiter les variables présentant un grand nombre de modalités, pour lesquelles le one-hot encoding est impraticable. Elle est particulièrement adaptée aux variables catégorielles qui sont naturellement ordonnées (exemples: niveau de diplôme, catégorie d’âge, étage d’un appartement…). En revanche, cette approche est peu adaptée aux variables non ordonnées (exemples: secteur d’activité, département, pays…) car elle introduit un ordre fictif qui peut perturber les modèles qui interprètent les entiers comme des valeurs ordonnées.
Le target encoding consiste à remplacer chaque modalité d’une variable catégorielle par la moyenne de la variable cible pour cette modalité. Cette approche est notamment proposée par CatBoost³ et par scikit-learn⁴. Comme l’ordinal encoding, cette approche permet d’obtenir une unique variable numérique et est donc utile pour traiter les variables présentant un grand nombre de modalités. Par ailleurs, le target encoding fonctionne bien avec la méthode des histogrammes décrite précédemment, dans la mesure où les valeurs encodées sont par construction ordonnées en fonction de leur association avec la variable cible. Toutefois, il est important d’utiliser le target encoding en lissant la moyenne ou en recourant à une validation croisée car il est sujet au surapprentissage. De plus, les implémentations existantes réalisent l’encodage une seule fois avant l’entraînement au niveau de l’ensemble des données d’entraînement, pas au niveau de chaque split; l’ordre des modalités qui résulte de l’encodage peut être peu pertinent sur certaines parties des données d’entraînement si celles-ci présentent un haut degré d’hétérogénéité.

La dernière approche, appelée support natif des variables catégorielles (native support for categorical features) n’est pas un encodage et est une spécificité des implémentations du gradient boosting. Cette approche a été introduite par LightGBM, puis reprise par XGBoost et scikit-learn. Dans cette approche, l’objectif est de déterminer le meilleur split directement à partir des modalités d’une variable catégorielle, en les séparant en deux sous-ensembles (par exemple : {‘A’, ‘B’, ‘C’} et {‘D’, ‘E’, ‘F’} pour une variable comportant six modalités). La difficulté est qu’il est souvent impossible en pratique de trouver le partitionnement optimal par une énumération exhaustive des partitions possibles, car il existe \(2^{k-1} - 1\) partitions possibles pour une variable à \(k\) modalités. C’est pourquoi le support natif des variables catégorielles repose sur une méthode plus efficace dont l’optimalité a été démontrée par Fisher (1958): à chaque split, les modalités sont triées selon \(-\frac{\sum_{i} g_i}{\sum_{i} h_i}\) ⁵, puis le meilleur split est choisi en testant les différentes divisions possibles de cette liste triée. Par exemple, si pour un split donné les modalités sont triées dans l’ordre ABDFEC, l’algorithme examinera les \(k-1\) splits A|BDFEC, AB|DFEC, ABD|FEC, etc. Cette approche peut être considérée comme une variante optimisée du target encoding, avec deux différences notables: l’encodage des modalités se fait à partir du gradient et de la hessienne de la fonction de perte (et non à partir de \(y\)), et cet encodage a lieu à chaque split et non une fois pour toutes avant l’entraînement. Par ailleurs, cette approche peut rencontrer des difficultés quand les variables catégorielles comprennent un nombre très élevé des modalités (au-delà de quelques centaines).

1.2.2 Comparaison des différents approches

Déterminer quelle approche des variables catégorielles est adaptée dans une situation donnée n’est pas toujours aisé. Les cas d’usage des différentes approches peuvent être résumés comme ceci:

le one-hot-encoding est adapté uniquement aux variables catégorielles comprenant peu de modalités;
l’ordinal encoding est adapté aux variables catégorielles qui sont naturellement ordonnées, et ce quel que soit le nombre de modalités (car la variable catégorielle est implicitement convertie en variable numérique);
le target encoding est adapté aux variables catégorielles comprenant un grand nombre de modalités et non naturellement ordonnées;
le support natif des variables catégorielles est adapté à tous les types de variables catégorielles, à l’exception de celles qui comprennent un nombre très élevé des modalités (au-delà de quelques centaines).

Comparé aux autres approches, le support natif des variables catégorielles comporte plusieurs avantages: il permet de réduire le nombre de splits, d’obtenir des arbres plus simples et d’augmenter l’efficacité computationnelle de l’entraînement des arbres. Ces avantages apparaissent clairement avec un exemple⁶. Imaginons qu’on s’intéresse à une variable catégorielle prenant les modalités ABCDEF, et que sur une feuille donnée de l’arbre, le meilleur partitionnement sur cette variable soit ACF - BDE. Une approche de one-hot-encoding aura besoin de trois splits pour approximer ce partitionnement: un premier pour séparer A et BCDEF, un deuxième pour séparer C et BDEF et un troisième pour séparer F et BCDE (l’ordre des splits pouvant différer). Une approche d’ordinal encoding aura besoin de quatre splits: un split pour isoler A, un split pour isoler F, et deux splits pour isoler C (car C est au milieu de l’ordre des modalités). Enfin, une approche de target encoding aura besoin d’un nombre variable de splits, qui dépend de l’ordre des modalités dans l’encoding: si le target encoding a trié les modalités dans l’ordre ACFBDE, alors un unique split suffira; si l’ordre est très différent, alors il faudra davantage de splits. Inversement, le support natif des variables catégorielles identifiera immédiatement le partitionnement optimal, et ne fera qu’un seul split, ce qui simplifie la structure de l’arbre et accélère l’entraînement.

1.2.3 Approches intégrées aux implémentations des méthodes ensemblistes

Certaines implémentations des méthodes ensemblistes prennent en charge directement certaines des quatre approches présentées ci-dessus, auquel cas il est possible d’entraîner le modèle sur des données contenant des variables catégorielles sans preprocessing particulier; dans les autres cas, il faut préparer les données en amont de l’entraînement et de la prédiction, par exemple en utilisant un ColumnTransformer de scikit-learn (OneHotEncoder(), TargetEncoder(), OrdinalEncoder()). Le tableau et les notes ci-dessous résument quelles approches sont proposées par chaque implémentations des méthodes ensemblistes.

Table 1: Prise en charge des variables catégorielles dans les implémentations des méthodes ensemblistes

Approche	`ranger`	`scikit-learn`	`XGBoost`	`LightGBM`	`CatBoost`
One-hot-encoding
Ordinal encoding
Target encoding
Support natif des variables catégorielles

ranger: le traitement des variables catégorielles (factors) est contrôlé par l’argument respect.unordered.factors, qui peut prendre trois valeurs: ignore (ordinal encoding), order (target encoding) et partition (essayer toutes les combinaisons possibles). L’usage de cet argument est détaillé dans la documentation de la fonction ranger(). L’usage de la modalité partition n’est pas recommandé. En revanche, ranger ne prend pas en charge le one-hot-encoding.
LightGBM: cette implémentation utilise par défaut le one-hot-encoding pour les variables catégorielles comprenant 4 modalités ou moins, et le support natif des variables catégorielles pour les autres. Ce seuil peut être modifié via le paramètre max_cat_to_onehot. En revanche, LightGBM ne prend pas en charge ni l’ordinal encoding ni le target encoding.
XGBoost: le traitement des variables catégorielles est contrôlé par l’argument enable_categorical. Si enable_categorical = True (en Python), alors XGBoost applique le support natif des variables catégorielles. Par ailleurs, le paramètre max_cat_to_onehot permet d’utiliser le one-hot-encoding pour les variables catégorielles comprenant moins de max_cat_to_onehot modalités, et le support natif pour les autres (voir la documentation). En revanche, XGBoost ne prend pas en charge ni l’ordinal encoding ni le target encoding.
CatBoost: cette implémentation est celle qui propose le plus d’options relatives aux variables catégorielles. Par défaut, elle utilise le one-hot-encoding pour les variables catégorielles comprenant peu de modalités, et une variante de target encoding aux autres. Le seuil par défaut varie selon le type de tâche et peut être modifié via le paramètre one_hot_max_size. La documentation de CatBoost propose un notebook qui détaille les différents hyperparamètres.
scikit-learn: l’implémentation du gradient boosting (HistGradientBoostingClassifier, HistGradientBoostingRegressor) propose le support natif des variables catégorielles. Cette implémentation ne propose pas de one-hot-encoding pour les variables catégorielles comprenant peu de modalités, et ne prend pas en charge ni l’ordinal encoding ni le target encoding.

1.3 Le traitement des valeurs manquantes

Le traitement des valeurs manquantes dans les variables explicatives est un problème qui peut être traité à deux moments: soit de façon classique lors de la préparation des données (preprocessing), soit directement lors de l’entraînement des modèles, car toutes les implémentations de référence des méthodes ensemblistes proposent une prise en charge des valeurs manquantes au moment de l’entraînement. La première approche est décrite dans la section sur la préparation des données. Le paragraphe qui suit se concentre sur la seconde approche et s’attache à décrire en détail la méthode utilisée par chaque implémentation, car les documentations sont souvent incomplètes sur ce point.

XGBoost: le paramètre missing permet de préciser quelle valeur dans les données doit être considérée comme manquante (np.nan par défaut). Les valeurs manquantes sont traitées en modifiant légèrement l’algorithme de détermination des critères de partition, de façon à ce qu’il recherche à la fois le meilleur split et le meilleur noeud-enfant vers lequel envoyer les valeurs manquantes. Pour ce faire, le gain associé à chaque règle de décision candidate est calculé de deux façons différentes: en mettant les valeurs manquantes dans le noeud de droite, puis en les mettant dans le noeud de gauche. Le gain le plus élevé des deux indique dans quel noeud les valeurs manquantes doivent être envoyées, conditionnellement à la règle de décision candidate. Une fois que toutes les règles candidates ont été examinées, on obtient simultanément la meilleure règle de décision, et la meilleure façon de traiter les valeurs manquantes. Cette approche est systématiquement appliquée aux variables numériques, et aux variables catégorielles si le support natif des variables catégorielles est activé (enable_categorical = True, voir la section Section 1.2). Ceci dit, il arrive fréquemment que la règle de décision optimale pour un noeud repose sur une variable qui ne comprend aucune valeur manquante dans la population du noeud à partitionner; en ce cas les valeurs manquantes sont envoyées à droite par défaut⁷.
LightGBM: seules les valeurs na sont considérées comme manquantes; elles sont traitées selon une approche très similaire à celle d’XGBoost. Dans le cas des variables numériques, l’algorithme de détermination des critères de partition recherche à la fois le meilleur split et le meilleur noeud-enfant vers lequel envoyer les valeurs manquantes. Toutefois, lorsque la règle de décision optimale pour un noeud repose sur une variable qui ne comprend aucune valeur manquante dans la population du noeud à partitionner, toute valeur manquante rencontrée dans cette variable à l’étape de prédiction est convertie en 0, ce qui peut avoir des effets imprévisibles sur les prédictions⁸. Dans le cas des variables catégorielles, les valeurs manquantes sont systématiquement envoyées vers le noeud-enfant de droite.
ranger propose également une approche similaire à celle d’XGBoost, à une différence près: l’algorithme de détermination des critères de partition recherche d’abord uniquement le meilleur split, puis une fois celui-ci trouvé, détermine vers quel noeud-enfant il est préférable d’envoyer éventuelles les valeurs manquantes. S’il n’y en a pas, les valeurs manquantes rencontrées en prédiction seront envoyées au noeud-enfant de gauche.
scikit-learn propose également une approche similaire à celle d’XGBoost, à deux différences près: seules les valeurs np.nan sont considérées comme manquantes, et lorsqu’il n’y a pas de valeurs manquantes au moment de construire la règle de décision, les valeurs manquantes rencontrées en prédiction seront envoyées au noeud-enfant comprenant le plus d’observations⁹.
CatBoost: cette implémentation utilise une approche très simple pour les valeurs manquantes. S’agissant des variables numériques, l’algorithme remplace systématiquement les valeurs manquantes par une valeur soit extrêmement faible (inférieure à toutes les valeurs observées dans les données), soit extrêmement élevée (supérieure à toutes les valeurs observées), garantissant ainsi qu’elles seront toujours dirigées vers le noeud-enfant de gauche (respectivement vers le noeud-enfant de droite). Ce choix est contrôlé par l’hyperparamètre nan_mode. Pour les valeurs catégorielles, CatBoost traite les valeurs manquantes comme une catégorie distincte à part entière, en leur attribuant un encodage spécifique lors de la transformation ordonnée des variables catégorielles.

References

Fisher, Walter D. 1958. “On Grouping for Maximum Homogeneity.” Journal of the American Statistical Association 53 (284): 789–98.

Prokhorenkova, Liudmila, Gleb Gusev, Aleksandr Vorobev, Anna Veronika Dorogush, and Andrey Gulin. 2018. “CatBoost: Unbiased Boosting with Categorical Features.” Advances in Neural Information Processing Systems 31.

Footnotes

Voir cette page de la documentation de scikit-learn pour plus d’éléments.↩︎
Il est bien sûr possible de n’encoder que les modalités les plus fréquentes, et de regrouper toutes les autres dans une seule variable binaire.↩︎
Le target encoding utilisé par CatBoost est présenté en détail dans Prokhorenkova et al. (2018) et sur ce billet de blog.↩︎
Voir cet exemple dans la documentation de scikit-learn.↩︎
Il s’agit de l’équation donnant le poids optimal d’une feuille terminale, avec \(\lambda = 0\).↩︎
Cet exemple s’appuie sur la documentation de scikit-learn.↩︎
Voir ce post ↩︎
Voir cette issue. Ce comportement imprévisible peut aisément être résolu par une étape de preprocessing des variables numériques. Par exemple, le transformer MinMaxScaler de scikit-learnpermet de s’assurer que ces variables prennent des valeurs comprises entre 0 et 1, ce qui signifie que les valeurs manquantes seront toujours envoyées à gauche par défaut↩︎
Voir la documentation ↩︎