Вложенный алгоритм выборки

Алгоритм вложенной выборки представляет собой вычислительный подход к решению задач байесовской статистики , заключающийся в сравнении моделей и генерации выборок на основе апостериорных распределений. Его разработал в 2004 году физик Джон Скиллинг.

Фон

Теорему Байеса можно применить к паре конкурирующих моделей. $M_{1}$ и $M_{2}$ для данных $D$, одно из которых может быть истинным (хотя какое именно неизвестно), но оба не могут быть истинными одновременно. Апостериорная вероятность для $M_{1}$ может быть рассчитано как:

${\begin{aligned}P(M_{1}\mid D)&={\frac {P(D\mid M_{1})P(M_{1})}{P(D)}}\\&={\frac {P(D\mid M_{1})P(M_{1})}{P(D\mid M_{1})P(M_{1})+P(D\mid M_{2})P(M_{2})}}\\&={\frac {1}{1+{\frac {P(D\mid M_{2})}{P(D\mid M_{1})}}{\frac {P(M_{2})}{P(M_{1})}}}}\end{aligned}}$

Априорные вероятности $M_{1}$ и $M_{2}$ уже известны, так как выбраны исследователем заранее. Однако оставшийся байесовский фактор $P(D\mid M_{2})/P(D\mid M_{1})$ оценить не так просто, поскольку, как правило, это требует маргинализации мешающих параметров. В целом, $M_{1}$ имеет набор параметров, которые можно сгруппировать и назвать $\theta$, и $M_{2}$ имеет свой вектор параметров, который может иметь разную размерность, но все равно называется $\theta$. Маргинализация $M_{1}$ является

$P(D\mid M_{1})=\int d\theta \,P(D\mid \theta ,M_{1})P(\theta \mid M_{1})$

и аналогично для $M_{2}$. Этот интеграл часто аналитически неразрешим, и в этих случаях необходимо использовать численный алгоритм для поиска приближения. Алгоритм вложенной выборки был разработан Джоном Скиллингом специально для аппроксимации этих интегралов маргинализации, и он имеет дополнительное преимущество, заключающееся в создании выборок из апостериорного распределения. $P(\theta \mid D,M_{1})$. Это альтернатива методам из байесовской литературы. такие как выборка мостов и выборка защитной важности.

Вот простая версия алгоритма вложенной выборки, за которой следует описание того, как он вычисляет предельную плотность вероятности. $Z=P(D\mid M)$ где $M$ является $M_{1}$ или $M_{2}$:

Start with $N$ points $\theta _{1},\ldots ,\theta _{N}$ sampled from prior.
for $i=1$ to $j$ do        % The number of iterations j is chosen by guesswork.
    $L_{i}:=\min($current likelihood values of the points$)$;
    $X_{i}:=\exp(-i/N);$
    $w_{i}:=X_{i-1}-X_{i}$
    $Z:=Z+L_{i}\cdot w_{i};$
    Save the point with least likelihood as a sample point with weight $w_{i}$.
    Update the point with least likelihood with some Markov chain Monte Carlo steps according to the prior, accepting only steps that
    keep the likelihood above $L_{i}$.
end
return $Z$;

На каждой итерации $X_{i}$ - это оценка количества предшествующей массы, покрытой гиперобъемом в пространстве параметров всех точек с вероятностью, превышающей $\theta _{i}$. Весовой фактор $w_{i}$ это оценка количества априорной массы, которая находится между двумя вложенными гиперповерхностями. $\{\theta \mid P(D\mid \theta ,M)=P(D\mid \theta _{i-1},M)\}$ и $\{\theta \mid P(D\mid \theta ,M)=P(D\mid \theta _{i},M)\}$. Этап обновления $Z:=Z+L_{i}w_{i}$ вычисляет сумму по $i$ из $L_{i}w_{i}$ численно аппроксимировать интеграл

${\begin{aligned}P(D\mid M)&=\int P(D\mid \theta ,M)P(\theta \mid M)\,d\theta \\&=\int P(D\mid \theta ,M)\,dP(\theta \mid M)\end{aligned}}$

В пределе $j\to \infty$, эта оценка имеет положительное смещение порядка $1/N$ который можно удалить с помощью $(1-1/N)$ вместо $\exp(-1/N)$ в приведенном выше алгоритме.

Идея состоит в том, чтобы разделить диапазон $f(\theta )=P(D\mid \theta ,M)$ и оценим для каждого интервала $[f(\theta _{i-1}),f(\theta _{i})]$, насколько априори вероятно, что случайно выбранный $\theta$ будет соответствовать этому интервалу. Это можно рассматривать как байесовский способ численной реализации интегрирования Лебега .

Реализации

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

• Простые примеры на C , R или Python находятся на веб-сайте Джона Скиллинга.
• Порт Haskell приведенных выше простых кодов находится на Hackage.
• Пример в R, первоначально разработанный для подгонки спектров , описан по адресу и находится на GitHub.
• NestedSampler является частью набора инструментов Python BayesicFitting. для подбора общей модели и расчета доказательств. Это на Гитхабе
• Пример на C++ под названием Diamonds находится на GitHub.
• Высокомодульный параллельный пример Python для статистической физики и физики конденсированного состояния находится на GitHub.
• pymatnest — это пакет Python , предназначенный для изучения энергетического ландшафта различных материалов, расчета термодинамических переменных при произвольных температурах и определения фазовых переходов, который находится на GitHub.
• Программный пакет MultiNest способен выполнять вложенную выборку на мультимодальных апостериорных распределениях. Он имеет интерфейсы для ввода C++, Fortran и Python и доступен на GitHub.
• PolyChord — еще один пакет программного обеспечения для вложенной выборки, доступный на GitHub. Вычислительная эффективность PolyChord лучше масштабируется с увеличением числа параметров, чем MultiNest, а это означает, что PolyChord может быть более эффективным для задач большой размерности.
• NestedSamplers.jl — пакет Julia для реализации одно- и многоэллипсоидальных алгоритмов вложенной выборки, находится на GitHub.
• Korali — это высокопроизводительная среда для количественной оценки неопределенности, оптимизации и глубокого обучения с подкреплением, которая также реализует вложенную выборку.

Приложения

С тех пор, как в 2004 году была предложена вложенная выборка, она стала использоваться во многих аспектах области астрономии . В одной статье предлагалось использовать вложенную выборку для выбора космологической модели и обнаружения объектов, поскольку она «уникально сочетает в себе точность, общую применимость и вычислительную осуществимость». Усовершенствование алгоритма для обработки мультимодальных апостериорных изображений было предложено как средство обнаружения астрономических объектов в существующих наборах данных. Другие применения вложенной выборки находятся в области обновления конечных элементов , где алгоритм используется для выбора оптимальной модели конечных элементов , и это было применено к структурной динамике . Этот метод отбора проб также использовался в области моделирования материалов. Его можно использовать для изучения статистической суммы из статистической механики и получения термодинамических свойств.

Динамическая вложенная выборка

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

Общедоступные пакеты программного обеспечения для динамической вложенной выборки включают:

• dynesty — реализация динамической вложенной выборки на Python, которую можно загрузить с GitHub.
• dyPolyChord: пакет программного обеспечения, который можно использовать с Python, C++ и Fortran, а также с предыдущими дистрибутивами. dyPolyChord доступен на GitHub.

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

См. также

• Сравнение байесовских моделей
• Список алгоритмов