6.3 Liquidity and solvency analysis
6.3.1 Liquidity analysis
Sur les données extrêmes, certains chercheurs ont tenté d’apprendre sans réduire la di- mension ni partitionner récursivement le problème. Les modèles considérés associent donc directement un très grand nombre d’attributs à un très grand nombre de labels. Comme expliqué dans le chapitre précédent, peu de modèles ("baseline labels fréquents", "baye- sien naif") sont capables de le faire sur des ordinateurs standards mais ils n’obtiennent pas de bonnes performances prédictives. Au lieu d’appliquer ces modèles simples, certains choisissent plutôt d’apprendre des modèles très complexes (mémoire et temps) pour les dimensions XML en recourant à des stratégies d’accélération des calculs comme la pa- rallélisation sur des supercalculateurs ou à des astuces d’optimisation. Par exemple, les approches de type one-vs-rest (aussi appelé one-vs-all) ne passent pas à l’échelle en XML car elles consistent à apprendre un modèle par label. Mais, en parallélisant l’apprentissage sur un millier de machines, des chercheurs sont parvenus à évaluer un one-vs-rest SVM regularisé avec la norme L1 sur le jeu de données Wiki-LSHTC [42]. Les résultats sont bons mais l’approche est difficilement exploitable dans de nombreuses applications car elle nécessite des moyens de calculs importants.
Pour des raisons de moyens de calculs nécessaires, peu d’approches de la littérature ont exploré à ce jour des solutions de ce type pour atteindre des performances compétitives. A notre connaissance, il en existe trois seulement : PD-Sparse, PPD-Sparse et DISMEC. PD-Sparse - Primal-Dual Sparse PD-Sparse apprend un modèle linéaire (y = Wb Tx)
parcimonieux (W creux) dont l’objectif est, pour chaque instance (xi, yi), que le score dans
b
yiassocié aux labels présents dans yi soit plus grand avec une marge que le score des labels
absents ("separation Ranking Loss" [161]) : min
W L(ybi, yi) = minW j∈N (ymaxi),k∈P(yi)
(1 +ycij −ycik)+ (2.17)
où P(yi) (resp. N (yi)) désigne l’ensemble des indices des labels présents (resp. absents)
dans yi. PD-Sparse résoud le problème régularisé avec Elastic Net [137].
Résolu avec une approche standard (gradient stochastique), un tel modèle est trop complexe (mémoire/temps) pour passer à l’échelle. Pour accélérer les calculs, le problème est converti dans une version duale où les variables duales sont les prédictions, les variables primales étant les paramètres de la projection. De plus, une stratégie de sélection de labels "actifs" permet d’éviter de calculer le gradient complet et de faire de lourdes mises à jour à chaque itération. Enfin, pour optimiser la mémoire et les calculs, des régularisations permettent de rendre les paramètres parcimonieux dans l’espace dual et dans l’espace primal. Puisqu’ils restent parcimonieux tout au long de l’apprentissage, seuls les paramètres non nuls sont stockés en mémoire grâce à des tables de hashage efficaces. La résolution s’effectue une approche FBCFW (Fully Corrective Block Coordinate Frank Wolfe) [162].
DiSMEC - Distributed Sparse Machines for Extreme Multi-label Classifica- tion DisMEC apprend un modèle séparateur linéaire avec marge wj pour chaque label
j ∈ {1, ..., dy} dont l’objectif est d’avoir wTjxi ≥ 1 si yij = 1 (label présent) et wTjxi ≤ −1
si yij = 0 (label absent). Avec une régularisation en norme L2, le problème se formule
comme suit : min wj kwjk22+ C n X i=1 max(0, 1 − yij × wjTxi)2 (2.18)
Ce problème est résolu par une méthode de Newton à région de confiance [141]. L’implémentation des auteurs est doublement parallélisée : le problème est découpé par paquets de 1000 labels et les modèles associés à ces 1000 labels sont appris en parallèle sur des machines de 32/64 coeurs. Les modèles wj sont finalement rendus parcimonieux
en appliquant un seuillage dur (à 0.01). Cela permet d’avoir un modèle beaucoup moins coûteux en mémoire, plus rapide pour effectuer des prédictions, et plus robuste.
PPDSparse - Parallel Primal-Dual Sparse PPDSparse a été proposé par les mêmes auteurs que PDSparse suite au constat que la fonction de coût du précédent classifieur est non séparable par rapport aux labels. Effectivement, elle dépend du score de tous les labels à la fois et cela a deux inconvénients majeurs : pas de possibilité de parallélisation et coût en mémoire du modèle trop élevé.
Une fonction de coût plus simple suivant la stratégie "1-vs-all" comme dans DISMEC permet non seulement d’avoir de très bonnes performances mais est également paralléli- sable. Dans PPDSparse, les auteurs choisissent donc d’optimiser cette fonction de coût (voir (2.18)) et de démontrer les mêmes propriétés de parcimonie duale et primale qu’ils avaient dans PD-Sparse. Les sous-modèles associés à chaque label peuvent être appris en parallèle et similairement à PDSparse, une sélection des instances actives permet d’accé- lérer encore la résolution. Parallélisé sur 100 coeurs, ce modèle est nettement plus rapide que PD-Sparse et DISMEC.
5
Conclusion
Dans un contexte où l’apprentissage multi-label suscite une attention croissante, les chercheurs tentent de répondre aux besoins actuels en matière de traitement de données de grande dimension. Nous avons présenté et structuré les trois solutions de la littérature : ré- duction de dimension, méthodes arborescentes, astuces d’optimisation/d’implémentation. Réduction de dimension Pour faire face à la complexité des problèmes, un grand nombre de méthodes de réduction de dimension multi-label ont été publiées au cours des dernières décennies. Ces publications enrichissent grandement la littérature mais il reste difficile de les comparer, de choisir la plus pertinente pour le problème à résoudre et de déterminer le travail qu’il reste à faire dans le domaine. Notre analyse tente de fournir ces éléments. Nous avons proposé une vue d’ensemble des méthodes à travers une typologie unificatrice pour démêler les liens entre les différentes méthodes. Elle repose sur trois critères majeurs. Le premier critère est l’espace que les méthodes réduisent (espace des attributs, espace des labels ou les deux). Les approches de réduction de l’espace des at- tributs sont répandues pour le moment mais avec l’intérêt croissant pour l’apprentissage multi-label extrême, les méthodes qui réduisent également la dimension de l’espace des labels sont en plein essor. Le deuxième critère distingue les méthodes qui réduisent un espace en tenant compte des informations portées par l’autre de celles qui effectuent la réduction de manière indépendante. Contrairement à il y a quelques années, les méthodes dépendantes prédominent aujourd’hui : en préservant les liens entre les attributs et les labels, elles sont plus efficaces pour la tâche d’apprentissage. Le troisième critère est la pré- sence/absence d’un couplage entre le classifieur et la stratégie de réduction de dimension. Aujourd’hui, les deux scénarios sont très déséquilibrés et la grande majorité des approches
ne sont pas couplées au classifieur. Outre ces aspects structurants majeurs, les méthodes diffèrent pour deux composants supplémentaires : le type de transformation (implicite, ex- plicite, linéaire, non linéaire) qu’elles effectuent et les contraintes/régularisations qu’elles imposent à la résolution du problème. Bien que ces différences ne distinguent pas les ap- proches par leur nature même, elles peuvent avoir un impact important sur leur efficacité et leur capacité de déploiement dans des applications réelles.
Méthodes arborescentes Nous avons présenté deux types de méthodes arborescentes. Celles qui construisent des arbres d’instances et celles qui construisent des arbres de la- bels. De façon générale, ces méthodes découpent récursivement l’ensemble des labels (resp. des instances) pour maximiser un objectif donné. Les méthodes hiérarchiques ont de nombreux avantages pour la tâche d’apprentissage multi-label extrême : opérations dé- composées en sous-tâches simples et rapides, prédiction en temps logarithmique, parallé- lisation facile, décisions récursives permettant une grande expressivité. Mais elles peuvent néanmoins présenter quelques défauts. Le partitionnement limite de façon définitive la qualité d’un classifieur local au sein d’un sous-ensemble. Et, puisque le partitionnement est hiérarchique, une erreur dans les premières étapes peut fortement pénaliser la qualité de l’algorithme. En revanche, des solutions existent pour limiter ce problème comme la déclinaison de l’arbre en forêt (aléatoire ou non) ou l’application de pondérations dans les noeuds selon leur qualité prédictive sur un ensemble de validation.
Astuces d’optimisation/d’implémentation Cette troisième stratégie est la moins répandue. Plutôt que de réduire la dimension ou de découper récursivement le problème, ces méthodes utilisent d’autres astuces pour passer à l’échelle. Les astuces sont la parallé- lisation sur des supercalculateurs, la conversion primal/dual du problème d’optimisation ou les régularisations permettant d’assurer un modèle creux. Même si ces approches sont difficilement exploitables dans de nombreuses applications car elles nécessitent des moyens de calculs importants, elle permettent d’obtenir des performances prédictives intéressantes et de mettre au défi les autres types de solutions.