Предварительно обусловленный алгоритм Кранка – Николсона

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

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

Алгоритм с таким названием был описан в 2013 году Коттером, Робертсом , Стюартом и Уайтом. а ее свойства эргодичности были доказаны год спустя Хайрером , Стюартом и Фоллмером. В конкретном контексте отбора проб диффузионных мостов этот метод был представлен в 2008 году.

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

Обзор

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

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

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

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

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

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

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

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

Особая форма этого предложения pCN заключается в том, чтобы принять

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

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

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

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

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

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

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

Вероятность принятия принимает простую форму

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

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

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

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

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

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

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