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

Dit paper introduceert pathsig, een GPU-versnelde PyTorch-bibliotheek die pad-sigaturen efficiënt berekent en projecteert, waardoor trainingshastigheden met 10-30x toenemen en de geheugenefficiëntie voor grootschalig machine learning wordt geoptimaliseerd.

De kern

Stel je voor dat je een lange, chaotische reis door een stad moet beschrijven. Je hebt een kaart met straten (de data), maar de route is niet lineair; je slaat af, komt terug, loopt in cirkels en maakt snelle bochten. Hoe vertaal je die complexe, kronkelige reis naar een simpele lijst met getallen die een computer kan begrijpen?

In de wereld van kunstmatige intelligentie (AI) gebruiken wetenschappers iets dat "Path Signatures" (pad-kenmerken) noemen. Het is als een magische vingerafdruk voor een reis. Deze vingerafdruk onthoudt niet alleen waar je bent geweest, maar ook in welke volgorde je dingen hebt gedaan en hoe je hebt bewogen. Dit is ontzettend krachtig voor AI, maar tot nu toe was het berekenen van deze vingerafdrukken voor lange reizen erg traag en duur voor computers.

Hier komt pathsig om de hoek kijken. Het is een nieuwe, supersnelle tool die deze berekeningen op moderne grafische kaarten (GPUs) uitvoert.

Hier is een uitleg in simpele taal, met een paar creatieve vergelijkingen:

1. Het Probleem: De "Rekenmachine" die te traag is

Stel je voor dat je een gigantische bibliotheek hebt met boeken over elke mogelijke route die iemand ooit heeft gelopen. Om een AI te leren deze routes te begrijpen, moet je voor elke route een heel specifiek, complex getal berekenen (de signature).

• De oude manier: Het was alsof je deze berekeningen één voor één deed met een potlood en papier. Zelfs de snelste computers (de "rekenmachines" van de vorige generatie) kwamen hier niet meer mee op gang als je duizenden routes tegelijk wilde analyseren. Ze werden overbelast en traag.
• Het gevolg: Mensen konden deze krachtige techniek niet gebruiken voor grote, echte projecten zoals het voorspellen van beurskoersen of het analyseren van medische data in real-time.

2. De Oplossing: Een Super-Factory op een Chip

De auteur, Tobias Nygaard, heeft pathsig gebouwd. Denk hierbij niet aan een enkele rekenaar, maar aan een gigantische fabriek op een chip (de GPU).

• De Analogie: Stel je voor dat je 10.000 pakketjes moet sorteren.
  • De oude methode: Eén persoon loopt langs de band, pakt één pakketje, schrijft er een label op, en legt het neer. Dan het volgende.
  • De pathsig-methode: Je hebt een fabriek met 10.000 robots die allemaal tegelijk aan hun eigen pakketje werken. Ze werken niet alleen sneller, maar ze zijn ook slim ingericht zodat ze niet in de weg lopen van elkaar.
• Het resultaat: pathsig is 10 tot 30 keer sneller dan de beste bestaande tools. Het kan duizenden reizen tegelijk "lezen" zonder dat de computer in de war raakt.

3. Slimme Strategieën: "Knipt en Plakt" in plaats van "Alles Opslaan"

Een groot probleem bij het berekenen van deze vingerafdrukken is het geheugen. Normaal gesproken moet je elke tussenstap van de reis onthouden om terug te kunnen rekenen (voor het leren van de AI).

