Reasoning under Uncertainty with Log-Linear Description Logics

Abstract

The position paper provides a brief summary of log-linear description logics and their applications. We compile a list of ve requirements that we believe a probabilistic description logic should have to be useful in practice. We demonstrate the ways in which log-linear description logics answer to these requirements.

Introduction

Uncertainty is pervasive in the real world and reasoning in its presence one of the most pressing challenges in the development of intelligent systems. It is therefore hard to imagine how the Semantic Web could succeed without the ability to represent and reason under uncertainty. Nevertheless, purely logical approaches to knowledge representation and reasoning such as description logics have proven useful in providing the formal backbone of the Semantic Web. There is not only a large body of important work on the logical and algorithmic properties of such languages but also highly optimized tools that are successfully employed in meaningful applications. Still, the need to model uncertainty persists. Two prominent examples where the processing of uncertainty is crucial are (a) data integration (schema and instance alignment) and (b) ontology learning. In both cases, algorithms usually generate con dence values for particular axioms. In ontology matching, for instance, string similarity measures are often used to nd con dence values for equivalence axioms between concepts and properties, respectively.

There have been attempts to combine logic and probability in various ways. Resulting approaches are probabilistic formalism for description logics [ 4, 5, 2, 6, 8 ] and, more generally, statistical relational languages [ 3 ]. The former are important theoretical contributions but have not been adopted by practitioners. We believe this is primarily due to the computational complexity of probabilistic inference, the rather involved way of expressing uncertainties syntactically, and the lack of implementations. Statistical relational approaches, on the other hand, have been successfully applied to numerous real-world problems but they do not explicitly take into account the notion of coherency and consistency which is crucial in the context of the Semantic Web. top bottom nominal conjunction existential restriction

Syntax

> ? fag C u D 9r:C

Semantics

I ; faI g

CI \ DI fx 2

I j9y 2

I : (x; y) 2 rI ^ y 2 CI g

Based on these observations (and biases), and with the more concrete applications of ontology learning and matching in mind, we have compiled the following wish list for a probabilistic description logic. 1. The system must be usable by individuals knowledgeable only in Semantic

Web languages and tools such as OWL and Protege; 2. It must be possible to express uncertainty in form of degrees of con dence (real-valued weights) and not necessarily in form of precise probabilities.

Real-world problems such as ontology matching and learning require this; 3. The user should not have to worry about inconsistent and incoherent input to the probabilistic reasoner. All types of inconsistencies are handled by the probabilistic reasoner and not the user; 4. Two types of queries should be supported under uncertainty: (a) The \most probable ontology" query and (b) the probability of (conjunctions) of axioms query; and 5. The worst-case complexity should not exceed that of probabilistic graphical models such as Markov and Bayesian networks. While inference in these models is generally NP-hard, numerous highly e cient algorithms exist and can be employed in the context of probabilistic DLs.

These ve requirements are captured by log-linear description logics [ 7 ]. We provide a brief overview of log-linear description logics and discuss how this family of probabilistic logics answers to the outlined requirements. 2

Log-Linear Description Logics

Log-linear description logics integrate description logics with probabilistic loglinear models. Detailed technical and empirical results are available [ 7 ] and are mostly omitted in this position paper. The syntax of log-linear description logics is taken from the underlying description logic. However, it is possible to assign real-valued weights to axioms. Here, we focus on the log-linear description logic based on E L++ [ 1 ] without concrete domains (see Table 1) which we denote as E L++-LL. E L++ captures the expressivity of numerous ontologies in the biomedical sciences and other domains, and it is the description logic on which the web ontology language pro le OWL 2 EL is based. More formally, a E L++-LL ontology C = (CD; CU) is a pair consisting of a deterministic E L++ CBox (set of axioms) CD and an uncertain CBox CU = f(c; wc)g which is a set of pairs (c; wc) with each c being a E L++ axiom and w a real-valued weight assigned to c. 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 con dence. Every axiom can either be part of the deterministic or the uncertain CBox but not of both.

The semantics of log-linear DLs is based on joint probability distributions over coherent E L++ CBoxes and similar to that of Markov logic [ 9 ]. The weights of the axioms determine the log-linear probability distribution. For a E L++LL CBox (CD; CU) and a E L++ CBox C0 over the same set of basic concept descriptions and role names, we have that

P (C0) = 8< Z1 exp : 0

P f(c;wc)2CU:C0j=cg wc if C0 is coherent

