Weighted Conformal Clustering

Technische Samenvatting: Weighted Conformal Clustering

Probleemformulering
Clustering is een fundamenteel instrument voor het ontdekken van latente structuren in ongelabelde data, maar standaard pipelines resulteren doorgaans in "harde" toezijgingen van observaties aan clusters zonder een rigoureuze kwantificering van de toezijgingsonzekerheid. Hoewel bestaande methoden onzekerheid adresseren via bootstrapping, globale cluster-existentietesten of Bayesiaanse geloofwaardige intervallen (credible sets), negeren zij vaak de specifieke onzekerheid die inherent is aan de toezijging van individuele observaties.

Recent werk door [11] introduceerde een conformal inference framework voor clustering door labeltoezijging te behandelen als een voorspellingsprobleem. Echter, er bestaat een kritische theoretische beperking: de kalibratielabels die in [11] worden gebruikt zijn synthetisch, gegenereerd door een datagedreven clusteringalgoritme, in plaats van geobserveerde grondwaarheid-labels (ground-truth labels). Bijgevolg wordt de vereiste uitwisselbaarheid-aanname (exchangeability assumption) voor geldige conformal prediction geschonden, wat leidt tot potentiële onderdekking (undercoverage). De uitdaging is om betrouwbaarheidssets voor clusterlabels te construeren die eindige-steekproef dekking garanderen, ondanks deze distributionele mismatch tussen de synthetische kalibratielabels en de ongeobserveerde latente grondwaarheid-labels.

Methodologie
De auteurs stellen een Weighted Conformal Clustering framework voor dat de distributionele mismatch adresseert door het probleem te formuleren als een conditionele label-distributieverschuiving. De kernmethodologie verloopt in drie stadia:

1. Oracle-Weighted Split Conformal Clustering:
   De auteurs leiden eerst een "oracle" procedure af die exacte eindige-steekproef marginale dekking bereikt. Deze aanpak maakt gebruik van weighted conformal prediction, waarbij gewichten worden geconstrueerd om de discrepantie te corrigeren tussen de synthetische labeldistributie (geïnduceerd door het clusteringalgoritme) en de ware latente labeldistributie. De gewichten worden gedefinieerd als likelihood-ratio's die de ware conditionele labeldichtheid $p^*_{Y|X}$ vergelijken met de synthetische labelkansen gegenereerd door het clusteringalgoritme. Hoewel theoretisch solide, is deze oracle procedure computationeel onuitvoerbaar omdat het vereist dat de clusteringregel op leave-one-out uitgebreide datasets wordt geëvalueerd voor elk kalibratiepunt en elk testpunt.

2. Augmented Calibration Mechanism:
   Om de methode computationeel haalbaar te maken, introduceren de auteurs een nieuw augmented calibration mechanisme. In plaats van het clusteringalgoritme apart te fitten op de kalibratieset en herhaaldelijk op leave-one-out sets, fitte het algoritme het clusteringmodel één keer op een uitgebreide dataset $D_{aug} = D_{ca} \cup \{x\}$, waarbij $D_{ca}$ de kalibratieset is en $x$ het testpunt. Deze enkele fit zorgt ervoor dat de synthetische likelihood-termen kunnen factoriseren en wegvallen tijdens normalisatie, waardoor de gewichten reduceren tot een pointwise likelihood-ratio vorm. Dit mechanisme overbrugt full-conformal en split-conformal benaderingen, en elimineert de noodzaak voor herhaaldelijk refitten.

3. Estimated-Weight Construction:
   Omdat de ware conditionele dichtheid $p^*_{Y|X}$ onbekend is, vervangt de methode de oracle-gewichten door geschatte gewichten met behulp van een soft classifier $\hat{\pi}$ die getraind is op een aparte trainingssplit. Het uiteindelijke algoritme (Algoritme 1) omvat:

   • Het splitsen van de data in trainings- en kalibratiesets.
   • Het fitten van een clusteringalgoritme op de trainingsset om labels en een soft classifier te genereren.
   • Het fitten van het clusteringalgoritme op de uitgebreide kalibratieset ($D_{ca} \cup \{x\}$) om synthetische labels te genereren.
   • Het uitlijnen van de synthetische labels met de trainingslabels via een permutatie $\hat{\sigma}$.
   • Het berekenen van conformity scores en het construeren van de betrouwbaarheidsset met behulp van de geschatte gewichten afgeleid van de ratio van de geschatte conditionele dichtheid tot de uitgebreide clusteringkansen.

