Bootstrapping over grote datasets

Bootstrapping is een handige techniek om statistische kenmerken (denk aan gemiddelde, deciel, betrouwbaarheidsintervallen) van een populatie af te leiden op basis van een verzamelde steekproef. Het op schaal implementeren kan moeilijk zijn en in use cases met streaming data onmogelijk. Toen ik probeerde te leren hoe je op schaal kunt bootstrappen, kwam ik een Google-blog tegen (bijna tien jaar oud) die Poisson-bootstrapping introduceert. Sindsdien heb ik een nog ouder artikel ontdekt, Hanley en MacGibbon (2006), dat een versie van deze techniek schetst. Deze post is een poging om er zeker van te zijn dat ik de logica goed genoeg heb begrepen om het aan iemand anders uit te leggen. We beginnen met een beschrijving van klassieke bootstrapping om eerst te motiveren waarom Poisson-bootstrapping gaaf is.

Klassieke bootstrapping

Stel dat we de gemiddelde leeftijd van leerlingen op een school willen berekenen. We kunnen herhaaldelijk steekproeven van 100 leerlingen trekken, de gemiddelden berekenen en ze opslaan. Vervolgens kunnen we een eindgemiddelde van die steekproefgemiddelden nemen. Dit eindgemiddelde is een schatting van het populatiegemiddelde.

In de praktijk is het vaak niet mogelijk om herhaalde samples uit een populatie te trekken. Dit is waar bootstrapping om de hoek komt kijken. Bootstrapping bootst dit proces een beetje na. In plaats van samples uit de populatie te trekken, trekken we samples (met vervanging) uit het ene sample dat we hebben verzameld. De pseudo-samples worden resamples genoemd.

Het blijkt dat dit extreem effectief is. Het is rekenkundig duurder dan een gesloten vormoplossing, maar maakt geen sterke aannames over de verdeling van de populatie. Bovendien is het goedkoper dan het herhalen van steekproefverzamelingen. In de praktijk wordt het veel gebruikt in de industrie, omdat gesloten vormoplossingen in veel gevallen niet bestaan ​​of moeilijk goed te krijgen zijn, bijvoorbeeld bij het afleiden van decielen van een populatie.

Waarom werkt bootstrapping?

Bootstrapping voelt verkeerd. Of in ieder geval de eerste keer dat ik erover hoorde, voelde het niet goed. Waarom zou één sample zoveel informatie moeten bevatten?

Sampling met vervanging van de originele steekproef die u trok, is gewoon een manier om het trekken van de populatie na te bootsen. De originele steekproef die u trok, lijkt gemiddeld op uw populatie. Dus wanneer u er opnieuw een steekproef uit trekt, trekt u in feite steekproeven uit dezelfde waarschijnlijkheidsverdeling.

Wat als je toevallig een vreemde steekproef trekt? Dat kan en daarom nemen we een resampling. Resampling helpt ons om meer te leren over de distributie van de steekproef zelf. Wat als je originele steekproef te klein is? Naarmate het aantal observaties in de steekproef groeit, convergeren bootstrapping-schattingen naar populatiewaarden. Er zijn echter geen garanties over eindige steekproeven.

Er zijn problemen, maar gezien de beperkingen waarin we opereren, is dit de best mogelijke informatie die we hebben over de populatie. We hoeven er niet van uit te gaan dat de populatie een specifieke vorm heeft. Aangezien berekeningen vrij goedkoop zijn, wordt bootstrapping een zeer krachtig hulpmiddel om te gebruiken.

Demonstratie van klassieke bootstrapping

We leggen bootstrapping uit met twee voorbeelden. De eerste is een kleine dataset waarbij het idee is dat je de wiskunde in je hoofd kunt doen. De tweede is een grotere dataset waarvoor ik code schrijf.

Voorbeeld 1: De gemiddelde leeftijd van leerlingen op een school bepalen

