Anytime Exact Belief Propagation
Gabriel Azevedo Ferreira Quentin Bertrand Charles Maussion Rodrigo de Salvo Braz
cs.AI






Anytime Exact Belief Propagation
    Gabriel Azevedo Ferreira, Quentin Bertrand, Charles Maussion, Rodrigo de Salvo Braz

Artificial Intelligence Center

SRI International

Menlo Park CA, USA 


    December 30, 2023
=================================================================================================================================================================



Statistical Relational Models and, more recently, Probabilistic Programming,
have been making strides towards an integration of logic and probabilistic reasoning.
A natural expectation for this project is that a probabilistic logic reasoning algorithm reduces to a logic reasoning algorithm when
provided a model that only involves 0-1 probabilities,
exhibiting all the advantages of logic reasoning such
as short-circuiting, intelligibility, and the ability to provide proof trees for a query answer.
In fact, we can take this further and require that these
characteristics be present even for probabilistic models
with probabilities near 0 and 1, with graceful degradation
as the model becomes more uncertain.
We also seek inference that has amortized constant time complexity
on a model's size (even if still exponential in the induced width of a more directly relevant portion of it) so that it can be applied to huge knowledge bases
of which only a relatively small portion is relevant to typical queries.
We believe that, among the probabilistic reasoning algorithms, Belief Propagation is the most similar to logic reasoning:
messages are propagated among neighboring variables,
and the paths of message-passing 
are similar to proof trees. However, Belief Propagation
is either only applicable to tree models, or approximate
(and without guarantees) for precision and convergence.
In this paper we present work in progress on an Anytime Exact Belief Propagation algorithm
that is very similar to Belief Propagation but is exact
even for graphical models with cycles,
while exhibiting soft short-circuiting, amortized constant time complexity in the model size, and which can provide probabilistic proof trees.





§ INTRODUCTION


Statistical Relational Models <cit.> and, more recently, Probabilistic Programming,
have been making strides towards probabilistic logic inference algorithms that integrate logic and probabilistic reasoning.
These algorithms perform inference
on probabilistic logical models,
which generalize regular logical models by containing formulas that have a probability of being true, rather than always being true.

While Statistical Relational Models and Probabilistic Programming focus on higher-level representations such as relations and data structures,
even regular graphical models such as Bayesian networks can
be thought of as probabilistic logic models,
since conditional probability distributions (or factors,
for undirected models) can be described by formulas
and therefore thought of as probabilistic formulas.
This paper focuses on regular graphical models
that will later serve as a basis for higher-level probabilistic logic
models (as further discussed in the conclusion).

Naturally, probabilistic inference algorithms must be able to perform inference
on purely logic models, since these can be seen as 
probabilistic logic models whose formulas have probability 1
of being true.
In this case, it is desirable that the probabilistic inference algorithms  reduce to logic reasoning
in a way that exploits the logic structure of the model nearly as efficiently
as pure logic reasoning algorithms would.
In fact, we should expect even more: if a model (or part of it)
is near-certain (with probabilities close to 0 and 1),
then the model is very close to a purely logical model
and it is reasonable to expect a probabilistic inference algorithm to
exploit the logical structure to some degree,
with graceful degradation as the model becomes more uncertain.

Short-circuiting is a type of structure that is an important source of efficiency for logic reasoning.
A formula is short-circuited if its value can be determined
from the value of only some of its sub-formulas.
For example, if a model
contains the formula A ⇐ B ∨ C ∨ D and B happens to be true, then a logic reasoning algorithm can conclude that A is true without having to decide whether C and D are true.
However, if a probabilistic reasoning algorithm knows P(A | B ∨ C ∨ D) = 1 and that P(B) = 0.9,
it will typically still need to compute P(C) and P(D) in order to compute P(A),
even though it is already possible to affirm that P(A) ≥ 0.9
without any reasoning about C and D.
Providing such a bound can be considered a soft short-circuiting that
approximates logical short-circuiting as probabilities get closer to 0 and 1, but such ability is absent from most probabilistic inference
methods.







Soft short-circuiting serves as a basis for an anytime, incremental
algorithm that trades bound accuracy for time. Given more time,
the algorithm may determine that P(C) ≥ 0.8 independently of B,
perhaps by recursively processing another rule P(C | E ∨ F),
which allows it to increase its lower bound P(A) ≥ 0.98,
a tight bound obtained without ever reasoning about some
potentially large parts of the model (in this case, rules involving D
or adding information about C).

There are several probabilistic inference algorithms, discussed in
Section <ref>, that produce bounds on query probabilities.
However, we find that most of these algorithms do not exhibit another
important property of logic reasoning algorithms:
a time complexity for inference that is amortized constant in the size of the entire model (although still exponential
on the induced width of the portion of the model
that is relevant for computing the current bound).
This is achieved by storing formulas in a model in hash tables indexed by the variables they contain, and looking up formulas only as needed
during inference as their variables come into play.
An important application for 
probabilistic logic reasoning in the future is reasoning
about thousands or even millions of probabilistic rules
(for example in knowledge bases learned from the Web such as NELL <cit.>),
for which this property will be essential.

