Lifted Aggregation in Directed First-Order Probabilistic Models

1 Introduction

Probabilistic graphical models, such as belief networks, are a popular tool for representing dependencies between random variables. However, such standard representations are propositional, hence are not well suited for describing relations between individuals or quantifying over sets of individuals. First-order logic has the capacity for representing relations and quantification of variables, but it does not treat uncertainty. Representations that mix graphical models and first-order logic (first-order probabilistic models) were proposed more than fifteen years ago [Horsch and Poole, 1990; Breese, 1992]. In these models, random variables are parameterized by logical variables that are typed with populations of individuals.

Among the appeals of the first-order probabilistic models is that one should be able to fully specify a model, that is, its structure and the accompanying probability distributions, before knowing the individuals in the modeled domain. This means in particular that, even though we might not know the sizes of the populations, we still should be able to specify the model. To make this possible, the length of a specification of a first-order probabilistic model must be independent of the sizes of the populations in the model.

Although many first-order probabilistic languages have since emerged [Getoor and Taskar, 2007; De Raedt et al., 2008], the most common exact inference technique has been based on dynamical propositionalization (grounding) of the portion of the first-order model that is relevant to the query, followed by probabilistic inference performed at the propositional level. The problemwith these propositional representations is that they may be extremely large, rendering inference intractable even for very simple first-order models. Other approaches exploit redundant computation [Koller and Pfeffer, 1997; Pfeffer and Koller, 2000], or compile the problem into an arithmetic circuit [Chavira et al., 2006].

The idea of lifted inference is to carry out as much inference as possible without propositionalizing. The correctness of this approach is judged by having the same result as if we had first grounded and then carried out standard inference. An exact lifted inference procedure for first-order probabilistic, directed models was proposed by Poole [2003]. One of the obstacles in avoiding propositionalization occurs when a first-order model contains adjacent parameterized random variables that have different parameterizations. This problem was investigated by de Salvo Braz et al. [2007]. Further work resulted in the C-FOVE algorithm [Milch et al., 2008], which is currently the state of the art in exact lifted inference.

While Poole considered directed models, the later work by de Salvo Braz et al. and Milch et al. focused on undirected models. Their results can be used for directed models, which have the advantage of allowing pruning of the part of the model that is irrelevant to the query. Also, conditional probability distributions in directed models can be interpreted and learned locally, which is important for models that are specified by people or need to be understood by people.

One aspect that arises in directed models is the need for aggregation that occurs when a parent random variable is parameterized by logical variables that are not present in a child random variable. Currently available first-order inference algorithms do not allow a description of aggregation in firstorder models that is independent of the sizes of the populations. In this paper we introduce a new data structure, aggregation parfactors, describe how to use it to represent aggregation in first-order models, and show how to perform lifted inference in its presence. Experiments presented in Section 5 show that aggregation parfactors can lead to gains in efficiency.

2 Preliminaries

Like previous work on lifted probabilistic inference, this paper is not tied to any particular first-order probabilistic language. We reason at the level of data structures and assume that various first-order languages (or their subsets) will compile to these data structures. First-order probabilistic languages share a concept of a parameterized random variable. We introduce related terms in Section 2.1. The idea of parameterized random variables is similar to the notion of plates [Buntine, 1994]; we use plates notation in our figures. In Section 2.2 we discuss aggregation in directed first-order probabilistic models.

2.1 Parameterized RandomVariables

If S is a set, we denote by |S| the size of the set S.

A population is a set of individuals. A population corresponds to a domain in logic. For example, a population may be a set of all soccer players involved in a soccer game, where rossi is one of the individuals and the population size is 22.

A parameter corresponds to a logical variable and is typed with a population. For example, parameter Player may be typed with the population of all players involved in a soccer game. Given parameter A, we denote its population by D(A). Given a set of constraints C, we denote a set of individuals from D(A) that satisfy constraints in C by D(A) : C.

