Почему случайная выборка Монте-Карло вместо равномерной выборки?

8

Почему так часто используют случайные выборки Монте-Карло вместо равномерной выборки?

Я предполагаю, что взятие рандомизированных образцов дает некоторую выгоду, но я не знаю, чем они могут быть.

Может ли кто-нибудь объяснить преимущество случайных выборок по сравнению с однородными выборками?

Алан Вульф
источник
Обычно, чтобы избежать повсеместного получения однородных шаблонов, если вы используете равномерно распределенные сэмплы с одинаковым расстоянием, то вы получите эффект муарового шаблона, поскольку некоторые пиксели будут попадать и пропускать объекты с регулярным интервалом. В идеале должна использоваться какая-то важная выборка для смещения направлений выборки.
PaulHK
Недавно я читал, что и стратифицированные выборки, и последовательности с низкой дискретностью (такие как halton, sobol и т. Д.) Являются средним звеном между случайной выборкой (которая создает шум) и равномерной выборкой (которая создает псевдонимы).
Алан Вулф

Ответы:

7

Места выборки с равномерным рисунком создадут сглаживание в выходных данных, когда есть геометрические элементы размера, сопоставимого или меньшего, чем сетка выборки. Вот почему существуют «зазубрины»: поскольку изображения состоят из равномерной квадратной сетки пикселей, и когда вы рендерите (например) угловую линию без сглаживания, она через равные промежутки пересекает строки / столбцы пикселей, создавая регулярный шаблон артефакты ступеньки в результирующем изображении.

Суперсэмплирование в более тонкой однородной сетке улучшит ситуацию, но на изображении все равно будут присутствовать похожие артефакты - только не так плохо. Вы можете увидеть это с MSAA, как на этом изображении сравнения из презентации NVIDIA о временном сглаживании:

сравнение без АА, MSAA с равномерной сеткой и временного АА

В 8-кратном MSAA-изображении (которое не является сеткой, но все еще имеет повторяющийся рисунок) все еще явно присутствуют неровности, хотя это сглаженные неровности. Сравните с результатом TXAA, который имеет более высокое эффективное число выборок (из-за временного повторного использования) и использует гауссовский, а не блочный фильтр для накопления выборок.

С другой стороны, случайная выборка производит шум вместо наложения. Нет шаблона для местоположений выборки, поэтому нет шаблона для возникающих ошибок. И псевдоним, и шум являются ошибками из-за отсутствия достаточного количества выборок для формирования чистого изображения, но, вероятно, шум является менее визуально нежелательным артефактом.

С другой другой стороны, совершенно случайная выборка (в том смысле , одинаково распределенных случайных величин ) , как правило, демонстрирует определенный уровень слипания. Совершенно случайно, некоторые области в домене будут иметь более плотные, чем в среднем, скопления образцов, а другие области будут отсутствовать в образцах; эти области будут, соответственно, перепредставлены и недопредставлены в итоговой оценке.

Скорость сходимости процесса Монте-Карло часто можно улучшить, используя такие вещи, как стратифицированная выборка , последовательности с низким расхождением или синий шум . Это все стратегии для генерации «сгруппированных» сэмплов, которые расположены немного более равномерно, чем сэмплы iid, но без создания каких-либо регулярных паттернов, которые могут привести к наложению.

Натан Рид
источник
Ах. А синий шум предотвращает слипание благодаря наличию менее низкочастотных данных в образце выборки.
Алан Вульф
6

Методы Монте-Карло основаны на законе больших чисел , который гласит, что среднее случайного события, повторенное большое количество раз, сходится к ожидаемому значению (если вы подбрасываете монету миллион раз, в среднем вы получите каждую сторону, равную половине время). Интеграция Монте-Карло использует этот закон для оценки интеграла путем усреднения большого числа случайных выборок.

Использование равномерного распределения нарушит алгоритм, потому что закон, на котором он основан, больше не будет применяться.

Жюльен Геро
источник
Да, но в основном это может быть суммировано как это для неизвестной проблемы, ramdom - лучшая стратегия. поскольку вклад неизвестен ...
Джуджаа
@joojaa: о, я понимаю тебя, и я прочитал вопрос по-другому. Да, Монте-Карло - это стратегия, которая работает, когда аналитическое решение неизвестно (хотя у математика, вероятно, был бы гораздо более точный способ выразить это).
Жюльен Геро,
Сказано иначе: даже если решение неизвестно, доказано, что Монте-Карло сходится к нему.
Жюльен Герто