Readings K F 11 3 11 5 Yedidia et al paper from the class website Mean Field and Variational Methods Loopy Belief Propagation Graphical Models 10708 Carlos Guestrin Carnegie Mellon University November 8th 2006 1 Understanding Reverse KL Energy Function The Partition Function Maximizing Energy Functional Minimizing Reverse KL Theorem Energy Function is lower bound on partition function Maximizing energy functional corresponds to search for tight lower bound on partition function 10 708 Carlos Guestrin 2006 2 Structured Variational Approximate Inference Pick a family of distributions Q that allow for exact inference e g fully factorized mean field Find Q2Q that maximizes For mean field 10 708 Carlos Guestrin 2006 3 Optimization for mean field Constrained optimization solved via Lagrangian multiplier 9 such that optimization equivalent to Take derivative set to zero Theorem Q is a stationary point of mean field approximation iff for each i 10 708 Carlos Guestrin 2006 4 Understanding fixed point equation Coherence Difficulty Intelligence Grade SAT Letter Happy 10 708 Carlos Guestrin 2006 Job 5 Simplifying fixed point equation Coherence Difficulty Intelligence Grade SAT Letter Happy 10 708 Carlos Guestrin 2006 Job 6 Qi only needs to consider factors that intersect Xi Theorem The fixed point Coherence Difficulty Intelligence Grade is equivalent to Letter Happy SAT Job where the Scope j Uj Xi 10 708 Carlos Guestrin 2006 7 There are many stationary points 10 708 Carlos Guestrin 2006 8 Very simple approach for finding one stationary point Coherence Difficulty Initialize Q e g randomly or smartly Set all vars to unprocessed Pick unprocessed var Xi Grade SAT Letter Happy update Qi Intelligence Job set var i as processed if Qi changed set neighbors of Xi to unprocessed Guaranteed to converge 10 708 Carlos Guestrin 2006 9 More general structured approximations Coherence Difficulty Mean field very na ve approximation Consider more general form for Q Intelligence Grade SAT Letter assumption exact inference doable over Q Happy Job Theorem stationary point of energy functional 10 708 Carlos Guestrin 2006 10 Computing update rule for general case Coherence Difficulty Intelligence Grade Consider one SAT Letter Happy 10 708 Carlos Guestrin 2006 Job 11 Structured Variational update requires inferece Compute marginals wrt Q of cliques in original graph and cliques in new graph for all cliques What is a good way of computing all these marginals Potential updates sequential compute marginals update j recompute marginals parallel compute marginals update all s recompute marginals 10 708 Carlos Guestrin 2006 12 What you need to know about variational methods Structured Variational method Equivalent to maximizing energy functional searching for a tight lower bound on the partition function Many possible models for Q select a form for approximate distribution minimize reverse KL independent mean field structured as a Markov net cluster variational Several subtleties outlined in the book 10 708 Carlos Guestrin 2006 13 Announcements Tomorrow s recitation Ajit on Loopy BP 10 708 Carlos Guestrin 2006 14 Recall message passing over junction trees Exact inference DIG Coherence generate a junction tree message passing over neighbors inference exponential in size of clique CD Difficulty Intelligence Grade SAT GSI Letter Happy Job GJSL HGJ 10 708 Carlos Guestrin 2006 15 Belief Propagation on Tree Pairwise Markov Nets Tree pairwise Markov net is a tree no need to create a junction tree Coherence Difficulty Intelligence Message passing Grade SAT Letter More general equation N i neighbors of i in pairwise MN Happy Job Theorem Converges to true probabilities 10 708 Carlos Guestrin 2006 16 Loopy Belief Propagation on Pairwise Markov Nets Coherence Difficulty Intelligence Grade SAT Letter What if we apply BP in a graph with loops Happy Job send messages between pairs of nodes in graph and hope for the best What happens evidence goes around the loops multiple times may not converge if it converges usually overconfident about probability values But often gives you reasonable or at least useful answers especially if you just care about the MPE rather than the actual probabilities 10 708 Carlos Guestrin 2006 17 Coherence More details on Loopy BP Difficulty Intelligence Grade Numerical problem Letter messages 1 get multiplied together as we go around the loops numbers can go to zero normalize messages to one SAT Happy Job Zi j doesn t depend on Xj so doesn t change the answer Computing node beliefs estimates of probs 10 708 Carlos Guestrin 2006 18 An example of running loopy BP 10 708 Carlos Guestrin 2006 19 Coherence Convergence Difficulty Intelligence Grade SAT Letter Happy Job If you tried to send all messages and beliefs haven t changed by much converged 10 708 Carlos Guestrin 2006 20 Non Convergence of Loopy BP Loopy BP can oscillate oscillations can small oscillations can be really bad Typically if factors are closer to uniform loopy does well converges if factors are closer to deterministic loopy doesn t behave well One approach to help damping messages new message is average of old message and new one often better convergence but when damping is required to get convergence result often bad 10 708 Carlos Guestrin 2006 graphs from Murphy et al 99 21 Loopy BP in Factor graphs What if we don t have pairwise Markov nets 1 2 Transform to a pairwise MN Use Loopy BP on a factor graph A ABC B ABD C D BDE E CDE Message example from node to factor from factor to node 10 708 Carlos Guestrin 2006 22 Loopy BP in Factor graphs From node i to factor j A F i factors whose scope includes Xi ABC B ABD C D BDE E CDE From factor j to node i Scope j Y Xi 10 708 Carlos Guestrin 2006 23 What you need to know about loopy BP Application of belief propagation in loopy graphs Doesn t always converge damping can help good message schedules can help see book If converges often to incorrect but useful results Generalizes from pairwise Markov networks by using factor graphs 10 708 Carlos Guestrin 2006 24
View Full Document
Unlocking...