We hebben de opdracht om de gemiddelde leeftijd van leerlingen op een school te bepalen. We nemen 5 leerlingen willekeurig. Het idee is om die 5 leerlingen te gebruiken om de gemiddelde leeftijd van alle leerlingen op de school af te leiden. Dit is onzin (en statistisch gezien onjuist), maar wees geduldig.

ages = (12, 8, 10, 15, 9)

We nemen nu een steekproef uit deze lijst met vervanging.

sample_1 = ( 8, 10,  8, 15, 12)
sample_2 = (10, 10, 12,  8, 15)
sample_3 = (10, 12,  9,  9,  9)
....
do this a 1000 times
....
sample_1000 = ( 9, 12, 12, 15,  8)

Bereken voor elke resampling het gemiddelde.

mean_sample_1 = 10.6
mean_sample_2 = 11
mean_sample_3 = 9.8
...
mean_sample_1000 = 11.2

Neem een ​​gemiddelde van die middelen.

mean_over_samples=mean(mean_sample_1, mean_sample_2, .. , mean_sample_1000)

Dit gemiddelde wordt dan uw schatting van het populatiegemiddelde. U kunt hetzelfde doen met elke statistische eigenschap: betrouwbaarheidsintervallen, afwijkingen, etc.

Voorbeeld 2: Bepalen van het 95e percentiel voor ‘tijd om betaling te verwerken’

Klanten op een app voor voedselbezorging betalen via de app. Nadat een betaling is geslaagd, wordt er een bestelling geplaatst bij het restaurant. De tijd om betaling te verwerken berekend als de tijd tussen het moment dat een klant op de knop ‘Betaling doen’ drukt en het moment dat feedback wordt geleverd (betaling succesvol, betaling mislukt) is een kritische metriek die de betrouwbaarheid van het platform weerspiegelt. Miljoenen klanten doen elke dag betalingen via de app.

Wij hebben de taak om het 95% percentiel van de distributie te schatten, zodat we snel problemen kunnen detecteren.

We illustreren klassiek bootstrapping als volgt:

• We nemen aan dat er een populatie is die een miljoen observaties heeft. In de echte wereld observeren we deze data nooit.
• We nemen willekeurig 1/10e van deze populatie. Dus we nemen 10.000 observaties. In werkelijkheid zijn dit de enige gegevens die we observeren.
• Vervolgens passen we dezelfde procedure toe die we hierboven hebben besproken. We resamplen observaties uit onze waargenomen data met vervanging. We doen dit vele, vele malen.
• Elke keer dat we een nieuwe steekproef nemen, berekenen we het 95e percentiel van die verdeling.
• Ten slotte nemen we het gemiddelde van de 95e percentielwaarden en bepalen we de betrouwbaarheidsintervallen daaromheen.

We krijgen de grafiek hieronder. Magisch genoeg vinden we dat de betrouwbaarheidsintervallen die we zojuist hebben gegenereerd het echte 95e percentiel bevatten (van onze populatie).

We kunnen dezelfde gegevens zien op het niveau van de bootstrap-statistiek.

De code om het bovenstaande te genereren staat hieronder. Probeer het zelf eens!

https://medium.com/media/f9e4bdb29882053ec328f73d8eff2547/href

Dit werkt allemaal prima, wat nu?

Nu we hebben vastgesteld dat klassieke bootstrapping echt werkt, gaan we proberen vast te stellen wat er gebeurt vanuit een wiskundig perspectief. Meestal vertellen teksten je om dit deel over te slaan als je niet geïnteresseerd bent. Ik moedig je echter aan om te blijven hangen, want dit is waar het echt leuk is.

Neem een ​​pauze

Laten we nu eens een spelletje doen. Stel je voor dat je een zak hebt gevuld met 5 ballen: een rode, blauwe, gele, groene en paarse bal. Je moet 5 ballen uit de zak trekken, één voor één. Nadat je een bal hebt getrokken, stop je hem terug in de zak en trek je hem opnieuw. Dus elke keer dat je een bal kiest, heb je 5 verschillend gekleurde ballen om uit te kiezen. Na elke ronde noteer je de gekozen bal in een leeg vakje (zoals hieronder weergegeven).