Finally, we are also interested in a third important
property of logic reasoning algorithms:
the ability to produce an intelligible trace of its inference
(such as a proof or refutation tree)
that serves as a basis for explanations
and debugging.
In probabilistic reasoning, Belief Propagation
is perhaps the closest we get to this, since local message-passing
is easily understood and the tree of messages can be used as 
a proof tree. However, BP only returns correct marginal probabilities
for graphical models without cycles, 
and non-guaranteed approximation and convergence for general graphical
models. 

In this paper, we present work in progress on Anytime Exact Belief Propagation,
an algorithm that exhibits the three properties described above:
it incrementally computes bounds on marginal probabilities that
can be provided at any time, whose accuracy can be traded off for time,
and that eventually converge to the exact marginal;
it has time complexity amortized constant in the size of the entire model;
and it produces a tree of local messages that can be used to 
explain its conclusion.



§ RELATED WORK



The most obvious candidates for probabilistic logic reasoning approaches
that exhibit logic properties with graceful degradation are the ones
based on logic programming: 
Bayesian Logic Programs <cit.>,
PRISM <cit.>, 
Stochastic Logic Programs <cit.>,
and ProbLog <cit.>.
While these approaches can be used with sampling, they typically
derive (by regular logic programming methods)
a proof tree for the query and evidence in order to determine which portion of the model is qualitatively relevant to them.
Only after that does the probabilistic reasoning starts.
This prevents selecting portions of the model based on quantitative relevance.

More recently, the ProbLog group has proposed two methods for anytime inference:
<cit.>
successively finds multiple explanations for a query,
each of them narrowing bounds on the latter's probability.
However, finding an explanation requires inference on the entire model,
or at least on a qualitatively relevant portion that may include
quantitatively irrelevant knowledge.
<cit.>
proposes a method based on forward reasoning with iterative deepening.
Because the reasoning goes forward, there is no clear way to limit the inference
to the portion most relevant to a query (which is a form of backward inference),
and no selection for more likely proofs.

Our calculation of bounds is equivalent to the one presented in 
<cit.>,
but that work does not attempt to focus on relevant portions of a model
and does not exploit the graphical model's factorization as much as our method and Variable Elimination do.
Box propagation 
<cit.> 
propagates boxes, which are looser bounds
than ours and Leisink & Kappen's bounds.
In fact, their method can easily use these tighter bounds, but in any case
it does not deal with cycles, stopping the unrolling of the model (the Bethe tree) once
a cycle is found. Ihler <cit.>
presents a similar method that does not stop
when a cycle is found, but is not guaranteed to converge to the exact marginal.

Liu et al <cit.>
present a method very similar to ours based on growing an AND-OR search tree
from the query and bounding the not-yet-processed remaining of the model.
As more of the tree is expanded, the better the bounds become.
The main difference from our method is that the AND-OR search tree has a child
per value of each random variable, making it arguably less intelligible
and harder to use as a proof tree and to generalize to richer representations such as
Statistical Relational Models.



§ BACKGROUND




 §.§ Graphical Models


Graphical models are a standard framework for reasoning with uncertainty.
The most common types are Bayesian networks
and Markov networks.
In both cases, a joint probability distribution
for each assignment tuple to N random variables
is defined as a normalized product of non-negative real functions {ϕ_i}_i∈ 1..K,
where 1..K is short for {1,…,K},
each of them applied to a subtuple _i of :[For simplicity, we use the same symbols for both random variables and their values, but the meaning should be clear.]

    P() = 1/Z∏_i=1 ^K ϕ_i(_i),

where Z is a normalization constant equal to ∑_∏_i ϕ_i(_i).
Functions ϕ_i are called factors
and map each assignment on their arguments to a potential,
a non-negative real number that represents
how likely the assignment _i is.
This representation is called factorized due to its
breaking the joint probability into this product.
In Bayesian networks, K = N and factors are conditional probabilities
P(X_i | Pa_i), for each random variable X_i in , where Pa_i
are its parents in a directed acyclic graph.

For succinctness, we often do not explicitly write the arguments to factors:

    P() = 1/Z∏_i ϕ_i(_i) = 1/Z∏_i ϕ_i.


The marginal probability (MAR) problem consists of computing

    P() = ∑_∖ P(),

where  is a subtuple of containing queried variables, and ∑_∖ is the summation over all variables in but not in .
It can be shown that P()=1/Z_∑_∖∏_i ϕ_i
for Z_ a normalization constant over .
Therefore, because Z_ is easily computable if || is small,
the problem can be simply reduced to computing a summation over products of factors, which the rest of the paper focuses on.

We denote the variables (or neighbors) of a factor ϕ or set of factors M
as Var(ϕ) and Var(M).
The neighbors neighbors_M(V) of a variable V given a set of factors M is defined as the set of factors {ϕ∈ M : V ∈ Var(ϕ) }.
We call a set of factors a model.
The factor graph of a model M is the graph with variables
and factors of M as nodes and with an edge between
each factor and each of its variables.



 §.§ Belief Propagation


Belief Propagation <cit.>

is an algorithm that computes the marginal probability
of a random variable given a graphical model whose factor graph
has no cycles.




