Online Conformal Prediction Beyond Feedback

Problemformulierung: Online Conformal Prediction über Feedback hinaus

Unsicherheitsquantifizierung ist entscheidend für den Einsatz von maschinellem Lernen in sicherheitskritischen Anwendungen. Online Conformal Prediction (OCP) bietet einen theoretisch fundierten Rahmen zur Generierung von Vorhersagesets, die garantieren, dass das wahre Label mit einer vom Benutzer spezifizierten Häufigkeit enthalten ist, selbst bei nicht-i.i.d. Datenströmen und Black-Box-Klassifikatoren. Herkömmliche OCP-Methoden verlassen sich jedoch auf eine Feedbackschleife: Nachdem ein Vorhersageset ausgegeben wurde, erhält der Algorithmus Feedback (entweder das wahre Label oder ein Coverage-Signal), um zukünftige Sets anzupassen und vergangene Fehlabdeckungen zu kompensieren.

Diese Arbeit befasst sich mit einem Szenario, in dem ein solches Feedback nicht verfügbar oder nicht praktikabel ist. In vielen sicherheitskritischen Szenarien, wie etwa bei latenten Probes für Large Language Models (LLMs), muss ein Algorithmus Eingaben in Sicherheitskategorien klassifizieren. Wenn die Probe die Antwort verweigert (einen Menschen oder ein stärkeres System anfragt), kann das Label schließlich verfügbar werden. Für Eingaben, bei denen die Probe jedoch eine Entscheidung ausführt, wird das Label jedoch nie beobachtet. Dies schafft ein „Beyond-Feedback“-Szenario: Der Lernende muss zwischen der Ausgabe eines Vorhersagesets oder der Abfrage des korrekten Labels wählen, kann aber nicht beides tun. Folglich beobachtet der Lernende nie, ob ein ausgeführte Vorhersageset korrekt war, was die Standardmechanismen zur Kompensation verwendet in bestehenden OCP-Methoden verhindert.

Methodik: OCP mit Abfragen (OCPQ)

Die Autoren schlagen Online Conformal Prediction with Queries (OCPQ) vor, eine Methode, die für dieses „Beyond-Feedback“-Protokoll entwickelt wurde. Der Ansatz erfolgt in zwei Hauptschritten:

1. Reduktion auf Partielle Überwachung (Partial Monitoring): Das Problem wird auf ein endliches partielles Überwachungsspiel reduziert. Die „Arme“ des Spiels bestehen aus einer endlichen Menge von Vorhersageschwellenwerten $M \subset [0, 1]$ und einer separaten Abfrage-Aktion (Query).

   • Vorhersage-Aktion: Die Auswahl eines Schwellenwertes $m \in M$ generiert ein Vorhersageset $\Gamma_C(x_t, m)$ basierend auf einem Black-Box-Klassifikator $C$. Diese Aktion liefert keine Beobachtung (Null-Feedback $\perp$) und keinen direkten Reward.
   • Abfrage-Aktion: Die Auswahl der Abfrage-Aktion offenbart das wahre Label $y_t$, liefert aber kein Vorhersageset und erzeugt keinen Reward.
   • Reward-Struktur: Der Algorithmus definiert eine Hilfs-Rewardfunktion $R(m, t)$. Wenn das wahre Label durch das Vorhersageset abgedeckt ist ($y_t \in \Gamma_C(x_t, m)$), beträgt der Reward $1 - m(1-\beta)$, wobei $\beta$ ein vom Benutzer definierter Parameter ist, der den Trade-off zwischen Coverage und Effizienz steuert. Wenn das Label nicht abgedeckt ist, ist der Reward 0. Die Abfrage-Aktion liefert immer 0 Reward. Diese Struktur motiviert den Lernenden dazu, enge Schwellenwerte (kleines $m$) zu wählen, während die Abdeckung aufrechterhalten wird.

2. Algorithmus-Design: OCPQ passt den label-effizienten exponentiell gewichteten Forecaster von Cesa-Bianchi, Lugosi und Stoltz (2004) an.

   • In jeder Runde $t$ führt der Algorithmus mit einer festen Wahrscheinlichkeit $\epsilon$ eine Abfrage durch.
   • Wird eine Abfrage durchgeführt, wird das wahre Label $y_t$ beobachtet. Der Algorithmus aktualisiert dann die kumulativen Reward-Schätzungen $\hat{Z}_{m,t}$ für alle Schwellenwerte $m \in M$ mittels eines Verfahrens der inversen Wahrscheinlichkeitsgewichtung, wodurch den Reward effektiv rekonstruiert wird, der erzielt worden wäre, falls eine Vorhersage getroffen worden wäre.
   • Wird keine Abfrage durchgeführt, zieht der Algorithmus einen Schwellenwert $m_t$ aus einer exponentiell gewichteten Verteilung basierend auf den aktuellen Schätzungen $\hat{Z}_{m,t}$ und gibt das entsprechende Vorhersageset aus. Es wird kein Feedback empfangen.

