Technische Samenvatting: Wedden op Momenten – Legendre Jumper Martingalen voor Online Exchangeability Testing

Probleemstelling

In de conformationele voorspelling (conformal prediction) berust de validiteit van voorspellingssets op de aanname van exchangeability (uitwisselbaarheid), wat impliceert dat de sequentie van p-waarden gegenereerd door een conformationele transducer onafhankelijk en identiek verdeeld (IID) is volgens een uniforme verdeling op $[0, 1]$. Schendingen van deze aanname duiden op distributieve verschuivingen.

Hoewel conformationele test-martingalen (CTM's) worden gebruikt om online de exchangeability te testen, heeft de standaard Simple Jumper (SJ) martingale (Vovk et al., 2022) een kritieke beperking: deze maakt gebruik van een lineaire wedfunctie gebaseerd op het eerste-graads verschoven Legendre-polynoom. Bijgevolg is de SJ geometrisch beperkt tot het detecteren van verschuivingen in het gemiddelde (locatie) van de p-waarden. Het faalt in het accumuleren van significante rijkdom wanneer de distributieve verschuiving het gemiddelde behoudt maar hogere-orde momenten wijzigt, zoals variantie, scheefheid (skewness) of kurtosis. Bovendien lijden pogingen om meerdere wedstrategieën te combineren vaak onder de "jumping tax" (springbelasting), waarbij kapitaal wordt verdund over een exponentieel groeiende toestandsruimte, wat de detectiesnelheid ernstig belemmert.

Methodologie

Het artikel stelt een familie van conformationele test-martingalen voor gebaseerd op verschoven Legendre-polynomen ($\tilde{P}_k$), die orthogonaal zijn op het interval $[0, 1]$. Deze polynomen dienen als de basis voor wedfuncties die in staat zijn om afwijkingen in specifieke momenten van de p-waarde-distributie te detecteren.

1. Simple Legendre Jumper (SLJ)

De SLJ generaliseert de Simple Jumper door de lineaire wedfunctie te vervangen door een verschoven Legendre-polynoom van een willekeurige graad $k$:
$$f^{(k)}_\epsilon(p) = 1 + \epsilon \tilde{P}_k(p)$$
waarbij $\epsilon$ een parameter is die wordt geselecteerd uit een discreet rooster.

• Mechanisme: Voor $k=1$ herstelt het de standaard SJ (detectie van gemiddelde-verschuivingen); voor $k=2$ detecteert het variantieveranderingen; voor $k=3$ scheefheid; enzovoort.
• Beperking: Exclusief wedden op een enkele graad $k$ zorgt ervoor dat de martingale belangrijke verschuivingen in andere momenten mist, wat leidt tot suboptimale accumulatie van bewijs.

2. Product Legendre Jumper (PLJ)

Om complexe, multimodale afwijkingen gelijktijdig te vangen, combineert de PLJ wedfuncties van meerdere graden $K$ in een enkel product:
$$f^K_\epsilon(p) = \frac{\prod_{k \in K} (1 + \epsilon_k \tilde{P}_k(p))}{Z(\epsilon)}$$
waarbij $Z(\epsilon)$ een normalisatieconstante is die vereist is voor $|K| \ge 3$ om te waarborgen dat het integraal van de wedfunctie gelijk is aan 1.

• De "Jumping Tax": De PLJ onderhoudt een Markov-keten over de gezamenlijke toestandsruimte $\mathcal{E} = \prod_{k \in K} \mathcal{E}_k$. Naarmate het aantal graden $|K|$ toeneemt, groeit de omvang van de toestandsruimte exponentieel ($|\mathcal{E}| = g^{|K|}$). De "jumping tax" verwijst naar de verdunding van kapitaal: wanneer de omgeving verschuift, verdeelt het springmechanisme nieuw kapitaal uniform over deze enorme toestandsruimte, wat de concentratie van rijkdom op de optimale wedstrategie vertraagt.

3. Variational Legendre Jumper (VLJ)

Om de exponentiële schaling van de PLJ op te lossen, introduceren de auteurs de Variational Legendre Jumper, geïnspireerd door mean-field benaderingen in variational inference.

• Ontkoppeling: In plaats van een enkele Markov-keten over de productruimte, voert de VLJ $|K|$ onafhankelijke sub-jumpers uit (één voor elke graad $k \in K$).
• Consensus: Bij elke stap berekent de VLJ een consensusparameter $\bar{\epsilon}_k$ voor elke graad op basis van het vermogen-gewogen gemiddelde van de toestand van de sub-jumper.
• Global Bet: De globale martingale werkt bij met de genormaliseerde product van de wedfuncties geëvalueerd op deze consensusparameters.
• Complexiteit: Dit reduceert de computationele kosten van exponentieel $O(g^{|K|})$ naar lineair $O(|K| \cdot g)$, waardoor testen van hogere-orde momenten computationeel haalbaar wordt met minimaal verlies aan statistische kracht.

4. Composite Legendre Jumper

Volgend aan het kader van Vovk et al. (2022), middelt de Composite Legendre Jumper de basis-martingale (SLJ, PLJ of VLJ) over een rooster van springfrequenties $J \in \{10^{-4}, \dots, 1\}$.

• Robuustheid: Dit zorgt voor robuustheid wanneer de tijdschaal van de distributieve verschuiving onbekend is.
• Wealth Floor: De inclusie van $J=1$ garandeert dat de martingale nooit onder $1/|\mathcal{E}|$ zakt, wat een absolute rijkdomvloer biedt onder exchangeability die vaste-rate varianten missen.

Belangrijkste Bijdragen

1. Generalisatie van Wedfuncties: De introductie van de Simple Legendre Jumper, die de lineaire wedfunctie van de Simple Jumper uitbreidt naar willekeurige-graads verschoven Legendre-polynomen, wat detectie van variantie, scheefheid en hogere-orde moment-afwijkingen mogelijk maakt.
2. Aanpak van de "Jumping Tax": De ontwikkeling van de Product Legendre Jumper om gezamenlijke afwijkingen te vangen, gevolgd door de Variational Legendre Jumper, die het gezamenlijke adaptatieprobleem factoriseert via een mean-field benadering. Dit slaagt erin de toestandsruimte-schaling van exponentieel naar lineair te reduceren met behoud van statistische kracht.
3. Composite Robuustheid: De integratie van deze methoden in een Composite Legendre Jumper, die middelt over verschillende springfrequenties om automatische adaptatie aan onbekende verschuivings-tijdschalen en een gegarandeerde rijkdomvloer te bieden.
4. Empirische Validatie: Demonstratie op een real-world classificatietaak (Wine Quality dataset) waarbij aangetoond wordt dat gecombineerde methoden (PLJ en VLJ) consistent beter presteren dan single-degree martingalen onder distributieve verschuivingen, terwijl de variationele benadering een verwaarloosbaar verlies aan prestatie oplevert ten opzichte van de exacte productmethode.

Resultaten

De auteurs evalueerden de voorgestelde methoden op de Wine Quality dataset met behulp van een conformationele nearest-neighbor classifier onder vier datatellorderingen: geschud (exchangeable), abrupte veranderpunten (Red $\to$ White, White $\to$ Red), en originele volgorde.

• Exchangeability: Onder geschudde data bleven alle martingalen nabij nul of daalden ze licht, wat bevestigt dat ze geen valse alarmen geven.
• Distributieve Verschuiving: Onder niet-exchangeable ordeningen bereikten de Product en Variational Legendre Jumpers met $K=\{1, 2, 3\}$ consequent de hoogste finale log-martingale waarden, waarbij ze de single-degree Simple Legendre Jumper ($k=1$) overtroffen met 30%–60% in log-schaal bewijs.
• Falende Single-Degree: Martingalen die uitsluitend wedden op variantie ($k=2$) of scheefheid ($k=3$) presteerden slecht wanneer de verschuiving meerdere momenten betrof, en cumuleerden orders van grootte minder bewijs dan de gecombineerde benaderingen.
• Efficiëntie vs. Kracht: De Variational Legendre Jumper (VLJ) kwam bijna exact overeen met de prestaties van de Product Legendre Jumper (PLJ), maar vereiste aanzienlijk minder toestanden (bijv. 15 toestanden versus 125 toestanden voor $K=\{1, 2, 3\}$).
• Composite Superioriteit: De Composite Legendre Jumper presteerde beslissend beter dan fixed-rate varianten onder distributieve verschuivingen (bijv. het bereiken van $\log_{10} M_n \approx 100$ versus fixed-rate $\approx 90$) en voorkwam de trage accumulatie van verliezen die men ziet bij fixed-rate martingalen onder exchangeability.

Betekenis en Claims

Het artikel claimt dat de Composite Legendre Jumper de standaardkeuze zou moeten zijn voor praktijkgebruikers wanneer de tijdschaal van distributieve verschuivingen onbekend is. Het biedt een robuuste oplossing die:

1. Complexe, multimodale afwijkingen van uniformiteit detecteert die lineaire wedfuncties missen.
2. De "vloek van dimensionaliteit" vermijdt die gepaard gaat met gezamenlijke wedstrategieën via variationele factorisatie.
3. Een theoretische en praktische rijkdomvloer biedt, wat stabiliteit onder de nulhypothese garandeert.

De auteurs merken op dat hoewel de variationele benadering empirisch presteert op gelijke hoogte met het exacte product, de theoretische grenzen aan het verlies van statistische kracht door mean-field factorisatie een openstaand probleem blijven. Ze suggereren ook dat toekomstig werk de data-gedreven selectie van polynoomgraden kan verkennen (analoog aan de aanpak van Ledwina voor Neyman's smooth test) om de efficiëntie verder te optimaliseren. De implementatie is beschikbaar in de Python-package online-cp.