📊 statistics

Hash-augmented adaptive multilevel splitting Monte Carlo algorithm for accurate estimation of two-sample permutation test p-values

Dieses Paper stellt einen Hash-augmentierten adaptiven Multilevel-Splitting-Monte-Carlo-Algorithmus vor, der im Python-Paket `hamstest` implementiert ist, um beliebig kleine p-Werte für Zwei-Stichproben-Permutationstests mit komplexen Statistiken präzise zu schätzen und gleichzeitig Herausforderungen im Zusammenhang mit der Diskretisierung der Verteilung sowie der Gewährleistung gültiger Konfidenzintervalle zu bewältigen.

Ursprüngliche Autoren: Nikita Golikov, Vladimir Sukhov, Gennady Korotkevich, Alexey Sergushichev

Veröffentlicht 2026-07-15

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Nikita Golikov, Vladimir Sukhov, Gennady Korotkevich, Alexey Sergushichev

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 versucht, einen sehr seltenen Kriminellen in einer Stadt mit Millionen von Einwohnern zu fassen. Sie haben eine Liste von Verdächtigen (Ihre Daten) und wollen wissen: „Wie wahrscheinlich ist es, dass dieses spezifische Muster an Hinweisen rein durch Glück entstanden ist?“ In der Welt der Statistik nennt man das einen Permutationstest. Man mischt die Hinweise Millionen von Malen durch, um zu sehen, wie oft ein „glückliches“ Muster auftritt.

Normalerweise, wenn das Muster häufig vorkommt, kann man einfach die glücklichen Durchmischungen zählen. Aber was, wenn das Muster so selten ist, dass es nur einmal in einer Billion Versuchen auftritt? Das ist, als würde man versuchen, ein einzelnes bestimmtes Sandkorn auf einem Strand zu finden, der so groß wie ein Planet ist. Wenn Sie versuchen, dieses Korn durch zufälliges Auswählen einzelner Körner zu finden (die alte Monte-Carlo-Methode), könnten Sie Ihr ganzes Leben lang Sand auswählen und immer noch nie dieses eine Korn finden. Sie müssten $10^{10}$ Körner auswählen, nur um eine vernünftige Schätzung für eine winzige Wahrscheinlichkeit von $10^{-10}$ zu erhalten, was völlig unpraktikabel ist.

Das Problem: Der „steckengebliebene“ Aufzug

Den Autoren dieser Arbeit wurde klar, dass Standardmethoden bei der Behandlung solcher winzigen Wahrscheinlichkeiten an eine Wand stoßen, insbesondere weil die „Sandkörner“ (die Datenkombinationen) nicht alle einzigartig sind. Manchmal führen tausende verschiedene Durchmischungen zum exakt gleichen Ergebnis. Es ist, als wäre ein Aufzug, der nur in den 1., 10. und 100. Stock fährt, aber die 2. bis 99. Etage überspringt. Wenn Sie versuchen, in den 99. Stock zu gelangen, kann der Aufzug dort einfach nicht halten, weil dieser nicht existiert. Diese „Diskretion“ führt dazu, dass die Mathematik stecken bleibt, was es unmöglich macht, zu schätzen, wie selten ein Ereignis wirklich ist.

Die Lösung: Das „Hash“-Tag und die Sprossenleiter

Das Team unter der Leitung von Nikita Golikov und Kollegen entwickelte ein neues Werkzeug namens hamstest. Ihr Geheimrezept ist ein cleverer Trick namens hash-augmentierte adaptive mehrstufige Spaltung (hash-augmented adaptive multilevel splitting).

So funktioniert es, unter Verwendung einer unterhaltsamen Analogie:

Die Leiter (Multilevel Splitting): Anstatt zu versuchen, direkt auf den Gipfel des Berges zu springen (das seltene Ereignis), bauen sie eine Leiter. Sie beginnen unten und fragen: „Wie viele Menschen erreichen die erste Sprosse?“ Dann: „Wie viele dieser Menschen erreichen die zweite Sprosse?“ Sie teilen die Gruppe immer wieder in immer kleinere Gruppen auf, während sie höher klettern. Dies verwandelt einen unmöglichen Sprung in eine Reihe von einfachen, handhabbaren Schritten.
Das „Hash“-Tag (Die Lösung für den steckengebliebenen Aufzug): Das große Problem war, dass viele Menschen auf derselben Sprosse standen (denselben Score hatten), was es unmöglich machte, die Gruppe weiter aufzuspalten. Um dies zu beheben, gaben die Autoren jedem einzelnen Menschen ein einzigartiges, unsichtbares Hash-Tag (eine Zufallszahl). Selbst wenn zwei Menschen denselben Score haben, sind ihre Hash-Tags unterschiedlich. Dies ermöglicht es dem Algorithmus zu sagen: „Okay, wir können nicht nach dem Score aufteilen, aber wir können nach dem Hash-Tag aufteilen.“ Dies verwandelt einen flachen, feststeckenden Boden in eine glatte, kontinuierliche Treppe, auf der der Algorithmus immer die nächste Stufe finden kann.

