When One Point Is Not Enough: Addressing Ambiguous Instances in Dimensionality Reduction by Splitting

Technische Samenvatting: Aanpak van Ambigue Instanties in Dimensiereductie door Splitsing

Probleemdefinitie
Dimensiereductie (DR) is een fundamenteel hulpmiddel voor het visualiseren van hoogdimensionale data, maar is inherent een verliesgevend proces. Hoewel de bestaande literatuur diverse vervormingen heeft gedocumenteerd, zoals het scheuren van manifolds, identificeert dit artikel een eerder over het hoofd gezien bron van visuele artefacten: ambigue instanties. Dit zijn datapunten die sterk vergelijkbaar zijn met meerdere, onderling dissimile buurten in de hoogdimensionale ruimte.

Standaard DR-methoden mappingen elke data-instantie af op één enkel punt in de visuele ruimte. Bijgevolg kan een ambigue instantie niet trouw haar lidmaatschap van meerdere distincte buurten gelijktijdig vertegenwoordigen. Ze wordt gedwongen naar één enkele locatie, wat resulteert in partiële buurtembedding. In deze toestand lijkt de instantie slechts tot één buurt (of geen enkele) te behoren, waardoor haar ware relatie tot andere dissimile groepen wordt verduisterd. Dit artefact is bijzonder problematisch voor analyses op instantieniveau, zoals Explainable AI (XAI) of single-cell biologie, waar het begrijpen van de precieze buurtstructuur cruciaal is. Bestaande metrieken zoals betrouwbaarheid en continuïteit falen in het onderscheiden van partiële buurtembedding van andere vervormingen, omdat ze opereren op de uiteindelijke embedding zonder toegang tot de onderliggende data-ambiguïteit.

Methodologie
De auteurs stellen een op grafen gebaseerde aanpak voor om deze ambiguïteiten te identificeren en op te lossen door ambigue instanties te "splitsen" in meerdere punten, waarbij elk punt binnen zijn respectieve buurt wordt geplaatst. De methodologie volgt het twee-fase DR-kader (relatie en mapping) geïntroduceerd door Paulovich et al.:

1. Grafconstructie en Versparring:

   • De hoogdimensionale relaties worden gemodelleerd als een ongerichte gewogen graaf $G$.
   • Om betekenisvolle buurtstructuren bloot te leggen en overbodige randen te verwijderen die worden veroorzaakt door toevallige nabijheid, passen de auteurs spectrale versparring toe met het Spielman-Srivastava-algoritme. Dit levert een gereduceerde graaf $\bar{G}$ op die de structurele en algebraïsche eigenschappen van het origineel behoudt, terwijl het zwakke verbindingen verwijdert.

