Introduction

Markov logic networks [Domingos and Lowd, 2009] use weighted first-order logic formulas to specify large Markov networks with repeated sub-structures compactly. The use of first-order logic makes them especially amenable to expressing prior or domain knowledge, which can be easily translated from natural language to first-order logic formulas. As a result, they are routinely used to model prior knowledge in a wide variety of application domains including natural language processing [Venugopal et al., 2014;Riedel and McCallum, 2011], computer vision [Tran and Davis, 2008] and social network analysis [Chen et al., 2013].

Although the MLN representation is compact, it is now well-known that inference in them can be quite challenging and is often a major bottleneck. Specifically, the ground Markov network which is obtained by grounding or propositionalizing the first-order formulas is often so large that even approximate probabilistic inference methods such as Gibbs sampling, Belief Propagation, and MaxWalkSAT are computationally infeasible. To address this issue, several lifted inference algorithms that exploit symmetries in the MLN, and avoid constructing the ground Markov network as much as possible, have been proposed in previous work (cf. [Van den Broeck et al., 2012;Singla et al., 2014;Gogate and Domingos, 2011;Venugopal and Gogate, 2014;Kersting et al., 2010]). However, these methods do not function well on arbitrary MLN structures and in the presence of evidence or observations [Van den Broeck and Darwiche, 2013]. As a result, in practice, ground inference is often unavoidable.

Recently there has been growing interest in developing approaches that perform efficient inference over the ground network. Popular approaches include performing lazy inference which constructs the ground network incrementally [Singla and Domingos, 2006b], reducing the size of the network by leveraging evidence [Shavlik and Natarajan, 2009], and using fast, approximate counting approaches that ground the predicates but not the formulas [Venugopal et al., 2015;Sarkhel et al., 2016;Das et al., 2016]. The approach proposed in this paper is related and addresses the following fundamental difficulty associated with the approximate counting approach: it is scalable only on MLNs having both shared sub-structures and weights (MLNs in which all groundings of a first-order formula have the same weight).

In this paper, we consider inference in MLNs having shared sub-structures but no shared weights (we call them untied MLNs), namely MLNs in which different groundings of a first-order formula have different weights. Such MLNs are more common in real-world applications [Singla and Domingos, 2006a;Venugopal et al., 2014] since using the same weight for all groundings of a first-order formula often yields a biased, inaccurate model. For example, to specify that a word in a web-page determines the topic of a webpage, we can specify the formula Word(w, p) ⇒ Topic(p, t) with a single weight w. However, this model is unrealistic since it assumes that the dependency between every word and every topic is identical. A more practical solution will have m • n different weights, where m is the number of words and n is the number of topics. In the MLN nomenclature, this is represented as a variable preceded by a '+' sign. Thus, for our running example, we would write Word(+w, p) ⇒ Topic(p, +t), and associate a different weight for each grounding (combination) of the '+' variables.

This paper addresses the problem of scaling up inference in untied MLNs and makes the following contributions.

1. We develop a novel graphical model encoding for untied MLN formulas and prove that our new encoding is exact, i.e., the partition function of the graphical model is equal to the sum of the weights of the satisfied groundings in a given world, and exact inference over it is more efficient than the encoding proposed in [Venugopal et al., 2015]. 2. We propose an approximate graphical model encoding for untied MLN formulas. This is useful when the exact encoding has large treewidth. The key idea is to cluster together groundings of a formula having similar weights to yield a graphical model with smaller treewidth. We evaluate our proposed exact and approximate encodings on several MLN benchmarks and compare their performance to [Venugopal et al., 2015]. Our results clearly demonstrate that our new encodings, both exact and approximate, substantially improve the scalability, convergence, and accuracy of Gibbs sampling and MaxWalkSAT.

Notation and Background

