I metodi Monte Carlo sono una classe di tecniche per il campionamento casuale di una distribuzione di probabilità.

Ci sono molti domini problematici dove descrivere o stimare la distribuzione di probabilità è relativamente semplice, ma calcolare una quantità desiderata è intrattabile. Questo può essere dovuto a molte ragioni, come la natura stocastica del dominio o un numero esponenziale di variabili casuali.

Invece, una quantità desiderata può essere approssimata usando un campionamento casuale, indicato come metodi Monte Carlo. Questi metodi sono stati inizialmente utilizzati all’epoca della creazione dei primi computer e rimangono pervasivi in tutti i campi della scienza e dell’ingegneria, compresa l’intelligenza artificiale e l’apprendimento automatico.

In questo post, scoprirete i metodi Monte Carlo per il campionamento delle distribuzioni di probabilità.

Dopo aver letto questo post, saprete:

• Spesso, non possiamo calcolare una quantità desiderata in probabilità, ma possiamo definire le distribuzioni di probabilità delle variabili casuali direttamente o indirettamente.
• Il campionamento Montecarlo è una classe di metodi per il campionamento casuale da una distribuzione di probabilità.
• Il campionamento Montecarlo è alla base di molti metodi di apprendimento automatico come il ricampionamento, la regolazione degli iperparametri e l’apprendimento in ensemble.

Avvia il tuo progetto con il mio nuovo libro Probability for Machine Learning, che include tutorial passo dopo passo e i file del codice sorgente Python per tutti gli esempi.

Iniziamo.

Panoramica

Questo tutorial è diviso in tre parti; esse sono:

1. Necessità del campionamento
2. Cosa sono i metodi Monte Carlo?
3. Esempi di metodi Monte Carlo

Necessità del campionamento

Ci sono molti problemi nella probabilità, e più in generale nel machine learning, dove non possiamo calcolare direttamente una soluzione analitica.

In effetti, si può sostenere che l’inferenza esatta può essere intrattabile per la maggior parte dei modelli probabilistici pratici.

Per la maggior parte dei modelli probabilistici di interesse pratico, l’inferenza esatta è intrattabile, e quindi dobbiamo ricorrere a qualche forma di approssimazione.

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

Il calcolo desiderato è tipicamente una somma di una distribuzione discreta o un integrale di una distribuzione continua ed è intrattabile da calcolare. Il calcolo può essere intrattabile per molte ragioni, come il gran numero di variabili casuali, la natura stocastica del dominio, il rumore nelle osservazioni, la mancanza di osservazioni, e altro.

In problemi di questo tipo, è spesso possibile definire o stimare le distribuzioni di probabilità per le variabili casuali coinvolte, direttamente o indirettamente attraverso una simulazione computazionale.

Invece di calcolare direttamente la quantità, si può usare il campionamento.

Il campionamento fornisce un modo flessibile per approssimare molte somme e integrali a costi ridotti.

– Pagina 590, Deep Learning, 2016.

I campioni possono essere estratti casualmente dalla distribuzione di probabilità e utilizzati per approssimare la quantità desiderata.

Questa classe generale di tecniche per il campionamento casuale da una distribuzione di probabilità è indicata come metodi Monte Carlo.

Vuoi imparare la probabilità per l’apprendimento automatico

Prendi subito il mio corso crash gratuito di 7 giorni via email (con codice di esempio).

Clicca per iscriverti e ottieni anche una versione gratuita del corso in PDF Ebook.

Scarica il tuo mini-corso gratuito

Cosa sono i metodi Monte Carlo?

I metodi Monte Carlo, o MC in breve, sono una classe di tecniche per il campionamento casuale di una distribuzione di probabilità.

Ci sono tre ragioni principali per usare i metodi Monte Carlo per campionare a caso una distribuzione di probabilità; sono:

• Stimare la densità, raccogliere campioni per approssimare la distribuzione di una funzione obiettivo.
• Approssimare una quantità, come la media o la varianza di una distribuzione.
• Ottimizzare una funzione, individuare un campione che massimizzi o minimizzi la funzione obiettivo.

I metodi Monte Carlo prendono il nome dal casinò di Monaco e sono stati sviluppati per risolvere problemi di fisica delle particelle all’epoca dello sviluppo dei primi computer e del progetto Manhattan per lo sviluppo della prima bomba atomica.

Questa è chiamata approssimazione di Monte Carlo, dal nome di una città europea nota per i suoi lussuosi casinò di gioco. Le tecniche Monte Carlo sono state sviluppate per la prima volta nell’area della fisica statistica – in particolare, durante lo sviluppo della bomba atomica – ma sono ora ampiamente utilizzate anche in statistica e nell’apprendimento automatico.

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

