Manifold Dimension Estimation via Local Graph Structure

Technische Samenvatting: Schatting van Manifold-dimensie via Lokale Grafestructuur

Probleemstelling
Het schatten van de intrinsieke dimensie $d$ van een manifold die is ingebed in een hoog-dimensionale omgevingsruimte $\mathbb{R}^p$ is een fundamentele uitdaging in niet-lineaire dimensiereductie. Hoewel veel bestaande schatters (bijv. Local PCA, DanCo, TwoNN) vertrouwen op de "vlakke-aanneming"—het benaderen van lokale buurten als $d$-dimensionale lineaire deelruimten—stuit deze aanpak op problemen wanneer manifolds significante kromming vertonen of niet-lineair zijn ingebed. Recente methoden zoals Curvature-Adjusted PCA (CA-PCA) proberen dit aan te pakken door eigenstructuren expliciet te corrigeren voor kromming, maar lijden vaak onder overschatting in hoog-dimensionale omgevingsruimten of computationele instabiliteit. De auteurs identificeren een gat in methoden die lokale kromming robuust kunnen modelleren zonder te vertrouwen op instabiele directe krommingsschatting of detectie van eigenwaarde-gaten.

Methodologie
De auteurs stellen een nieuw kader voor dat de schatting van manifold-dimensie herformuleert als een regressieprobleem op lokale PCA-coördinaten. In plaats van lokale vlakheid aan te nemen of krommingstensors expliciet te schatten, modelleert de methode de lokale buurt van een punt $x_k$ als een grafiek van een gladde functie $g: \mathbb{R}^d \to \mathbb{R}^{p-d}$.

1. Lokale Grafische Representatie: Voor een punt $x_k$ en zijn $K$-naaste buren voeren de auteurs PCA uit om een lokaal coördinatenstelsel vast te stellen dat is uitgelijnd met de geschatte raakruimte. De eerste $d$ coördinaten vertegenwoordigen de raakruimte, terwijl de overige $p-d$ coördinaten de normaalruimte vertegenwoordigen.
2. Regressieformulering: Het kader stelt dat de normaalcoördinaten kunnen worden uitgedrukt als een functie van de raakcoördinaten. Aangezien de Taylor-ontwikkeling van eerste orde van deze functie nul is (per definitie van de raakruimte), maken de auteurs gebruik van termen van tweede orde (kwadratisch) om lokale kromming te vangen.
3. Aftasten van Kandidaat-dimensies: Het algoritme iteratieert door kandidaat-dimensies $j$ (van 1 tot $p-1$). Voor elke $j$ behandelt het de eerste $j$ PCA-coördinaten als invoer en de $(j+1)$-de coördinaat als uitvoer, en past een kwadratisch regressiemodel aan.
4. Twee Schatters:
   • Quadratic Embedding (QE): Gebruikt Ordinary Least Squares (OLS) om het kwadratische model aan te passen. Het evalueert de goodness-of-fit met de $F$-statistiek en de aangepaste $R^2$. De geschatte dimensie is de kleinste $j$ waarbij de modelfit statistisch significant wordt (p-waarde < 1%) en significant blijft voor alle hogere dimensies.
   • Total Least Squares (TLS): Gebruikt Total Least Squares om rekening te houden met fouten in zowel invoer- als uitvoervariabelen. In plaats van $F$-statistieken evalueert het de relatieve daling in totale TLS-fout ($\eta_j$) tussen opeenvolgende dimensies. De geschatte dimensie komt overeen met de piek in relatieve daling.

Belangrijkste Bijdragen

