Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.
Lære Hvad er Monte Carlo-metoder? | Monte Carlo-metoder
Introduktion til Reinforcement Learning
course content

Kursusindhold

Introduktion til Reinforcement Learning

Introduktion til Reinforcement Learning

1. RL Kerneprincipper
2. Multi-Armet Bandit-Problem
3. Dynamisk Programmering
4. Monte Carlo-metoder
5. Temporal Difference-Læring

book
Hvad er Monte Carlo-metoder?

Note
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:

  1. Definer et domæne af mulige input;
  2. Generer tilfældige input fra en sandsynlighedsfordeling;
  3. Evaluer en funktion på disse input;
  4. 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:

010111+(x+y)2dxdy\int_0^1 \int_0^1 \frac{1}{1 + (x + y)^2} \, dx \, dy
  1. Inddataområde: dette dobbeltintegral har to variable, x[0,1]x \in [0, 1] og y[0,1]y \in [0, 1];
  2. Generering: begge disse variable er uafhængige af hinanden og uniformt fordelt;
  3. Evaluering: for at få en punktværdi kan funktionen under integralet anvendes;
  4. 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}")
copy

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]×[0,1][0, 1] \times [0, 1];
  • Kvartcirklen har radius 1 og er centreret i origo.

Arealet af kvartcirklen er πr24\displaystyle\frac{\pi r^2}{4} eller π4\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:

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

Så værdien af π\pi kan beregnes som

π4Points insideTotal points\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}")
copy

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.

question mark

Hvad er en primær fordel ved at bruge Monte Carlo-metoder frem for dynamisk programmering til løsning af MDP'er?

Select the correct answer

Var alt klart?

Hvordan kan vi forbedre det?

Tak for dine kommentarer!

Sektion 4. Kapitel 1

Spørg AI

expand

Spørg AI

ChatGPT

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

course content

Kursusindhold

Introduktion til Reinforcement Learning

Introduktion til Reinforcement Learning

1. RL Kerneprincipper
2. Multi-Armet Bandit-Problem
3. Dynamisk Programmering
4. Monte Carlo-metoder
5. Temporal Difference-Læring

book
Hvad er Monte Carlo-metoder?

Note
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:

  1. Definer et domæne af mulige input;
  2. Generer tilfældige input fra en sandsynlighedsfordeling;
  3. Evaluer en funktion på disse input;
  4. 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:

010111+(x+y)2dxdy\int_0^1 \int_0^1 \frac{1}{1 + (x + y)^2} \, dx \, dy
  1. Inddataområde: dette dobbeltintegral har to variable, x[0,1]x \in [0, 1] og y[0,1]y \in [0, 1];
  2. Generering: begge disse variable er uafhængige af hinanden og uniformt fordelt;
  3. Evaluering: for at få en punktværdi kan funktionen under integralet anvendes;
  4. 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}")
copy

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]×[0,1][0, 1] \times [0, 1];
  • Kvartcirklen har radius 1 og er centreret i origo.

Arealet af kvartcirklen er πr24\displaystyle\frac{\pi r^2}{4} eller π4\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:

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

Så værdien af π\pi kan beregnes som

π4Points insideTotal points\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}")
copy

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.

question mark

Hvad er en primær fordel ved at bruge Monte Carlo-metoder frem for dynamisk programmering til løsning af MDP'er?

Select the correct answer

Var alt klart?

Hvordan kan vi forbedre det?

Tak for dine kommentarer!

Sektion 4. Kapitel 1
some-alt