Monte-Carlo-Methoden sind eine Klasse von Techniken zur Zufallsstichprobenziehung einer Wahrscheinlichkeitsverteilung.

Es gibt viele Problembereiche, in denen die Beschreibung oder Schätzung der Wahrscheinlichkeitsverteilung relativ einfach ist, aber die Berechnung einer gewünschten Größe ist unlösbar. Dies kann viele Gründe haben, wie z. B. die stochastische Natur der Domäne oder eine exponentielle Anzahl von Zufallsvariablen.

Stattdessen kann eine gewünschte Größe durch die Verwendung von Zufallsstichproben angenähert werden, die als Monte-Carlo-Methoden bezeichnet werden. Diese Methoden wurden erstmals zu der Zeit verwendet, als die ersten Computer entwickelt wurden, und sind in allen Bereichen der Wissenschaft und Technik, einschließlich künstlicher Intelligenz und maschinellem Lernen, allgegenwärtig.

In diesem Beitrag lernen Sie Monte-Carlo-Methoden für die Stichprobenziehung von Wahrscheinlichkeitsverteilungen kennen.

Nach dem Lesen dieses Beitrags wissen Sie:

• Oft können wir eine gewünschte Menge nicht mit Wahrscheinlichkeit berechnen, aber wir können die Wahrscheinlichkeitsverteilungen für die Zufallsvariablen direkt oder indirekt definieren.
• Monte-Carlo-Sampling eine Klasse von Methoden für die Zufallsauswahl aus einer Wahrscheinlichkeitsverteilung.
• Monte-Carlo-Sampling bildet die Grundlage für viele Methoden des maschinellen Lernens wie Resampling, Hyperparameter-Tuning und Ensemble-Lernen.

Starten Sie Ihr Projekt mit meinem neuen Buch Probability for Machine Learning, inklusive Schritt-für-Schritt-Tutorials und den Python-Quellcode-Dateien für alle Beispiele.

Lassen Sie uns loslegen.

Übersicht

Dieses Tutorial ist in drei Teile gegliedert; sie sind:

1. Notwendigkeit der Stichprobenziehung
2. Was sind Monte-Carlo-Methoden?
3. Beispiele für Monte-Carlo-Methoden

Notwendigkeit des Samplings

Es gibt viele Probleme in der Wahrscheinlichkeitsrechnung und im weiteren Sinne im maschinellen Lernen, bei denen wir nicht direkt eine analytische Lösung berechnen können.

In der Tat kann man argumentieren, dass eine exakte Inferenz für die meisten praktischen probabilistischen Modelle unpraktikabel ist.

Für die meisten probabilistischen Modelle von praktischem Interesse ist eine exakte Inferenz unpraktikabel, und so müssen wir auf eine Form der Approximation zurückgreifen.

– Seite 523, Pattern Recognition and Machine Learning, 2006.

Die gewünschte Berechnung ist typischerweise eine Summe einer diskreten Verteilung oder ein Integral einer kontinuierlichen Verteilung und ist intractable zu berechnen. Die Berechnung kann aus vielen Gründen intractable sein, wie z. B. die große Anzahl von Zufallsvariablen, die stochastische Natur des Gebiets, Rauschen in den Beobachtungen, das Fehlen von Beobachtungen und mehr.

Bei Problemen dieser Art ist es oft möglich, die Wahrscheinlichkeitsverteilungen für die beteiligten Zufallsvariablen zu definieren oder zu schätzen, entweder direkt oder indirekt über eine rechnerische Simulation.

Anstatt die Größe direkt zu berechnen, kann Sampling verwendet werden.

Sampling bietet eine flexible Möglichkeit, viele Summen und Integrale zu reduzierten Kosten zu approximieren.

– Seite 590, Deep Learning, 2016.

Samples können zufällig aus der Wahrscheinlichkeitsverteilung gezogen und zur Approximation der gewünschten Größe verwendet werden.

Diese allgemeine Klasse von Techniken zur zufälligen Ziehung von Stichproben aus einer Wahrscheinlichkeitsverteilung wird als Monte-Carlo-Methoden bezeichnet.

Willst du Wahrscheinlichkeit für maschinelles Lernen lernen

Nimm jetzt meinen kostenlosen 7-Tage-E-Mail-Crashkurs (mit Beispielcode).

Klicken Sie hier, um sich anzumelden und zusätzlich eine kostenlose PDF-Ebook-Version des Kurses zu erhalten.

Laden Sie sich Ihren KOSTENLOSEN Mini-Kurs herunter

