Online conformal inference with retrospective adjustment for faster adaptation to distribution shift

Technische Samenvatting: Online Conformal Inference met Retrospectieve Aanpassing

Probleemstelling

Conformal prediction biedt een distributievrij kader voor het construeren van voorspellingssets met gegarandeerde dekking, primair gebaseerd op de aanname van uitwisselbaarheid van data. Echter, in online leeromgevingen waar datadistributies in de loop van de tijd evolueren (niet-stationaire tijdreeksen, concept drift), wordt deze aanname frequent geschonden. Recente methoden die pogingen doen om dit soort distributieverschuivingen aan te pakken, lijden echter doorgaans aan trage adaptatie.

Bestaande benaderingen, zoals Adaptive Conformal Inference (ACI), updaten voorspellingen op een puur forward-wijze: wanneer een nieuw datapunt arriveert, wordt een voorspelling gegenereerd op basis van het huidige model, terwijl eerder berekende voorspellingen en residuen vast blijven staan. Bijgevolg wordt de historische kalibratieset inconsistent met het huidige datagenereerde proces naarmate de distributie verschuift, wat leidt tot een vertraagde herstel van het nominale dekkingsniveau en te conservatieve (brede) voorspellingsintervallen. Bovendien is het naïef implementeren van een methode die eerdere voorspellingen bijwerkt (retrospectieve aanpassing) computationeel prohibitief, aangezien dit vaak herhaaldelijke hertraining van het model vereist met een complexiteit van $O(n^4)$ per tijdstap.

Methodologie

De auteurs stellen RetroAdj voor, een nieuwe online conformal inference-methode die snellere adaptatie bereikt door middel van retrospectieve aanpassing. In plaats van enkel nieuwe residuen toe te voegen aan een kalibratieset, herziet RetroAdj dynamisch de gehele set van eerdere residuen en voorspellingen telkens wanneer nieuwe data arriveert.

Kernmechanisme

1. Retrospectieve Recalibratie: Bij de aankomst van een nieuw datapunt $(X_t, Y_t)$ werkt de methode het basisregressiemodel bij en herberekent cruciaal de Leave-One-Out (LOO) residuen voor alle actieve datapunten in het huidige tijdvenster. Dit brengt de gehele kalibratieset in lijn met de meest recente datadistributie.
2. Efficiënte Implementatie via Lineaire Smoothers: Om de $O(n^4)$ complexiteit van hertraining te vermijden, beperkt de methode de onderliggende regressieschatter tot lineaire smoothers (specifiek Kernel Ridge Regression, KRR) die closed-form LOO-updateformules toestaan.
   • Lemma 1 & 2: Maakt gebruik van de zelfstabiele eigenschap van KRR om LOO-residuen en voorspellingen uit te drukken als eenvoudige correcties op de volledige model-fit, waardoor hertraining wordt vermeden.
   • Matrix-updates: Het algoritme maakt gebruik van rank-one matrix-updates (Sherman-Morrison formule) en symmetrische rank-one "downdates" om de inverse kernelmatrix efficiënt bij te werken terwijl het sliding window beweegt. Dit vermindert de computationele complexiteit per tijdstap van $O(n^4)$ naar $O(n^2)$.
3. Integratie met ACI: De methode opereert binnen het Adaptive Conformal Inference (ACI) kader. Het werkt het miscoverageniveau $\alpha_t$ bij op basis van de dekking-indicatoren, maar in tegenstelling tot standaard ACI reconstrueert het het voorspellingsinterval $\hat{C}_t$ met behulp van de volledig bijgewerkte set retrospectieve residuen.

Algoritme Overzicht

• Input: Venstergrootte $w$, doelstelling miscoverage $\alpha$, initiële data.
• Proces:
  1. Observeer $X_t$ en genereer een voorspellingsinterval met de Jackknife+-formule met de huidige set retrospectieve residuen.
  2. Observeer $Y_t$.
  3. Update de basis KRR-schatter en de inverse kernelmatrix met behulp van Lemma's 3 en 4 (rank-one updates/downdates).
  4. Herbereken alle LOO-residuen en voorspellingen voor het actieve venster.
  5. Update $\alpha_{t+1}$ met behulp van een ACI-gebaseerde regel (bijv. standaard ACI, SFOGD, DtACI).

