Lære Hvad er Monte Carlo-metoder?

Definition

Monte Carlo (MC) metoder er en klasse af beregningsalgoritmer, der benytter tilfældig udvælgelse til at estimere numeriske resultater.

Monte Carlo-metoder anvendes, når deterministiske løsninger er vanskelige eller umulige at opnå. De erstatter præcise beregninger med approksimationer, som forbedres med antallet af tilfældige prøver.

Hvordan fungerer de?

Monte Carlo-metoder kan variere fra opgave til opgave, men de følger alle et fælles mønster:

Definer et domæne af mulige input;
Generer tilfældige input fra en sandsynlighedsfordeling;
Evaluer en funktion på disse input;
Aggregér resultaterne for at producere et estimat.

Eksempler

Selvom mønsteret beskrevet ovenfor kan lyde komplekst, bør disse eksempler hjælpe med at tydeliggøre idéen bag det.

Integralberegning

Beregning af integraler er en ikke-triviel opgave, der normalt kræver anvendelse af mange teknikker for at opnå det korrekte resultat.

Lad os forsøge at anvende Monte Carlo-metoden til at løse dette integral:

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

Inddataområde: dette dobbeltintegral har to variable, $x \in [0, 1]$ og $y \in [0, 1]$ ;
Generering: begge disse variable er uafhængige af hinanden og uniformt fordelt;
Evaluering: for at få en punktværdi kan funktionen under integralet anvendes;
Aggregering: værdien af dette integral kan defineres som et volumen under kurven. Volumen kan beregnes som produktet af basisarealet og gennemsnitshøjden. Basisarealet er 1 (enhedskvadrat), og gennemsnitshøjden er gennemsnittet af resultaterne fra det foregående trin.


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

Approksimation af $\Large\pi$

At approksimere $\pi$ er en af de mest ikoniske anvendelser af Monte Carlo-metoden. Det illustrerer, hvordan tilfældig sampling kan løse et geometrisk problem uden brug af kompleks calculus.

Overvej et enhedskvadrat med en kvartcirkel indskrevet:

Kvadratet spænder over $[0, 1] \times [0, 1]$ ;
Kvartcirklen har radius 1 og er centreret i origo.

Arealet af kvartcirklen er $\displaystyle\frac{\pi r^2}{4}$ eller $\displaystyle\frac{\pi}{4}$ , og arealet af kvadratet er 1. Lad os nu udtage tilfældige punkter inden for kvadratet. Med et tilstrækkeligt stort antal prøver gælder:

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

Så værdien af $\pi$ kan beregnes 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 Bandits

I multi-armed bandit-scenariet er et centralt mål at estimere aktionsværdien for hver arm — det vil sige den forventede belønning ved at vælge en bestemt handling. En almindelig strategi er at estimere disse værdier ved at gennemsnitliggøre de observerede belønninger, der opnås ved at trække i hver arm over tid. Denne teknik er faktisk en Monte Carlo-metode.

Monte Carlo-metoder for MDP'er

I modsætning til dynamisk programmering-metoder, som er afhængige af en fuldstændig og nøjagtig model af miljøets dynamik, lærer Monte Carlo-metoder udelukkende gennem erfaring — det vil sige fra faktiske eller simulerede sekvenser af tilstande, handlinger og belønninger.

Dette gør Monte Carlo-tilgange særligt kraftfulde: de kræver ingen forhåndsviden om, hvordan miljøet fungerer. I stedet udleder de værdiestimater direkte fra, hvad der sker under interaktionen. I mange virkelige scenarier, hvor modellering af miljøet er upraktisk eller umuligt, er denne evne til at lære af rå erfaring en væsentlig fordel.

Når direkte interaktion med miljøet er dyr, risikabel eller langsom, kan Monte Carlo-metoder også lære af simuleret erfaring, forudsat at der findes en pålidelig simulering. Dette muliggør udforskning og læring i et kontrolleret, gentageligt miljø — dog forudsætter det adgang til en model, der kan generere plausible overgange.

Var alt klart?

Tak for dine kommentarer!

Sektion 4. Kapitel 1

Spørg AI

Spørg om hvad som helst eller prøv et af de foreslåede spørgsmål for at starte vores chat

Stryg for at vise menuen

Definition

Monte Carlo (MC) metoder er en klasse af beregningsalgoritmer, der benytter tilfældig udvælgelse til at estimere numeriske resultater.

Hvordan fungerer de?

Monte Carlo-metoder kan variere fra opgave til opgave, men de følger alle et fælles mønster:

Definer et domæne af mulige input;
Generer tilfældige input fra en sandsynlighedsfordeling;
Evaluer en funktion på disse input;
Aggregér resultaterne for at producere et estimat.

Eksempler

Selvom mønsteret beskrevet ovenfor kan lyde komplekst, bør disse eksempler hjælpe med at tydeliggøre idéen bag det.

Integralberegning

Beregning af integraler er en ikke-triviel opgave, der normalt kræver anvendelse af mange teknikker for at opnå det korrekte resultat.

Lad os forsøge at anvende Monte Carlo-metoden til at løse dette integral:

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

Inddataområde: dette dobbeltintegral har to variable, $x \in [0, 1]$ og $y \in [0, 1]$ ;
Generering: begge disse variable er uafhængige af hinanden og uniformt fordelt;
Evaluering: for at få en punktværdi kan funktionen under integralet anvendes;
Aggregering: værdien af dette integral kan defineres som et volumen under kurven. Volumen kan beregnes som produktet af basisarealet og gennemsnitshøjden. Basisarealet er 1 (enhedskvadrat), og gennemsnitshøjden er gennemsnittet af resultaterne fra det foregående trin.


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

Approksimation af $\Large\pi$

Overvej et enhedskvadrat med en kvartcirkel indskrevet:

Kvadratet spænder over $[0, 1] \times [0, 1]$ ;
Kvartcirklen har radius 1 og er centreret i origo.

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

Så værdien af $\pi$ kan beregnes 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 Bandits

Monte Carlo-metoder for MDP'er

Var alt klart?

Tak for dine kommentarer!

Sektion 4. Kapitel 1

Hvad er Monte Carlo-metoder?

Hvordan fungerer de?

Eksempler

Integralberegning

Approksimation af π\Large\piπ

Multi-armed Bandits

Monte Carlo-metoder for MDP'er

Awesome!

Hvad er Monte Carlo-metoder?

Hvordan fungerer de?

Eksempler

Integralberegning

Approksimation af π\Large\piπ

Multi-armed Bandits

Monte Carlo-metoder for MDP'er

Approksimation af $\Large\pi$

Approksimation af $\Large\pi$