📊 statistics

Betting on Moments: Legendre Jumper Martingales for Online Exchangeability Testing

Dieses Paper führt eine Familie von konformen Test-Martingalen auf Basis verschobener Legendre-Polynome ein, die den Simple Jumper erweitern, um höherwertige Verteilungsabweichungen zu detektieren, und bietet skalierbare Varianten wie die Variational und Composite Legendre Jumpers an, um Rechenkosten zu bewältigen und sich an unbekannte Shift-Zeitskalen beim Online-Exchangeability-Testing anzupassen.

Ursprüngliche Autoren: Johan Hallberg Szabadváry

Veröffentlicht 2026-06-23

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Johan Hallberg Szabadváry

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie sind ein Detektiv, der herauszufinden versucht, ob ein Datenstrom sich „normal“ verhält oder ob etwas Verdächtiges im Gange ist. In der Statistik wird dieses „normale“ Verhalten als Austauschbarkeit bezeichnet. Es bedeutet im Grunde, dass die Daten eine faire, zufällige Mischung sind, bei der die Zukunft genau wie die Vergangenheit aussieht. Wenn die Daten anfangen, sich seltsam zu verhalten (vielleicht werden die Zahlen plötzlich breiter gestreut oder sie häufen sich an merkwürdigen Stellen), ist es Ihr Job als Detektiv, diese Änderung so schnell wie möglich zu erkennen.

Dieses Papier stellt eine neue Familie von „Detektiv-Werkzeugen“ vor, die Legendre-Jumper-Martingale. Denken Sie an diese als Wettmaschinen, die „Vermögen“ (Evidenz) anhäufen, wann immer die Daten gegen die Regeln der Zufälligkeit verstoßen.

Hier ist eine Aufschlüsselung ihrer Funktionsweise unter Verwendung einfacher Analogien:

1. Der alte Detektiv: Der „Simple Jumper“

Vor diesem Papier war das beste Werkzeug der Simple Jumper. Stellen Sie sich vor, dieser Detektiv hat eine sehr einfache Strategie: Er wettet nur darauf, ob die durchschnittliche Zahl zu hoch oder zu niedrig ist.

Das Problem: Wenn die Daten um denselben Durchschnitt zentriert bleiben, aber plötzlich chaotisch werden (die Zahlen springen wild auf und ab oder werden in die Mitte zusammengedrückt), bemerkt dieser Detektiv dies überhaupt nicht. Er ist wie ein Sicherheitsmann, der nur prüft, ob jemand einen roten Hut trägt, aber ignoriert, wenn die Person um sich rennt und schreit.

2. Der neue Detektiv: Der „Simple Legendre Jumper“

Die Autoren haben den Detektiv aufgerüstet, indem sie ihm ein anspruchsvolleres Sichtfeld gegeben haben. Anstatt nur auf den Durchschnitt zu schauen, kann er nun die Form der Daten betrachten.

Die Analogie: Stellen Sie sich die Daten wie einen Haufen Sand vor. Der alte Detektiv prüfte nur, ob der Haufen zu hoch oder zu niedrig war. Der neue Detektiv kann auch prüfen, ob der Haufen zu breit ist (Varianz), ob er zu einer Seite neigt (Schiefe/Skewness) oder ob er seltsame Beulen hat (Kurtosis).
Wie es funktioniert: Er verwendet spezielle mathematische Formen, die Legendre-Polynome. Denken Sie an diese als verschiedene „Linsen“ oder „Filter“. Eine Linse sucht nach breiten Streuungen, eine andere nach geneigten Haufen und so weiter. Indem er auf diese Formen wettet, kann der Detektiv Änderungen erkennen, die der alte übersehen hätte.

3. Der „All-in-One“-Detektiv: Der „Product Legendre Jumper“

Was ist, wenn die Daten gleichzeitig alles falsch machen? Wenn sie chaotisch, geneigt und beulig zugleich sind?

Die Idee: Die Autoren haben einen Detektiv geschaffen, der gleichzeitig auf all diese Formen wettet. Er kombiniert die Linsen zu einem superstarken Werkzeug.
Der Haken (Die „Jumping Tax“): Um dies zu tun, muss der Detektiv jede mögliche Kombination von Formen gleichzeitig im Blick behalten. Wenn Sie 5 verschiedene Formen zu prüfen haben, explodiert die Anzahl der Kombinationen. Es ist, als müsste man sich jede mögliche Outfit-Kombination für 5 verschiedene Personen gleichzeitig merken. Der Detektiv wird so sehr durch den Versuch, alle Möglichkeiten zu prüfen, ausgebremst, dass er sich sehr langsam bewegt. Die Autoren nennen dies die „Jumping Tax“ – man zahlt einen hohen Preis an Geschwindigkeit und Speicherplatz, um diese Macht zu erhalten.

