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

Das Paper stellt „pathsig" vor, eine PyTorch-native, GPU-beschleunigte Bibliothek, die durch parallele CUDA-Kernel und flexible Projektionsmechanismen die effiziente Berechnung und das Training von Pfad-Signaturen für skalierbares maschinelles Lernen ermöglicht.

Das Wesentliche

Stellen Sie sich vor, Sie versuchen, die Geschichte eines wandernden Wanderers zu erzählen. Der Wanderer hat einen Pfad zurückgelegt, der sich durch einen dichten Wald schlängelt. Ein einfacher Bericht wie „Er ging 10 Meter nach Norden" reicht nicht aus. Um die Geschichte wirklich zu verstehen, müssen Sie wissen: Wie hat er gewandert? Hat er sich langsam und gleichmäßig bewegt oder hastig und zitternd? Hat er sich im Kreis gedreht, bevor er geradeaus ging?

In der Welt der künstlichen Intelligenz (KI) nennt man diese detaillierte Pfadbeschreibung ein „Signature" (Unterschrift). Es ist eine mathematische Methode, um komplexe, zeitliche Daten (wie Aktienkurse, Sprachaufnahmen oder Sensordaten) in eine Form zu bringen, die Computer leicht verstehen und lernen können.

Das Problem bisher war jedoch: Diese Berechnungen waren extrem langsam und speicherintensiv, besonders wenn man sie auf riesigen Datenmengen trainieren wollte. Es war, als würde man versuchen, einen Ozean mit einem kleinen Eimer zu leeren.

Hier kommt pathsig ins Spiel.

Was ist pathsig? (Der Turbo für Daten)

pathsig ist eine neue Software-Bibliothek, die wie ein Supersportwagen für Datenverarbeitung funktioniert. Sie wurde speziell für moderne Grafikkarten (GPUs) entwickelt, die normalerweise für das Rendern von Videospielen genutzt werden, aber hier genutzt werden, um mathematische Berechnungen mit enormer Geschwindigkeit durchzuführen.

Stellen Sie sich die Berechnung einer Signatur wie das Zusammenbauen eines riesigen Lego-Modells vor:

• Die alten Methoden: Sie bauten das Modell Stein für Stein, in einer einzigen Reihe, und mussten dabei ständig den ganzen bisherigen Stapel im Kopf behalten. Das war mühsam und langsam.
• pathsig: Es organisiert Tausende von kleinen Baufirmen (die GPU-Kerne), die gleichzeitig an verschiedenen Teilen des Modells arbeiten. Es nutzt einen cleveren Trick, bei dem es nur die notwendigen Teile betrachtet und den Rest ignoriert. Das Ergebnis? Die Berechnung ist 10- bis 30-mal schneller als bei den bisherigen besten Methoden.

Die genialen Tricks im Detail

Hier sind die drei Haupt-Features von pathsig, erklärt mit einfachen Bildern:

1. Der „Präfix-Trick" (Effizientes Bauen)

Stellen Sie sich vor, Sie müssen alle möglichen Wörter aus Buchstaben bilden. Wenn Sie das Wort „Hund" bilden, müssen Sie auch „H", „Hu" und „Hun" kennen.
Frühere Bibliotheken haben oft alles auf einmal berechnet, was viel Speicherplatz verschwendete. pathsig ist wie ein kluger Handwerker: Es berechnet nur die Teile, die es wirklich braucht, und speichert sie so, dass der nächste Schritt sofort darauf aufbauen kann. Es nutzt die GPU so effizient, dass sie fast nie leerläuft.

2. Der „Fenster-Trick" (Mehrere Geschichten gleichzeitig)

Oft wollen wir nicht nur den gesamten Pfad eines Wanderers betrachten, sondern auch, was er in den letzten 10 Minuten getan hat, oder in den letzten 5 Minuten.
Früher musste man für jedes dieser Zeitfenster die Berechnung von vorne beginnen. pathsig kann jedoch alle Fenster gleichzeitig berechnen. Es ist, als würde man nicht einen, sondern Tausende von Wachposten haben, die gleichzeitig verschiedene Abschnitte des Pfades beobachten. Das macht die Analyse von Echtzeit-Daten (wie bei autonomen Autos) viel schneller.

3. Der „Schneidemeister" (Projektion und Reduktion)

Manchmal ist die vollständige Geschichte zu lang und zu kompliziert. Vielleicht interessiert uns nur, ob der Wanderer bergauf oder bergab ging, nicht aber, ob er einen Stein umgangen hat.
pathsig erlaubt es, die Signatur zu „projizieren". Das bedeutet, man kann dem Computer sagen: „Ignoriere alle komplizierten Details und konzentriere dich nur auf diese spezifischen Muster."

• Anisotrope Trunkierung: Stellen Sie sich vor, einige Sinne sind schärfer als andere. In manchen Datenströmen ist die Bewegung in einer Richtung sehr glatt, in einer anderen sehr ruckartig. pathsig kann die Berechnung so anpassen, dass es bei den glatten Teilen weniger Details speichert und bei den ruckartigen mehr. Das spart enorm viel Rechenleistung.