Was sie fanden (und was sie nicht fanden)

Die Autoren testeten diese neue Methode an zwei klassischen statistischen Tests: dem Kolmogorov–Smirnov-Test und dem Mann–Whitney–U-Test.

Die Ergebnisse: In ihren Simulationen war die neue Methode unglaublich genau. Als sie versuchten, Wahrscheinlichkeiten so winzig wie $10^{-243}$ (das ist eine 1 mit 243 Nullen!) zu schätzen, landeten die Schätzungen der Methode genau beim wahren Wert. Sie berechneten auch Konfidenzintervalle (einen Bereich, in dem sich die wahre Antwort wahrscheinlich verbirgt), und in etwa 95 % ihrer Testläufe lag die wahre Antwort innerhalb dieses Bereichs.
Die „Full Resampling“-Regel: Sie probierten verschiedene Wege aus, um die Simulation durchzuführen. Sie fanden heraus, dass eine Methode namens „Full Resampling“ (bei der sie bei jedem Schritt alle Stichproben neu mischen) am zuverlässigsten und robustesten ist. Sie schlagen vor, eine spezifische Einstellung namens $\alpha = 1$ als Standard zu verwenden, da diese in ihren Tests am besten funktionierte.
Was sie ausschlossen: Sie zeigten explizit auf, dass der alte Weg (nur den Score ohne das Hash-Tag zu verwenden) versagt, wenn die Daten „große Sprünge“ oder viele Bindungen (Ties) aufweisen. Sie bewiesen, dass der Algorithmus ohne das Hash-Tag stecken bleiben und falsche Antworten liefern kann. Sie merkten auch an, dass ihre Methode zwar gut für einseitige Tests funktioniert (Suche nach einem Muster in eine Richtung), die zweiseitige Version des Kolmogorov–Smirnov-Tests jedoch knifflig ist, da der „Aufzug“ ganz oben entkoppelt werden kann, was eine spezielle Handhabung erfordert.

Wie schnell ist es?

Das Team maß, wie lange der Algorithmus auf einem modernen Computer (einem Apple M3 Pro) benötigt. Sie fanden heraus, dass die Zeit, die der Algorithmus benötigt, hauptsächlich davon abhängt, wie selten das Ereignis ist. Wenn man nach etwas extrem Seltenem sucht (wie einem p-Wert von $10^{-100}$ ), dauert es länger, weil man mehr Sprossen der Leiter erklimmen muss. Jedoch hing die Zeit beim Mann–Whitney–U-Test nicht viel von der Größe des Datensatzes ab, da die Mathematik für diesen spezifischen Test sehr effizient aktualisiert werden kann.

Das Fazit

Die Autoren haben nicht „jedes“ statistische Problem im Universum gelöst, aber sie haben ein sehr mächtiges, flexibles Werkzeug geschaffen, das für jeden benutzerdefinierten Teststatistiken funktionieren kann, den ein Wissenschaftler erfinden könnte. Sie haben dieses Werkzeug in einer kostenlosen Python-Bibliothek namens hamstest verpackt.

Sie schlagen vor, dass für die meisten Menschen die Methode des „Full Resampling“ mit $\alpha = 1$ die beste Wahl ist. Sie weisen auch darauf hin, dass die Methode zwar schnell ist, die exakte Zeit jedoch von der spezifischen Mathematik des Tests abhängt, den man ausführt. Wenn Sie ein Forscher sind, der mit winzigen Wahrscheinlichkeiten und unordentlichen Daten zu tun hat, bietet dieses Werkzeug einen Weg zu genauen Antworten, ohne auf den Wärmetod des Universums warten zu müssen.

Kurz gesagt: Sie haben einen kaputten, steckengebliebenen Aufzug in ein glattes, schnelles Rolltreppen-System verwandelt, das Sie ganz nach oben auf den statistischen Berg bringen kann, selbst wenn der Pfad voller Schlaglöcher ist.

Technische Zusammenfassung: Hash-augmentiertes adaptives mehrstufiges Splitting für Permutationstest-p-Werte