4. Der smarte Detektiv: Der „Variational Legendre Jumper“

Um die „Jumping Tax“ zu beheben, haben die Autoren einen klügeren Weg der Denkweise erfunden.

Die Analogie: Anstatt eines riesigen Detektivs, der versucht, jede Outfit-Kombination zu behalten, stellen Sie sich ein Team von Spezialisten vor. Einer beobachtet die Breite, ein anderer die Neigung, ein anderer die Beulen. Sie arbeiten unabhängig voneinander, teilen aber ihre Erkenntnisse, um eine endgültige Entscheidung zu treffen.
Das Ergebnis: Dieses Team (der Variational Legendre Jumper) ist fast so leistungsstark wie der riesige „All-in-One“-Detektiv, läuft aber unglaublich schnell. Er reduziert die Speicherkosten von „exponentiell“ (unmöglich für große Probleme) auf „linear“ (leicht zu handhaben). Es ist wie der Austausch eines Supercomputers, der abstürzt, gegen einen eleganten Laptop, der die Arbeit erledigt.

5. Das Sicherheitsnetz: Der „Composite Legendre Jumper“

In der realen Welt wissen Sie nie, wie schnell sich die Daten verändern werden. Manchmal ändern sie sich sofort, manchmal driften sie langsam ab.

Das Problem: Wenn Sie Ihren Detektiv darauf einstellen, schnell zu sein, könnten Sie durch langsame Änderungen verwirrt werden. Wenn Sie ihn auf langsam einstellen, könnten Sie einen plötzlichen Absturz verpassen.
Die Lösung: Der Composite Legendre Jumper ist wie die Einstellung eines ganzen Trupps von Detektiven, jeder mit einer anderen Geschwindigkeitseinstellung. Sie wetten alle zusammen, und das System stützt sich automatisch auf diejenigen, die in diesem Moment am besten arbeiten.
Der Bonus: Dieser Trupp besitzt auch einen „Vermögens-Boden“. Selbst wenn die Daten perfekt normal sind und niemand Geld verdient, garantiert das System, dass Sie nicht alles verlieren. Es stellt sicher, dass Sie immer ein Sicherheitsnetz haben.

Was haben sie herausgefunden?

Die Autoren haben diese Werkzeuge an einem realen Datensatz über die Weinqualität (Rotwein vs. Weißwein) getestet.

Das Ergebnis: Wenn die Daten zufällig gemischt wurden (normal), blieben alle Werkzeuge ruhig. Aber als die Daten nach Weintyp sortiert wurden (was eine plötzliche Verschiebung erzeugte), erkannten die neuen Werkzeuge (insbesondere die Variational- und Composite-Versionen) die Änderung viel schneller und stärker als der alte „Simple Jumper“.
Der Gewinner: Der Composite Legendre Jumper wird als die „Standardwahl“ empfohlen. Er ist das Schweizer Taschenmesser der Gruppe: Er bewältigt unbekannte Geschwindigkeiten, erkennt komplexe Änderungen und lässt Sie niemals pleite gehen.

Kurz gesagt: Das Papier liefert uns bessere Werkzeuge, um zu erkennen, wann Daten aufhören, sich zufällig zu verhalten. Sie haben diese Werkzeuge smarter gemacht (Prüfung komplexer Muster), schneller (Vermeidung der Steuer durch zu viele Kombinationen) und sicherer (Garantie eines Mindestwerts), was sie wesentlich besser darin macht, reale Datenverschiebungen zu erfassen.

Technisches Resümee: Wetten auf Momente – Legendre-Jumper-Martingale für Online-Austauschbarkeitstests

Problemstellung

In der konformen Prädiktion (Conformal Prediction) beruht die Validität von Vorhersagesets auf der Annahme der Austauschbarkeit (Exchangeability). Dies impliziert, dass die Sequenz der durch einen konformen Transducer generierten p-Werte unabhängig und identisch verteilt (IID) gemäß einer Gleichverteilung auf $[0, 1]$ ist. Verletzungen dieser Annahme deuten auf Verteilungsverschiebungen hin.

Obwohl konforme Test-Martingale (CTMs) verwendet werden, um die Austauschbarkeit online zu testen, weist das Standard-Simple Jumper (SJ)-Martingal (Vovk et al., 2022) eine kritische Einschränkung auf: Es verwendet eine lineare Wettfunktion basierend auf dem verschobenen Legendre-Polynom ersten Grades. Infolgedessen ist das SJ geometrisch darauf beschränkt, Verschiebungen im Mittelwert (Lageparameter) der p-Werte zu detektieren. Es versäumt es, signifikantes Vermögen anzuhäufen, wenn die Verteilungsverschiebung den Mittelwert beibehält, aber höhere Momente wie Varianz, Schiefe oder Kurtosis verändert. Darüber hinaus leiden Versuche, mehrere Wettstrategien zu kombinieren, oft unter der „Jumping Tax“ (Sprungsteuer), bei der das Kapital über einen exponentiell wachsenden Zustandsraum verwässert wird, was die Detektionsgeschwindigkeit erheblich behindert.

