Hamiltonian monte carlo on Manifolds Chang liu 2015-09-14
Hamiltonian Monte Carlo on Manifolds Chang Liu 2015-09-14
Outline ntroduction to hamiltonian monte carlo Riemann manifold Langevin and hamiltonian Monte Carlo methods(Girolami Calderhead 2011) Geodesic monte carlo on embedded Manifolds Byrne Girolami, 2013)
Outline • Introduction to Hamiltonian Monte Carlo • Riemann manifold Langevin and Hamiltonian Monte Carlo methods (Girolami & Calderhead, 2011) • Geodesic Monte Carlo on Embedded Manifolds (Byrne & Girolami, 2013)
Introduction to hamiltonian Monte carlo (Ref: Neal, 2011) History Overview Hamiltonian Dynamics MCMC from Hamiltonian dynamics lustrations of hmc and its benefits
Introduction to Hamiltonian Monte Carlo (Ref: Neal, 2011) • History • Overview • Hamiltonian Dynamics • MCMC from Hamiltonian dynamics • Illustrations of HMC and its benefits
History Background: for the task of simulating the distribution of states for a system of idealized molecules (Metropolis, et al., 1953 MCMC with Metropolis test (Alder Wainwright, 1959 ): deterministic approach by simulating Hamiltonian dynamics Birth: combining(hybrid) (Duane, et al., 1987): Hybrid Monte Carlo. Renamed as Hamiltonian monte carlo afterwards Application to statistics (Neal, 1993ab probabilistic inference and Bayesian learning (Neal, 1996a]: neural network models (Ishwaran, 1999 ): generalized linear models
History • Background: for the task of simulating the distribution of states for a system of idealized molecules, – (Metropolis, et al., 1953): MCMC with Metropolis test. – (Alder & Wainwright, 1959): deterministic approach by simulating Hamiltonian dynamics. • Birth: combining (hybrid) – (Duane, et al., 1987): Hybrid Monte Carlo. Renamed as Hamiltonian Monte Carlo afterwards. • Application to statistics – (Neal, 1993ab): probabilistic inference and Bayesian learning – (Neal, 1996a): neural network models – (Ishwaran, 1999): generalized linear models – …
Overview The metropolis-Hastings method for sampling from the target distribution p( by a proposal transition distribution q(xtlxt-1 Sample xt-1 from q(xlxt-1 Set xt=xt-1 with probability 11. pcxi-1dqxt-ikxi-i22 otherwise set xt =xt-1 x t-1t-1 Hamiltonian dynamics can be seen as a proposal generator it provides a deterministic proposal from xt-1 to xt-1 with p(x)invariant. So the acceptance rate is high and the samples are less correlated
Overview • The Metropolis-Hastings method for sampling from the target distribution 𝑝 𝑥 by a proposal transition distribution 𝑞 𝑥𝑡 𝑥𝑡−1 : – Sample 𝑥𝑡−1 ∗ from 𝑞 𝑥 𝑥𝑡−1 – Set 𝑥𝑡 = 𝑥𝑡−1 ∗ with probability min 1, 𝑝 𝑥𝑡−1 ∗ 𝑞 𝑥𝑡−1 𝑥𝑡−1 ∗ 𝑝 𝑥𝑡−1 𝑞 𝑥𝑡−1 ∗ 𝑥𝑡−1 , otherwise set 𝑥𝑡 = 𝑥𝑡−1 • Hamiltonian dynamics can be seen as a proposal generator: it provides a deterministic proposal from 𝑥𝑡−1 to 𝑥𝑡−1 ∗ with 𝑝 𝑥 invariant. So the acceptance rate is high and the samples are less correlated
Overview Applied to MCMC: given a target distribution p(x HMC provides proposals not for x but the augmented random variable z=(x, v) with stationary distribution p(z)a exp (H(z)), where H(z==logp(x)+v M1/2. note that p(x=p(r, so samples of z will provide correct samples of x For practice: simulate the hamiltonian dynamics by some discrete integrator(e. g. leap frog that keeps some certain properties of the hamilton dynamics(e.g. symplectic symmetric consistent) correct the discretization error by mh test
Overview • Applied to MCMC: given a target distribution 𝑝 𝑥 , HMC provides proposals not for 𝑥 but the augmented random variable 𝑧 = 𝑥, 𝑣 with stationary distribution 𝑝 𝑧 ∝ exp −𝐻 𝑧 , where 𝐻 𝑧 = −log 𝑝 𝑥 + 𝑣 ⊤𝑀𝑣/2. Note that 𝑝 𝑥 = 𝑝 𝑥 , so samples of 𝑧 will provide correct samples of 𝑥. • For practice: simulate the Hamiltonian dynamics by some discrete integrator (e.g. leap frog) that keeps some certain properties of the Hamilton dynamics (e.g. symplectic, symmetric, consistent); correct the discretization error by MH test
Hamiltonian Dynamics Hamiltonians equation a dynamic system with degree of freedom d can be described by a d-dim vector q( generalized coordinate)and a d-dim vector p( generalized momentum, defined by p i ac(a, a, t) in physics), z=(q,p is called the canonical coordinates The dynamic system is dominated by its Hamiltonian: H (q, p, t)=iqipi L(a, q tlg=g(p If U does not change with time, H(a,p, t)=h(q, p), in which case H(q,p)=u+ K is the energy of the system
Hamiltonian Dynamics • Hamiltonian’s Equation – A dynamic system with degree of freedom 𝑑 can be described by a 𝑑-dim vector 𝑞 (generalized coordinate) and a 𝑑-dim vector 𝑝 (generalized momentum, defined by 𝑝𝑖 = 𝜕ℒ 𝑞,𝑞ሶ,𝑡 𝜕𝑞ሶ𝑖 in physics), 𝑧 = (𝑞, 𝑝) is called the canonical coordinates. – The dynamic system is dominated by its Hamiltonian: 𝐻 𝑞, 𝑝,𝑡 = σ𝑖 𝑞ሶ 𝑖𝑝𝑖 − ℒ(𝑞, 𝑞ሶ.𝑡)ȁ𝑞ሶ=𝑞ሶ 𝑝 . If 𝑈 does not change with time, 𝐻 𝑞, 𝑝,𝑡 = 𝐻(𝑞, 𝑝), in which case 𝐻 𝑞, 𝑝 = 𝑈 + 𝐾 is the energy of the system
Hamiltonian Dynamics Hamilton s equations The system evolves following aH H q dz Alternative expression JVH(), where dt d×d d×d d×d 0 dxd For HMC, h(q,p)=u(a)+k(p, k(p)=p M-lp/2 qi =[m pli aU =agi
Hamiltonian Dynamics • Hamilton’s Equations – The system evolves following: 𝑞ሶ 𝑖 = 𝜕𝐻 𝜕𝑝 𝑝ሶ 𝑖 = − 𝜕𝐻 𝜕𝑞 – Alternative expression: 𝑑𝑧 𝑑𝑡 = 𝐽𝛻𝐻 𝑧 , where 𝐽 = 0𝑑×𝑑 𝐼𝑑×𝑑 −𝐼𝑑×𝑑 0𝑑×𝑑 – For HMC, 𝐻 𝑞, 𝑝 = 𝑈 𝑞 + 𝐾 𝑝 ,𝐾 𝑝 = 𝑝 𝑇𝑀−1𝑝/2, 𝑞ሶ 𝑖 = 𝑀−1𝑝 𝑖 𝑝ሶ 𝑖 = − 𝜕𝑈 𝜕𝑞𝑖
Hamiltonian dynamics Properties of Hamiltonian Dynamics - Reversibility The mapping Is determined by Hamiltonian's equation from(a(t),p(t) to( q(t +s),p(t +s)) is one to one The inverse mapping is just negate p and apply Ts( See the Hamilton's equation Conservation of the hamiltonian The system evolves with its hamiltonian unchanged dh d ∑ dq: ah dp; aH ∑ ah ahaHaH 0 i=1 api agi aqi api
Hamiltonian Dynamics • Properties of Hamiltonian Dynamics – Reversibility • The mapping 𝑇𝑠 determined by Hamiltonian’s equation from 𝑞 𝑡 ,𝑝 𝑡 to 𝑞 𝑡 + 𝑠 ,𝑝 𝑡 + 𝑠 is one to one. The inverse mapping is just negate 𝑝 and apply 𝑇𝑠 . (See the Hamilton’s equation.) – Conservation of the Hamiltonian • The system evolves with its Hamiltonian unchanged:
Hamiltonian dynamics Properties of hamiltonian Dynamics Volume Preservation(Liouville' s theorem ): the volume V of a region R in the phase space((g, p) space)is preserved under the transformation Ts Proof: letz=(q,p),V=J R(tq么 z·dS= dt ar(t) Rt(. i)dz, 卩·z=卩.(q,p) .+妞-∑两/∑Dnm1 a ah a 0H 0 i=1 dgi opi api dgi
Hamiltonian Dynamics • Properties of Hamiltonian Dynamics – Volume Preservation (Liouville’s theorem): the volume 𝑉 of a region 𝑅 in the phase space ((𝑞, 𝑝) space) is preserved under the transformation 𝑇𝑠 • Proof: let 𝑧 = (𝑞, 𝑝), 𝑉 = �� �� 𝑑𝑧, 𝑑𝑉 𝑑𝑡 �� �𝜕�ׯ = 𝑧ሶ ⋅ 𝑑𝑆 = �� �� 𝛻 ⋅ 𝑧ሶ 𝑑𝑧, 𝛻 ⋅ 𝑧ሶ = 𝛻 ⋅ 𝑞ሶ, 𝑝ሶ =