Skeleton Regression: A Graph-Based Approach to Estimation with Manifold Structure

Titel: Skeleton Regression: Een op grafen gebaseerde aanpak voor schatting met manifold-structuur

Auteurs: Zeyu Wei en Yen-Chi Chen (Universiteit van Washington)
Publicatie: Electronic Journal of Statistics

---

1. Het Probleem

Veel moderne datasets vertonen een complexe geometrische structuur waarbij de covariaten (voorspellers) niet willekeurig in een hoogdimensionale ruimte zijn verdeeld, maar zich rondom een laagdimensionale manifold bevinden die is ingebed in die hoge dimensie.

• Uitdaging: Traditionele niet-parametrische regressiemethoden (zoals k-NN of kernelregressie) lijden vaak onder de "vloek van de dimensionaliteit" wanneer ze direct worden toegepast op de oorspronkelijke hoogdimensionale ruimte.
• Bestaande oplossingen: Methoden zoals Principal Component Regression (PCR) of Manifold Regularization proberen de structuur te benutten, maar zijn vaak niet robuust tegen variaties die de data van de ware manifold afwijken (ruis) of falen bij data die bestaat uit meerdere disjuncte (niet-verbonden) componenten.
• Doel: Een regressieframework ontwikkelen dat de onderliggende geometrische structuur effectief benut, de vloek van de dimensionaliteit omzeilt, en robuust is tegen ruis en meerdere manifolds.

2. Methodologie: Het Skeleton Regression Framework

De auteurs introduceren een tweestapsframework dat grafentheorie combineert met niet-parametrische regressietechnieken.

Stap 1: Constructie van de "Skeleton" (Het Skelet)

In plaats van elke datapunt als een knooppunt te gebruiken, wordt een vereenvoudigde grafische representatie van de data geconstrueerd, genaamd het skeleton.

• Knooppunten (Knots): Deze worden gegenereerd via $k$-means clustering met een groot aantal clusters (typisch $\approx \sqrt{n}$). Deze punten fungeren als representatieve centra van de data.
• Randen (Edges): Randen worden toegevoegd tussen knooppunten als hun respectievelijke Voronoi-cellen een gemeenschappelijke grens delen. Dit wordt benaderd via het analyseren van de 2-Nearest-Neighbor (2-NN) regio's van de steekproefpunten.
• Gewichting: De randen worden gewogen met Voronoi-dichtheid, wat de waarschijnlijkheid meet dat een punt tussen twee knooppunten valt.
• Segmentatie: Het skelet kan worden opgesplitst in disjuncte componenten (bijv. als de data uit meerdere gescheiden manifolds bestaat) door een drempelwaarde op de randgewichten toe te passen.

Stap 2: Projectie van Data

Elke oorspronkelijke covariaat $\mathbf{x}$ wordt geprojecteerd op het skelet $S$:

• Als de twee dichtstbijzijnde knooppunten niet verbonden zijn, wordt het punt geprojecteerd op het dichtstbijzijnde knooppunt.
• Als ze verbonden zijn, wordt het punt orthogonaal geprojecteerd op de lijn (rand) die deze knooppunten verbindt.
• Hierdoor wordt de data afgebeeld op een verzameling van 0-dimensionale punten (knooppunten) en 1-dimensionale lijnsegmenten (randen), onafhankelijk van de oorspronkelijke ruimtelijke dimensie $d$.

Stap 3: Regressie op het Skelet

Op het geprojecteerde skelet worden niet-parametrische methoden toegepast, gebruikmakend van een skelet-gebaseerde afstand ($d_S$). Deze afstand is de kortste padlengte over de grafische structuur (geodesische afstand op het skelet).
De auteurs passen drie methoden toe:

1. S-Kernel Regressie: Een kernel-geschatte gemiddelde op basis van de skelet-afstand.
2. S-kNN Regressie: $k$-Nearest Neighbors op basis van de skelet-afstand.
3. S-Lineaire Spline (S-Lspline): Een lineaire spline die over het grafische netwerk continu is. Dit wordt geformuleerd als een lineair regressiemodel waarbij de voorspellingen op de randen lineaire interpolaties zijn tussen de waarden op de knooppunten.

