# Piecewise-Deterministic Markov Chain Monte Carlo

2018.08.06 (미완성)

논문 출처 https://arxiv.org/abs/1707.05296

# Piecewise-Deterministic Markov Process

# 정의

어떤 시점에서의 behaviour가 Random jump에 의해 결정되지만 그 변화(evolution)는 시간에 대한 상미분방정식(ODE)에 의해 결정되는 프로세스를 PDMP라고 합니다. PDMP는 ODE(flow), Event rate(jump rate), Markov transition kernel(trasition measure)들에 의해 정의됩니다.

일단 $Z = \mathbb{R}^{n}$라 놓으면 $Z$-valued continuous time PDMP는 random jump에 의해 변화하고 deterministic dynamics를 포함하는 $c\grave{a}dl\grave{a}g$ process가 됩니다.

1. 여기서 만족하는 ODE는 다음과 같이 표현됩니다.

$\frac{dz_{t}}{dt} = \phi(z_{t})$

$\phi$는 미분가능한 이동(drift)을 의미하며, $\phi:Z \rightarrow Z$인 함수입니다.
이 식은 semi-group 성질 $\Phi_{s}\circ\Phi_{t} = \Phi_{s+t}$와 $t \mapsto \Phi_{t}(z)$가 $c\grave{a}dl\grave{a}g$라는 조건을 만족하는 결정론적(deterministic)인 흐름,

$(z, t) \in \mathbb{R}^{+} \times Z \mapsto \Phi_{t}(z) \in Z$

을 만들어 냅니다.

2. Event rate는 $\lambda:Z \mapsto \mathbb{R}^{+}$인 함수로 정의됩니다. 여기서 $\lambda(z_{t})\epsilon + o(\epsilon)$는 time interval $[t, t+\epsilon]$동안 event가 한 번 일어날 확률을 의미합니다.

3. $Z$에서 $Z$로 가는 Markov transition kernel $Q$는 event time $t$에서 $z_{t} \sim Q(z_{t-}, \cdot)$로 표현되고, $z_{t-}$는 event는 바로 직전의 프로세스가 됩니다.

역시 수식만으로 이해하기엔 한계가 있습니다.

저의 동료의 설명에 의하면 세포분열의 양상을 PDMP로 표현할 수 있다고 합니다. 세포의 크기를 $z_{t}$로 놓으면 시간에 따른 세포 성장은 ODE로 표현될 수 있습니다. 세포는 성장하다가 일정 크기가 되면 분열할 것입니다. 이때 $[t, t+\epsilon]$ 동안 한 번 분열할 확률은 Event rate가 됩니다. 분열을 하면 분열된 세포의 크기는 다시 작아집니다. 이 분열이라는 event의 직전과 직후 크기 관계는 Markov transition kernel로 표현될 수 있을 것입니다.

이 논문에서는 PDMP를 다음과 같이 시뮬레이션 했습니다.

# PD-MCMC

PDMP 방법으로 원하는 Probability distribution을 sampling하기 위해서는 적어도 원하는 distribution을 invariant distirbution으로 admit해야합니다. 이 invariant를 보장하는 충분조건은 논문에 잘 나와있습니다. ㅎㅎ

# 기존의 PD-MCMC 알고리즘들

우리가 알고 있는 모든 continuous time PD-MCMC 알고리즘들은 하나의 framework로 귀결됩니다.

sampling하려는 density distribution을 $\pi(x) = exp(-U(x))$라고 하고 $z = (x, v)$로 놓았을 때 확장된 distribution은 $Z = X \times V$에서

$\rho(dz) = \phi(dx)\psi(dv)$

로 표현됩니다. 여기서 $\psi$는 $V$ space위의 보조 함수(auxiliary function)입니다. $V$는 $\mathbb{R}^{d}$ 또는 unit hypersphere $\mathbb{S}^{d-1}$가 될 수 있습니다.

다음으로 linear dynamics는

$\phi(z) = (v, 0_{d})$

로 표현됩니다. 이는 analytic하게 다루기 쉽고

$\Phi_{t}(z) = (x + vt, v)$

로 표현될 수 있습니다. 동시에 $\nabla \cdot \phi = 0$을 만족합니다. 또한 이러한 모든 알고리즘들은 time reversal로 볼 수 있는 $S(x, v) = (x, -v)$에 의존합니다.

이러한 알고리즘들은 event rate과 transition kernel을 어떻게 정하느냐에 따라 달라집니다. 그 예시로는 Bouncy particle sampler, Zig-Zag sampler, BPS sampler with randomized bounces 등이 있습니다.

# Hamiltonian PD-MCMC

앞선 예시들은 linear flow에 기반하여 전개되었지만 Hamiltonian dynamics를 이용하면 좀 더 general하게 기술할 수 있습니다.