{'fraction_non_alphanumeric': 0.044400638317844736, 'fraction_numerical': 0.010419600112644326, 'mean_word_length': 4.2120841487279845, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Differential Semantics of Lazy AR Propagation

In this paper we present a differential semantics of Lazy AR Propagation (LARP) in discrete Bayesian networks. We describe how both single and multi dimensional partial derivatives of the evidence may easily be calculated from a junction tree in LARP equilibrium. We show that the simplicity of the calculations stems from the nature of LARP. Based on the differential semantics we describe how variable propagation in the LARP architecture may give access to additional partial derivatives. The cautious LARP (cLARP) scheme is derived to produce a flexible cLARP equilibrium that offers additional opportunities for calculating single and multidimensional partial derivatives of the evidence and subsets of the evidence from a single propagation. The results of an empirical evaluation illustrates how the access to a largely increased number of partial derivatives comes at a low computational cost.


INTRODUCTION
Bayesian networks (BNs) (Pearl 1988;Cowell, Dawid, Lauritzen, and Spiegelhalter 1999;Jensen 2001) are efficient knowledge representations for reasoning under uncertainty. Usually, the inference process in a BN proceeds either by message passing in a secondary computational structure (Lauritzen and Spiegelhalter 1988;Shenoy and Shafer 1990;Jensen, Lauritzen, and Olesen 1990) or by direct computations (Shachter 1986;Pearl 1988;Li and D'Ambrosio 1994;Zhang and Poole 1994;Dechter 1996;Darwiche 2003). Darwiche (2003) gives a differential semantics of inference by considering it as the task of computing the value of an algebraic function while Park and Darwiche (2004) based on a similar algebraic function representation give a differential semantics of the HUGIN (Jensen, Lauritzen, and Olesen 1990) and Shenoy-Shafer (Shenoy and Shafer 1990) algorithms.
In this paper we present a differential semantics of Lazy Propagation (LP) (Madsen and Jensen 1999). LP is another join-tree-based algorithm for inference in BNs. The main motivation for this work is to determine the flexibility and suitability of LP w.r.t. computing partial derivatives of the evidence. Computing partial derivatives is an important part of hypothesis driven parameter sensitivity analysis, for instance.
We show how the fundamental properties of LPmaintain decompositions of clique and separator potentials, postpone the elimination of variables for as long as possible, take advantage of barren variables, and exploit independence relations induced by evidence -support efficient calculation of single and multi dimensional partial derivatives of the evidence and subsets of the evidence from a junction tree in equilibrium. Due to space limitations we focus on LARP (Madsen 2004b) where messages are computed using arc-reversal (Shachter 1986). In addition we describe how variable propagation (Jensen 2001) and a cautious propagation scheme (Jensen 1995) support the calculation of additional derivatives. The paper contains an empirical evaluation of the overhead introduced by the cautious propagation scheme.

PRELIMINARIES AND NOTATION
A discrete BN N = (X, G, P) over variables X consists of an acyclic, directed graph G = (V, E) and a set of conditional probability distributions (CPDs) P = {Θ X| π(X) : X ∈ X}. The vertices V of G correspond one-to-one with the variables of X, i.e. X ∼ V. N induces a factorization of the joint probability distribution over X: where π(X) is the set of variables corresponding to the parents of the vertex representing X in G, fa(X) = π(X) ∪ {X}, and Θ X| π(X) is the CPD of X given its parents π(X). We use θ x|π to denote the entry of Θ X| π(X) where X = x and π(X) = π, i.e. (x, π) is a configuration of (X, π(X)) and θ x|π = Θ X=x| π(X)=π . We denote a configuration of (X i , π(X i )) as (x i , π i ) A probability potential φ(X|Y) where X, Y ⊆ X is a non-negative function over X ∪ Y. Let φ(H|T ) be a probability potential with head H = H(φ) and tail T = T(φ), then the domain dom(φ) of φ is defined as dom(φ) = H ∪ T . When the distinction between head and tail variables is not important, we will in- takes on values f(x) = 1 and f(y) = 0 for all y = x and we use f(x) as an abbreviation for f(X = x). If X is not observed, then f(x) = 1/|X|. Hard evidence X = {X = x} enables us to instantiate all potentials φ with X ∈ dom(φ) to reflect X = x reducing the domain size of φ by one. We refer to the instantiation of φ as an application of f(X) on φ. The instantiation of potentials enables us to take advantage of independence relations induced by .

POTENTIALS AND OPERATIONS
Probabilistic inference using LARP proceeds by message passing in a junction tree T = (C, S) where sets of probability potentials are passed between cliques C and separators S. Messages are passed in two flows (collect and distribute) relative to a preselected root R ∈ C. We define the notion of a clique / separator potential (referred to as a potential).

Definition 3.1 [Potential]
A potential on W ⊆ X is a singleton π W = (Φ) where Φ is a set of non-negative real functions on subsets of W.
We call a potential π W vacuous if π W = (∅). The vacuous potential is denoted π ∅ . We define the operations of combination, division, and contraction as follows:

Definition 3.3 [Division]
The division of potentials π W 1 = (Φ 1 ) and π W 2 = (Φ 2 ) denotes the potential on W 1 given by: Notice the simplicity of potential combination and division. The operations reduce to set manipulations.

Definition 3.4 [Contraction]
The contraction c(π W ) of a potential π W = (Φ) is the non-negative function on W given by: We define the contraction of π ∅ as c(π ∅ ) = 1.

LAZY AR PROPAGATION
Inference in LARP proceeds, as mentioned, by message passing in a junction tree representation T = (C, S) of N. Prior to the message passing T is initialized. During message passing variables are eliminated by marginalization. Marginalization proceeds by arcreversal and barren variable elimination.

INITIALIZATION
The first step in initialization of T is to associate a vacuous potential with each clique A ∈ C. Initialization proceeds by assigning π X = ({Θ X| π(X) }) for each X ∈ X with a clique A, which can accommodate it, i.e. fa(X) ⊆ A.
After initialization each clique A holds a potential π A = (Φ). The set of clique potentials is invariant during insertion and propagation of evidence. After initialization the joint potential π X on T = (C, S) is: Let π A = (Φ) be the clique potential for clique A. The domain of the contraction of π A is: and has the property dom(c(π A )) ⊆ A.
Subsequently, an evidence function f(X) is assigned to each A with X ∈ A for all X. If {f 1 , . . . , f |A| } is the set of evidence functions associated with A, then π A = ({f 1 , . . . , f |A| }) is the evidence potential for clique A.

MESSAGES
The message π A B is passed from clique A to clique B by absorption, see Figure 1. Absorption from A to B involves eliminating the variables A \ B from the combination of the potential associated with A and the messages passed to A from adjacent cliques adj(A) except B. In principle π A B is computed as: (2) where π C A is the message passed from C to A. In LARP the projection operation of (2) proceeds as: 1. Let Φ be the potentials of π where: 5. Eliminate each variable X ∈ S from Φ by a sequence of arc-reversals and barren variable eliminations. Let Φ * be the result.

Associate the message π
A head variable may be instantiated by evidence though. Details may be found in (Madsen 2004a;Madsen 2004b). Notice that in the traditional LP scheme all evidence may not be received by each clique. Consider Figure 1 and assume B is instantiated by evidence. In this case, any evidence located in cliques to the left of B will not be included in the message passed from B to A. We make sure to propagate all evidence by skipping step 4. This may, however, decrease the performance of evidence propagation as additional calculations are required. In Section 8 we report on an empirical evaluation of the impact of this adjustment.

POSTERIOR CLIQUE POTENTIAL
After completion of the two-phase message passing the potential π * A of each clique A is: where π C A is the message received from C ∈ adj(A), π A is the potential associated with A, and π A is the evidence potential associated with A.
The joint probability distribution P(A, ) is obtained as the contraction c(π * A ) of π * A : Notice that π X remains invariant during message passing. Finally, we have:

A DIFFERENTIAL SEMANTICS
We present a differential semantics of LARP similar to the semantics of HUGIN and Shenoy-Shafer propagation given by Park and Darwiche (2004). Park and Darwiche (2004) give the following differential semantics of P(x| ), P( \ X ) and P(x, π| ): where X ∈ and f(X) is the (uniform) evidence function for X, where X ∈ , and where π is a configuration of π(X). (2004) show how the above probabilities and the partial derivatives may be computed from either a HUGIN or a Shenoy-Shafer propagation.

SINGLE DIMENSIONAL PARTIAL DERIVATIVE
Let T = (C, S) be a consistent junction tree with A ∈ C and let π * . CPDs and evidence functions are associated with A as part of the initialization of T whereas CPDs and probability potentials are received by A from adjacent cliques during inference. For each X ∈ A s.t. fa(X) ⊆ A we may compute: where π X = ({Θ X| π(X) }) and π is a configuration of π(X). Notice that A may be any clique for which fa(X) ⊆ A. Similarly, we may compute: where π f(X) = ({f(X)}). Notice that A may be any clique for which X ∈ A.
The partial derivative of P( ) w.r.t. a parameter θ s of the contraction of a message π C i A is: where C i ∈ adj(A) is a clique adjacent to A, S = A ∩ C i , and s is a configuration of S.
Notice that decompositions of the derivatives in (3) - (5) are obtained if potential marginalization is applied instead of contraction.
The key difference between the Shenoy-Shafer and LP is that in the latter messages are factorized into sets of potentials. This factorization offers some additional opportunities with respect to computing partial derivatives. That is, the decomposition of clique and separator potentials can be exploited to increase the number of single dimensional partial derivatives, which may be computed after a single propagation.
We are able to compute additional single dimensional derivatives w.r.t. evidence and single parameters.
In addition to computing ∂P( ) ∂θs for any separator S = A ∩ C for C ∈ adj(A), we may compute the partial derivative of P( ) with respect to each potential φ received from a adjacent clique C of A, i.e. φ ∈ Φ for some message π C A = (Φ). This is an extension compared to the differential semantics of Shenoy-Shafer and HUGIN propagation.

Example 5.1
Due to the factorization of clique potentials and the use of arc-reversal for message computation, the partial where π φ = ({φ(X|U)}). Notice φ is either a potential of P or a computed potential. In the later case, we have computed φ from a subset P φ of P by a sequence of arcreversals and barren variable eliminations.

MULTI DIMENSIONAL PARTIAL DERIVATIVE
Due to the decomposition of π * A into the potentials Φ * A , we may easily compute multi dimensional partial derivatives of P( ) w.r.t. parameters, evidence functions, and potentials of received messages represented in Φ * A as well as a mixture of the three. For instance, we may from π * A compute multi dimensional partial derivatives such as: where n = k + l + m and (6) as: where w is an instantiation of W = dom(c(π Θ )) ∪ dom(c(π f )) ∪ dom(c(π θ )).

Example 5.2
Let T = (C, S) be a junction tree in LARP equilibrium. Figure 2 shows the content of the messages passed to clique A ∈ C from adjacent cliques and the potential associated with A.

VARIABLE PROPAGATION
Variable propagation (Jensen 2001;Madsen and Jensen 1999) is a method for computing arbitrary joint probability distributions in a (consistent) junction tree T = (C, S). The aim of variable propagation is to compute the joint probability distribution P(W) for a set W ⊆ C for any C ∈ C. If W ⊆ C for any C ∈ C, then P(W) = C\W c(π * C ). Variable propagation using any variant of LP is particularly simple as it corresponds to not performing certain computations as computations are only performed when variables are eliminated.
Let T = (C, S) be a consistent junction tree and consider the calculation of the joint potential π * A∪{X} over A ∪ {X} where A ∈ C and X ∈ A. π * A∪{X} can be computed by collecting the variable X from a clique B where X ∈ B. This operation, in principle, proceeds by recomputing the messages passed from B to A without eliminating X in the process. By exploiting the decomposition of clique and separator potentials induced by LARP, it is necessary only to consider a single potential of each message passed between cliques A and B. Only a single potential in each message contains the elimination of X in its evaluation.
Let W ⊆ A∪B be a subset such that there exists no C ∈ C with W ⊆ C. The potential π W can be computed by collecting variables to any clique in a subtree T W of T spanning a set of cliques C W such that W ⊆ C∈C W C.

Theorem 6.1 [Variable Propagation]
Variable propagation of X from clique B ∈ C to clique A ∈ C where X ∈ A and X ∈ B results in π * A∪{X} as the clique potential of A.

Corollary 6.2
Variable propagation of X from clique B ∈ C to clique A ∈ C where X ∈ A and X ∈ B results in π * D∪{X} as the clique potential for each clique D on the path between B and A.
Variable propagation is useful when determining multi dimensional partial derivatives as the following exam-ple illustrates. Figure 1 with potentials π A = (Φ A ) and π B = (Φ B ), respectively. Assume T is consistent,

Example 6.3 Let A and B be adjacent cliques as in
Variable propagation of fa(X i ) amounts to recomputing all messages of π B A created by elimination of some variable in fa(X i ). After variable propagation of fa(X i ) to A, we may compute: where π * A is the potential at A after variable propagation. In essence, we have propagated the CPD Θ X i | π(X i ) to A (and possibly other CPDs and potentials as well).

A CAUTIOUS PROPAGATION SCHEME
In this section we present a cautious propagation scheme (Jensen 1995) of LARP referred to as cLARP. An early, simpler variant of cautious LP using Variable Elimination for message computation was introduced by Madsen and Jensen (1999).
The aim of cautious propagation is to support efficient calculation of the probability of subsets of the evidence by adjusting the message passing scheme. cLARP turns out to be quite useful for computing additional single and multi dimensional partial derivatives w.r.t. to evidence and subsets of . cLARP is based on cautious entering of evidence (Jensen 1995;Madsen and Jensen 1999): postpone the instantiation of an evidence variable X until the point where X would be eliminated by summation, if it had not been observed. This is contrary to the normal scheme where evidence functions are applied immediately to reduce the domain sizes of potentials.
Cautious entering of evidence implies that clique potentials are never changed (not even to reflect ) as evidence functions are only applied when calculating separator messages. Consider the calculation of π A B in (2). An evidence function f(X) reflecting hard evidence on any variable X ∈ A, X ∈ B is applied to potentials of π = π A ⊗ π A ⊗ ⊗ C∈adj(A)\{B} π C A prior to variable elimination. In cLARP the projection operation of (2) proceeds as follows: 1. Let Φ be the potentials of π where: π = π A ⊗ π A ⊗ ⊗ C∈adj(A)\{B} π C A .

Remove potentials of barren variables from Φ.
3. If X ∈ A \ B is observed, then apply f(X) on potentials of Φ.
4. Eliminate each non-barren variable X ∈ S from Φ by a sequence of arc-reversals and barren variable eliminations. Let Φ * be the result.

Associate the message π
Cautious entering of evidence allows us to easily retract evidence, which again allows us to compute additional partial derivatives after a single propagation. For each clique A and each separator S, we may compute single and multi dimensional partial derivatives for subsets ⊆ meeting at A and S, respectively.
Example 7.1 Figure 3 shows content of clique potential π A and messages π C 0 A , π C 1 A , and π C 2 A passed to A from adjacent cliques C 0 , C 1 , and C 2 (we do not include the evidence functions in the clique potentials shown (except for f(X 3 ))). We assume evidence = {x 1 , x 3 , x 7 , x 8 , x 9 , x 10 , x 11 }.
At clique A we can compute partial derivatives of subsets of where any combination of {x 9 , x 10 , x 11 } and {x 3 } is retracted. For instance, we may compute: In cLARP we maintain two sets of separator mail boxes in the junction tree T. One set of mail boxes for messages with evidence and one set of mail boxes for messages without evidence. We let T = (C, S) denote the junction tree spanned by C and the separators S with evidence and let T = (C, S ) denote the junction tree spanned by C and the separators S without evidence. Initially, we establish equilibrium of T and next the equilibrium of T is established.

Example 7.2
Since T gives access to a set of virgin (clique) and separator potentials we may compute partial derivatives for additional subsets of the evidence. For instance: In fact we may at A compute partial derivatives w.r.t. a large number of subsets of the evidence. The following sets can be retracted individually and in any combination {x 9 , x 10 , x 11 }, {x 1 }, {x 8 }, {x 3 }, and {x 7 }.
Notice that even though {x 9 , x 10 , x 11 } and {x 7 } are contained in the same separator potential π C 2 A , they can be retracted independently as the two subsets of evidence are independent (and because of the decomposition of π C 2 A ). This is neither possible in Shenoy-Shafer nor HUGIN propagation.

PERFORMANCE ANALYSIS
The goal of our performance analysis is to empirically determine the overhead in computations introduced by propagating the entire set of evidence as well as the cautious propagation scheme. We analyzed both randomly generated and real-world BNs. For each network we propagated 25 randomly generated sets of evidence of size n for n = 0, . . . , 25.  space size of clique A ∈ C where X denotes the state space size of X and C is the set of cliques of the junction tree. cLARP consistently produce an average largest potential size that is at least as high as the average largest potential size of the all-evidence and normal propagation schemes. The cost of propagating all evidence is in most cases negligible.

DISCUSSION
This paper describes how single and multi dimensional partial derivatives may easily be computed from a LARP equilibrium. To facilitate the calculation of partial derivatives, we introduce a few modifications and extensions to LARP. We adjust the absorption algorithm to include all evidence (not only the relevant evidence), we introduce variable propagation as part of LARP, and finally we define the cLARP scheme. The goal of the performance analysis was to determine the impact of propagating all evidence and the cLARP scheme. We are the first to demonstrate the impact of the cautious propagation scheme on the performance of inference. The experiments indicate that cLARP has a higher computational cost than LARP. This is expected as the cLARP scheme postpones the instantiation of an observed variable X until the point where X would be eliminated if it had not been observed.
That is, each observed variable X is instantiated in each clique A where X ∈ C and not instantiated in each clique B where X ∈ B. Hence, when eliminating an unobserved variable Y from a potential φ where X ∈ dom(φ) we are summing over dom(φ) instead of dom(φ) \ {X}.
The experiments illustrates the computational overhead introduced by propagating all evidence and the cLARP scheme. The computational overhead of propagating all evidence is low, whereas the computational overhead of the cautious propagation scheme is higher. Notice that in some cases all evidence LARP and LARP have the same performance. This implies, for instance, that the average size of the largest potential created during inference is not impacted by propagating all evidence. In addition, since propagating all evidence does not change the time performance significantly either it suggests that all or almost all evidence is already propagated by LARP. The LARP and cLARP algorithms give support for computing additional single and multi dimensional partial derivatives over the Shenoy-Shafer and HUGIN algorithms. In particular, we may compute partial derivatives w.r.t. subsets of separator messages and subsets of the evidence.
The decomposition of clique and separator potentials combined with the property that each probability potential has (at most) one head variable suggest that the differential semantics of LARP is well-suited for hypothesis driven sensitivity analysis. Future work includes an application of the differential semantics of LARP to hypothesis driven parameter sensitivity analysis. Similarly, cLARP supports easy calculation of a large set of single and multi partial derivatives of the evidence and subsets of the evidence. For this reason, the architecture should be well-suited for hypothesis driven parameter sensitivity analysis.