A substitution is of the form {X1/t1. . . . ,Xk/tk}, where the Xi are distinct parameters, and each term ti is a parameter typed with a population or a constant denoting an individual from a population. A ground substitution is a substitution, where each ti is a constant.

A parameterized random variable is of the form f (t1, . . . ,tk), where f is a functor (either a function symbol or a predicate symbol) and ti are terms. We denote a set of parameters of the parameterized random variable f (t1, . . . , tk) by P( f (t1, . . . , tk)). Each functor has a set of values called the range of the functor. We denote the range of the functor f by range( f ). Examples of parameterized random variables are in j(Player) and in j(rossi). We have P(in j(Player)) = {Player} and P(in j(rossi)) = /0.

A parameterized random variable f (t1, . . . , tk) represents a set of random variables, one for each possible ground substitution to all of its parameters. For example, if Player is typed with a population consisting of all 22 individuals playing the game, then in j(Player) represents 22 random variables: in j(rossi), in j(panucci), . . . , in j(desailly) corresponding to ground substitutions {Player/rossi}, {Player/panucci}, . . . , {Player/desailly}, respectively. The range of the functor of the parameterized random variable is the domain of random variables represented by the parameterized random variable.

Let v denote an assignment of values to random variables; v is a function that takes a random variable and returns its value. We extend v to also work on parameterized random variables, where we assume that free parameters are universally quantified. For example, if v(in j(Player)) = true, then each of the random variables represented by in j(Player), namely in j(rossi), in j(panucci), . . . , in j(desailly), is assigned the value true by v.

FIRST-ORDER PROPOSITIONAL

Figure 1: A first-order model from Example 1 and its equivalent belief network. Aggregation is denoted by curved arcs.

2.2 Aggregation in Directed First-order Probabilistic Models

First-order probabilistic models describe probabilistic dependencies between parameterized random variables. A grounding of a first-order probabilistic model is a propositional probabilistic model obtained by replacing each parameterized random variable with the random variables it represents and replicating appropriate probability distributions.

Example 1. Consider the directed first-order probabilistic model and its grounding presented in Figure 1. The model is meant to represent that whether a player playing a soccer game is substituted or not during a single soccer game depends on whether he gets injured. The probability of an injury in turn depends on a physical condition of the player. The model has four nodes: a parameterized random variable shape(Player) with range { f it, un f it}, a parameterized random variable in j(Player) with range {true, f alse}, a parameterized random variable sub(Player) with range {true, f alse}, and a variable substitution() with range {true, f alse} that is true if a player was substituted during the game and f alse otherwise. We have D(Player) = {rossi, panucci, . . . , desailly} and |D(Player) | = 22.

A parameterized random variable shape(Player) represents the 22 random variables in the corresponding propositional model, as do variables in j(Player) and sub(Player). Therefore, in the propositional model, the number of parent nodes influencing the node substitution() is equal to 22. Their common effect aggregates in the child variable. In the discussed model we use the logical OR as an aggregation operator to describe the (deterministic) conditional probability distribution P(substitution()|sub(Player)). Note that substitution() is a noisy-OR of in j(Player).

In a directed first-order model, when a child variable has a parent variable with extra parameters, in the grounding the child variable has an unbounded number of parents. We need some aggregation operator to describe how the child variable depends on the parent variable. Following Zhang and Poole [1996], we assume that the range of the parent variable is a subset of the range of the child variable, and use a commutative and associative deterministic binary operator over the range of the child variable as an aggregation operator ⊗.

Given probabilistic input to the parent variable, we can construct any causal independence model covered by the definition of causal independence from Zhang and Poole [1996], which in turn covers common causal independence models such as noisy-OR [Pearl, 1986] and noisy-MAX [D´ıez, 1993] as special cases. In other words, this allows any causal independence model to act as underlying mechanism for aggregation in directed first-order models. For other types of aggregation in first-order models, see Jaeger [2002].

In this paper we require that the directed first-order probabilistic models satisfy the following conditions:

1. for each parameterized random variable, its parent has at most one extra parameter
2. if a parameterized random variable c(. . .) has a parent p(. . . , A, . . . ) with an extra parameter A, then:
3. (a) p(. . . ,A, . . .) is the only parent of c(. . .)
4. (b) the range of p is a subset of the range of c
5. (c) c(. . .) is a deterministic function of the parent: c(. . .) = p(. . . ,a1, . . .)⊗. . .⊗ p(. . . ,an, . . .) = ⊗a∈D(A) p(. . . ,a, . . .), where ⊗ is a commutative and associative deterministic binary operator over the range of c.

At first the above conditions seem to be very restrictive, but they in fact are not. There is no need to define the aggregation over more than one parameter due to the associativity and commutativity of the ⊗ operator. We can obtain more complicated distributions by introducing auxiliary variables and combining multiple aggregations.

Example 2. Consider a parent variable p(A,B,C) and a child variable c(C). We can describe a ⊗-based aggregation over A and B, c(C) = ⊗(a,b)∈D(A)×D(B) p(A,B,C) using an auxiliary parameterized random variable c′ (B,C) such that c′ has the same range as c. Let c′ (B,C) = ⊗a∈D(A) p(A,B,C), then

Similarly, with the use of auxiliary nodes, we can construct a distribution that combines an aggregation with influence from other parent nodes or even combines multiple aggregations generated with different operators.

In the rest of the paper, we assume that the discussed models satisfy conditions (1) and (2), for ease of presentation and with no loss of generality.

3 Existing Algorithm

In this section, we introduce counting formulas [Milch et al., 2008] and parfactors [Poole, 2003] and give an overview of the C-FOVE algorithm [Milch et al., 2008].

3.1 Counting Formulas

A counting formula is #A:C[ f (. . . ,A, . . .)], where A is a parameter that is bound by the # sign, C is a set of inequality constraints involving A and f (. . . ,A, . . .) is a parameterized random variable.

The value of #A:C[ f (. . . ,A, . . .)], given an assignment of values to random variables v, is the histogram h that maps the range of f to natural numbers such that

The range of such a counting formula is the set of histograms having a bucket for each element x in the range of f with entries adding up to |D(A) : C |. The number of such histograms is (|D(A):C |+|range( f )|-1 |range( f )|-1 ), which for small values of |range( f )| is O(|D(A) : C ||range( f )|-1 ). Thus, any extensional representation of a function on a counting formula #A:C[ f (. . . ,A, . . .)] requires amount of space at least linear in |D(A) : C |.

Counting formulas allow us to exploit interchangeability within factors. They were inspired by work on cardinality potentials [Gupta et al., 2007] and counting elimination [de Salvo Braz et al., 2007]. They are a new form of parameterized random variables. Unless otherwise stated, by parameterized random variables we understand both forms: the standard, defined in Section 2.1, and counting formulas.

3.2 Parametric Factors

A factor on a set of random variables represents a function that, given an assignment of a value to each random variable from the set, returns a real number. Factors are used in the variable elimination algorithm [Zhang and Poole, 1994] to store initial conditional probabilities and intermediate results of computation during probabilistic inference in graphical models. Operations on factors include multiplication of factors and summing out random variables from a factor.

Let v be an assignment of values to random variables and let F be a factor on a set of random variables S. We extend v to factors and denote by v(F) the value of the factor F given v. If v does not assign values to all of the variables in S, then v(F) denotes a factor on other variables.

A parametric factor or parfactor is a triple 〈C,V,F〉 where C is a set of inequality constraints on parameters (between a parameter and a constant or between two parameters), V is a set of parameterized random variables and F is a factor from the Cartesian product of ranges of parameterized random variables in V to the reals.

A parfactor 〈C,V,F〉 represents a set of factors, one for each ground substitution G to all free parameters in V that satisfies constraints in C. Each such factor FG is a factor on the set of random variables obtained by applying a substitution G. Given an assignment v to the random variables represented by V, we define v(FG) = v(F).

We use parfactors to represent probability distributions for parameterized random variables in first-order models and intermediate computation results during lifted inference.

Normal-Form Constraints

