Grundlagen Statistik & Algorithmen, Teil 4

Der Monte-Carlo-Algorithmus und -Simulationen

| Autor / Redakteur: Michael Matzer / Nico Litzel

Der monegassische Stadtbezirk Monte-Carlo
Der monegassische Stadtbezirk Monte-Carlo (Bild: © Noppasinw - stock.adobe.com)

Eine Reihe von Algorithmen dient der Suche von Lösungen, ohne vorher die Antwort zu kennen, und von Entscheidungen, die nach „wahrscheinlich richtig oder falsch“ beurteilt werden. Das ist sinnvoll für das Risiko-Management, aber auch für die Nutzung von Supercomputern. Ein solcher Algorithmus ist der Monte-Carlo-Algorithmus und die darauf basierenden Simulationen

Im Unterschied zu einem deterministischen Algorithmus, der mit definierten und reproduzierbaren Zuständen arbeitet, arbeitet ein Monte-Carlo-Algorithmus ergebnisoffen mit Zufallswerten. Das klingt zunächst zwar wenig ermutigend, aber der Nutzer arbeitet hier, wie sonst, mit Wahrscheinlichkeiten statt mit Gewissheiten.

Ein Monte-Carlo-(MC)-Algorithmus ist ein randomisierter Algorithmus, der durch die Wahl von zufälligen Zwischenergebnissen zu einem (im Mittel) guten bzw. näherungsweise korrekten Ergebnis gelangen soll. Mit Zufallswerten gefüttert, darf der MC-Algorithmus mit einer nach oben beschränkten Wahrscheinlichkeit ein falsches Ergebnis liefern. Man rechnet also keinesfalls wild drauflos, bis der Welt die Energie ausgegangen ist, sondern hat von vornherein eine Bremse eingebaut.

Wiederholt man den Algorithmus mit unabhängigen Zufallsbits genügend oft, wird sukzessive die Fehlerwahrscheinlichkeit gesenkt. Sinkt sie unter einen vertretbaren Schwellenwert (KPI: Key Performance Indicator), dann ist die Antwort bzw. Entscheidung wahrscheinlich richtig. Der Clou: Der MC-Algorithmus darf ein falsches Ergebnis liefern, sein ebenso randomisierter Bruder, der Las-Vegas-Algorithmus, darf hingegen nur korrekte Lösungen berechnen. Beide lassen sich ineinander konvertieren.

Entscheidungsprobleme

Wie gesagt, gibt es Monte-Carlo-Algorithmen für Suchprobleme (Probleme, bei denen eine Lösung zu berechnen ist) und für Entscheidungsprobleme (Probleme, bei denen eine Ja/Nein-Frage zu beantworten ist). Eine solche Entscheidung könnte die Beurteilung eines eingehenden Datenpakets nach seiner Legitimität und Unschädlichkeit sein, aber auch ein so komplexer Vorgang wie etwa eine Kreditvergabe (im Bereich Risk Management).

Bei Monte-Carlo-Algorithmen für Entscheidungsprobleme unterscheidet man zwischen ein- und zweiseitigen Fehlern. Bei einem zweiseitigen Fehler darf ein Monte-Carlo-Algorithmus sowohl False Positives liefern (also die Ausgabe „Ja“, obwohl „Nein“ richtig wäre), als auch False Negatives (also die Ausgabe „Nein“, obwohl „Ja“ richtig wäre).

Bei einseitigem Fehler ist nur eine der beiden Fehlermöglichkeiten erlaubt. Eine häufige Vereinbarung besteht darin, von einem einseitigen Fehler zu sprechen und damit False Negatives zu meinen. Es gibt dabei drei Komplexitätsklassen für Probleme.

