Monte Carlo methoden zijn een klasse van technieken voor het aselect bemonsteren van een kansverdeling.

Er zijn veel probleemdomeinen waar het beschrijven of schatten van de kansverdeling relatief eenvoudig is, maar het berekenen van een gewenste grootheid onuitvoerbaar is. Dit kan verschillende oorzaken hebben, zoals de stochastische aard van het domein of een exponentieel aantal willekeurige variabelen.

In plaats daarvan kan een gewenste grootheid worden benaderd door gebruik te maken van aselecte steekproeven, Monte Carlo-methoden genoemd. Deze methoden werden voor het eerst gebruikt rond de tijd dat de eerste computers werden gemaakt en zijn nog steeds alomtegenwoordig in alle gebieden van wetenschap en techniek, met inbegrip van kunstmatige intelligentie en machine learning.

In dit bericht ontdekt u Monte Carlo-methoden voor het bemonsteren van kansverdelingen.

Na het lezen van dit bericht weet u:

• Vaak kunnen we een gewenste grootheid niet berekenen in waarschijnlijkheid, maar kunnen we de kansverdelingen voor de willekeurige variabelen direct of indirect definiëren.
• Monte Carlo sampling een klasse van methoden voor het aselect bemonsteren uit een kansverdeling.
• Monte Carlo sampling vormt de basis voor veel machine learning methoden, zoals resampling, hyperparameter tuning, en ensemble learning.

Start je project met mijn nieuwe boek Probability for Machine Learning, inclusief stap-voor-stap tutorials en de Python broncodebestanden voor alle voorbeelden.

Laten we aan de slag gaan.

Overzicht

Deze handleiding is onderverdeeld in drie delen; deze zijn:

1. Noodzaak van steekproeftrekking
2. Wat zijn Monte Carlo-methoden?
3. Voorbeelden van Monte Carlo Methoden

Noodzaak van Sampling

Er zijn veel problemen in kansrekening, en breder in machine learning, waar we niet direct een analytische oplossing kunnen berekenen.

Er valt zelfs iets voor te zeggen dat exacte inferentie voor de meeste probabilistische modellen in de praktijk onuitvoerbaar is.

Voor de meeste probabilistische modellen van praktisch belang is exacte inferentie onuitvoerbaar, en dus moeten we onze toevlucht nemen tot een of andere vorm van benadering.

– Bladzijde 523, Pattern Recognition and Machine Learning, 2006.

De gewenste berekening is meestal een som van een discrete verdeling of een integraal van een continue verdeling en is onuitvoerbaar om te berekenen. De berekening kan om vele redenen onuitvoerbaar zijn, zoals het grote aantal willekeurige variabelen, de stochastische aard van het domein, ruis in de waarnemingen, het ontbreken van waarnemingen, enzovoort.

In dit soort problemen is het vaak mogelijk om de kansverdelingen voor de betrokken willekeurige variabelen te bepalen of te schatten, hetzij direct, hetzij indirect via een computersimulatie.

In plaats van de grootheid direct te berekenen, kan gebruik worden gemaakt van steekproeven.

Bemonstering biedt een flexibele manier om veel sommen en integralen tegen lagere kosten te benaderen.

– Page 590, Deep Learning, 2016.

Stalen kunnen willekeurig uit de kansverdeling worden getrokken en worden gebruikt om de gewenste grootheid te benaderen.

Deze algemene klasse van technieken voor het trekken van willekeurige steekproeven uit een kansverdeling wordt Monte Carlo-methoden genoemd.

Wil je Kansberekening leren voor Machine Learning

Doe nu mee aan mijn gratis 7-daagse e-mailcrashcursus (met voorbeeldcode).

Klik om je aan te melden en ontvang ook een gratis PDF-versie van de cursus.

Download je gratis minicursus

Wat zijn Monte Carlo-methoden?

Monte Carlo-methoden, kortweg MC, zijn een klasse technieken voor het willekeurig bemonsteren van een kansverdeling.