Ein echtes Beispiel: Die Vorhersage von Wetter oder Börsen

In dem Papier wird ein Experiment beschrieben, bei dem versucht wurde, das Verhalten von „fraktionaler Brownscher Bewegung" (eine Art mathematisches Rauschen, das in der Natur und Finanzwelt vorkommt) vorherzusagen.

• Das Problem: Die Daten waren chaotisch und voller Details.
• Die Lösung mit pathsig: Anstatt alle möglichen Kombinationen von Bewegungen zu berechnen (was wie das Durchsuchen eines riesigen Bibliotheksarchivs wäre), wählte pathsig nur die wichtigsten Buchstabenkombinationen aus.
• Das Ergebnis: Das Modell lernte schneller, machte weniger Fehler und benötigte dabei 2,24-mal weniger Zeit für das Training als mit herkömmlichen Methoden. Es war, als würde man einem Schüler nicht das ganze Lexikon geben, sondern nur die 100 wichtigsten Wörter, die er wirklich braucht, um eine Geschichte zu schreiben.

Warum ist das wichtig für uns?

pathsig macht es möglich, komplexe zeitliche Daten in Echtzeit zu analysieren.

• Für Ärzte: Schnellere Analyse von Herzfrequenzdaten, um Anomalien sofort zu erkennen.
• Für Finanzexperten: Bessere Vorhersagen von Aktienkursen, indem man Muster erkennt, die für das menschliche Auge unsichtbar sind.
• Für Roboter: Roboter können ihre Bewegungen und die Umgebung schneller verstehen und darauf reagieren.

Zusammenfassend:
pathsig ist der Turbo-Modus für die Analyse von Zeitreihen. Es nimmt die komplizierte Mathematik der „Pfad-Signaturen", packt sie in einen Hochleistungs-Container für Grafikkarten und erlaubt es uns, riesige Datenmengen in einem Bruchteil der bisherigen Zeit zu verstehen. Es ist nicht nur schneller; es ist schlauer, weil es weiß, welche Details wirklich zählen und welche man weglassen kann.

Technische Zusammenfassung

1. Problemstellung

Pfad-Signaturen (Path Signatures) sind ein mächtiges Werkzeug zur Darstellung sequenzieller Daten, das auf der Theorie der rauen Pfade (Rough Path Theory) basiert. Sie bieten eine universelle Approximationseigenschaft und sind robust gegenüber unregelmäßigen Abtastraten. In der Praxis werden jedoch unendlichdimensionale Signaturen durch endlichdimensionale, abgeschnittene (truncated) Versionen approximiert.

Das zentrale Problem besteht darin, dass bestehende Bibliotheken für die Berechnung und Differentiation von Pfad-Signaturen oft nicht die erforderliche Skalierbarkeit für groß angelegtes, gradientenbasiertes maschinelles Lernen bieten. Die Berechnung ist rechenintensiv, und der Speicherbedarf wächst oft linear mit der Sequenzlänge oder der Dimensionalität, was das Training auf GPUs ineffizient macht oder zu Speicherüberläufen (OOM) führt. Zudem fehlt es oft an Flexibilität bei der Auswahl der Merkmale (z. B. starre Tiefen-Abschnitte statt benutzerdefinierter Projektionen).

2. Methodik und Architektur

Die Autoren stellen pathsig vor, eine native PyTorch-Bibliothek, die Pfad-Signaturen direkt im Wort-Basis-System (word basis) berechnet und CUDA-Kernel für die Parallelisierung nutzt.

• Berechnung im Wort-Basis-System: Anstatt Operationen im Tensor-Algebra-Raum durchzuführen, arbeitet pathsig direkt mit den Koeffizienten, die durch Wörter (Folgen von Indizes) indiziert sind.
• Präfix-geschlossene Mengen (Prefix-Closed Sets): Die Kernidee ist die Zerlegung der Wortbasis in Mengen, die unter Präfixen abgeschlossen sind. Für jedes Wort $w$ werden die Signaturen-Koeffizienten unabhängig aktualisiert, wobei nur die Koeffizienten der eigenen Präfixe benötigt werden.
• CUDA-Optimierung: Jeder CUDA-Thread berechnet die Koeffizienten für eine solche präfix-geschlossene Menge (erzeugt von einem einzelnen Wort). Dies nutzt die Speicherlokalität optimal aus und vermeidet komplexe Synchronisationslogik auf Warp- oder Block-Ebene.
• Horner-Verfahren: Zur effizienten Berechnung der Inkremente wird das Horner-Schema verwendet, um die Tensor-Exponentialfunktion zu approximieren, ohne alle Zwischenterme explizit zu bilden. Dies reduziert die Anzahl der Gleitkommaoperationen und verbessert die numerische Stabilität.
• Backpropagation: Für das Training wird ein effizienter Rückwärtspfad implementiert. Anstatt alle Zwischensignaturen zu speichern (was den Speicherbedarf linear mit der Sequenzlänge erhöhen würde), werden diese Werte während des Backpropagations-Schritts rekonstruiert. Dies nutzt die algebraische Struktur der Signaturen (Gruppenähnlichkeit und Invertierbarkeit) aus, um benötigte Werte aus dem Endzustand und den Inkrementen zurückzurechnen.
• Fensterung (Windowing): Die Bibliothek unterstützt die parallele Berechnung von Signaturen über benutzerdefinierte Zeitfenster (sowohl expandierende als auch gleitende Fenster) in einem einzigen Aufruf, was Overheads minimiert und die GPU-Auslastung maximiert.

