Mannigfaltigkeiten lernen und triangulieren mittels Kollaps

Computer operieren digital, waehrend Formen in unsere Welt oft glatt sind, manchmal mit Ecken und Kanten. Wir benoetigen daher Methoden und Algorithmen die glatte in digitale Beschreibungen umwandeln. In 2D ist das nicht so schwierig, denken Sie zum Beispiel an Pac-Man. In 3D ist das schon wesentlich schwieriger. In den letzten drei oder vier Jahrzehnten haben 3D-Modellierung und Grafik eine bedeutende Entwicklung erfahren: vergleichen Sie zum Beispiel, Shogun: Total War oder Super Mario 64 mit modernen Computerspielen wie Forza Horizon 4 und Red Dead Redemption 2 oder Filmen wie Interstellar. Obwohl wir unsere Umgebung als drei-dimensional erleben, ist diese Sicht nicht vollstaendig und hoehere Dimensionen sind manchmal notwendig um die Welt zu beschreiben. Ein Beispiel sind Schwarze Loecher die durch Einsteins allgemeine Relativitaetstheorie modelliert werden. Das ist eine vier-dimensionale Theorie, die Raum und Zeit in die Raumzeit integriert. Die Berechnungen der ins Schwarze Loch stroemenden Gase erfordern eine Diskretisierung der vier-dimensionalen Raumzeit. Hoehere Dimensionen sind aber nicht nur fuer die allgemeine Relativitaetstheorie wichtig: - In der Datenwissenschaft treten oft hohe Dimensionen auf: wenn wir an den monatlichen Ausgaben einer Gruppe von Menschen fuer Essen, Trinken, Kleidung, Computerspiele und Kino interessiert sind, stossen wir auf einen (5 mal 12) 60-dimensionalen Raum. - Roboter mit mehreren Gelenken fuehren auch zu hohen Dimensionen, da jeder Winkel, den ein Gelenk mit einem benachbarten Gelenk einnimmt eine Dimension zur Beschreiben zufuegt. - Hoch-dimensionale Raeume treten auch bei der Modellierung des Gasflusses um Flugzeugfluegel und bei der Beschreibung der Position einzelner Atome in einem Molekuel auf. In den naechsten zwei Jahren werden wir neue, nachweislich korrekte und schnelle Algorithmen entwickeln, um hoch-dimensionale Raeume zu diskretisieren. Es gibt bereits einige solche Algorithmen, diese sind aber entweder langsam oder es ist nicht immer klar ob die Ergebnisse korrekt sind, oder manchmal beides. Wir befinden uns in einem fruehen Stadium der Entwicklung hoch-dimensionaler Diskretisierungsmethoden, ähnlich wie 3D-Grafiken in den 80er und 90er Jahren des letzten Jahrhunderts waren. Wir erwarten starke Entwicklungen, die die Fortschritte in der 3D-Grafik widerspiegeln.

Die mediale Achse ist eine Menge, der in der Mitte einer Form liegt und als Skelett agiert. Betrachtet man zum Beispiel die Kontur einer Hand, dann ist die mediale Achse ein Baum, dem jeder Finger einen Ast bildet. Mit Hilfe der medialen Achse ist es einfach, verschiedene Komponenten (in diesem Fall die Finger) einer geometrischen Form zuzuordnen. Die mediale Achse erhält auf diese Weise einen Teil der geometrischen Information. Sie wird daher häufig bei der Segmentierung von Formen, beim Formenlernen und bei der Formerkennung verwendet. Obwohl dies in der Praxis recht nützlich ist, gibt es dabei jedoch erhebliche Probleme: In der Praxis haben wir keine mathematisch perfekte geometrische Form. Wir können eine Form nur mit einer endlichen Präzision messen, oder anders ausgedrückt, es gibt ein gewisses Rauschen in der Messung. Außerdem können wir nur eine endliche Anzahl von Messungen durchführen. Es ist jedoch bekannt, dass schon ein geringes Maß an Rauschen die mediale Achse dramatisch ändern kann. Diese Instabilität ist so erheblich, dass nicht bewiesen wurde, dass man die mediale Achse mit einer Turing-Maschine berechnen kann. Eine Turingmaschine ist ein Modell für einen "perfekten" Computer, das vom Begründer der Informatik und Code brechender Held des Zweiten Weltkriegs, Alan Turing, eingeführt wurde (der breiten Öffentlichkeit bekannt durch den Film "The Imitation Game"). Wir (d. h. meine Mitarbeiter und ich) haben uns in den letzten Jahren mit der Instabilität der medialen Achse befasst. Wir haben gezeigt, dass sie durch spezifische Veränderungen stabil wird, was auch bedeutet, dass sie mit einer Turingmaschine berechenbar ist. In der Praxis bedeutet unser Ergebnis, dass die Mediale Achse ein zuverlässiges Werkzeug für die Segmentierung von Formen und das Lernen von Formen ist, d.h. selbst mit gestörten Daten kann man eine (gute) Annäherung an die Mediale Achse finden, die dann in Lern- oder Segmentierungsalgorithmen verwendet werden kann. Dieses Projekt leistete einen kleinen Beitrag zur Suche nach erklärbarer künstlicher Intelligenz und erklärbaren Maschinenlehre: In den letzten 20 jahre haben Informatiker mit Deep Neural Networks beeindruckende Ergebnisse erzielt. Ein aktuelles Beispiel für ein solches beeindruckendes Werkzeug ist ChatGPT. Das Problem bei den meisten Lernmethoden, die auf Deep Neural networks basieren (und ChatGPT ist da keine Ausnahme), ist jedoch, dass die Antworten, die es gibt, nicht erklärt werden können und die Ergebnisse gelegentlich völlig falsch sind. Dieses Problem tritt jedoch nicht nur beim Deep Learning auf, sondern auch in anderen Bereichen des Maschinen-Lernens. Für die mediale Achse einer geometrischen Form ist dieses Projekt einen Schritt weiter gegangen: Wir haben bewiesen, dass die mediale Achse gut approximiert werden kann, was eine große Anzahl von Lernalgorithmen, die auf der medialen Achse stützen, mathematisch untermauert.