Theoretische Ergebnisse

Das Paper etabliert Finite-Horizon-Garantien für OCPQ unter einem oblivious adversariellen Datenstrom der Länge $T$:

• Regret: Der erwartete Regret im Vergleich zum besten fixen Schwellenwert im Rückblick ist $O(T^{2/3})$. Speziell gilt mit $\epsilon = T^{-1/3}$ und $\eta = T^{-2/3}\sqrt{\ln|M|}$ ein Regret, der durch $T^{2/3}(2\sqrt{\ln|M|} + 1)$ begrenzt ist. Die Autoren merken an, dass diese Rate asymptotisch optimal für diese Klasse von partiellen Überwachungsspielen ist.
• Coverage: Die erwartete Coverage-Rate $p_{cover}$ erfüllt:
  $$E[p_{cover}] \ge \beta - O(T^{-1/3})$$
  Dies garantiert, dass die Coverage mit steigendem $T$ gegen das vom Benutzer definierte Ziel $\beta$ konvergiert.
• Abfragerate: Der Algorithmus fragt das Label nur in einem erwarteten Anteil von $T^{-1/3}$ der Runden ab.
• Hochwahrscheinlichkeits-Bounds: Das Paper leitet auch Hochwahrscheinlichkeits-Bounds für sowohl Regret als auch Coverage ab und zeigt, dass die Varianz der Performance des Algorithmus kontrolliert wird und kein pathologisches Verhalten aufweist.

Empirische Ergebnisse

Experimente wurden auf realen Datensätzen durchgeführt, um den Ansatz zu validieren:

• Verteilungsverschiebung (Distribution Shift): OCPQ wurde auf Standard-Benchmarks (MNIST, CIFAR-10, CIFAR-100) getestet, bei denen die Trainingsverteilung von der Testverteilung abwich (z. B. MNIST zu USPS oder MNIST zu MNIST-C). Die Ergebnisse zeigten, dass der Coverage-Effizienz-Trade-off über den Parameter $\beta$ gesteuert werden konnte. Die empirische Coverage lag konsistent über der theoretischen Untergrenze.
• LLM Safety Monitoring: Die Methode wurde zur Sicherheitsüberwachung von LLM-Prompts unter Verwendung des WildGuardMix-Datensatzes angewendet, der sowohl vanilla als auch adversariell umgeschriebene Prompts enthält. Die Genauigkeit des Basis-Klassifikators sank bei adversariellen Prompts signifikant, doch OCPQ hielt die Coverage über der theoretischen Grenze aufrecht und behielt gleichzeitig informative Vorhersagesets bei.
• Vergleich: Im Vergleich zu Adaptive Conformal Inference (ACI), das volles Feedback voraussetzt, erreichte OCPQ vergleichbare Coverage-Effizienz-Fronten, obwohl es signifikant weniger Informationen nutzte (Abfrage von nur ca. 5 % der Runden).

Bedeutung und Beiträge

Das Paper beansprucht die folgenden Beiträge:

1. Neues Protokoll: Es formuliert OCP in einem „Beyond-Feedback“-Szenario, in dem ausgeführte Vorhersagen niemals evaluiert werden – ein Szenario, das in sicherheitskritischen Anwendungen häufig vorkommt, in denen Labels nur für abgebrochene Abfragen verfügbar sind.
2. Algorithmische Reduktion: Es reduziert dieses Problem auf ein partielles Überwachungsspiel und passt Techniken des label-effizienten adversariellen Lernens an, um es zu lösen; insbesondere wird der Forecaster so modifiziert, dass Abfragen als distinkte Aktionen behandelt werden, die eine Vorhersage ersetzen, statt ihr zu folgen.
3. Theoretische Garantien: Es liefert endliche Erwartungswerte für Regret und Coverage für OCP in diesem Setting und zeigt, dass eine valide Unsicherheitsquantifizierung mit nur $O(T^{-1/3})$ Label-Abfragen möglich ist.
4. Praktische Wirksamkeit: Experimente demonstrieren, dass eine spärliche Supervision (zufällige Abfragen) ausreicht, um eine nützliche Coverage und Effizienz-Trade-off aufrechtzuerhalten, selbst unter adversariellen Verteilungsverschiebungen, ohne dass Feedback von ausgeführten Vorhersagesets erforderlich ist.

Die Autoren merken an, dass die Methode konservativ ist (die empirische Coverage liegt oft über der Grenze), was eine Folge der schwachen Annahmen ist, die für die Formulierung des partiellen Überwachungsspiels erforderlich sind. Zukünftige Arbeiten könnten weniger konservative Methoden oder Erweiterungen auf adaptive Adversaries untersuchen.