• Regressie-gebaseerd Kader: Het artikel introduceert een nieuw perspectief dat dimensieschatting als een recursief regressieprobleem neerzet. Dit vervangt instabiele lokale geometrische schatting (zoals directe krommingsberekening) door een statistisch geaggregeerd aanpassingsproces, wat grotere robuustheid biedt tegen schaarste in bemonstering en ruis.
• Krommingsbewuste Modellering: Door kwadratische modellen te gebruiken, vangt de methode de kromming van de manifold expliciet zonder expliciete krommingsschatting of eigenwaarde-correctie te vereisen, waardoor de overschattingproblemen die gebruikelijk zijn bij PCA-gebaseerde methoden worden verminderd.
• Robuustheid tegen Ruis en Nonlineariteit: Het kader neemt natuurlijk rekening met ruis en is ontworpen om goed te presteren op manifolds met complexe, niet-lineaire embeddings waar vlakke-aannemingen falen.
• Praktische Implementatie: De auteurs bieden twee concrete schatters (QE en TLS) met gedetailleerde algoritmen, inclusief heuristieken voor het beperken van de zoekruimte ($p_{max}$) op basis van buurtgrootte om computationele haalbaarheid te waarborgen.

Experimentele Resultaten
De auteurs evalueerden QE en TLS op 18 synthetische manifolds (waaronder bollen, vervormde bollen en Gaussische oppervlakken) en 6 real-world datasets (ISOMAP, MNIST, ISOLET, Fashion MNIST, Frey Face, Gas Sensor Array Drift).

• Synthetische Data: QE en TLS vertoonden concurrerende of superieure prestaties vergeleken met state-of-the-art methoden (Local PCA, CA-PCA, DanCo, TwoNN, MADA, enz.), met name in regimes met kleine steekproeven en op niet-lineair ingebedde manifolds (bijv. vervormde bollen). Ze mitigatieerden effectief de overschatting die werd waargenomen bij CA-PCA en Local PCA wanneer de omgevingsdimensie $p$ aanzienlijk groter is dan de intrinsieke dimensie $d$.
• Ruisrobuustheid: In aanwezigheid van Gaussische, uniforme en Laplace-ruis behielden de voorgestelde methoden robuuste prestaties en presteerden ze beter dan veel op vlakheid gebaseerde schatters, wiens nauwkeurigheid aanzienlijk verslechterde.
• Real-world Data: Op real-world datasets leverden de schatters resultaten op die consistent waren met consensusbereiken (bijv. schatten van ISOMAP $\approx 3$, MNIST $\approx 8-11$). Opmerkelijk is dat ze de ernstige overschatting voorkwamen die werd waargenomen bij Local PCA en CA-PCA op datasets met hoge omgevingsdimensies.
• Waargenomen Beperkingen: De methoden vertoonden verminderde prestaties op "triviale" manifolds met nul kromming (bijv. hyperballen), waarbij het kwadratische model een verkeerde specificatie is. Bovendien is TLS onderaan begrensd door 2 vanwege de afhankelijkheid van relatieve foutdalingen tussen dimensies.

Betekenis en Claims
Het artikel claimt dat door het paradigma te verschuiven van geometrische benadering naar statistische regressie, het voorgestelde kader verbeterde robuustheid en nauwkeurigheid bereikt, met name in uitdagende regimes met kleine steekproefgroottes en complexe kromming. De auteurs stellen dat hun methoden een overtuigend alternatief bieden voor bestaande top-presterende schatters, en effectief de beperkingen van zowel op vlakheid gebaseerde benaderingen als op eigenwaarden gebaseerde krommingscorrecties aanpakken. Zij concluderen dat hoewel de huidige kwadratische formulering effectief is, toekomstig werk meer expressieve modellen zou kunnen verkennen als er betrouwbare diagnostische hulpmiddelen voor steekproefstatistieken worden ontwikkeld. Het werk wordt gepresenteerd als een belangrijke stap naar het oplossen van de aanhoudende uitdagingen in de schatting van manifold-dimensie, hoewel de auteurs bescheiden blijven wat betreft de noodzaak van verdere verfijning in evaluatiecriteria (specifiek voor TLS) en de behandeling van ruis in de schatting van de raakruimte.