Log-Linear Description Logics

1 Introduction

Numerous real-world problems require the ability to handle both deterministic and uncertain knowledge. Due to differences in epistemological commitments made by their particular AI communities, researchers have mostly been concerned with either one of these two types of knowledge. While the representation of purely logical knowledge has been the focus of knowledge representation and reasoning, reasoning about knowledge in the presence of uncertainty has been the major research theme of the machine learning and uncertainty in AI communities. Nevertheless, there have been some attempts to combine the diverse concepts and methods by several researchers. The resulting approaches include probabilistic description logics [Jaeger, 1994; Koller et al., 1997; Lukasiewicz and Straccia, 2008] and statistical relational languages [Getoor and Taskar, 2007] to name but a few. While the former have mainly been studied on a theoretical level, statistical relational languages have been proven useful for a number of practical applications such as data integration [Niepert et al., 2010] and NLP [Riedel and MezaRuiz, 2008]. A line of work that has regained importance with the use of semantic web languages is the combination of probabilistic models with description logics [Lukasiewicz and Straccia, 2008]. Probabilistic description logic programs [Lukasiewicz, 2007], for instance, combine description logic programs under the answer set and well-founded semantics with independent choice logic [Poole, 2008].

In this paper, we represent and reason about uncertain knowledge by combining log-linear models [Koller and Friedman, 2009] and description logics [Baader et al., 2003].

Log-linear models allow us to incorporate both probabilistic and deterministic dependencies between description logic axioms. The ability to integrate heterogeneous features make log-linear models a commonly used parameterization in areas such as NLP and bioinformatics and a number of sophisticated algorithms for inference and parameter learning have been developed. In addition, log-linear models form the basis of some statistical relational languages such as Markov logic [Richardson and Domingos, 2006].

The logical component of the presented theory is based on description logics for which consequence-driven reasoning is possible [Kr¨otzsch, 2010; Baader et al., 2005]. We focus particularly on the description logic EL++ which captures the expressivity of numerous ontologies in the medical and biological sciences and other domains. EL++ is also the description logic on which the web ontology language profile OWL 2 EL is based [Baader et al., 2005]. Reasoning services such as consistency and instance checking can be performed in polynomial time. It is possible to express disjointness of complex concept descriptions as well as range and domain restrictions [Baader et al., 2008]. In addition, role inclusion axioms (RIs) allow the expression of role hierarchies r ⊑ s and transitive roles r ◦ r ⊑ r.

In real-world applications, uncertainty occurs often in form of degrees of confidence or trust. The semantic web community, for instance, has developed numerous data mining algorithms to generate confidence values for description logic axioms with ontology learning and matching being two prime applications. Most of these confidence values have no clearly defined semantics. Confidence values based on lexical similarity measures, for instance, are in widespread use while more sophisticated algorithms that generate actual probabilities make often na¨ıve assumptions about the dependencies of the underlying probability distribution. Hence, formalisms and inference procedures are needed that incorporate degrees of confidence in order to represent uncertain axioms and to compute answers to probabilistic queries while utilizing the logical concepts of coherency and consistency.

To respond to this need, we introduce log-linear description logics as a novel formalism for combining deterministic and uncertain knowledge. We describe a convenient representation of log-linear description logics that allows us to adapt existing concepts and algorithms from statistical relational AI to answer standard probabilistic queries. In particular, we formulate maximum a-posteriori queries and present an efficient algorithm that computes most probable coherent models, a reasoning service not supported by previous probabilistic description logics. We conclude the paper with an experimental evaluation of ELOG, our implementation of a log-linear description logic reasoner.

2 Description Logics

Description logics (DLs) are a family of formal knowledge representation languages. They provide the logical formalism for ontologies and the Semantic Web. We focus on the particular DL EL++ without concrete domains, henceforth denoted as EL++ [Baader et al., 2005]. We conjecture that the presented ideas are also applicable to other description logics for which materialization calculi exist [Kr¨otzsch, 2010].

