Technische Samenvatting: Voronoi Histogrammen voor Adaptieve Vectorisatie van Verwachte Persistentie Diagrammen

1. Probleemstelling

Topologische Data-Analyse (TDA) maakt gebruik van Persistente Homologie (PH) om de topologische kenmerken van puntenwolken te vangen, die worden gecodeerd als Persistentie Diagrammen (PD's). Een PD representeert topologische kenmerken (cycli) als punten $(b, d)$ in een open halfvlak $\Omega$, waarbij $b$ en $d$ de geboorte- en sterftetijden aangeven. Echter, PD's kunnen niet direct worden gebruikt als input voor standaard machine learning-algoritmen, wat vectorisatie noodzakelijk maakt.

Een aanzienlijke bottleneck bij het gebruiken van PD's is hun hoge computationele complexiteit; het verkrijgen van een PD kan $O(m^3)$ of zelfs $O(|X|^9)$ bereiken voor 1-dimensionale kenmerken. Om dit te mitigeren, werd de Verwachte Persistentie Diagram (EPD) ontwikkeld. Een EPD is een distributie van topologische kenmerken afgeleid door het middelen van de PD's van meerdere ondergesamplede deelverzamelingen van een puntenwolk. Hoewel EPD's de tijdkosten verminderen, vertrouwen bestaande vectorisatiemethoden voor EPD's (zoals Persistence Images, Persistence Silhouettes en Persistence Landscapes) op voorgedefinieerde continue punttransformatiefuncties (bijv. Gaussische kernen of landschapfuncties) en vaste discretisatiegrids. Deze methoden introduceren ontwerpkeuzes met betrekking tot gladheid, bandbreedte en gridresolutie, wat lokale massaverschillen kan vervagen of niet-optimale regio's in het $(geboorte, sterfte)$-vlak kan benadrukken.

Het artikel adresseert de behoefte aan een alternatieve vectorisatiemethode die expliciete gladde punttransformatie-modellen vermijdt en in plaats daarvan gebruikmaakt van adaptieve, datarijke partitionering om de EPD-distributie te representeren.

2. Methodologie: Voronoi-gebaseerde Representatie (Vrep)

De auteurs stellen Vrep voor, een vectorisatiemethode die de empirische EPD behandelt als een distributie van topologische kenmerken en deze representeert met behulp van histogrammen gebaseerd op Voronoi-diagrammen.

Kernmechanisme

1. Codeboek Sampling: In plaats van een vast grid construeert Vrep een verzameling willekeurige codeboeken $S$. Elk codeboek $C = \{c_1, ..., c_k\}$ bestaat uit punten gesampled uit de ondersteuning van de EPD (de verzameling topologische kenmerken).
2. Voronoi Partitionering: Voor een gegeven codeboek $C$ wordt het open halfvlak $\Omega$ verdeeld in Voronoi-cellen $V(c_i)$, waarbij elke cel punten bevat die dichter bij $c_i$ liggen dan bij enige andere $c_j$.
3. Histogram Constructie: De representatie $\Phi(\bar{\mu}, C)$ wordt gedefinieerd als de vector van genormaliseerde massa's van de EPD $\bar{\mu}$ die in elke Voronoi-cel valt:
   $$\Phi(\bar{\mu}, C) = [\bar{\mu}(V(c_1)), \bar{\mu}(V(c_2)), ..., \bar{\mu}(V(c_k))]$$
4. Aggregatie: Om de uiteindelijke representatie $\hat{\Phi}(\bar{\mu})$ te vormen, concateneert de methode histogrammen gegenereerd uit meerdere codeboeken die gesampled zijn uit de dataset.
5. Diagonaal-bewuste Variant (Vrepd): Een specifieke variant, Vrepd, bevat een Voronoi-cel gecentreerd rond de diagonaal $\partial\Omega$ (waar $b=d$). Dit is cruciaal voor het scheiden van ruis (kenmerken nabij de diagonaal) van significante topologische kenmerken.

Codeboek Sampling Strategieën

Het artikel evalueert drie strategieën voor het samplen van de punten binnen een codeboek:

• Default: Uniforme sampling uit de EPD-ondersteuning.
• Persistence-Weighted: Sampling gewogen door persistentie ($d-b$), waarbij prioriteit wordt gegeven aan significante kenmerken.
• Uniform: Sampling uit een vast rechthoek boven de diagonaal (EPD-irrelevant).

Normalisatie

De methode normaliseert de EPD naar een eenheids-$l_1$-norm ($\bar{\mu} \leftarrow \bar{\mu}/\bar{\mu}(\Omega)$). Dit behandelt de EPD als een waarschijnlijkheidsdistributie, waardoor alle EPD's dezelfde massa hebben, wat het directe gebruik van de Wasserstein-afstand voor stabiliteitsanalyse en dissimilariteitsmeting mogelijk maakt, zonder de noodzaak voor Optimal Partial Transport-metrieken.

3. Theoretische Bijdragen

Het artikel stelt theoretische garanties vast met betrekking tot de stabiliteit en de representatieve capaciteit van Vrep onder specifieke condities:

• Stabiliteitsgrenzen: De auteurs bewijzen dat Vrep stabiel is onder perturbaties van de EPD. Specifiek, als de EPD een $\Delta$-perturbatie ondergaat (kleine beweging van Dirac-massa's), is de verandering in de Vrep-representatie Lipschitz-continu met betrekking tot $\Delta$. De foutmarge hangt af van de codeboekgrootte $k$ en de eigenschappen van de dataset.
• Wasserstein-gerelateerde Grenzen: Het artikel biedt een voorwaardelijke ondergrens die de $l_1$-afstand tussen twee Vrep-vectoren relateert aan de Wasserstein-afstand ($W_1$) tussen de onderliggende EPD's.
  $$\|\Phi(\bar{\mu}, C) - \Phi(\bar{\nu}, C)\|_1 \geq \frac{W_1(\bar{\mu}, \bar{\nu}) - \text{benaderingsfouten}}{d_{max}(C)}$$
  Dit resultaat verduidelijkt dat Vrep de variaties op Wasserstein-schaal effectief behoudt wanneer het codeboek "goed opgelost" is (d.w.z. de benaderingsfout is klein ten opzichte van de scheiding van de distributies). Het is geen algemene monotone behoudgarantie, maar een voorwaardelijke consistentiebewering.

4. Experimentele Resultaten

De auteurs evalueerden Vrep en Vrepd op taken van gesuperviseerde puntenwolk-classificatie en ongesuperviseerde dimensionaliteitsreductie, waarbij ze deze vergeleken met standaardmethoden: Persistence Image (PI), Persistence Silhouettes (PS), Persistence Landscape (PL) en het end-to-end netwerk PointNet.

Classificatie Prestaties

• Datasets: Experimenten werden uitgevoerd op diverse datasets, waaronder proteïnestructuren, CAD-mechanische componenten en tijdreeksgegevens (getransformeerd naar puntenwolken via time-delay embedding).
• Resultaten: Vrep en Vrepd behaalden consequent hogere of vergelijkbare classificatienauwkeurigheid (gebruikmakend van een Random Forest classifier) vergeleken met PI, PS en PL over de meeste topologie-gevoelige datasets.
  • Op de Proteïne-dataset behaalde Vrep een nauwkeurigheid van 98,5% (tegenover 95,5% voor PI).
  • Op CAD-datasets presteerden Vrep en Vrepd beter dan andere ongesuperviseerde methoden, hoewel PI in sommige ruisinstellingen competitieve resultaten liet zien.
• Codeboek Gevoeligheid: De persistence-weighted codeboek samplingstrategie leverde vaak de beste resultaten op, vooral in ruisgevoelige omgevingen, omdat deze de representatie focust op significante topologische kenmerken.

Stabiliteit en Schaalbaarheid

• Perturbatie Stabiliteit: Experimenten op een 3D-dynamisch systeem-dataset toonden aan dat Vrep stabiel is onder Gaussische ruis-perturbaties. Interessant genoeg demonstreerde Vrepd (met de diagonaalcel) een iets hogere stabiliteit dan Vrep, waarschijnlijk door een betere scheiding van ruis nabij de diagonaal.
• Tijdcomplexiteit:
  • Vrep heeft een tijdcomplexiteit van $O(m^2tk)$ voor een dataset van grootte $m$, waarbij $t$ het aantal codeboeken is en $k$ de codeboekgrootte. Dit is kwadratisch ten opzichte van de datasetgrootte.
  • Echter, Vrep is in werkelijke runtime sneller dan PL en PS en schaalt beter met het aantal gesamplede PD's ($n$), omdat het de EPD-ondersteuning subsampleert naar een vaste grootte, terwijl PI/PS/PL elke gesamplede PD individueel moeten verwerken.
  • Hoewel PointNet (gesuperviseerd) een hoge nauwkeurigheid bereikte, biedt Vrep een competitief alternatief voor ongesuperviseerde taken (zoals dimensionaliteitsreductie) waar PointNet niet kan worden toegepast.

Ongesuperviseerde Dimensionaliteitsreductie

In een t-SNE visualisatietaak op een dynamisch systeem-dataset produceerde Vrep clusters met hogere Calinski-Harabasz (CH) indices (1751) vergeleken met PI (569) en PL (1655), wat wijst op superieure clusterseparatie.

5. Betekenis en Claims

Het artikel positioneert Vrep als een complementaire representatie in plaats van een universele vervanging voor bestaande methoden.

• Adaptief vs. Glad: De primaire bijdrage is de verschuiving van gladde, op kernen gebaseerde functionele benaderingen naar adaptieve, datarijke telling. Vrep aggregeert massa over cellen gedefinieerd door de data zelf, wat het potentieel trouwer maakt aan de empirische massatoewijzing van de EPD.
• Trade-off: De auteurs erkennen expliciet de trade-off: Vrep vat grove massatoewijzing efficiënt samen, maar is inherent verlieslatend wat betreft fijnmazige geometrie binnen een Voronoi-cel. Bij consequentie kunnen gladde methoden (zoals PI of kernmethoden) beter presteren dan Vrep wanneer de relevante topologische variatie bestaat uit fijne lokale verschuivingen of vormveranderingen binnen een cel.
• Ongesuperviseerde Bruikbaarheid: Een belangrijke betekenis is de toepasbaarheid van de methode op ongesuperviseerd leren. In tegen tegenstelling tot gesuperviseerde deep learning-benaderingen (bijv. PointNet, PersLay), vereist Vrep geen labels voor feature extractie, wat het geschikt maakt voor dimensionaliteitsreductie en clustering-taken.
• Bescheiden Claims: De auteurs beweren niet dat Vrep alle bestaande vectorisaties domineert. Ze merken op dat kernmethoden (PWGK, SWK) op specifieke datasets (bijv. CAD) beter kunnen presteren dan Vrep, maar tegen een aanzienlijk hogere computationele kosten. Het artikel concludeert dat Vrep een competitief, adaptief alternatief is dat gunstige schaling biedt met het aantal gesamplede PD's en een afwijkende benaderingsbias biedt die geschikt is voor topologie-gevoelige classificatie.