Impara Cosa Sono i Metodi Monte Carlo?

Definizione

I metodi Monte Carlo (MC) sono una classe di algoritmi computazionali che si basano sul campionamento casuale per stimare risultati numerici.

I metodi Monte Carlo vengono utilizzati quando le soluzioni deterministiche sono difficili o impossibili da ottenere. Sostituiscono i calcoli esatti con approssimazioni che migliorano all'aumentare del numero di campioni casuali.

Come funzionano?

I metodi Monte Carlo possono variare da un compito all'altro, ma tutti tendono a seguire un unico schema:

Definizione di un dominio di possibili input;
Generazione di input casuali da una distribuzione di probabilità;
Valutazione di una funzione su questi input;
Aggregazione dei risultati per produrre una stima.

Esempi

Sebbene lo schema descritto sopra possa sembrare complesso, questi esempi dovrebbero aiutare a chiarire l'idea alla base.

Calcolo degli integrali

Il calcolo degli integrali è un compito non banale che solitamente richiede l'applicazione di molte tecniche per ottenere il risultato corretto.

Proviamo ad applicare il metodo Monte Carlo per risolvere questo integrale:

\int_0^1 \int_0^1 \frac{1}{1 + (x + y)^2} \, dx \, dy

Dominio di ingresso: questo integrale doppio ha due variabili, $x \in [0, 1]$ e $y \in [0, 1]$ ;
Generazione: entrambe queste variabili sono indipendenti tra loro e distribuite uniformemente;
Valutazione: per ottenere un valore puntuale, si può utilizzare la funzione sotto l'integrale;
Aggregazione: il valore di questo integrale può essere definito come il volume sotto la curva. Il volume può essere calcolato come prodotto dell'area di base e dell'altezza media. L'area di base è 1 (quadrato unitario) e l'altezza media è la media dei risultati ottenuti nel passo precedente.


              12345678910111213141516
            
import numpy as np

result = 0
# Many samples are required for estimates to be precise
for i in range(100000):
  # Generation of random variables
  x, y = np.random.uniform(), np.random.uniform()
  # Computation of point value
  value = 1 / (1 + (x + y) ** 2)
  # Mean aggregation
  result += (value - result) / (i + 1)

# Closed-form solution of this integral
true_result = 2*np.arctan(2) - np.pi/2 - (1/2)*np.log(5) + np.log(2)
print(f"Approximated result: {result}")
print(f"True result: {true_result}")

Approssimazione di $\Large\pi$

L'approssimazione di $\pi$ è uno degli utilizzi più iconici del metodo Monte Carlo. Questo esempio mostra come il campionamento casuale possa risolvere un problema geometrico senza l'uso di calcoli complessi.

Si consideri un quadrato unitario con un quarto di cerchio inscritto al suo interno:

Il quadrato copre $[0, 1] \times [0, 1]$ ;
Il quarto di cerchio ha raggio 1 ed è centrato nell'origine.

L'area del quarto di cerchio è $\displaystyle\frac{\pi r^2}{4}$ ovvero $\displaystyle\frac{\pi}{4}$ , mentre l'area del quadrato è 1. Ora si campionano punti casuali all'interno del quadrato. Con una dimensione del campione sufficientemente grande:

