Fast confidence bounds for the false discovery proportion over a path of hypotheses

Dit paper introduceert een nieuw algoritme dat de berekening van post-hoc grenzen voor de False Discovery Proportion over een pad van hypotheses versnelt van $O(|\mathcal K|m^2)$ naar $O(|\mathcal K|m)$ door gebruik te maken van de boomstructuur van de referentiefamilie.

De kern

Titel: De Snelweg voor Wetenschappelijke Ontdekkingen: Hoe je duizenden hypotheses in een flits controleert

Stel je voor dat je een gigantische bibliotheek binnenstapt met miljoenen boeken (hypothesen). Je wilt weten welke boeken waarheid bevatten en welke nep zijn. Maar je hebt geen tijd om elk boek één voor één te lezen. Je wilt een snelle manier hebben om te zeggen: "Ik heb 100 boeken uitgezocht, en ik ben er 95% zeker van dat er maximaal 5 nep-boeken tussen zitten."

In de statistische wereld noemen we dit het controleren van de False Discovery Proportion (FDP). Het is cruciaal in onderzoek, bijvoorbeeld bij het zoeken naar genen die ziektes veroorzaken of bij het scannen van hersenbeelden.

Dit artikel van Guillermo Durand introduceert een nieuwe, razendsnelle manier om deze controle uit te voeren, zelfs als je je zoektocht stap voor stap uitbreidt.

Het Probleem: De "Slome" Weg

Stel je voor dat je een bos hebt met bomen (de hypotheses). Je wilt weten hoeveel "dode takken" (foute ontdekkingen) er in een bepaalde groep zitten.

• De oude manier (Naïef): Je loopt elke keer opnieuw door het hele bos om te tellen. Als je 1000 bomen hebt, moet je dit 1000 keer doen. Elke keer tel je alles opnieuw. Dit is als het proberen van elke sleutel op een ring om een deur te openen, elke keer opnieuw. Het kost eeuwen.
• Het probleem: In de wetenschap willen we vaak een "curve" zien: wat gebeurt er als we 1 boom toevoegen? Dan 2? Dan 3? De oude methode wordt hierdoor onmogelijk traag.

De Oplossing: Een Slimme Boswachter

De auteur bedacht een nieuwe methode die gebruikmaakt van de structuur van het bos. In veel wetenschappelijke studies zijn hypotheses niet willekeurig; ze zitten in groepen.

• Genen zitten in chromosomen.
• Hersengebieden zitten in lobben.
• Dit noemen we een Woudstructuur (Forest Structure).

De nieuwe algoritmen (de "slimme boswachters") doen twee dingen:

1. Het "Vijgen" van het Woud (Pruning)

Stel je voor dat je een boom hebt met een tak die al volledig dood is, en die tak bestaat uit kleinere takjes die ook dood zijn.

• De slimme truc: Als je weet dat de grote tak al "vol" is met fouten, heb je geen zin meer om de kleine takjes eronder te tellen. Je knipt de hele grote tak eraf en zegt: "Oké, deze hele sectie is al geteld, we hoeven niet meer hiernaartoe."
• Dit noemt de auteur Pruning. Het verwijdert onnodige werk. Het is alsof je een overvolle koffer uitpakt en de dubbelgepakte kleding eruit haalt voordat je gaat reizen.

2. De "Opwaartse" Teller (Fast Algorithm)

Dit is de echte magische truc.

• De oude manier: Tel alles opnieuw van nul.
• De nieuwe manier: Je telt niet opnieuw. Je loopt gewoon een pad door het bos. Als je van stap 10 naar stap 11 gaat, voeg je één nieuwe boom toe.
  • De nieuwe boswachter kijkt alleen naar die ene nieuwe boom.
  • Hij vraagt zich af: "Valt deze boom onder een groep die al vol zit?"
  • Als ja: niets verandert in de telling.
  • Als nee: hij telt gewoon +1.
  • Hij werkt zich dan snel omhoog in de boomstructuur (van tak naar stam) om te zien of de "capaciteit" van die groep vol zit.
• Het resultaat: In plaats van het hele bos opnieuw te tellen, doet hij slechts een paar snelle checks. Het is als het bijwerken van een scorebord in een voetbalwedstrijd: je hoeft niet de hele wedstrijd opnieuw te spelen om de nieuwe score te weten; je telt gewoon +1 bij de vorige score.

Waarom is dit zo belangrijk?

In het artikel wordt een voorbeeld gegeven waarbij de nieuwe methode 33.000 keer sneller is dan de oude methode.

• Vroeger: Als je een simulatie wilde doen met 10.000 hypotheses, duurde het berekenen van de volledige curve dagen of weken. Wetenschappers moesten vaak genoegen nemen met slechts een paar steekproeven.
• Nu: Met deze nieuwe methode kan diezelfde berekening in een fractie van een seconde. Je kunt nu 100% van de curve zien, in plaats van slechts een klein stukje.

