Conformal Prediction for Long-Tailed Classification

Die Autoren stellen neue Methoden für die konforme Vorhersage bei stark unausgewogenen Klassendistributionen vor, die durch eine prevalence-adjusted softmax-Funktion und eine Interpolation zwischen marginaler und klassenbedingter Abdeckung einen optimalen Kompromiss zwischen der Größe der Vorhersagemengen und der Abdeckung seltener Klassen ermöglichen.

Das Wesentliche

🌿 Das Problem: Der „Lange Schwanz" und die seltene Pflanze

Stellen Sie sich vor, Sie sind ein Hobby-Gärtner und finden eine unbekannte Pflanze im Wald. Sie machen ein Foto und laden es in eine App hoch. Die App soll Ihnen sagen, was für eine Pflanze das ist.

Das Problem ist: In der Natur gibt es Tausende von Pflanzenarten.

• Einige sind extrem häufig (wie die Löwenzahn). Die App kennt diese auswendig.
• Andere sind extrem selten (wie eine seltene Orchidee). Die App hat vielleicht nur ein einziges Foto davon in ihrer Datenbank gesehen.

In der Statistik nennt man das eine „long-tailed" (langschwänzige) Verteilung. Wenn man eine KI trainiert, lernt sie die häufigen Pflanzen super, aber bei den seltenen macht sie oft Fehler oder ist unsicher.

🎯 Die Lösung: Der „Sicherheitskorb" statt einer einzelnen Antwort

Früher sagten KIs: „Das ist zu 90 % ein Löwenzahn." Wenn sie sich aber bei einer seltenen Orchidee irren, ist das katastrophal.

Diese Forscher schlagen vor: Geben Sie keine einzelne Antwort, sondern eine Liste!
Statt zu sagen: „Das ist eine Orchidee", sagt die App: „Es könnte eine Orchidee, eine Lilie oder eine Orchidee-Art X sein."

Das nennt man einen Vorhersagekorb (Prediction Set).