Komplexitätsklassen für Entscheidungsprobleme mit randomisierten Algorithmen

  • BPP (von englisch bounded error probabilistic polynomial time): Wenn die korrekte Ausgabe Ja (Nein) lautet, beträgt die Wahrscheinlichkeit, dass der Algorithmus Ja (oder Nein) ausgibt, mindestens 2/3.
  • RP (von englisch randomized polynomial time): Wenn die korrekte Ausgabe Ja lautet, beträgt die Wahrscheinlichkeit, dass der Algorithmus Ja ausgibt, mindestens 1/2. Wenn die korrekte Ausgabe Nein lautet, beträgt die Wahrscheinlichkeit, dass der Algorithmus Nein ausgibt, 1.
  • co-RP: Wenn die korrekte Ausgabe Ja lautet, beträgt die Wahrscheinlichkeit, dass der Algorithmus Ja ausgibt, 1; wenn die korrekte Ausgabe Nein lautet, beträgt die Wahrscheinlichkeit, dass der Algorithmus Nein ausgibt, mindestens 1/2. Damit enthält co-RP die Komplemente der Probleme in RP. RP und co-RP ergänzen einander.

Wenn ein solcher RP-Algorithmus die Ausgabe Ja liefert, wissen wir mit Sicherheit, dass die Ausgabe Ja korrekt ist (da die Definition sicherstellt, dass bei korrekter Ausgabe Nein dies auf jeden Fall auch ausgegeben wird). Wenn dagegen ein RP-Algorithmus die Ausgabe Nein liefert, wissen wir nichts über die korrekte Ausgabe (da nach der Definition die Ausgabe Nein möglich ist, wenn Ja oder Nein korrekt wäre).

Anwendungsfälle

Der Nutzwert des MC-Algorithmus wird deutlicher, wenn man seine Anwendungsfälle unter die Lupe nimmt. Ein Beispiel ist der Miller-Rabin-Test, bei dem bestimmt wird, ob eine natürliche Zahl eine Primzahl ist. Die Ausgabe des Tests lautet entweder „sicher zusammengesetzt“ oder „wahrscheinlich prim“. Die Wahrscheinlichkeit, dass eine zusammengesetzte Zahl als „wahrscheinlich prim“ klassifiziert wird, liegt pro Durchgang unter 25 Prozent und kann durch mehrfache Ausführung weiter gesenkt werden (sodass mit höherer Wahrscheinlichkeit Primzahlen gefunden werden). Der Miller-Rabin-Test liefert keine Aussage über die Faktoren einer zusammengesetzten Zahl.

Abb. 1. Illustration zur Monte-Carlo-Bestimmung von Pi.
Abb. 1. Illustration zur Monte-Carlo-Bestimmung von Pi. (Bild: gemeinfrei / CC0)

Der Monte-Carlo-Algorithmus lässt sich zur Bestimmung der Kreiszahl Pi heranziehen. Dazu sind die Wahl zufälliger Punkte auf der Kreisfläche und eine sehr komplexe Formel notwendig (siehe Abb. 1). Sie ergibt das Flächenintegral einer Viertelkreisfläche. Aus diesem ergibt sich das Verhältnis von Fläche, Durchmesser und Umfang.

Im Einsatzbereich des Hochleistungsrechnens, das auf massivem Multiprocessing in Parallelverarbeitung über tausende von Prozessorkernen und Rechnerknoten hinweg beruht, lassen sich probabilistische Lösungsverfahren wie der MC-Algorithmus ausnutzen. Zahlreiche Supercomputer in der Top-500-Liste arbeiten deshalb mit Grafikprozessoren (GPU), die für die Parallelverarbeitung optimiert sind.

Monte-Carlo-Simulation

Abb. 2. Numerische Integration mit dem Monte-Carlo-Algorithmus. Neue Punkte werden dunkelblau dargestellt, alte hingegen hellblau. Die Punkte bzw. Knoten werden einheitlich über das Integrationsintervall verteilt. Der Wert des Integrals tendiert zu 3,32.
Abb. 2. Numerische Integration mit dem Monte-Carlo-Algorithmus. Neue Punkte werden dunkelblau dargestellt, alte hingegen hellblau. Die Punkte bzw. Knoten werden einheitlich über das Integrationsintervall verteilt. Der Wert des Integrals tendiert zu 3,32. (Bild: Thomas Steiner / CC BY-SA 3.0)