Was sind Monte-Carlo-Methoden?

Monte-Carlo-Methoden, kurz MC, sind eine Klasse von Techniken für die Zufallsauswahl einer Wahrscheinlichkeitsverteilung.

Es gibt drei Hauptgründe für die Verwendung von Monte-Carlo-Methoden zur Stichprobenziehung einer Wahrscheinlichkeitsverteilung; sie sind:

• Dichte schätzen, Stichproben sammeln, um die Verteilung einer Zielfunktion zu approximieren.
• Annäherung an eine Größe, z. B. den Mittelwert oder die Varianz einer Verteilung.
• Optimierung einer Funktion, Auffinden einer Stichprobe, die die Zielfunktion maximiert oder minimiert.

Monte-Carlo-Methoden sind nach dem Casino in Monaco benannt und wurden erstmals entwickelt, um Probleme in der Teilchenphysik zu lösen, etwa zur Zeit der Entwicklung der ersten Computer und des Manhattan-Projekts zur Entwicklung der ersten Atombombe.

Dies nennt man eine Monte-Carlo-Approximation, benannt nach einer Stadt in Europa, die für ihre plüschigen Spielkasinos bekannt ist. Monte-Carlo-Techniken wurden zuerst im Bereich der statistischen Physik – insbesondere bei der Entwicklung der Atombombe – entwickelt, werden aber inzwischen auch in der Statistik und beim maschinellen Lernen häufig eingesetzt.

– Seite 52, Maschinelles Lernen: A Probabilistic Perspective, 2012.

Die Ziehung einer Stichprobe kann so einfach sein wie die Berechnung der Wahrscheinlichkeit für ein zufällig ausgewähltes Ereignis oder so komplex wie die Durchführung einer Computersimulation, wobei letztere oft als Monte-Carlo-Simulation bezeichnet wird.

Mehrere Stichproben werden gesammelt und verwendet, um die gewünschte Menge zu approximieren.

Nach dem Gesetz der großen Zahlen aus der Statistik wird die approximierte Größe umso genauer, je mehr Zufallsversuche durchgeführt werden.

… das Gesetz der großen Zahlen besagt, dass wenn die Stichproben x(i) i.i.d. sind, dann konvergiert der Durchschnitt fast sicher zum Erwartungswert

– Seite 591, Deep Learning, 2016.

Als solches bietet die Anzahl der Stichproben eine Kontrolle über die Genauigkeit der zu approximierenden Größe, die oft durch die Rechenkomplexität des Ziehens einer Stichprobe begrenzt wird.

Indem wir genügend Stichproben erzeugen, können wir jedes gewünschte Maß an Genauigkeit erreichen. Das Hauptproblem ist: Wie erzeugen wir effizient Stichproben aus einer Wahrscheinlichkeitsverteilung, insbesondere in hohen Dimensionen?

– Seite 815, Maschinelles Lernen: A Probabilistic Perspective, 2012.

Ausgehend vom zentralen Grenzwertsatz wird die Verteilung der Stichproben eine Normalverteilung bilden, deren Mittelwert als approximierte Größe genommen und die Varianz verwendet werden kann, um ein Konfidenzintervall für die Größe zu liefern.

Das zentrale Grenzwertsatz besagt, dass die Verteilung des Mittelwerts , zu einer Normalverteilung konvergiert. Dies erlaubt uns, Konfidenzintervalle um den Schätzwert , unter Verwendung der kumulativen Verteilung der Normaldichte zu schätzen.

– Seite 592, Deep Learning, 2016.

Monte-Carlo-Methoden werden durch die Art und Weise definiert, wie Stichproben gezogen werden, oder durch die Einschränkungen, die dem Stichprobenprozess auferlegt werden.

Einige Beispiele für Monte-Carlo-Sampling-Methoden sind: direktes Sampling, Wichtigkeits-Sampling und Rejection Sampling.

• Direktes Sampling. Direktes Sampling der Verteilung ohne vorherige Information.
• Importance Sampling. Stichprobenziehung aus einer einfacheren Annäherung an die Zielverteilung.
• Rejection Sampling. Stichprobenziehung aus einer breiteren Verteilung und Berücksichtigung von Stichproben nur innerhalb eines Bereichs der gesampelten Verteilung.

Es ist ein riesiges Thema, dem viele Bücher gewidmet sind. Als Nächstes wollen wir die Idee des Monte-Carlo-Samplings anhand einiger bekannter Beispiele konkretisieren.

Beispiele für Monte-Carlo-Sampling