Methodik

Das Paper schlägt eine Familie von konformen Test-Martingalen vor, die auf verschobenen Legendre-Polynomen ( $\tilde{P}_k$ ) basieren, welche auf dem Intervall $[0, 1]$ orthogonal sind. Diese Polynome dienen als Basis für Wettfunktionen, die in der Lage sind, Abweichungen in spezifischen Momenten der p-Wert-Verteilung zu detektieren.

1. Simple Legendre Jumper (SLJ)

Der SLJ generalisiert den Simple Jumper, indem er die lineare Wettfunktion durch ein verschobenes Legendre-Polynom beliebigen Grades $k$ ersetzt:
$f^{(k)}_\epsilon(p) = 1 + \epsilon \tilde{P}_k(p)$
wobei $\epsilon$ ein aus einem diskreten Gitter ausgewähltes Parameter ist.

Mechanismus: Für $k=1$ stellt er das Standard-SJ wieder her (Detektion von Mittelwertverschiebungen); für $k=2$ detektiert er Varianzänderungen; für $k=3$ Schiefe; und so weiter.
Einschränkung: Das Wetten ausschließlich auf einen einzelnen Grad $k$ führt dazu, dass das Martingal dominante Verschiebungen in anderen Momenten übersieht, was zu einer suboptimalen Akkumulation von Evidenz führt.

2. Product Legendre Jumper (PLJ)

Um komplexe, multimodale Abweichungen gleichzeitig zu erfassen, kombiniert der PLJ Wettfunktionen mehrerer Grade $K$ in ein einziges Produkt:
$f^K_\epsilon(p) = \frac{\prod_{k \in K} (1 + \epsilon_k \tilde{P}_k(p))}{Z(\epsilon)}$
wobei $Z(\epsilon)$ eine Normalisierungskonstante ist, die für $|K| \ge 3$ erforderlich ist, um sicherzustellen, dass das Integral der Wettfunktion gleich 1 ist.

Die „Jumping Tax“: Der PLJ führt eine Markov-Kette über den gemeinsamen Zustandsraum $\mathcal{E} = \prod_{k \in K} \mathcal{E}_k$ . Wenn die Anzahl der Grade $|K|$ steigt, wächst die Größe des Zustandsraums exponentiell ( $|\mathcal{E}| = g^{|K|}$ ). Die „Jumping Tax“ bezieht sich auf die Verwässerung des Kapitals: Wenn sich die Umgebung verschiebt, verteilt der Sprungmechanismus das neue Kapital gleichmäßig über diesen massiven Zustandsraum, was die Konzentration des Vermögens auf die optimale Wettstrategie verzögert.

3. Variational Legendre Jumper (VLJ)

Um die exponentielle Skalierung des PLJ zu lösen, führt die Autorenschaft den Variational Legendre Jumper ein, der von Mean-Field-Approximationen in der Variationsinferenz inspiriert ist.

Entkopplung: Anstatt einer einzigen Markov-Kette über den Produktraum führt der VLJ $|K|$ unabhängige Sub-Jumper (einen für jeden Grad $k \in K$ ) aus.
Konsens: In jedem Schritt berechnet der VLJ einen Konsens-Parameter $\bar{\epsilon}_k$ für jeden Grad basierend auf dem vermögensgewichteten Mittelwert des Zustands des Sub-Jumpers.
Globaler Einsatz (Global Bet): Das globale Martingal aktualisiert sich unter Verwendung des normalisierten Produkts der Wettfunktionen, die an diesen Konsensparametern ausgewertet wurden.
Komplexität: Dies reduziert die Rechenkosten von exponentiell $O(g^{|K|})$ auf linear $O(|K| \cdot g)$ , wodurch das Testen höherer Momente rechentechnisch handhabbar wird, bei minimalem Verlust an statistischer Power.

4. Composite Legendre Jumper

Folgend dem Framework von Vovk et al. (2022) mittelt der Composite Legendre Jumper das Basismartingal (SLJ, PLJ oder VLJ) über ein Gitter von Sprungraten $J \in \{10^{-4}, \dots, 1\}$ .

Robustheit: Dies gewährleistet Robustheit, wenn die Zeitskala der Verteilungsverschiebung unbekannt ist.
Vermögensuntergrenze (Wealth Floor): Die Einbeziehung von $J=1$ garantiert, dass das Martingal unter Austauschbarkeit niemals unter $1/|\mathcal{E}|$ fällt, was eine absolute Vermögensuntergrenze bietet, die festen Rate-Varianten fehlt.