Belangrijkste Bijdragen
Het artikel levert drie primaire bijdragen:

1. Nieuw Framework: Het introduceert een framework voor onzekerheidskwantificering in clustering dat de onzekerheid expliciet modelleert als een conditionele label-distributieverschuiving, waarbij gebruik wordt gemaakt van weighted conformal prediction om de niet-uitwisselbare aard van synthetische labels te hanteren.
2. Augmented Calibration: Het stelt een computationeel hanteerbaar "augmented calibration" mechanisme voor. Deze innovatie verwijdert de computationele last van leave-one-out refitting terwijl de theoretische voordelen van weighted conformal prediction behouden blijven, wat een nieuw principe biedt dat toepasbaar is op ongesuperviseerd leren buiten clustering.
3. Theoretische Garanties: De auteurs vestigen eindige-steekproef dekking-bounds voor de estimated-weight procedure. Het dekkingsverlies wordt expliciet begrensd door de total variation distance tussen de geschatte conditionele labeldistributie en de ware latente distributie. In tegen tegenstelling tot eerdere benaderingen, leunt dit framework niet op "replace-one" stabiliteitsaannames, aangezien het augmentatiemechanisme het proces inherent stabiliseert.

Empirische Resultaten
De voorgestelde methode (Algoritme 1) wordt geëvalueerd tegen de split conformal clustering methode ([11]) en een naïeve cutoff-methode over verschillende settings:

• Gaussian Mixture Models (GMM): In zowel laag-dimensionale ($R^2$) als hoog-dimensionale ($R^{50}$) settings, handhaaft de weighted aanpak een geldige dekking met informatieve (kleinere) betrouwbaarheidsset-groottes. In hoge dimensies met spectral clustering produceert de split conformal methode overdreven grote, oninformatieve sets, terwijl de weighted methode informatief blijft.
• Nietlineaire Clustering: Experimenten op "three moons" en "two concentric circles" datasets laten zien dat de weighted methode een informatieve set-grootte handhaaft over een breder bereik van ruisniveaus (variantie) vergeleken met de split conformal methode, die faalt om informatieve sets te produceren naarmate clustering moeilijker wordt.
• MNIST Toepassing: Toegepast op deep clustering op de MNIST-dataset, kwantificeert de methode succesvol de onzekerheid. Het produceert singleton sets voor duidelijke clustercentra en grotere sets voor ambigue grensregio's, waarmee moeilijk te classificeren cijfers correct worden geïdentificeerd.

Betekenis en Claims
Het artikel positioneert dit werk als een substantiële stap voorwaarts voor het opkomende veld van conformal clustering. Door synthetische labels te behandelen als een inducerende distributieverschuiving, breiden de auteurs de toepasbaarheid van conformal prediction uit voorbij de gladde parametrische mixture modellen die in eerder werk ([11]) werden overwogen. De methode is bijzonder significant voor hoog-dimensionale en nietlineaire clusteringtoepassingen waar standaard conformal benaderingen moeite hebben om informatieve betrouwbaarheidssets te bieden. De auteurs beweren dat hun framework een meer rigoureuze en veelzijdige benadering van onzekerheidskwantificering biedt, die geldige dekking garandeert, zelfs wanneer het onderliggende clusteringalgoritme complex of de datadistributie niet-standaard is. Het artikel concludeert dat het augmented calibration mechanisme een breder methodologisch principe vertegenwoordigt met potentiële toepassingen in ongesuperviseerd leren buiten de specifieke context van clustering.