Let X be a parameter in V from a parfactor 〈C,V,FF〉. In general, the size of the set D(X) : C depends on other parameters in V (see discussions on uniform solution counting partitions in de Salvo Braz et al. [2007] and normal form constraints in Milch et al. [2008]).

Milch et al. [2008] introduced a special class of sets of inequality constraints. Let C be a set of inequality constraints on parameters and X be a parameter. We denote by E C X the set of terms t such that (X ̸=t) ∈C. Set C is in normal form if for each inequality (X ̸=Y) ∈ C, where X and Y are parameters, E C X \{Y} = E C Y \{X}.

Consider a parfactor 〈C,V,FF〉, where C is in normal form. For all parameters X in V, |D(X) : C | = |D(X)|-|E C X |.

We require that for a parfactor 〈C,V,FF〉 involving counting formulas, the union of C and the constraints in all the counting formulas in V is in normal form. Other parfactor do not need to be in normal form.

3.3 C-FOVE

Let Φ be a set of parfactors. Let J (Φ) denote a factor equal to the product of all factors represented by elements of Φ. Let U be the set of all random variables represented by parameterized random variables present in parfactors in Φ. Let Q be a subset of U. The marginal of J (Φ) on Q, denoted JQ(Φ), is defined as JQ(Φ) = ∑U\Q J (Φ).

Given Φ and Q, the C-FOVE algorithm computes the marginal JQ(Φ) by summing out random variables from U\Q, where possible in a lifted manner. Evidence can be handled by adding to Φ additional parfactors on observed random variables.

As lifted summing out is only possible under certain conditions, the C-FOVE algorithm uses elimination enabling operations, such as applying substitutions to parfactors and multiplication. Below we show when and how these operations can be applied to aggregation parfactors. We refer the reader to Milch et al. [2008] for more details on C-FOVE.

4 Incorporating aggregation in C-FOVE

In Section 4.1, we show how to represent aggregation in firstorder models using a simple form of aggregation parfactors. In Section 4.2, we show how these aggregation parfactors can be converted to parfactors that in turn can be used during inference with C-FOVE. In Section 4.3, we describe when and how reasoning directly in terms of these aggregation parfactors can achieve improved efficiency. In Section 4.4 we outline how a generalized version of aggregation parfactors increases the number of cases for which efficiency is improved.

4.1 Aggregation Parfactors

Example 3. Consider the model presented in Figure 1. We cannot represent the conditional probability distribution P(substitution()|sub(Player)) with a parfactor 〈/0, {sub(Player), substitution()}, F〉 as even simple noisyOR cannot be represented as a product. A parfactor 〈/0, {sub(rossi), . . . , sub(desailly), substitution()}, F〉 is not an adequate input representation of this distribution because its size would depend on |D(Player)|. The same applies to a parfactor 〈/0, {#Player: /0[sub(Player)], substitution()}, F〉 as the size of the range of #Player: /0[sub(Player)] depends on | D(Player) |.

Definition 1. An aggregation parfactor is a hex-tuple 〈C, p(. . . , A, . . . ), c(. . . ), Fp, ⊗, CA〉, where

• p(. . . ,A, . . . ) and c(. . . ) are parameterized random variables
• the range of p is a subset of the range of c
• A is the only parameter in p(. . . ,A, . . .) that is not in c(. . . )
• C is a set of inequality constraints not involving A
• Fp is a factor from the range of p to real numbers
• ⊗ is a commutative and associative deterministic binary operator over the range of c
• CA is a set of inequality constraints involving A.

An aggregation parfactor 〈C, p(. . . , A, . . . ), c(. . . ), Fp, ⊗, CA〉 represents a set of factors, one for each ground substitution G to parameters P(p(. . . , A, . . . ))∪ P(. . . )) \{A} that satisfies constraints in C. Each factor FG is a mapping from the Cartesian product (×a∈D(A):CA range(p)) ×range(c) to the reals, which, given an assignment of values to random variables v, is defined as follows:

