pathsig: A GPU-Accelerated Library for Truncated and Projected Path Signatures

Le papier présente pathsig, une bibliothèque native PyTorch accélérée par GPU qui calcule efficacement des signatures de chemin tronquées et projetées, offrant des gains de vitesse significatifs et une gestion optimisée de la mémoire pour l'apprentissage à grande échelle.

L'essentiel

Imaginez que vous essayez de décrire le trajet d'une voiture qui a conduit toute la journée. Vous pourriez simplement dire "elle est allée du point A au point B", mais cela ne vous dit rien sur les virages serrés, les arrêts brusques ou les accélérations.

Pour comprendre vraiment un chemin (une séquence de données), les mathématiciens utilisent une méthode appelée "Signature de chemin". C'est comme un résumé ultra-détaillé et mathématique de tout le trajet, qui capture non seulement où la voiture est allée, mais aussi comment elle s'y est prise.

Le problème, c'est que calculer ce résumé est extrêmement lourd et lent, un peu comme essayer de dessiner chaque virage de la route avec un crayon à la main, point par point. C'est trop lent pour les ordinateurs modernes qui doivent traiter des millions de trajets en temps réel.

Voici ce que propose ce papier : pathsig.

1. Le Problème : Le Bouchon sur l'Autoroute

Les logiciels actuels pour calculer ces signatures sont comme des camions de déménagement qui traversent une ville en heure de pointe. Ils sont lourds, prennent beaucoup de place (mémoire) et vont lentement, surtout quand on essaie de les faire apprendre à des intelligences artificielles (ce qu'on appelle l'apprentissage par gradient).

2. La Solution : pathsig, le Super-Hélicoptère

L'auteur, Tobias Nygaard, a créé pathsig, une nouvelle boîte à outils qui fonctionne directement sur les puces graphiques (les GPU, comme ceux de votre carte graphique de jeu vidéo).

Au lieu de faire avancer les camions un par un, pathsig envoie une escouade d'hélicoptères qui travaillent tous en même temps.

• La métaphore du chantier : Imaginez que vous devez peindre un mur avec des motifs complexes. Les anciennes méthodes peignaient le motif entier, puis le suivant, puis le suivant. pathsig, lui, divise le mur en milliers de petits carrés et envoie un peintre (un processeur) pour chaque carré. Tout le mur est peint en un clin d'œil.
• Le résultat : C'est 10 à 30 fois plus rapide pour le calcul simple, et jusqu'à 50 fois plus rapide quand l'ordinateur doit apprendre et corriger ses erreurs (l'entraînement).

3. L'Innovation : Ne pas tout calculer (La Projection)

Une autre astuce géniale de pathsig est qu'il ne force pas à calculer tout le résumé.

• L'analogie du menu : Imaginez que vous commandez un repas. La méthode classique vous donne un menu complet avec 100 plats, même si vous ne voulez que 3. C'est du gaspillage.
• L'approche pathsig : Elle vous permet de dire : "Je ne veux que les plats avec du poisson et des légumes". Elle ne calcule que ce dont vous avez besoin.
• Pourquoi c'est utile ? Parfois, certaines parties du trajet sont très régulières et d'autres très chaotiques. pathsig peut ignorer les détails inutiles et se concentrer uniquement sur les parties importantes, ce qui rend le calcul encore plus léger et rapide.

4. La Preuve par l'Exemple : Le Détective de la Route

Pour prouver que leur méthode fonctionne, les auteurs ont fait un test : ils ont demandé à l'ordinateur de deviner le "style de conduite" (un paramètre mathématique appelé Hurst) d'une voiture qui roule de manière aléatoire.

• Ils ont comparé leur méthode "intelligente" (qui ne garde que les détails importants) avec la méthode classique (qui garde tout).
• Résultat : La méthode intelligente a été plus précise, plus rapide et a utilisé beaucoup moins de mémoire. C'est comme si un détective avait trouvé le coupable en examinant seulement 3 indices au lieu de 20, tout en étant plus sûr de son coup.

En Résumé

pathsig, c'est comme passer d'un vieux tracteur à une Formule 1 pour le calcul des signatures de chemin.

