Importance Sampling

Importance Sampling

Importance Sampling ist ein Begriff aus dem Bereich der stochastischen Prozesse, der die Technik zur Erzeugung von Stichproben anhand einer Wahrscheinlichkeitsverteilung beschreibt. Importance Sampling ist eine von mehreren Möglichkeiten zur Varianzreduktion, also zur Steigerung der Effizienz von Monte-Carlo-Simulationen.

Grundlagen

Monte-Carlo-Simulationen werden oft benutzt, um Erwartungswerte einer Größe $ \mathcal{A} $ (hier mit $ \left\langle \mathcal{A} \right\rangle $ bezeichnet, sonst – insbesondere in der Mathematik – oft als $ \operatorname{E}(\mathcal{A}) $ dargestellt),

$ \left\langle \mathcal{A} \right\rangle = \sum_{x \in \Omega} P(x) \, \mathcal{A}(x), $

zu berechnen, wobei $ P(x) $ ein normiertes statistisches Gewicht wie beispielsweise ein Boltzmanngewicht ist. $ \mathcal{A}(x) $ ist der Wert der Größe $ \mathcal{A} $ im Zustand $ x $. Die Summation (oder Integration) läuft dabei über einen Raum $ \Omega $, z. B. den Phasenraum der Teilchen im System. Da dieser Phasenraum im Allgemeinen sehr hochdimensional ist, kann die Summe bzw. das Integral im Allgemeinen nicht berechnet werden. Statt den wahren Erwartungswert zu berechnen, berechnet man einen Schätzer $ \overline{\mathcal{A}} $ mithilfe einer Zufallsstichprobe S, die den Umfang $ N $ hat.

Für den einfachsten Fall (Simple Sampling) gleichverteilt zufällig ausgewählter Zustände ergibt sich für den Mittelwert:

$ \overline{\mathcal{A}} = \frac{\sum_{x \in S} P(x) \, \mathcal{A}(x)}{\sum_{x \in S} P(x)}, $

wobei $ P(x) $ (beispielsweise proportional zu $ \exp(-\beta E(x)) $) sowie $ \mathcal{A}(x) $ nach der zufälligen Wahl von x berechnet werden. Für eine große Stichprobe nähert sich der Schätzer dem Mittelwert:

$ \lim_{N \to \infty} \overline{\mathcal{A}} = \left\langle \mathcal{A} \right\rangle $

Diese Methode ist meistens nicht sehr effektiv, da oft nur wenige relevante Zustände in die Mittelwertbildung eingehen. Um dieses Problem zu umgehen und so die Standardabweichung des gemessenen Mittelwertes bei gleichem Stichprobenumfang zu reduzieren, versucht man Zustände mit einem größeren Gewicht häufiger in die Mittelwertbildung eingehen zu lassen als Zustände mit einem geringeren Gewicht: Der obigen Schätzer des Simple Sampling kann durch Erweitern mit $ 1=W(x)/W(x) $ auch wie folgt ausgedrückt werden:

$ \overline{\mathcal{A}} = \frac{\sum_{x \in S} P(x)/W(x) \, \mathcal{A}(x) W(x)}{\sum_{x \in S} P(x)/W(x) W(x)}. $

Werden Zustände $ x $ mit der Wahrscheinlichkeit $ W(x) $ erzeugt (Importance Sampling), so berechnet sich der Mittelwert in der Folge einfach mithilfe von

$ \overline{\mathcal{A}} = \frac{\sum_{x \in S} P(x)/ W(x) \mathcal{A}(x)}{\sum_{x \in S} P(x) \,/\, W(x)}. $

Beispiel

Werden die Systemzustände z. B. willkürlich mit einer Wahrscheinlichkeit $ W(x) $ proportional zu $ P(x) $ erzeugt (das ist gerade die Metropoliswahl), so ergibt sich

$ \overline{\mathcal{A}} = \frac{1}{N}\sum_{x \in S} \mathcal{A}(x). $

Gerade, dass hier nur die Proportionalität $ W(x) \propto P(x) $ erforderlich ist, ist ein Vorteil der Methode.

