Focused Belief Propagation for Query-Specific InferenceAnton Chechetka Carlos GuestrinCarnegie Mellon University Carnegie Mellon UniversityAbstractWith the increasing popularity of large-scale probabilistic graphical models, even“lightweight” approximate inference methodsare becoming infeasible. Fortunately, oftenlarge parts of the model are of no immediateinterest to the end user. Given the variablethat the user actually cares about, we showhow to quantify edge importance in graphicalmodels and to significantly speed up infer-ence by focusing computation on importantparts of the model. Our algorithm empiri-cally demonstrates convergence speedup bymultiple times over state of the art.1 INTRODUCTIONProbabilistic graphical models (PGMs) have shownmuch success in modeling complex systems, from pro-tein folding to sensor networks (Yanover and Weiss,2002, Deshpande et al., 2004). Increasingly, applica-tions require the use of large-scale graphical models.For example, a model of a relatively small academicdepartment can have millions of factors (Richardsonand Domingos, 2006). With such models, even rela-tively fast approximate inference techniques take manyhours to finish. We argue that there exists a signifi-cant inference opportunity that remains unexploitedby existing algorithms: often, very few variables of thePGM are actually of interest to the end user. In thispaper, we show how exploiting information on whichvariables actually matter to the end user can dramat-ically speed up the inference.In many real-life PGMs the majority of unknown vari-ables serve only for modeling convenience, but do notdirectly affect the end user decisions. For example, inan automated system for patient monitoring (BeinlichAppearing in Proceedings of the 13thInternational Con-ference on Artificial Intelligence and Statistics (AISTATS)2010, Chia Laguna Resort, Sardinia, Italy. Volume 9 ofJMLR: W&CP 9. Copyright 2010 by the authors.et al., 1988), the only variable of direct interest may bewhether the patient needs immediate attention of thehospital staff. In a smart home setting (Pentney et al.,2006), the variable of interest may be whether a cer-tain room is likely to be occupied in the near future: tosave energy, the smart home would turn the air condi-tioning off in rooms that are not likely to be occupiedsoon. However, an implicit assumption of the stan-dard belief propagation (Pearl, 1988) variants, such asresidual belief propagation (RBP) (Elidan et al., 2006)or residual splash BP (Gonzalez et al., 2009) is thatevery variable marginal is equally important. There-fore, a lot of computation is often wasted on refiningbeliefs over parts of the model that have very littleeffect on the query.In this paper, we introduce a novel principled notion ofimportance of PGM edges to the query marginal. Un-like existing edge sensitivity estimates (Kjaerulff, 1993,Choi and Darwiche, 2008), our edge importance val-ues can be computed efficiently. Based on our notion ofedge importance, we propose an extension of RBP thatfocuses computation on the areas of the model thatare likely to affect the inference result over the querythe most. Moreover, computing edge importance canbe done on-demand, eliminating the need to precom-pute importance values for all the edges in advance andpreserving the anytime nature of BP. We show empir-ically on real-life large-scale graphical models that ouralgorithm, query-specific belief propagation (QSBP),converges several times faster than RBP.2 BACKGROUNDWe briefly review a particular formalism of probabilis-tic graphical models, namely factor graphs (for details,see Koller and Friedman, 2009), and loopy belief prop-agation, an approximate inference algorithm.Probabilistic graphical models represent factor-ized probability distributions, where the distributionP (X ) over a large set of random variables X is decom-posed into a product of low-dimensional functions:P (X ) =1ZYfα∈Ffα(Xα), (1)Focused Belief Propagation for Query-Specific Inferencewhere1every Xα⊆ X is a subset of X (typically,|Xα|  |X |), fα≥ 0 are factors and Z is the nor-malization constant. A probabilistic graphical modelis a combination of the factorized distribution (1) andgraphical structure induced by the factors fα. Sev-eral alternative PGM formulations exist, dependingon the type of graphs being used. Here, we use fac-tor graphs: given the factorized distribution (1),the corresponding factor graph is a bipartite graph({X , F}, E) with one node for every factor fα∈ F andevery random variable Xi∈ X , and an undirected edge(α−i) for every pair of fαand Xisuch that Xi∈ Xα(see Fig. 1(a) for an example).The central problem of this paper is, given the factorgraph G and query variables Q to find the marginaldistribution P (Q). Unfortunately, this problem ofprobabilistic inference is known to be #P-completein the exact case and NP-hard in the approximatecase (Roth, 1996). Thus, we will address the prob-lem of improving the convergence speed of belief prop-agation (Pearl, 1988), an approximate inference algo-rithm.Loopy belief propagation (LBP), first proposedby Pearl (1988), is an algorithm for approximate infer-ence in factor graphs, which has been very successfulin practice (McEliece et al., 1998, Yedidia et al., 2003).Let Γαbe the set of neighbors of node α in a factorgraph. LBP is an iterative algorithm that repeatedlyupdates the messages mα−ifrom factors fαto theirrespective variables Xiuntil convergence, as follows:m(t+1)α−i(xi) ∝Xxα\xifα(xα)Yj∈Γα\i˜P(t)(xj)m(t)α−j(xj), (2)where˜P (·) are the estimates of single-variablemarginals defined as˜P (Xi= xi) ∝Yα∈Γimα−i(xi). (3)LBP is guaranteed to converge to exact variablemarginals on graphs without cycles, but there are fewguarantees for general factor graphs. Nevertheless,LBP beliefs are often successfully used instead of truemarginals in applications (Yanover and Weiss, 2002).Instead of directly computing an approximation to thequery marginal P (Q), loopy BP computes a set ofsingle-variable marginals˜P (Xq) . The query marginalis then approximated as˜P (Q) ≡QXq∈Q˜P (Xq) .1Notation: we will denote individual variables with reg-ular font capital letters and index using Latin subscripts(Xi, Xj, . . . ), sets of variables with bold font capital let-ters and index using Greek subscripts (Xα, Xβ, . . . ) anddenote the individual assignments with lower case letters(Xi= xi, Xα= xα).iαjkrsβγδ(a) An