Weighted Conformal Clustering

Technisches Resümee: Gewichtetes Konformes Clustering

Problemformulierung
Clustering ist ein grundlegendes Werkzeug zur Aufdeckung latenter Strukturen in unbeschrifteten Daten, doch typische Pipelines führen meist zu „harten“ Zuweisungen von Beobachtungen zu Clustern, ohne eine rigorose Quantifizierung der Zuweisungsunsicherheit zu leisten. Während bestehende Methoden die Unsicherheit durch Bootstrapping, globale Existenztests für Cluster oder Bayes'sche Glaubwürdigkeitsintervalle adressieren, vernachlässigen sie oft die spezifische Unsicherheit, die der Zuweisung einzelner Beobachtungen innewohnt.

Neuere Arbeiten von [11] führten einen konformen Inferenzrahmen für das Clustering ein, indem sie die Label-Zuweisung als ein prädiktives Problem behandelten. Es besteht jedoch eine kritische theoretische Einschränkung: Die Kalibrierungs-Labels in [11] sind synthetisch und werden durch einen datenabhängigen Clustering-Algorithmus generiert, anstatt aus beobachteten Ground-Truth-Labels zu bestehen. Folglich wird die Voraussetzung der Austauschbarkeit, die für eine valide konforme Prädiktion erforderlich ist, verletzt, was zu potenzieller Unterdeckung führt. Die Herausforderung besteht darin, Konfidenzmengen für Cluster-Labels zu konstruieren, die trotz dieser Verteilungsabweichung zwischen den synthetischen Kalibrierungs-Labels und den unobservierten latenten Ground-Truth-Labels Garantien auf endlicher Stichprobenabdeckung bieten.

Methodik
Die Autoren schlagen ein Gewichtetes Konformes Clustering-Framework vor, das die Verteilungsabweichung adressiert, indem es das Problem als einen bedingten Label-Verteilungs-Shift formuliert. Die Kernmethodik verläuft in drei Stufen:

1. Oracle-Gewichtetes Split-Konformes Clustering:
   Die Autoren leiten zunächst ein „Oracle“-Verfahren ab, das eine exakte endliche Stichproben-Marginalabdeckung erreicht. Dieser Ansatz nutzt gewichtete konforme Prädiktion, wobei die Gewichte konstruiert werden, um die Diskrepanz zwischen der synthetischen Label-Verteilung (induziert durch den Clustering-Algorithmus) und der wahren latenten Label-Verteilung zu korrigieren. Die Gewichte sind definiert als Likelihood-Verhältnisse, welche die wahre bedingte Label-Dichte $p^*_{Y|X}$ mit den synthetischen Label-Wahrscheinlichkeiten vergleichen, die durch den Clustering-Algorithmus generiert werden. Obwohl dieses Oracle-Verfahren theoretisch fundiert ist, ist es rechnerisch nicht handhabbar, da es erfordert, die Clustering-Regel auf Leave-One-Out-augmentierten Datensätzen für jeden Kalibrierungs- und Testpunkt auszuwerten.

2. Augmentierter Kalibrierungsmechanismus:
   Um die Methode rechentechnisch handhabbar zu machen, führen die Autoren einen neuartigen augmentierten Kalibrierungsmechanismus ein. Anstatt den Clustering-Algorithmus separat auf dem Kalibrierungsdatensatz und wiederholt auf Leave-One-Out-Datensätzen anzupassen, passt der Algorithmus das Clustering-Modell einmalig auf einem augmentierten Datensatz $D_{aug} = D_{ca} \cup \{x\}$ an, wobei $D_{ca}$ der Kalibrierungsdatensatz und $x$ der Testpunkt ist. Diese einmalige Anpassung ermöglicht es, dass die synthetischen Likelihood-Terme faktorisieren und sich während der Normalisierung herauskürzen, wodurch die Gewichte zu einer punktweisen Likelihood-Ratio-Form reduziert werden. Dieser Mechanismus überbrückt Full-Conformal- und Split-Conformal-Ansätze und eliminiert die Notwendigkeit der wiederholten Neu-Anpassung.

3. Konstruktion geschätzter Gewichte:
   Da die wahre bedingte Dichte $p^*_{Y|X}$ unbekannt ist, ersetzt die Methode die Oracle-Gewichte durch geschätzte Gewichte unter Verwendung eines Soft-Classifiers $\hat{\pi}$, der auf einem separaten Trainings-Split trainiert wurde. Der finale Algorithmus (Algorithmus 1) umfasst:

   • Aufteilung der Daten in Trainings- und Kalibrierungssets.
   • Anpassung eines Clustering-Algorithmus auf dem Trainingsset, um Labels und einen Soft-Classifier zu generenieren.
   • Anpassung des Clustering-Algorithmus auf dem augmentierten Kalibrierungsset ($D_{ca} \cup \{x\}$), um synthetische Labels zu generieren.
   • Abgleich der synthetischen Labels mit den Trainings-Labels via einer Permutation $\hat{\sigma}$.
   • Berechnung der Konformitäts-Scores und Konstruktion der Konfidenzmenge unter Verwendung der geschätzten Gewichte, die aus dem Verhältnis der geschätzten bedingten Dichte zu den augmentierten Clustering-Wahrscheinlichkeiten abgeleitet werden.