Eine Monte-Carlo-Simulation oder Monte-Carlo-Studie, auch MC-Simulation genannt, ist ein Verfahren aus der Stochastik, bei dem eine sehr große Zahl gleichartiger Zufallsexperimente die Basis darstellt. Auch hier soll die Wahrscheinlichkeitstheorie helfen, aufwendig lösbare Probleme zu beantworten, am denen sich Analyse-Methoden die Zähne ausbeißen würden.

Als Grundlage ist vor allem das Gesetz der großen Zahlen zu sehen. Die Zufallsexperimente können entweder – etwa durch Würfeln – real durchgeführt werden oder in Computerberechnungen. Zur Simulation des Zufalls werden scheinbar zufällig gewählte Zahlen herangezogen und mittels geeigneter Algorithmen wie etwa dem MC-Algorithmus berechnet.

Zu den Anwendungen der MC-Simulation gehören das oben angeführte Beispiel der Bestimmung der Zahl Pi. Die Ermittlung von Verteilungen ist ein eminent wichtiger Bereich in der modernen Wirtschaft, beispielsweise in Werbung, Logistik oder Finanzen. Es lassen sich durch Simulation Zufallsvariablen und Korrelationskoeffizienten ermitteln, die in ihrer Gesamtheit Eingang in eine empirische Verteilungsfunktion finden. Mit dieser Funktion hat man ein alternatives Mittel an der Hand, um Schätzungen für Erwartungswerte vornehmen zu können. Man ist nicht mehr auf das arithmetische Mittel angewiesen und kann zudem die Parameter, die eine Verteilung beeinflussen, schätzen.

Nachbildung komplexer Prozesse

Diese Simulationen helfen bei der Nachbildung komplexer Prozesse wie etwa im Wetter oder im Klima, die sich nicht direkt analysieren lassen. Auch Produktionsprozesse in einem Fertigungsunternehmen sind simulierbar, um Engpässe und Opportunitäten in der Produktion aufzudecken. In der Immobilienwirtschaft lassen sich zwecks Wertermittlung eines Objekts Ableitungen aus bisherigen Bewertungen vornehmen.

Auch an der Börse spielen Simulationen eine zunehmende Rolle, denn dort nimmt die Rechenkapazität ebenso zu wie die Übertragungsgeschwindigkeit der Netzwerke. Wenn beispielsweise keine analytische Formel für die Bewertung eines Finanzproduktes bekannt ist, lassen sich durch MC-Simulation geeignete Verteilungsannahmen der relevanten Zufallsgrößen finden und auf einfache Art komplexe Finanzkontrakte bepreisen. Das ist ungefähr so, als würde man ein Karnickel aus einem Hut zaubern, in den man zuvor nur etwas Feenstaub (die MC-Simulation) gestreut hat.

In letzter Zeit haben besonders die Physik und das darauf basierende Engineering von den Möglichkeiten der MC-Simulation profitiert. Wohin wird sich beispielsweise ein Regentropfen, der auf die Erde fällt, weiterbewegen? Er wird zufällig mit anderen Tropfen gleicher Größe in gleichartiger Umgebung kollidieren. Wird er dabei zerfallen oder sich mit anderen Tröpfchen vereinigen?