Let M be a set of factors and P_M be 
the probability distribution it defines.
Then, for a set of variables Q ⊆ Var(M),
we define:


    P_M(Q) ∝ m^M_. ← Q (note that m^M_ϕ← Q does not depend on ϕ).
    
        m^M_V ←ϕ = ∑_Sϕ∏_S^j ∈ S m^M^j_ϕ← S^j
            where {S^1,…,S^n} Var(ϕ) ∖ V,
            M^j  is the set of factors in M ∖{ϕ} connected to S^j,
    
        m^M_ϕ← V = ∏_ϕ^j ∈ neighbors_M(V) m^M^j_V ←ϕ^j, 
            where {ϕ^1,…,ϕ^n} neighbors_M(V),
            M^j  is the set of factors in M connected to ϕ^j.
	

Note that each message depends on a number of sub-messages.
Since the factor graph is a tree (it has no cycles),
each sub-message involves a disjoint set of factors M^j.
This is crucial for the correctness of BP because it allows the computation to be separately performed for each branch.

If a graphical model has cycles, an iterative version of BP, loopy BP, can still be applied to it
<cit.>.
In this case, since a message will eventually depend on itself, we use its value from a previous iteration,
with random or uniform messages in the initial iteration.
By iterating until a convergence criterion is reached, loopy BP provides distributions, called beliefs, that in practice often approximate the marginal of the query well.
However, loopy BP is not guaranteed to provide a good approximation, or even to converge.




 §.§ Anytime Belief Propagation




Even though BP is based on local computations between neighboring nodes,
it only provides any information on the query's answer once it has analyzed the entire model,
even if some parts of the model have a relatively small influence on the answer.
This goes against our initial goal  providing information on the query's answer even after analyzing only a (hopefully more relevant) portion of the model.




Anytime BP <cit.>
is an algorithm based on (loopy) BP that
computes iteratively improved bounds on a message.
A bound (following definitions in <cit.>) on a message m is any set of messages
to which m is known to belong.
Anytime BP (and, later, Anytime Exact BP)
only use bounds that are convex sets of messages,
and that can therefore be represented
by a finite number of messages (the bounds extrema),
the convex hull of which is the entire bound.
Initially, the bound on a message on a variable V
is the simplex (V),
the set of all possible probability distributions on V,
and whose extremes are the distributions that place
the entire probability on a single value.
For example, if V is a boolean random variable,
its simplex
is the set {V = true10, V = false10}.

It turns out that the computation of a message m given its sub-messages
is a convex function. Therefore, given the bounds on sub-messages
represented by their extremes, we can compute a bound b(m) on m
by computing the extremes of this bound,
each extreme being equal to the message computed from
a combination of extremes to the sub-messages.
This provides a finite set of extremum messages that define b(m)
and can be used to compute further bounds.

Figure <ref> shows an example of Anytime Belief propagation on a factor network.
The algorithm provides increasingly improving bounds on the belief m(A)
on query A,
by first returning the simplex (A) as a bound,
then returning the bound computed from simplex sub-messages,
and then successively refining this bound by selecting one or more of the sub-messages,
obtaining tighter bounds on these sub-messages, and recomputing
a tighter bound for m(A).
At every step from (b) to (d), factors are included in the set so as to complete some random variable's blanket
(we do not show the expansions from (d) to (e), however, only their consequences).
We include the table for factor 
ϕ_1 but omit the others.
For simplicity, the figure uses binary variables only and shows
bounds as the interval of possible probabilities for value 1, but it applies to multi-valued variables as well.

This incrementally processes the model from the query,
eventually processing it all and producing an exact bound
on the final result.
Like BP, Anytime BP is exact only for tree graphical models,
and approximate for graphical models with cycles
(in this case, the bounds are exact for the belief,
that is, they bound the approximation to the marginal).
The main contribution of this paper is Anytime Exact BP,
which is a bounded
versions of BP that is exact for any graphical models,
presented in Section <ref>.



 §.§ Cycle Cutset Conditioning


If a graphical model has cycles, an iterative version of BP, loopy BP, can still be applied to it
<cit.>.
However, loopy BP is not guaranteed to provide a good approximation, or even to converge.

Cycle cutset conditioning <cit.> is a way of using BP to solve a graphical model M with cycles.
The method uses the concept of absorption:
if a factor ϕ_i(_i) has some of its variables ⊆_i set
to an assignment , it can be replaced by a new factor ϕ',
defined on ∖ and ϕ'(_i ∖) = ϕ_i(_i ∖, ).
Then, cutset conditioning consists of selecting C, a cycle cutset random variables
in M such that, when fixed to a value c, gives rise through absorption in all factors involving variables in C to a new graphical model M_c without cycles and defined on the other variables ∖ C
such that P_M_c(∖ C) = P_M(∖ C, c).
The marginal P_M(Q) can then be computed by
going over all assignments to C and solving the corresponding
M_c with BP:

    P_M(Q)     = ∑_∖ Q P_M() 
        =  ∑_c ∑_∖ (Q ∪ C) P_M(∖ C, c) 
        =  ∑_c ∑_∖ (Q ∪ C) P_M_c(∖ C)
        =  ∑_c P_M_c(Q)  (using BP on M_c).


