Gibbs Sampling in Probabilistic Description Logics with Deterministic Dependencies

Abstract

In many applications there is interest in representing both probabilistic and deterministic dependencies. This is especially the case in applications using Description Logics (DLs), where ontology engineering usually is based on strict knowledge, while there is also the need to represent uncertainty. We introduce a Markovian style of probabilistic reasoning in rst-order logic known as Markov logic and investigate the opportunities for restricting this formalism to DLs. In particular, we show that Gibbs sampling with deterministic dependencies speci ed in an appropriate fragment remains correct, i.e., probability estimates approximate the correct probabilities. We propose a Gibbs sampling method incorporating deterministic dependencies and conclude that this incorporation can speed up Gibbs sampling signi cantly.

Introduction

While probabilistic languages often represent uncertain evidence and exceptions, there is also the need to further represent deterministic knowledge. As a tradeo , there are probabilistic formalisms that allow for the representation of neardeterministic knowledge, i.e., knowledge represented with probabilities approximating 0 or 1. However, since knowledge representation with logic in its origin is based on strict formulas, we believe it is important to consider the perspective in which uncertainty is an additional feature to deterministic knowledge. This perspective is especially suited for Description Logics (DLs) [ 3 ], where ontology engineering usually is based on specifying strict taxonomies with strict disjointness and strict domain and range restrictions on roles, and where the tradeo between complexity and expressivity is well-studied.

Gibbs sampling [ 2, 4, 5 ] is a Markov chain Monte Carlo (MCMC) method to estimate a conditional probability distribution by generating samples from a simpler distribution. Since Markov chains constructed with Gibbs sampling are known to be regular, estimates of probabilities are known to be correct in the long run. Though this method is often used in practice, it is insu cient for logic in the presence of deterministic dependencies, since in this case the correct ow of the ? This work is supported by the European Union project CASAM (FP7-217061). chain usually is broken down. Similarly, Gibbs sampling with near-determinism involves transitions with probabilities approximating 0, leading to unacceptably long convergence times (cf. [ 7 ]). In order to solve this problem, in [ 7 ] the MCSAT algorithm is proposed. MC-SAT samples new states with respect to a set of auxiliary variables. However, while MC-SAT is a powerful method to compute conditional probabilities, it is restricted to near-determinism.

In this paper, we propose a formalism based on Markov logic [ 6 ] and show that by restricting the deterministic part of the knowledge to a fragment of ALH, Markov chains constructed with Gibbs sampling remain regular. To the best of our knowledge, until now there has not been a language discovered allowing for global deterministic dependencies in Gibbs sampling. We present a Gibbs sampling method incorporating these dependencies and conclude that this incorporation can speed up Gibbs sampling signi cantly.

In Sect. 2, we introduce probabilistic knowledge representation and Markov networks. In Sect. 3, the formalism of Markov logic [ 6 ] is presented and extended to incorporate deterministic dependencies. Further, we de ne the language ALH for the representation of determinism. Then, in Sect. 4, we introduce to problems with Gibbs sampling in knowledge representation. In Sect. 5, we propose a Gibbs sampling algorithm incorporating deterministic dependencies in ALH . Finally, in Sect. 6 we summarize the results. 2

Preliminaries

For the representation of probabilistic and deterministic knowledge, we will focus on Description Logics (DLs). We assume the reader to be familiar with the syntax and semantics of DLs [ 3 ] and rst-order logic [ 4 ]. 2.1

Probabilistic Knowledge Representation The basic notion of probabilistic knowledge representation formalisms is the socalled random experiment. A random variable X is a function assigning a value to the result of a random experiment. In the sequel, we will use only Boolean random variables with values 1 or 0 (true or false, respectively).

Let X = fX1; :::; Xng be the ordered set of all random variables of a random experiment. An event X = x is an assignment X1 = x1; :::; Xn = xn to all random variables, and a certain vector of values x is referred to as a possible world. If it is clear from the context, we write x as an abbreviation for X = true and :x as an abbreviation for X = false. A possible world can be associated with a probability P (X = x) = p, where p is a real value in [0; 1].1