Problemstellung
Nichtparametrische Permutationstests, wie etwa der Kolmogorov–Smirnov- und der Mann–Whitney–U-Test, sind grundlegend für die statistische Hypothesenprüfung, insbesondere beim Vergleich zweier Gruppen ohne Annahme einer spezifischen Datenverteilung. Während eine exakte p-Wert-Berechnung ideal ist, ist sie für komplexe oder benutzerdefinierte Teststatistiken aufgrund der exponentiellen Anzahl möglicher Permutationen ( $\binom{n+m}{n}$ ) oft algorithmisch nicht handhabbar. Folglich verlassen sich Forscher auf Monte-Carlo-Sampling. Standardmäßige Monte-Carlo-Methoden leiden jedoch unter einer schlechten relativen Genauigkeit bei der Schätzung sehr kleiner p-Werte (z. B. $10^{-10}$ oder kleiner), was eine unpraktikable Anzahl von Stichproben erfordert, um nach multiplen Hypothesenkorrekturen statistische Power zu erreichen.

Darüber hinaus führt die Anwendung von Multilevel Splitting – einer Technik zur Schätzung seltener Ereigniswahrscheinlichkeiten durch die Zerlegung in ein Produkt bedingter Wahrscheinlichkeiten – auf Permutationstests spezifische Herausforderungen ein. Permutationstests operieren in diskreten Räumen, in denen die Verteilung der Teststatistik oft große Sprünge (Diskretisierung) aufweist. In solchen Fällen können viele verschiedene Kombinationen von Daten identische Statistikwerte ergeben. Diese Diskretisierung kann die adaptive Auswahl intermediärer Level verhindern, die für das Multilevel Splitting erforderlich sind, und dazu führen, dass der Algorithmus fehlschlägt oder verzerrte Schätzungen liefert, wenn die bedingte Wahrscheinlichkeit, zum nächsten Level überzugehen, nicht nahe an einer Zielkonstante (z. B. 0,5) gehalten werden kann.

Methodik
Die Autoren schlagen einen hash-augmentierten adaptiven Multilevel-Splitting-Monte-Carlo-Algorithmus vor, um die Diskretisierungsprobleme zu adressieren, die in Permutationstests inhärent sind. Die Kernmethodik umfasst drei Schlüsselkomponenten:

Hash-augmentierte Ordnung: Um das Problem zu lösen, dass mehrere Kombinationen denselben Statistikwert teilen, führen die Autoren eine strikte totale Ordnung auf die Kombinationen ein. Anstatt nur nach der Teststatistik $S(A)$ zu ordnen, definieren sie eine Ordnung $A \succ_{S,h} B$ , die zuerst auf dem Statistikwert basiert und bei identischen Statistiken durch einen Hash-Wert $h(A)$ ergänzt wird.
- Die Hash-Funktion $h(A)$ bildet Kombinationen auf ganze Zahlen ab. Eine praktische Implementierung verwendet eine Summe unabhängiger zufälliger Ganzzahlen, die jedem Element zugewiesen sind, was $O(1)$ -Updates während der Markov-Chain-Monte-Carlo-Schritte (MCMC) ermöglicht.
- Diese Augmentierung "glättet" effektiv die diskrete Verteilung und stellt sicher, dass für jede Level-Grenze eine gültige nächste Grenze gefunden werden kann, sodass die bedingte Wahrscheinlichkeit schätzbar bleibt.
Adaptives Multilevel Splitting mit MCMC: Der Algorithmus schätzt den p-Wert $Pr(S \ge \gamma)$ , indem er diesen in ein Produkt bedingter Wahrscheinlichkeiten über eine Sequenz verschachtelter Ereignisse zerlegt, die durch die hash-augmentierte Ordnung definiert sind.
- Adaptive Level: Beginnend mit einem trivialen Level sampelt der Algorithmus Kombinationen und nutzt deren Quantile (z. B. den Median), um die nächste Level-Grenze zu definieren.
- MCMC-Sampling: Um Stichproben für das nächste Level zu generieren, verwendet der Algorithmus ein Metropolis-artiges MCMC-Verfahren. Er startet mit bestehenden Stichproben, die die neue Grenzbedingung erfüllen, und stört diese (durch Vertauschen von Elementen), um neue unabhängige Stichproben zu erzeugen.
- Resampling-Strategien: Die Arbeit evaluiert "Full Resampling" (Duplizieren bestehender gültiger Stichproben und Störung aller von ihnen) gegenüber "Partial Resampling" (nur eine Teilmenge der Stichproben stören). Es wurde festgestellt, dass Full Resampling robuster gegenüber den durch die Diskretisierung des Problems eingeführten Sampling-Biases ist.
Schätzung im Log-Raum: Der Algorithmus schätzt den Logarithmus des p-Werts, um extreme Werte ohne numerischen Underflow zu handhaben. Er nutzt die Digamma- ( $\psi$ ) und Trigamma-Funktionen ( $\psi_1$ ), um den Mittelwert und die Varianz der Log-Schätzungen zu berechnen, die aus den Eigenschaften der Ordnungsstatistiken von Gleichverteilungen abgeleitet sind. Dies ermöglicht die Konstruktion valider Konfidenzintervalle.

