📊 statistics

Prototype Selection Using Topological Data Analysis

Dit artikel introduceert twee op topologische data-analyse gebaseerde prototype-selectiemethoden, TPS en BoundaryTPS, die gebruikmaken van multi-schaal persistentiestructuren om beslissingsgrenzen en klasseproporties effectief te behouden, terwijl ze een superieure stabiliteit en afwijkende operationele kenmerken vertonen in vergelijking met bestaande klassieke baselines.

Oorspronkelijke auteurs: Jordan Eckert, Elvan Ceyhan, Henry Schenck

Gepubliceerd 2026-06-02

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Jordan Eckert, Elvan Ceyhan, Henry Schenck

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een robot probeert te leren om verschillende soorten fruit te herkennen. Je hebt een enorme doos met 10.000 appels, sinaasappels en bananen. Als je de robot elk stuk fruit laat zien, zal het eeuwig duren voordat hij heeft geleerd, en hij kan in de war raken door een paar beschadigde of vreemd gevormde exemplaren (ruis).

Prototype Selectie is de kunst van het kiezen van een kleine, perfecte "representatieve" handvol fruit uit die enorme doos. Het doel is om de robot slim te houden, maar ook snel.

Lange tijd hebben wetenschappers verschillende manieren gehad om deze handvol fruit te kiezen:

De "Schoonmaker": Gooit het beschadigde fruit weg.
De "Clusteraar": Kiest het gemiddeld uitziende fruit uit een groep.
De "Optimizer": Probeert de wiskundig perfecte weinige te vinden.

Maar deze methoden kijken naar het fruit slechts als punten in de ruimte. Ze begrijpen de vorm van het probleem niet echt (specifiek: waar de appels ophouden en de sinaasappels beginnen (de "beslissingsgrens")).

Het Nieuwe Idee: Topologische Data Analyse (TDA)

Dit artikel introduceert twee nieuwe methoden, TPS en BoundaryTPS, die gebruikmaken van een tak van de wiskunde genaamd Topologische Data Analyse.

Denk aan TDA niet als het kijken naar individuele stukken fruit, maar als het kijken naar de vorm van de hele stapel.

Als je een stapel fruit hebt met een gat in het midden (zoals een donutvorm), ziet TDA de "lus" of het "gat".
Als het fruit gewoon een solide massa is, ziet TDA een "solide massa".

De auteurs stellen dat het belangrijkste deel van leren de grens is — de rommelige, complexe rand waar de ene klasse fruit overgaat in de andere. Hun nieuwe methoden zijn ontworpen om specifiek de vorm van deze randen te behouden.

De Twee Nieuwe Methoden

1. BoundaryTPS (De "Grenswachter")

Hoe het werkt: Stel je voor dat je een grens tussen twee landen bewaakt. Je wilt de mensen die vlak aan de grenslijn wonen behouden, omdat zij het terrein het beste kennen. Je geeft minder om de mensen die diep in het midden van het land wonen.
De Truc: Deze methode wijst een "gewicht" toe aan elk datapunt. Punten nabij de beslissingsgrens krijgen een "laag gewicht" (ze komen vroeg in het selectieproces terecht). Punten diep binnen een klasse krijgen een "hoog gewicht" (ze worden vertraagd).
Het Resultaat: Het filtert de data zodat de uiteindelijke handvol prototypes compact rond de beslissingsgrenzen is gepakt, waardoor de complexe vorm van de rand behouden blijft.

2. TPS (De "Tweestaps-Verkenner")

Hoe het werkt: Deze methode hanteert een tweestapsbenadering.
- Stap 1: Het kijkt naar de grens tussen klassen (zoals het mengen van appels en sinaasappels) om de "rand"-punten te vinden.
- Stap 2: Het kijkt naar de overlevers van Stap 1 en kiest de "typische" punten die het midden van de fruitstapels vertegenwoordigen.
Het Resultaat: Het levert een gebalanceerd team op: enkele experts op de rommelige randen, en enkele experts in het typische, veilige binnenste.

Wat Hebben Ze Gevonden?

De auteurs hebben deze nieuwe methoden getest tegen zeven oude, klassieke methoden met behulp van 15 real-world datasets (zoals medische dossiers, satellietbeelden en chemische analyse van wijn). Dit is wat er gebeurde:

Vormbehoud (De "Kaart"-test):
- Als je een kaart van een stad neemt en de meeste straten verwijdert, wil je er nog steeds de belangrijkste lussen en wijken in kunnen zien.
- BoundaryTPS was het beste in het intact houden van de "lussen" en "gaten" van de originele data. Het behield de topologische vorm beter dan enige andere geteste methode.
- TPS was een nipte tweede.
- De oude methoden maakten deze vormen vaak plat, waardoor de complexe structuur van de data verloren ging.
Stabiliteit (De "Herhaalbaarheid"-test):
- Als je de data lichtjes door elkaar husselt (zoals een kaartspel anders delen), zul je dan dezelfde handvol prototypes kiezen?
- TPS was het meest stabiel. Het koos bijna elke keer dezelfde mensen, zelfs wanneer de data licht veranderde.
- Veel van de oude methoden waren "springerig" en kozen totaal andere sets mensen, alleen maar omdat de data een klein beetje werd gehusseld.
Prestaties (De "Toetsscore"-test):
- Maakten deze nieuwe methoden de robot slimmer?
- Verrassing: Ze waren competitief, maar niet de absolute winnaars. De oude methoden (zoals K-Means of SPOTGreedy) behaalden vaak iets hogere scores op de test.
- Echter, de nieuwe methoden waren erg goed in het omgaan met ongebalanceerde data (waarbij één klasse fruit zeldzaam is). Ze gooiden de zeldzame vruchten niet per ongeluk weg.
Snelheid:
- Beide nieuwe methoden zijn snel. Ze schalen goed, wat betekent dat ze niet exponentieel langzamer worden naarmate de dataset groter wordt.

De Kern van het Verhaal

Dit artikel beweert niet dat deze nieuwe methoden je altijd de hoogste toetsscore zullen geven. In plaats daarvan beweert het dat ze een andere soort waarde bieden:

Ze zijn stabieler (je krijgt elke keer hetzelfde resultaat).
Ze zijn beter in het behouden van de vorm van de grenzen van de data.
Ze kunnen van nature omgaan met ongebalanceerde data zonder dat er speciale trucjes nodig zijn.

Als je een methode voor datasetreductie nodig hebt die betrouwbaar is, de complexe geometrie van je data behoudt en niet in de war raakt door kleine veranderingen in de input, dan zijn deze topologische methoden een krachtig nieuw instrument in de gereedschapskist.

Technische Samenvatting: Prototype Selectie middels Topologische Data-Analyse