De Metafoor: De Supermarkt

Stel je voor dat je een supermarkt binnengaat en je wilt weten hoeveel producten in je winkelmandje "vervalsen" (nep zijn).

• Oude methode: Elke keer als je een nieuw product toevoegt, loop je door de hele supermarkt om te controleren of je totale aantal nep-producten nog binnen de limiet valt.
• Nieuwe methode: De supermarkt is opgedeeld in schappen (het woud). Je weet dat Schap A maximaal 2 nep-producten kan hebben.
  • Je voegt een product toe aan Schap A.
  • Je kijkt alleen naar Schap A. Is het nu vol? Nee? Dan is je totale telling gewoon +1.
  • Is Schap A nu vol? Dan "sluit" je Schap A (pruning) en hoef je er nooit meer naar te kijken, zelfs niet als je nog 100 producten toevoegt aan andere schappen.

Conclusie

Dit artikel biedt een nieuwe "snelweg" voor statistici. Door slim gebruik te maken van de natuurlijke groepering van data (het woud) en door onnodig werk weg te knippen (pruning), kunnen onderzoekers nu veel grotere en complexere vragen beantwoorden dan ooit tevoren. Het maakt het mogelijk om met meer zekerheid en in minder tijd te zeggen: "Ja, deze ontdekkingen zijn betrouwbaar."

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "Fast confidence bounds for the false discovery proportion over a path of hypotheses" van Guillermo Durand, geschreven in het Nederlands.

Titel: Snelle betrouwbaarheidsgrenzen voor de proportie van valse ontdekkingen over een pad van hypothesen

1. Het Probleem

In het veld van meervoudig toetsen (multiple testing), zoals bij Genoom-Wide Association Studies (GWAS) of functionele MRI, is het vaak nodig om post-hoc inferentie uit te voeren. Dit betekent dat onderzoekers na het verzamelen van data een selectie van hypothesen maken en willen weten hoeveel van deze selectie waarschijnlijk "valse ontdekkingen" (false discoveries) zijn.

De traditionele aanpak richt zich op het controleren van de False Discovery Rate (FDR), wat een verwachte waarde is. Een robuustere aanpak is het berekenen van een bovengrens voor het aantal valse ontdekkingen met een bepaalde betrouwbaarheid (post hoc bounds). Dit leidt tot een controle van de False Discovery Proportion (FDP) met hoge waarschijnlijkheid (False Discovery Exceedance of FDX).

De uitdaging:
De methode van Blanchard et al. (2020) en Durand et al. (2020) maakt gebruik van een "referentiefamilie" van hypotheseregions om deze bovengrenzen te construeren. Als deze referentiefamilie een bosstructuur (forest structure) heeft (waarbij regions ofwel disjunct zijn ofwel genest), kan de bovengrens $V^*_R(S)$ voor een enkele selectie $S$ efficiënt worden berekend.

Echter, in de praktijk willen onderzoekers vaak de bovengrens berekenen voor een heel pad van toenemende selectiesets $(S_1, S_2, \dots, S_m)$, bijvoorbeeld gebaseerd op de $t$ kleinste p-waarden. Het herhaaldelijk toepassen van de bestaande algoritmen voor elke stap $t$ resulteert in een rekencomplexiteit van $O(|K|m^2)$, waarbij $|K|$ de grootte van de referentiefamilie is en $m$ het aantal hypothesen. Voor grote datasets is dit te traag en onpraktisch.

2. Methodologie

Het artikel introduceert een nieuwe aanpak die de rekencomplexiteit drastisch verlaagt door gebruik te maken van de incrementele aard van de selectiepaden (waarbij $S_{t+1} = S_t \cup \{i_{t+1}\}$).

De methodologie bestaat uit drie hoofdblokken:

A. Pruning van het bos (Algoritme 2)

Voordat de berekeningen beginnen, wordt de referentiefamilie geoptimaliseerd.