Wir verwenden ständig Monte-Carlo-Methoden, ohne darüber nachzudenken.

Wenn wir zum Beispiel eine Bernoulli-Verteilung für einen Münzwurf definieren und das Werfen einer Münze durch Stichproben aus dieser Verteilung simulieren, führen wir eine Monte-Carlo-Simulation durch. Außerdem führen wir eine Monte-Carlo-Simulation durch, wenn wir eine Stichprobe aus einer Gleichverteilung für die ganzen Zahlen {1,2,3,4,5,6} ziehen, um den Wurf eines Würfels zu simulieren.

Wir verwenden die Monte-Carlo-Methode auch, wenn wir eine Zufallsstichprobe von Daten aus dem Bereich sammeln und die Wahrscheinlichkeitsverteilung der Daten mithilfe eines Histogramms oder einer Dichteschätzmethode schätzen.

Es gibt viele Beispiele für den Einsatz von Monte-Carlo-Methoden in einer Reihe von wissenschaftlichen Disziplinen.

Zum Beispiel können Monte-Carlo-Methoden verwendet werden für:

• Berechnen der Wahrscheinlichkeit eines Zuges eines Gegners in einem komplexen Spiel.
• Berechnung der Wahrscheinlichkeit eines Wetterereignisses in der Zukunft.
• Berechnung der Wahrscheinlichkeit eines Fahrzeugunfalls unter bestimmten Bedingungen.

Die Methoden werden verwendet, um schwierige Inferenzen bei Problemen in der angewandten Wahrscheinlichkeitsrechnung anzugehen, wie z.B. die Stichprobenziehung aus probabilistischen grafischen Modellen.

Verwandt ist die Idee der sequentiellen Monte-Carlo-Methoden, die in Bayes’schen Modellen verwendet werden und oft als Partikelfilter bezeichnet werden.

Partikelfilterung (PF) ist ein Monte-Carlo- oder simulationsbasierter Algorithmus für rekursive Bayes’sche Inferenz.

– Seite 823, Machine Learning: A Probabilistic Perspective, 2012.

Monte-Carlo-Methoden sind auch in der künstlichen Intelligenz und im maschinellen Lernen allgegenwärtig.

Viele wichtige Technologien, die zum Erreichen der Ziele des maschinellen Lernens verwendet werden, basieren auf der Ziehung von Stichproben aus einer Wahrscheinlichkeitsverteilung und der Verwendung dieser Stichproben zur Bildung einer Monte-Carlo-Schätzung einer gewünschten Größe.

– Seite 590, Deep Learning, 2016.

Sie bilden die Grundlage für die Schätzung der Wahrscheinlichkeit von Ergebnissen bei Problemen der künstlichen Intelligenz durch Simulation, z. B. in der Robotik. Einfacher ausgedrückt: Monte-Carlo-Methoden werden verwendet, um unlösbare Integrationsprobleme zu lösen, wie z. B. das Abfeuern zufälliger Strahlen bei der Pfadverfolgung in der Computergrafik beim Rendern einer computergenerierten Szene.

Im maschinellen Lernen bilden Monte-Carlo-Methoden die Grundlage für Resampling-Techniken wie die Bootstrap-Methode zur Schätzung einer Größe, z. B. der Genauigkeit eines Modells auf einem begrenzten Datensatz.

Der Bootstrap ist eine einfache Monte-Carlo-Technik zur Annäherung an die Stichprobenverteilung. Dies ist besonders nützlich in Fällen, in denen der Schätzer eine komplexe Funktion der wahren Parameter ist.

– Seite 192, Maschinelles Lernen: A Probabilistic Perspective, 2012.

Zufälliges Sampling von Modell-Hyperparametern beim Tuning eines Modells ist eine Monte-Carlo-Methode, ebenso wie Ensemble-Modelle, die verwendet werden, um Herausforderungen wie die begrenzte Größe und das Rauschen in einer kleinen Datenstichprobe und die stochastische Varianz in einem Lernalgorithmus zu überwinden.

• Resampling-Algorithmen.
• Zufälliges Hyperparameter-Tuning.
• Ensemble-Lernalgorithmen.

Monte-Carlo-Methoden bilden auch die Grundlage für randomisierte oder stochastische Optimierungsalgorithmen, wie z. B. die beliebte Simulated Annealing-Optimierungstechnik.

Monte-Carlo-Algorithmen, von denen Simulated Annealing ein Beispiel ist, werden in vielen Zweigen der Wissenschaft verwendet, um schwer exakt zu berechnende Größen abzuschätzen.