\frac{\text{Punti all'interno del quarto di cerchio}}{\text{Punti totali}} \approx \frac\pi4

Quindi il valore di $\pi$ può essere calcolato come

\pi \approx 4 \cdot \frac{\text{Punti all'interno}}{\text{Punti totali}}


              1234567891011121314151617181920212223242526272829
            
import numpy as np
import matplotlib.pyplot as plt

# Lists for coordinates
inside = []
outside = []

# Many samples are required for estimates to be precise
for _ in range(100000):
  # Generation of random variables
  x, y = np.random.uniform(), np.random.uniform()
  # Splitting points inside and outside of the circle
  if x**2 + y**2 <= 1:
    inside.append((x, y))
  else:
    outside.append((x, y))

# Plotting points
plt.figure(figsize=(6,6))
plt.scatter(*zip(*inside), color="blue", s=1, label="Inside")
plt.scatter(*zip(*outside), color="red", s=1, label="Outside")
plt.legend()
plt.xlabel("x")
plt.ylabel("y")
plt.show()

estimate = 4 * len(inside) / (len(inside) + len(outside))
print(f"Estimated value of pi: {estimate}")
print(f"True value of pi: {np.pi}")

Banditi a più braccia

Nel contesto dei banditi a più braccia, un obiettivo fondamentale è stimare il valore d'azione per ciascuna leva, ovvero la ricompensa attesa scegliendo una determinata azione. Una strategia comune consiste nello stimare questi valori facendo la media delle ricompense osservate ottenute tirando ciascuna leva nel tempo. Questa tecnica è, infatti, un metodo Monte Carlo.

Metodi Monte Carlo per MDP

A differenza dei metodi di programmazione dinamica, che si basano su un modello completo e accurato della dinamica dell'ambiente, i metodi Monte Carlo apprendono esclusivamente dall'esperienza — ovvero da sequenze reali o simulate di stati, azioni e ricompense.

Questo rende gli approcci Monte Carlo particolarmente potenti: non richiedono alcuna conoscenza preliminare su come funziona l'ambiente. Invece, estraggono le stime di valore direttamente da ciò che accade durante l'interazione. In molti scenari reali, dove modellare l'ambiente è impraticabile o impossibile, questa capacità di apprendere dall'esperienza grezza rappresenta un vantaggio significativo.

Quando l'interazione diretta con l'ambiente è costosa, rischiosa o lenta, i metodi Monte Carlo possono anche apprendere da esperienze simulate, a condizione che esista una simulazione affidabile. Questo consente esplorazione e apprendimento in un contesto controllato e ripetibile — anche se presuppone l'accesso a un modello in grado di generare transizioni plausibili.

Tutto è chiaro?

Grazie per i tuoi commenti!

Sezione 4. Capitolo 1

Chieda ad AI

Chieda pure quello che desidera o provi una delle domande suggerite per iniziare la nostra conversazione

Suggested prompts:

Can you explain more about how Monte Carlo methods are used in Markov Decision Processes (MDPs)?

What are some real-world applications of Monte Carlo methods?

How do Monte Carlo methods compare to other approximation techniques?

Awesome!

Completion rate improved to 2.7

Scorri per mostrare il menu

Definizione

I metodi Monte Carlo (MC) sono una classe di algoritmi computazionali che si basano sul campionamento casuale per stimare risultati numerici.

Come funzionano?

I metodi Monte Carlo possono variare da un compito all'altro, ma tutti tendono a seguire un unico schema:

Definizione di un dominio di possibili input;
Generazione di input casuali da una distribuzione di probabilità;
Valutazione di una funzione su questi input;
Aggregazione dei risultati per produrre una stima.

Esempi

Sebbene lo schema descritto sopra possa sembrare complesso, questi esempi dovrebbero aiutare a chiarire l'idea alla base.

Calcolo degli integrali

Il calcolo degli integrali è un compito non banale che solitamente richiede l'applicazione di molte tecniche per ottenere il risultato corretto.

Proviamo ad applicare il metodo Monte Carlo per risolvere questo integrale:

\int_0^1 \int_0^1 \frac{1}{1 + (x + y)^2} \, dx \, dy

Dominio di ingresso: questo integrale doppio ha due variabili, $x \in [0, 1]$ e $y \in [0, 1]$ ;
Generazione: entrambe queste variabili sono indipendenti tra loro e distribuite uniformemente;
Valutazione: per ottenere un valore puntuale, si può utilizzare la funzione sotto l'integrale;
Aggregazione: il valore di questo integrale può essere definito come il volume sotto la curva. Il volume può essere calcolato come prodotto dell'area di base e dell'altezza media. L'area di base è 1 (quadrato unitario) e l'altezza media è la media dei risultati ottenuti nel passo precedente.


              12345678910111213141516
            
import numpy as np

result = 0
# Many samples are required for estimates to be precise
for i in range(100000):
  # Generation of random variables
  x, y = np.random.uniform(), np.random.uniform()
  # Computation of point value
  value = 1 / (1 + (x + y) ** 2)
  # Mean aggregation
  result += (value - result) / (i + 1)

# Closed-form solution of this integral
true_result = 2*np.arctan(2) - np.pi/2 - (1/2)*np.log(5) + np.log(2)
print(f"Approximated result: {result}")
print(f"True result: {true_result}")

Approssimazione di $\Large\pi$

Si consideri un quadrato unitario con un quarto di cerchio inscritto al suo interno:

Il quadrato copre $[0, 1] \times [0, 1]$ ;
Il quarto di cerchio ha raggio 1 ed è centrato nell'origine.

\frac{\text{Punti all'interno del quarto di cerchio}}{\text{Punti totali}} \approx \frac\pi4

Quindi il valore di $\pi$ può essere calcolato come

\pi \approx 4 \cdot \frac{\text{Punti all'interno}}{\text{Punti totali}}


              1234567891011121314151617181920212223242526272829
            
import numpy as np
import matplotlib.pyplot as plt

# Lists for coordinates
inside = []
outside = []

# Many samples are required for estimates to be precise
for _ in range(100000):
  # Generation of random variables
  x, y = np.random.uniform(), np.random.uniform()
  # Splitting points inside and outside of the circle
  if x**2 + y**2 <= 1:
    inside.append((x, y))
  else:
    outside.append((x, y))

# Plotting points
plt.figure(figsize=(6,6))
plt.scatter(*zip(*inside), color="blue", s=1, label="Inside")
plt.scatter(*zip(*outside), color="red", s=1, label="Outside")
plt.legend()
plt.xlabel("x")
plt.ylabel("y")
plt.show()

estimate = 4 * len(inside) / (len(inside) + len(outside))
print(f"Estimated value of pi: {estimate}")
print(f"True value of pi: {np.pi}")

Banditi a più braccia

Metodi Monte Carlo per MDP

Tutto è chiaro?

Grazie per i tuoi commenti!

Sezione 4. Capitolo 1

Cosa Sono i Metodi Monte Carlo?

Come funzionano?

Esempi

Calcolo degli integrali

Approssimazione di π\Large\piπ

Banditi a più braccia

Metodi Monte Carlo per MDP

Awesome!

Cosa Sono i Metodi Monte Carlo?

Come funzionano?

Esempi

Calcolo degli integrali

Approssimazione di π\Large\piπ

Banditi a più braccia

Metodi Monte Carlo per MDP

Approssimazione di $\Large\pi$

Approssimazione di $\Large\pi$