Prelevare un campione può essere semplice come calcolare la probabilità per un evento selezionato casualmente, o può essere complesso come eseguire una simulazione computazionale, con quest’ultima spesso indicata come una simulazione Monte Carlo.

Campioni multipli sono raccolti e utilizzati per approssimare la quantità desiderata.

In base alla legge dei grandi numeri della statistica, più prove casuali vengono eseguite, più accurata diventa la quantità approssimata.

… la legge dei grandi numeri afferma che se i campioni x(i) sono i.i.d., allora la media converge quasi sicuramente al valore atteso

– Pagina 591, Deep Learning, 2016.

Come tale, il numero di campioni fornisce il controllo sulla precisione della quantità che viene approssimata, spesso limitata dalla complessità computazionale del disegno di un campione.

Generando abbastanza campioni, possiamo raggiungere qualsiasi livello di precisione desiderato. Il problema principale è: come possiamo generare in modo efficiente campioni da una distribuzione di probabilità, in particolare in dimensioni elevate?

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

Inoltre, dato il teorema del limite centrale, la distribuzione dei campioni formerà una distribuzione normale, la cui media può essere presa come quantità approssimata e la varianza utilizzata per fornire un intervallo di confidenza per la quantità.

Il teorema del limite centrale ci dice che la distribuzione della media , converge verso una distribuzione normale Questo ci permette di stimare intervalli di confidenza intorno alla stima , utilizzando la distribuzione cumulativa della densità normale.

– Pagina 592, Deep Learning, 2016.

I metodi Monte Carlo sono definiti in termini di modalità di estrazione dei campioni o di vincoli imposti al processo di campionamento.

Alcuni esempi di metodi di campionamento Monte Carlo includono: campionamento diretto, campionamento di importanza e campionamento di rifiuto.

• Campionamento diretto. Campionamento della distribuzione direttamente senza informazioni preliminari.
• Campionamento d’importanza. Campionamento da un’approssimazione più semplice della distribuzione obiettivo.
• Campionamento a rifiuto. Campionamento da una distribuzione più ampia e considerare solo i campioni all’interno di una regione della distribuzione campionata.

È un argomento enorme con molti libri dedicati. Quindi, rendiamo concreta l’idea del campionamento Monte Carlo con alcuni esempi familiari.

Esempi di campionamento Monte Carlo

Utilizziamo i metodi Monte Carlo tutto il tempo senza pensarci.

Per esempio, quando definiamo una distribuzione Bernoulli per il lancio di una moneta e simuliamo il lancio di una moneta campionando da questa distribuzione, stiamo eseguendo una simulazione Monte Carlo. Inoltre, quando campioniamo da una distribuzione uniforme per i numeri interi {1,2,3,4,5,6} per simulare il lancio di un dado, stiamo eseguendo una simulazione Monte Carlo.

Stiamo anche usando il metodo Monte Carlo quando raccogliamo un campione casuale di dati dal dominio e stimiamo la distribuzione di probabilità dei dati usando un istogramma o un metodo di stima della densità.

Ci sono molti esempi dell’uso dei metodi Monte Carlo in una gamma di discipline scientifiche.

Per esempio, i metodi Monte Carlo possono essere usati per:

• Calcolare la probabilità di una mossa di un avversario in un gioco complesso.
• Calcolare la probabilità di un evento meteorologico nel futuro.
• Calcolare la probabilità di un incidente automobilistico in condizioni specifiche.

I metodi sono usati per affrontare difficili inferenze in problemi di probabilità applicata, come il campionamento da modelli grafici probabilistici.

Relativa è l’idea dei metodi Monte Carlo sequenziali utilizzati nei modelli bayesiani che sono spesso indicati come filtri a particelle.

Il filtraggio a particelle (PF) è un algoritmo Monte Carlo, o basato sulla simulazione, per l’inferenza bayesiana ricorsiva.

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

I metodi Monte Carlo sono anche pervasivi nell’intelligenza artificiale e nell’apprendimento automatico.

Molte importanti tecnologie utilizzate per realizzare obiettivi di apprendimento automatico si basano sul disegno di campioni da una qualche distribuzione di probabilità e sull’utilizzo di questi campioni per formare una stima Monte Carlo di qualche quantità desiderata.

– Pagina 590, Deep Learning, 2016.

Forniscono la base per stimare la probabilità di risultati in problemi di intelligenza artificiale tramite simulazione, come la robotica. Più semplicemente, i metodi Monte Carlo sono utilizzati per risolvere problemi di integrazione intrattabili, come lo sparo di raggi casuali nel path tracing per la computer grafica durante il rendering di una scena generata dal computer.

