Was sind Monte-Carlo-Methoden?
Monte-Carlo-(MC)-Methoden sind eine Klasse von rechnergestützten Algorithmen, die auf Zufallsstichproben basieren, um numerische Ergebnisse zu schätzen.
Monte-Carlo-Methoden werden eingesetzt, wenn deterministische Lösungen schwierig oder unmöglich zu erhalten sind. Sie ersetzen exakte Berechnungen durch Approximationen, die sich mit der Anzahl der Zufallsstichproben verbessern.
Funktionsweise
Monte-Carlo-Methoden können je nach Aufgabe variieren, folgen jedoch alle einem einheitlichen Muster:
- Definition eines Bereichs möglicher Eingaben;
- Erzeugung zufälliger Eingaben aus einer Wahrscheinlichkeitsverteilung;
- Auswertung einer Funktion auf diesen Eingaben;
- Aggregation der Ergebnisse zur Schätzung.
Beispiele
Obwohl das oben beschriebene Muster komplex erscheinen mag, sollten diese Beispiele die dahinterstehende Idee verdeutlichen.
Integralberechnung
Die Berechnung von Integralen ist eine anspruchsvolle Aufgabe, die in der Regel den Einsatz verschiedener Techniken erfordert, um das korrekte Ergebnis zu erzielen.
Im Folgenden wird versucht, das Monte-Carlo-Verfahren zur Lösung dieses Integrals anzuwenden:
∫01∫011+(x+y)21dxdy- Eingabebereich: Dieses Doppelintegral besitzt zwei Variablen, x∈[0,1] und y∈[0,1];
- Generierung: Beide Variablen sind unabhängig voneinander und gleichverteilt;
- Auswertung: Zur Bestimmung eines Punktwerts kann die Funktion unter dem Integral verwendet werden;
- Aggregation: Der Wert dieses Integrals kann als Volumen unter der Kurve definiert werden. Das Volumen ergibt sich als Produkt aus Grundfläche und durchschnittlicher Höhe. Die Grundfläche beträgt 1 (Einheitsquadrat) und die durchschnittliche Höhe ist der Mittelwert der im vorherigen Schritt erhaltenen Ergebnisse.
12345678910111213141516import 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 von π
Die Approximation von π ist eine der bekanntesten Anwendungen der Monte-Carlo-Methode. Sie zeigt, wie zufällige Stichproben ein geometrisches Problem lösen können, ohne dass komplexe Analysis erforderlich ist.
Betrachte ein Einheitsquadrat mit einem eingeschriebenen Viertelkreis:
- Das Quadrat erstreckt sich über [0,1]×[0,1];
- Der Viertelkreis hat den Radius 1 und ist im Ursprung zentriert.
Die Fläche des Viertelkreises beträgt 4πr2 bzw. 4π, und die Fläche des Quadrats ist 1. Nun werden zufällige Punkte innerhalb des Quadrats gezogen. Bei ausreichend großer Stichprobe gilt:
Gesamtanzahl der PunktePunkte im Viertelkreis≈4πDer Wert von π kann somit berechnet werden als
π≈4⋅Gesamtanzahl der PunktePunkte im Viertelkreis1234567891011121314151617181920212223242526272829import 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
Im Multi-Armed-Bandit-Szenario besteht ein zentrales Ziel darin, den Aktionswert für jeden Arm zu schätzen – das heißt, die erwartete Belohnung bei Auswahl einer bestimmten Aktion. Eine gängige Strategie ist die Schätzung dieser Werte durch Mittelung der beobachteten Belohnungen, die im Laufe der Zeit durch Ziehen jedes Arms erhalten wurden. Diese Technik ist tatsächlich eine Monte-Carlo-Methode.
Monte-Carlo-Methoden für MDPs
Im Gegensatz zu dynamischen Programmiermethoden, die auf ein vollständiges und genaues Modell der Umgebungsdynamik angewiesen sind, lernen Monte-Carlo-Methoden ausschließlich aus Erfahrung – das heißt, aus tatsächlichen oder simulierten Sequenzen von Zuständen, Aktionen und Belohnungen.
Dies macht Monte-Carlo-Ansätze besonders leistungsfähig: Sie erfordern kein Vorwissen darüber, wie die Umgebung funktioniert. Stattdessen werden Wertschätzungen direkt aus den während der Interaktion gesammelten Erfahrungen abgeleitet. In vielen realen Szenarien, in denen die Modellierung der Umgebung unpraktisch oder unmöglich ist, stellt diese Fähigkeit, aus roher Erfahrung zu lernen, einen entscheidenden Vorteil dar.
Wenn die direkte Interaktion mit der Umgebung kostspielig, riskant oder langsam ist, können Monte-Carlo-Methoden auch aus simulierter Erfahrung lernen, sofern eine zuverlässige Simulation existiert. Dies ermöglicht Erkundung und Lernen in einer kontrollierten, wiederholbaren Umgebung – vorausgesetzt, es steht ein Modell zur Verfügung, das plausible Übergänge erzeugen kann.
Danke für Ihr Feedback!
Fragen Sie AI
Fragen Sie AI
Fragen Sie alles oder probieren Sie eine der vorgeschlagenen Fragen, um unser Gespräch zu beginnen
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
Was sind Monte-Carlo-Methoden?
Swipe um das Menü anzuzeigen
Monte-Carlo-(MC)-Methoden sind eine Klasse von rechnergestützten Algorithmen, die auf Zufallsstichproben basieren, um numerische Ergebnisse zu schätzen.
Monte-Carlo-Methoden werden eingesetzt, wenn deterministische Lösungen schwierig oder unmöglich zu erhalten sind. Sie ersetzen exakte Berechnungen durch Approximationen, die sich mit der Anzahl der Zufallsstichproben verbessern.
Funktionsweise
Monte-Carlo-Methoden können je nach Aufgabe variieren, folgen jedoch alle einem einheitlichen Muster:
- Definition eines Bereichs möglicher Eingaben;
- Erzeugung zufälliger Eingaben aus einer Wahrscheinlichkeitsverteilung;
- Auswertung einer Funktion auf diesen Eingaben;
- Aggregation der Ergebnisse zur Schätzung.
Beispiele
Obwohl das oben beschriebene Muster komplex erscheinen mag, sollten diese Beispiele die dahinterstehende Idee verdeutlichen.
Integralberechnung
Die Berechnung von Integralen ist eine anspruchsvolle Aufgabe, die in der Regel den Einsatz verschiedener Techniken erfordert, um das korrekte Ergebnis zu erzielen.
Im Folgenden wird versucht, das Monte-Carlo-Verfahren zur Lösung dieses Integrals anzuwenden:
∫01∫011+(x+y)21dxdy- Eingabebereich: Dieses Doppelintegral besitzt zwei Variablen, x∈[0,1] und y∈[0,1];
- Generierung: Beide Variablen sind unabhängig voneinander und gleichverteilt;
- Auswertung: Zur Bestimmung eines Punktwerts kann die Funktion unter dem Integral verwendet werden;
- Aggregation: Der Wert dieses Integrals kann als Volumen unter der Kurve definiert werden. Das Volumen ergibt sich als Produkt aus Grundfläche und durchschnittlicher Höhe. Die Grundfläche beträgt 1 (Einheitsquadrat) und die durchschnittliche Höhe ist der Mittelwert der im vorherigen Schritt erhaltenen Ergebnisse.
12345678910111213141516import 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 von π
Die Approximation von π ist eine der bekanntesten Anwendungen der Monte-Carlo-Methode. Sie zeigt, wie zufällige Stichproben ein geometrisches Problem lösen können, ohne dass komplexe Analysis erforderlich ist.
Betrachte ein Einheitsquadrat mit einem eingeschriebenen Viertelkreis:
- Das Quadrat erstreckt sich über [0,1]×[0,1];
- Der Viertelkreis hat den Radius 1 und ist im Ursprung zentriert.
Die Fläche des Viertelkreises beträgt 4πr2 bzw. 4π, und die Fläche des Quadrats ist 1. Nun werden zufällige Punkte innerhalb des Quadrats gezogen. Bei ausreichend großer Stichprobe gilt:
Gesamtanzahl der PunktePunkte im Viertelkreis≈4πDer Wert von π kann somit berechnet werden als
π≈4⋅Gesamtanzahl der PunktePunkte im Viertelkreis1234567891011121314151617181920212223242526272829import 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
Im Multi-Armed-Bandit-Szenario besteht ein zentrales Ziel darin, den Aktionswert für jeden Arm zu schätzen – das heißt, die erwartete Belohnung bei Auswahl einer bestimmten Aktion. Eine gängige Strategie ist die Schätzung dieser Werte durch Mittelung der beobachteten Belohnungen, die im Laufe der Zeit durch Ziehen jedes Arms erhalten wurden. Diese Technik ist tatsächlich eine Monte-Carlo-Methode.
Monte-Carlo-Methoden für MDPs
Im Gegensatz zu dynamischen Programmiermethoden, die auf ein vollständiges und genaues Modell der Umgebungsdynamik angewiesen sind, lernen Monte-Carlo-Methoden ausschließlich aus Erfahrung – das heißt, aus tatsächlichen oder simulierten Sequenzen von Zuständen, Aktionen und Belohnungen.
Dies macht Monte-Carlo-Ansätze besonders leistungsfähig: Sie erfordern kein Vorwissen darüber, wie die Umgebung funktioniert. Stattdessen werden Wertschätzungen direkt aus den während der Interaktion gesammelten Erfahrungen abgeleitet. In vielen realen Szenarien, in denen die Modellierung der Umgebung unpraktisch oder unmöglich ist, stellt diese Fähigkeit, aus roher Erfahrung zu lernen, einen entscheidenden Vorteil dar.
Wenn die direkte Interaktion mit der Umgebung kostspielig, riskant oder langsam ist, können Monte-Carlo-Methoden auch aus simulierter Erfahrung lernen, sofern eine zuverlässige Simulation existiert. Dies ermöglicht Erkundung und Lernen in einer kontrollierten, wiederholbaren Umgebung – vorausgesetzt, es steht ein Modell zur Verfügung, das plausible Übergänge erzeugen kann.
Danke für Ihr Feedback!