Figure <ref> (a) shows a model with
a cycle. Panel (b) shows how cutset conditioning for cutset {A}
can be used to compute P(Q): we successively fix A to each
value a in its domain, and use absorption to
create two new factors ϕ_1' = ϕ_1(C,a) and ϕ'_2(E) = ϕ_2(E,a). This new model does not contain any cycles and BP computes P(Q,a). The overall P(Q) is then computed as ∑_a P(Q,a).
Now, consider that the messages computed across the reduced model
that depend on a can be thought of as functions of a.
From that angle, the multiple applications of BP for each a
can be thought of as a single application of BP in which
A is a fixed, free variable that is not eliminated and
becomes a parameter in the propagated messages (panel (c)).
This has the advantage of computing all messages that do not
depend on a only once.

While cutset conditioning solves graphical models with cycles exactly,
it has some disadvantages.
Like standard BP, cutset conditioning requires the entire model to be processed before providing useful information.
In fact, simply finding a cutset already requires going over the entire model, before inference proper starts.
Besides, its cost grows exponentially in the size of the cutset,
which may be larger than the induced tree width.
Our main proposal in this paper, Anytime Exact Belief Propagation,
counters those disadvantages by processing the model
in an incremental way, providing a hard bound around the exact
solution, determining the cutset during inference,
and summing out cutset variables as soon as possible
as opposed to summing them out only at the end.



§ ANYTIME EXACT BELIEF PROPAGATION



We are now ready to present the main contribution of this paper,
Anytime Exact Belief Propagation (AEBP).
Like cutset conditioning, the algorithm applies
to any graphical models, including those with cycles.
Unlike cutset conditioning, it does not require
a cutset to be determined in advance,
and instead determines it on the fly,
through local message-passing.
It also performs a gradual discovery of the model, providing bounds on the final result as it goes.
This is similar to Anytime BP, but
Anytime Exact BP, as the name implies,
provides bounds on the exact query marginal probability
and eventually converges to it.

We first provide the intuition for Anytime Exact BP through an example.
Consider the graphical model in Figure <ref> (the full model is shown in (e)).
If we simply apply Anytime BP to compute P(Q), messages will be computed in an infinite loop.
This occurs because Anytime BP has no way of identifying loops.
AEBP, on the other hand, takes an extra measure in this regard: when it requests a new bound from one of the branches
leading to a node, it also provides the set of factors known so far to belong to the other branches.
Any variable that is in the branch and is connected to these external factors must necessarily be a cutset variable.
Upon finding a cutset variable C, AEBP considers it fixed and does not sum it out,
and resulting messages are functions of C (as well we the regular variable for which we have a message).
Branches sharing a cutset variable C will therefore return bounds that are functions of C.
Cutset variables are summed out only after messages from all branches containing C are collected.

While the above procedure is correct, delaying the sum over cutset variables until the very end
is exponentially expensive in the number of them.
Figure <ref>
shows an example in which a cutset variable (G) that occurs only in an inner cycle
is summed out when that cycle is processed (at node E), while the more global cutset variables (C and F)
are summed out at the end, when the more global cycle is processed (at node A).




Algorithm 1 presents the general formulation.
It works by keeping track of each component, that is,
a branch of the factor graph rooted in either a variable or factor,
its Node,
and computing a message from Node to some other requesting node
immediately outside the component.
Each component is initially set with the external factors
that have already been selected by other components.
The message is on a variable V (this is Node itself if Node
is a variable, and some argument of Node if it is a factor).
In the first update, the component sets the bound to the simplex on V
and creates its children components: if Node is a variable,
the children components are based on the factors on it that are not already external;
if it is a factor, they are based on its argument variables.

