8.3 Relative valuation
8.3.3 Summary of relative valuation
Sommaire
1 Introduction . . . 71
2 Travaux connexes . . . 73
3 Proposition : stockage des paramètres basé sur le count-sketch 75
4 Analyse de l’erreur du "count-sketch" et impact sur le di-
mensionnement . . . 76
5 Étude expérimentale . . . 80
6 Conclusion . . . 85
1
Introduction
Les caractéristiques des données multi-label de grande dimension confrontent l’ap- prentissage à un défi de gestion de la mémoire. La montée en puissance des supercal- culateurs permet d’affronter les changements d’échelle [208]. Cependant, leur utilisation est sévèrement limitée par l’accès technologique et les ressources financières, et de nom- breuses applications fonctionnent encore sur des ordinateurs standards. Et de plus en plus de nouvelles applications ciblent les appareils à ressources limitées tels que les smart- phones et les capteurs de l’Internet des Objets (IoT) [209, 210]. Dans ce contexte, les limitations sur la puissance de calcul allouée peuvent restreindre, voire empêcher, le dé- ploiement de certaines tâches d’apprentissage automatique. Par exemple, pour le jeu de données de référence Wiki10-31K [211] un modèle linéaire simple nécessite le stockage de d = dx× dy = 101938 × 30938 = 3.15 × 109 paramètres, ce qui représente environ 11.7 Go
de stockage de la plupart des ordinateurs ou des smartphones standards.
Cependant, plusieurs expériences numériques ont montré que seuls les plus grands paramètres des modèles d’apprentissage automatique sont réellement utiles pour faire des prédictions précises (voir Figure 4.1 et [212, 213]). Ces observations sont confirmées pour la régression linéaire par un résultat théorique classique [214] : un sous-ensemble limité de variables qui sont naturellement sélectionnées sous régularisation L0 [215] conduit au
risque de l’oracle et par conséquent aux meilleures garanties sur la qualité des prédictions. Mais en pratique, il est bien connu que la régularisation L0 n’est pas applicable pour des
raisons de stabilité/dérivabilité. Elle est souvent remplacée par les régularisations L1 et
L2 ou par une pénalisation de type seuillage dur [212]. Ces stratégies fournissent des
solutions parcimonieuses mais nécessitent le stockage en mémoire de tous les paramètres du modèle, et même de ceux qui sont petits ou nuls, pendant le processus d’optimisation.
0 0.2 0.4 0.6 0.8 1 Pe rfo rm anc es Bibtex
Percentage of deleted parameters
P@ 1 Test P@ 1 Train P@ 3 Test P@ 3 Train Corel5k Delicious 0 20 40 60 80 100 0 20 40 60 80 100 0 20 40 60 80 100
Figure 4.1 – Pour trois jeux de données classiques : évolution des performances du modèle des moindres carrés ordinaires lorsque ses paramètres les plus bas - en valeur absolue - sont progressivement supprimés. On peut noter que les performances sont maintenues avec une petite partie des plus grands paramètres.
Dans ce chapitre, nous proposons une nouvelle approche pour estimer avec précision les paramètres les plus importants tout en économisant de la mémoire. Cette approche peut être intégrée dans n’importe quel modèle qui est entraîné avec une technique basée sur la descente de gradient. Pendant le processus d’optimisation, la strategie proposée ne stocke en mémoire qu’une matrice de m << d valeurs à partir de laquelle il peut reconstruire les d paramètres d’origine du modèle et identifier les plus grands avec une bonne précision. Notre approche repose sur l’algorithme de "count-sketch" [216] qui appartient à la famille des méthodes d’identification des "heavy-hitters" [217]. Ces méthodes ont été développées à l’origine dans les moteurs de recherche et dans les boutiques en ligne pour déterminer les requêtes les plus fréquentes ou les produits les plus demandés sans avoir à stocker des compteurs de tous les éléments [218]. L’algorithme consiste à stocker de manière indépendante t (∼ 10) fois toutes les valeurs de paramètres sur différents ensembles de
r << d compteurs en agrégeant aléatoirement plusieurs valeurs dans les mêmes compteurs avec une fonction de hachage. L’approximation d’un paramètre donné est ensuite estimée par la médiane des valeurs stockées dans les t compteurs qui lui sont associés. La qualité de cette approximation s’avère bonne pour les plus grandes valeurs de paramètres.
Nous avons testé cette approche pour le cas populaire du problème de régression linéaire one-vs-rest résolu avec une descente de gradient stochastique [219]. Des expé- riences numériques sur neuf jeux de données de la littérature d’apprentissage multi-label avec diverses cardinalités de paramètres (de douze mille à trois milliards) confirment que la stratégie de stockage proposée mène à des performances identiques au modèle de base qui stocke toutes les valeurs des paramètres en mémoire alors qu’elle permet de réduire très significativement la consommation mémoire (de 80% à 99,9%). Nous avons également comparé notre approche à la stratégie de hachage des attributs [220] qui est l’alternative standard pour réduire la consommation de mémoire : nos performances sont meilleures (de 10% en moyenne et jusqu’à 50%) pour la même économie de mémoire. Nous complétons les résultats expérimentaux avec une borne théorique de l’erreur d’approximation rela- tive des paramètres et nous détaillons le cas particulier d’une distribution des paramètres suivant une loi de Zipf couramment observée.
Le reste du chapitre est organisé comme suit. La section 2 rappelle les travaux pré- cédents sur l’économie de mémoire. La section 3 détaille l’approche par "count-sketch" proposée. La section 4 montre les bornes théoriques de l’erreur d’approximation des paramètres et discute des hyperparamètres de notre proposition. La section 5 présente les comparaisons expérimentales.
2
Travaux connexes
Dans cette section, nous décrivons d’abord l’approche de hachage des attributs qui est le moyen standard pour limiter la consommation de mémoire en réduisant le nombre de paramètres des modèles d’apprentissage. Ensuite, nous présentons les principales mé- thodes d’identification des "heavy hitters" qui nous semblent pertinentes pour parvenir aux mêmes finalités mais qui ont été initialement développées dans la littérature sur l’analyse des flux.
2.1
Réduction de la consommation mémoire avec du hachage
d’attributs
Le nombre de paramètres d’un modèle d’apprentissage est généralement fonction du nombre d’attributs dans les données. Par conséquent, il peut être réduit en appliquant une réduction de dimension sur l’espace des attributs [221, 222]. On considère ici les
projections aléatoires car elles réduisent la dimension et n’entraînent pas de coût d’ap- prentissage supplémentaire.
L’une des stratégies de projection aléatoire les plus populaires est le hashing trick [220]. Il projette un vecteur d’attributs x ∈ Rdx en un vecteur d’attributs réduits x0 ∈ Rd0x avec
deux fonctions de hachage φ et s qui associent un index i ∈ {0, ..., dx−1} à respectivement
un autre index φ(i) ∈ {0, ..., d0x− 1} et un signe s(i) ∈ {−1, 1}. Le vecteur d’attributs réduits x0 est calculé comme suit :
1. x0 est initialisé avec des zéros.
2. ∀i ∈ {0, ..., dx− 1}, x0φ(i) = x0φ(i)+ s(i) × xi.
Ce type de projections aléatoires a été appliqué avec succès pour réduire la consom- mation de mémoire dans de nombreux modèles d’apprentissage ou de data mining [223] tels que l’algorithme de clustering k-means [224], les k plus proches voisins [225] ou les réseaux de neurones [226]. Elles peuvent cependant être limitantes en compressant trop les attributs ou en faisant l’approximation de rang faible.
2.2
Réduction de la consommation mémoire avec des méthodes
d’identification de "heavy-hitters" dans des flux
Pour dépasser les limites des méthodes de réduction de dimension, nous souhaitons développer dans ce chapitre une approche qui ne réduit pas les données initiales avant apprentissage. Cependant, sans réduire les données, le modèle peut avoir un très grand nombre de paramètres donc notre proposition a pour but d’estimer uniquement les plus grands paramètres -qui sont les plus utiles pour les prédictions- sans avoir à tous les sto- cker en mémoire. Ce problème est proche d’un problème rencontré dans l’analyse des flux dans lequel on considère un très grand nombre de compteurs mis à jour progressivement par un flux d’incréments et où le but est d’estimer les "heavy-hitters" qui sont les plus grands. Le scénario d’utilisation le plus courant consiste à déterminer les requêtes les plus fréquentes dans les moteurs de recherche.
Les méthodes d’identification des "heavy-hitters" développées dans la littérature sur l’analyse des flux peuvent être organisées en trois familles principales : [227] : (i) les méthodes basées sur des compteurs, (ii) les méthodes basées sur les quantiles et (iii) les méthodes basées sur les "sketchs". Les méthodes basées sur les "sketchs" se sont révélées être les plus efficaces et les plus polyvalentes [227]. Elles utilisent des fonctions de hachage pour projeter un grand ensemble de valeurs p dans un plus petit M qui permet d’estimer avec précision les "heavy-hitters" de p. Dans le scenario le plus courant, les composants de p, qui sont les compteurs associés à chaque requête, sont incrémentés de un à chaque événement du flux. Des généralisations ont été proposées pour des mises à jour avec des valeurs réelles et, dans ce cas, les méthodes basées sur les "sketchs" les plus utilisées
sont le "count-min-sketch" [217] et le "count-sketch" [216]. Cependant, le "count-min- sketch" est un modèle de type tourniquet strict qui ne traite que des problèmes pour lesquels la somme des mises à jour d’un compteur reste positive à tout instant. Par conséquent, nous considérons ici la stratégie de "count-sketch" qui convient le mieux pour l’apprentissage d’un modèle d’apprentissage automatique dont les paramètres sont habituellement a priori non contraints à être positifs.