Nach der Simulation mehrerer konkreter Tropfen sind Aussagen über die durchschnittliche Tropfengröße möglich oder auch zu Temperatur und Tröpfchendichte, bei denen Schnee oder Hagel entstehen. Das Phänomen der Tröpfchen ist von großer Bedeutung bei der Konstruktion von Einspritzpumpen in Verbrennungsmotoren. An der Universität Stuttgart ist es dadurch gelungen, den Benzinverbrauch eines Verbrennungsmotors um einen zweistelligen Prozentsatz zu senken. Am Höchstleistungsrechenzentrum Stuttgart (HLRS) wird auch in einer Art Rundum-Kino der Zerfall eines Treibstoff-Tropfens als Simulation gezeigt, natürlich in extremer „Zeitlupe“ – ein faszinierender Anblick.

Das Problem des Handlungsreisenden und seine praktischen Anwendungen

Grundlagen Statistik & Algorithmen, Teil 1

Das Problem des Handlungsreisenden und seine praktischen Anwendungen

18.06.18 - Ob beim Design von künstlichen Neuronalen Netzwerken fürs Deep Learning, in der Logistik oder beim Layout von Leiterplatten – überall stößt man auf das mathematisch lösbare Problem des Handlungsreisenden: Wie lässt sich eine Tour mit mehreren Stationen auf dem kürzesten Weg und mit dem geringsten Aufwand bewältigen? lesen

So verfeinert das Bayes-Theorem Spam-Filter – und mehr

Grundlagen Statistik & Algorithmen, Teil 2

So verfeinert das Bayes-Theorem Spam-Filter – und mehr

25.06.18 - Mithilfe des Satzes von Bayes lassen sich Parameter schätzen und Hypothesen induktiv testen. In einem Spamfilter können so wahrscheinliche Spam-Mails ermittelt werden. Und aus den Symptomen, die bei einem bekannten Test auftreten, lassen sich wahrscheinliche Krankheitsursachen aufspüren. Der Satz von Bayes, der bedingte Wahrscheinlichkeiten beschreibt, ist also ein nahezu universell nutzbares Werkzeug der Statistik. lesen

Speed für Mustererkennung mit dem Rete-Algorithmus

Grundlagen Statistik & Algorithmen, Teil 3

Speed für Mustererkennung mit dem Rete-Algorithmus

02.07.18 - Geschäftsregeln halten zahlreiche Unternehmensprozesse am Laufen, deshalb können sie mitunter sehr umfangreich werden. Der Umfang macht ihre Ausführung zeitaufwendig, weshalb jede Methode, sie zu beschleunigen, willkommen ist. Der Rete-Algorithmus beschleunigte 1979 die damals bestehenden Systeme für die Verarbeitung von Business Rules um den Faktor 3.000. Er ist bis heute die Grundlage zahlreicher Expertensysteme, etwa in der Mustererkennung. lesen

Kommentare werden geladen....

Kommentar zu diesem Artikel abgeben

Der Kommentar wird durch einen Redakteur geprüft und in Kürze freigeschaltet.

Anonym mitdiskutieren oder einloggen Anmelden

Avatar
Zur Wahrung unserer Interessen speichern wir zusätzlich zu den o.g. Informationen die IP-Adresse. Dies dient ausschließlich dem Zweck, dass Sie als Urheber des Kommentars identifiziert werden können. Rechtliche Grundlage ist die Wahrung berechtigter Interessen gem. Art 6 Abs 1 lit. f) DSGVO.
  1. Avatar
    Avatar
    Bearbeitet von am
    Bearbeitet von am
    1. Avatar
      Avatar
      Bearbeitet von am
      Bearbeitet von am

Kommentare werden geladen....

Kommentar melden

Melden Sie diesen Kommentar, wenn dieser nicht den Richtlinien entspricht.

Kommentar Freigeben

Der untenstehende Text wird an den Kommentator gesendet, falls dieser eine Email-hinterlegt hat.

Freigabe entfernen

Der untenstehende Text wird an den Kommentator gesendet, falls dieser eine Email-hinterlegt hat.

copyright

Dieser Beitrag ist urheberrechtlich geschützt. Sie wollen ihn für Ihre Zwecke verwenden? Infos finden Sie unter www.mycontentfactory.de (ID: 45415245 / Analytics)