Lära Vad är Monte Carlo-metoder?

Definition

Monte Carlo (MC)-metoder är en klass av beräkningsalgoritmer som bygger på slumpmässig provtagning för att uppskatta numeriska resultat.

Monte Carlo-metoder används när deterministiska lösningar är svåra eller omöjliga att erhålla. De ersätter exakta beräkningar med approximationer som förbättras med antalet slumpmässiga prover.

Hur fungerar de?

Monte Carlo-metoder kan variera mellan olika uppgifter, men alla tenderar att följa ett gemensamt mönster:

Definiera en domän av möjliga indata;
Generera slumpmässiga indata från en sannolikhetsfördelning;
Utvärdera en funktion på dessa indata;
Sammanfatta resultaten för att producera en uppskattning.

Exempel

Även om mönstret som beskrivs ovan kan låta komplext, bör dessa exempel hjälpa till att förtydliga idén bakom det.

Integralkomputation

Att beräkna integraler är en icke-trivial uppgift som vanligtvis kräver att flera tekniker tillämpas för att uppnå korrekt resultat.

Låt oss försöka använda Monte Carlo-metoden för att lösa denna integral:

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

Inmatningsdomän: denna dubbelintegral har två variabler, $x \in [0, 1]$ och $y \in [0, 1]$ ;
Generering: båda dessa variabler är oberoende av varandra och jämnt fördelade;
Utvärdering: för att få ett punktvärde kan funktionen under integralen användas;
Aggregering: värdet av denna integral kan definieras som volymen under kurvan. Volymen kan beräknas som produkten av basytan och medelhöjden. Basytan är 1 (enhetskvadrat) och medelhöjden är medelvärdet av resultaten från föregående steg.


              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}")

Approximation av $\Large\pi$

Att approximera $\pi$ är ett av de mest ikoniska användningsområdena för Monte Carlo-metoden. Det illustrerar hur slumpmässig sampling kan lösa ett geometriskt problem utan avancerad kalkyl.

Betrakta en enhetskvadrat med en inskriven kvartscirkel:

Kvadraten sträcker sig över $[0, 1] \times [0, 1]$ ;
Kvartscirkeln har radie 1 och är centrerad i origo.

Arean av kvartscirkeln är $\displaystyle\frac{\pi r^2}{4}$ eller $\displaystyle\frac{\pi}{4}$ , och arean av kvadraten är 1. Nu kan vi slumpmässigt välja punkter inom kvadraten. Med tillräckligt stort urval:

\frac{\text{Points inside the quarter circle}}{\text{Total points}} \approx \frac\pi4

Så värdet på $\pi$ kan beräknas som

\pi \approx 4 \cdot \frac{\text{Points inside}}{\text{Total points}}


              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}")

Multi-armed banditer

I multi-armed bandit-sammanhang är ett centralt mål att uppskatta aktionsvärdet för varje arm — det vill säga den förväntade belöningen av att välja en viss handling. En vanlig strategi är att uppskatta dessa värden genom att medelvärdesberäkna de observerade belöningarna som erhålls från att dra i varje arm över tid. Denna teknik är faktiskt en Monte Carlo-metod.

Monte Carlo-metoder för MDP:er

Till skillnad från dynamisk programmering, som är beroende av en fullständig och korrekt modell av miljöns dynamik, lär sig Monte Carlo-metoder enbart från erfarenhet — det vill säga från faktiska eller simulerade sekvenser av tillstånd, handlingar och belöningar.

Detta gör Monte Carlo-metoder särskilt kraftfulla: de kräver ingen förkunskap om hur miljön fungerar. Istället hämtar de värdeuppskattningar direkt från det som sker under interaktion. I många verkliga scenarier, där det är opraktiskt eller omöjligt att modellera miljön, är denna förmåga att lära från rå erfarenhet en stor fördel.

När direkt interaktion med miljön är kostsam, riskabel eller långsam, kan Monte Carlo-metoder även lära från simulerad erfarenhet, förutsatt att en tillförlitlig simulering finns. Detta möjliggör utforskning och inlärning i en kontrollerad, upprepningsbar miljö — även om det förutsätter tillgång till en modell som kan generera trovärdiga övergångar.

Var allt tydligt?

Tack för dina kommentarer!

Avsnitt 4. Kapitel 1

Fråga AI

Fråga vad du vill eller prova någon av de föreslagna frågorna för att starta vårt samtal

Svep för att visa menyn

Definition

Monte Carlo (MC)-metoder är en klass av beräkningsalgoritmer som bygger på slumpmässig provtagning för att uppskatta numeriska resultat.

Hur fungerar de?

Monte Carlo-metoder kan variera mellan olika uppgifter, men alla tenderar att följa ett gemensamt mönster:

Definiera en domän av möjliga indata;
Generera slumpmässiga indata från en sannolikhetsfördelning;
Utvärdera en funktion på dessa indata;
Sammanfatta resultaten för att producera en uppskattning.

Exempel

Även om mönstret som beskrivs ovan kan låta komplext, bör dessa exempel hjälpa till att förtydliga idén bakom det.

Integralkomputation

Att beräkna integraler är en icke-trivial uppgift som vanligtvis kräver att flera tekniker tillämpas för att uppnå korrekt resultat.

Låt oss försöka använda Monte Carlo-metoden för att lösa denna integral:

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

Inmatningsdomän: denna dubbelintegral har två variabler, $x \in [0, 1]$ och $y \in [0, 1]$ ;
Generering: båda dessa variabler är oberoende av varandra och jämnt fördelade;
Utvärdering: för att få ett punktvärde kan funktionen under integralen användas;
Aggregering: värdet av denna integral kan definieras som volymen under kurvan. Volymen kan beräknas som produkten av basytan och medelhöjden. Basytan är 1 (enhetskvadrat) och medelhöjden är medelvärdet av resultaten från föregående steg.


              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}")

Approximation av $\Large\pi$

Betrakta en enhetskvadrat med en inskriven kvartscirkel:

Kvadraten sträcker sig över $[0, 1] \times [0, 1]$ ;
Kvartscirkeln har radie 1 och är centrerad i origo.

\frac{\text{Points inside the quarter circle}}{\text{Total points}} \approx \frac\pi4

Så värdet på $\pi$ kan beräknas som

\pi \approx 4 \cdot \frac{\text{Points inside}}{\text{Total points}}


              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}")

Multi-armed banditer

Monte Carlo-metoder för MDP:er

Var allt tydligt?

Tack för dina kommentarer!

Avsnitt 4. Kapitel 1

Vad är Monte Carlo-metoder?

Hur fungerar de?

Exempel

Integralkomputation

Approximation av π\Large\piπ

Multi-armed banditer

Monte Carlo-metoder för MDP:er

Awesome!

Vad är Monte Carlo-metoder?

Hur fungerar de?

Exempel

Integralkomputation

Approximation av π\Large\piπ

Multi-armed banditer

Monte Carlo-metoder för MDP:er

Approximation av $\Large\pi$

Approximation av $\Large\pi$