First-order Logic. The language of first-order logic (cf. [Genesereth and Kao, 2013]) consists of quantifiers (∀ and ∃), logical variables, constants, predicates, and logical connectives (∨, ∧, ¬, ⇒, and ⇔). A predicate is a relation that takes a specific number of arguments as input and outputs either TRUE (synonymous with 1) or FALSE (synonymous with 0). The arity of a predicate is the number of its arguments. A term is either a logical variable or a constant. We denote predicates by strings in typewriter font (e.g., R, Smokes) followed by a parenthesized list of terms.

A first-order formula is recursively defined as follows:(i) An atomic formula (atom) is a predicate; (ii) Negation of an atom is a formula; (iii) If f and g are formulas then connecting them by binary connectives such as ∧ and ∨ yields a formula; and (iv) If f is a formula and x is a logical variable then ∀xf and ∃xf are formulas. A first-order knowledge base (KB) is a set of first-order formulas.

We assume that each argument of each predicate is typed and can only be assigned to a finite set of constants. By extension, each logical variable in each formula is also typed. We assume that our language does not contain the equality symbol and function symbols. We further assume that all firstorder formulas are disjunctive (clauses), have no free logical variables, have only universally quantified logical variables (namely, the KB is in conjunctive normal form (CNF)), and have no constants. Note that all first-order formulas can be easily converted to this form.

A ground atom is an atom that contains no logical variables. A ground formula is a formula containing only ground atoms. The grounding of a first-order formula f is the set of all possible ground formulas that can be obtained from f by substituting all the logical variables in it by constants in their domain. A ground KB is obtained from a first-order KB by grounding all of its first-order formulas. A possible world, denoted by ω, is a truth assignment to all possible ground atoms in the first-order KB. Markov Logic Networks (MLNs). An issue with first-order logic is that it cannot represent uncertainty: all worlds that violate even one ground formula are considered inconsistent.

MLNs soften the constraint expressed by each formula, by attaching a weight to it. The higher the weight, the higher the probability of the clause being satisfied, all other things being equal. MLNs can also be seen as a first-order template for generating large Markov networks. Formally, an MLN is a set of pairs (f i , θ i ) where f i is a formula in first-order logic and θ i is a real number. Given a set of constants, an MLN represents a ground Markov network which has one random variable for each grounding of each predicate and one propositional feature for each grounding of each formula. The weight associated with the feature is the weight attached to the corresponding formula. The ground Markov network represents the following probability distribution:

where N i (ω) is the number of groundings of f i that evaluate to TRUE given ω and Z θ is the normalization constant. We call this the #SG problem. Important inference queries over MLNs such as computing the partition function, finding the marginal probability of a variable given evidence (where evidence is an assignment to a subset of variables), and finding the most probable assignment to all variables given evidence, also called the MAP inference problem, require solving the #SG problem at every iteration.

Solving the #SG problem. The main computational bottleneck in many inference algorithms for MLNs such as Gibbs sampling for marginal inference and MaxWalkSAT [Kautz et al., 1997] for MAP inference is computing N i (ω). Until recently, the #SG problem was solved using the following naive method: given a clause f i and a world ω, generate all possible ground clauses of f i and count only those that are satisfied in ω. [Venugopal et al., 2015] showed that the problem could be solved efficiently by reducing it to the problem of computing the number of solutions of a constraint satisfaction problem (i.e., a Markov network in which all potentials have just two values: 0 or 1). Formally, given a first-order clause f i and a world ω, the corresponding constraint network C i has a variable for each (universally quantified) logical variable in f i . The domain of each variable in C i is the set of constants in the domain of the corresponding logical variable. For each atom R(x 1 , . . . , x u ) in f i , we have a constraint φ in C defined as follows:

) denotes an assignment to the variables in the constraint network and ω R(X1,...,Xu) is the projection of the world ω on the ground atom R(X 1 , . . . , X u ).

Example 1. Fig. 1 shows the constraint network for a formula f and a world ω.

[ Venugopal et al., 2015] showed that if #C i denotes the number of solutions of the constraint network C i associated with a clause f i and world ω then:

denotes the set of logical variables in f i and ∆(x j ) is the set of constants in the domain of x j . Thus, if a junction tree algorithm is used to compute #C i , then its time and space complexity is exponential in treewidth plus one and treewidth respectively. Since the treewidth can be much smaller than the number of logical variables, the complexity of Venugopal et al.'s method can be exponentially smaller than the naive approach, which is exponential in the number of logical variables. Untied MLN. An MLN formula represents a template for generating ground formulas (obtained by replacing logical variables with domain objects). Often in the Markov Logic literature, it is assumed the weight of each of these grounding is the same, i.e. they are tied. However, in many realistic settings (e.g., for many information extraction tasks such as event extraction [Venugopal et al., 2014]), the parameter tying assumption is too strong. MLNs relax this constraint using the '+' operator, which learns a separate weight for each grounding of each logical variable associated with a '+' sign.

Example 2. Let f = ∀x, ∀y, ∀z ¬R(x, y) ∨ S(y, z) be an MLN formula. Then to specify that different weights are attached to different groundings of x and z of f , we use the formula: f = ∀x, ∀y, ∀z ¬R(+x, y) ∨ S(y, +z)

We will use X + to denote the set of logical variable associated with the "+" operator. To denote the weights (or parameters) associated with f we will use θ f . A complete assignment to all the variables in X + (denoted by x + ) corresponds to exactly one parameter from the parameter set θ. Hence, we will denote each such individual parameter by θ x+ . In the above example if ∆(x) = {A, B} and ∆(y) = {C, D} then the parameter set is,

For these MLNs we can rewrite Equation 1 as follows:

where,

is the total weight of the satisfied groundings of a first order formula f i . We will refer the task of computing the expression W fi as #WSG (short for, total weight of satisfied groundings). Since, #WSG generalizes #SG (which is #P-complete), it is obvious that no efficient algorithm can exist for solving the #WSG problem.

3 Exact Encoding for untied formulas [Venugopal et al., 2015] and [Sarkhel et al., 2016] used a constraint network to solve the #SG problem. In this section, we extend their approach to untied MLNs. Since untied MLNs have different weights for each combination of the "+" variables, we will use a dynamic Markov Random Field (dMRF)foot_1 instead of constraint network for each first-order formula and show that the partition function of the dMRF corresponds to the #WSG problem. It should be noted that our approach generalizes Venugopal et al.'s approach because a constraint network is an MRF having only 0/1 potentials. We demonstrate our proposed dMRF encoding on the following clause: f = ∀x, ∀y, ∀z ¬R(+x, y)∨S(y, +z). Let the domain of each logical variable be {A, B}. The formula has a different parameter (instead of only one parameter) for each grounding of the variables x and z (denoted by θ x,z ). Our task here is to compute the total weight of f alse groundings of f given ω. To solve the task, we create a MRF having three random variables (see Fig. 2), one for each logical variable x, y, and z, and having three potentials, φ 1 (x, y), φ 2 (y, z), and, φ 3 (x, z). Here, φ 1 (x, y) and φ 2 (y, z) are exactly same as the functions φ 1 and φ 2 in the Fig. 1. For φ 3 (x, z) each potential entry indexed by x, z is equal to the parameter θ x,z .

Given the above set up, notice that if we take a product of the three functions φ 1 (x, y), φ 2 (y, z), and, φ 3 (x, z), then the resulting function φ(x, y, z) will have θ x,z associated with an entry (x, y, z) iff R(x, y) is true and S(y, z) is f alse. Since the weight of a ground formula, indexed by (x, y, z), is given by θ x,z and it evaluates to f alse iff R(x, y) is true and S(y, z) is f alse, by extension φ(x, y, z) = θ x,z implies that the ground formula (x, y, z) is f alse. Therefore, we can compute the total weight of groundings of f that evaluate to f alse, by simply summing over all the entries in φ(x, y, z), which is the same as computing the partition function of the constructed MRF. To compute the total weight of true groundings we need to compute the total weight of all possible groundings, which in this case, equals to (|∆(y)| × x,z θ x,z ). Subtracting the obtained partition function from this quantity will give us the total weight of true groundings.

