Unreduced Persistence Diagrams for Topological Machine Learning

Diese Arbeit zeigt, dass Machine-Learning-Pipelines, die topologische Merkmale nutzen, welche aus unreduzierten Persistenzdiagrammen abgeleitet wurden, eine vergleichbare oder sogar bessere Leistung als solche unter Verwendung vollständig reduzierter Diagramme erzielen können, während sie gleichzeitig signifikante Vorteile hinsichtlich der Rechenkosten und der Speichereffizienz bieten.

Das Wesentliche

Stellen Sie sich vor, Sie versuchen, einem Computer beizubringen, Formen zu erkennen, wie zum Beispiel den Unterschied zwischen einem Kreis, einer Kugel und einem Donut (Torus). Um dies zu tun, verwenden Mathematiker ein Werkzeug namens Persistente Homologie. Betrachten Sie dieses Werkzeug als einen „topologischen Scanner“, der eine Punktwolke betrachtet und fragt: „Wo sind die Löcher? Wo sind die Schleifen?“

Der Scanner erstellt einen Bericht, der Persistenzdiagramm (PD) genannt wird. Dieser Bericht ist eine Liste von Punkten, wobei jeder Punkt ein Merkmal (wie ein Loch) und wie lange es „persistierte“, bevor es verschwand, während die Form wuchs, darstellt.

Das Problem: Der teure Bericht

Traditionell muss der Computer eine enorme Menge an schwerer Arbeit leisten, die „Reduktion“ genannt wird, um diesen Bericht zu erhalten. Es ist, als würde ein Bibliothekar versuchen, eine Bibliothek zu organisieren, indem er jedes einzelne Buch mit jedem anderen vergleicht, um Duplikate zu entfernen und die perfekte Zusammenfassung zu finden. Dieser Prozess ist:

1. Langsam: Er nimmt viel Zeit in Anspruch.
2. Speicherhungrig: Er benötigt eine riesige Menge an Computer-RAM (Arbeitsspeicher).
3. Verschwenderisch: Die Autoren stellten etwas Seltsames fest. Wenn sie diese detaillierten Berichte in Machine-Learning-Modelle einspeisten, ignorierten die Modelle den Großteil der Informationen. Es war, als hätte der Bibliothekar Stunden damit verbracht, eine 500-seitige Zusammenfassung zu schreiben, aber der Leser benötigt nur die ersten drei Sätze, um die Geschichte zu verstehen.

Die Lösung: Die „unreduzierte“ Skizze

Die Autoren stellten eine einfache Frage: Was wäre, wenn wir den schweren Bearbeitungsprozess komplett überspringen?

Anstatt den vollen „Reduktionsprozess“ durchzuführen, um den perfekten, endgültigen Bericht zu erhalten, schlagen sie unreduzierte Persistenzdiagramme vor.

• Die Analogie: Stellen Sie sich vor, Sie skizzieren ein Gesicht. Die „reduzierte“ Methode ist wie ein professioneller Künstler, der Stunden damit verbringt, jede Linie zu verfeinern, Fehler zu korrigieren und die Schattierung zu perfektionieren, bevor er Ihnen die Zeichnung zeigt. Die „unreduzierte“ Methode ist wie das schnelle Skizzieren der Hauptmerkmale (Augen, Nase, Mund) direkt aus den Rohdaten, ohne zu korrigieren oder zu verfeinern.
• Das Ergebnis: Überraschenderweise kann der Computer (das Machine-Learning-Modell) das Gesicht oft genauso gut aus der schnellen Skizze erkennen wie aus dem polierten Meisterwerk.

Was sie getan haben

Das Team entwickelte eine neue, schnellere Version der Software (basierend auf einem populären Tool namens Ripser), die die schwere Bearbeitung überspringt. Anstatt des vollständigen Berichts generiert sie diese „Skizzen“ (die sie Unreduced Diagrams oder spezifische Typen wie Low-Ones und Quasi-Apparent Pairs nennen).

Sie testeten dies bei drei verschiedenen Herausforderungen:

1. Formerkennung: Unterscheidung zwischen Kreisen, Kugeln und Donuts in verrauschten Daten.
2. Bildklassifizierung: Identifizierung von Kleidungsstücken (wie Sandalen vs. Sneaker) im Fashion-MNIST-Datensatz.
3. Gehirnscan-Regression: Vorhersage des Alters einer Person basierend auf der Struktur der Blutgefäße im Gehirn.