Probleemstelling
Moderne classificatie-pipelines worden vaak gehinderd door knelpunten waarbij de omvang van de trainingsset, in plaats van de kosten van een enkele voorspelling, de inferentietijd domineert. Hoewel parametrische modellen (bijv. SVM's, Random Forests) de last verschuiven naar de trainingstijd, schalen zij nog steeds met het aantal trainingsinstanties. Prototype selectie pakt dit aan door de trainingsset te comprimeren tot een kleine, representatieve subset. Bestaande taxonomieën van prototype selectie—inclusief condensatie, editie, hybride, competentie-gebaseerde en optimalisatie-gebaseerde families—werken zonder een expliciete representatie van de topologische structuur van de data. Bijgevolg wordt de geometrie van tussen-klasse beslissingsgrenzen, die complexe structuren kunnen vertonen over meerdere ruimtelijke schalen, slechts impliciet gevangen. Dit artikel adresseert de kloof in het benutten van de multi-schaal topologische structuur van data als een direct criterium voor prototype selectie.

Methodologie
De auteurs introduceren twee varianten van een Topologische Prototype Selector (TPS) die gebruikmaken van persistente homologie, een kerninstrument in Topologische Data-Analyse (TDA), om prototypes te identificeren en te behouden. Beide methoden vertrouwen op de Rips-filtratie, maar verschillen in de wijze waarop zij boundary-informatie coderen:

Boundary-Conscious Topological Prototype Selector (BoundaryTPS):
- Mechanisme: Dit is een eenfasige methode die gebruikmaakt van een vertex-gewogen Rips-filtratie. Het wijst gewichten toe aan doelklasse-punten op basis van hun nabijheid tot niet-doelklassen (specifiek, de som van de afstanden tot de $k$ dichtstbijzijnde niet-doel buren).
- Proces: Punten nabij de beslissingsgrens ontvangen lage gewichten en komen vroeg in de filtratie, terwijl binnenste punten hoge gewichten ontvangen en worden vertraagd. Dit zorgt ervoor dat de topologie van de grensregio op fijnere schalen wordt opgelost.
- Selectie: Prototypes worden geselecteerd door het identificeren van persistentie-kenmerken op een specifiek kwantiel van de lifetime-distributie. Een tolerantieparameter $\tau$ maakt het mogelijk om een venster van kenmerken rond het doelkwantiel te selecteren om de robuustheid te verbeteren.
Topological Prototype Selector (TPS):
- Mechanisme: Dit is een twee-fasige methode die boundary-informatie impliciet codeert door een gemengde puntenwolk te construeren die zowel doel- als niet-doel observaties bevat.
- Fase 1 (Boundary-Neighborhood): Een standaard Rips-filtratie wordt gebouwd op de gemengde wolk om de tussen-klasse topologische structuur te vangen. Kenmerken worden geselecteerd op basis van een kwantiel van de lifetime-distributie, en de overlevende doelklasse-punten worden behouden.
- Fase 2 (Interior): Een tweede Rips-filtratie wordt gebouwd op de overlevers uit Fase 1 om de binnen-klasse topologie te vangen. Kenmerken worden geselecteerd op basis van de gemiddelde lifetime om typische binnenste samples te behouden.
- Resultaat: De definitieve set combineert grens-relevante punten uit Fase 1 met binnenste-ondersteunende punten uit Fase 2.

Belangrijkste Bijdragen

Nieuw Criterium: Het artikel introduceert persistente homologie als een criterium voor prototype selectie, een capaciteit die voorheen niet in dit domein is benut.
Duale Realisaties: Het presenteert TPS en BoundaryTPS, en demonstreert dat het coderen van boundary-informatie via gemengde-klasse filtraties (TPS) versus vertex-gewichten (BoundaryTPS) empirisch verschillende specialisaties leidt.
Uitgebreide Benchmarking: Beide methoden worden geëvalueerd tegen zeven klassieke baselines (CNN, CNN+ENN, DROP3, ICF, IB3, KMeans, SPOTGreedy) over vijftien real-world datasets en zes downstream classifiers onder geneste cross-validatie.
Topologische Preservatie: De studie toont aan dat topologische methoden de $H_1$ persistentie-diagram structuur aanzienlijk beter behouden dan dichtheid-gebaseerde of keten-beslissing baselines.
Stabiliteit: Beide methoden vertonen een hogere selectie-stabiliteit (gemeten door fold-to-fold Jaccard gelijkenis) dan enige geteste keten-beslissing selector.
Klassenimbalans: De methoden erven de proporties van de bronset zonder dat hiervoor label-bewuste mechanismen nodig zijn.

Resultaten

Topologische Getrouwheid: BoundaryTPS bereikt de laagste gemiddelde Friedman rang (2.00) op $H_1$ Wasserstein-1 afstand, waarmee het vijf van de zeven baselines significant verslaat. TPS rangschikt derde (3.60). Beide methoden clusteren aan de top van het prestatiespectrum voor het behoud van lus-structuren ( $H_1$ ), terwijl klassieke methoden deze kenmerken vaak afvlakken.
Selectie-stabiliteit: TPS bereikt de hoogste gemiddelde Jaccard gelijkenis (0.225) over folds, gevolgd door BoundaryTPS (0.202). Beiden zijn significant stabieler dan keten-beslissing methoden zoals CNN+ENN (0.057) en DROP3 (0.080).
Classificatie Prestaties: Op geaggregeerde Geometric Mean (G-Mean) zijn de topologische methoden competitief maar niet leidend. SPOTGreedy en KMeans bereiken de hoogste geaggregeerde G-Mean (0.84). TPS en BoundaryTPS bereiken respectievelijk 0.79 en 0.76. Het artikel merkt op dat hoewel zij de rauwe classificatie-nauwkeurigheid niet domineren, zij een uniek en waardevol werkpunt bieden in de design space, met name wat betreft structurele preservatie en stabiliteit.
Schaalbaarheid: Empirisch gezien schalen beide methoden sub-kwadratisch in steekproefomvang.

Betekenis en Claims
Het artikel claimt dat de primaire betekenis van dit werk ligt in het verschuiven van het paradigma van prototype selectie van louter geometrische of statistische heuristieken naar een framework dat geworteld is in multi-schaal topologische invarianten. De auteurs stellen dat hoewel bestaande methoden impliciet een boundary-proximity principe veronderstellen, zij er niet in slagen de complexe, multi-schaal structuur van beslissingsgrenzen op te lossen. Door expliciet gebruik te maken van persistente homologie, bieden de voorgestelde methoden een gefundeerde manier om punten te behouden die de topologische "vorm" van de data definiëren, in het bijzonder de lussen en grenzen die vaak verloren gaan bij dichtheid-gebaseerde reductie.

De auteurs karakteriseren de resultaten bescheiden: de topologische methoden presteren niet universeel beter dan bestaande baselines in downstream classificatie-nauwkeurigheid (G-Mean), maar zij bezetten een unieke en waardevolle regio in de design space door superieure topologische preservatie en selectie-stabiliteit te bieden. Het werk suggereert dat voor toepassingen waar de structurele integriteit van de beslissingsgrens of de reproduceerbaarheid van het selectieproces van essentieel belang is, topologische criteria een distinct en effectief alternatief bieden voor klassieke benaderingen.