Concept and role descriptions in EL++ are defined recursively beginning with a set NC of concept names, a set NR of role names, and a set NI of individual names, and are built with the constructors depicted in the column "Syntax" of Table 1. We write a and b to denote individual names; r and s to denote role names; and C and D to denote concept descriptions. The semantics are defined in terms of an interpretation I = (ΔI , ·I ) where ΔI is the non-empty domain of the interpretation and ·I is the interpretation function which assigns to every A ∈ NC a set AI ⊆ ΔI , to every r ∈ NR a relation rI ⊆ ΔI × ΔI , and to every a ∈ NI an element aI ∈ ΔI .

A constraint box (CBox) is a finite set of general concept inclusion (GCIs) and role inclusion (RIs) axioms. Given a CBox C, we use BCC to denote the set of basic concept descriptions, that is, the smallest set of concept descriptions consisting of the top concept ⊤, all concept names used in C, and all nominals {a} appearing in C. A CBox C is in normal form if all GCIs have one of the following forms, where C1, C2 ∈ BCC and D ∈ BCC ∪ {⊥}:

and if all role inclusions are of the form r ⊑ s or r1 ◦ r2 ⊑ s. By applying a finite set of rules and introducing new concept and role names, any CBox C can be turned into a normalized CBox of size polynomial in C. For any EL++ CBox C we write norm(C) to denote the set of normalized axioms that result from the application of the normalization rules to C.

An interpretation I satisfies an axiom c if the condition in the column "Semantics" in Table 1 holds for that axiom.

An interpretation I is a model of a CBox C if it satisfies every axiom in C. A concept C is subsumed by a concept D with respect to a CBox C, written C ⊑C D, if C I ⊆ DI in every model of C. A normalized CBox is classified when subsumption relationships between all concept names are made explicit. A CBox C is coherent if for all concept names C in C we have that C ̸⊑C⊥. For every axiom c and every set of axioms C ′ , we write C |= c if every model of C is also a model of {c} and we write C |= C ′ if C |= c′ for every c′ ∈ C ′ . For a finite set NU ⊆ NC ∪NR of concept and role names the set of all normalized axioms constructible from NU is the union of (a) all normalized GCIs constructible from concept and role names in NU and the top and bottom concepts; and (b) all normalized RIs constructible from role names in NU.

3 Log-Linear Models

Log-linear models are parameterizations of undirected graphical models (Markov networks) which are central to the areas of reasoning under uncertainty and statistical relational learning [Koller and Friedman, 2009; Getoor and Taskar, 2007]. A Markov network M is an undirected graph whose nodes represent a set of random variables {X1, ...,Xn} and whose edges model direct probabilistic interactions between adjacent nodes. A distribution P is a log-linear model over a Markov networkM if it is associated with:

• a set of features {f1(D1), ..., fk(Dk)}, where each Di is a clique inMand each fi is a function fromDi to R,
• a set of real-valued weights w1, ...,wk, such that

where Z is a normalization constant.

Arguably one of the more successful statistical relational languages is Markov logic [Richardson and Domingos, 2006] which can be seen as a first-order template language for loglinear models with binary variables. A Markov logic network is a finite set of pairs (Fi,wi), 1 ≤ i ≤ k, where each Fi is a first-order formula and each wi a real-valued weight associated with Fi. With a finite set of constants C it defines a log-linear model over possible worlds. A possible world x is a truth assignments to ground atoms (predicates without variables) with respect to C. Each variable Xj, 1 ≤ j ≤ n, corresponds to a ground atom and feature fi corresponds to the number of true groundings of Fi in possible world x.

4 Log-Linear Description Logics

Log-linear description logics integrate description logics with probabilistic log-linear models. While the syntax of loglinear description logics is that of the underlying description logic, it is possible (but not necessary) to assign real-valued weights to axioms. The semantics is defined by a log-linear probability distribution over coherent ontologies. In the remainder of the paper, we focus on the log-linear description logic EL++ without nominals and concrete domains 1 which we denote as EL++-LL.

1 We conjecture that the theory is extendable to capture nominals and concrete domains. However, we leave this to future work.

4.1 Syntax