Die Ergebnisse

1. Leistung: In fast jedem Test schnitten die Modelle, die auf den „Skizzen“ (unreduzierten Diagrammen) trainiert wurden, genauso gut ab wie oder sogar besser als die Modelle, die mit den „polierten Berichten“ (vollständig reduzierten Diagrammen) trainiert wurden.
2. Geschwindigkeit & Speicher: Dies ist der größte Gewinn. Weil sie die schwere Bearbeitung übersprungen haben:
   • Nutzte die neue Methode signifikant weniger Speicher (manchmal bis zu 13-mal weniger).
   • War sie viel schneller, insbesondere bei der Verwendung mehrerer Computerkerne gleichzeitig (parallele Verarbeitung).
   • In einem extremen Fall lief die alte Methode aus dem Speicher und stürzte ab, während die neue Methode die Aufgabe erfolgreich abschloss.

Der Haken (Stabilität)

Die Autoren geben zu, dass diese „Skizzen“ etwas empfindlicher gegenüber Rauschen sind als die „polierten Berichte“. Wenn man die Daten zu stark erschüttert, kann sich die Skizze drastischer verändern als der polierte Bericht. In ihren Experimenten mit realistischen Mengen an Rauschen blieben die Skizzen jedoch stabil genug, um nützlich zu sein.

Das Fazit

Die Arbeit legt nahe, dass wir in der Welt des Topologischen Machine Learnings viel Zeit und Computerleistung verschwenden, indem wir versuchen, unsere Datenberichte „perfekt“ zu machen. Durch die Verwendung von unreduzierten Persistenzdiagrammen können wir eine „gut genüge“ Zusammenfassung viel schneller und mit weniger Speicherplatz erhalten, und der Computer lernt ebenso effektiv aus ihr. Es ist ein Kompromiss: Eine etwas gröbere Skizze für einen massiven Gewinn an Geschwindigkeit und Effizienz.

Technische Zusammenfassung

Technisches Resümee: Unreduzierte Persistenzdiagramme für Topologisches Maschinelles Lernen

Problemstellung

Die Kombination von Topologischer Datenanalyse (TDA) mit überwachtem maschinellem Lernen (ML) ist zu einem Standardansatz für die Analyse komplexer Daten in verschiedenen Bereichen geworden, darunter Biologie, Neurowissenschaften und Materialwissenschaften. Die Standardpipeline umfasst die Berechnung der Persistenten Homologie (PH), um Persistenzdiagramme (PDs) zu generieren, diese zu vektorisieren und ML-Modelle zu trainieren.

Es wurden jedoch zwei kritische Ineffizienzen in dieser Pipeline beobachtet:

1. Informationsredundanz: Empirische Belege deuten darauf hin, dass ML-Modelle oft signifikante Teile der in vektorisierten PDs enthaltenen Informationen ignorieren. Beispielsweise zeigten Regressionsaufgaben eine „nahezu optimale“ Leistung unter Verwendung der Persistenz des 28. am stärksten persistenten Punktes, und Benchmarks deuten darauf hin, dass naive statistische Vektorisierungen oft ebenso gut abschneiden wie komplexe.
2. Rechenaufwand: Die Berechnung vollständig reduzierter PDs ist oft der rechenintensivste Schritt in der Pipeline und erfordert erheblichen Speicherplatz und Zeit, insbesondere für große Datensätze.

Die zentrale Hypothese dieser Arbeit ist, dass, wenn ML-Modelle gut mit Vektorisierungen arbeiten können, die Informationen verwerfen, die vollständige Berechnung der PH (speziell die Reduktion von Randmatrizen) möglicherweise eine unnötige Rechenbelastung darstellt. Die Autoren schlagen vor, die vollständige Reduktion der Randmatrix gänzlich zu vermeiden, indem unreduzierte Persistenzdiagramme verwendet werden, die direkt aus unreduzierten Randmatrizen abgeleitet sind.

Methodik

Theoretischer Rahmen

Die Autoren definieren mehrere Arten von unreduzierten Persistenzdiagrammen (PDs), die aus einer Randmatrix $M$ konstruiert werden, ohne den standardmäßigen spaltenweisen Reduktionsalgorithmus durchzuführen. Diese basieren auf den Eigenschaften der Matrizenkolonnen:

• Apparent Pair (AP) PD: Paare $(low(M_j), j)$, wobei der niedrigste nicht-null Eintrag in Spalte $j$ der einzige Nicht-Null-Eintrag in dieser Zeile links ist (ein spezifisches Muster, das ein Persistenzpaar ohne Reduktion anzeigt).
• Lower Quasi-Apparent Pair (qAP↓) PD: Paare $(low(M_j), j)$, wobei $\beta(M_j) \neq -1$.
• Upper Quasi-Apparent Pair (qAP↑) PD: Paare $(\beta(M_j), j)$, wobei $\beta(M_j) \neq -1$. Hierbei ist $\beta(M_j)$ der höchste Zeilenindex eines Eintrags mit dem Wert 1 in Spalte $j$, der durch Reduktion nicht eliminiert werden kann.
• Low-Ones (L1) PD: Die Multimenge der Paare $(low(M_j), j)$ für alle Spalten, bei denen $low(M_j) \neq -1$.

Die L1- und qAP↑-Konstruktionen werden besonders für Vietoris-Rips (VR) Komplexe hervorgehoben, da andere unreduzierte Typen für diese Filtrationen möglicherweise nur ephemere Paare (Null-Persistenz) in höheren Homologie-Dimensionen liefern.

Stabilitätsanalyse

Die Arbeit untersucht die Lipschitz-Stabilität dieser Transformationen im Hinblick auf die Bottleneck-Distanz ($d_B$).

• Theoretische Ergebnisse: Die vollständig reduzierte (FR) PD-Transformation ist global stabil mit einer Lipschitz-Konstante $C=1$. Im Gegensatz dazu sind unreduzierte PDs (AP, qAP) im Allgemeinen nicht global stabil. Kleine Störungen in der Filtrationsfunktion können die Ordnung der Randmatrix-Spalten ändern, was zum Erscheinen oder Verschwinden von Apparent Pairs führt, was zu kombinatorischer Instabilität führt.
• Lokale Stabilität: Die Autoren beweisen, dass unreduzierte PDs lokal Lipschitz-stabil sind. Wenn die Störung der Filtrationsfunktion klein genug ist, um die Ordnung der Simplizes zu bewahren (speziell kleiner als die Hälfte der minimalen Lücke zwischen benachbarten Filtrationswerten), bleiben die Transformationen stabil.
• Experimentelle Stabilität: Experimentelle Untersuchungen an gestörten Punktwolken zeigen, dass während große Instabilitätsspitzen (bei denen sich die Anzahl der Punkte im Diagramm ändert) auftreten, diese selten sind. Die Mehrheit der Störungen führt zu Stabilitätsverhältnissen, die vergleichbar mit oder besser als im vollständig reduzierten Fall sind.

Computergestützte Implementierung

Um die rechnerischen Vorteile zu testen, implementierten die Autoren eine modifizierte Version des Ripser-Algorithmus, um qAP↑-Diagramme für VR-Komplexe zu berechnen.

• Parallelisierung: Im Gegensatz zum standardmäßigen Reduktionsalgorithmus, der Spalten seriell (von links nach rechts) verarbeitet, kann die Berechnung von qAP↑-Diagrammen parallelisiert werden. Der Algorith률 sucht unabhängig über die Spalten der Filtrations-Coboundary-Matrix.
• Speichereffizienz: Die Implementierung vermeidet das Speichern der vollständigen Randmatrix und der für die Reduktion benötigten Arbeitsgrenzen. Sie nutzt eine Hash-Map, um Paare zu speichern und überspringt „Zero Apparent Pairs“ (ephemere Paare) frühzeitig im Prozess.

Zentrale Ergebnisse

Rechenleistung

Das Benchmarking auf einem 32-Kern AMD Ryzen Threadripper PRO System gegenüber dem Standard-Ripser zeigte signifikante Gewinne:

• Wall Time (Reale Zeit): Die parallelisierte qAP↑-Berechnung erreichte eine durchschnittliche 20-fache Beschleunigung der Rechenzeit im Vergleich zur vollständigen Persistenzberechnung.
• Speicher: Der unreduzierte Ansatz benötigte etwa 1/13 des Speichers von Ripser für nicht-schwellenwertbasierte Beispiele und 1/1,86 für schwellenwertbasierte Beispiele.
• Skalierbarkeit: Die Autoren berechneten erfolgreich unreduzierte Diagramme für den torus4-Datensatz (50.000 Punkte), eine Aufgabe, bei der Ripser aufgrund von Speicherbeschränkungen (Anforderung von >300 GB RAM) scheiterte. Für den Cyclo-Octan-Datensatz verbrauchte die qAP↑-Berechnung 454-mal weniger Speicher und benötigte 59,5-mal weniger Zeit als Ripser.