A distribution P(X) of a random variable X is a mapping from the domain of X to probability values in [0; 1] such that the values of X sum up to 1. Distributions can be de ned for (ordered) sets of random variables as well. A mapping P(X1; : : : ; Xk) from the domain of a set of random variables to the 1 We assume the reader to be familiar with Kolmogorov's axioms of probability. k-dimensional cross product of [0; 1] such that all combinations of values sum up to 1 is called joint distribution. A full joint distribution P(X1; : : : ; Xn) is a joint distribution where all random variables of a random experiment are involved. Let = fx1; :::; xrg be the set of all possible worlds. In order to specify a full joint distribution P(X1; : : : ; Xn), probabilities P (X = xi) for all xi must be given such that Pir=1 P (X = xi) = 1. The expression P(X1; : : : ; Xm; xm+1; : : : ; xl) denotes an m-dimensional distribution where the values of Xm+1; :::; Xl have been xed. In slight misuse of notation, we sometimes write e for these xed values.

The conditional probability distribution of X given evidence e is de ned by P(X j e) = PP( X(e;)e) = P(X; e) = <P (x; e); P (:x; e)>, where is a normalizing constant. Note that P(X j e) is only de ned, if P (e) > 0.

The most common query types in probabilistic knowledge representation are the conditional probability query, i.e., the computation of P(X j e) and the maximum a posteriori (MAP) query, where the objective is to nd the most likely assignment of values to random variables X1; :::; Xm given evidence e, i.e., the computation of argmax X1;:::;Xm P(X1; :::; Xm j e). In this paper, we will focus on the former query type. 2.2

Markov Networks Since the representation of P(X1; : : : ; Xn) in principle requires the speci cation of 2n probability values, there is interest in formalisms with a less complex representation. The main idea to achieve a more compact representation is that one can exploit independence assumptions. Usually, this is the case in graph-based formalisms, where the representation of the full joint probability distribution can be decomposed into di erent factors. Besides Bayesian networks, the most important graph-based formalism is the formalism of Markov networks [ 1, 2 ].