The syntax of log-linear description logics is equivalent to the syntax of the underlying description logic except that it is possible to assign weights to GCIs and RIs. More formally, a EL++-LL CBox C = (C D, C U) is a pair consisting of a deterministic EL++ CBox C D and an uncertain CBox C U = {(c,wc)} which is a set of pairs (c,wc) with each c being a EL++ axiom and w a real-valued weight assigned to c. Given a EL++-LL CBox C we use BCC to denote the set of basic concept descriptions occurring in C D or C U .

While the deterministic CBox contains axioms that are known to be true, the uncertain CBox contains axioms for which we only have a degree of confidence. Intuitively, the greater the weight of an axiom the more likely it is true. Every axiom can either be part of the deterministic or the uncertain CBox but not both. The deterministic CBox is assumed to be coherent.

4.2 Semantics

The semantics of log-linear DLs is based on joint probability distributions over coherent EL++ CBoxes. The weights of the axioms determine the log-linear probability distribution. For a EL++-LL CBox (C D, C U) and a CBox C ′ over the same set of basic concept descriptions and role names, we have that

where Z is the normalization constant of the log-linear probability distribution P . The semantics of the log-linear description logic EL++-LL leads to exactly the probability distributions one would expect under the open world semantics of description logics as demonstrated by the following example.

Example 1. Let BCC = {C,D}, let C D = ∅, and let C U = {〈C ⊑ D, 0.5〉, 〈C ⊓ D ⊑⊥, 0.5〉}. Then 2 , P ({C ⊑ D,C ⊓ D ⊑⊥}) = 0, P ({C ⊑ D}) = Z -1 exp(0.5), P ({C ⊑ D,D ⊑ C}) = Z -1 exp(0.5), P ({C ⊓ D ⊑⊥ }) = Z -1 exp(0.5), P ({D ⊑ C}) = Z -1 exp(0), and P (∅) = Z -1 exp(0) with Z = 3 exp(0.5) + 2 exp(0).

4.3 Herbrand Representation

In order to formalize probabilistic queries for log-linear description logics we represent EL++-LL CBoxes as sets of first-order sentences modeling the uncertain and deterministic axioms. We begin by defining some basic concepts.

Definition 2. Let P be a set of predicate symbols and C be a set of constant symbols. An atom is an expression of the form p(t1, ..., tn) where p ∈ P and t1, ..., tn are variables or constant symbols. A literal is an atom or its negation. Let S be a set of first-order formulas built inductively from the literals, with universally quantified variables only. A grounding of a formula is obtained by replacing each variable with a constant symbol in C. The Herbrand base of S with respect to C is the set of ground atoms whose predicate symbols occur in S. Each subset of the Herbrand base is a Herbrand interpretation specifying which ground atoms are true. A Herbrand interpretation H is a Herbrand model of S, written as |=H S, if and only if it satisfies all groundings of formulas in S.

2 We omit trivial axioms that are present in every classified CBox such as C ⊑ ⊤ and C ⊑ C.

The set of formulas F listed in Table 2 is partially derived from the EL++ completion rules [Baader et al., 2005]. We are now in the position to define a bijective function ϕ that, given a finite set of concept and role names NU, maps each normalized EL++-LL CBox over NU to a subset of the Herbrand base of F with respect to NU.

Definition 3 (CBox Mapping). Let NC and NR be sets of concept and role names and let NU ⊆ NC ∪NR be a finite set. Let T be the set of normalized EL++ axioms constructible from NU. Moreover, let H be the Herbrand base of F with respect to NU. The function ϕ : ℘(T ) → ℘(H) maps normalized CBoxes to subsets of H as follows: (ϕ(C) = ⋃c∈C ϕ(c))

All predicates are typed meaning that r, s, ri, (1 ≤ i ≤ 3), are role names, C1,C2 basic concept descriptions, and D basic concept descriptions or the bottom concept.

We now prove that, relative to a finite set of concept and role names, the function ϕ induces a one-to-one correspondence between Herbrand models of the first-order theory F and coherent and classified EL++ CBoxes.