and C0 j= CD; otherwise where Z is the normalization constant of the log-linear probability distribution.

The semantics of the log-linear description logic leads to probability distributions one would expect under the open world semantics of description logics. Example 1. Let Student and Professor be two classes and let CD = ; and CU = fhStudent v Professor; 0:5i; hStudent u Professor v?; 0:5ig: Then1, P (fStudent v Professor; StudentuProfessor v?g) = 0, P (fStudent v Professorg) = Z 1 exp(0:5), P (fStudent v Professor; Professor v Studentg) = Z 1 exp(0:5), P (fStudent u Professor v?g) = Z 1 exp(0:5), P (fProfessor v Studentg) = Z 1 exp(0), and P (;) = Z 1 exp(0) with Z = 3 exp(0:5) + 2 exp(0).

We distinguish two types of probabilistic queries. The maximum a-posteriori (MAP) query: \Given a E L++-LL CBox, what is a most probable coherent E L++ CBox over the same concept and role names?"; and the conditional probability query: \Given a E L++-LL CBox, what is the probability of a conjunction of axioms?" We believe that the rst type of query is useful since it infers the most probable coherent ontology from one that contains axioms with con dence values. The MAP query, therefore, has immediate applications in ontology learning and matching.

Probabilistic inference in log-linear description logics seems daunting at rst, considering the combinatorial complexity of the problem. It turns out, however, that both the MAP and the conditional probability query can be computed e ciently for ontologies with thousands of known and uncertain axioms [ 7 ]. The worst-case complexity of both queries is equivalent to the worst-case complexity of the analogous queries in Markov and Bayesian networks (requirement 5). 1 We omit trivial axioms that are present in every classi ed CBox such as Student v > and Student v Student.

Log-Linear Description Logics in Practice ELOG is a log-linear description logic reasoner developed at the University of Mannheim. A detailed description, the source code, and example ontologies are available at its webpage2. ELOG directly loads ontologies expressed in OWL 2 EL. The assignment of con dence values to axioms is made with the annotation property \con dence." Consider the following example ontology zoo:owl: SubClassOf(

Annotation(<http://URI/ontology#confidence> "0.5"^^xsd:double) <http://zoo/Penguin> <http://zoo/Bird> ) DisjointClasses( <http://zoo/Bird> <http://zoo/Mammal> ) Here, the subclass axiom is assigned the con dence value 0.5 and the disjointness axiom is considered true since it is not annotated. Therefore, the subclass axiom is part of the uncertain CBox and the disjointness axiom is part of the deterministic CBox. Considering that annotations can simply be added with popular ontology editors such as Protege or using the OWL API3, log-linear description logics ful ll requirements 1 and 2. In addition, the annotated axioms do not have to be consistent or coherent in any way because ELOG computes the probabilistic queries with respect to the joint probability distribution over coherent ontologies. Thus, ELOG also ful lls requirement 3.

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

3 http://owlapi.sourceforge.net/

References

1. Baader , F. , Brandt , S. , Lutz , C. : Pushing the EL envelope . In: Proceedings of the International Joint Conference on Arti cial Intelligence ( 2005 )

2. Costa , P. : Bayesian semantics for the Semantic Web . Ph.D. thesis , George Mason University ( 2005 )

3. Getoor , L. , Taskar , B. : Introduction to Statistical Relational Learning . MIT Press ( 2007 )

4. Jaeger , M. : Probabilistic reasoning in terminological logics . In: Proceedings of the Conference on the Principles of Knowledge Representation and Reasoning ( 1994 )

5. Koller , D. , Levy , A. , Pfe er , A.: P-classic: A tractable probabilistic description logic . In: Proceedings of the 14th AAAI Conference on Arti cial Intelligence ( 1997 )

6. Lukasiewicz , T. , Straccia , U. : Managing uncertainty and vagueness in description logics for the semantic web . J. of Web Sem . 6 ( 2008 )

7. Niepert , M. , Noessner , J. , Stuckenschmidt , H.: Log-Linear Description Logics . In: Proceedings of the International Joint Conference on Arti cial Intelligence ( 2011 )

8. Predoiu , L. , Stuckenschmidt , H.: Probabilistic models for the semantic web . In: The Semantic Web for Knowledge and Data Management ( 2008 )

9. Richardson , M. , Domingos , P. : Markov logic networks . Machine Learning ( 2006 )