Next, we will precisely define how to encode the #WSG problem as a partition function computation problem. MRF Encoding. Given a first-order clause f and a world ω, the corresponding dMRF G has a variable for each (universally quantified) logical variable in f . The domain of each variable in G is the set of constants in the domain of the corresponding logical variable. For each atom R(x 1 , . . . , x u ) in f , we have a potential φ in G defined as follows:

where x u = (x 1 = X 1 , . . . , x u = X u ) denotes an assignment to the dMRF variables and ω R(X1,...,Xu) is the projection of the world ω on the ground atom R(X 1 , . . . , X u ), namely the truth-value of the ground atom R(X 1 , . . . , X u ) in ω. Finally if x i , . . . , x j are variables associated with the '+' operator and if the corresponding parameters are θ xi,...,xj then we have a potential ψ in G defined as: ψ(xi, . . . , xj) = θx i ,...,x j By generalizing the arguments presented for the example MLN given above, we can show that:

Theorem 1. Let f be a first-order clause, {x} be logical variables in f , X + ⊆ {x} be logical variables associated with '+' operators, {θ x+ } be parameters attached to f , ω be a world and let Z G denote the partition function of the dMRF G obtained from (f, ω) using the MRF encoding. Then,

is the set of constants in the domain of x.

Since we have reduced the #WSG problem to the partition function calculation problem, we can use any graphical model inference algorithm such as the junction tree algorithm [Lauritzen and Spiegelhalter, 1988] and leverage its advances and guarantees to compute the former efficiently. Thus, the time and space complexity of solving #WSG using the junction tree algorithm is exponential in the treewidth of G.

An important property of our MRF encoding is that junction tree inference over it is guaranteed to have either the same or smaller complexity than inference in the constraint network encoding proposed by [Venugopal et al., 2015]. This is because unlike the constraint network encoding which grounds all the '+' variables, the MRF encoding takes advantage of the structure induced by the '+' variables and this can yield significant reductions in complexity. For example, the treewidth of the MRF encoding of the formula f = ∀x, ∀y, ∀z ¬R(+x, y) ∨ S(y, z) (notice that our running example is no + sign associated with z) is 1, while one will have to create O(n) constraint networks having treewidth 1 each in order to solve the #WSG problem using Venugopal et al.'s approach. Thus, inference on the MRF encoding will be more efficient by a factor of O(n) over the constraint network encoding. In summary, Theorem 2. The time and space complexity for solving #WSG using the junction tree algorithm is no-worse (i.e., at least the same or better) than solving #SG using same algorithm.

Since, local-search based algorithms such as MaxWalkSAT and Gibbs sampling require solving #WSG at every iteration, we can efficiently implement them using our encoding. This will significantly improve their computational complexity.

Approximate Encoding for untied formulas

In the encoding described in the previous section, we added a new potential to account for the fact that different groundings corresponding to the '+' variables have different weights. This encoding is impractical if the treewidth of the graphical model or the number of objects is large. Therefore, in order to improve the computational complexity, we propose to reduce the number of weights associated with each formula by replacing weights which are close to each other by a single weight. We illustrate this idea next. Consider the formula in our running example: f = ∀x, ∀y, ∀z ¬R(+x, y) ∨ S(y, +z). Assume now that the domain of each logical variable is {A, B, C, D}. There are 16 different parameters associated with f , each corresponding to a full assignment to (x, z). Now assume that θ A,C , θ A,D , θ B,C , θ B,D , are almost the same. In that case we can combine the four (partially) ground formulas associated with these parameters into a single formula f = ∀x , ∀y, ∀z ¬R(x , y) ∨ S(y, z ) having a single parameter θ and ∆(x ) = {A, B}, ∆(z ) = {C, D} and ∆(y) = {A, B, C, D}. Similarly we can combine the other formulas yielding the four parameters given in Fig. 3.

