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

Часть серии статей о
Байесовская статистика
Апостериор = Вероятность × Априор ÷ Доказательства
Фон
Байесовский вывод Байесовская вероятность Теорема Байеса Теорема Бернштейна–фон Мизеса Согласованность Теорема Кокса Правление Кромвеля Принцип правдоподобия Принцип безразличия Принцип максимальной энтропии
Модельное строительство
Сопряженный априор Линейная регрессия Эмпирический Байес Иерархическая модель
Апостериорное приближение
Марковская цепь Монте-Карло Приближение Лапласа Интегрированные вложенные приближения Лапласа Вариационный вывод Приблизительное байесовское вычисление
Оценщики
Байесовская оценка Достоверный интервал Максимальная апостериорная оценка
Приближение доказательств
Нижняя граница доказательств Nested sampling
Model evaluation
Bayes factor (Schwarz criterion) Model averaging Posterior predictive
Mathematics portal
v t e

Алгоритм вложенной выборки — это вычислительный подход к задачам байесовской статистики по сравнению моделей и генерации выборок из апостериорных распределений. Он был разработан в 2004 году физиком Джоном Скиллингом. ^[1]

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

${\displaystyle {\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}}}$

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

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

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

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

Начать с точек, выбранных из предшествующих. для выполнения  % Количество итераций j выбирается наугад. текущие значения правдоподобия точек ; Сохраните точку с наименьшим правдоподобием как точку выборки с весом .${\displaystyle N}$${\displaystyle \theta _{1},\ldots ,\theta _{N}}$ ${\displaystyle i=1}$${\displaystyle j}$ ${\displaystyle L_{i}:=\min(}$${\displaystyle )}$${\displaystyle X_{i}:=\exp(-i/N);}$ ${\displaystyle w_{i}:=X_{i-1}-X_{i}}$ ${\displaystyle Z:=Z+L_{i}\cdot w_{i};}$${\displaystyle w_{i}}$ Обновите точку с наименьшим правдоподобием с помощью некоторых шагов Монте-Карло цепи Маркова в соответствии с априорными данными, принимая только те шаги, которые сохранить вероятность выше . конец возврата ;${\displaystyle L_{i}}$ ${\displaystyle Z}$

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

${\displaystyle {\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}}}$

В пределе эта оценка имеет положительное смещение порядка ^[4] , которое можно устранить, используя вместо в приведенном выше алгоритме.${\displaystyle j\to \infty }$${\displaystyle 1/N}$${\displaystyle (1-1/N)}$${\displaystyle \exp(-1/N)}$

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

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

Собственные примеры кода Скиллинга (например, один из Sivia and Skilling (2006), ^[6] доступны на веб-сайте Скиллинга) выбирают случайную существующую точку и выбирают близлежащую точку, выбранную на случайном расстоянии от существующей точки; если вероятность выше, то точка принимается, в противном случае она отклоняется, и процесс повторяется. Мукерджи и др. (2006) ^[7] обнаружили более высокие показатели принятия, выбирая точки случайным образом внутри эллипсоида, нарисованного вокруг существующих точек; эта идея была усовершенствована в алгоритме MultiNest ^[8] , который лучше обрабатывает мультимодальные апостериорные распределения, группируя точки в контуры вероятности и рисуя эллипсоид для каждого контура.

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

• Простые примеры на языках C , R или Python можно найти на сайте Джона Скиллинга.
• Порт вышеприведенных простых кодов на Haskell доступен на Hackage.
• Пример на языке R, изначально разработанный для подгонки спектров , описан на сайте Бояна Николича и доступен на GitHub.
• NestedSampler является частью набора инструментов Python BayesicFitting ^[9] для подгонки общей модели и расчета доказательств. Он доступен на GitHub.
• Реализация на языке C++ под названием DIAMONDS находится на GitHub.
• Высокомодульный пример параллельного решения на Python для статистической физики и физики конденсированного состояния находится на GitHub.
• pymatnest — это пакет, предназначенный для исследования энергетического ландшафта различных материалов, расчета термодинамических переменных при произвольных температурах и определения фазовых переходов . Находится на GitHub.
• Пакет программного обеспечения MultiNest способен выполнять вложенную выборку на основе многомодальных апостериорных распределений. ^{[8] [10]} Он имеет интерфейсы для входных данных C++, Fortran и Python и доступен на GitHub.
• PolyChord — еще один программный пакет для вложенной выборки, доступный на GitHub. Вычислительная эффективность PolyChord лучше масштабируется с увеличением числа параметров, чем MultiNest, что означает, что PolyChord может быть более эффективным для многомерных задач. ^[11] Он имеет интерфейсы для функций правдоподобия, написанных на Python, Fortran, C или C++.
• NestedSamplers.jl, пакет Julia для реализации алгоритмов вложенной выборки с одним и несколькими эллипсоидами, находится на GitHub.
• Korali — это высокопроизводительная среда для количественной оценки неопределенности, оптимизации и глубокого обучения с подкреплением, которая также реализует вложенную выборку.

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

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

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

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

Динамическая вложенная выборка применялась к различным научным проблемам, включая анализ гравитационных волн ^[17] , картографирование расстояний в космосе ^{[18] и обнаружение экзопланет [19]} .

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