En als ik u nu zou vragen: hoe groot is de kans dat elke bal wordt gekozen voor elk vakje dat we moeten vullen?

Voor slot 1,

• De rode bal kan met een waarschijnlijkheid van 1/5 worden gekozen
• De paarse bal kan met een waarschijnlijkheid van 1/5 worden gekozen
• De groene bal kan met een waarschijnlijkheid van 1/5 worden gekozen
• De blauwe bal kan met een waarschijnlijkheid van 1/5 worden gekozen
• De gele bal kan met een waarschijnlijkheid van 1/5 worden gekozen

Hetzelfde geval geldt voor sleuf 2, 3, 4 en 5

Laten we even focussen op de rode bal. Deze kan minimaal nul keer gekozen worden (hij wordt helemaal niet gekozen) en maximaal 5 keer. De kansverdeling van het voorkomen van de rode bal is als volgt:

• Rode bal 0 keer gekozen: Dit kan maar op 1 manier gebeuren.
• Rode bal 1 keer gekozen: Dit kan op 5 manieren gebeuren. Rode bal is gekozen voor slot 1, Rode bal is gekozen voor slot 2 … (je snapt het wel).
• Rode bal 2 keer gekozen: Dit kan op 10 manieren. Bevestig de rode bal op slot 1, er zijn 4 opties. Bevestig de rode bal op slot 2, er zijn 3 nieuwe opties, …
• Rode bal 3 keer gekozen: Dit kan op 10 manieren gebeuren. Dit is precies hetzelfde als de logica hierboven.
• Rode bal 4 keer gekozen: Dit kan op 5 manieren gebeuren. Vergelijkbaar met één keer gekozen worden.
• Rode bal wordt 5 keer gekozen. Dit kan op 1 manier gebeuren.

Dit is gewoon 5 kies k, waar k = {0, 1, 2, 3, 4, 5}

Laten we deze twee feiten samenvoegen, alleen voor de rode ballen

Wat we zojuist hebben beschreven is de binominale verdeling waarbij n=5 En p = 1/5

Of algemener,

Vervang nu de observaties door ballen.

Wanneer we bootstrappen, halen we in feite elke observatie uit een binominale verdeling.

Bij klassieke bootstrapping, wanneer we resamplen, Elke observatie volgt de binominale verdeling met n = n, k = {0, …, n} en p = 1/n. Dit wordt ook uitgedrukt als Binomiaal(n, 1/n).

Een zeer interessante eigenschap van de binominale verdeling is dat naarmate n steeds groter wordt en p steeds kleiner wordt, de binominale verdeling convergeert naar een Poisson-verdeling met Poisson(n/p). Ik zal ooit een intuïtieve uitleg schrijven over waarom dit gebeurt, maar als je geïnteresseerd bent, kun je nu dit zeer goed geschreven stuk lezen.

Dit werkt voor elke n en p zodat n/p constant is. In de gif hieronder laten we dit zien voor lambda (n/p) = 5.

In ons speciale geval zullen we gewoon convergeren naar Poisson(1) omdat p gewoon 1/n is.

Dan volgt daaruit dat een andere manier om opnieuw te bemonsteren zou zijn om elke observatie uit een Poisson(1)-verdeling te halen.

Poisson-bootstrapping betekent dat we een Poisson(1)-proces gebruiken om resamples te genereren voor het bootstrappen van een statistiek.

Geen probleem, waarom is dit nuttig?

Er zijn twee fasen van het bootstrappen van een statistiek van belang. De eerste fase is het maken van resamples, de tweede fase is het berekenen van de statistiek op elke resample. Klassiek en Poisson bootstrapping zijn identiek in de tweede fase, maar verschillend in de eerste fase.

Dit is op twee manieren nuttig:

• Met Poisson-bootstrapping wordt het aantal passes dat we nodig hebben om gegevens opnieuw te bewerken, verminderd.
• Poisson-bootstrapping werkt in gevallen waarin we geen vaste n hebben. Bijvoorbeeld wanneer we data streamen in.

Verminderen van het aantal passes tijdens het opnieuw bemonsteren

De Poisson bootstrap zorgt voor aanzienlijke rekenwinsten bij het maken van resamples. De beste manier om hiernaar te kijken is in code.

https://medium.com/media/172c87ccb04c3cfee8c16f3e6c823989/href

Vergelijk regel (8) hierboven met de equivalente regel in de klassieke bootstrap:

# classical, needs to know (data)
bootstrap_samples = np.random.choice(data, (n_iter, n), replace=True) 

# poisson, does not need to know (data)
weights = np.random.poisson(1, (n_iter, n))

Bij de klassieke bootstrap moet je weten gegevensterwijl dit bij de Poisson-bootstrap niet het geval is.

De implicaties hiervan zijn zeer significant voor gevallen waarin de data erg groot is (denk aan 100-en miljoenen observaties). Dit komt omdat het genereren van resamples wiskundig gezien gereduceerd wordt tot het genereren van tellingen voor elke observatie.

• Bij klassieke bootstrapping volgen de tellingen voor elke observatie een Binomiaal(n, 1/n)Samen volgen ze een Multinominaal(n, 1/n, 1/n, …, 1/n). Dit betekent dat wanneer u een telling voor een observatie genereert, dit invloed heeft op de telling voor de andere observaties. Bijvoorbeeld, in ons balvoorbeeld, zodra u de telling voor een rode bal hebt gegenereerd, heeft dit een directe impact op de tellingen voor de andere ballen. Bijvoorbeeld, als de telling voor de rode bal 2 is, dan weten we dat we nog maar 3 ballen hebben om uit te kiezen.
• Bij Poisson-bootstrapping zijn de tellingen voor elke observatie onafhankelijk van elkaar. Dus als je 1000 resamples nodig hebt, genereer je gewoon 1000 Poisson(1)-trekkingen voor de rode bal. Dan ben je klaar en kun je doorgaan naar de volgende observatie.

Opnieuw bemonsteren wanneer n onbekend is

Er zijn gevallen waarin n effectief onbekend is. Bijvoorbeeld in gevallen waarin u betalingsgegevens streamt of waar de gegevens zo groot zijn dat ze over meerdere opslaginstanties verspreid zijn.

Bij klassieke bootstrap moeten we elke keer dat we een toegenomen n waarnemen, het resamplingproces opnieuw uitvoeren (omdat we met vervanging samplen). Dit maakt deze methode behoorlijk rekenkundig duur en verspillend. Bij de Poisson bootstrap kunnen we gewoon onze Poisson(1) tekent voor elk exemplaar. Elke keer dat een nieuw exemplaar wordt toegevoegd, hoeven we alleen maar de Poisson(1) tekent voor dit nieuwe exemplaar.

Conclusie

Klassieke bootstrapping is een zeer effectieve techniek om de distributie van een statistiek te leren van een verzamelde steekproef. In de praktijk kan het onbetaalbaar duur zijn voor zeer grote datasets. Poisson bootstrapping is een versie van bootstrapping die efficiënte parallelle berekening van resamples mogelijk maakt. Dit komt door twee redenen:

1. Bij het opnieuw bemonsteren onder Poisson-bootstraps doen we elke waarneming slechts één keer.
2. Bij streaminggegevens kunnen we met Poisson-bootstraps nieuwe resamples stapsgewijs verwerken, in plaats van dat we in één keer de hele dataset opnieuw moeten bemonsteren.

Ik hoop dat je dit nuttig vond. Ik sta altijd open voor feedback en correcties. De afbeeldingen in dit bericht zijn van mij. Voel je vrij om ze te gebruiken!

De Poisson Bootstrap werd oorspronkelijk gepubliceerd in Towards Data Science op Medium, waar mensen de discussie voortzetten door dit verhaal te markeren en erop te reageren.