C(0,1) に対する ZigZag サンプラーの軌道
A Blog Entry on Bayesian Computation by an Applied Mathematician
$$
$$
1 Zig-Zag 過程
1.1 はじめに
1次元の Zig-Zag 過程は元々,Curie-Weiss 模型 における Glauber 動力学を lifting により非可逆化して得る Markov 連鎖の,スケーリング極限として特定された Feller-Dynkin 過程である (Bierkens and Roberts, 2017).
区分確定的 Markov 過程(PDMP)といい,ランダムな時刻にランダムな動きをする以外は,決定論的な動きをする過程である.
PDMP の一般論については次の記事も参照:
ただし Zig-Zag 過程は,(Goldstein, 1951) で電信方程式と関連して,同様の過程が扱われた歴史もある.
1.2 設定
Zig-Zag 過程 \(Z=(X,\Theta)\) の状態空間は,力学的な立場に立って \(E=\mathbb{R}^d\times\{\pm1\}^d\) と見ることが多い.
力学における相空間と同様,\(X\in\mathbb{R}^d\) が位置を,\(\theta\in\{\pm1\}^d\) が速度を表すと解する.すなわち,Zig-Zag 過程は全座標系と \(45\) 度をなす方向に,常に一定の単位速さで \(\mathbb{R}^d\) 上を運動する粒子とみなせる.
すなわち,\((x,\theta)\in E\) から出発する Zig-Zag 過程は,次の微分方程式系で定まる決定論的なフロー \(\phi_{(x,\theta)}:\mathbb{R}\to\mathbb{R}^d\) に従って運動する粒子とみなせる: \[ \frac{d \phi_{(x,\theta)}(t)}{d t}=\theta,\qquad \frac{d \Theta_t}{d t}=0. \]
1.3 アルゴリズム
1.3.1 全体像
Zig-Zag 過程 \(Z\) は次のようにしてシミュレーションできる:
1.3.2 到着時刻 \(T_i\) のシミュレーション方法
Zig-Zag 過程のシミュレーションは,ほとんど強度
\[ M_i(t):=\int^t_0m_i(s)\,ds \] を持つ非一様 Poisson 点過程のシミュレーションに帰着される.
実はこれは,指数分布確率変数 \(E_i\overset{\text{iid}}{\sim}\operatorname{Exp}(1)\) について \[ T_i\overset{\text{d}}{=}M_i^{-1}(E_i) \] と求まる.
1.3.3 Poisson 剪定
仮にこの逆関数 \(M_i^{-1}\) が得られない場合でも,剪定 (Lewis and Shedler, 1979) によって \(T_i\) は正確なシミュレーションが可能である.
この方法は,\(M_i^{-1}\) を数値的に計算するよりも遥かに速い.これは \(M_i\) の定義に積分が存在し,これが多くの場合高次元になるためである.
1.4 レート関数の条件
Zig-Zag 過程 \(Z\) がどのような分布に従うかは,全てレート関数 \(\lambda_1,\cdots,\lambda_d\) に委ねられている.
1.5 エルゴード性の条件
\(\pi\) が不変分布になるための十分条件 1.4 は極めて緩かったが,MCMC として使えるためにはエルゴード性が成り立つ必要がある.
1.6 Subsampling Technology
Zig-Zag 過程はレート関数 \(\lambda\) の設計に大きな自由度があった(第 1.4 節).
これにより,Zig-Zag 過程ではバイアスを導入しない subsampling が可能であり,これを通じて データサイズに依らない一定効率での事後分布サンプリングが可能になる という super-efficiency (Bierkens et al., 2019) と呼ばれる性質を持つ.
この性質が実用上は最も重要である.詳しくは,次の記事を参照:
2 シミュレーション
2.1 1次元での例
ZigZag サンプラーは非対称なダイナミクスを持っており,その点が MALA (Metropolis-adjusted Langevin Algorithm) や HMC (Hamiltonian Monte Carlo) などの従来手法と異なる.
1次元でその違いを確認するために,Cauchy 分布という裾の重い分布を用いる.Cauchy 分布 \(\mathrm{C}(\mu,\sigma)\) は次のような密度を持つ: \[ f(x)=\frac{1}{\pi\sigma}\frac{1}{1+\left(\frac{x-\mu}{\sigma}\right)^2}. \]
その裾の重さ故,平均も分散も存在しない(発散する).
このとき,次のような観察が得られる:
MALA と比較すると,その再帰の速さが歴然としている:4
Code
using AdvancedHMC, AdvancedMH, ForwardDiff
using LinearAlgebra
using LogDensityProblems
using LogDensityProblemsAD
using StructArrays
using Distributions
using Random
Random.seed!(2)
# Define the target distribution (1D Cauchy) using the `LogDensityProblem` interface
struct LogTargetDensityCauchy
::Float64
loc::Float64
scaleend
logdensity(p::LogTargetDensityCauchy, θ) = -log(π) - log(p.scale) - log(1 + ((θ[1] - p.loc)/p.scale)^2)
LogDensityProblems.dimension(p::LogTargetDensityCauchy) = 1
LogDensityProblems.capabilities(::Type{LogTargetDensityCauchy}) = LogDensityProblems.LogDensityOrder{0}()
LogDensityProblems.
# Choose initial parameter value for 1D
= [500.0]
initial_θ
# Use automatic differentiation to compute gradients
= LogDensityProblemsAD.ADgradient(Val(:ForwardDiff), LogTargetDensityCauchy(0.0, 1.0))
model_with_ad
# Set up the sampler with a multivariate Gaussian proposal.
= 100
σ² = MALA(x -> MvNormal((σ² / 2) .* x, σ² * I))
spl
# Sample from the posterior.
= sample(model_with_ad, spl, 2000; initial_params=initial_θ, chain_type=StructArray, param_names=["θ"])
chain
# plot
= chain.θ
θ_vector = zip(1:length(θ_vector), θ_vector)
sample_values = plot_1dtraj(sample_values, title="1D MALA Sampler (Cauchy Distribution)", markersize=0, ylim=(-30, 750), label="MALA_1D") p2
C(0,1) に対する MALA サンプラーの軌道
2つを並べて比較すると,Langevin ダイナミクスの方は,少し diffusive な動き(random walk property と呼ばれる)が見られることがわかる.
2.2 2次元での例
\[ \Sigma^{-1}=\begin{pmatrix}2&-1\\-1&2\end{pmatrix} \]
で定まる分散共分散行列 \(\Sigma\) を持った中心化された正規分布 \(\pi(x)dx=\mathrm{N}_2(0,\Sigma)(dx)\) に対しては,対数尤度は
\[\begin{align*} \log\pi(x)&=-\log\left((2\pi)^{d/2}(\det\Sigma)^{1/2}\right)\\ &\qquad\quad-\frac{1}{2}x^\top\Sigma^{-1}x \end{align*}\]
であるから,\(\phi:=-\log\pi\) の第 \(i\) 成分に関する微分は
\[\begin{align*} \partial_i\phi(x)&=\frac{\partial }{\partial x_i}\biggr(\frac{1}{2}x^\top\Sigma^{-1}x\biggl)\\ &=\Sigma^{-1}x. \end{align*}\]
using ZigZagBoomerang
using SparseArrays
= 2
d
# 対数尤度関数 ϕ の第 i 成分に関する微分を計算
= sparse([1,1,2,2], [1,2,1,2], [2.0,-1.0,-1.0,2.0])
Γ ∇ϕ(x, i, Γ) = ZigZagBoomerang.idot(Γ, i, x)
# 初期値
= 0.0
t0 = randn(d)
x0 0 = rand([-1.0,1.0], d)
θ
# Rejection bounds
= 1.0 * ones(length(x0))
c
# ZigZag 過程をインスタンス化
= ZigZag(Γ, x0*0)
Z
# シミュレーション実行
= 20.0
T = spdmp(∇ϕ, t0, x0, θ0, T, c, Z, Γ; adapt=true)
zigzag_trace, (tT, xT, θT), (acc, num)
# 軌跡を離散化
= collect(zigzag_trace) traj
- 1
-
勾配関数
∇ϕ
の計算のためには,共分散行列の逆(精度行列ともいう)をSparseMatrixCSC
型で指定する必要があることに注意.idot
の実装 も参照. - 2
-
idot
は,疎行列Γ
の第i
列と,疎ベクトルx
との内積を高速に計算する関数.
3 Zig-Zag サンプラーの実装
ZigZagBoomerang
の実装を紹介する.
Julia の MCMC パッケージ一般については次の稿を参照:
3.1 ZigZag サンプラーを提供しているパッケージ一覧
3.1.1 R
パッケージ
Joris Bierkens ら開発の R パッケージ RZigZag
(GitHub / CRAN) が最も手軽に実行できる.
3.1.2 Julia
パッケージ
一方で,(Bierkens et al., 2022) では Julia によるパッケージ ZigZagBoomerang
(GitHub / ANN / docs) も提供している.名前によらず,2022.1 月リリースの v.0.11
以降は BPS もサポートしている.
using Pkg
Pkg.add("ZigZagBoomerang")
3.2 ZigZag
オブジェクト
4 文献紹介
Zig-Zag Sampler を導入したのは (Bierkens et al., 2019) であるが,ざっと仕組みを把握をしたいならば (Corbella et al., 2022) の第二章がよっぽどわかりやすいだろう.
References
Footnotes
計算過程は省略したが,\(d=2\) の場合と,\(d=3\) の場合を少しやってみると良い.↩︎
参照測度は,\([d]\) 上のものは計数測度 \(\#\) をとっている.↩︎
従って,レート関数 \(\lambda\) は連続とする.この関数 \(\gamma_i\) は,\(U\) の情報には依らない追加のリフレッシュ動作を仮定に加える.実際,\(\lambda_i(x,\theta)-\lambda_i(x,F_i(\theta))=\theta_i\partial_iU(x)\) である限り,\(\theta\) と \(F_i(\theta)\) の往来には影響を与えず釣り合っているため,どのような \(\gamma_i\) をとっても,平衡分布には影響を与えない.しかし,高くするごとにアルゴリズムの対称性が上がるため,\(\gamma\equiv0\) とすることが Monte Carlo 推定量の漸近分散を最小にするという (Andrieu and Livingstone, 2021).(Bierkens et al., 2021) でも同様の洞察がなされている.↩︎
(Bierkens et al., 2019) にある提示の仕方である.Zig-Zag の 2000 単位時間を単純に MALA と比較はできないと筆者も考えるが,ダイナミクスに注目していただきたい.実際,自分で実装してみると,シード値をいじらないと,Zig-Zag は必ずしも 500 単位時間前後でモード \(0\) に戻るわけではない.↩︎
実は6つ持つ.他の初期値は
σ=(Vector(diag(Γ))).^(-0.5); λref=0.0, ρ=0.0
↩︎