Le hachage de caractéristiques, également connu sous le nom d'astuce de hachage, est une technique en apprentissage automatique qui consiste à convertir des caractéristiques catégorielles éparses et de haute dimension en une représentation vectorielle compacte de taille fixe. Elle applique une fonction de hachage à chaque nom de caractéristique (ou jeton) pour déterminer son index dans le vecteur de sortie, et éventuellement une seconde fonction de hachage pour déterminer le signe de la contribution. Cette méthode évite de maintenir un dictionnaire de caractéristiques séparé, réduisant ainsi la mémoire et les frais de calcul, au prix de l'introduction de collisions de hachage qui peuvent légèrement dégrader les performances du modèle.
La technique est particulièrement utile pour les tâches d'apprentissage à grande échelle, telles que la publicité en ligne, la classification de textes et les systèmes de recommandation, où le nombre de caractéristiques uniques peut atteindre des millions ou des milliards. En mappant les caractéristiques dans un espace de, disons, 10 000 à 1 million de dimensions, le hachage de caractéristiques permet un entraînement efficace avec des modèles linéaires ou des réseaux de neurones, souvent avec une perte de précision négligeable.
Histoire et origines
Le concept du hachage de caractéristiques trouve ses racines au début des années 2000, avec des développements indépendants dans le traitement du langage naturel et les méthodes à noyau. L'une des premières utilisations publiées fut celle de John Langford et ses collègues en 2007, qui l'ont appliqué à l'apprentissage à grande échelle pour la détection de spam. La technique a gagné une reconnaissance plus large après l'article de 2009 « Feature Hashing for Large Scale Multitask Learning » de Kilian Weinberger et ses collègues, qui a formalisé l'approche et démontré son efficacité sur plusieurs tâches.
Avant cela, des idées similaires sont apparues dans le contexte du hachage pour les approximations de noyaux, comme les travaux sur les caractéristiques aléatoires d'Ali Rahimi et Benjamin Recht en 2007. Le hachage de caractéristiques est également étroitement lié à l'« astuce de hachage » utilisée dans le système d'apprentissage Vowpal Wabbit, développé par Langford chez Yahoo! Research.
Comment cela fonctionne
Le hachage de caractéristiques fonctionne en deux étapes principales. D'abord, chaque nom de caractéristique (par exemple, un mot ou une valeur catégorielle) est passé à travers une fonction de hachage, généralement un hachage de 32 ou 64 bits, pour produire un entier. Cet entier est ensuite réduit modulo la dimension de sortie souhaitée, donnant l'index où la valeur de la caractéristique (souvent 1 pour la présence) est accumulée. Pour réduire le biais dû aux collisions, une seconde fonction de hachage détermine le signe (+1 ou -1) de la contribution, de sorte que les collisions tendent à s'annuler en moyenne.
Par exemple, dans la classification de textes, chaque mot d'un document est haché vers un index dans un vecteur de taille, disons, 100 000. Le vecteur est ensuite utilisé comme entrée pour un classifieur linéaire ou un réseau de neurones. Parce que la fonction de hachage est déterministe, la même caractéristique mappe toujours au même index, assurant la cohérence entre l'entraînement et l'inférence.
Le principal avantage est qu'aucun dictionnaire de caractéristiques n'a besoin d'être stocké, ce qui est crucial lorsque l'espace de caractéristiques est trop grand pour tenir en mémoire. Cependant, des collisions peuvent se produire, où différentes caractéristiques mappent au même index, provoquant potentiellement des interférences. L'impact est généralement faible si la dimension de sortie est suffisamment grande par rapport au nombre de caractéristiques.
Applications en apprentissage automatique
Le hachage de caractéristiques est largement utilisé dans les systèmes d'apprentissage automatique à grande échelle, en particulier dans le contexte de l'apprentissage en ligne et du calcul distribué. C'est un composant central de la bibliothèque Vowpal Wabbit, utilisée pour la prédiction du taux de clic dans la publicité. Il est également employé dans le traitement du langage naturel pour les représentations sac-de-mots, où chaque document est converti en un vecteur haché, permettant un entraînement efficace de classifieurs sur des corpus de textes massifs.
Dans les systèmes de recommandation, le hachage de caractéristiques peut encoder les identifiants d'utilisateurs et d'articles, ainsi que les caractéristiques contextuelles, en une représentation compacte, permettant aux modèles de gérer des millions d'utilisateurs et d'articles sans tables de correspondance explicites. Il est également utilisé dans l'ingénierie de caractéristiques pour les machines à gradient boosting, telles que XGBoost et LightGBM, où les caractéristiques catégorielles sont souvent hachées pour réduire l'utilisation de la mémoire.
Plus récemment, le hachage de caractéristiques a été appliqué dans l'apprentissage profond pour les couches d'incorporation, où il peut servir d'alternative de taille fixe aux incorporations apprises, en particulier pour les catégories rares ou invisibles. Cette approche est parfois appelée « incorporations par hachage » et peut être bénéfique dans les scénarios d'apprentissage en ligne où de nouvelles caractéristiques apparaissent fréquemment.
Avantages et limites
Le principal avantage du hachage de caractéristiques est l'efficacité mémoire. Comme aucun dictionnaire n'est requis, le modèle peut être entraîné sur des données avec un nombre illimité de caractéristiques, tant que la dimension de sortie du hachage est fixe. Cela est particulièrement utile dans les contextes de streaming ou distribués, où les caractéristiques peuvent être découvertes à la volée.
Un autre avantage est la simplicité : l'implémentation est directe et ne nécessite pas de prétraitement complexe. Cela permet également un parallélisme facile, car chaque caractéristique peut être hachée indépendamment.
Cependant, le hachage de caractéristiques a des limites. Les collisions de hachage peuvent dégrader la précision du modèle, surtout lorsque la dimension de sortie est trop petite. La technique perd également en interprétabilité, car il n'est pas possible de mapper un index haché vers le nom de caractéristique original sans stocker un mappage séparé, ce qui va à l'encontre du but. De plus, le choix de la fonction de hachage et de la dimension de sortie nécessite un réglage, et il y a un compromis entre le taux de collision et l'utilisation de la mémoire.
Comparaison avec les méthodes alternatives
Le hachage de caractéristiques est souvent comparé à d'autres techniques de réduction de dimensionnalité, telles que l'encodage one-hot, l'encodage par étiquettes et les incorporations apprises. L'encodage one-hot est simple mais nécessite un dictionnaire et peut être extrêmement gourmand en mémoire pour les caractéristiques à haute cardinalité. L'encodage par étiquettes attribue des identifiants entiers mais impose un ordre arbitraire, ce qui peut être trompeur pour les données catégorielles. Les incorporations apprises, comme celles utilisées dans les réseaux de neurones, peuvent capturer des relations sémantiques mais nécessitent un entraînement et un vocabulaire fixe.
Le hachage de caractéristiques se situe entre ces approches : il est plus efficace en mémoire que l'encodage one-hot, évite le problème d'ordre de l'encodage par étiquettes, et ne nécessite ni entraînement ni vocabulaire. Cependant, il ne capture pas les relations entre les caractéristiques, ce que les incorporations peuvent faire.
En pratique, le hachage de caractéristiques est souvent utilisé comme référence ou comme solution de repli lorsque d'autres méthodes sont infaisables en raison de l'échelle. Il est également combiné avec d'autres techniques, telles que l'augmentation de données ou le pruning de modèles, pour améliorer l'efficacité dans les systèmes de production.
Développements récents et recherche
La recherche sur le hachage de caractéristiques se poursuit, en particulier dans le contexte de l'apprentissage profond et des systèmes à grande échelle. Des études ont analysé l'effet des collisions de hachage sur les performances du modèle, conduisant à des directives pour choisir la dimension de sortie. Certains travaux ont proposé des fonctions de hachage apprises qui s'adaptent à la distribution des données, réduisant potentiellement les collisions.
À l'ère des grands modèles de langage, le hachage de caractéristiques est moins proéminent car ces modèles utilisent généralement la tokenisation et des incorporations apprises. Cependant, il reste pertinent pour gérer les caractéristiques catégorielles dans les données tabulaires et pour l'ingénierie de caractéristiques efficace dans les pipelines de apprentissage automatique.
Des travaux récents ont également exploré l'utilisation du hachage de caractéristiques dans l'apprentissage fédéré et les contextes de préservation de la vie privée, où le hachage peut servir de forme d'obfuscation des caractéristiques. De plus, les accélérateurs matériels tels que AWS Trainium et Google Cloud TPU peuvent bénéficier de l'empreinte mémoire réduite que fournit le hachage de caractéristiques.
Dans l'ensemble, le hachage de caractéristiques est une technique mature qui continue de trouver de nouvelles applications dans les environnements à grande échelle et à ressources limitées.