• Principe: Als een regio $R_k$ een bovengrens $\zeta_k$ heeft die groter is dan of gelijk is aan de som van de bovengrenzen van zijn directe kinderen in het bos ($\zeta_k \geq \sum \zeta_{k'}$), dan draagt deze regio $R_k$ nooit bij aan de minimale waarde in de berekening van de bovengrens.
• Actie: Dergelijke "redundante" regio's worden verwijderd uit de familie.
• Resultaat: Dit verkleint de grootte van de familie $|K|$ zonder de statistische garantie te verliezen, wat de berekening versnelt.

B. Het Snelle Algoritme voor een Kromme (Algoritme 3 en 4)

In plaats van de berekening voor elke $S_t$ vanaf nul te starten, gebruikt het nieuwe algoritme de resultaten van $S_t$ om $S_{t+1}$ te berekenen.

• Mechanisme: Het algoritme onderhoudt een teller $\eta_k$ voor elke regio $R_k$ in het bos. Deze teller vertegenwoordigt het aantal hypothesen in $S_t \cap R_k$ dat nog "actief" is (d.w.z. nog niet de grens $\zeta_k$ heeft bereikt).
• Update: Wanneer een nieuwe hypothees $i_{t+1}$ wordt toegevoegd aan de selectie:
  1. Het algoritme volgt het pad in het bos van de bladnode (atom) van $i_{t+1}$ naar de wortel.
  2. Voor elke regio op dit pad wordt de teller $\eta_k$ met 1 verhoogd.
  3. Zodra $\eta_k$ de drempelwaarde $\zeta_k$ bereikt, wordt deze regio "verzadigd". De regio en al zijn sub-structuren worden gemarkeerd als niet-bijdragend voor verdere berekeningen (ze worden toegevoegd aan een verzameling $K^-$).
• Complexiteit: Door deze incrementele update en het gebruik van de bosstructuur, daalt de complexiteit van $O(|K|m^2)$ naar $O(|K|m)$ (of specifieker $O(Hm + |K|)$, waarbij $H$ de diepte van het bos is).

C. Implementatie

De algoritmen zijn geïmplementeerd in het R-pakket sanssouci. De datastructuur gebruikt lijsten om de atomen (bladeren) en de regio's per diepte te representeren, wat efficiënte toegang mogelijk maakt.

3. Belangrijkste Bijdragen

1. Nieuw Algoritme (Algorithm 3/4): Een lineaire-tijd algoritme ($O(|K|m)$) om de volledige kromme van post-hoc bovengrenzen te berekenen voor een genest pad van selecties, in plaats van kwadratische tijd.
2. Pruning-strategie (Algorithm 2): Een methode om de referentiefamilie vooraf te minimaliseren, wat de rekenlast verder verlaagt en de efficiëntie van zowel het oude als het nieuwe algoritme verbetert.
3. Formele Bewijzen: Het artikel bevat rigoureuze wiskundige bewijzen (in Sectie 7) dat het nieuwe algoritme correct de minimale waarden berekent die nodig zijn voor de betrouwbaarheidsgrenzen, en dat de pruning geen informatie verliest.
4. Praktische Toepasbaarheid: Het maakt het mogelijk om simulatiestudies uit te voeren met een groot aantal herhalingen en volledige krommen, wat voorheen ondoenbaar was vanwege de rekentijd.

4. Resultaten

De auteurs hebben numerieke experimenten uitgevoerd om de prestaties te vergelijken tussen de "naïeve" aanpak (herhaaldelijk het oude algoritme aanroepen) en de nieuwe snelle aanpak (met en zonder pruning).

• Snelheidswinst: De nieuwe methode is aanzienlijk sneller. In Scenario 3 (met $m=10.240$ hypothesen) werd de rekentijd met een factor 33.000 verbeterd.
  • Naïeve aanpak: ~337 seconden.
  • Snelle aanpak (gepruned): ~0,01 seconden.
• Effect van Pruning: Pruning levert een extra snelheidswinst op (factor 2 tot 3 binnen de snelle methode), vooral wanneer de data weinig signaal bevat, waardoor meer regio's kunnen worden verwijderd.
• Schalingsgedrag: De resultaten bevestigen de theoretische complexiteit: de naïeve methode schaalt kwadratisch met $m$, terwijl de nieuwe methode lineair schaalt.

5. Betekenis en Conclusie

Dit werk is van groot belang voor de statistische praktijk in de bio-informatica en neurowetenschappen.

• Haalbaarheid van Simulaties: Het maakt uitgebreide simulatiestudies mogelijk om nieuwe methoden te valideren, waarbij men nu volledige krommen van FDP-grenzen kan analyseren in plaats van slechts enkele punten.
• Interactieve Analyse: Het stelt onderzoekers in staat om interactief te werken met grote datasets (bijvoorbeeld in Shiny-applicaties), waarbij ze direct feedback krijgen over de betrouwbaarheid van hun selecties terwijl ze de drempelwaarden aanpassen.
• Toekomstperspectief: De auteurs benadrukken dat verdere ontwikkeling van het sanssouci-pakket nodig is, waaronder het vereenvoudigen van de dataformaten en het integreren van methoden voor afhankelijke p-waarden.

Kortom, het artikel biedt een fundamentele algoritmische verbetering die de barrière voor het gebruik van robuuste post-hoc inferentie in grote datasets significant verlaagt.