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

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

Фон

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

${displaystyle {egin{aligned}P(M_{1}mid D)&={frac {P(Dmid M_{1})P(M_{1})}{P(D)}}&={frac {P(Dmid M_{1})P(M_{1})}{P(Dmid M_{1})P(M_{1})+P(Dmid M_{2})P(M_{2})}}&={frac {1}{1+{frac {P(Dmid M_{2})}{P(Dmid M_{1})}}{frac {P(M_{2})}{P(M_{1})}}}}end{aligned}}}$

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

${displaystyle P(Dmid M_{1})=int d heta ,P(Dmid heta ,M_{1})P( heta mid M_{1})}$

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

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

Начать с ${displaystyle N}$ точки ${displaystyle heta _{1},ldots , heta _{N}}$ взяты из приора.за ${displaystyle i=1}$ к ${displaystyle j}$ делать        % Число итераций 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 heta _{i}}$. Фактор веса ${displaystyle w_{i}}$ это оценка количества предшествующей массы, которая лежит между двумя вложенными гиперповерхностями ${displaystyle { heta mid P(Dmid heta ,M)=P(Dmid heta _{i-1},M)}}$ и ${displaystyle { heta mid P(Dmid heta ,M)=P(Dmid heta _{i},M)}}$. Шаг обновления ${displaystyle Z:=Z+L_{i}w_{i}}$ вычисляет сумму по ${displaystyle i}$ из ${displaystyle L_{i}w_{i}}$ для численной аппроксимации интеграла

${displaystyle {egin{aligned}P(Dmid M)&=int P(Dmid heta ,M)P( heta mid M),d heta &=int P(Dmid heta ,M),dP( heta mid M)end{aligned}}}$

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

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

Реализации

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

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

Приложения

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

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

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

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

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

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

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

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

Рекомендации

1. Скиллинг, Джон (2004). «Вложенная выборка». Материалы конференции AIP. 735: 395–405. Bibcode:2004AIPC..735..395S. Дои:10.1063/1.1835238.
2. Скиллинг, Джон (2006). «Вложенная выборка для общих байесовских вычислений». Байесовский анализ. 1 (4): 833–860. Дои:10.1214 / 06-BA127.
3. Чен, Мин-Хуэй, Шао, Ци-Ман и Ибрагим, Джозеф Джордж (2000). Методы Монте-Карло в байесовских вычислениях. Springer. ISBN  978-0-387-98935-8.
4. Уолтер, Клемент (2017). «Оценка методом Монте-Карло на основе точечного процесса». Статистика и вычисления. 27: 219–236. arXiv:1412.6368. Дои:10.1007 / s11222-015-9617-y. S2CID  14639080.
5. Яса, Томислав; Сян, Нин (2012). «Вложенный отбор проб применяется в байесовском анализе затухания акустики помещения». Журнал Акустического общества Америки. 132 (5): 3251–3262. Bibcode:2012ASAJ..132.3251J. Дои:10.1121/1.4754550. PMID  23145609. S2CID  20876510.
6. Веб-сайт Джона Скиллинга
7. Алгоритм вложенной выборки в Haskell at Hackage
8. Вложенный алгоритм выборки в R на сайте Bojan Nikolic
9. Вложенный алгоритм выборки в R на GitHub
10. Вложенный алгоритм выборки на C ++ на GitHub
11. Вложенный алгоритм выборки в Python на GitHub
12. Вложенный алгоритм выборки для моделирования материалов на GitHub
13. Feroz, F .; Хобсон, М. (2008). «Мультимодальная вложенная выборка: эффективная и надежная альтернатива методам Монте-Карло с цепью Маркова для анализа астрономических данных». MNRAS. 384 (2): 449–463. arXiv:0704.3704. Bibcode:2008МНРАС.384..449Ф. Дои:10.1111 / j.1365-2966.2007.12353.x. S2CID  14226032.
14. Программный пакет вложенной выборки MultiNest на GitHub
15. Программный пакет вложенной выборки PolyChord на GitHub
16. Хэндли, Уилл; Майк, Хобсон; Энтони, Ласенби (2015). «полихорда: вложенная семплирование нового поколения». Ежемесячные уведомления Королевского астрономического общества. 453 (4): 4384–4398. arXiv:1506.00171. Bibcode:2015МНРАС.453.4384H. Дои:10.1093 / мнрас / stv1911. S2CID  118882763.
17. Mukherjee, P .; Parkinson, D .; Лиддл, А. (2006). «Алгоритм вложенной выборки для выбора космологической модели». Астрофизический журнал. 638 (2): 51–54. arXiv:Astro-ph / 0508461. Bibcode:2006ApJ ... 638L..51M. Дои:10.1086/501068. S2CID  6208051.
18. Mthembu, L .; Marwala, T .; Friswell, M.I .; Адхикари, С. (2011). «Выбор модели при обновлении конечно-элементной модели с использованием байесовской статистики свидетельств». Механические системы и обработка сигналов. 25 (7): 2399–2412. Bibcode:2011MSSP ... 25,2399 млн. Дои:10.1016 / j.ymssp.2011.04.001.
19. Партай, Ливия Б. (2010). «Эффективная выборка конфигурационных пространств атомов». Журнал физической химии B. 114 (32): 10502–10512. arXiv:0906.3544. Дои:10.1021 / jp1012973. PMID  20701382. S2CID  16834142.
20. Хигсон, Эдвард; Хэндли, Уилл; Хобсон, Майкл; Ласенби, Энтони (2019). «Динамическая вложенная выборка: улучшенный алгоритм оценки параметров и расчета доказательств». Статистика и вычисления. 29 (5): 891–913. arXiv:1704.03459. Bibcode:2019S&C .... 29..891H. Дои:10.1007 / s11222-018-9844-0. S2CID  53514669.
21. Хигсон, Эдвард (2018). "dyPolyChord: динамическая вложенная выборка с помощью PolyChord". Журнал открытого программного обеспечения. 3 (29): 965. Дои:10.21105 / joss.00965.
22. Программный пакет динамической вложенной выборки dyPolyChord на GitHub
23. Программный пакет вложенной выборки dynesty на GitHub
24. Спигл, Джошуа (2020). «dynesty: Пакет динамической вложенной выборки для оценки байесовских апостериорных данных и свидетельств». Ежемесячные уведомления Королевского астрономического общества. 493 (3): 3132–3158. arXiv:1904.02180. Дои:10.1093 / mnras / staa278. S2CID  102354337.
25. Эштон, Грегори; и другие. (2019). «Билби: удобная библиотека байесовских выводов для гравитационно-волновой астрономии». Серия дополнений к астрофизическому журналу. 241 (2): 13. arXiv:1811.02042. Bibcode:2019ApJS..241 ... 27A. Дои:10.3847 / 1538-4365 / ab06fc. S2CID  118677076.
26. Цукер, Кэтрин; и другие. (2018). «Отображение расстояний через молекулярное облако Персея с использованием наблюдений {CO}, звездной фотометрии и измерений параллакса Gaia {DR} 2». Астрофизический журнал. 869 (1): 83. arXiv:1803.08931. Дои:10.3847 / 1538-4357 / aae97c. S2CID  119446622.
27. Гюнтер, Максимилиан; и другие. (2019). «Супер-Земля и два суб-Нептуна, проходящие через ближайший тихий М-карлик TOI-270». Природа Астрономия. 3 (12): 1099–1108. arXiv:1903.06107. Bibcode:2019НатАс ... 3.1099G. Дои:10.1038 / с41550-019-0845-5. S2CID  119286334.