It is important to notice that D(A) : CA might vary for different ground substitutions G if the set C∪CA is not in normal form (see Section 3.2). The space required to represent an aggregation parfactor does not depend on the size of the set D(A) : CA. It is also at most quadratic in the size of range(c), as the operator ⊗ can be represented as a factor from range(c)×range(c) to range(c).

When an aggregation parfactor 〈C, p(. . . ,A, . . .), c(. . .), Fp, ⊗, CA〉 is used to describe aggregation in a first-order model, the factor Fp will be a constant function with the value 1. An aggregation parfactor created during inference may have a non-trivial Fp component (see Section 4.3).

Example 4. Consider the first-order model and its grounding presented in Figure 1. We can represent the conditional probability distribution P(substitution()|sub(Player)) with an aggregation parfactor 〈 /0, sub(Player), subst itut ion(), Fsub, OR, /0〉, where Fsub is a constant function with the value 1. The size of the representation does not depend on the population size of the parameter Player.

In the rest of the paper, Φ denotes a set of parfactors and aggregation parfactors. The notation introduced in Section 3.3 remains valid under the new meaning of Φ.

4.2 Conversion to Parfactors

Conversion using counting formulas

Consider an aggregation parfactor 〈C, p(. . . ,A, . . .), c(. . .), Fp, ⊗, CA〉. Since ⊗ is an associative and commutative operator, given an assignment of values to random variables v, it does not matter which of the variables p(. . . ,a, . . .), a ∈ D(A):CA are assigned each value from range(p), but only how many of them are assigned each value. This property was a motivation for the counting elimination algorithm [de Salvo Braz et al., 2007] and counting formulas [Milch et al., 2008], and allows us to convert aggregation parfactors to a product of two parfactors, where one of the parfactors involves a counting formula.

Proposition 1. Let gA = 〈C, p(. . . ,A, . . . ), c(. . . ), Fp, ⊗, CA〉 be an aggregation parfactor from Φ such that set C∪CA is in normal form. Let F# be a factor from the Cartesian product range(#A:CA [p(. . . ,A, . . .)]) × range(c) to {0,1}. Given an assignment of values to random variables v, the function is defined as follows:

where h() is a histogram from range(#A:CA [p(. . . ,A, . . .)]). Then J (Φ) = J (Φ \ {gA}∪ {〈C ∪CA, {p(. . . , A, . . . )}, Fp〉, 〈C, {#A:CA [p(. . . , A, . . . )], c(. . . )}, F#〉}).

If the set C∪CA is not in normal form we will need to use splitting operation described in Section 4.3 to convert the aggregation parfactor to a set of aggregation parfactors with constraint sets in normal form.

Conversion for MAX and MIN operators

If in an aggregation parfactor ⊗ is the MAX operator (which includes the OR operator as a special case), we can use a factorization presented by D´ıez and Gal´an [2003] to convert the aggregation parfactor to parfactors without counting formulas. The factorization is an example of the tensor rank-one decomposition of a conditional probability distribution [Savicky and Vomlel, 2007].

Proposition 2. Let gA =〈C, p(. . . ,A, . . .), c(. . .), Fp, MAX, CA〉 be an aggregation parfactor from Φ, where MAX operator is induced by a total ordering ≺ of range(c). Let s() be a successor function induced by ≺. Let c′ (. . . ) be an auxiliary parameterized random variable with the same parameterization and the same range as c. Let Fc be a factor from the Cartesian product range(p)×range(c) to real numbers that, given an assignment of values to random variables v, is defined as follows:

Let FΔ be a factor from the Cartesian product range(p)×range(c) to real numbers that, given v, is defined as follows:

An analogous proposition holds for the MIN operator. In both cases, as shown in Section 5, the above conversion is advantageous to the conversion described in Proposition 1, which uses counting formulas.

4.3 Operations on Aggregation Parfactors

In the previous section we showed that aggregation parfactors can be used during a modeling phase and then, during inference with the C-FOVE algorithm, once populations are known, aggregation parfactors can be translated to parfactors.

Such a solution allows us to take advantage of the modeling properties of aggregation parfactors and C-FOVE inference capabilities. It is also possible to exploit aggregation parfactors during inference. In this section we describe operations on aggregation parfactors that can be added to the C-FOVE algorithm. These operation can delay or even avoid translation of aggregation parfactors to parfactors involving counting formulas. This in turn, as we will see in Section 5, can result in more efficient inference.

Splitting

The C-FOVE algorithm applies substitutions to parfactors to handle observations and queries and to enable the multiplication of parfactors. As this operation results in the creation of a residual parfactor, it is called splitting. Below we present how aggregation parfactors can be split on substitutions.

Proposition 3. Let gA = 〈C, p(. . . ,A, . . . ), c(. . . ), Fp, ⊗, CA〉 be an aggregation parfactor from Φ. Let {X/t} be a substitution such that (X ̸= t) /∈ C and X ∈ P(p(. . . ,A, . . . ))\{A} and term t is a constant such that t ∈D(X), or a parameter such that t ∈ P(p(. . . ,A, . . .))\{A}. Let gA[X/t] be a parfactor gA with all occurrences of X replaced by term t. Then J (Φ) = J(Φ\ {gA}∪ {gA[X/t], 〈C∪{X ̸= t}, p(. . . ,A, . . .), c(. . .), Fp, ⊗, CA〉}).

Proposition 3 allows us to split an aggregation parfactor on a substitution that does not involve the aggregation parameter. Below we show how to split on a substitution that involves the aggregation parameter A and a constant. Such an operation divides the individuals from D(A) : C in two data structures: an aggregation parfactor and a standard parfactor. We have to make sure that after splitting c(. . . ) is still equal to a ⊗-based aggregation over the whole D(A) : C.

Proposition 4. Let gA = 〈C, p(. . . ,A, . . . ), c(. . . ), Fp, ⊗, CA〉 be an aggregation parfactor from Φ. Let {A/t} be a substitution such that (A ̸= t) /∈ CA and term t is a constant such that t ∈ D(A), or a parameter such that t ∈ P(p(. . . ,A, . . . ))\{A}. Let c′ (. . .) be an auxiliary parameterized random variable with the same parameterization and range as c(. . .). Let CA[A/t] be a set of constraints CA with all occurrences of A replaced by term t. Let F1 be a factor from the Cartesian product range(p) × range(c′ ) × range(c) to real numbers. Given an assignment of values to random variables v, the function is defined as follows:

Splitting presented in Proposition 4 corresponds to the expansion of a counting formula in C-FOVE. The case where a substitution is of the form {X/A} can be handled in a similar fashion as described in Proposition 4. If a substitution has more than one element, then we split recursively on its elements using the above propositions.

Multiplication

The C-FOVE algorithm multiplies parfactors to enable elimination of parameterized random variables. An aggregation parfactor can be multiplied by a parfactor on p(. . . , A, . . . ).

Proposition 5. Let gA = 〈C, p(. . . ,A, . . .), c(. . .), Fp, ⊗, CA〉 be an aggregation parfactor from Φ and g1 = 〈C1, {p(. . . ,A, . . .)}, F1〉 be a parfactor from Φ such that C1 = C∪CA. Let g2 = 〈C, p(. . . ,A, . . .), c(. . .), FpF1, ⊗, CA〉. Then J (Φ) = J (Φ \ {gA, g1}∪ {g2}).

We call g2 the product of gA and g1.

Summing out

The C-FOVE algorithm sums out random variables to compute the marginal. Below we show how in some cases we can sum out p(. . . , A, . . . ) directly from an aggregation parfactor.

When p(. . . ,A, . . .) represents a set of random variables that can be treated as independent, aggregation decomposes into a binary tree of applications of the aggregation operator. Figure 2 illustrates this for a case where n = |D(A) :CA | is a power of two. The results at each level of the tree are identical, therefore we need to compute them only once. In the general case, covered by Proposition 6, we use a square-andmultiply method [Pi˙ngala, 200 BC], whose time complexity is logarithmic in |D(A) :CA |, to eliminate p(. . . ,A, . . .) from an aggregation parfactor.

Proposition 6. Let gA = 〈C, p(. . . ,A, . . .), c(. . .), Fp, ⊗, CA〉 be an aggregation parfactor from Φ. Assume that P(c(. . .)) = P(p(. . . ,A, . . .))\{A} and that set C∪CA is in normal form. Let S denote a set of random variables represented by p(. . . ,A, . . .). Assume that no other parfactor or aggregation parfactor in Φ involves parameterized random variables that represent random variables from S. Let m = ⌊log2 |D(A) : CA |⌋ and bm . . . b0 be the binary representation of |D(A) :CA |. Let (F0, . . . ,Fm) be a sequence of factors from range of c to the reals, defined recursively as follows:

Proposition 6 does not allow variable c(. . .) in an aggregation parfactor to have extra parameters that are not present in variable p(. . . , A, . . . ). The C-FOVE algorithm handles extra parameters by introducing counting formulas on these parameters. Then it can proceed with standard summation. We cannot apply the same approach to aggregation parfactors as newly created counting formulas could have ranges incompatible with the range of the aggregation operator. We need a special summation procedure, described below in Proposition 7.

Proposition 7. Let gA = 〈C, p(. . . ,A, . . .), c(. . . ,E, . . .), Fp, ⊗, CA〉 be an aggregation parfactor from Φ. Assume that P(c(. . .))\{E} = P(p(. . . ,A, . . .))\{A}, that set C∪CA is in normal form. Let S denote a set of random variables represented by p(. . . ,A, . . .). Assume that no other parfactor or aggregation parfactor in Φ involves parameterized random variables that represent random variables from S. Let m = ⌊log2 |D(A) : CA |⌋ and bm . . . b0 be the binary representation of |D(A) :CA |. Let (F0, . . . ,Fm) be a sequence of factors from range of c to real numbers, defined recursively as follows:

Let CE be a set of constraints from C that involve E. Let F# be a factor from the range of counting formula #E:CE [c(. . . ,E, . . . )] to real numbers defined as follows:

The above proposition can be generalized to the cases where c(. . . ) has more than one extra parameter.

If set C∪CA is not in normal form, then |D(A) : CA | might vary for different ground substitutions to parameters in p(. . . ,A, . . . ) and we will not be able to apply Propositions 6 and 7. We can follow Milch et al. [2008] and bring constraints in the aggregation parfactor to a normal form by splitting it on appropriate substitutions. Once the constraints are in normal form, |D(A) : CA | does not change for different ground substitutions. The other approach is to compute uniform solution counting partitions [de Salvo Braz et al., 2007] using a constraint solver and use this information when summing out p(. . . , A, . . . ).

4.4 Generalized aggregation parfactors

Propositions 6 and 7 require that random variables represented by p(. . . ,A, . . .) are independent. They are only dependent if they either have a common ancestor in the grounding or a common observed descendant. If during inference we eliminate the common ancestor or condition on the observed descendant before we eliminate p(. . . ,A, . . . ) through aggregation, we may introduce a counting formula on p(. . . , A, . . . ). This would prevent us from applying results of Propositions 6 and 7 and performing efficient lifted aggregation.

We need to delay such conditioning and summing out until we eliminate p(. . . ,A, . . .). It requires a generalized version of the aggregation parfactor data structure, a septuple 〈C, p(. . . ,A, . . .), c(. . . ,E, . . .), V, Fp∪V, ⊗, CA〉 where V is a set of context parameterized random variables and Fp∪V is a factor from the Cartesian product of ranges of parameterized random variables in {p(. . . ,A, . . . )}∪V to the reals. The factor Fp∪V stores the dependency between p(. . . ,A, . . . ) and context variables.

Generalization of propositions from Sections 4.2 and 4.3 is straightforward. Proposition 5 has to be generalized so aggregation parfactors can be multiplied by parfactors on variables other than p(. . . ,A, . . . ), and generalized versions of Propositions 6 and 7 have to manipulate larger factors.

The third experiment from Section 5 involved inference with generalized aggregation parfactors.

5 Experiments

In our experiments, we investigated how the population size of parameters and the size of the range of parameterized random variables affect inference in the presence of aggregation.

We compared the performance of variable elimination (VE), variable elimination with the noisy-MAX factorization [D´ıez and Gal´an, 2003] (VE-FCT), C-FOVE, C-FOVE with the lifted noisy-MAX factorization described in Section 4.2 (C-FOVE-FCT), and C-FOVE with aggregation parfactors (AC-FOVE). We used Java implementations of the above algorithms on an Intel Core 2 Duo 2.66GHz processor with 1GB of memory made available to the JVM.

In the first experiment, we tested the above algorithms on the model introduced in Example 1 and depicted in Figure 1. In the second experiment, used a modified version of this model, in which range(in j) = range(sub) = range(subst itut ion) = {0, 1, 2}, and subst itut ion() is a noisyMAX of in j(Player). In both experiments, we measured the time necessary to compute the marginal of the variable substitution() using a top-down elimination ordering. We varied the population size n of the parameter Players from 1 to 100,000.

Figures 3 and 4 show the results of the experiments. The time complexity for VE is exponential in n, and the algorithm did not scale as n increased. The time complexity for VEFCT is linear in n. In the model with noisy-OR, the time complexity for C-FOVE is also linear in n, but C-FOVE does lifted inference and it achieved better results then VE-FCT, which performs inference at the propositional level. In the model with noisy-MAX, the time complexity for C-FOVE is quadratic in n, and C-FOVE was outperformed by VE-FCT. C-FOVE-FCT and AC-FOVE, for which the time complexity is logarithmic in n, performed best in both cases (for clarity we did not show the C-FOVE-FCT performance in Figures 3 and 4). The difference between their performance and the performance of C-FOVE was apparent even for small populations in the second experiment , which involved aggregation over non-binary random variables.

For the third experiment we used an ICL theory [Poole, 2008] from Carbonetto et al. [2009] that explains how people alter their smoking habits within their social network. Parameters of the model were learned from data of smoking and drug habits among teenagers attending a school in Scotland [Pearson and Michell, 2000] using methods described by Carbonetto et al. [2009]. Given the population size n, the equivalent propositional graphical model has 3n 2 +n nodes and 12n 2 -9n arcs. We varied n from 2 to 140 and for each value, we computed a marginal probability of a single individual being a smoker. Figure 5 shows the results of the experiment. VE, VE-FCT and C-FOVE algorithms failed to solve instances with a population size greater than 8, 10, and 11, respectively. AC-FOVE was able to handle efficiently much larger instances and it ran out of memory for a population size of 159. The AC-FOVE algorithm performed equally to the C-FOVE-FCT algorithm except for small populations. It is important to remember that the C-FOVE-FCT algorithm, unlike AC-FOVE, can only be applied to MAX and MIN-based aggregation.

6 Conclusions and FutureWork

In this paper we demonstrated the use of aggregation parfactors to represent aggregation in directed first-order probabilistic models, and how aggregation parfactors can be incorporated into the C-FOVE algorithm. Theoretical analysis and empirical tests showed that in some cases, lifted inference with aggregation parfactors leads to significant gains in efficiency.

While presented the algorithm can handle a wide range of aggregation cases, there still exist models that can't be handled efficiently by lifted inference, for example a "lattice" structure presented by Poole [2008]. These models pose an interesting challenge for future research.

To date, all empirical evaluations of lifted inference, including the evaluation in this paper, have been performed using simple first-order probabilistic models. Now we have inference procedures that allow for more comprehensive evaluation of the practical potential of lifted inference.

Acknowledgments

Authors wish to thank Peter Carbonetto, Michael Chiang, Mark Crowley, Craig Wilson, James Wright, and IJCAI reviewers for valuable comments. This work was supported by NSERC grant to David Poole.