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

Эта статья предоставляет недостаточный контекст для тех, кто не знаком с предметом . Пожалуйста, помогите улучшить статью , предоставив читателю больше контекста . ( Октябрь 2009 г. ) ( узнайте, как и когда удалять это шаблонное сообщение )

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

Задний план

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

${\ displaystyle {\ begin {align} 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{выровнено}}}$

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

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

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

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

Начните с точек , выбранных из предыдущего.for to do  % Количество итераций j выбирается наугад. текущие значения правдоподобия точек ; Сохраните точку с наименьшей вероятностью как точку выборки с весом .${\ Displaystyle Н}$${\ Displaystyle \ тета _ {1}, \ ldots, \ тета _ {N}}$ ${\ Displaystyle я = 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 }$

Реализации

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

• Простые примеры на C , R или Python есть на сайте Джона Скиллинга. ^[6]
• Порт Haskell вышеуказанных простых кодов находится на Hackage . ^[7]
• Пример в R , изначально предназначенный для подгонки спектров , описан в ^[8] и находится на GitHub. ^[9]
• Пример на C++ под названием Diamonds есть на GitHub. ^[10]
• Высокомодульный параллельный пример Python для статистической физики и физики конденсированного состояния находится на GitHub. ^[11]
• pymatnest — это пакет Python , предназначенный для изучения энергетического ландшафта различных материалов, расчета термодинамических переменных при произвольных температурах и обнаружения фазовых переходов . Он доступен на GitHub. ^[12]
• Программный пакет MultiNest способен выполнять вложенную выборку на мультимодальных апостериорных распределениях. ^[13] Он имеет интерфейсы для входных данных C++, Fortran и Python и доступен на GitHub. ^[14]
• PolyChord — еще один программный пакет для вложенных сэмплов, доступный на GitHub. ^[15] Вычислительная эффективность PolyChord лучше масштабируется с увеличением количества параметров, чем MultiNest, что означает, что PolyChord может быть более эффективным для задач с большими размерами. ^[16]
• NestedSamplers.jl — пакет Julia для реализации алгоритмов вложенной выборки с одним и несколькими эллипсоидами — находится на GitHub. ^[17]

Приложения

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

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

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

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

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

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

Смотрите также

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

использованная литература