The above idea can be set up as a clustering problem. However, in order to reduce the complexity, care must be taken to ensure that each cluster is the Cartesian product of subsets of domains of the '+' variables. In two dimensions, this is equivalent to biclustering [Hartigan, 1972]. For instance, in the above example, putting the diagonal elements of the matrix in Fig. 3 into one cluster will not yield reductions in the computational complexity. This is because all constants in the domain of x and z will be involved in the computations. On the other hand, consider the cluster given by x ∈ {A, B} and z ∈ {C, D} shown in Fig. 3. In this case, only two constants in each domain will be involved in computations.

Formally, we are interested in finding the optimal joint clustering over all the '+' variables. Since the parameters associated with an untied formula can be arranged in a tensor (i.e., a multi-dimensional array), where each logical variable represents one dimension or order, we define this problem as a tensor clustering problem. A tensor qunatizer Q induces a partition (P (l) ) on the set of values (∆(i l )) for each dimension (i l ) of the tensor, and hence reduces its size. For example, in Fig. 3,a Select a random ordering O of X+. for each variable x ∈ X+ chosen according to O do Create a random partition P (x) of size kx of ∆(x) /* The set {P (x) } defines the initial cluster assignment */ while the cluster assignment changes do for each variable x ∈ O do Find the optimum partition P (x) that minimizes Eq. ( 3) assuming that partitions associated with other variables are fixed.

and P (z) = {R, S} = {{A, B}, {C, D}}. We are interested in finding a quantizer having minimum quantization error:

where Q(a) is the cluster mean. Solving the joint clustering problem is computationally hard. A naive approach which searches for all possible partitions of a given domain is not scalable since the number of possible partitions of size k for a set of size n (also known as the Stirling numbers of the kind) grows exponentially with n. Hence, to solve this optimization problem we propose a greedy approach. Our method is described in Algorithm 1. It begins by selecting an ordering O of variables. For each variable, the algorithm assigns each of its domain values to a random cluster. Then for each variable x along the ordering O, it determines the best possible cluster assignment for x assuming that the assignments of the other variables are fixed. The algorithm repeats the assignment process until convergence. Since the cluster assignment step for each variable always reduces the objective function given in Eq. (3), Algorithm 1 is guaranteed to reach a local optima. Formally, Theorem 3. Algorithm 1 is guaranteed to converge to a local minima.

Once we have obtained the joint-clusters, we can use Algorithm 2 to create a collection of Markov networks for each formula f , each of which has smaller treewidth as well as variables with smaller domain size than the Markov network obtained using the encoding described in the previous section. This reduces the complexity of the junction tree algorithm. The basic idea in Algorithm 2 is to create one first-order formula f for each cluster and attach to it a weight equal to the cluster center. The formula represents a subset of groundings of f , the partition function of which can be computed efficiently by ignoring the weight potential. We summarize the computational complexity of using the junction tree algorithm for inference on the encoding returned by Algorithm 2 in the following theorem: Encode f as a Markov network G, and Add G to G. return G.

Experiments

Setup

We evaluate the graphical model encodings proposed in our paper by using them within two inference algorithms: (1) Gibbs sampling to compute marginal probabilities and (2) MaxWalkSAT for MAP inference. Specifically, we perform the counting sub-step within both inference algorithms using our new graphical model encodings for the counting problem. We compare our exact encoding as well as approximate encoding methods with the encoding approach proposed in Venugopal et al. (we refer to this as '#SG'). We conducted our experiments on the following three datasets:

(i) Student MLN having the formula ¬Student(x, +p) ∨ ¬Publish(x, z) ∨Cited(z, +u) (ii) WebKB MLN from the Alchemy web page (iii) Citation Information-Extraction (IE) MLN form the Alchemy web page The primary goal of our experimental evaluation is to test the accuracy and scalability of our new encodings.

In our experiments, we implemented our system on top of the publicly available Magician system [Venugopal et al., 2016] that uses #SG. That is, we used the same counting subroutines as the ones used by Magician, but replaced the graphical model encoding used in Magician with our proposed exact and approximate encoding methods respectively.