Lemma 4. Let NC and NR be sets of concept and role names and let NU ⊆ NC ∪ NR be a finite set. Let T be the set of normalized EL++ axioms constructible from NU and let H be the Herbrand base of F with respect to NU. Then,

• (a) for any C ⊆ T we have that if C is classified and coherent then ϕ(C) is a Herbrand model of F; and
• (b) for any H ⊆ H we have that if H is a Herbrand model of F then ϕ-1 (H) is a classified and coherent CBox.

From Lemma 4 we know that, relative to a finite set NU of concept and role names, each normalized CBox over NU that is classified and coherent, corresponds to exactly one Herbrand model of F. We extend the normalization of EL++ CBoxes to EL++-LL CBoxes as follows.

Lemma 4 provides the justification for constructing the logical representation of a EL++-LL CBox as follows: G is a set of weighted ground formulas carrying the uncertain information and it is derived from the axioms in the uncertain CBox C U as follows. For every pair (c, wc) ∈ C U we add the conjunction of ground atoms∧

to G with weight wc. The set K is constructed analogously from the deterministic CBox C D except that we do not associate weights with the ground formulas. 3

Example 6. Let C D = {C ⊑ D} and C U = {〈B ⊓ C ⊓ D ⊑ E, 0.5〉}. Then, normLL(C) = norm({C ⊑ D})∪norm({B⊓ C ⊓ D ⊑ E}) = {C ⊑ D,C ⊓ D ⊑ A,B ⊓ A ⊑ E} with A a new concept name. We have that ϕ(norm({C ⊑ D})) = {sub(C, D)} and ϕ(norm({B ⊓ C ⊓ D ⊑ E})) = {int(C,D,A), int(B,A,E)}. Hence, we add sub(C,D) to K and int(C, D, A) ∧ int(B, A, E) with weight 0.5 to G.

4.4 MaximumA-Posteriori Inference

Under the given syntax and semantics the first central inference task is the maximum a-posteriori (MAP) query: "Given a EL++-LL CBox, what is a most probable coherent EL++ CBox over the same concept and role names?" In the context of probabilistic description logics, the MAP query is crucial as it infers a most probable classical ontology from a probabilistic one. The MAP query also captures two important problems that frequently occur in the context of the Semantic Web: Ontology learning and ontology matching.

The following theorem combines the previous results and formulates the EL++-LL MAP query as a maximization problem subject to a set of logical constraints.

Theorem 7. Let C = (C D, C U) be a EL++-LL CBox, let NU be the set of concept and role names used in normLL(C), and let H be the Herbrand base of F with respect to NU. Moreover, let K be the set of ground formulas constructed from C D and let G be the set of weighted ground formulas constructed from C U . Then, with

we have that ϕ-1 ( ˆH) is a most probable coherent CBox over NU that entails C D .

By showing that every partial weighted MAX-SAT problem can be reduced to an instance of the EL++ MAP query problem of Theorem 7 in polynomial time and by invoking the complexity results for the former problem [Creignou et al., 2001] we can prove the following theorem.

3 Note that the number of formulas in G and K is equal to the number of axioms in C U and C D , respectively.

Theorem 8. The maximum a-posteriori problem for EL++- LL CBoxes is NP-hard and APX-complete.

Conversely, we can solve a MAP query by reducing it to a (partial) weighted MAX-SAT instance with a set of clauses polynomial in the number of axioms and basic concept descriptions. There exist several sophisticated algorithms for weighted MAX-SAT. We developed ELOG 4 , an efficient EL++-LL reasoner based on integer linear programming (ILP). Let F NU be the set of all groundings of formulas in F with respect to the set of constant symbols NU. For each ground atom gi occurring in a formula in G,K, or F NU we associate a unique variable xi ∈ {0, 1}. Let C G j be the set of indices of ground atoms in sentence Gj ∈ G, let C K j be the set of indices of ground atoms in sentence Kj ∈ K, and let C F j ( ¯ C F j ) be the set of indices of unnegated (negated) ground atoms of sentence Fj ∈ F NU in clausal form. With each formula Gj ∈ G with weight wj (without loss of generality we assume non-negative weights) we associate a unique variable zj ∈ {0, 1}. Then, the ILP is stated as follows