From the second update on, the component selects a child,
updates the child's external factors by including that child's
siblings external factors,
updates the child's bound,
updates its own set of factors by including the child's newly discovered
factors, and computes a new bound.
If Node is a factor, this is just the product of the bounds of its children.
If Node is a variable, this is obtaining by
multiplying ϕ and children bounds, and summing out
the set of variables 
S.
S is the set of variables that occur only inside ,
(which excludes V and cutset variables connected to external factors,
but does include cutset variables that occur only inside this component.
This allows cutset variables to be eliminated as soon as possible in the process.
To compute the marginal probability for a query Q,
all that is needed is to create a component for Q without
external factors and update it successively until it converges to
an exact probability distribution. 
During the entire process, even before convergence, this component tree can be used as a trace of the inference process, indicating how each message has been computed from sub-messages so far, similarly to a probabilistic proof or refutation tree in logic reasoning.


	Update(𝒞)
	is a component, defined as a tuple 

	(V,Node, Bound, M, ExteriorFactors, Children)

	where:
	V: the variable for which a message is being computed
	Node: a variable or factor from which the 

	      message on variable V is being computed
	Bound: a bound on the computed message
	Factors: the set of factors selected for this message already
	ExternalFactors: set of factors already observed outside

	the component, and used to identify new cutset variables.
	Children: components for the sub-messages of this message.
	first update Bound (V)
	Node is variable Factors factors with Node as argument 

		 and not in ExternalFactors	
	Children components based on each 

	factor in Factors 

	and ExternalFactors set 

	to .ExternalFactors
	 // Node is factor ϕ
	Bound ∑_C ∪ Sϕ∏_Ch ∈ Children
	Children components based on each variable

argument (that is, neighbor) of ϕ

and ExternalFactors set 

to .ExternalFactors ∖{ϕ}
	Child ← chooseNonConvergedChild(Children)
	Child.ExternalFactors

	        ExternalFactors   ∪

	            ⋃_Ch ∈ Children ∖{Child} Ch.Factors
	Update(Child)
	Factors  Factors ∪ Child.Factors
	ChildrenBoundProduct ∏_Ch ∈ Children Ch.Bound
	Node is variable Bound  ChildrenBoundsProduct
	 // Node is factor ϕ
	S variables in ChildrenBoundProduct 

	not in any factor in ExternalFactors
	Bound ∑_Sϕ∏_Ch ∈ Children Ch.Bound
	
Algorithm 1: Anytime Exact Belief Propagation.





neuron/.style=shape=circle, minimum size=.9cm, inner sep=0, draw, font=,
            			 io/.style=neuron, fill=gray!20
            

































§ CONCLUSION


We presented our preliminary work on Anytime Exact Belief Propagation,
an anytime, exact inference method for graphical models that provides
hard bounds based on a neighborhood of a query.
The algorithm aims at generalizing the advantages of logic reasoning
to probabilistic models, even for dependencies that are not certain, but near certain.

Future work includes finishing the implementation, evaluating it on
benchmarks, and generalizing it higher-level logic representations
such as relational models and probabilistic programs. To achieve that,
we will employ techniques from the lifted inference literature
<cit.>
as well as probabilistic inference modulo theories
<cit.>.

aaai







§ BELIEF PROPAGATION WITH SEPARATOR CONDITIONING: AN EXACT MESSAGE-PASSING INFERENCE ALGORITHM FOR ANY GRAPHICAL MODEL


Belief Propagation is equivalent to the inference calculation  when the graphical model does not present any cycles. 

The same can not be stated for general graphical models, where loopy belief propagation algorithm may not converge. If it does,  not necessarily it converges to an optimal solution.

We based our anytime algorithm, therefore, upon an adaptation of the belief propagation, where we “break” the cycles by summing  out some variables in a later step of the process. This provides us with an exact elimination algorithm.

    

 §.§ Definitions

We provide some definitions  that  are useful in defining the algorithm.
    

  §.§.§ Partition

    Let M be a set of factors. A partition Pt_M of M id a tuple of nonempty sets of factors
    
    Pt_M = (Pt^1,…,Pt^k)

    such that each element of M is exactly in one of the subsets Pt^i. That is to say that :
    
    
    
  * for i = 1,…,k  Pt^i ≠∅
    
  * for i,j = 1,…,k  i≠ j  ,   Pt^i∩ Pt^j = ∅
    
  * ⋃_i=1,…,kPt^i=M
    
    

  §.§.§ Separator

    
	A separator of set of a partition Pt_M is defined as following:

    Sep(Pt_M) ={V:    ∃ i, j ,  i≠ j,  s.t. 
        V∈ Var(Pt^i)∩ Var(Pt^j) }
  
	
	

 §.§ BP with conditioning

	Let M be a set of factors.
	Then, for a set of variables Q ⊆ Var(M),
	we can employ Belief Propagation with Separator Conditioning (S-BP) to compute P(Q):
	
	
    P_M(Q) ∝ m^M_. ← Q (note that m^M_ϕ← Q does not depend on ϕ).
    
    		    m^M_V ←ϕ = ∑_C ∑_S∖ Cϕ∏_S^j ∈ S m^Pt^j_ϕ← S^j ∪ C
            where {S_1,…,S_n} = Var(ϕ) ∖ V,
           (Pt^1,…,Pt^n) is any n-partition of M ∖{ϕ},
           C is the Sep(Pt∖{ϕ}),
    
    		    m^M_ϕ← V = ∑_C ∏_ϕ^j ∈ neighbors_M(V) m^Pt^j_V ∪ C ←ϕ^j, 
            where  neighbors_M(V)  are the factors on V in M, 
           (Pt^1,…,Pt^n) is any n-partition of M such that ϕ^j ∈ Pt^j,
           C is Sep(Pt)∖ V.
	
	
	
		We prove that m^M_ϕ← V∝ P_M(V) and m^M_V ←ϕ∝ P_M(V) by induction on the size of M.
		If |M|=0, m^M_ϕ← V = 1, which when normalized is equal to Uniform(V) = P_M(V).
		m^M_V ←ϕ is undefined for |M|=0, but for |M|=1 (that is, M={ϕ}),
		C=∅ and m^M_V ←ϕ = ∑_S ϕ(V,S) ∝ P_M(V).
		
		If |M|>0, 
		
    m^M_ϕ← V    = ∑_C ∏_ϕ^j ∈ neighbors_M(V) m^Pt^j_V ∪ C ←ϕ^j
       ∝∑_C ∏_ϕ^j ∈ neighbors_M(V) P_Pt^j(V ∪ C)
        = ∑_C ∏_ϕ^j ∈ neighbors_M(V)∑_Var(Pt^j)∖(V ∪ C)Pt^j
        = ∑_C ∑_Var(M)∖(V ∪ C)∏_ϕ^j ∈ neighbors_M(V) Pt^j
        = ∑_Var(M)∖ V∏_ϕ^j ∈ neighbors_M(V) Pt^j
        = ∑_Var(M)∖ V M
       ∝ P_M(V)

        
		
    m^M_V←ϕ    = ∑_C ∑_S ∖ Cϕ∏_S^j ∈ S m^Pt^j_ϕ← S^j ∪ C
       ∝∑_C ∑_S ∖ Cϕ∏_S^j ∈ S P_Pt^j(S^j ∪ C)
        = ∑_C ∑_S ∖ Cϕ P_M ∖ϕ(S ∪ C)
       ∝∑_C ∑_S ∖ Cϕ∏_ϕ' ∈ M ∖ϕϕ'
       ∝∑_C ∑_S ∖ C P_M(S ∪ C)
        = ∑_S ∪ C P_M(S ∪ C)
        = ∑_Var(M) ∖ V P_M(Var(M) ∖ V)
        = P_M(V).

	
	
	S-BP reduces to regular BP if the model does not contain loops. Otherwise,
	it uses separators to ensure incoming messages are
	computed on components (sets of factors) that are disjoint given a separator set.
	The separator set for a message is marginalized out at the end of its computation.
	
	Unlike BP, S-BP is not a deterministic algorithm, since there may be several
	choices for Pt.
	It can be made deterministic by representing the set of factors M
	as a tree of all partitions to be used in all message computations.
	Later, we will use partial specifications of M in this manner
	to represent bounds on M.
	


§ BOUNDING FUNCTIONS

	
	The following definition introduces the concept of iteratively bounding the value f(a) of a function f for a unknown domain element a.
	A bound on some mathematical object α is simply some set containing α.
	A bounding function does two things given a bound on a: it computes a bound on f(a),
	and computes a strictly tighter bound (a smaller set) on a in the process.
	This yields a bounding sequence generated by an iterative process in which partial or complete ignorance on a and therefore f(a) leads to tighter and tighter bounds on a and f(a) until we converge to the exact values.
	
	When we apply this framework to  our particular application of exact BP, a will be the model M and the cutset Q, and f will be the messages on them. The bounds on (M,Q) will be based keep partial descriptions of M and Q and convergence is obtained when they are fully analyzed. We will have a bound on the messages during the entire process, making the algorithm anytime. However, we define the notions of bounding functions and sequences in an abstract way that applies to any functions and sets, and those in probabilistic inference are just one case.
	
	The intuition behind a bounding function is that, instead of receiving an exact argument a,
	it receives a set of possible arguments A' ⊆ A containing a (a bound on a), and returns the possible results B = f(A') (and thus guaranteed to contain f(a)), and also a strictly smaller A”⊂ A' determined during the processing. A” can then be fed again to f̅ to obtain an even better bound on f(a).
	
	
		Let f : A → B be any function, and a ∈ A.
		A function f̅ : 2^A → (2^A, 2^B) is a bounding function of f
		with respect to a if, for any A' ⊆ A for which a ∈ A',
		f̅(A') = (A”, B) satisfies a ∈ A”, A”⊂ A', and B = { f(a”) : a”∈ A”}.
	
	
	
		
		Let A be a finite, discrete set,
		f : A → B be any function with domain A,
		and f̅ a bounding function of f.
		Then there is n ∈ℕ and a sequence defined by
		
    A_0 = A; B_0 = B 
        (A_i , B_i) = f̅(A_i - 1), i = 1,…,n

		such that, for all i ≥ 1,
		B_i ⊂ B_i-1, f(a) ∈ B_i, and B_n = { f(a) }.
	
	
	
		The existence of the sequence and its properties, except for B_n = {f(a)}, comes directly from the definition
		of a bounding function.
		We prove B_n = {f(a)} by induction on |A_i|.
		If |A_i|=1, A_i={a} and B_i = {f(a)}
		by the definition of bounding function.
		If |A_i| > 1, then |A_i+1| < |A_i|, and by induction
		it defines a sequence from (A_i+1, B_i+1) to (A_n, B_n) such that B_n = { f(a) }.
		Therefore, A_i defines a sequence from (A_i, B_i), (A_i+1, B_i+1) to (A_n, B_n)  such that B_n = { f(a) }.
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	

§ BOUNDED ANYTIME EXACT BP

	
	We now define bounding functions for the message functions in BP.
	
	
		For a carrier set 𝕄, we inductively define partition tree on 𝕄 as either of the following objects:
		
			
			
  * a set 𝕄∖Φ^ext, where Φ^ext⊆𝕄
			(that is to say, a set defined by exclusion).
			
			
  * a tuple (Pt_1,…,Pt_n) of partition trees on 𝕄.
		
	
	A complete partition tree is a partition tree in which all the leaves are equal to 𝕄∖𝕄 = ∅.
	
	
	When 𝕄 is a set of factors, we can annotate a partition tree
	with a set of external factors Φ^ext that do not occur in it, a set
	of external separator variables D^ext present in more than one of its partition sub-trees and
	also in the external factors Φ^ext, and
	a set of internal separator variables D present in more than one of its partition
	subtrees but not in the external factors Φ^ext.

	A partition tree Pt induces a set completion(Pt) all the full partition trees consistent with Pt. A set of full partition trees can be used as a bound on a single, unknown full partition tree.
	
	We will use such bounds, represented by a partial partition tree, as the bounds A_i on an unknown full partition tree passed to bounding functions for the message functions m_ϕ← V and m_V ←ϕ .

	The bounding function obtains a partial partition tree Pt_i representing an unknown full partition tree, chooses an j-th incoming message
	that has not converged yet, obtains a tighter bound Pt^j and a tighter bound B^j_i+1 on
	the respective incoming message, and generates a tighter Pt_i+1 and bound B_i+1 on message as a result.
	
	For fixed V and ϕ, the message calculations m^Pt,D,D^ext_V ←ϕ and m^Pt,D,D^ext_ϕ← V are functions on a complete Pt.
	The bounding functions can be defined as functions on partial Pt as follows:
	
	
		Given a set of factors M and a cutset Q, m̅_V and m̅_V ←ϕ are bounding functions with respect to P_M(Q). (Note that A_0 = 2^𝕄× compl(Q) and B_0 = ℙ(V).)
	
    

	
	
    m̅_V ←ϕ^Pt_i, D_i, D^ext_i = ((Pt_i+1,D_i+1,D^ext_i+1),B_i+1) 
            where 
           if Pt_i is of the form 𝕄∖Φ^ext_i,
               {S_V ←ϕ^1,…,S_V ←ϕ^n} is Var(ϕ) ∖ (V ∪ D^ext_i)
               Pt^j_i+1 is 𝕄∖ (Φ_i^0 ∪{ϕ}), j = 1,…,n
               Pt_i+1 is (Pt^1_i+1,…,Pt^n_i+1)
               B_i+1 is 𝒫(V)
           else
            j =  index of incoming message not yet exhausted
            ((Pt_i+1^j, D_i+1^j, D_i+1^ext,j), B_i+1^j) = m̅_ϕ← S_i^j ∪ D_i^Pt_i^j, D_i^j, D_i^ext
            ((Pt_i+1^k, D_i+1^k, D_i+1^ext,k), B_i+1^k) = ((Pt_i^k, D_i^k, D_i^ext,k), B_i^k),
                                                    k ≠ j 
            D^ext_i+1 = ( ⋃_j D^j_i+1) ∩ Var(Φ^ext_i)
            D_i+1 = ( ⋃_j D^j_i+1) ∖ D^ext_i+1
            B_i+i = ∑_D_i+1∑_S_V ←ϕ∖ D_i+1ϕ∏_j=1^n B_i+1^j

        
        
    m̅_ϕ← V^Pt_i, D_i, D^ext_i = ((Pt_i+1,D_i+1,D^ext_i+1),B_i+1)
            where 
           if Pt_i is of the form 𝕄∖Φ^ext_i,
               {ϕ^1_ϕ← V,…,ϕ_ϕ← V^n} is neighbors_Pt_i(V) ∖{ϕ}
               Pt^j_i+1 is 𝕄∖ (Φ_i^ext∪⋃_k≠ jϕ_ϕ← V^k), j = 1,…,n
               Pt_i+1 is (Pt^1_i+1,…,Pt^n_i+1)
               B_i+1 is 𝒫(V)
           else
            j =  index of incoming message not yet exhausted
            ((Pt_i+1^j, D_i+1^j, D_i+1^ext,j), B_i+1^j) = m̅_V ←ϕ_ϕ← V^j^Pt_i^j, D_i^j, D_i^ext
            ((Pt_i+1^k, D_i+1^k, D_i+1^ext,k), B_i+1^k) = ((Pt_i^k, D_i^k, D_i^ext,k), B_i^k),
                                                    k ≠ j 
            D^ext_i+1 = ( ⋃_j D^j_i+1) ∩ Var(Φ^ext_i)
            D_i+1 = ( ⋃_j D^j_i+1) ∖ D^ext_i+1
           Pt_i+1 is (Pt_1,…,Pt_n)
            B_i+i = ∑_D_i+1∏_j=1^n B_i+1^j
	
	





§ COMPUTING WITH BOUNDS


In the algorithm described on section <ref>, we make two operations that can be specially expensive:


    B_i+1 = {∑_N ϕ(V, N) ∏_N_j ∈ N b^j : b^j ∈ B_i^j }

and

    B_i+i = {∏_j = 1..N b^j : b^j ∈ B_i^j }



One can easily see that the computation of such expressions is not computationally possible in the general case: if we consider bounds with an infinite number of elements there would be an infinite number of computations to do.
However, this can be a relatively inexpensive computation in certain conditions, such as in the case where the B's are convex sets with a finite number of extreme points. In this section we show that these conditions are fulfilled in our case and provide a way to preform this operations.



 §.§ The simplex bound


We define a bound on a query Q as a set of non-normalized probabilities for that query. The simplest and most general bound we can assign to a query is the simplex relative to Q, noted as 𝒫_Q. The simplex is defined as:


    𝒫_Q ≡{ϕ(Q) : Q →ℝ,  ∑_q∈ Qϕ(q) = 1}


One can easily see that a simplex is a convex set. Its extreme points are:


    ext(_Q) = {ϕ : ∃ q∈ Q  s.t. ϕ(q) = 1  and ∀ p ≠ q  ϕ(p) = 0 }

Which is a finite set.



 §.§ Operations with sets (definitions)


This means that the probability distribution of Q can be any function whose sum over the values of Q is equal to one. That makes 𝒫_Q a trivial bound for _M(Q).

We define the product of bounds as the set of products of each term from both sets. The product between a bound and a term is defined the same way.


    B_1 × B_2 ≡{ϕ_1×ϕ_2 : ϕ_1 ∈ B_1, ϕ_2 ∈ B_2}



    B ×ϕ≡{ϕ×ϕ' : ϕ' ∈ B}



We define the normalization operator  in the following manner. Given a convex set functions B:


    (B) = {ϕ/∑_domain(ϕ)ϕ : ϕ∈ B }




 §.§ Proving convexity


Consider a function ϕ : D_ϕ→ℝ, with D_ϕ finite, and B a convex set of functions f:D_B→ℝ with finite extreme points. Let A ⊂ D_ϕ. 
. We prove that:


  * (∑_A ϕ B) is convex 

  * ext((∑_A ϕ B)) ⊂∑_A ϕ ext(B)


We split the proof in two parts:



  §.§.§ 1

we want to prove that: 



  * ∑_A ϕ B is convex :

Consider ψ_1,...,ψ_k ∈∑_A ϕ B. Then ψ_i = ∑_A ϕψ'_i, i = 1,...,k, ψ'_i ∈ B. consider α_j>0, j= 1,..,k such that ∑_jα_j=1.
Then:


    ∑_i= 1,...,kα_iψ_i=∑_i= 1,...,kα_i∑_Aϕψ_i=∑_Aϕ∑_i= 1,...,kα_iψ_i=



    =∑_Aϕ(ψ”) , with ψ”∈ B


This implies that ∑_i= 1,...,kα_iψ_i ∈∑_A ϕ B, i.e, that ∑_A ϕ B is convex.


  * ext(∑_A ϕ B) ⊂∑_A ϕ ext(B)

The proof follows by contradiction.

Consider ψ∈ ext(∑_Aϕ B) and suppose that ψ∉∑_Aϕ ext(B). Then ψ = ∑_Aϕψ', with ψ' = ∑_iα_iψ'_i, ψ'_i ∈ B and α_i>0 summing to 1. Then:


    ψ = ∑_Aϕ∑_iα_iψ'_i = ∑_iα_i(∑_Aϕψ'_i) = ∑_iα_iψ_i