Nel machine learning, i metodi Monte Carlo forniscono la base per tecniche di ricampionamento come il metodo bootstrap per stimare una quantità, come l’accuratezza di un modello su un set di dati limitato.

Il bootstrap è una semplice tecnica Monte Carlo per approssimare la distribuzione di campionamento. Questo è particolarmente utile nei casi in cui lo stimatore è una funzione complessa dei parametri reali.

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

Il campionamento casuale degli iperparametri del modello quando si sintonizza un modello è un metodo Monte Carlo, così come i modelli ensemble utilizzati per superare le sfide come la dimensione limitata e il rumore in un piccolo campione di dati e la varianza stocastica in un algoritmo di apprendimento.

• Algoritmi di campionamento.
• Tuning casuale degli iperparametri.
• Algoritmi di apprendimento ensemble.

I metodi Monte Carlo forniscono anche la base per algoritmi di ottimizzazione randomizzati o stocastici, come la popolare tecnica di ottimizzazione Simulated Annealing.

Gli algoritmi di Monte Carlo, di cui l’annealing simulato è un esempio, sono usati in molte branche della scienza per stimare quantità difficili da calcolare esattamente.

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

• Algoritmi di ottimizzazione stocastica.

Esempio di lavoro sul campionamento Monte Carlo

Possiamo concretizzare il campionamento Monte Carlo con un esempio di lavoro.

In questo caso, avremo una funzione che definisce la distribuzione di probabilità di una variabile casuale. Useremo una distribuzione gaussiana con una media di 50 e una deviazione standard di 5 e trarremo dei campioni casuali da questa distribuzione.

Facciamo finta di non conoscere la forma della distribuzione di probabilità di questa variabile casuale e vogliamo campionare la funzione per avere un’idea della densità di probabilità. Possiamo estrarre un campione di una data dimensione e tracciare un istogramma per stimare la densità.

La funzione NumPy normal() può essere usata per estrarre a caso dei campioni da una distribuzione gaussiana con la media (mu), la deviazione standard (sigma) e la dimensione del campione specificate.

Per rendere l’esempio più interessante, ripeteremo questo esperimento quattro volte con campioni di dimensioni diverse. Ci aspetteremmo che all’aumentare della dimensione del campione, la densità di probabilità approssimi meglio la vera densità della funzione obiettivo, data la legge dei grandi numeri.

L’esempio completo è elencato qui sotto.

L’esecuzione dell’esempio crea quattro campioni di dimensioni diverse e traccia un istogramma per ciascuno.

Si può vedere che le piccole dimensioni del campione di 10 e 50 non catturano efficacemente la densità della funzione obiettivo. Possiamo vedere che 100 campioni sono migliori, ma non è fino a 1.000 campioni che vediamo chiaramente la familiare forma a campana della distribuzione di probabilità gaussiana.

Questo evidenzia la necessità di disegnare molti campioni, anche per una semplice variabile casuale, e il beneficio di una maggiore precisione dell’approssimazione con il numero di campioni disegnati.

Lettura complementare

Questa sezione fornisce altre risorse sull’argomento se volete approfondire.

Libri

• Capitolo 29 Metodi Monte Carlo, Teoria dell’informazione, inferenza e algoritmi di apprendimento, 2003.
• Capitolo 27 Campionamento, Ragionamento bayesiano e apprendimento automatico, 2011.
• Sezione 14.5 Inferenza approssimativa nelle reti bayesiane, Artificial Intelligence: A Modern Approach, 3rd edition, 2009.
• Capitolo 23 Monte Carlo inference, Machine Learning: A Probabilistic Perspective, 2012.
• Capitolo 11 Sampling Methods, Pattern Recognition and Machine Learning, 2006.
• Capitolo 17 Monte Carlo Methods, Deep Learning, 2016.

Articoli

• Campionamento (statistica), Wikipedia.
• Metodo Monte Carlo, Wikipedia.
• Integrazione Monte Carlo, Wikipedia.
• Campionamento di importanza, Wikipedia.
• Campionamento di rifiuto, Wikipedia.

Sommario

In questo post, hai scoperto i metodi Monte Carlo per il campionamento di distribuzioni di probabilità.

In particolare, hai imparato:

• Spesso, non possiamo calcolare una quantità desiderata in probabilità, ma possiamo definire le distribuzioni di probabilità per le variabili casuali direttamente o indirettamente.
• Il campionamento Monte Carlo una classe di metodi per il campionamento casuale da una distribuzione di probabilità.
• Il campionamento Monte Carlo è alla base di molti metodi di apprendimento automatico come il ricampionamento, la regolazione degli iperparametri e l’apprendimento in ensemble.

Hai qualche domanda?
Fai le tue domande nei commenti qui sotto e farò del mio meglio per rispondere.