3. Belangrijkste Bijdragen

• Nieuw Framework: De introductie van "Skeleton Regression" als een brug tussen manifold learning en niet-parametrische regressie.
• Theoretische Garanties: De auteurs bewijzen consistentie en convergentiesnelheden voor de voorgestelde methoden.
  • Op randen (edges) convergeert de estimator met een snelheid van $O(h) + O_p(\sqrt{1/nh})$, vergelijkbaar met 1D kernelregressie.
  • Op knooppunten met niet-nul massa (waar veel data op projecteert) is de convergentie $O(h) + O_p(\sqrt{1/n})$.
  • Op knooppunten met nul massa convergeert de schatter naar een gewogen gemiddelde van de aangrenzende randen.
• Robuustheid: Het framework is specifiek ontworpen om robuust te zijn tegen additieve ruis en data die uit meerdere disjuncte manifolds bestaat, situaties waarin andere methoden (zoals Spectral Series of PCR-LE) vaak falen.
• Interpreteerbaarheid: Het outputt niet alleen een voorspellingsmodel, maar ook een visueel interpreteerbaar skelet dat de onderliggende structuur van de covariaten samenvat.

4. Resultaten

De methode werd getest op zowel gesimuleerde als echte datasets:

• Simulaties:

  • Yinyang Data (meerdere disjuncte componenten): Alle skeleton-methoden (S-Kernel, S-kNN, S-Lspline) presteerden aanzienlijk beter dan standaard kNN, Ridge, Lasso, Spectral Series en Fast-KRR. Dit bevestigt dat het skelet de disjuncte structuur beter vastlegt.
  • Noisy Yinyang Data: Bij toevoeging van 20% ruis bleven de skeleton-methoden superieur, met name S-Kernel.
  • SwissRoll Data (continue 2D manifold): De skeleton-methoden presteerden beter dan de concurrenten, waarbij S-Kernel de beste resultaten leverde. Dit toont aan dat de methode ook werkt op verbonden, multidimensionale manifolds.
  • Hoogdimensionale setting: De tests werden uitgevoerd met een omgevingsdimensie van $d=1000$ (door ruisvariabelen toe te voegen). De skeleton-methoden waren hier robuust, terwijl andere methoden sterk degradeerden.

• Echte Data:

  • Cup Images (COIL-20): Het voorspellen van rotatiehoeken. Hier presteerde S-Lspline het beste, zelfs beter dan kNN. De auteurs suggereren dat de skelet-afstanden hier minder accuraat waren dan de lineaire structuur van het skelet zelf.
  • SDSS Data (Sterrenkunde): Het voorspellen van spectroscopische roodverschuiving op basis van fotometrische kleuren. Hier presteerde kNN en Spectral Series het beste, maar de skeleton-methoden leverden vergelijkbare resultaten. Cruciaal is dat het gegenereerde skelet een duidelijke 1-dimensionale structuur en monotoon trend in de data onthulde, wat waardevol is voor exploratieve data-analyse.

5. Betekenis en Conclusie

De "Skeleton Regression" biedt een krachtige, computatie-efficiënte en theoretisch onderbouwde oplossing voor regressieproblemen met manifold-structuur.

• Voordeel: Het omzeilt de vloek van de dimensionaliteit door de data te reduceren tot een 1-dimensionale grafische structuur, terwijl het de globale geometrie behoudt.
• Toepasbaarheid: Het is bijzonder effectief bij data met complexe, mogelijk disjuncte structuren en hoge ruisniveaus.
• Toekomst: De auteurs wijzen op kansen voor uitbreiding naar simpliciale complexen (voor hogere dimensies binnen de manifold), toepassing op stromende data (online updates van het skelet) en het gebruik van andere graf-smoothers.

Samenvattend biedt dit werk een nieuwe paradigma voor het omgaan met complexe, hoogdimensionale data door deze te vertalen naar een interpreteerbaar grafisch skelet waarop standaard statistische technieken met succes kunnen worden toegepast.