2. Identificatie van Ambigue Instanties:

   • Ambiguïteit wordt topologisch gedefinieerd. De auteurs passen het concept van Lokale Articulatiepunten (LAP's) aan. Een hoekpunt wordt beschouwd als een LAP als de verwijdering ervan het aantal samenhangende componenten binnen een lokale $r$-stap geïnduceerde buurt verhoogt.
   • Een instantie wordt ambigu geacht als het een LAP is in de verspaarde graaf $\bar{G}$. Dit geeft aan dat de instantie disjuncte buurten verbindt die anders gescheiden zouden zijn.
   • Lemma 3.1 wordt gebruikt om de berekening te optimaliseren: als een hoekpunt geen LAP is bij een bepaalde straal $r$, kan het geen LAP zijn bij een grotere straal $r' > r$.

3. Vertex-splitsing en Beslissingsregels:

   • Zodra een ambigue vertex $v_i$ is geïdentificeerd, wordt deze gesplitst in $K$ kopieën, waarbij $K overeenkomt met het aantal samenhangende componenten dat overblijft nadat $v_i$ uit zijn lokale buurt is verwijderd.
   • Beslissingsregels: Niet alle potentiële splitsingen worden uitgevoerd. De aanpak filtert het volgende eruit:
     • LAP-LAP-verbindingen: Als een rand twee buurten overbrugt en beide eindpunten LAP's zijn, wordt de splitsing onderdrukt om het creëren van kunstmatige isolatie te voorkomen.
     • Zwakke verbindingen: Een door de gebruiker gedefinieerde drempelwaarde $\tau_w$ (verhouding van verbindingsterkte tot de sterkste component) filtert splitsingen eruit waarbij de verbinding met een buurt te zwak is om betekenisvol te zijn. Dit voorkomt het creëren van visueel geïsoleerde punten door onvoldoende aantrekkingskrachten.

4. Mapping en Visualisatie:

   • De gemodificeerde graaf, met gesplitste vertices, wordt geprojecteerd in de visuele ruimte met behulp van standaard lokale DR-technieken (bijvoorbeeld UMAP of ForceAtlas2).
   • Visuele codering: Gesplitste instanties worden weergegeven als distincte markers (bijvoorbeeld kruisen) die met stippellijnen zijn verbonden met hun oorspronkelijke positie of met elkaar, waardoor analisten de meerdere buurtlidmaatschappen van een enkel datapunt kunnen traceren.

Belangrijkste Bijdragen

• Definitie van Partiële Buurtembedding: Het artikel introduceert en definieert formeel dit specifieke artefact dat voortkomt uit ambigue instanties, en onderscheidt dit van algemene DR-vervormingen.
• Graftheoretische Detectie: Het presenteert een methode om ambigue instanties te identificeren met behulp van Lokale Articulatiepunten op verspaarde buurtgrafen.
• Splitsingsmechanisme: De auteurs stellen een concrete aanpak voor met bijna lineaire tijdscomplexiteit om ambigue instanties te splitsen, waarbij ze deze repliceren in de projectie om meerdere buurtlidmaatschappen weer te geven.
• Empirische Validatie: De aanpak wordt gedemonstreerd op diverse datasets (SVHN, MNIST, tekstcorpora en single-cell RNA-sequencing), waarbij wordt aangetoond dat het verborgen buurtlidmaatschappen onthult die niet zichtbaar zijn in standaardprojecties.

Resultaten

• Kwalitatieve Inzichten: In de SVHN-dataset werd een verkeerd geclassificeerd cijfer '1' (voorspeld als '7') in standaard UMAP getoond als behorend tot uitsluitend de '7'-buurt. De voorgestelde aanpak splitste de instantie, waardoor zijn gelijktijdige gelijkenis met de '1'-buurt werd onthuld, en zo de ambiguïteit van de fout van de classifier verklaarde. Evenzo bleek in tekstdata een paper over "ILP-gestuurde modellen voor toxicologie" tot zowel ILP- als Case-Based Reasoning (CBR)-clusters te behoren, een dualiteit die in standaardprojecties werd verduisterd.
• Kwantitatieve Analyse:
  • Impact van Versparring: Experimenten die bewaarde $k$-dichtstbijzijnde buren ($k$NN) maten, toonden aan dat spectrale versparring lokale buurtstructuren behoudt die vergelijkbaar zijn met de originele graaf (verhoudingen dicht bij 1 voor de meeste datasets), hoewel enige variatie werd waargenomen in single-cell data met hoge intrinsieke dimensionaliteit.
  • Beperkingen van Metrieken: Standaard metrieken (betrouwbaarheid en continuïteit) bleken inefficiënt in het identificeren van ambigue instanties, aangezien deze punten vergelijkbaar zijn verdeeld als niet-ambigue punten over de metriekverdelingen.
  • Parametergevoeligheid: Het verhogen van het aantal buren in de initiële graaf verlaagde over het algemeen het aantal gedetecteerde splitsingen, aangezien verhoogde connectiviteit buurten overbrugt die anders disjunct zouden lijken.

Betekenis en Beweringen
Het artikel betoogt dat het herkennen van ambiguïteit essentieel is voor het interpreteren van fijnkorrelige lokale structuren in DR. De auteurs beweren dat het niet rekening houden met ambigue instanties kan leiden tot onvolledige of onjuiste interpretaties, met name in domeinen zoals XAI en biologie waar context op instantieniveau vitaal is. Door deze instanties te splitsen, biedt de methode een trouwere representatie van de hoogdimensionale topologie van de data, waarbij "voorheen verborgen buurtlidmaatschappen" worden onthuld. Het werk suggereert dat huidige DR-kwaliteitsmetrieken ontoereikend zijn voor dit specifieke type artefact en dat toekomstige evaluatiekaders rekening moeten houden met datagedreven ambiguïteit in plaats van alleen mapping-geïnduceerde instabiliteit.