Algorithmen zur topologische Datenanalyse

In der heutigen Zeit werden ununterbrochen riesige Datenmengen generiert. Zum Beispiel werden auf YouTube 300 Stunden Videomaterial hochgeladen - pro Minute! Bei diese Datenmassen benötigt man intelligente Methoden, um die relevanten Informationen aus einer Datensammlung zu extrahieren; diese Prozedur wird als Datenanalyse bezeichnet. Zu den Anwendungsbereichen zählen Empfehlungssysteme für Nutzer von Audio- oder Videostreamseiten oder die automatisierte Erkennung von Anomalien bei Überwachungskameras. In den letzten 15 Jahren wurde ein neuer und vielleicht überraschender Ansatz zur Datenanalyse entwickelt: die qualitativen Eigenschaften einer Datenmenge werden mit Hilfe der mathematischen Theorie der Topologie untersucht. Die grobe Idee beteht darin, die Daten in eine geometrische Form zu transformieren und dann zu untersuchen, wie diese Form verbunden ist. Zum Beispiel sind ein Ball und ein Donut verschiedenartig verbunden, weil letzterer ein Loch in seiner Mitte hat. Eine solche topologischen Analyse offenbart oftmals relevante Information über die zugrundeliegenden Daten, wie durch eine Vielzahl von Anwendungsbeispielen aufgezeigt wurde, z.B. in der Biologie, Physik oder Computergrafik. Jedoch braucht die Comouterberechnung der topologischen Eigenschaften für große Daten eine lange Zeit, was den Einsatz dieser Methoden auf eher kleine Beispiel reduziert. Das Ziel des Projekts ist es, dies zu ändern: wir möchten Computerprogramme entwickeln, die Datenmengen verarbeiten können, welche mit heutiger Technologie nicht zu bewerkstelligen sind. Auf diese Weise erweitern wir erheblich die potentiellen Anwendungsgebiete, in denen topologische Datenanalyse neue Einsichten liefern kann. Ein solcher Fortschritt benötigt neuartige Wege um die relevante topologische Information einer Datenmenge zu berechnen. Um die Vorteile unserer entwickelten Methoden zu verifizieren, werden wir diese mit den Werkzeugen der theoretischen Informatik untersuchen; gleichzeitg werden wir sie mit existierenden Methoden auf realistischen Datenmengen vergleichen. Letzteres erscheint vielleicht als das natürlichere Qualitätsmerkmal, jedoch ist ersteres von ebensogrosser Bedeutung, da es einen Vergleich von Berechnungsmethoden auf allen potentiellen zukünftigen Eingaben erlaubt, während Experimente nur das Verhalten auf derzeit verfügbaren Eingaben wiedergeben. Lösungen, die in beiden Varianten überlegen sind, liefern langfristig wertvollere Beiträge zum Forschungsgebiet. Dieses Projekt hat einen bemerkenswert interdisziplinären Charakter, indem es algebraische Topologie, Datenanalyse, Geometrie, theoretische Informatik und Softwareentwicklung zusammenbringt. Es etabliert effiziente Berechnung als Brückenschlag zwischen abstrakter Mathematik und realen Anwendungsbereichen und ebnet den Weg für topologische Methoden als Standardwerkzeug im Kontext der Datenanalyse.

In diesem Projekt haben wir uns zum Ziel gesetzt, algorithmische Fragestellungen im Bereich der topologischen Datenanalyse zu untersuchen und die Grenzen des Machbaren zu verschieben. Dabei verwendeten wir sowohl Methoden der theoretischen Informatik als auch des Algorithm Engineering, um diese Fragestellungen aus verschiedenen Blickwinkeln zu beleuchten. Wir stellen einige der Hauptresultate kurz vor: (1) Ein Hauptproblem der topologischen Datenanalyse ist die Berechnung von persistenten Barcodes. Dabei existiert eine Diskrepanz zwischen der theoretischen Komplexitaet des Problems (der Algorithmus braucht im schlimmsten Fall kubisch viel Zeit bezueglich der Eingabegroesse) und der praktisch beobachteten Komplexitaet auf realen Daten (linear und damit - zum Glueck - sehr schnell). Wir konnten zeigen, dass die Komplexitaet der Barcodeberechnung unter natuerlichen Modellen im Erwartungswert besser ist als kubisch. Das heisst, wir konnten die folkloristische Aussage, dass worst-case Instanzen "selten" sind, mathematisch praezise fassen und mit Hilfe von probabilistischer Topologie beweisen. (2) Multi-parameter Persistenz ist ein Teilbereich der topologischen Datenanalyse mit wachsender Bedeutung. Ein ungeloestes Hauptproblem in diesem Bereich war die Frage der effizienten Berechnung der Interleavingdistanz zwischen zwei Instanzen. Diese Frage ist bedeutend, da die Interleavingdistanz in einem gewissen mathematisch beweisbaren Sinn das "beste" Distanzmass darstellt. Wir konnten beweisen, dass die Berechnung dieser Distanz NP-schwer ist, ebenso wie die Approximation dieser Distanz bis auf einen Faktor von 3. Dieses Resultat sagt also, dass die Existenz eines effizienter Algorithmus sehr unwahrscheinlich ist. Ein positiver Effekt dieses Resultats ist, dass sich Forscher nun auf andere Distanzmasse konzentrieren koennen. Unser Projekt hat ebenfalls fuer die alternative Matchingdistanz mehrere effiziente Algorithmen vorgeschlagen. (3) Ein wichtiger Baustein fuer die schnelle Berechnung mit Daten ist Kompression: wie laesst sich die topologische Essenz eines Datensatzes moeglichst effizient beschreiben? Fuer multi-parametrisierte Datensaetze haben wir hier ein Verfahren entwickelt. Es komprimiert Datensaetze von mehreren Gigabytes Groesse in wenigen Sekunden, ohne die topologischen Eigenschaften zu aendern. Damit wird die Analyse eines Datensatzes erheblich erleichtert. Unsere Software ist frei verfuegbar. Die Vielzahl an bedeutenden erreichten Resultaten gibt uns Recht, dass unser ganzheitlicher Ansatz erfolgreich war. Wir erwarten, dass unsere Resultate, sowohl theoretischer als auch praktischer Natur, das Forschungsfeld in der Zukunft voranbringen werden und weitere Anwendungen von persistenter Homologie in der Datenanalyse ermoeglichen werden. Da die topologische Datenanalyse sehr vielseitig eingesetzt wird (in praktisch allen Naturwissenschaften und darueber hinaus) haben unsere Resultaten eine indirekte Auswirkung weit ueber den Bereich der algorithmischen Topologie hinaus.