• De Analogie: Stel je voor dat je een lange film moet analyseren. De oude methoden hielden elke frame van de film in hun geheugen vast, waardoor hun hersenen (het geheugen) volliepen.
• De pathsig-methode: pathsig is slim genoeg om de film te analyseren zonder alles op te slaan. Het gebruikt een slimme wiskundige truc (Chen's relatie) om te zeggen: "Ik hoef niet de hele film te zien, ik kan de eindstand berekenen door alleen te kijken naar de laatste scène en de vorige scène."
• Het voordeel: Het gebruikt veel minder geheugen. Je kunt dus veel langere reizen analyseren zonder dat je computer vastloopt.

4. De "Maatwerk" Lens: Niet alles is even belangrijk

Soms wil je niet de volledige vingerafdruk van een reis, maar alleen de interessante delen.

• De Analogie: Stel je voor dat je een foto van een drukke markt maakt. Je wilt misschien alleen de mensen in rode kleding zien, of alleen de kinderen. Je wilt niet de hele foto in detail analyseren als dat niet nodig is.
• De pathsig-methode: pathsig laat je kiezen welke delen van de reis belangrijk zijn. Je kunt zeggen: "Ik wil alleen kijken naar de bochten die naar links gaan" of "Ik wil alleen kijken naar de snelle bewegingen". Dit heet een projectie.
• Waarom is dit cool? Het maakt de data veel compacter. In plaats van een zee van getallen, krijg je een kleine, krachtige set getallen die precies datgene vertelt wat je nodig hebt. In een test met het voorspellen van de snelheid van een wiskundig proces (Hurst-parameter) bleek deze "smalle" versie zelfs beter te presteren dan de "brede" versie, omdat hij minder ruis bevatte.

5. Waarom is dit belangrijk voor de toekomst?

Dit klinkt misschien als pure wiskunde, maar het heeft grote gevolgen:

• Financiële wereld: Het kan helpen om complexe beurspatronen sneller te herkennen.
• Medische wereld: Het kan artsen helpen om de beweging van een patiënt (bijvoorbeeld bij Parkinson) nauwkeuriger te analyseren.
• Robotica: Robots kunnen hun bewegingen sneller leren optimaliseren.

Samenvattend:
pathsig is als het geven van een supersnelheidsbril aan AI-modellen. Het maakt het mogelijk om complexe, kronkelige data (zoals tijdreeksen) te begrijpen, niet door alles langzaam en zwaar te berekenen, maar door slim, parallel en op maat gemaakte berekeningen te doen. Het maakt een krachtige wiskundige techniek eindelijk bruikbaar voor de grote, snelle wereld van vandaag.

Technische samenvatting

Probleemstelling

Pad-ondertekeningen (path signatures) zijn een krachtige wiskundige methode voor het vertegenwoordigen van sequentiële data, gebaseerd op iteratieve integralen. Ze bieden sterke theoretische garanties, zoals universele benadering en invariantie onder tijdsreparametrisatie. Hoewel deze methoden zijn geëvolueerd van vaste kenmerkextractoren naar trainbare componenten in machine learning-modellen, ontbreekt het bestaande softwarebibliotheken vaak aan de schaalbaarheid die nodig is voor grootschalig, op gradiënten gebaseerd leren.

De huidige uitdagingen zijn:

1. Schaalbaarheid: Bestaande bibliotheken (zoals iisignature, esig, Signatory) zijn vaak niet geoptimaliseerd voor GPU's of gebruiken CPU-gebaseerde backends die de GPU niet volledig benutten.
2. Geheugenefficiëntie: Het berekenen van terugwaartse propagatie (backpropagation) door de ondertekening vereist vaak het opslaan van tussenresultaten, wat leidt tot lineaire geheugenschaalbaarheid met de tijdstap, wat snel onhoudbaar wordt.
3. Rigiditeit: De meeste methoden zijn beperkt tot "truncation" (afkappen op een vaste diepte $N$), wat leidt tot redundante kenmerken en hoge dimensionale kosten, zelfs wanneer alleen een subset van de coëfficiënten nodig is voor een specifieke taak.

Methodologie

Het paper introduceert pathsig, een PyTorch-native bibliotheek die ondertekeningen direct berekent in de "woordbasis" (word basis) van de tensoralgebra, met gebruikmaking van CUDA-kernen voor parallelle verwerking.

Kernmethodologische innovaties:

1. Berekening in de Woordbasis met Horner's Methode:

   • In plaats van te werken met gelaagde tensoroperaties, werkt pathsig direct met woorden (sequenties van indexen).
   • Het deconstrueert de berekening in prefix-gesloten verzamelingen van woorden. Voor een woord $w$ worden alleen de coëfficiënten van $w$ en zijn eigen prefixen bijgewerkt.
   • Het gebruikt Horner's methode om de som van prefix- en suffix-termen efficiënt te evalueren zonder expliciet de coëfficiënten van de tensor-exponentiële functie te hoeven vormen. Dit vermindert het aantal drijvende-kommabewerkingen en vermindert afrondingsfouten.

2. GPU-Parallelisatie Strategie:

   • Elke CUDA-thread krijgt een prefix-gesloten verzameling van woorden toegewezen (gegenereerd door één enkel woord).
   • Deze granulariteit zorgt voor optimale geheugenlokaaliteit en uniforme controleflow, wat beter presteert dan grovere toewijzingen op het niveau van warps of blocks.

3. Efficiënte Backpropagation (Gradiënten):

   • Om het geheugengebruik te minimaliseren, slaat pathsig tijdens de forward-pass alleen de eind-ondertekening op.
   • Tijdens de backward-pass worden de vereiste tussenliggende waarden (prefixen en suffixen) reconstrueerd via algebraïsche eigenschappen van de ondertekening (Chen's relatie en de inverse van de tijdsomgekeerde weg).
   • Dit elimineert de noodzaak om $O(M \cdot D)$ geheugen te gebruiken (waarbij $M$ het aantal tijdstappen en $D$ de dimensie is), waardoor het geheugengebruik drastisch daalt.

4. Flexibele Projecties:

   • Woordprojecties: Het is mogelijk om de ondertekening te projecteren op een willekeurige, door de gebruiker gespecificeerde verzameling woorden, in plaats van een vaste diepte-truncatie. Dit maakt "sparsification" mogelijk.
   • Anisotrope Truncatie: In plaats van een uniforme diepte voor alle kanalen, kunnen gewichten per kanaal worden toegepast. Woorden met een "gewogen graad" onder een bepaalde drempel worden behouden. Dit is nuttig voor paden met inhomogene regulariteit over verschillende kanalen.

5. Vensterberekening (Windows):

   • De bibliotheek ondersteunt het berekenen van ondertekeningen over meerdere, door de gebruiker gespecificeerde tijdsvensters in één enkele GPU-call, wat de vaste overhead verlaagt en extra parallelisme introduceert.

Belangrijkste Bijdragen

• pathsig Library: Een open-source, pip-installabele PyTorch-pakket dat ondertekeningen en log-ondertekeningen (in de Lyndon-basis) berekent met hoge snelheid op GPU's.
• Geheugenoptimalisatie: Een algoritme voor backpropagation dat het geheugengebruik reduceert tot ongeveer $2\times$ de grootte van de output, in plaats van lineair te schalen met de sequentielengte.
• Generalisatie: Ondersteuning voor willekeurige projecties op woordverzamelingen en anisotrope truncatie, wat leidt tot compactere representaties.
• Log-Signature Ondersteuning: Efficiënte berekening van log-ondertekeningen zonder alle coëfficiënten tot de maximale diepte te hoeven materialiseren.

Resultaten

De prestaties zijn getest op een NVIDIA H200 GPU en vergeleken met keras_sig en pySigLib.

• Snelheid:

  • Forward Pass: pathsig is 10–30x sneller dan bestaande bibliotheken voor het berekenen van afgeknipte ondertekeningen.
  • Training (Forward + Backward): pathsig toont snelheidswinsten van 4–10x (en tot 40x in specifieke configuraties) ten opzichte van concurrenten.
  • Log-Signatures: Voor log-ondertekeningen zijn de snelheidswinsten zelfs groter (tot 60-70x sneller dan pySigLib), voornamelijk door de vermijding van het materialiseren van alle coëfficiënten.
  • Vensters: Voor vensterberekeningen worden snelheidswinsten van 3.9x tot 6380x waargenomen, met een mediaan van 153x.

• Geheugengebruik:

  • pathsig heeft een extreem laag piekgeheugengebruik. Waar keras_sig vaak uitvalt met "Out of Memory" (OOM) fouten bij lange sequenties of grote batches, blijft pathsig stabiel.
  • De geheugenreductie ten opzichte van keras_sig loopt op tot 1265x in bepaalde configuraties.

• Toepassing (Lead-Lag Voorbeeld):

  • In een experiment voor het schatten van de Hurst-parameter van fractionele Brownse beweging, bleek een "sparse word projection" (die alleen relevante interacties behield) niet alleen 6.25x minder kenmerken te hebben, maar ook een 2.24x snellere trainingstijd en een lagere testfout te leveren vergeleken met een volledige truncatie.

Betekenis

Dit paper is significant omdat het de praktische toepasbaarheid van pad-ondertekeningen in moderne deep learning-pipelines mogelijk maakt. Door de berekeningskosten en het geheugengebruik drastisch te verlagen, opent pathsig de deur voor:

1. Grootschalige toepassing: Het gebruik van ondertekeningen in grote datasets en complexe modellen die voorheen onbereikbaar waren door computatiekosten.
2. Efficiënter Leren: De mogelijkheid om gradiënten efficiënt door de ondertekening te sturen, maakt het mogelijk om de ondertekening zelf te trainen of te fine-tunen.
3. Slimme Feature Selectie: De ondersteuning voor willekeurige projecties en anisotrope truncatie stelt onderzoekers in staat om domeinkennis (zoals causale relaties tussen kanalen) direct in de feature-extractie te integreren, wat leidt tot compactere en performantere modellen.

Kortom, pathsig transformeert pad-ondertekeningen van een theoretisch krachtig maar computationeel zwaar concept naar een praktische, schaalbare tool voor state-of-the-art machine learning.