Er zijn drie hoofdredenen om Monte Carlo methoden te gebruiken voor het aselect bemonsteren van een kansverdeling; deze zijn:

• Dichtheid schatten, steekproeven verzamelen om de verdeling van een doelfunctie te benaderen.
• Een grootheid bij benadering bepalen, zoals het gemiddelde of de variantie van een verdeling.
• Een functie optimaliseren, een monster zoeken dat de doelfunctie maximaliseert of minimaliseert.

Monte Carlo-methoden zijn genoemd naar het casino in Monaco en werden voor het eerst ontwikkeld om problemen in de deeltjesfysica op te lossen rond de tijd van de ontwikkeling van de eerste computers en het Manhattan-project voor de ontwikkeling van de eerste atoombom.

Dit wordt een Monte Carlo-benadering genoemd, genoemd naar een stad in Europa die bekend staat om zijn weelderige gokcasino’s. Monte Carlo-technieken werden voor het eerst ontwikkeld op het gebied van de statistische fysica – met name tijdens de ontwikkeling van de atoombom – maar worden nu ook op grote schaal gebruikt in de statistiek en bij machinaal leren.

– Pagina 52, Machine Learning: A Probabilistic Perspective, 2012.

Het trekken van een steekproef kan zo eenvoudig zijn als het berekenen van de waarschijnlijkheid voor een willekeurig gekozen gebeurtenis, of kan zo complex zijn als het uitvoeren van een computersimulatie, waarbij de laatste vaak een Monte Carlo-simulatie wordt genoemd.

Meerdere steekproeven worden verzameld en gebruikt om de gewenste grootheid te benaderen.

Gezien de wet van de grote getallen uit de statistiek zal de benaderde grootheid nauwkeuriger worden naarmate er meer willekeurige proeven worden genomen.

… de wet van de grote getallen stelt dat als de steekproeven x(i) i.i.d. zijn, dan convergeert het gemiddelde vrijwel zeker naar de verwachte waarde

– Pagina 591, Deep Learning, 2016.

Zo biedt het aantal steekproeven controle over de precisie van de grootheid die wordt benaderd, vaak beperkt door de computationele complexiteit van het trekken van een steekproef.

Door voldoende steekproeven te genereren, kunnen we elk gewenst niveau van nauwkeurigheid bereiken dat we willen. De belangrijkste vraag is: hoe genereren we efficiënt steekproeven uit een kansverdeling, vooral in hoge dimensies?

– Bladzijde 815, Machine Learning: A Probabilistic Perspective, 2012.

Daarnaast zal, gegeven het centrale limiettheorema, de verdeling van de steekproeven een normale verdeling vormen, waarvan het gemiddelde kan worden genomen als de benaderde grootheid en de variantie kan worden gebruikt om een betrouwbaarheidsinterval voor de grootheid te geven.

De centrale limiet stelling vertelt ons dat de verdeling van het gemiddelde , convergeert naar een normale verdeling Hierdoor kunnen we betrouwbaarheidsintervallen schatten rond de schatting , met behulp van de cumulatieve verdeling van de normale dichtheid.

– Page 592, Deep Learning, 2016.

Monte Carlo-methoden worden gedefinieerd in termen van de manier waarop steekproeven worden getrokken of de beperkingen die aan het steekproefproces worden opgelegd.

Enkele voorbeelden van Monte Carlo-bemonsteringsmethoden zijn: directe steekproeftrekking, belangbemonstering en afwijzingssteekproeftrekking.

• Directe steekproeftrekking. Het direct bemonsteren van de verdeling zonder voorafgaande informatie.
• Importance Sampling. Bemonstering uit een eenvoudiger benadering van de doelverdeling.
• Afwijzingsbemonstering. Het trekken van steekproeven uit een bredere verdeling en alleen rekening houden met steekproeven binnen een regio van de bemonsterde verdeling.

Het is een enorm onderwerp met vele boeken eraan gewijd. Laten we het idee van Monte Carlo steekproeftrekking nu eens concreet maken met een paar bekende voorbeelden.

