Online Learning-to-Defer with Varying Experts

Problemformulierung
Learning-to-Defer (L2D) ist ein Framework, das entwickelt wurde, um prädiktive Modelle mit externen Experten (menschlich oder automatisiert) zu integrieren, um die Zuverlässigkeit von Systemen zu erhöhen, indem unsichere oder hochriskante Eingaben an kompetentere Agenten weitergeleitet werden. Während die bestehende L2D-Forschung hauptsächlich in Batch-Umgebungen mit festen Expertenpools und vollständiger Überwachung (Beobachtung aller Expertenvorhersagen während des Trainings) operiert, stehen reale Bereitstellungen vor erheblichen Herausforderungen: Daten kommen sequenziell an, die Verfügbarkeit von Experten schwankt (z. B. aufgrund von Schichten oder Ressourcenbeschränkungen), und die Zuverlässigkeit von Experten kann sich im Laufe der Zeit ändern. Darüber hinaus arbeiten praktische Systeme oft unter Bandit-Feedback, bei dem der Lerner nur das Ergebnis der gewählten Aktion (Vorhersage oder spezifische Expertenabfrage) beobachtet, nicht jedoch die Ground Truth oder die Leistung aller verfügbaren Experten. Dieser Beitrag schließt die Lücke zwischen klassischen L2D-Annahmen und diesen dynamischen, Online-Realitäten, indem er das erste Online-L2D-Framework für Multiklassen-Klassifizierung mit Bandit-Feedback und einem dynamisch variierenden Pool von Experten einführt.

Methodik
Die Autoren schlagen ein allgemeines Framework vor, bei dem in jeder Runde $t$ eine erweiterte Eingabe $(x_t, A_t)$ offengelegt wird, bestehend aus einem Merkmalsvektor $x_t$ und einer Menge verfügbarer Experten $A_t$. Der Lerner muss entscheiden, ob er eine Klassenlabel vorhersagt oder an einen der verfügbaren Experten in $A_t$ deferiert. Die Interaktion folgt einem semi-adversariellen Setting: Eingaben können adversariell gewählt werden, aber Labels werden aus einer festen (wenn auch unbekannten) Verteilung gezogen, die konditional auf die Eingabe ist.

Die wesentlichen methodischen Beiträge umfassen:

1. Echte Deferierungsverlustfunktion und Surrogat: Die Autoren definieren einen echten Deferierungsverlust $\ell_{def}$, der Kosten für Fehlklassifizierung und Kosten für Expertenabfragen berücksichtigt. Da dieser Verlust nicht differenzierbar ist, führen sie eine konvexe Surrogatverlustfunktion $\Phi_{def}$ ein, die standardmäßige score-basierte Surrogate (wie eingeschränkte Hinge-Loss) auf das Online-Setting mit variierenden Experten erweitert. Dieses Surrogat ist so konzipiert, dass es nicht von den Scores nicht verfügbarer Experten beeinflusst wird.
2. H-Konsistenz-Schranken für Online-Lernen: Ein signifikanter theoretischer Schritt ist die Erweiterung von $H$-Konsistenz-Schranken vom Batch-Lernen auf das Online-Setting. Die Autoren beweisen, dass die Minimierung des Surrogat-Deferierungs-Regrets im Online-Framework ein begrenztes wahres Deferierungs-Regret sicherstellt, vorausgesetzt, das zugrundeliegende Surrogat gestattet eine $H$-Konsistenz-Schranke bezüglich des Zero-One-Verlusts.
3. Algorithmus-Design: Der vorgeschlagene Algorithmus (Algorithmus 1) nutzt Online-Gradientenabstieg (OGD) mit projizierten Gradienten. Um die Einschränkung zu handhaben, dass die Summe der Scores für verfügbare Labels null sein muss (erforderlich für den eingeschränkten Hinge-Loss), projiziert der Algorithmus die Gewichtsmatrix auf einen für den aktuellen Satz verfügbarer Experten spezifischen zulässigen Unterraum $K_{A_t}$. Diese Projektion erhält die Vorhersagen der Hypothese auf dem verfügbaren Label-Set. Der Algorithmus integriert eine Explorationsrate $\gamma_t$, um das Bandit-Feedback zu handhaben, und schätzt die Verlustfunktion basierend auf dem beobachteten Ergebnis der gesampelten Aktion.