1. C'est rapide : Grâce aux puces graphiques (GPU).
2. C'est économe : Ça ne prend pas toute la mémoire de l'ordinateur.
3. C'est flexible : On peut demander à l'ordinateur de ne calculer que ce qui est vraiment utile, comme un menu à la carte.

C'est une avancée majeure pour permettre aux intelligences artificielles de mieux comprendre les données qui bougent dans le temps (comme les actions en bourse, les signaux médicaux ou la reconnaissance de la parole) sans faire planter les ordinateurs.

Résumé technique

Titre

pathsig : Une bibliothèque accélérée par GPU pour les signatures de chemins tronquées et projetées

1. Problématique

Les signatures de chemins (path signatures) sont des représentations riches et théoriquement garanties pour les données séquentielles, offrant une invariance par reparamétrisation temporelle et une robustesse face à un échantillonnage irrégulier. Bien que les méthodes basées sur les signatures aient évolué d'extracteurs de caractéristiques fixes vers des composants apprenables dans les modèles d'apprentissage automatique, leur adoption à grande échelle reste limitée par des contraintes de performance :

• Coût computationnel : Le calcul des signatures tronquées et la différenciation (rétropropagation) à travers elles sont coûteux, surtout pour des séquences longues ou des dimensions élevées.
• Limites des bibliothèques existantes : Les bibliothèques actuelles (comme iisignature, esig, Signatory, keras_sig) manquent souvent de scalabilité pour l'apprentissage basé sur le gradient à grande échelle. Elles peinent à exploiter efficacement le parallélisme des GPU ou consomment trop de mémoire, devenant un goulot d'étranglement lors de l'entraînement de modèles complexes.
• Rigidité des projections : L'approche standard consiste à tronquer la signature à une profondeur $N$ fixe, ce qui inclut souvent des termes redondants ou non pertinents, augmentant inutilement la dimensionnalité et le coût de calcul.

2. Méthodologie et Architecture

L'auteur propose pathsig, une bibliothèque native PyTorch conçue pour calculer les signatures de chemins directement dans la base des mots (word basis) en utilisant des noyaux CUDA optimisés.

A. Calcul sur des ensembles de mots préfixés (Prefix-Closed Sets)

Au lieu d'opérer sur l'algèbre tensorielle graduée traditionnelle, pathsig travaille directement sur les coefficients indexés par des mots.

• Décomposition : L'ensemble des mots est décomposé en ensembles préfixés (un ensemble de mots où tous les préfixes d'un mot sont également présents dans l'ensemble).
• Algorithme de mise à jour : Pour chaque mot, les coefficients de la signature sont mis à jour de manière indépendante en utilisant la relation de Chen et la méthode de Horner. Cela permet d'éviter la formation explicite des coefficients de l'exponentielle tensorielle, réduisant le nombre d'opérations flottantes intermédiaires et améliorant la stabilité numérique.
• Parallélisation GPU : Chaque thread CUDA est assigné à un ensemble préfixé généré par un seul mot. Cette granularité fine maximise la localité de la mémoire et assure un flux de contrôle uniforme, surpassant les assignations plus grossières (par blocs ou warps).

B. Rétropropagation (Backpropagation) efficace

Pour l'apprentissage profond, le calcul des gradients par rapport aux incréments du chemin est crucial.

• Reconstruction sans stockage : Au lieu de stocker toutes les signatures intermédiaires (ce qui coûterait une mémoire linéaire en fonction de la longueur de la séquence), pathsig reconstruit les valeurs nécessaires lors du passage arrière.
• Propriétés algébriques : En exploitant le fait que la signature est un élément de groupe (inversible), l'algorithme reconstruit les signatures partielles $S_{0, t_j}$ et $S_{t_j, T}$ en utilisant uniquement la signature finale et les incréments du chemin, via des récursions avant et arrière sur les préfixes et suffixes des mots.

C. Projections et Troncature Anisotrope

pathsig dépasse la simple troncature par profondeur $N$ :

