¿Por qué el muestreo aleatorio de Monte Carlo en lugar del muestreo uniforme?

8

¿Por qué es tan común usar ubicaciones de muestra aleatorias monte carlo, en lugar de un muestreo uniforme?

Supongo que tomar muestras aleatorias ofrece algún beneficio, pero no sé cuáles podrían ser.

¿Alguien puede explicar la ventaja de las ubicaciones de muestras aleatorias sobre las ubicaciones de muestras uniformes?

Alan Wolfe
fuente
Por lo general, para evitar obtener patrones uniformes en todas partes, si está utilizando muestras uniformes igualmente espaciadas, obtendrá efectos de patrón de muaré a medida que algunos píxeles golpean y fallan características en un intervalo regular. Idealmente, se debería utilizar algún tipo de muestreo importante para sesgar las direcciones de muestreo.
PaulHK
Recientemente leí que tanto el muestreo estratificado como las secuencias de baja discrepancia (como halton, sobol, etc.) son un punto intermedio entre el muestreo aleatorio (que crea ruido) y el muestreo uniforme (que crea aliasing).
Alan Wolfe

Respuestas:

7

Las ubicaciones de muestra con un patrón uniforme crearán alias en la salida, siempre que haya características geométricas de tamaño comparable o menor que la cuadrícula de muestreo. Esa es la razón por la que existen "jaggies": porque las imágenes están hechas de una cuadrícula de píxeles cuadrados uniforme, y cuando se renderiza (por ejemplo) una línea en ángulo sin suavizado, cruza filas / columnas de píxeles a intervalos regulares, creando un patrón regular de artefactos de escalera en la imagen resultante.

El supermuestreo en una cuadrícula uniforme más fina mejorará las cosas, pero la imagen seguirá teniendo artefactos similares, pero no tanto. Puede ver esto con MSAA, como en esta imagen de comparación de una presentación de NVIDIA sobre antialiasing temporal:

comparación de no AA, MSAA de cuadrícula uniforme y AA temporal

La imagen 8x MSAA (que no es del todo una cuadrícula pero aún tiene un patrón repetitivo) todavía tiene irregularidades, aunque son irregularidades con suavizado. Compare con el resultado TXAA, que tiene un recuento de muestras efectivo más alto (debido a la reutilización temporal) y utiliza un filtro gaussiano en lugar de un cuadro para acumular las muestras.

Por otro lado, el muestreo aleatorio produce ruido en lugar de alias. No hay patrón para las ubicaciones de muestra, por lo que no hay patrón para los errores resultantes. Tanto el alias como el ruido son errores debido a que no hay suficientes muestras para formar una imagen limpia, pero podría decirse que el ruido es el artefacto menos objetable visualmente.

Por otra parte, el muestreo perfectamente al azar (en el sentido de variables aleatorias iid ) tiende a exhibir un cierto nivel de formación de grumos. Por pura casualidad, algunas áreas en el dominio tendrán grupos de muestras más densos que el promedio, y otras áreas carecerán de muestras; esas áreas estarán, respectivamente, sobrerrepresentadas y subrepresentadas en la estimación resultante.

La tasa de convergencia del proceso de Monte Carlo a menudo puede mejorarse mediante el uso de elementos como muestreo estratificado , secuencias de baja discrepancia o ruido azul . Estas son todas las estrategias para generar muestras "desagrupadas" que se espacian un poco más uniformemente que las muestras iid, pero sin crear ningún patrón regular que pueda generar alias.

Nathan Reed
fuente
Ah Y el ruido azul evita el agrupamiento al tener menos datos de baja frecuencia en el patrón de muestreo.
Alan Wolfe
6

Los métodos de Monte Carlo se basan en la ley de los grandes números , que establece que el promedio de un evento aleatorio repetido una gran cantidad de veces converge hacia el valor esperado (si lanza una moneda miles de millones, en promedio obtendrá la mitad de cada lado hora). La integración de Monte Carlo utiliza esa ley para evaluar una integral promediando una gran cantidad de muestras aleatorias.

El uso de una distribución uniforme rompería el algoritmo porque la ley en la que se basa ya no se aplicaría.

Julien Guertault
fuente
Sí, pero sobre todo se puede resumir como esto para un problema desconocido, el ramdom es la mejor estrategia. ya que se desconoce la contribución ...
joojaa
@joojaa: oh, me doy cuenta de que he leído la pregunta de manera diferente. Sí, Monte Carlo es una estrategia que funciona cuando la solución analítica es desconocida (aunque una persona de matemáticas probablemente tendría una forma mucho más precisa de plantearla).
Julien Guertault
Dicho de otra manera: incluso si la solución es desconocida, se ha demostrado que Monte Carlo converge hacia ella.
Julien Guertault