Inference for Clustering: Conformal Sets for Cluster Labels

1. Problemstellung

Clustering ist eine fundamentale Aufgabe im unüberwachten Lernen, die in vielen wissenschaftlichen und industriellen Bereichen eingesetzt wird. Trotz der weitverbreiteten Nutzung fehlt es jedoch an rigorosen Methoden zur Quantifizierung der Unsicherheit bei Cluster-Zuordnungen.

• Herausforderung: Herkömmliche Clustering-Algorithmen liefern oft deterministische Labels, die keine Aussage über die Zuverlässigkeit der Zuordnung für neue Datenpunkte machen.
• Fehleranfälligkeit: Kleine Änderungen in den Daten oder der Vorverarbeitung können zu nicht reproduzierbaren Ergebnissen führen (z. B. in der Einzelzell-RNA-Sequenzierung).
• Lücken in der Literatur: Bestehende Ansätze zur Unsicherheitsquantifizierung konzentrieren sich entweder auf die Existenz von Clustern (z. B. SigClust) oder auf die Unsicherheit von Cluster-Zentren (Centroids). Es fehlt jedoch ein modellunabhängiger Rahmen, der Unsicherheit in den Cluster-Labels selbst quantifiziert.
• Spezifisches Hindernis: Da Cluster-Labels nicht beobachtet, sondern aus den Daten geschätzt werden, verletzen naive Anwendungen konformaler Inferenz die Annahme der Austauschbarkeit (Exchangeability). Dies führt zu einer starken Unterdeckung (Under-coverage), d. h., die Konfidenzmengen sind zu klein, um das wahre Label mit der gewünschten Wahrscheinlichkeit zu enthalten.

2. Methodik: Split Conformal Clustering mit Stochastischen Labels

Die Autoren schlagen einen neuen Rahmen vor, der auf Split Conformal Prediction basiert, jedoch speziell für das unüberwachte Lernen adaptiert wird.

Kernidee: Stochastische Clustering-Algorithmen

Um das Problem der fehlenden Austauschbarkeit zu lösen, führen die Autoren stochastische Clustering-Labels ein. Anstatt deterministische Labels zu verwenden, werden Labels aus weichen (soft) Wahrscheinlichkeitsverteilungen (z. B. Posterior-Wahrscheinlichkeiten aus Mischmodellen) stochastisch gezogen. Dies simuliert die Unsicherheit der Zuordnung direkt im Labeling-Prozess.

Der Algorithmus (Algorithm 1)

Das Verfahren läuft wie folgt ab:

1. Aufteilung: Die Daten werden zufällig in Trainings- ($I_{tr}$) und Kalibrierungs- ($I_{ca}$) Mengen aufgeteilt.
2. Stochastisches Clustering: Auf beiden Mengen wird ein stochastischer Clustering-Algorithmus angewendet, der für jeden Datenpunkt $x$ eine Wahrscheinlichkeitsverteilung über die $K$ Cluster liefert. Daraus werden stochastische Labels $\{Y_i\}$ gezogen.
3. Klassifikator-Training: Ein weicher Klassifikator $\hat{\pi}$ (z. B. SVM oder Random Forest) wird auf den Trainingsdaten mit den stochastischen Labels trainiert, um für beliebige Eingaben Wahrscheinlichkeitsvektoren vorherzusagen.
4. Alignment: Da die Cluster-Labels in Trainings- und Kalibrierungsdaten durch Permutationen unterschiedlich sein können, wird eine optimale Permutation $\hat{\sigma}$ gefunden, die die Diskrepanz zwischen den vorhergesagten und den stochastischen Labels in der Kalibrierungsmenge minimiert (Lineares Zuordnungsproblem).
5. Konformitäts-Scores: Für die Kalibrierungsdaten werden Konformitäts-Scores berechnet (basierend auf dem generalisierten inversen Quantil-Score von Romano et al., 2020).
6. Konfidenzmengen: Für einen neuen Testpunkt $x$ wird eine Konfidenzmenge $\hat{C}(x)$ konstruiert, die alle Labels enthält, deren Score unter einem bestimmten empirischen Quantil der Kalibrierungsscores liegt.

3. Theoretische Garantien

Die Autoren leiten eine endliche Stichproben-Untergrenze für die Abdeckungswahrscheinlichkeit her. Diese zeigt, dass die Gültigkeit der Konfidenzmengen von zwei Eigenschaften des verwendeten Clustering-Algorithmus abhängt:

1. Konsistenz (Consistency): Der geschätzte weiche Label-Verteilung $\hat{\gamma}_n$ muss gegen die wahre bedingte Verteilung $\gamma^*$ konvergieren (gemessen durch den $L_1$-Fehler).
2. Stabilität (Replace-One Stability): Der Algorithmus muss stabil sein, d. h., das Entfernen oder Ersetzen eines einzelnen Datenpunkts darf die gemeinsame Verteilung der geschätzten Labels nur geringfügig verändern.

Ergebnisse:

• Endliche Stichprobe: Die Unterdeckung wird durch die Summe aus Konsistenzfehler und Stabilitätsfehler begrenziert (Satz 1).
• Asymptotische Abdeckung: Unter milden Bedingungen (Konsistenz und asymptotische Replace-One-Invarianz) konvergiert die Abdeckungswahrscheinlichkeit gegen das gewünschte Niveau $1-\alpha$.
• Parametrische Mischmodelle: Es wird bewiesen, dass korrekt spezifizierte parametrische Mischmodelle (z. B. Gaußsche Mischmodelle) diese Bedingungen erfüllen, wenn die Parameterschätzer konsistent sind.

4. Ergebnisse und Evaluation

Simulationen

Die Methode wurde an synthetischen Daten (Gaußsche Mischmodelle GMM und Gamma-Mischmodelle GaMM) getestet und mit zwei naiven Ansätzen verglichen:

1. Naiver Split Conformal (mit harten Labels): Führt zu schwerer Unterdeckung, da die Deterministik die Austauschbarkeit bricht.
2. Cutoff-Methode (Schwellenwert auf weichen Labels): Führt zu überkonservativen, uninformative großen Mengen (Over-coverage), da sie keine Kalibrierung der Unsicherheit vornimmt.

Ergebnis: Der vorgeschlagene Algorithmus (Split CC mit stochastischen Labels) erreicht die gewünschte Abdeckung (z. B. 90%) und liefert gleichzeitig informative Konfidenzmengen, die in unsicheren Regionen (Grenzen zwischen Clustern) größer sind und in sicheren Regionen klein (Singletons) bleiben.

Anwendung: Single-Cell RNA-Sequenzierung

Die Methode wurde auf einen PBMC-3K Datensatz (periphere Blutmononukleäre Zellen) angewendet, um Zelltypen zu identifizieren.

• Ergebnis: Die Konfidenzmengen spiegeln die biologische Realität wider. Gut definierte Zelltypen (z. B. B-Zellen, NK-Zellen) erhielten fast immer Singleton-Konfidenzmengen (hohe Sicherheit). Zelltypen mit fließenden Übergängen oder ähnlichen Transkriptom-Profilen (z. B. T-Zellen, Monozyten) erhielten größere Mengen, was die inhärente Unsicherheit der Zuordnung korrekt quantifiziert.
• Visualisierung: Die Methode erlaubt es, Regionen im Merkmalsraum zu identifizieren, in denen die Cluster-Zuordnung zuverlässig ist, und solche, in denen Mehrdeutigkeiten bestehen.

5. Bedeutung und Beiträge

• Pionierarbeit: Dies ist einer der ersten erfolgreichen Versuche, konformale Inferenz auf ein rein unüberwachtes Lernproblem anzuwenden.
• Lösung des Austauschbarkeitsproblems: Die Einführung stochastischer Labels als Brücke zwischen geschätzten Clustern und konformaler Inferenz ist ein entscheidender methodischer Durchbruch.
• Praktische Anwendbarkeit: Die Methode ist modellagnostisch (kann mit verschiedenen stochastischen Clustering-Algorithmen kombiniert werden) und liefert interpretierbare Unsicherheitsmaße, die für kritische Entscheidungen in der Biomedizin und anderen Bereichen essenziell sind.
• Theoretische Fundierung: Die Arbeit liefert eine klare theoretische Roadmap, welche Eigenschaften ein Clustering-Algorithmus besitzen muss, um verlässliche Inferenz zu ermöglichen (Konsistenz und Stabilität).

Zusammenfassend bietet das Paper ein rigoroses Werkzeug, um die Zuverlässigkeit von Clustering-Ergebnissen zu quantifizieren und damit die Interpretierbarkeit und Robustheit unüberwachter Lernverfahren in der Praxis erheblich zu verbessern.