Warum zufällige Monte-Carlo-Probenahme statt einheitlicher Probenahme?

8

Warum ist es so üblich, monte carlo randomisierte Stichprobenorte anstelle einer einheitlichen Stichprobe zu verwenden?

Ich gehe davon aus, dass die Entnahme randomisierter Stichproben einen gewissen Nutzen bringt, aber ich weiß nicht, was sie sein könnten.

Kann jemand den Vorteil randomisierter Probenorte gegenüber einheitlichen Probenorten erklären?

Alan Wolfe
quelle
Um zu vermeiden, dass überall einheitliche Muster angezeigt werden, erhalten Sie normalerweise Moiré-Mustereffekte, wenn Sie in regelmäßigen Abständen Merkmale treffen und verfehlen, wenn Sie gleichmäßig verteilte Samples mit gleichem Abstand verwenden. Idealerweise sollte eine wichtige Abtastung verwendet werden, um die Abtastrichtungen zu beeinflussen.
PaulHK
Ich habe kürzlich gelesen, dass sowohl geschichtete Stichproben als auch Sequenzen mit geringer Diskrepanz (wie Halton, Sobol usw.) einen Mittelweg zwischen Zufallsstichproben (die Rauschen erzeugen) und einheitlichen Stichproben (die Aliasing erzeugen) darstellen.
Alan Wolfe

Antworten:

7

Stichprobenpositionen mit einem einheitlichen Muster erzeugen ein Aliasing in der Ausgabe, wenn geometrische Merkmale vorhanden sind, deren Größe mit dem Stichprobenraster vergleichbar oder kleiner ist. Das ist der Grund, warum "Zacken" existieren: Weil Bilder aus einem einheitlichen quadratischen Pixelraster bestehen und wenn Sie (zum Beispiel) eine abgewinkelte Linie ohne Antialiasing rendern, kreuzt sie in regelmäßigen Abständen Zeilen / Spalten von Pixeln und erzeugt ein regelmäßiges Muster von Treppenartefakte im resultierenden Bild.

Supersampling in einem feineren, gleichmäßigen Raster verbessert die Dinge, aber das Bild weist immer noch ähnliche Artefakte auf - nur weniger schlecht. Sie können dies mit MSAA sehen, wie in diesem Vergleichsbild aus einer NVIDIA-Präsentation zum zeitlichen Antialiasing:

Vergleich von kein AA, MSAA mit einheitlichem Gitter und zeitlichem AA

Das 8x MSAA-Bild (das kein richtiges Raster ist, aber immer noch ein sich wiederholendes Muster aufweist) enthält immer noch deutlich Zacken, obwohl es sich um Antialias-Zacken handelt. Vergleichen Sie mit dem TXAA-Ergebnis, das sowohl eine höhere effektive Probenanzahl aufweist (aufgrund der zeitlichen Wiederverwendung) als auch einen Gaußschen Filter anstelle eines Boxfilters zum Akkumulieren der Proben verwendet.

Andererseits erzeugt eine zufällige Abtastung Rauschen anstelle von Aliasing. Es gibt kein Muster für die Probenpositionen, also kein Muster für die resultierenden Fehler. Sowohl Aliasing als auch Rauschen sind Fehler, da nicht genügend Samples vorhanden sind, um ein sauberes Bild zu erzeugen. Rauschen ist jedoch wahrscheinlich das weniger visuell störende Artefakt.

Auf der anderen dagegen perfekt Stichproben (im Sinne von iid Zufallsvariablen ) dazu , ein gewisses Maß an Verklumpung zu zeigen. Rein zufällig weisen einige Bereiche in der Domäne überdurchschnittlich dichtere Probenklumpen auf, und andere Bereiche fehlen in den Proben. Diese Bereiche werden in der resultierenden Schätzung jeweils über- bzw. unterrepräsentiert sein.

Die Konvergenzrate des Monte-Carlo-Prozesses kann häufig durch Verwendung von geschichteten Stichproben , Sequenzen mit geringer Diskrepanz oder blauem Rauschen verbessert werden . Dies sind alles Strategien, um "entklumpte" Samples zu generieren, die etwas gleichmäßiger verteilt sind als iid-Samples, ohne jedoch regelmäßige Muster zu erstellen, die zu Aliasing führen könnten.

Nathan Reed
quelle
Ah. Und blaues Rauschen verhindert das Verklumpen, indem es weniger niederfrequente Daten im Abtastmuster enthält.
Alan Wolfe
6

Monte-Carlo-Methoden stützen sich auf das Gesetz der großen Zahlen , das besagt, dass der Durchschnitt eines zufälligen Ereignisses, das viele Male wiederholt wird, gegen den erwarteten Wert konvergiert (wenn Sie eine Münze millionenfach werfen, erhalten Sie im Durchschnitt jede Seite der Hälfte Zeit). Die Monte-Carlo-Integration verwendet dieses Gesetz, um ein Integral durch Mittelung einer großen Anzahl von Zufallsstichproben zu bewerten.

Die Verwendung einer gleichmäßigen Verteilung würde den Algorithmus brechen, da das Gesetz, auf dem er basiert, nicht mehr gelten würde.

Julien Guertault
quelle
Ja, aber meistens kann dies für ein unbekanntes Problem zusammengefasst werden. Ramdom ist die beste Strategie. da Beitrag unbekannt ist ...
joojaa
@joojaa: oh, ich erkenne dich und ich habe die Frage anders gelesen. Ja, Monte Carlo ist eine Strategie, die funktioniert, wenn die analytische Lösung unbekannt ist (obwohl eine mathematische Person wahrscheinlich eine viel präzisere Art hätte, sie auszudrücken).
Julien Guertault
Anders gesagt: Auch wenn die Lösung unbekannt ist, konvergiert Monte Carlo nachweislich darauf zu.
Julien Guertault