Wesentliche Beiträge

Algorithmische Innovation: Die Einführung eines hash-augmentierten Ordnungsschemas, das es dem adaptiven Multilevel Splitting ermöglicht, in diskreten Permutationsräumen korrekt zu funktionieren, und so das "Large Jump"-Problem überwindet, bei dem Standardmethoden versagen.
Robuste Implementierung: Eine detaillierte Analyse der Resampling-Strategien (Full vs. Partial) und der MCMC-Stoppkriterien, die zeigt, dass Full Resampling mit einem spezifischen Skalierungsparameter ( $\alpha=1$ ) das beste Gleichgewicht zwischen Konvergenzgeschwindigkeit und Bias-Reduktion bietet.
Software-Release: Die Entwicklung und Open-Source-Veröffentlichung des Python-Pakets hamstest, welches den vorgeschlagenen Algorithmus implementiert. Es ermöglicht Nutzern, benutzerdefinierte Teststatistiken zu definieren, und bietet effiziente Schnittstellen (einschließlich C++-Backends) für die Hochleistungs-p-Wert-Schätzung.
Validierung: Ein strenger Vergleich gegen exakte Algorithmen für Kolmogorov–Smirnov- und Mann–Whitney–U-Tests, der zeigt, dass die vorgeschlagene Methode p-Werte so klein wie $10^{-243}$ mit validen Konfidenzintervallen genau schätzt.

Ergebnisse
Die Autoren evaluierten den Algorithmus sowohl für Kolmogorov–Smirnov- als auch für Mann–Whitney–U-Tests über verschiedene Stichprobengrößen ( $n+m$ bis zu 10.000) und Ziel-p-Werte (bis zu $10^{-100}$ ).

Genauigkeit: Die geschätzten p-Werte stimmten eng mit den wahren Werten (berechnet via exakter Methoden, sofern verfügbar) überein, ohne sichtbare Verzerrung. Der Median der Schätzungen lag über alle getesteten Parameter hinweg im Einklang mit dem wahren p-Wert.
Konfidenzintervalle: Die konstruierten 95%-Konfidenzintervalle (basierend auf $\log \hat{p} \pm 2\hat{\sigma}$ ) erfassten in der überwiegenden Mehrheit der unabhängigen Durchläufe den wahren Log-p-Wert, was die theoretischen Varianzschätzungen validiert.
Performance: Die Laufzeiten hingen primär von der Größenordnung des p-Werts und der Stichprobengröße ab. Der Algorithmus zeigte eine lineare Skalierbarkeit bezüglich der Anzahl der benötigten Level, was die Schätzung extrem kleiner p-Werte ermöglicht, die für Standard-Monte-Carlo-Verfahren rechnerisch nicht handhabbar wären.
Resampling-Vergleich: Die "Full-Median"-Variante (Full Resampling mit Median-Grenzwahl) übertraf die Partial-Resampling-Varianten konsistent in Bezug auf Konvergenzgeschwindigkeit und Robustheit gegenüber Bias, insbesondere beim Kolmogorov–Smirnov-Test, wo die Diskretisierung der Verteilung ausgeprägter ist.

Bedeutung
Das Paper behauptet, dass diese Arbeit eine wesentliche Verbesserung gegenüber klassischen Monte-Carlo-Ansätzen für die p-Wert-Schätzung in Permutationstests darstellt. Durch die Adressierung der spezifischen Fallstricke diskreter Räume – nämlich der Unfähigkeit, intermediäre Level aufgrund von Bindungen (Ties) bei den Teststatistiken zu definieren – ermöglicht der vorgeschlagene Algorithmus die genaue und effiziente Schätzung beliebig kleiner p-Werte. Diese Fähigkeit ist entscheidend für moderne High-Throughput-Anwendungen (z. B. Genomik, Neurowissenschaften), bei denen tausende Tests simultan durchgeführt werden und eine präzise Kontrolle der False Discovery Rates eine zuverlässige Schätzung der Tail-Wahrscheinlichkeiten erfordert. Die Autoren merken an, dass eine frühere Version dieses Algorithmus (oh-ne die Hash-Augmentierung) bereits erfolgreich in der Gene Set Enrichment Analysis (GSEA) eingesetzt wurde; die vorliegende Arbeit erweitert diesen Nutzen auf eine breitere Klasse von Zwei-Stichproben-Statistiken und löst die Instabilitätsprobleme, die bei bestimmten Eingangsverteilungen auftraten. Die Verfügbarkeit des hamstest-Pakets stellt sicher, dass diese fortgeschrittenen statistischen Fähigkeiten für benutzerdefinierte Statistiken in praktischen Forschungsabläufen zugänglich sind.