– Seite 530, Artificial Intelligence: A Modern Approach, 3rd edition, 2009.

• Stochastische Optimierungsalgorithmen.

Arbeitsbeispiel für Monte-Carlo-Sampling

Wir können das Monte-Carlo-Sampling anhand eines Arbeitsbeispiels konkretisieren.

In diesem Fall haben wir eine Funktion, die die Wahrscheinlichkeitsverteilung einer Zufallsvariablen definiert. Wir werden eine Gauß-Verteilung mit einem Mittelwert von 50 und einer Standardabweichung von 5 verwenden und Stichproben aus dieser Verteilung ziehen.

Setzen wir voraus, dass wir die Form der Wahrscheinlichkeitsverteilung für diese Zufallsvariable nicht kennen und die Funktion stichprobenartig untersuchen wollen, um eine Vorstellung von der Wahrscheinlichkeitsdichte zu bekommen. Wir können eine Stichprobe einer bestimmten Größe ziehen und ein Histogramm zeichnen, um die Dichte abzuschätzen.

Die NumPy-Funktion normal() kann verwendet werden, um Stichproben aus einer Gauß-Verteilung mit dem angegebenen Mittelwert (mu), der Standardabweichung (sigma) und der Stichprobengröße zu ziehen.

Um das Beispiel interessanter zu machen, werden wir dieses Experiment viermal mit unterschiedlich großen Stichproben wiederholen. Es ist zu erwarten, dass die Wahrscheinlichkeitsdichte mit zunehmender Größe der Stichprobe die wahre Dichte der Zielfunktion besser annähert, da das Gesetz der großen Zahlen gilt.

Das vollständige Beispiel ist unten aufgeführt.

Das Ausführen des Beispiels erzeugt vier unterschiedlich große Stichproben und zeichnet für jede ein Histogramm.

Wir können sehen, dass die kleinen Stichprobengrößen von 10 und 50 die Dichte der Zielfunktion nicht effektiv erfassen. Wir können sehen, dass 100 Stichproben besser sind, aber erst bei 1.000 Stichproben sehen wir deutlich die bekannte Glockenform der Gaußschen Wahrscheinlichkeitsverteilung.

Dies unterstreicht die Notwendigkeit, viele Stichproben zu ziehen, selbst für eine einfache Zufallsvariable, und den Vorteil, dass die Genauigkeit der Approximation mit der Anzahl der gezogenen Stichproben steigt.

Weitere Lektüre

In diesem Abschnitt finden Sie weitere Ressourcen zum Thema, wenn Sie tiefer einsteigen möchten.

Bücher

• Kapitel 29 Monte-Carlo-Methoden, Informationstheorie, Inferenz und Lernalgorithmen, 2003.
• Kapitel 27 Sampling, Bayesian Reasoning and Machine Learning, 2011.
• Abschnitt 14.5 Approximate Inference In Bayesian Networks, Artificial Intelligence: A Modern Approach, 3. Auflage, 2009.
• Kapitel 23 Monte-Carlo-Inferenz, Maschinelles Lernen: A Probabilistic Perspective, 2012.
• Kapitel 11 Sampling Methods, Pattern Recognition and Machine Learning, 2006.
• Kapitel 17 Monte Carlo Methods, Deep Learning, 2016.

Artikel

• Sampling (Statistik), Wikipedia.
• Monte-Carlo-Methode, Wikipedia.
• Monte-Carlo-Integration, Wikipedia.
• Importance Sampling, Wikipedia.
• Rejection Sampling, Wikipedia.

Zusammenfassung

In diesem Beitrag haben Sie Monte-Carlo-Methoden für das Sampling von Wahrscheinlichkeitsverteilungen kennengelernt.

Speziell haben Sie gelernt:

• Oft können wir eine gewünschte Größe nicht in der Wahrscheinlichkeitsrechnung berechnen, aber wir können die Wahrscheinlichkeitsverteilungen für die Zufallsvariablen direkt oder indirekt definieren.
• Monte-Carlo-Sampling eine Klasse von Methoden für das Sampling aus einer Wahrscheinlichkeitsverteilung.
• Monte-Carlo-Sampling bildet die Grundlage für viele Methoden des maschinellen Lernens wie Resampling, Hyperparameter-Tuning und Ensemble-Lernen.

Haben Sie noch Fragen?
Stellen Sie Ihre Fragen in den Kommentaren unten und ich werde mein Bestes tun, um sie zu beantworten.