Results for MaxWalkSAT.

Fig. 4 shows the 'cost' of the MAP solution returned by each solver (the cost is typically reported when the MAP problem, which is a maximization problem, is solved as a minimization problem) as a function of time. The smaller the cost, the better the solver. Each solver was given 200 seconds for each dataset. We tested four versions of our solvers against '#SG.' They are '#WSG,' which is the exact encoding approach and three different 'C-p's which are obtained by using the clustering approach described in section 4, where the number of clusters equals p% of the number of constants in the domain.

We observe that our new approaches are better than '#SG' and 'C-10' which compresses the parameter space to 10% of the original is the best performing solver. We conjecture that this is because, when p is small, MaxWalkSAT performs more flips/second which results in a better exploration of the state-space, which in turn improves its accuracy.

Results for Gibbs Sampling

For Gibbs sampling, we evaluate the convergence of the sampler and the accuracy of the computed marginals.

For measuring convergence of the Gibbs sampler, we use the Gelman-Rubin (G-R) Statistic [Gelman and Rubin, 1992]. For a well-mixed sampler, the G-R statistic should ideally decrease over time illustrating that the MCMC chain has mixed. To compute the G-R statistics, we set up five Gibbs samplers from random initialization and measure within chain and across chain variances for the marginal probabilities for 1000 randomly chosen ground query atoms. We compute the G-R statistics for each of these query atoms and report the mean G-R statistic.

For measuring accuracy, we use the KL-divergence between the average true marginal probabilities of ground query atoms and the average approximate marginal probability computed by the Gibbs sampler using our encodings. Note that obtaining the true marginal probabilities is infeasible for arbitrary evidence. Therefore, for this experiment, we did not use evidence, in which case, the average true marginal probability is equal to 0.5. Fig. 5 compares the convergence of the Gibbs sampler for #SG as well as different clustering based approximations. We observe that C-10 has the best convergence, and as we in-crease the number of clusters, the convergence gradually becomes worse. When we have fewer clusters, the complexity of weighted counting is smaller, which helps us draw more samples and achieve faster convergence.

Fig. 6 compares the accuracy of Gibbs sampler when used with #SG as well as different clustering based approximations. As before, for a smaller number of clusters, we get higher accuracy within a fixed time (since we can collect more samples/second). As we increase the number of clusters, for the same time interval we collect fewer samples, and therefore, the accuracy of computing the marginals is reduced.

In both Fig. 5 and Fig. 6, the performance of #WSG was almost identical to C-90. Therefore, for readability, we do not show the curves for #WSG.

Conclusion

In this paper, we developed two novel graphical model encodings for MLN formulas that have different weights for different subsets of groundings. Both these encodings are useful in solving a computationally complex counting problem that manifests itself in several sampling and local-search based MLN inference algorithms. Namely, counting the sum of weights of the groundings of an MLN formula that are sat- isfied in a given world. The first encoding was an exact encoding such that the partition function of the graphical model corresponds exactly to the number of satisfied groundings in the MLN formula. The second was an approximate encoding that clustered formula groundings with approximately similar weights together, which in several cases, reduces the treewidth of the encoded graphical model. We incorporated our encoding in two well-known inference algorithms, the Gibbs sampling, and the MaxWalkSAT. We demonstrated through experiments that both of our encoding techniques result in more scalable and accurate inference algorithms.

Although our approach achieves scalability for the inference task of the untied MLNs, the greatest challenge is to learn these models from the data. Since inference is a substep of many popular learning methods, in future, we will focus on developing a scalable learning algorithm for untied MLNs by extending our current work. We will also explore other efficient encodings (e.g., variational inference based encoding) for solving the counting task. Finally, since our cluster-based encoding introduces symmetry in the otherwise asymmetric untied MLNs, in future, we will implement novel lifted inference algorithms for these MLNs by leveraging our clustering idea.