Maschinelles Lernen

Die Autoren evaluierten die Leistung von Random Forest Klassifikatoren und Regressoren, die auf Vektorisierungen unreduzierter PDs (L1, qAP, AP) im Vergleich zu vollständig reduzierten PDs (FR) für drei Aufgaben trainiert wurden:

1. Synthetische Formklassifizierung: Klassifizierung von Punktwolken (Kreis, Kugel, Torus usw.) mit variierenden Rauschpegeln.
2. Fashion-MNIST Klassifizierung: Klassifizierung von Kleidungsbildern mittels kubischer Komplexe.
3. Brain Artery Tree Regression: Vorhersage des Alters von Probanden anhand von 3D-Hirnscan-Daten.

Ergebnisse:

• Gleichwertigkeit und Verbesserung: In allen Experimenten erbrachte mindestens ein Typ unreduzierter PDs eine Leistung, die ebenso gut wie oder besser als die der vollständig reduzierten PDs war.
• L1-Überlegenheit: Die L1-Diagramme schnitten konsistent auf einem Niveau mit oder sogar besser als FR-Diagramme ab. In der Fashion-MNIST-Aufgabe übertrafen L1-Diagramme FR-Diagramme um mindestens 10 Prozentpunkte in der durchschnittlichen Präzision.
• Robustheit: Diese Ergebnisse waren robust gegenüber verschiedenen Filtrationstypen (Alpha, Rips), Vektorisierungsmethoden (Persistence Images, Adcock-Carlsson-Koordinaten) und Rauschpegeln.
• Merkmalsrelevanz: Eine Analyse der Fashion-MNIST-Aufgabe ergab, dass L1- und FR-Modelle auf unterschiedlichen Regionen des Persistence-Image-Raums basieren. Die wichtigsten Merkmale für L1-Modelle konzentrierten sich auf $H_0$ (verbundene Komponenten), während FR-Modelle Merkmale sowohl aus $H_0$ als auch aus $H_1$ gleichmäßiger nutzten. Dies deutet darauf hin, dass unreduzierte Diagramme unterschiedliche, potenziell nützliche Informationen kodieren, die während der vollständigen Reduktion verworfen werden.

Bedeutung und Behauptungen

Die Arbeit kommt zu dem Schluss, dass unreduzierte Persistenzdiagramme effektive Substitute für vollständig reduzierte Diagramme in topologischen maschinellen Lern-Pipelines sind.

• Effizienz: Durch die Vermeidung des teuren Reduktionsschritts können Anwender eine signifikante Reduktion des Speicherbedarfs und der Rechenzeit erreichen, was die Analyse von Datensätzen ermöglicht, die mit Standard-PH-Methoden derzeit nicht handhabbar sind.
• Leistung: Entgegen der Annahme, dass die Reduktion für die Qualität notwendig sei, demonstrieren die Autoren, dass die durch Reduktion verworfenen Informationen oft nicht entscheidend für die nachgeschaltete ML-Leistung sind und dass unreduzierte Diagramme sogar distinkte, vorteilhafte Merkmale erfassen können.
• Zukünftige Richtungen: Die Autoren merken an, dass unreduzierte Diagramme zwar Rechenzeit sparen, die Vektorisierung jedoch aufgrund der größeren Anzahl an Punkten langsamer sein kann. Sie schlagen vor, dass zukünftige Arbeiten darauf abzielen sollten, Algorithmen zu entwickeln, die Vektorisierungen direkt aus unreduzierten Matrizen berechnen, ohne alle Paare explizit speichern zu müssen, um die Pipeline weiter zu optimieren.

Die Studie behauptet bescheiden, dass diese Ergebnisse auf eine Verschiebung in der Konstruktion von PH-ML-Pipelines hindeuten könnten, die potenziell die Recheneffizienz und den Erhalt „roher“ topologischer Merkmale gegenüber der strikten mathematischen Vollständigkeit vollständig reduzierter Diagramme priorisiert.