Every state of the variables xi of a solution for the ILP corresponds (via the function ϕ) to a most probable classified and coherent CBox over NU that entails C D . Adding all constraints of type (4) at once, however, would lead to a large and potentially intractable optimization problem. Therefore, we employ a variant of the cutting plane inference algorithm first proposed in the context of Markov logic [Riedel, 2008]. We first solve the optimization problem without constraints of type (4). Given a solution to the partial problem we determine in polynomial time those constraints of type (4) that are violated by this solution, add those to the formulation, and solve the updated problem. This is repeated until no violated constraints remain. Please note that the MAP query derives a most probable CBox and classifies it at the same time.

4.5 Conditional Probability Inference

The second type of inference task is the conditional probability query: "Given a EL++-LL CBox, what is the probability of a conjunction of axioms?" More formally, given a EL++- LL CBox C and a set C Q of normalized EL++-LL axioms over the same concept and role names, the conditional probability query is given by P (C Q | C) = ∑{C′ :CQ⊆C′ } P (C ′ ) where each C ′ is a classified and normalized CBox over the same set of basic concept descriptions and role names.

4 http://code.google.com/p/elog-reasoner/

Algorithm 1 MC-ILP for EL++-LL

Input: weights wj and variables zj of the MAP ILP 1: cj ←wj for all j 2: x(0) ← solution of ILP with all wj set to 0 3: for k ← 1 to n do 4: set all zj and all wj to 0 5: for all zj satisfied by x(k-1) do 6: with probability 1 - e-cj fix zj to 1 in ILP(k) 7: end for 8: for all zj not fixed to 1 do 9: with probability 0.5 set wj to 1 in ILP(k) 10: end for 11: x(k) ← solution of ILP(k) 12: end for

Determining the exact conditional probability is infeasible in the majority of use-cases. Hence, for the reasoner ELOG 4 , we developed a Markov chain Monte Carlo (MCMC) variant similar to MC-SAT, a slice sampling MCMC algorithm [Poon and Domingos, 2006]. Simpler sampling strategies such as Gibbs sampling are inadequate due to the presence of deterministic dependencies. Poon and Domingos showed that the Markov chain generated by MC-SAT satisfies ergodicity and detailed balance. In practice, however, it is often too timeconsuming to obtain uniform samples as required by MCSAT and, thus, we loosen the uniformity requirement in favor of higher efficiency.

Algorithm 1 lists the pseudo-code of MC-ILP which is based on the previous MAP ILP except that we also add, for each query axiom not in C U , a constraint of type (2) associated with a new variable zj and weight 0. In each iteration, after fixing certain variables to 1 (line 6), we build an ILP where the coefficients of the objective function are set to 1 with probability 0.5 and remain 0 otherwise (line 9). The solution is then as close as possible to the uniform sample. MC-ILP samples coherent and classified CBoxes from the joint distribution and determines the probability of a conjunction of axioms as the fraction of samples in which they occur together.

5 Experiments

To complement the presented theory we also assessed the practicality of the reasoning algorithms. After all, the development of the theory was motivated primarily by the need for algorithms that, given a set of axioms with confidence values, compute a most probable coherent ontology. Two examples of this problem are ontology learning and ontology matching. Due to space considerations, we only discuss and evaluate the results on an instance of the former problem.

The ontology learning community has developed and applied numerous machine learning and data mining algorithms to generate confidence values for DL axioms. Most of these confidence values have no clearly defined semantics. Confidence values based on lexical similarity measures, for instance, are in widespread use while more sophisticated algorithms that generate actual probabilities make often na¨ıve assumptions about the dependencies of the underlying probability distribution. Hence, formalisms are needed that incorporate these various types of confidence values in order to compute most probable ontologies while utilizing the logical concepts of coherency and consistency.

We decided to generate confidence values using a "crowdsourcing" service. Probably the best known crowdsourcing platform is the Amazon Mechanical Turk (AMT) 5 . With AMT, Amazon offers numerous options for designing customized questionnaires. Due to its relatively high publicity (about 100,000 tasks were available at the time of this writing), it attracts a lot of users and consequently seems most suitable for our scenario.

