Online Conformal Prediction Beyond Feedback

Probleemformulering: Online Conformal Prediction voorbij feedback

Onzekerheidskwantificatie is cruciaal voor het inzetten van machine learning in veiligheidskritische toepassingen. Online Conformal Prediction (OCP) biedt een theoretisch gefundeerd kader voor het genereren van voorspellingssets die garanderen dat het ware label met een door de gebruiker gespecificeerde frequentie wordt opgenomen, zelfs voor niet-i.i.d. datastromen en black-box classifiers. Echter, standaard OCP-methoden vertrouwen op een feedbackloop: nadat een voorspellingsset is uitgegeven, ontvangt het algoritme feedback (ofwel het ware label, ofwel een dekkingssignaal) om toekomstige sets aan te passen, waardoor eerdere tekortkomingen in de dekking worden gecompenseerd.

Dit artikel behandelt een setting waarin dergelijke feedback niet beschikbaar of ontoelaatbaar is. In veel veiligheidskritische scenario's, zoals latente probes voor Large Language Models (LLM's), moet een algoritme inputs classificeren in veiligheidscategorieën. Als de probe onthoudt zich van een oordeel (een mens of een sterker systeem raadplegen), kan het label uiteindelijk beschikbaar komen. Echter, voor inputs waarbij de probe een beslissing heeft genomen die daadwerkelijk wordt ingezet, wordt het label nooit waargenomen. Dit creëert een "beyond feedback"-scenario: de leerder moet kiezen tussen het uitvoeren van een voorspellingsset of het opvragen van het juiste label, maar kan niet beide doen. Bijgevolg neemt de leerder nooit waar of een ingezette voorspellingsset correct was, wat de standaard compensatiemechanismen die in bestaande OCP-methoden worden gebruikt, verhindert.

Methodologie: OCP met Queries (OCPQ)

De auteurs stellen Online Conformal Prediction with Queries (OCPQ) voor, een methode die is ontworpen voor dit beyond-feedback protocol. De aanpak verloopt in twee hoofdstappen:

1. Reductie naar Partial Monitoring: Het probleem wordt gereduceerd tot een eindig partial monitoring spel. De "armen" van het spel bestaan uit een eindige verzameling voorspellingsdrempels $M \subset [0, 1]$ en een aparte query-actie.

   • Voorspellingsactie: Het selecteren van een drempel $m \in M$ genereert een voorspellingsset $\Gamma_C(x_t, m)$ op basis van een black-box classifier $C$. Deze actie levert geen observatie op (nul feedback $\perp$) en geen directe beloning.
   • Query-actie: Het selecteren van de query-actie onthult het ware label $y_t$, maar produceert geen voorspellingsset en levert een beloning van nul op.
   • Beloningsstructuur: Het algoritme definieert een hulpbeloningsfunctie $R(m, t)$. Als het ware label wordt gedekt door de voorspellingsset ($y_t \in \Gamma_C(x_t, m)$), is de beloning $1 - m(1-\beta)$, waarbij $\beta$ een door de gebruiker gedefinieerde parameter is die de afweging tussen dekking en efficiëntie regelt. Als het label niet wordt gedekt, is de beloning 0. De query-actie levert altijd 0 beloning op. Deze structuur stimuleert de leerder om nauwe drempels (kleine $m$) te selecteren terwijl de dekking behouden blijft.

2. Algoritmeontwerp: OCPQ past de label-efficiënte exponentieel gewogen forecaster van Cesa-Bianchi, Lugosi, en Stoltz (2004) aan.

   • In elke ronde $t$ voert het algoritme een query uit met een vaste waarschijnlijkheid $\epsilon$.
   • Als een query wordt uitgevoerd, wordt het ware label $y_t$ waargenomen. Het algoritme werkt vervolgens de cumulatieve beloningsschattingen $\hat{Z}_{m,t}$ voor alle drempels $m \in M$ bij met behulp van een inverse waarschijnlijkheidsgewichtsregeling, waardoor de beloning effectief wordt gereconstrueerd die zou zijn verkregen als er een voorspelling was gedaan.
   • Als er geen query wordt uitgevoerd, samplet het algoritme een drempel $m_t$ uit een exponentieel gewogen distributie gebaseerd op de huidige schattingen $\hat{Z}_{m,t}$ en geeft de bijbehorende voorspellingsset uit. Er wordt geen feedback ontvangen.