with ψ_i ∈∑_Aϕ B. Then ψ is a convex combination of elements in ∑_Aϕ B, which s a contradiction on the assumption that it is an extreme point.





  §.§.§ 2

we want to prove that: 



  * (B) is convex 

We note ∑_domain(ϕ)ϕ = |ϕ| for any function  ϕ.

Let ψ = ∑_i α_iψ_i be a convex combination of ψ_i∈(B). One can easily see that


    ψ∈(B)  |ψ| = 1  and ψ∝ψ'  for some ψ' ∈ B


We prove that |ψ| = 1 through the following equation:


    |ψ| = |∑_iα_iψ_i| = ∑_iα_i|ψ_i| = ∑_iα_i× 1 = 1


Now we prove the second part of the equivalence stament:

We have ∀ i ,  ψ_i = ψ_i'/|ψ_i'| for some ψ'_i ∈ B. Then:


    ψ = ∑_i α_iψ_i = ∑_iα_i/|ψ_i'|ψ'_i = ∑_iβ_iψ'_i


Where β_i = α_i/|ψ_i'|. Calling N = ∑_iβ_i, we have that ∑_i β_i/Nψ_i ∈ B because it is a convex combination of elements in S. Therefore:


    ψ = N × (∑_i β_i/Nψ_i)    and   ∑_i β_i/Nψ_i ∈ B


