11Approximate Inference by SamplingGraphical Models – 10708Ajit SinghCarnegie Mellon UniversityNovember 3rd, 2006Readings:K&F: 10.1, 10.2, 10.310-708 –©Ajit Singh 20062Approximate inference overview There are many many many many approximate inference algorithms for PGMs We will focus on three representative ones: sampling - today variational inference - continues next class loopy belief propagation and generalized belief propagation210-708 –©Ajit Singh 20063Goal Often we want expectations given samples x[1] … x[m] from a distribution P.10-708 –©Ajit Singh 20064Forward SamplingSample nodes in topological order310-708 –©Ajit Singh 20065Forward Sampling P(Y = y) = #(Y = y) / N P(Y = y | E = e) = #(Y = y, E = e) / #(E = e) Rejection sampling: throw away samples that do not match the evidence. Sample efficiency How often do we expect to see a record with E = e ?10-708 –©Ajit Singh 20066IdeaWhat is we just fix thevalue of evidence nodes ?What is expected numberof records with (Intelligence = Low) ?410-708 –©Ajit Singh 20067Likelihood Weighting10-708 –©Ajit Singh 20068Importance Sampling What if you cannot easily sample ? Posterior distribution on a Bayesian network P(Y = y | E = e) where the evidence itself is a rare event. Sampling from a Markov network with cycles is always hard See homework 4 Pick some distribution Q(X) that is easier to sample from. Assume that if P(x) > 0 then Q(x) > 0 Hopefully D(P||Q) is small510-708 –©Ajit Singh 20069Importance Sampling Unnormalized Importance Sampling10-708 –©Ajit Singh 200610Mutilated BN Proposal Generating a proposal distribution for a Bayesian network Evidenced nodes have no parents. Each evidence node Zi= zihas distribution P(Zi= zi) = 1 Equivalent to likelihood weighting610-708 –©Ajit Singh 200611Forward Sampling Approaches Forward sampling, rejection sampling, and likelihood weighting are all forward samplers Requires a topological ordering. This limits us to Bayesian networks Tree Markov networks Unnormalized importance sampling can be done on cyclic Markov networks, but it is expensive See homework 4 Limitation Fixing an evidence node only allows it to directly affect its descendents. 10-708 –©Ajit Singh 200612Scratch space710-708 –©Ajit Singh 200613Markov Blanket Approaches Forward Samplers: Compute weight of Xigiven assignment to ancestors in topological ordering Markov Blanket Samplers: Compute weight of Xigiven assignment to its Markov Blanket.10-708 –©Ajit Singh 200614Markov Blanket Samplers Works on any type of graphical model covered in the course thus far.810-708 –©Ajit Singh 200615Gibbs Sampling1. Let X be the non-evidence variables2. Generate an initial assignment ξ(0) 3. For t = 1..T1. ξ(t)= ξ(t-1)2. For each Xiin X1. ui= Value of variables X -{Xi} in sample ξ(t)2. Compute P(Xi| ui)3. Sample xi(t)from P(Xi| ui)4. Set the value of Xi= xi(t)in ξ(t)4. Samples are taken from ξ(0)… ξ(T)10-708 –©Ajit Singh 200616Computing P(Xi| ui) The major task in designing a Gibbs sampler is deriving P(Xi| ui) Use conditional independence Xi ⊥ Xj| MB(Xi) for all Xjin X -MB(Xi) - {Xi}P(X|Y = y) = P(Y|X = x) =910-708 –©Ajit Singh 200617Pairwise Markov Random Field10-708 –©Ajit Singh 200618Markov Chain Interpretation The state space consists of assignments to X. P(xi| ui) are the transition probability (neighboring states differ only in one variable) Given the transition matrix you could compute the exact stationary distribution Typically impossible to store the transition matrix. Gibbs does not need to store the transition matrix !1010-708 –©Ajit Singh 200619Scratch space10-708 –©Ajit Singh 200620Convergence Not all samples ξ(0)… ξ(T)are independent. Consider one marginal P(xi|ui). Burn-in Thinning1110-708 –©Ajit Singh 200621MAP by Sampling Generate a few samples from the posterior For each Xithe MAP is the majority assignment10-708 –©Ajit Singh 200622What you need to know Forward sampling approaches Forward Sampling / Rejection Sampling Generate samples from P(X) or P(X|e) Likelihood Weighting / Importance Sampling Sampling where the evidence is rare Fixing variables lowers variance of samples when compared to rejection sampling. Useful on Bayesian networks & tree Markov networks Markov blanket approaches Gibbs Sampling Works on any graphical model where we can sample from P(Xi| rest). Markov chain interpretation. Samples are independent when the Markov chain converges. Convergence heuristics, burn-in,
View Full Document
Unlocking...