Voorbeelden van Monte Carlo Steekproeftrekking

We gebruiken de Monte Carlo methode voortdurend zonder erbij na te denken.

Bijv. als we een Bernoulli verdeling definiëren voor het opgooien van een munt en het opgooien van een munt simuleren door uit deze verdeling te steekproeven, voeren we een Monte Carlo simulatie uit. En als we een steekproef nemen uit een uniforme verdeling voor de gehele getallen {1,2,3,4,5,6} om het werpen van een dobbelsteen te simuleren, dan voeren we een Monte Carlo simulatie uit.

We gebruiken de Monte Carlo methode ook als we een willekeurige steekproef van gegevens uit het domein verzamelen en de kansverdeling van de gegevens schatten met behulp van een histogram of een dichtheidsschattingsmethode.

Er zijn veel voorbeelden van het gebruik van Monte Carlo-methoden in allerlei wetenschappelijke disciplines.

Methoden van Monte Carlo kunnen bijvoorbeeld worden gebruikt voor:

• Berekenen van de waarschijnlijkheid van een zet van een tegenstander in een complex spel.
• Berekenen van de waarschijnlijkheid van een weersgebeurtenis in de toekomst.
• Berekenen van de waarschijnlijkheid van een auto-ongeluk onder specifieke omstandigheden.

De methoden worden gebruikt om moeilijke gevolgtrekkingen te maken bij problemen in toegepaste waarschijnlijkheid, zoals steekproeven uit probabilistische grafische modellen.

Gerelateerd is het idee van sequentiële Monte Carlo-methoden die worden gebruikt in Bayesiaanse modellen die vaak worden aangeduid als deeltjesfilters.

Particle filtering (PF) is een Monte Carlo-, of simulatiegebaseerd, algoritme voor recursieve Bayesiaanse inferentie.

– Pagina 823, Machine Learning: A Probabilistic Perspective, 2012.

Monte Carlo-methoden zijn ook alomtegenwoordig in kunstmatige intelligentie en machine learning.

Veel belangrijke technologieën die worden gebruikt om machine learning-doelen te bereiken, zijn gebaseerd op het trekken van steekproeven uit een waarschijnlijkheidsverdeling en het gebruik van deze steekproeven om een Monte Carlo-schatting te maken van een gewenste grootheid.

– Page 590, Deep Learning, 2016.

Ze vormen de basis voor het schatten van de waarschijnlijkheid van uitkomsten in kunstmatige-intelligentieproblemen via simulatie, zoals robotica. Eenvoudiger gezegd, Monte Carlo-methoden worden gebruikt om hardnekkige integratieproblemen op te lossen, zoals het afvuren van willekeurige stralen in path tracing voor computergraphics bij het renderen van een door de computer gegenereerde scène.

In machine learning vormen Monte Carlo-methoden de basis voor resampling-technieken zoals de bootstrap-methode voor het schatten van een grootheid, zoals de nauwkeurigheid van een model op een beperkte dataset.

De bootstrap is een eenvoudige Monte Carlo-techniek om de steekproefverdeling te benaderen. Dit is vooral nuttig in gevallen waarin de schatter een complexe functie is van de ware parameters.

– Bladzijde 192, Machine Learning: A Probabilistic Perspective, 2012.

Random sampling van modelhyperparameters bij het tunen van een model is een Monte Carlo-methode, net als ensemble-modellen die worden gebruikt om uitdagingen zoals de beperkte omvang en ruis in een kleine gegevenssteekproef en de stochastische variantie in een leeralgoritme te overwinnen.

• Resampling-algoritmen.
• Random hyperparameter tuning.
• Ensemble-leeralgoritmen.

Monte Carlo-methoden vormen ook de basis voor gerandomiseerde of stochastische optimalisatiealgoritmen, zoals de populaire Simulated Annealing-optimalisatietechniek.