Then:


    ψ∝ψ'   for some ψ'∈ B


Which proves that (B) is convex.


  * ext((B)) ⊂ ext(B)

Consider ψ∈(B). Then, ∃ψ' ∈ B  s.t.  ψ = ψ'/|ψ'|. According to Krein-Milman theorem, ψ' = ∑_i=1,...,kα_iψ'_i , α_i>0, ∑_iα_i = 1 and ψ_i'∈  ext(B). Then:


    ψ = ∑_i (|ψ'_i|α_i)(ψ'_i/|ψ'_i|)/|∑_iα_iψ'_i| = ∑_ic_iψ'_i/|ψ'_i|,  with  c_i =  |ψ'_i|α_i /|∑_iα_iψ'_i|


We can easily see that c_i > 0 and ∑_ic_i = 1 and that ψ'_i/|ψ'_i|∈(ext(B)).
Also, (ext(B)) ⊂(B), since ∀ψ' ∈ ext(B),  ψ'/|ψ'|∈(B). Then we have:

    (B) = C.Hull((ext(B)))

Then, because the extreme points of a convex se S are those that are not convex combinations of any others (except 1 × themselves), we have:

    ext((B)) ⊂ ext(B)






 §.§ Storing and computing the following bounds


The operations with bounds can be resumed by applying the expression (∑_Aϕ B) for a certain set of variables A, a factor ϕ and a previous bound B. The last section showed that it suffices to store the extreme points of previous bounds and compute and store the new bound as a result of (∑_Aϕψ) for each ψ∈ ext(B).