• Vorteil: Die echte Antwort ist mit hoher Wahrscheinlichkeit in der Liste enthalten.
• Nachteil: Wenn die Liste zu lang ist (z. B. „Es könnte eine der 500 Pflanzenarten sein"), ist sie nutzlos. Niemand hat Zeit, 500 Bilder zu vergleichen.

⚖️ Das Dilemma: Zu klein oder zu groß?

Bisher gab es nur zwei extreme Optionen für diese Listen:

1. Die „Kleine Liste" (Standard-Methode):
   Die App gibt nur 1–2 Namen aus.

   • Problem: Bei seltenen Pflanzen ist die Liste oft falsch oder leer. Die seltenen Arten werden ignoriert, weil die KI sie nicht gut genug kennt.
   • Analogie: Ein Detektiv, der nur den wahrscheinlichsten Verdächtigen nennt. Wenn er sich bei einem seltenen Fall irrt, ist der Täter auf freiem Fuß.

2. Die „Riesige Liste" (Klassenweise Methode):
   Um sicherzugehen, dass auch die seltenen Pflanzen dabei sind, gibt die App eine riesige Liste aus.

   • Problem: Die Liste ist so lang, dass niemand sie durchgehen kann.
   • Analogie: Der Detektiv nennt alle 10.000 Einwohner der Stadt als Verdächtige. Technisch gesehen ist der Täter dabei, aber es bringt nichts.

✨ Die neue Idee: Der „Goldene Mittelweg"

Die Forscher haben zwei neue Methoden entwickelt, die das Beste aus beiden Welten verbinden: Kleine Listen, die aber auch die seltenen Pflanzen nicht vergessen.

Methode 1: Der „Angepasste Wahrscheinlichkeits-Rechner" (PAS)

Stellen Sie sich vor, die KI berechnet normalerweise nur, wie ähnlich eine Pflanze den Bildern in ihrer Datenbank ist.

• Bei häufigen Pflanzen (Löwenzahn) ist das Bild klar.
• Bei seltenen Pflanzen (Orchidee) ist das Bild unscharf.

Die neue Methode PAS sagt der KI: „Hey, vergiss nicht, wie selten diese Pflanze eigentlich ist!"

• Wenn die KI eine seltene Orchidee sieht, die sie nur zu 40 % sicher findet, sagt die normale KI: „Nicht in die Liste!"
• Die neue PAS-Methode sagt: „Aber warte, Orchideen sind so selten, dass wir sie trotzdem in die Liste aufnehmen müssen, um sicherzugehen."

Das Ergebnis: Die Liste bleibt kurz, aber die seltenen Pflanzen werden nicht mehr systematisch übersehen. Es ist, als würde man einem Detektiv sagen: „Achte besonders auf die seltenen Verdächtigen, auch wenn du nicht zu 100 % sicher bist."

Methode 2: Der „Dimmer-Schalter" (INTERP-Q)

Stellen Sie sich zwei Schalter vor:

• Schalter A: „Nur die häufigsten Pflanzen" (Kleine Liste, schlechte Abdeckung der Seltenen).
• Schalter B: „Alle möglichen Pflanzen" (Riesige Liste, perfekte Abdeckung).

Die neue Methode INTERP-Q ist wie ein Dimmer zwischen diesen beiden Schaltern. Der Nutzer kann einen Regler bewegen:

• „Ich will eine sehr kurze Liste, aber ich will, dass die seltenen Pflanzen zu 80 % dabei sind."
• „Ich will eine etwas längere Liste, damit die seltenen Pflanzen zu 99 % dabei sind."

Man kann also genau einstellen, wie viel Arbeit man investieren möchte, um die seltenen Fälle zu finden.

🌍 Warum ist das wichtig?

Das klingt nach einer kleinen technischen Verbesserung, hat aber große Auswirkungen:

1. Artenschutz: Wenn wir seltene, bedrohte Pflanzenarten in der Natur identifizieren wollen, dürfen wir sie nicht übersehen. Diese Methode hilft, diese „Nadeln im Heuhaufen" zu finden, ohne den Heuhaufen zu durchwühlen.
2. Medizin: Bei der Diagnose seltener Krankheiten ist es wichtiger, den seltenen Fall zu erkennen, als den häufigen Schnupfen perfekt zu klassifizieren.
3. Vertrauen: Nutzer können der KI mehr vertrauen, weil sie wissen: „Wenn die KI eine seltene Pflanze in die Liste aufnimmt, hat sie sich das wirklich überlegt und nicht nur geraten."

Zusammenfassung in einem Satz

Die Forscher haben eine neue Art entwickelt, KI-Listen zu erstellen, die kurz und übersichtlich bleiben, aber gleichzeitig sorgenfältig darauf achten, dass auch die seltenen und wichtigen Fälle nicht übersehen werden, indem sie die KI „leise" anweisen, die Seltenheit der Objekte mitzudenken.

Technische Zusammenfassung

1. Problemstellung

Das Paper adressiert das Problem der Erstellung von Vorhersagemengen (prediction sets) im Kontext von Klassifikationsproblemen mit stark langschwänzigen Klassenverteilungen (long-tailed distributions). Solche Verteilungen sind in realen Szenarien wie der Pflanzenidentifikation (z. B. Pl@ntNet), der Tiererkennung oder der medizinischen Diagnose üblich, wo einige Klassen sehr häufig vorkommen, während andere (z. B. seltene oder gefährdete Arten) nur durch wenige Beispiele repräsentiert sind.

Die zentrale Herausforderung besteht darin, Vorhersagemengen zu erstellen, die zwei oft widersprüchliche Anforderungen erfüllen:

1. Gute klassenbedingte Abdeckung (Class-Conditional Coverage): Seltene Klassen dürfen nicht systematisch aus den Vorhersagemengen ausgeschlossen werden. Dies ist kritisch, da das Erkennen seltener Fälle (z. B. seltene Krankheiten oder bedrohte Arten) oft wichtiger ist als das Erkennen häufiger Fälle.
2. Angemessene Set-Größe: Die Mengen sollten klein genug sein, damit menschliche Entscheidungsträger sie praktisch überprüfen können. Große Mengen (z. B. Hunderte von Kandidaten) sind unbrauchbar.

Das Dilemma: Herkömmliche Methoden der konformen Vorhersage (Conformal Prediction, CP) zwingen Praktiker zu einer binären Wahl:

• Standard-CP: Liefert kleine Mengen, garantiert aber nur eine marginale Abdeckung (über alle Klassen gemittelt). In langschwänzigen Szenarien führt dies dazu, dass seltene Klassen eine sehr schlechte Abdeckung haben.
• Classwise-CP (Mondrian): Garantiert eine Abdeckung für jede Klasse einzeln, führt aber in langschwänzigen Szenarien zu extrem großen Mengen, da für seltene Klassen kaum Kalibrierungsdaten vorhanden sind (die Schwellenwerte gehen gegen unendlich).

2. Methodik

Die Autoren schlagen zwei neue Ansätze vor, um einen besseren Kompromiss zwischen Set-Größe und klassenbedingter Abdeckung zu finden. Beide Ansätze basieren auf dem Framework der geteilten konformen Vorhersage (split conformal prediction).

Ansatz I: Zielsetzung der (gewichteten) Makro-Abdeckung durch neue Score-Funktionen

Statt die marginale Abdeckung zu optimieren, zielt dieser Ansatz auf die Makro-Abdeckung (Macro-Coverage) ab, definiert als der Durchschnitt der klassenbedingten Abdeckungen über alle Klassen.

• Theoretische Grundlage: Die Autoren leiten eine optimale Vorhersagemenge her, die die erwartete Set-Größe unter einer Makro-Abdeckungsbeschränkung minimiert. Die Lösung erfordert das Schwellenwert-Setzen basierend auf dem Verhältnis $p(y|x) / p(y)$ (posteriore Wahrscheinlichkeit geteilt durch Klassenprävalenz).
• PAS (Prevalence-Adjusted Softmax): Da die wahren Wahrscheinlichkeiten unbekannt sind, schlagen die Autoren eine neue Score-Funktion vor:
  $$s_{PAS}(x, y) = -\frac{\hat{p}(y|x)}{\hat{p}(y)}$$
  Hierbei ist $\hat{p}(y|x)$ die vom Klassifikator vorhergesagte Wahrscheinlichkeit und $\hat{p}(y)$ die geschätzte Prävalenz der Klasse. Durch Anwendung von Standard-CP mit diesem Score wird die marginale Abdeckung garantiert, während die Menge gleichzeitig die Makro-Abdeckung optimiert.
• WPAS (Weighted PAS): Eine Erweiterung, bei der Benutzer spezifische Klassen (z. B. gefährdete Arten) höher gewichten können, um deren Abdeckung zu priorisieren.

Ansatz II: Interpolation zwischen marginaler und klassenbedingter Abdeckung (INTERP-Q)

Dieser Ansatz bietet eine einfache, parametrisierbare Methode, um zwischen den Extremen von Standard-CP und Classwise-CP zu interpolieren.

• Methode: Die Schwellenwerte für die Vorhersagemengen werden linear interpoliert. Sei $\hat{q}$ der globale Schwellenwert (Standard-CP) und $\hat{q}^{CW}_y$ der klassenspezifische Schwellenwert (Classwise-CP). Der neue Schwellenwert für Klasse $y$ ist:
  $$\hat{q}^{IQ}_y = \tau \cdot \hat{q}^{CW}_y + (1 - \tau) \cdot \hat{q}$$
  wobei $\tau \in [0, 1]$ ein Interpolationsparameter ist.
• Eigenschaften:
  • $\tau = 0$: Entspricht Standard-CP (kleine Mengen, schlechte Abdeckung für seltene Klassen).
  • $\tau = 1$: Entspricht Classwise-CP (garantierte Abdeckung, aber extrem große Mengen).
  • Nichtlinearer Effekt: Selbst kleine Reduktionen von $\tau$ (z. B. von 1 auf 0,99) führen zu drastischen Verkleinerungen der durchschnittlichen Set-Größe, während die Abdeckung für seltene Klassen weitgehend erhalten bleibt. Dies liegt daran, dass die Score-Verteilungen seltener Klassen stark verzerrt sind.
  • Garantie: Theoretisch wird eine marginale Abdeckung von mindestens $1 - 2\alpha$ garantiert, empirisch jedoch oft nahe $1 - \alpha$.

3. Wichtige Beiträge

1. Neue Score-Funktion (PAS): Einführung der „Prevalence-Adjusted Softmax"-Score-Funktion, die theoretisch fundiert ist, um die Trade-off-Optimierung zwischen Set-Größe und Makro-Abdeckung zu lösen.
2. Einfache Interpolations-Prozedur (INTERP-Q): Ein praktischer Algorithmus, der es Nutzern ermöglicht, den Trade-off durch einen einzigen Parameter $\tau$ feinjustierbar zu steuern, ohne komplexe neue Schwellenwertberechnungen pro Klasse durchführen zu müssen.
3. Umgang mit Datenknappheit: Die Methoden adressieren spezifisch das Problem, dass für seltene Klassen kaum Kalibrierungsdaten verfügbar sind, was bei herkömmlichen klassenbedingten Methoden zu unbrauchbar großen Mengen führt.
4. Gewichtung für kritische Klassen: Die Möglichkeit, über WPAS spezifische Klassen (z. B. bedrohte Arten) zu priorisieren, ohne die gesamte Struktur der Vorhersagemenge zu zerstören.

4. Ergebnisse

Die Methoden wurden auf zwei großen, langschwänzigen Bilddatensätzen evaluiert: Pl@ntNet-300K (1.081 Klassen) und iNaturalist-2018 (8.142 Klassen).

• Trade-off-Optimierung:
  • Standard-CP liefert kleine Mengen (z. B. durchschnittlich 1,57 bei Pl@ntNet), aber über 40 % der Klassen haben eine Abdeckung unter 50 %.
  • Classwise-CP erreicht eine hohe Abdeckung, erzeugt aber unpraktisch große Mengen (durchschnittlich 780 bei Pl@ntNet).
  • Standard mit PAS: Erreicht eine durchschnittliche Set-Größe von nur 2,57 (nahe Standard-CP), reduziert aber die Anzahl der Klassen mit Abdeckung < 50 % auf 180 (Verbesserung um mehr als die Hälfte).
  • INTERP-Q: Ermöglicht eine feine Abstimmung. Bei $\tau = 0,99$ werden die Mengen drastisch verkleinert (z. B. von 780 auf 7,6 bei Pl@ntNet), während die Abdeckung für die meisten Klassen hoch bleibt.
• Priorisierung seltener Klassen: In einem Fallstudien-Szenario zur Identifikation gefährdeter Pflanzenarten zeigte WPAS, dass sich die Abdeckung für diese spezifischen Klassen signifikant verbessern lässt, ohne die Set-Größe für andere Klassen stark zu erhöhen.
• Menschliche Entscheidungsfindung: Simulationen menschlicher Entscheidungsträger (Experten vs. Zufallsgleiter) zeigen, dass die vorgeschlagenen Methoden die Wahrscheinlichkeit korrekter Identifikation über alle Klassen hinweg ausgleichen und robust gegenüber der Art des menschlichen Benutzers sind.

5. Bedeutung und Ausblick

Das Paper liefert einen wichtigen Beitrag zur Zuverlässigkeit von KI-Systemen in kritischen, unausgewogenen Umgebungen.

• Praktische Relevanz: Für Anwendungen wie Citizen-Science-Apps (z. B. Pl@ntNet) oder medizinische Diagnosen ist es entscheidend, dass seltene, aber wichtige Fälle nicht übersehen werden. Die vorgeschlagenen Methoden ermöglichen es, Vorhersagemengen zu generieren, die sowohl klein genug für den menschlichen Nutzer als auch fair gegenüber seltenen Klassen sind.
• Vermeidung von „Model Collapse": Durch die Verbesserung der Abdeckung seltener Klassen in menschlich-KI-Systemen wird verhindert, dass diese Klassen in zukünftigen Trainingszyklen ignoriert werden, was zu einer Degradation des Modells führen würde.
• Flexibilität: Die Kombination aus einer theoretisch fundierten Score-Funktion (PAS) und einer einfach zu bedienenden Interpolationsmethode (INTERP-Q) bietet Praktikern flexible Werkzeuge, um je nach Anforderung (z. B. maximale Abdeckung vs. minimale Set-Größe) die beste Konfiguration zu wählen.

Zusammenfassend füllen die Autoren eine Lücke in der Literatur zur konformen Vorhersage, indem sie zeigen, dass es möglich ist, die Nachteile von Standard- und Classwise-CP in langschwänzigen Szenarien zu überwinden und einen optimalen Kompromiss zu finden.