Monte Carlo-algoritmen, waarvan gesimuleerde annealing een voorbeeld is, worden in veel takken van wetenschap gebruikt om grootheden te schatten die moeilijk exact te berekenen zijn.

– Blz. 530, Artificial Intelligence: A Modern Approach, 3rd edition, 2009.

• Stochastische optimalisatiealgoritmen.

Werkvoorbeeld van Monte Carlo Sampling

We kunnen Monte Carlo sampling concreet maken met een uitgewerkt voorbeeld.

In dit geval hebben we een functie die de kansverdeling van een willekeurige variabele definieert. We gebruiken een Gaussische verdeling met een gemiddelde van 50 en een standaardafwijking van 5 en trekken willekeurige steekproeven uit deze verdeling.

Laten we doen alsof we de vorm van de kansverdeling voor deze willekeurige variabele niet kennen en we de functie willen bemonsteren om een idee te krijgen van de kansdichtheid. We kunnen een steekproef trekken van een bepaalde grootte en een histogram plotten om de dichtheid te schatten.

De normal() NumPy-functie kan worden gebruikt om willekeurig steekproeven te trekken uit een Gaussische verdeling met het opgegeven gemiddelde (mu), standaardafwijking (sigma), en steekproefgrootte.

Om het voorbeeld interessanter te maken, zullen we dit experiment vier keer herhalen met steekproeven van verschillende grootte. We verwachten dat naarmate de grootte van de steekproef toeneemt, de kansdichtheid de werkelijke dichtheid van de doelfunctie beter benadert, gegeven de wet van de grote getallen.

Het volledige voorbeeld staat hieronder.

Het uitvoeren van het voorbeeld levert vier steekproeven van verschillende grootte op en toont voor elk een histogram.

We kunnen zien dat de kleine steekproeven van 10 en 50 de dichtheid van de doelfunctie niet goed weergeven. We zien dat 100 steekproeven beter is, maar pas bij 1000 steekproeven zien we duidelijk de bekende klokvorm van de Gaussische kansverdeling.

Dit benadrukt de noodzaak om veel steekproeven te trekken, zelfs voor een eenvoudige willekeurige variabele, en het voordeel van een grotere nauwkeurigheid van de benadering naarmate het aantal getrokken steekproeven toeneemt.

Further Reading

Dit gedeelte geeft meer bronnen over het onderwerp als je dieper op de materie in wilt gaan.

Boeken

• Hoofdstuk 29 Monte Carlo Methods, Information Theory, Inference and Learning Algorithms, 2003.
• Hoofdstuk 27 Sampling, Bayesian Reasoning and Machine Learning, 2011.
• Sectie 14.5 Approximate Inference In Bayesian Networks, Artificial Intelligence: A Modern Approach, 3e editie, 2009.
• Hoofdstuk 23 Monte Carlo-inferentie, Machine Learning: A Probabilistic Perspective, 2012.
• Hoofdstuk 11 Sampling Methods, Pattern Recognition and Machine Learning, 2006.
• Hoofdstuk 17 Monte Carlo Methods, Deep Learning, 2016.

Artikelen

• Sampling (statistiek), Wikipedia.
• Monte Carlo methode, Wikipedia.
• Monte Carlo integratie, Wikipedia.
• Importance sampling, Wikipedia.
• Rejection sampling, Wikipedia.

Samenvatting

In dit bericht hebt u Monte Carlo-methoden voor het bemonsteren van kansverdelingen ontdekt.

In het bijzonder hebt u geleerd:

• Vaak kunnen we een gewenste grootheid niet in waarschijnlijkheid berekenen, maar we kunnen de kansverdelingen voor de willekeurige variabelen direct of indirect definiëren.
• Monte Carlo-steekproeftrekking een klasse methoden voor het willekeurig bemonsteren uit een kansverdeling.
• Monte Carlo sampling vormt de basis voor veel machine learning methoden, zoals resampling, hyperparameter tuning, en ensemble learning.

Heeft u nog vragen?
Stel uw vragen in de reacties hieronder en ik zal mijn best doen ze te beantwoorden.