• Projections sur des mots arbitraires : L'utilisateur peut spécifier n'importe quel ensemble fini de mots $I \subset W$. Cela permet de sélectionner uniquement les caractéristiques pertinentes, réduisant la dimensionnalité et la redondance.
• Signatures anisotropes : Au lieu de tronquer par la longueur du mot, on définit un degré pondéré $|w|_\gamma = \sum \gamma_i$. Cela permet de traiter différemment la régularité de différents canaux (variables) d'un chemin, offrant un compromis flexible entre la troncature complète et les projections arbitraires.

D. Fenêtrage (Windowing)

La bibliothèque supporte nativement le calcul de signatures sur des fenêtres glissantes ou expansives multiples en une seule invocation, introduisant une nouvelle dimension de parallélisme (au-delà des lots et des mots) pour saturer efficacement les GPU.

3. Résultats et Performances

Les benchmarks ont été réalisés sur un GPU NVIDIA H200 (140 Go de VRAM) en comparant pathsig avec keras_sig et pySigLib.

• Accélération (Speedup) :

  • Calcul de signature tronquée : pathsig est 10 à 30 fois plus rapide que les bibliothèques de référence pour le calcul direct.
  • Entraînement (Backpropagation) : Les gains atteignent 4 à 10 fois pour les tâches nécessitant la rétropropagation.
  • Signatures logarithmiques : Grâce à une projection alternative évitant la matérialisation de tous les coefficients, les gains peuvent atteindre jusqu'à 67x par rapport à pySigLib.
  • Calculs fenêtrés : Pour des configurations avec de nombreuses fenêtres, les accélérations vont de 3,9x à 6 380x, avec une médiane de 153x.

• Utilisation de la mémoire :

  • pathsig maintient une empreinte mémoire pic extrêmement faible, proche de 2x la mémoire nécessaire pour stocker uniquement la sortie de la signature.
  • Contrairement à keras_sig qui stocke toutes les signatures intermédiaires (complexité $O(B \cdot M \cdot D_{sig})$) et échoue souvent par manque de mémoire (OOM) sur des séquences longues, pathsig (complexité $O(B \cdot D_{sig})$) reste stable même pour des séquences très longues (ex: 1600 pas de temps).

• Cas d'usage (Lead-Lag) :
  Dans une expérience d'estimation du paramètre de Hurst d'un mouvement brownien fractionnaire multivarié, une projection de mots clairsemée (sparse word projection) basée sur la structure lead-lag a permis de réduire la dimensionnalité des caractéristiques par un facteur de 6,25 et le temps d'entraînement par 2,24, tout en obtenant une erreur de test inférieure à celle d'une troncature standard.

4. Contributions Clés

1. Implémentation GPU native : Une bibliothèque PyTorch entièrement optimisée pour le calcul et la différenciation des signatures de chemins, éliminant les goulots d'étranglement CPU/GPU.
2. Nouvelle approche algorithmique : L'utilisation de la base des mots et de la méthode de Horner sur des ensembles préfixés pour un calcul parallèle efficace et stable numériquement.
3. Flexibilité des projections : Support natif pour des projections arbitraires sur des ensembles de mots et des troncatures anisotropes, permettant des représentations plus compactes et adaptées au domaine.
4. Efficacité mémoire : Capacité à entraîner des modèles sur des séquences très longues sans stocker les états intermédiaires, rendant l'apprentissage profond par signatures viable à grande échelle.

5. Signification et Impact

Ce travail comble un fossé critique entre la théorie des signatures de chemins (théorie des chemins rugueux) et l'apprentissage automatique pratique à grande échelle. En rendant le calcul des signatures rapide, économe en mémoire et flexible, pathsig permet d'intégrer ces puissantes caractéristiques dans des architectures de deep learning modernes (RNN, Transformers, etc.) pour des applications telles que la finance quantitative, la reconnaissance de gestes, ou l'analyse de séries temporelles complexes. La capacité à projeter la signature sur des sous-ensembles de mots pertinents ouvre la voie à des modèles plus interprétables et plus efficaces, évitant la malédiction de la dimensionnalité inhérente aux troncatures classiques.

Le code source est disponible sous licence open-source et installable via pip, facilitant son adoption par la communauté.