Zentrale Beiträge
Das Paper leistet drei primäre Beiträge:

1. Neuartiges Framework: Es führt ein Framework zur Quantifizierung der Unsicherheit im Clustering ein, das das Problem explizit als bedingten Label-Verteilungs-Shift modelliert und gewichtete konforme Prädiktion nutzt, um die Nicht-Austauschbarkeit synthetischer Labels zu handhaben.
2. Augmentierte Kalibrierung: Es schlägt einen rechentechnisch handhabbaren „augmentierten Kalibrierungsmechanismus“ vor. Diese Innovation entfernt die Rechenlast der Leave-One-Out-Neu-Anpassung bei gleichzeitiger Beibehaltung der theoretischen Vorteile der gewichteten konformen Prädiktion und bietet ein neues Prinzip, das über das Clustering hinaus auf unüberwachtes Lernen anwendbar ist.
3. Theoretische Garantien: Die Autoren etablieren Endliche-Stichproben-Abdeckungsgrenzen für das Verfahren der geschätzten Gewichte. Der Abdeckungsverlust wird explizit durch die Total-Variation-Distanz zwischen der geschätzten bedingten Label-Verteilung und der wahren latenten Verteilung begrenzt. Im Gegensatz zu früheren Ansätzen beruht dieses Framework nicht auf „Replace-One“-Stabilitätsannahmen, da der Augmentationsmechanismus den Prozess inhärent stabilisiert.

Empirische Ergebnisse
Die vorgeschlagene Methode (Algorithmus 1) wird gegenüber der Split-Konformen-Clustering-Methode ([11]) und einer naiven Cutoff-Methode in verschiedenen Szenarien evaluiert:

• Gaußsche Mischmodelle (GMM): In sowohl niedrigdimensionalen ($R^2$) als auch hochdimensionalen ($R^{50}$) Settings bewahrt der gewichtete Ansatz eine valide Abdeckung mit informativen (kleineren) Konfidenzmengengrößen. In hohen Dimensionen unter Verwendung von Spektralem Clustering erzeugt die Split-Konforme Methode übermäßig große, uninformative Mengen, während die gewichtete Methode informativ bleibt.
• Nichtlineares Clustering: Experimente auf „Three Moons“- und „Two Concentric Circles“-Datensätzen zeigen, dass die gewichtete Methode über einen breiteren Bereich von Rauschpegeln (Varianz) hinweg informative Mengengrößen beibehält, während die Split-Konforme Methode versagt, informative Mengen zu produzieren, sobald das Clustering schwieriger wird.
• MNIST-Anwendung: Angewandt auf Deep Clustering auf dem MNIST-Datensatz quantifiziert die Methode erfolgreich die Unsicherheit. Sie erzeugt Singleton-Mengen für klare Cluster-Zentren und größere Mengen für ambivalente Grenzregionen, wodurch schwer klassifizierbare Ziffern korrekt identifiziert werden.

Bedeutung und Ansprüche
Das Paper positioniert diese Arbeit als substanziellen Schritt nach vorn für das aufstrebende Feld des konformen Clusterings. Indem die Autoren synthetische Labels als induzierenden Verteilungs-Shift behandeln, erweitern sie die Anwendbarkeit der konformen Prädiktion über die glatten parametrischen Mischmodelle hinaus, die in vorangegangenen Arbeiten ([11]) betrachtet wurden. Die Methode ist besonders signifikant für hochdimensionale und nichtlineare Clustering-Anwendungen, bei denen Standard-Konformitätsansätze Schwierigkeiten haben, informative Konfidenzmengen zu liefern. Die Autoren behaupten, dass ihr Framework einen rigoroseren und vielseitigeren Ansatz zur Quantifizierung der Unsicherheit bietet und valide Abdeckungsgarantien liefert, selbst wenn der zugrunde liegende Clustering-Algorithmus komplex oder die Datenverteilung nicht-standardmäßig ist. Das Paper schließt mit der Feststellung, dass der augmentierte Kalibrierungsmechanismus ein breiteres methodisches Prinzip darstellt, das Potenzial für Anwendungen im unüberwachten Lernen jenseits des spezifischen Kontextes des Clusterings besitzt.