【正文】 , is easy to sample. ? Easy to implement for Graphical Models. ? Proposed by Geman Geman (TPAMI, 1984). 103 ),( 1 dXXX ?? )|( jj XXP ?? Gibbs sampling algorithm ? Goal: draw a sequence of examples , when , , where is the target distribution。 ? Algorithm: ? Draw from some initial distribution ? For ? 1. ? 2. For each ? Sample according to ? Return 104 nxxx , 21 ???n Pxn ~P00 ~ Px nt ,1 ??ddiii Rxxx ?? ),( 1 ?1?? tt xx ][dj?jtx nxx , 21 ? )|( jj XXP ?? Why Gibbs sampling is easy for PGM? ? Sample 105 ),...|( hgeaFP??????ffffehPafPFehPaFPfehPegPafPdcePadPbcPbPaPFehPegPaFPdcePadPbcPbPaPhgeafPhgeaFPhgeaFP),|()|(),|()|(),|()|()|(),|()|()|()()(),|()|()|(),|()|()|()()(),...,(),...,(),...|(Only the factors that involve F left! ? Generally, for both Bayesian works and Markov works, the conditional probability for Gibbs sampling involves only factors that the query random variable lives in. ? Trivially generalize to the case where there is evidence ? Draw a sequence of examples where the target distribution is 106 )|( eEP ??? Theorem: The Gibbs sampling process has a unique stationary distribution (or ) ? Disadvantages of Gibbs sampling for PGMs: ? Slow convergence to stationary distribution. 107 )|( eEP ??PMetropolisHastings Algorithm 108 ? For Gibbs sampling, we assume that it is easy to generate a sample from . But sometimes, this is difficult. ? More generally, for a target distribution , it may be very difficult to generate sample directly according to , does MCMC help? ? The idea of MetropolisHastings: ? Using a proposal distribution : a transition model. 109 )|( jj XXP ?PP)|39。(~ xxT? An important result for Markov chain: ? Detailed Balance (Reversible Markov chain): Definition: A finite state MC with transition probability matrix T is said to be reversible if there exists a unique distribution P such that for all x, x’ The above equation is called detailed balance. ? Reversible: for any sequence , the probability that it occurs in the process is the same as the probability that occurs. 110 ).39。|()39。()|39。()( xxTxPxxTxP ?nxxx , 21 ?11 , xxx nn ??? Theorem: If the transition matrix T defines a regular Markov chain, and T satisfies the detailed balance . to P, then P is the unique stationary distribution of the Markov chain T. 111 ? MetropolisHastings algorithm: ? Goal: draw a sequence of examples , when , , where is the target distribution. ? Algorithm: ? Let be a proposal transition model. ? Define the transition matrix of a Markov chain as: ? Generate according to the MC of . 112 nxxx , 21 ???n Pxn ~P )|39。(~ xxT ???????)|39。(~)()39。|(~)39。(,1min)|39。(xxTxPxxTxPxxT nxxx , 21 ?T? Proposition: For any target distribution , and any proposal transition model , the Markov chain defined by in the MetropolisHastings algorithm satisfies the detailed balance . . Thus if the Markov chain defined by is regular, is the unique stationary distribution. 113 )|39。(~ xxTP PT TPConvergence 114 ? Mixing time for MCMC: ? What we need is the stationary distribution of the Markov chain, but how long does it take to converge mixing time (burn in). ? Gibbs sampling sometimes has very slow convergence. ? MetropolisHastings’s convergence depends on the proposal distribution. 115 ? Theory for the convergence for MCMC: ? For a Markov chain, the largest eigenvalue of the transition matrix T is 1。 the gap between the largest and the second largest (in absolute value) eigenvalue determines the mixing time. ? A main challenge for PGM: ? Design MCMC algorithms that: 1) efficiently implementable for PGMs。 2) mixing time is not too long. 116 Some Thoughts and Open Problems 117 ? Inference is NPhard, what shall we do? ? Develop practical algorithms. P plete is a worst case result. ? To solve the inference problem, we are in a situation very similar to solving TSP (NPhard): 118 TSP: Find the shortest path such that each vertex is visited exactly once. ? TSP (decision) is NPplete. ? Euclidean TSP is NPhard. ? Approximate TSP is NPhard. 119 Arora proved (G246。del prize, 2023) : Euclidean TSP + approximation polynomial approximation scheme ? Can we find a reasonable class of graphical models such that (approximate) inference has polynomial time algorithm? 120 121 Thanks! 122 演講完畢，謝謝觀看！