Belangrijkste Bijdragen

1. Retrospectief Aanpassingsmechanisme: Introductie van een methode die de gehele set kalibratieresiduen bijwerkt naarmate nieuwe data arriveert, in plaats van ze incrementeel toe te voegen. Dit verandert de adaptatiedynamiek fundamenteel, waardoor de kalibratieset onmiddellijk de distributieverschuivingen kan volgen.
2. Efficiënte $O(n^2)$ Implementatie: Ontwikkeling van een algoritme dat gebruikmaakt van rank-one matrix-updates voor KRR, waardoor retrospectieve aanpassing computationeel hanteerbaar wordt gemaakt en de complexiteit wordt teruggebracht van $O(n^4)$ naar $O(n^2)$ per stap.
3. Theoretische Garanties: Vaststelling van langetermijn-dekkinggaranties. De auteurs bewijzen dat de voorgestelde methode asymptotische kalibratie van het miscoverageniveau bereikt ten opzichte van het doelniveau $\alpha$ (in de zin van ACI), zelfs zonder de uitwisselbaarheidsaanname, mits het miscoverageniveau $\alpha_t$ via standaard ACI-dynamiek wordt bijgewerkt.

Experimentele Resultaten

De auteurs evalueerden RetroAdj op zowel synthetische als real-world datasets, waarbij ze het vergeleken met forward-update baselines (FW) met diverse regressiemodellen (KRR, FIMT-DD, AMRules, AMF) en ACI-varianten.

• Synthetische Data (Abrupte Verschuivingen): In settings met abrupte distributieverschuivingen (lineaire en niet-lineaire modellen) bereikte RetroAdj consistent een dekking die dicht bij het nominale niveau (0.9) lag, terwijl de breedte van de voorspellingsintervallen met ongeveer 30% werd verminderd vergeleken met bestaande forward-methoden. De methode vertoonde een snelle herstel van de dekking direct na een verschuiving, terwijl baselines een trage adaptatie en langdurige over-dekking vertoonden.
• Real-World Data: Experimenten met de Communities and Crime, Elec2 (elektriciteitsprijzen) en AIG stock price datasets bevestigden dat RetroAdj een stabiele dekking en nauwere intervallen handhaaft tijdens regimeveranderingen. Baselines vertoonden scherpe dalingen in dekking en pieken in intervalbreedte tijdens verschuivingen, gevolgd door geleidelijk herstel. RetroAdj vertoonde vrijwel geen degradatie in intervalbreedte tijdens stabiele perioden, wat aangeeft dat er geen statistische efficiëntiekosten zijn voor stabiele data.

Betekenis en Claims

Het artikel claimt dat RetroAdj een fundamentele afruil aanpakt tussen statistische efficiëntie (smalle intervallen) en adaptiviteit (snelheid van dekkingherstel) in online conformal prediction.

• Snellere Adaptatie: Door eerdere voorspellingen bij te werken, herstelt de methode de empirische dekking naar het doelniveau kort nadat een distributieverschuiving heeft plaatsgevonden, gedefinieerd als een verminderde "hersteltijd".
• Statistische Efficiëntie: De methode produceert significant nauwere voorspellingsintervallen dan bestaande online conformal methoden, met name in niet-stationaire omgevingen, zonder de validiteit van de dekking op te offeren.
• Computationele Haalbaarheid: Het werk demonstreert dat de statistische voordelen van retrospectieve recalibratie zonder prohibitieve computationele kosten kunnen worden behaald, mits het onderliggende model een lineaire smoother is.

De auteurs erkennen beperkingen, waarbij zij opmerken dat de $O(n^2)$ complexiteit nog steeds hoger is dan lineaire tijd streaming-algoritmen en dat de methode vaste venstergroottes vereist. Zij suggereren toekomstig werk gericht op datagedreven vensterselectie en het uitbreiden van het LOO-stabiliteitsconcept naar bredere klassen van regressiemodellen.