Manifold Dimension Estimation via Local Graph Structure

Technische Zusammenfassung: Schätzung der Mannigfaltigkeitsdimension über lokale Graphstrukturen

Problemstellung
Die Schätzung der intrinsischen Dimension $d$ einer Mannigfaltigkeit, die in einen hochdimensionalen umgebenden Raum $\mathbb{R}^p$ eingebettet ist, stellt eine fundamentale Herausforderung in der nichtlinearen Dimensionsreduktion dar. Während viele bestehende Schätzer (z. B. Local PCA, DanCo, TwoNN) auf der „Flachheitsannahme" basieren – der Approximation lokaler Nachbarschaften als $d$-dimensionale lineare Unterräume – stößt dieser Ansatz an Grenzen, wenn Mannigfaltigkeiten eine signifikante Krümmung aufweisen oder nichtlinear eingebettet sind. Neuere Methoden wie die Krümmungskorrigierte PCA (CA-PCA) versuchen dies zu adressieren, indem sie Eigenstrukturen explizit für Krümmungen korrigieren, leiden jedoch häufig unter Überschätzung in hochdimensionalen umgebenden Räumen oder rechnerischer Instabilität. Die Autoren identifizieren eine Lücke bei Methoden, die lokale Krümmungen robust modellieren können, ohne sich auf instabile direkte Krümmungsschätzungen oder Eigenwertlückendetektionen zu verlassen.

Methodik
Die Autoren schlagen ein neues Framework vor, das die Schätzung der Mannigfaltigkeitsdimension als Regressionsproblem auf lokalen PCA-Koordinaten neu fasst. Anstatt lokale Flachheit anzunehmen oder Krümmungstensoren explizit zu schätzen, modelliert die Methode die lokale Nachbarschaft eines Punktes $x_k$ als Graph einer glatten Funktion $g: \mathbb{R}^d \to \mathbb{R}^{p-d}$.

1. Lokale Graphrepräsentation: Für einen Punkt $x_k$ und seine $K$-nächsten Nachbarn führen die Autoren eine PCA durch, um ein lokales Koordinatensystem herzustellen, das an den geschätzten Tangentialraum ausgerichtet ist. Die ersten $d$ Koordinaten repräsentieren den Tangentialraum, während die verbleibenden $p-d$ Koordinaten den Normalraum darstellen.
2. Regressionsformulierung: Das Framework geht davon aus, dass die Normalkoordinaten als Funktion der Tangentialkoordinaten ausgedrückt werden können. Da die Taylor-Entwicklung erster Ordnung dieser Funktion (per Definition des Tangentialraums) null ist, nutzen die Autoren Terme zweiter Ordnung (quadratisch), um lokale Krümmungen zu erfassen.
3. Durchsuchen von Kandidatendimensionen: Der Algorithmus iteriert durch Kandidatendimensionen $j$ (von 1 bis $p-1$). Für jedes $j$ behandelt er die ersten $j$ PCA-Koordinaten als Eingaben und die $(j+1)$-te Koordinate als Ausgabe und passt ein quadratisches Regressionsmodell an.
4. Zwei Schätzer:
   • Quadratische Einbettung (QE): Verwendet die Methode der kleinsten Quadrate (OLS), um das quadratische Modell anzupassen. Sie bewertet die Güte der Anpassung mittels des $F$-Statistik-Werts und des adjustierten $R^2$. Die geschätzte Dimension ist das kleinste $j$, bei dem die Modellanpassung statistisch signifikant wird (p-Wert < 1 %) und für alle höheren Dimensionen signifikant bleibt.
   • Total Least Squares (TLS): Verwendet Total Least Squares, um Fehler sowohl in Eingabe- als auch in Ausgabepunkten zu berücksichtigen. Anstelle von $F$-Statistiken bewertet es den relativen Rückgang des gesamten TLS-Fehlers ($\eta_j$) zwischen aufeinanderfolgenden Dimensionen. Die geschätzte Dimension entspricht dem Peak des relativen Rückgangs.

Hauptbeiträge