For the evaluation of the different methods, we used the EKAW ontology as the gold standard. It consists of 75 classes, 33 object properties, 148 subsumption, and 2,299 disjointness axioms when materialized, and models the domain of scientific conferences. We generated HITs (human intelligence tasks) by creating questionnaires each with 10 yes/no questions. Half of these were used to generate confidence values for subsumption (disjointness) axioms. For the pair of class labels Conference Paper and Poster Session, for instance, the two types of yes/no questions were:

• (a) Is every Conference Paper also a Poster Session?
• (b) Can there be anything that is both a Conference Paper and a Poster Session?

For each pair of classes and for each type of question we obtained 9 responses from different AMT workers. The confidence value for a subsumption (disjointness) axiom was computed by dividing the number of "yes" ("no") answers by 9. We applied a threshold of 0.5, that is, only when the majority of the 9 workers answered with "yes" ("no") did we assign a confidence value to the axiom. Moreover, we halved the weights of the disjointness axioms for reasons of symmetry. This resulted in 2,507 axioms (84 subsumption and 2,423 disjointness) with confidence values. Based on these axioms we constructed two different sets. One consisting of the weighted axioms only and the other with 79 additional axioms implied by the gold standard ontology which are of the form r ⊑ s (7 axioms), C ⊑ ∃r.D (40 axioms), and ∃r.C ⊑ D (32 axioms).

5 http://www.mturk.com

We compared the EL++-LL reasoner ELOG with a greedy approach that is often employed in ontology learning scenarios. The greedy algorithm sorts the axioms in descending order according to their confidence values and adds one axiom at a time to an initially empty ontology. However, it adds an axiom only if it does not render the resulting ontology incoherent. To compute precision and recall scores we materialized all subsumption and disjointness axioms of the resulting ontology. We used the reasoner Pellet for the materialization of axioms and the coherence checks. All experiments were conducted on a desktop PC with Intel Core2 Processor P8600 with 2.4GHz and 2GB RAM. The reasoner ELOG, all ontologies, supplemental information, and the experimental results are available at http://code.google.com/p/elog-reasoner/.

ELOG's MAP inference algorithm needs on average 3.7 seconds and the greedy algorithm 33.6 seconds for generating the two coherent ontologies. Note that the 3.7 seconds include the time to classify the ontology. ELOG's cutting plane inference method needed 6 and 7 iterations, respectively. These results indicate that the MAP inference algorithm under the EL++-LL semantics is more efficient than the greedy approach for small to medium sized ontologies. Figures 1 and 2 depict the recall, precision, and F1 scores for both algorithms. The F1 score for the ontologies computed using EL++-LL MAP inference is, respectively, 5% and 12% higher than for the one created using the greedy algorithm. Furthermore, while the addition of known axioms leads to an F1 score increase of about 5% under the EL++-LL semantics it decreases for the greedy algorithm.

The MC-ILP algorithm needs between 0.4 and 0.6 seconds to compute one MCMC sample for either EL++-LL CBox. We find this to be an encouraging result providing further evidence that MCMC inference can be applied efficiently to compute conditional probabilities for conjunctions of axioms over real-world EL++-LL ontologies.

6 Conclusion and FutureWork

With this paper we introduced log-linear description logics as a family of probabilistic logics integrating several concepts from the areas of knowledge representation and reasoning and statistical relational AI. The combination of description logics and log-linear models allows one to compute probabilistic queries efficiently with algorithms originally developed for typical linear optimization problems. We focused on the description logic EL++ without nominals and concrete domains but we believe that the theory is extendable to other DLs for which materialization calculi exist.

Future work will be concerned with the inclusion of nominals and concrete domains, negated axioms in the deterministic CBox, and the design of algorithms for creating more compact representations of classified CBoxes.

Acknowledgments

Many thanks to Johanna V¨olker, Anne Schlicht, and the anonymous IJCAI reviewers for their valuable feedback.