Zentrale Beiträge

Generalisierung von Wettfunktionen: Die Einführung des Simple Legendre Jumper, der die lineare Wettfunktion des Simple Jumpers auf beliebige verschobene Legendre-Polynome erweitert und somit die Detektion von Varianz-, Schiefe- und höheren Momentenabweichungen ermöglicht.
Adressierung der „Jumping Tax“: Die Entwicklung des Product Legendre Jumper zur Erfassung gemeinsamer Abweichungen, gefolgt vom Variational Legendre Jumper, der das gemeinsame Anpassungsproblem mittels Mean-Field-Approximation faktorisiert. Dies reduziert die Skalierung des Zustandsraums erfolgreich von exponentiell auf linear, während die statistische Power erhalten bleibt.
Komposite Robustheit: Die Integration dieser Methoden in einen Composite Legendre Jumper, der über Sprungraten mittelt, um eine automatische Anpassung an unbekannte Zeitskalen von Verschiebungen zu ermöglichen und eine garantierte Vermögensuntergrenze zu bieten.
Empirische Validierung: Demonstration auf einer realen Klassifikationsaufgabe (Wine Quality Datensatz) unter Verwendung eines konformen Nearest-Neighbor-Klassifikators unter vier Datenordnungen: gemischt (austauschbar), abrupte Change-Points (Rot $\to$ Weiß, Weiß $\to$ Rot) und Originalreihenfolge.

Ergebnisse

Die Autoren evaluierten die vorgeschlagenen Methoden auf dem Wine Quality Datensatz unter Verwendung eines konformen Nearest-Neighbor-Klassifikators unter vier Datenordnungen: gemischt (austauschbar), abrupte Change-Points (Rot $\to$ Weiß, Weiß $\to$ Rot) und Originalreihenfolge.

Austauschbarkeit: Unter gemischten Daten blieben alle Martingale nahe Null oder sanken leicht ab, was bestätigt, dass sie keine Fehlalarme auslösen.
Verteilungsverschiebung: Unter nicht-austauschbaren Ordnungen erreichten die Product und Variational Legendre Jumper mit $K=\{1, 2, 3\}$ konsistent die höchsten finalen Log-Martingal-Werte und übertrafen den Single-Degree Simple Legendre Jumper ( $k=1$ ) um 30 %–60 % im Log-Maßstab der Evidenz.
Versagen einzelner Grade: Martingale, die ausschließlich auf Varianz ( $k=2$ ) oder Schiefe ( $k=3$ ) wetteten, schnitten schlecht ab, wenn die Verschiebung mehrere Momente betraf, und akkumulierten um Größenordnungen weniger Evidenz als die kombinierten Ansätze.
Effizienz vs. Power: Der Variational Legendre Jumper (VLJ) erreichte fast exakt die Performance des Product Legendre Jumpers (PLJ), benötigte jedoch signifikant weniger Zustände (z. B. 15 Zustände gegenüber 125 Zuständen für $K=\{1, 2, 3\}$ ).
Überlegenheit des Compositen: Der Composite Legendre Jumper übertraf die Fixed-Rate-Varianten unter Verteilungsverschiebungen entscheidend (erreichte z. B. $\log_{10} M_n \approx 100$ gegenüber $\approx 90$ bei Fixed-Rate) und verhinderte die langsame Akkumulation von Verlusten, die bei Fixed-Rate-Varianten unter Austauschbarkeit auftritt.

Signifikanz und Behauptungen

Das Paper behauptet, dass der Composite Legendre Jumper die Standardwahl für Praktiker sein sollte, wenn die Zeitskala von Verteilungsverschiebungen unbekannt ist. Er bietet eine robuste Lösung, die:

Komplexe, multimodale Abweichungen von der Gleichverteilung detektiert, die lineare Wettfunktionen übersehen.
Den „Fluch der Dimensionalität“ vermeidet, der mit gemeinsamen Wettstrategien verbunden ist, durch die Verwendung der variativen Faktorisierung.
Eine theoretische und praktische Vermögensuntergrenze bietet, die Stabilität unter der Nullhypothese gewährleistet.

Die Autoren merken an, dass die Variational-Approximation empirisch auf einem ähnlichen Niveau wie das exakte Produkt operiert, die theoretischen Grenzen bezüglich des Verlusts an statistischer Power durch die Mean-Field-Faktorisierung jedoch ein offenes Problem bleiben. Sie schlagen zudem vor, dass zukünftige Arbeiten die datengesteuerte Auswahl von Polynomgraden (analog zu Ledwinas Ansatz für Neymans Smooth Test) untersuchen könnten, um die Effizienz weiter zu optimieren. Die Implementierung ist über das Python-Paket online-cp verfügbar.