Предварительно подготовленный алгоритм Crank – Nicolson - Preconditioned Crank–Nicolson algorithm

В вычислительная статистика, то предварительно обусловленный алгоритм Кранка – Николсона (pCN) это Цепь Маркова Монте-Карло (MCMC) метод получения случайные выборки - последовательности случайных наблюдений - от цели распределение вероятностей для которых затруднен прямой отбор проб.

Наиболее важной особенностью алгоритма pCN является его устойчивость к размерам, что делает его хорошо подходящим для задач выборки большой размерности. Алгоритм pCN четко определен, с невырожденной вероятностью принятия, даже для целевых распределений на бесконечномерных Гильбертовы пространства. Как следствие, когда pCN реализуется на реальном компьютере в большом, но конечном измерении N, т.е. на N-мерное подпространство исходного гильбертова пространства, свойства сходимости (такие как эргодичность ) алгоритма не зависят от N. Это резко контрастирует с такими схемами, как гауссовское случайное блуждание Метрополиса – Гастингса и Алгоритм Ланжевена с поправкой на мегаполис, вероятность принятия которого вырождается к нулю при N стремится к бесконечности.

Алгоритм был представлен в 2013 году Коттером, Робертс, Стюарт и белый,^[1] и его свойства эргодичности были доказаны годом позже Hairer, Стюарт и Фоллмер.^[2]

Описание алгоритма

Обзор

Смотрите также: Алгоритм Метрополиса – Гастингса

Алгоритм pCN генерирует цепь Маркова ${\displaystyle (X_{n})_{n\in \mathbb {N} }}$ в гильбертовом пространстве ${\displaystyle {\mathcal {H}}}$ чья инвариантная мера является вероятностной мерой ${\displaystyle \mu }$ формы

${\displaystyle \mu (E)={\frac {1}{Z}}\int _{E}\exp(-\Phi (x))\,\mu _{0}(\mathrm {d} x)}$

для каждого измеримый набор ${\displaystyle E\subseteq {\mathcal {H}}}$, с нормирующей постоянной ${\displaystyle Z}$ данный

${\displaystyle Z=\int _{\mathcal {H}}\exp(-\Phi (x))\,\mu _{0}(\mathrm {d} x),}$

где ${\displaystyle \mu _{0}={\mathcal {N}}(0,C_{0})}$ это Гауссова мера на ${\displaystyle {\mathcal {H}}}$ с участием ковариационный оператор ${\displaystyle C_{0}}$ и ${\displaystyle \Phi \colon {\mathcal {H}}\to \mathbb {R} }$ это какая-то функция. Таким образом, метод pCN применяется к целевым вероятностным мерам, которые являются повторным взвешиванием эталонной гауссовской меры.

В Алгоритм Метрополиса – Гастингса - это общий класс методов, которые пытаются создать такие цепи Маркова ${\displaystyle (X_{n})_{n\in \mathbb {N} }}$, и сделать это с помощью двухэтапной процедуры предлагая новое состояние ${\displaystyle X'_{n+1}}$ учитывая текущее состояние ${\displaystyle X_{n}}$ а потом принимая или отвергая это предложение, в соответствии с определенной вероятностью принятия, определить следующее состояние ${\displaystyle X_{n+1}}$. Идея алгоритма pCN заключается в том, что умный выбор (несимметричного) предложения для нового состояния ${\displaystyle X'_{n+1}}$ данный ${\displaystyle X_{n}}$ может иметь связанную функцию вероятности принятия с очень желательными свойствами.

Предложение pCN

Специальная форма этого предложения pCN - принять

${\displaystyle X'_{n+1}={\sqrt {1-\beta ^{2}}}X_{n}+\beta \Xi _{n+1},}$

${\displaystyle \Xi _{n+1}\sim \mu _{0}{\text{ i.i.d.}}}$

или, что то же самое,

${\displaystyle X'_{n+1}|X_{n}\sim {\mathcal {N}}\left({\sqrt {1-\beta ^{2}}}X_{n},\beta C_{0}\right).}$

Параметр ${\displaystyle 0<\beta <1}$ это размер шага, который можно свободно выбирать (и даже оптимизировать для статистической эффективности). Затем один генерирует ${\displaystyle Z_{n+1}\sim \mathrm {Unif} ([0,1])}$ и устанавливает

${\displaystyle X_{n+1}=X'_{n+1}{\text{ if }}Z_{n+1}\leq \alpha (X_{n},X'_{n+1}),}$

${\displaystyle X_{n+1}=X_{n}{\text{ if }}Z_{n+1}>\alpha (X_{n},X'_{n+1}).}$

Вероятность принятия принимает простой вид

${\displaystyle \alpha (x,x')=\min(1,\exp(\phi (x)-\phi (x'))).}$

Это можно показать^[2] что этот метод не только определяет цепь Маркова, удовлетворяющую подробный баланс относительно целевого распределения ${\displaystyle \mu }$, а значит, ${\displaystyle \mu }$ как инвариантная мера, но также обладает спектральной щелью, не зависящей от размерности ${\displaystyle {\mathcal {H}}}$, так что закон ${\displaystyle X_{n}}$ сходится к ${\displaystyle \mu }$ так как ${\displaystyle n\to \infty }$. Таким образом, хотя еще может потребоваться настройка параметра размера шага ${\displaystyle \beta }$ Чтобы достичь желаемого уровня статистической эффективности, производительность метода pCN должна соответствовать размеру рассматриваемой проблемы выборки.

Противопоставьте симметричным предложениям

Такое поведение pCN резко контрастирует с предложением гауссовского случайного блуждания.

${\displaystyle X'_{n+1}\mid X_{n}\sim {\mathcal {N}}\left(X_{n},\beta \Gamma \right)}$

с любым выбором ковариации предложения ${\displaystyle \Gamma }$, или любой другой симметричный механизм предложения. Это можно показать с помощью Теорема Камерона – Мартина что для бесконечномерного ${\displaystyle {\mathcal {H}}}$ это предложение имеет нулевую вероятность принятия для ${\displaystyle \mu }$-почти все ${\displaystyle X'_{n+1}}$ и ${\displaystyle X_{n}}$. На практике, когда кто-то реализует предложение гауссовского случайного блуждания в размерности ${\displaystyle N}$, это явление можно увидеть в том, что

• для фиксированного ${\displaystyle \beta }$вероятность принятия стремится к нулю при ${\displaystyle N\to \infty }$, и
• для фиксированной желаемой вероятности положительного принятия, ${\displaystyle \beta \to 0}$ так как ${\displaystyle N\to \infty }$.

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

1. Cotter, S.L .; Робертс, Г. О .; Стюарт, А. М .; Уайт, Д. (2013). «Методы MCMC для функций: изменение старых алгоритмов, чтобы сделать их быстрее». Статист. Наука. 28 (3): 424–446. arXiv:1202.0709. Дои:10.1214 / 13-STS421. ISSN  0883-4237.
2. Hairer, M .; Стюарт, А. М .; Фоллмер, С. Дж. (2014). «Спектральные промежутки для алгоритма Метрополиса – Гастингса в бесконечных измерениях». Анна. Appl. Вероятно. 24 (6): 2455–2490. arXiv:1112.1392. Дои:10.1214 / 13-AAP982. ISSN  1050-5164.