Um Importance Sampling in der Praxis zu erreichen, geht man von einer Startkonfiguration aus und erzeugt mithilfe des Metropolisalgorithmus eine Markow-Kette aus Systemzuständen.

Neben der Metropoliswahl für die Sampling-Wahrscheinlichkeit $ W(x) $ gibt es weitere Möglichkeiten. Z. B. kann mit der Wahl $ W(x)=1/D(E(x)) $, wobei $ D(E(x)) $ diejenige Zustandsdichte der Energie ist, die dem Zustand $ x $ zugeordnet ist, das multikanonische Ensemble simuliert werden.

Literatur

  • W. K. Hastings: Monte Carlo Sampling Methods Using Markov Chains and Their Applications. In: Biometrika. Band 57, 1970, S. 97–109.
  • R. Srinivasan: Importance sampling – Applications in communications and detection. Springer-Verlag, Berlin 2002, ISBN 978-3-540-43420-7.
  • Thomas Müller-Gronbach, Erich Novak, Klaus Ritter: Monte Carlo-Algorithmen. Springer-Verlag, Berlin 2012, ISBN 978-3-540-89140-6, Abschnitt 5.4, S. 155–165.

Diese Artikel könnten dir auch gefallen



Die letzten News


13.01.2021
Schnellere und stabilere Quantenkommunikation
Einer internationalen Forschungsgruppe ist es gelungen, hochdimensionale Verschränkungen in Systemen aus zwei Photonen herzustellen und zu überprüfen. Damit lässt sich schneller und sicherer kommunizieren, wie die Wissenschaftlerinnen und Wissenschaftler zeigen.
12.01.2021
Elektrisch schaltbares Qubit ermöglicht Wechsel zwischen schnellem Rechnen und Speichern
Quantencomputer benötigen zum Rechnen Qubits als elementare Bausteine, die Informationen verarbeiten und speichern.
12.01.2021
ALMA beobachtet, wie eine weit entfernte kollidierende Galaxie erlischt
Galaxien vergehen, wenn sie aufhören, Sterne zu bilden.
11.01.2021
Umgekehrte Fluoreszenz
Entdeckung von Fluoreszenzmolekülen, die unter normalem Tageslicht ultraviolettes Licht aussenden.
11.01.2021
Weyl-Punkten auf der Spur
Ein Material, das leitet und isoliert – gibt es das? Ja, Forschende haben erstmals 2005 sogenannte topologische Isolatoren beschrieben, die im Inneren Stromdurchfluss verhindern, dafür aber an der Oberfläche äußerst leitfähig sind.
11.01.2021
MOONRISE: Schritt für Schritt zur Siedlung aus Mondstaub
Als Bausteine sind sie noch nicht nutzbar – aber die mit dem Laser aufgeschmolzenen Bahnen sind ein erster Schritt zu 3D-gedruckten Gebäuden, Landeplätzen und Straßen aus Mondstaub.
11.01.2021
Konstanz von Naturkonstanten in Raum und Zeit untermauert
Moderne Stringtheorien stellen die Konstanz von Naturkonstanten infrage. Vergleiche von hochgenauen Atomuhren bestätigen das jedoch nicht, obwohl die Ergebnisse früherer Experimente bis zu 20-fach verbessert werden konnten.
08.01.2021
Weder flüssig noch fest
E
08.01.2021
Mit quantenlimitierter Genauigkeit die Auflösungsgrenze überwinden
Wissenschaftlern der Universität Paderborn ist es gelungen, eine neue Methode zur Abstandsmessung für Systeme wie GPS zu entwickeln, deren Ergebnisse so präzise wie nie zuvor sind.
25.12.2020
Wie sich Sterne in nahe gelegenen Galaxien bilden
Wie Sterne genau entstehen, ist nach wie vor eines der grossen Rätsel der Astrophysik.
25.12.2020
Kartierung eines kurzlebigen Atoms
Ein internationales Team aus Deutschland, Schweden, Russland und den USA unter der Leitung von Wissenschaftern des European XFEL hat Ergebnisse eines Experiments veröffentlicht, das neue Möglichkeiten zur Untersuchung von Übergangszuständen in Atomen und Molekülen eröffnet.
25.12.2020
Skyrmionen – Grundlage für eine vollkommen neue Computerarchitektur?
Skyrmionen sind magnetische Objekte, von denen sich Forscher weltweit versprechen, mit ihnen die neuen Informationseinheiten für die Datenspeicher und Computerarchitektur der Zukunft gefunden zu haben.
25.12.2020
Mysterien in den Wolken: Große Tröpfchen begünstigen die Bildung kleinerer
Wissenschaftler des Max-Planck-Instituts für Dynamik und Selbstorganisation (MPIDS) berichten die über ihre neuen Erkenntnisse, wie ausfallende große Regentropfen und Eispartikel das Wachstum von Aerosolen begünstigen können, um neue Kondensationskerne oder Eiskeimteilchen in Wolken zu erzeugen.
25.12.2020
Kollidierende Sterne offenbaren grundlegende Eigenschaften von Materie und Raumzeit
Ein internationales Wissenschaftsteam um den Astrophysikprofessor Tim Dietrich von der Universität Potsdam schaffte den Durchbruch bei der Größenbestimmung eines typischen Neutronensterns und der Messung der Ausdehnung des Universums.
25.12.2020
Endgültige Ergebnisse und Abschied vom GERDA-Experiment
Die Zeit des GERDA-Experiments zum Nachweis des neutrinolosen doppelten Betazerfalls geht zu Ende.
18.12.2020
Galaxienhaufen, gefangen im kosmischen Netz
Mehr als die Hälfte der Materie in unserem Universum entzog sich bislang unserem Blick.
18.12.2020
Zwei planetenähnliche Objekte, die wie Sterne geboren wurden
Ein internationales Forschungsteam unter der Leitung der Universität Bern hat ein exotisches System entdeckt, das aus zwei jungen planetenähnlichen Objekten besteht, die sich in sehr grosser Entfernung umkreisen.
16.12.2020
Neuen Quantenstrukturen auf der Spur
Der technologische Fortschritt unserer modernen Informationsgesellschaft basiert auf neuartigen Quantenmaterialien.
16.12.2020
Das Protonenrätsel geht in die nächste Runde
Physiker am Max-Planck-Institut für Quantenoptik haben die Quantenmechanik mit Hilfe der Wasserstoffspektroskopie einem neuen bis dato unerreichten Test unterzogen und sind der Lösung des bekannten Rätsels um den Protonenladungsradius damit ein gutes Stück nähergekommen.
03.12.2020
Laborexperimente könnten Rätsel um Mars-Mond Phobos lösen
Was lässt die Oberfläche des Mars-Monds Phobos verwittern? Ergebnisse der TU Wien liefern wichtige Erkenntnisse, bald soll eine Weltraummission Gesteinsproben nehmen.
26.11.2020
Gesund bis zum Mars
Tübinger Wissenschaftlerin untersucht mit internationalem Weltraumforschungsteam die Einflüsse der Raumfahrt auf den menschlichen Körper.
26.11.2020
Stammbaum der Milchstraße
Galaxien wie die Milchstraße sind durch das Verschmelzen von kleineren Vorgängergalaxien entstanden.
26.11.2020
Nanodiamanten vollständig integriert kontrollieren
Physikerinnen und Physikern ist es gelungen, Nanodiamanten vollständig in nanophotonischen Schaltkreisen zu integrieren und gleichzeitig mehrere dieser Nanodiamanten optisch zu adressieren. Die Studie schafft Grundlagen für zukünftige Anwendungen im Bereich der Quantensensorik oder Quanteninformationsverarbeitung.
26.11.2020
Der Sonne ein Stück näher
Der Borexino-Kollaboration, an der auch Wissenschaftler der TU Dresden beteiligt sind, ist es nach über 80 Jahren gelungen, den Bethe-Weizsäcker-Zyklus experimentell zu bestätigen.
22.11.2020
Entfernungen von Sternen
1838 gewann Friedrich Wilhelm Bessel das Wettrennen um die Messung der ersten Entfernung zu einem anderen Stern mit Hilfe der trigonometrischen Parallaxe - und legte damit die erste Entfernungsskala des Universums fest.