3. Schlüsselbeiträge

• Hochleistungs-GPU-Berechnung: pathsig erreicht im Vergleich zu etablierten Bibliotheken (wie keras_sig und pySigLib) Geschwindigkeitssteigerungen von 10–30-fach bei der Berechnung abgeschnittener Signaturen und 4–10-fach beim Training mit Backpropagation.
• Geringer Speicherbedarf: Durch die Vermeidung der Speicherung aller Zwischensignaturen skaliert der Speicherverbrauch nur mit der Ausgabe-Größe ($O(B \cdot D_{sig})$) und nicht mit der Sequenzlänge ($O(B \cdot M \cdot D_{sig})$). Dies ermöglicht das Training auf langen Sequenzen, bei denen andere Bibliotheken scheitern.
• Flexible Projektionen: Über die reine Tiefen-Abschneidung (Truncation) hinaus unterstützt die Bibliothek:
  • Wort-Projektionen: Die Auswahl beliebiger, benutzerdefinierter Wortmengen, um Redundanzen zu entfernen und die Dimensionalität zu reduzieren.
  • Anisotrope Abschneidung: Eine gewichtete Abschneidung, die unterschiedliche Regularitäten verschiedener Kanäle berücksichtigt (z. B. wenn einige Signal-Kanäle „rauer" sind als andere).
• Log-Signaturen: Unterstützung für die effiziente Berechnung von Log-Signaturen im Lyndon-Basis-System, wobei nur die notwendigen Koeffizienten materialisiert werden.

4. Ergebnisse und Benchmarks

Die Evaluation wurde auf einer NVIDIA H200 GPU durchgeführt und verglich pathsig mit keras_sig und pySigLib.

• Geschwindigkeit:
  • Bei der Vorwärtsberechnung (Forward Pass) wurden mediane Speedups von 12,44× gegenüber keras_sig und 40,11× gegenüber pySigLib erzielt.
  • Beim Training (Forward + Backward) lagen die Speedups bei 7,88× (vs. keras_sig) und 24,88× (vs. pySigLib).
  • Für Log-Signaturen wurden sogar Speedups von bis zu 84× gegenüber pySigLib erreicht.
• Speichernutzung:
  • pathsig benötigt während des Trainings nur etwa das 2-fache des Speichers für die reine Signatur-Ausgabe.
  • Im Gegensatz dazu skaliert keras_sig linear mit der Sequenzlänge und führt bei längeren Sequenzen (z. B. Länge 800+) zu Out-of-Memory-Fehlern, selbst auf GPUs mit 140 GB VRAM. pathsig bleibt auch bei diesen Konfigurationen stabil.
• Anwendungsbeispiel (Lead-Lag):
  • In einem Experiment zur Schätzung des Hurst-Parameters von fraktionalem Brownscher Bewegung wurde eine sparse Lead-Lag-Projektion verwendet.
  • Diese Projektion reduzierte die Merkmalsdimensionalität um den Faktor 6,25 und die Trainingszeit um den Faktor 2,24, während sie gleichzeitig eine geringere Testfehler-Rate und bessere Lernkurven als die vollständige abgeschnittene Signatur aufwies.

5. Bedeutung und Ausblick

Die Arbeit macht Pfad-Signaturen für eine breitere Palette von Anwendungen im maschinellen Lernen praktisch nutzbar, insbesondere für Szenarien mit großen Datenmengen, langen Zeitreihen und komplexen Modellen, die Gradienten-basiertes Training erfordern.

Durch die Kombination aus GPU-Beschleunigung, extrem effizientem Speichermanagement und flexiblen Projektionsmechanismen überwindet pathsig die bisherigen Skalierungsbarrieren. Die Fähigkeit, benutzerdefinierte Wortmengen zu wählen, ermöglicht es Forschern, domänenspezifisches Wissen (z. B. durch Graphen oder anisotrope Gewichte) direkt in die Merkmalsextraktion zu integrieren, was zu kompakteren und effizienteren Modellen führt. Die Bibliothek ist als Open-Source-PyTorch-Paket verfügbar und integriert sich nahtlos in moderne ML-Workflows.