Hauptbeiträge
Der Beitrag beansprucht vier primäre Beiträge:

1. Erstes Online-L2D-Framework: Es stellt das erste Framework für Online-Learning-to-Defer unter Bandit-Feedback vor, bei dem sowohl die Datenverteilung als auch der Pool von Experten über die Zeit variieren können.
2. Theoretische Erweiterung: Es erweitert das Konzept der $H$-Konsistenz-Schranken auf das Online-Setting, eine Eigenschaft, die zuvor auf Batch-Lernanalysen beschränkt war.
3. Regret-Garantien: Der vorgeschlagene Algorithmus erreicht im allgemeinen Fall eine Regret-Schranke von $O((n + n_e)T^{2/3})$, wobei $n$ die Anzahl der Klassen und $n_e$ die Anzahl der beobachteten distincten Experten ist. Unter einer Low-Noise-Annahme (nahezu realisierbar) verbessert sich dies auf $O((n + n_e)\sqrt{T})$.
4. Empirische Validierung: Der Ansatz wird sowohl auf synthetischen als auch auf realen Datensätzen (Reuters4 und CIFAR10H) validiert und demonstriert seine Fähigkeit, sich an variierende Expertenverfügbarkeit und driftende Expertise anzupassen.

Ergebnisse
Experimente wurden unter drei Regimen zunehmender Komplexität durchgeführt: (1) feste Verfügbarkeit und Expertise, (2) driftende Verfügbarkeit mit fester Expertise und (3) vollständig dynamische Settings mit sowohl driftender Verfügbarkeit als auch driftender Expertise.

• Synthetische Daten: Der Algorithmus lernte erfolgreich die optimale Grenze zwischen Vorhersage und Deferierung, leitete Eingaben konsistent an die kompetentesten verfügbaren Experten weiter und hielt auch dann einen niedrigen Deferierungsverlust und eine hohe Genauigkeit aufrecht, wenn sich die Kompetenzbereiche der Experten im Laufe der Zeit verschoben.
• Reale Daten (Reuters4): Im anspruchsvollsten Setting (driftende Verfügbarkeit und Expertise) verfolgte die Methode die sich bewegenden Kompetenzbereiche der Experten effektiv. Sie deferierte mit hoher Frequenz an aktuell kompetente Experten, behielt eine stabile Kalibrierung bei und erreichte eine Aufgaben-Genauigkeit, die mit Baselines mit fester Expertise vergleichbar war.
• CIFAR10H: Unter Verwendung eines WideResNet-Prädiktors und menschlich annotierter Experten übertraf die Methode eine konfidenzbasierte Baseline, die gleichverteilt zufällig deferiert. Die gelernte Policy erreichte einen niedrigeren Deferierungsverlust und eine höhere Genauigkeit, was darauf hindeutet, dass sie gelernt hat, Beispiele an die am besten geeigneten Experten zu leiten, anstatt indiscriminiert zu deferieren.

Bedeutung
Der Beitrag positioniert sich als grundlegender Schritt hin zur Machbarkeit von Learning-to-Defer-Systemen für reale, nicht-stationäre Umgebungen. Indem die Autoren über die Annahme fester Expertenpools und vollständiger Überwachung hinausgehen, demonstrieren sie, dass konsistente, surrogatbasierte Methoden robust gegenüber adversariellen Umgebungen und variierender Experten Zuverlässigkeit gemacht werden können. Die theoretische Etablierung von $H$-Konsistenz im Online-Setting bietet eine rigorose Garantie, dass die Minimierung des Surrogatverlusts zur Minimierung des wahren Deferierungs-Regrets führt, und schließt damit eine kritische Lücke zwischen theoretischen L2D-Garantien und den praktischen Anforderungen von Streaming-Daten und dynamischen Expertensystemen.