A Markov network graph is a tuple G = (X; E), where X = fX1; :::; Xng is a set of nodes corresponding to the random variables of the domain and E is a set of undirected edges (Xi; Xj ), i 6= j, between these nodes. A clique C is a subgraph of G, whose nodes are all adjacent to each other. Let XC be the set of nodes contained in C. A clique C is called maximal, if there is no other clique Ci with XC XCi . Further, C = fC1; :::; Cmg is a set of cliques of G consisting of all nodes of X, i.e., XC1 [ ::: [ XCm = X.

A Markov network M = (G; F ) consists of a Markov network graph G and a set F which is comprised of non-negative real-valued functions fi for each clique Ci; i = 1; :::; m in G. A full joint probability distribution to be expressed can be decomposed into factors fi (cf. [ 1, 2 ]) such that

P (X = x) =

m 1 Y fi(xCi ) Z i (1) where Z is a normalizing constant summing over the products in (1) for all possible worlds x ensuring that Prk=1 P (X = xk) = 1. Note that each fi does only depend on the values of random variables corresponding to its clique Ci.

Markov Description Logics

Markov Logic The formalism of Markov logic [ 6 ] provides a means to combine the formalism of Markov networks with the expressivity of rst-order logic. A knowledge base in Markov logic is called a Markov logic network MLN = (F ; W). It consists of a multiset of rst-order formulas F = fF1; :::; Fpg and a multiset of real number weights W = fw1; :::; wpg such that each wi is associated to Fi. For simplicity, we use the notation of a set of weighted formulas wi Fi. An example Markov logic network is MLN 1 = f4 8x P (x) ! Q(x); 1:1 P (i)g, where i is a constant.

Let = fc1; :::; csg be the set of all constants mentioned in F . A grounding of a formula Fi is a substitution of all variables in the matrix of Fi with constants from (this corresponds to a domain closure).2 A Markov logic network MLN can be converted to a ( nite) set of weighted ground clauses Cl = fcl1; :::; clmg. Each atom appearing in Cl is referred to as a ground atom. The set of all these ground atoms corresponds to a set of Boolean random variables X = fX1; :::; Xng. Consequently, for each MLN with a xed set of constants , there is a set of possible worlds x. When a world x does not satisfy a formula, the idea is to ensure that this world is less probable rather than impossible as in rst-order logic.

For each MLN there is a corresponding Markov network M = (G; F ), with G = (X; EMLN ), where EMLN is the set of pairs of ground atoms (Xi; Xj ) appearing together in at least one cl i and a function fi 2 F for each cli 2 Cl . Note that each weighted ground clause cli corresponds to a (not necessarily maximal) clique Ci. In notation slightly di erently from [ 6 ], we specify the full joint distribution of a MLN with (1), where Note that Qim=1 exp(wi) = Qim=1 exp(ln fi(xCi )) = exp( Pim=1 ln fi(xCi )), where the last term often is used in the context of statistical physics with ln fi(xCi ) called an energy function [ 2, 5 ]. The advantage of using exp in Markov logic is that P (X = x) > 0 and that it is possible to specify w 2 R. There is often interest to represent a domain with both deterministic and probabilistic dependencies. While in [ 6 ] deterministic dependencies are approximated by assigning large weights to formulas, we propose to incorporate deterministic constraints to Markov logic in the context of DLs.

De nition 1. A Markov DL knowledge base KBM is a tuple (T ; A), where T is comprised of sets Tdet and Tw of deterministic resp. weighted axioms and A is comprised of sets Adet and Aw of deterministic resp. weighted assertions. 2 An existentially quanti ed formula is replaced by a disjunction of its groundings. Under consideration of a domain closure, corresponding Markov networks are similar to the ones introduced in Sect. 3.1. However, in Markov DL knowledge bases Cl = fcl1; :::; clmg is the set of weighted and deterministic ground clauses. We specify the full joint probability distribution of KBM with (1), where ( exp(wi), if cli is weighted and xCi satis es cli 0, if cli is deterministic and xCi does not satisfy cli 1, otherwise. (3) An advantage of having both deterministic and probabilistic dependencies is that initial ontology engineering is done as usual with standard reasoning support and with the possibility to add weighted axioms and weighted assertions on top of the strict fundament. Since lots of possible worlds do not have to be considered because their probability is known to be 0, probabilistic reasoning can be signi cantly faster.

The language for representing Tw and Aw can be any DL in which it is reasonable to assume a xed set of constants = fc1; :::; csg such that it is possible to compute a nite set of weighted ground clauses. For the representation of deterministic knowledge, in this paper we use the language ALH , a rather simple DL without an assertional component (i.e., we are not allowing for deterministic assertions). An ALH knowledge base KB consists of a set T of terminological axioms as depicted in Table 1, where A; B are atomic concepts and R; S are atomic roles with the additional restriction that equivalences as well as terminological cycles are not allowed. The semantics is de ned as usual. 9R:> v A domain restriction on roles > v 8R:A range restriction on roles Example 1. Let KBM = (fLynx v Animal ; Animal v :Plant g; f1 :1 Lynx (i ); 0 :6 Plant (i )g), where Tw = Adet = fg. Under domain closure there are 23 possible worlds xk (where e.g. Lynx is abbreviated with L): x1 = <L(i ); A(i ); P (i )> x2 = <L(i ); A(i ); :P (i )> x3 = <L(i ); :A(i ); P (i )> x4 = <L(i ); :A(i ); :P (i )> x5 = <:L(i ); A(i ); P (i )> x6 = <:L(i ); A(i ); :P (i )> x7 = <:L(i ); :A(i ); P (i )> x8 = <:L(i ); :A(i ); :P (i )> The full joint probability distribution is speci ed with respect to the set Cl = f:Lynx (i ) _ Animal (i ), :Animal (i ) _ :Plant (i ), 1 :1 Lynx (i ); 0 :6 Plant (i )g. The normalizing constant Z = 0 + exp(1:1) + 0 + 0 + 0 + 1 + exp(0:6) + 1 6:83 such that e.g. P (X = x7) ex6p:(803:6) 0:267. In order to keep the example simple, we do not consider roles (but the general structure would be the same).

Gibbs Sampling for Reasoning about Knowledge

Answering conditional probability queries P(X j e) by simply applying the full joint probability distribution is intractable [ 4 ]. Sampling or Monte Carloalgorithms avoid this problem by generating samples from a probability distribution which is much easier to compute. The objective is to approximate P(X j e). Sampling is like \coin ipping": Random numbers in [0; 1] are generated and a variable Xi is assigned true resp. false, if the corresponding number is lower resp. greater than the respective probability in the distribution of Xi.

A Markov chain (of length k) is a sequence of states x1; :::; xk (a state corresponds to a possible world) where each successing state only depends on the current state. Markov chain Monte Carlo (MCMC) algorithms [ 2, 4 ] are a powerful class of sampling algorithms walking through the state space = fx1; :::; xrg. With respect to an arbitrary order, each non-evidence variable Xi; i = 1; :::; m is sampled. This process is repeated N -times such that k = m N . After k 1 steps, the fractions of the number of states visited with X = x resp. X = :x are taken as the estimated probabilities of P(X j e).

Let xi be an assignment to X1; :::; Xi 1; Xi+1; :::; Xn. Gibbs sampling [ 2, 4, 5 ] is a special case of MCMC, where the probability of a transition T (xt ! xt+1) is T ((xi; xi) ! (x0i; xi)) = P (x0i j xi). In graph-based formalisms such as Markov networks, Gibbs sampling can be optimized by exploiting the graph structure: Let C1; :::; Cs be all cliques containing the node Xi. The Markov boundary of Xi is the set of its neighbours MB (Xi) = XC1 [ : : : [ XCs n fXig. If the values of MB (Xi) are known, denoted mb(Xi), it shields Xi from in uences of all other nodes in G, i.e., P(Xi j x1; :::; xi 1; xi+1; :::; xn) = P(Xi j mb(Xi)) = <P (xi; mb(Xi)); P (:xi; mb(Xi))>.

A Markov chain is regular if there is a number v such that for all pairs of states xi; xj the probability of getting from xi to xj in v steps is greater than 0 [ 2 ]. If a Markov chain is regular (in Markov networks if fi > 0 for all fi 2 F ) the probability distribution of the states converges to a unique stationary distribution . Finally, in the case of Gibbs Sampling, (xi) is known to be equal to P (xi j e). Markov chains through Gibbs Sampling and deterministic dependencies usually are not regular and can break down the state graph into disconnected regions: Example 2. Consider two ground atoms X1; X2 with the deterministic constraint X1 X2. The state graph for applying Gibbs sampling is depicted in Fig. 1. If the chain starts with (0; 0), it will never reach (1; 1). Consequently, (0; 0) = 1 and (1; 1) = 0, though there is no information of any preference.

Similarly, Gibbs sampling with near-determinism involves transitions with probabilities approximating 0, leading to unacceptably long convergence times (cf. [ 7 ]). Thus, since (near-)determinism is required in many applications, Gibbs sampling in general is not su cient for reasoning about knowledge. De nition 2. Let D be a set of deterministic dependencies. A Markov chain is regular with respect to D if there is a number v such that for all pairs of states xi; xj both satisfying D, the probability of getting from xi to xj in v steps is greater than 0.

A Markov chain being regular with respect to D has a unique stationary distribution , if the initial state x1 satis es D, i.e., P (X = x1) > 0. The di erence to regular Markov chains de ned in the previous section is that there are states xi with P (X = xi) = 0 that are simply not stepped into.

As can be seen from Example 2, the regularity of the Markov chain is broken, if X1 and X2 are constrained to be equal. This is also the case if they are constrained to be di erent. We will now show that it is possible to run a Markov chain constructed with Gibbs sampling that is regular with respect to deterministic constraints in ALH .

Theorem 1. Let KBM be a Markov DL knowledge base where Tdet is represented with ALH and Adet is empty. Then, a Markov chain constructed with Gibbs sampling is regular with respect to Tdet .

Proof. In order to prove the regularity, it is important to gure out states satisfying or falsifying Tdet . Ground clauses derived from disjointness axioms are of the form :At1 _ :At2, and ground clauses derived from all other axioms in ALH are of the form :At1 _ At2, where At1 and At2 are ground atoms. Therefore, clauses derived from Tdet are falsi ed only if At1 is assigned 1 (true) and At2 assigned 0 (false) or if both At1 and At2 are assigned 1. Since in ALH there are no cycles, an order X1 < ::: < Xn can be de ned for all ground atoms such that for all ground clauses :At1 _ At2 no ground atom At2 is lower in the order than At1. Atoms only mentioned in clauses :At1 _ :At2 can be added arbitrarily. Then, it is possible to construct a tree, where each node respects the de ned order and corresponds to a state (x1; :::; xn), and where the root node is a state where all atoms are assigned with 0, i.e., (0; :::; 0). For every 0 in (0; :::; 0), there is exactly one child node where the corresponding 0 is changed to 1. Then, for every 0 preceding the leftmost 1 in a node, there is also exactly one child node where the corresponding 0 is changed to 1. After constructing all children nodes, the tree contains exactly 2n nodes (i.e., one node for each state). This tree has the following property: If a node represents a state satisfying Tdet , then its parent node also represents a state satisfying Tdet . Since in ALH the state (0; :::; 0) satis es Tdet , for each node it holds that if it satis es Tdet then there is a path from this node to (0; :::; 0) satisfying Tdet . tu We will now specify a Gibbs sampling algorithm with deterministic dependencies in ALH . Instead of answering conditional probability queries P(X j e), with this algorithm it is possible to answer probability queries P(X) conditioned on the ground clauses obtained from Tdet .

Our objective is to exploit the fact that { due to restrictions in Tdet { there are a lot of state transition possibilities where the bit- ip probability (the probability that a random variable will change its value) is 0, i.e., a lot of cases in which one does not need to sample at all. We propose to assign an integer i to each random variable Xi. i is initially 0 and is increased whenever a bit- ip occurs for a variable Xj ; i 6= j that restricts the bit- ip probability of Xi to be 0 (\set"), and i is decreased whenever this speci c restriction does not hold any more (\release"). As long as i > 0, Xi is not sampled and we say that Xi is \blocked". Settings (+1) and releases ( 1) are depicted in Table 2 for groundings of all ALH -axioms with individuals i; j. Consider e.g. the rst row in the second column of Table 2: If the ground atom A(i) is 0 in xt and is 1 in xt+1 then B(i) is known to be 1 (otherwise xt+1 would violate this constraint) and B(i) > v 8R:A is increased, i.e., B(i) is blocked by A(i). Individuals with indicate that every individual of the closed domain has to be considered separately.

The Markov chain has to start with a state x1 satisfying Tdet . Such a state can be found with MaxWalkSat [ 9 ], a local search algorithm for the weighted satis ability problem. All deterministic clauses are assigned with a weight greater than the sum l of all weights of clauses obtained from Tw [ Aw . Then, a state violating clauses of total weight l or less satis es Tdet (cf. [ 9 ]). The state (0; :::0) is known to satisfy Tdet such that the chain could also start from this node, but MaxWalkSat will nd a node that will be (near to) the mode of the distribution such that the chain will approximate faster. Since all transitions to states not satisfying Tdet have probability 0, the whole chain does only involve states satisfying Tdet . In other words, it is guaranteed that P (mb(Xi)) > 0 such that the transition distribution P(Xi j mb(Xi)) is de ned. Given KBM , this distribution is computed with (1) where functions fi are de ned according to (3).

The Gibbs-ALH -algorithm is depicted in Fig. 2. If the value of Xi is ipped, the method setRelease is called with parameters Xi, the old and new value of Xi, xi resp. x0i, and the set Cl i of deterministic ground clauses containing Xi. This method sets and releases blockings as speci ed in Table 2. At the beginning of the process, it has to be ensured that all initial blockings are set. This is done by calling set , a function similar to setRelease, but only increasing i. Then, the settings and releases depicted in Table 2 ensure that for each Xi, i > 0 if and only if either P (xi j mb(Xi)) = 0 or P (:xi j mb(Xi)) = 0. Finally, after n N samples, the Boolean vector N[X] of counts over X is normalized by and the result represents the estimated distribution of P(X). The method can further be optimized by restricting X to a set of ground atoms assumed to be relevant for the query answer.

Algorithm Gibbs-ALH (KBM ; X; N ) Output An estimate of P(X) local variables:

N[X], a vector of counts over X Cl , a set of all (weighted) ground clauses obtained from KBM X = fX1; :::; Xng, the set of all random variables

= f 1; :::; ng, a set of integers initially assigned with 0 x = (x1; :::; xn), an initial state satisfying Tdet for i = 1 to n do if ( i = 0) set(Xi, :xi, xi, Cl i); for j = 1 to N do for i = 1 to n do if ( i = 0) sample the value x0i of Xi in x from P(Xi j mb(Xi)); if (xi 6= x0i) setRelease(Xi, xi, x0 , Cl i);

i

N[x] N[x] + 1 where x is the value of X in x return <N[ 1 ]; N[0]>

Conclusion

We have shown that deterministic dependencies in ALH retain the regularity of Markov chains constructed with Gibbs sampling. Further, we proposed a method incorporating these dependencies. Since lots of redundant samples are not generated by this method, we conclude that signi cant e ciency is gained. This is in contrast to previous results, where Gibbs sampling with (near-)determinism is known to give poor results. While Tdet is speci ed with ALH , the sets Tw and Aw of weighted axioms resp. weighted assertions can e.g. be speci ed in the expressive DL SHQ. In [ 7 ] it is shown that Gibbs sampling slows down more and more when clauses are assigned with weights beyond 4. Note that a world not satisfying a ground clause with weight 4 is as probable as a world not satisifying e3 ground clauses with weight 1. Thus, for ground clauses not intended to represent deterministic knowledge, a weight around 4 usually will suit the requirements of a knowledge engineer. However, often, in addition to axioms in ALH , there is also the need to represent deterministic assertions in Adet as well as deterministic functional- and transitive roles. Further research is required, in order to also incorporate these dependencies. Another open task is the implementation of the proposed method in order to compare its runtime performance with other approaches estimating probability distributions under consideration of (near-)deterministic knowledge (such as MC-SAT [ 7 ] or SampleSearch [ 8 ]).

References

1. Pearl , J. : Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference . Morgan Kaufmann, San Mateo, CA, 1988 .

2. Koller , D. , Levy , A. , Pfe er , A., Getoor , L. , Taskar , B. : Graphical Models in a Nutshell . In: Introduction to Statistical Relational Learning , pages 13 { 55 , Cambridge, MA: MIT Press, 2007 .

3. Baader , F. , Calvanese , D. , McGuinness , D. L. , Nardi , D. , Patel-Schneider , P.F. : The Description Logic Handbook: Theory, Implementation and Applications . Cambridge University Press, January 2003 .

4. Russell , S. , Norvig , P. : Arti cial Intelligence: A Modern Approach (Second Edition) Prentice Hall , 2003 .

5. Geman , S. , Geman , D. : Stochastic Relaxation, Gibbs Distribution and Bayesian Restoration of Images. IEE Transactions on Pattern Analysis and Machine Intelligence 6 , pages 721 { 741 , 1984 .

6. Domingos , P. , Richardson , M.: Markov Logic: A Unifying Framework for Statistical Relational Learning . In: Introduction to Statistical Relational Learning , pages 339 { 371 , Cambridge, MA: MIT Press, 2007 .

7. Poon , H. , Domingos , P. : Sound and E cient Inference with Probabilistic and Deterministic Dependencies . In Proceedings of AAAI-06 , Boston, Massachusetts, July 2006 .

8. Gogate , V. , Dechter , R.: SampleSearch: Importance Sampling in presence of Determinism . ICS technical report (Submitted) , July 2009 .

9. Jiang , Y. , Kautz , H. , Selman , B. : Solving Problems with Hard and Soft Constraints using a Stochastic Algorithm for MAX-SAT . In First International Joint Workshop on Arti cial Intelligence and Operations Research , 1995 .