• Regressionsbasiertes Framework: Das Papier führt eine neue Perspektive ein, die Dimensionschätzung als rekursives Regressionsproblem darstellt. Dies ersetzt instabile lokale geometrische Schätzungen (wie direkte Krümmungsberechnungen) durch ein statistisch aggregiertes Anpassungsverfahren, das eine größere Robustheit gegenüber Spärlichkeit der Stichproben und Rauschen bietet.
• Krümmungsbewusste Modellierung: Durch den Einsatz quadratischer Modelle erfasst die Methode die Krümmung der Mannigfaltigkeit explizit, ohne eine explizite Krümmungsschätzung oder Eigenwertkorrektur zu erfordern, wodurch die bei PCA-basierten Methoden üblichen Probleme der Überschätzung gemildert werden.
• Robustheit gegenüber Rauschen und Nichtlinearität: Das Framework nimmt Rauschen auf natürliche Weise auf und ist so konzipiert, dass es auf Mannigfaltigkeiten mit komplexen, nichtlinearen Einbettungen gut funktioniert, bei denen Flachheitsannahmen versagen.
• Praktische Implementierung: Die Autoren stellen zwei konkrete Schätzer (QE und TLS) mit detaillierten Algorithmen bereit, einschließlich Heuristiken zur Begrenzung des Suchraums ($p_{max}$) basierend auf der Nachbarschaftsgröße, um die rechnerische Machbarkeit sicherzustellen.

Experimentelle Ergebnisse
Die Autoren bewerteten QE und TLS an 18 synthetischen Mannigfaltigkeiten (einschließlich Kugeln, deformierten Kugeln und Gaußschen Oberflächen) und 6 realen Datensätzen (ISOMAP, MNIST, ISOLET, Fashion MNIST, Frey Face, Gas Sensor Array Drift).

• Synthetische Daten: QE und TLS zeigten im Vergleich zu State-of-the-Art-Methoden (Local PCA, CA-PCA, DanCo, TwoNN, MADA usw.) eine konkurrenzfähige oder überlegene Leistung, insbesondere bei kleinen Stichprobenumfängen und auf nichtlinear eingebetteten Mannigfaltigkeiten (z. B. deformierten Kugeln). Sie milderten effektiv die Überschätzung, die bei CA-PCA und Local PCA beobachtet wurde, wenn die umgebende Dimension $p$ die intrinsische Dimension $d$ signifikant übersteigt.
• Rauschrobustheit: In Gegenwart von Gaußschem, uniformem und Laplace-Rauschen behielten die vorgeschlagenen Methoden eine robuste Leistung bei und übertrafen viele auf Flachheit basierende Schätzer, deren Genauigkeit erheblich nachließ.
• Reale Daten: Bei realen Datensätzen lieferten die Schätzer Ergebnisse, die mit Konsensbereichen übereinstimmten (z. B. Schätzung von ISOMAP $\approx 3$, MNIST $\approx 8-11$). Bemerkenswerterweise vermieden sie die schwere Überschätzung, die bei Local PCA und CA-PCA auf Datensätzen mit hohen umgebenden Dimensionen beobachtet wurde.
• Beobachtete Einschränkungen: Die Methoden zeigten eine reduzierte Leistung bei „trivialen" Mannigfaltigkeiten mit null Krümmung (z. B. Hyperkugeln), wo das quadratische Modell eine Fehlspezifikation darstellt. Zudem ist TLS nach unten durch 2 begrenzt, bedingt durch seine Abhängigkeit von relativen Fehlerabfällen zwischen Dimensionen.

Bedeutung und Behauptungen
Das Papier behauptet, dass durch den Paradigmenwechsel von geometrischer Approximation zu statistischer Regression das vorgeschlagene Framework eine verbesserte Robustheit und Genauigkeit erreicht, insbesondere in herausfordernden Regimen mit kleinen Stichprobenumfängen und komplexer Krümmung. Die Autoren betonen, dass ihre Methoden eine überzeugende Alternative zu bestehenden, leistungsstarken Schätzern bieten und effektiv die Grenzen sowohl flachheitsbasierter Ansätze als auch eigenwertbasierter Krümmungskorrekturen adressieren. Sie schließen, dass die aktuelle quadratische Formulierung zwar effektiv ist, zukünftige Arbeiten jedoch ausdrucksstärkere Modelle erforschen könnten, sofern zuverlässige Diagnosewerkzeuge für Stichprobenstatistiken entwickelt werden. Die Arbeit wird als ein bedeutender Schritt zur Bewältigung der anhaltenden Herausforderungen bei der Schätzung der Mannigfaltigkeitsdimension präsentiert, wobei die Autoren jedoch bescheiden bleiben hinsichtlich des Bedarfs weiterer Verfeinerungen bei Bewertungskriterien (insbesondere für TLS) und beim Umgang mit Rauschen in der Tangentialraumschätzung.