Theoretische Resultaten

Het artikel stelt eindige horizon-garanties vast voor OCPQ onder een oblivious adversariële datastroom van lengte $T$:

• Regret (Spijt): De verwachte regret ten opzichte van de beste vaste drempel in hindsight is $O(T^{2/3})$. Specifiek, met $\epsilon = T^{-1/3}$ en $\eta = T^{-2/3}\sqrt{\ln|M|}$, is de regret begrensd door $T^{2/3}(2\sqrt{\ln|M|} + 1)$. De auteurs merken op dat dit tempo asymptotisch optimaal is voor deze klasse van partial monitoring spelen.
• Dekking: De verwachte dekkingsgraad $p_{cover}$ voldoet aan:
  $$E[p_{cover}] \ge \beta - O(T^{-1/3})$$
  Dit garandeert dat de dekking de door de gebruiker gedefinieerde doelstelling $\beta$ nadert naarmate $T$ toeneemt.
• Query Rate: Het algoritme vraagt het label op in slechts een verwacht $T^{-1/3}$ deel van de rondes.
• High-Probability Bounds: Het artikel leidt ook high-probability bounds af voor zowel regret als dekking, wat aantoont dat de variantie van de prestaties van het algoritme gecontroleerd wordt en geen pathologisch gedrag vertoont.

Empirische Resultaten

Experimenten werden uitgevoerd op real-world datasets om de aanpak te valideren:

• Distributieverschuiving: OCPQ werd getest op standaard benchmarks (MNIST, CIF-10, CIFAR-100) waarbij de trainingsdistributie verschilde van de testdistributie (bijv. MNIST naar USPS, of MNIST naar MNIST-C). De resultaten lieten zien dat de dekkings-efficiëntie-afweging kon worden gecontroleerd via de parameter $\beta$. De empirische dekking overtrof consequent de theoretische ondergrens.
• LLM Veiligheidsmonitoring: De methode werd toegepast op veiligheidsmonitoring voor LLM-prompts met de WildGuardMix dataset, die zowel vanilla als adversarieel herschreven prompts bevat. De nauwkeurigheid van de basisclassifier daalde significant op adversariële prompts, maar OCPQ behield de dekking boven de theoretische ondergrens terwijl de voorspellingssets informatief bleven.
• Vergelijking: Wanneer vergeleken met Adaptive Conformal Inference (ACI), die volledige feedback veronderstelt, bereikte OCPQ vergelijkbare dekkings-efficiëntie-fronten ondanks het gebruik van aanzienlijk minder informatie (door slechts ~5% van de rondes te query'en).

Betekenis en Bijdragen

De auteurs claimen de volgende bijdragen:

1. Nieuw Protocol: Het formuleert OCP in een "beyond feedback"-setting waarbij ingezette voorspellingen nooit worden geëvalueerd, een scenario dat gebruikelijk is in veiligheidskritische toepassingen waarbij labels alleen beschikbaar zijn voor onthoudende queries.
2. Algoritmische Reductie: Het reduceert dit probleem tot een partial monitoring spel en past technieken voor label-efficiënt adversarieel leren aan om het op te lossen, specifiek door de forecaster aan te passen zodat deze queries behandelt als afzonderlijke acties die voorspellingen vervangen, in plaats van deze te volgen.
3. Theoretische Garanties: Het biedt eindige horizon verwachte regret en dekking garanties voor OCP in deze setting, waarbij wordt aangetoond dat geldige onzekerheidskwantificatie mogelijk is met slechts $O(T^{-1/3})$ label queries.
4. Praktische Effectiviteit: Experimenten tonen aan dat schaarse supervisie (random queries) voldoende is om bruikbare dekking en efficiëntie-afwegingen te behouden, zelfs onder adversariële distributieverschuivingen, zonder dat feedback van ingezette voorspellingssets vereist is.

De auteurs merken op dat hoewel de methode conservatief is (de empirische dekking overtreft vaak de grens), dit een gevolg is van de zwakke aannames die vereist zijn voor de partial monitoring spel formulering. Toekomstig werk zou minder conservatieve methoden of uitbreidingen naar adaptieve adversaries kunnen verkennen.