Default Logics for Plausible Reasoning with Controversial Axioms

Abstract

Using a variant of Lehmann's Default Logics and Probabilistic Description Logics we recently presented a framework that invalidates those unwanted inferences that cause concept unsatis ability without the need to remove explicitly stated axioms. The solutions of this methods were shown to outperform classical ontology repair w.r.t. the number of inferences invalidated. However, con icts may still exist in the knowledge base and can make reasoning ambiguous. Furthermore, solutions with a minimal number of inferences invalidated do not necessarily minimize the number of con icts. In this paper we provide an overview over nding solutions that have a minimal number of con icts while invalidating as few inferences as possible. Speci cally, we propose to evaluate solutions w.r.t. the quantity of information they convey by recurring to the notion of entropy and discuss a possible approach towards computing the entropy w.r.t. an ABox.

-

In the Semantic Web, knowledge is represented by ontologies expressed in the Web Ontology Language OWL. The current standard, OWL2 [ 1 ], de nes di erent pro les all of which have some Description Logics as a rough syntactic variant. These Description Logics (DL) are decidable fragments of rst-order logics where knowledge is explicitly expressed in axioms and assertions. DL knowledge bases have well-de ned model-theoretic semantics. They allow to express knowledge on di erent levels of expressivity and enable to infer new conclusions from existing knowledge.

When ontologies evolve or one ontology is mapped to another, contradictions may be introduced that cause the knowledge base as a whole to be inconsistent. Yet, for an inconsistent knowledge base any conclusion|even meaningless ones|becomes trivially true. One cause of inconsistency is given by assertions of concepts that are inferred to be unsatis able. Hence, it is desirable to prevent concepts from being inferred unsatis able. A knowledge base can become inconsistent for other reasons, but we propose to start o with con ict-free conceptualizations and apply a method that never infers any concept to be unsatis able.

In the Semantic Web, agents interacting with an ontology assume that both the query and the answer are expressible in OWL2. Furthermore, the answer should have meaningful semantics but not infer con icts. We therefore demand any formalism allowing for plausible reasoning on controversial information to ful ll the following properties: 1. Permanence: The formalism for knowledge representation is not changed. 2. Coherency: No concept is inferred to be unsatis able 3. Autonomy: The procedure shall work automatically. 4. Originality: The original information should be kept. 5. Conservation: As little inferred information as possible shall be lost. We presented a method for solving unsatis able concepts [ 2 ] using a combination of Lehmann's Default Logics [ 3 ] and Lukasiewicz' Probabilistic Description Logics [ 4 ]. Instead of removing (explicit) axioms, we propose to invalidate those inferences that cause concepts to be inferred unsatis able [ 5 ]. While it is possible to reason with all information provided, we may still produce contradicting inferences. In this paper we show that minimizing the number of inferences invalidated does not necessarily minimize the number of those con icts. For nding optimal solutions we propose to evaluate these w.r.t. their information content which requires the de nition of the entropy of a solution. We discuss a possible approach towards computing the entropy w.r.t. an ABox and give an outlook on future work. 2

Procedure

For each unsatis able concept U of an ontology, its justi cations JUk v? [ 6 ], i.e. the minimal sets of axioms explaining the con ict, are determined in a rst step. Each of these justi cations is split up into two sets : one that contains all aalxlioomthserwahxiicohmcsoonftatihnatthveeruynjsuasttiis caabtiloenc,oncUkevp?t, [ 2 ]Uk.vA?ftearnwdarodnse, tthheatrocootnutnasinast justi cations are determined, which are those justi cations that do not depend on any other justi cation [ 7 ].

According to the partition scheme of Lehmann's Default Logics, the axioms of the root justi cations are put into partitions U0; : : : ; UN and a separate TBox T such that all concepts in T [Un are satis able for n = 0; : : : N . Thanks to the splitting, we do not have to perform additional satis ability checks for computing the partition. The resulting Default TBox is a family of (classical) TBoxes: DT = (T [ U0; : : : ; T [ UN ). For such a Default TBox we may either use the inference methods provided by Probabilistic Description Logics [ 4 ] or stick to classical reasoning on the single partitions, separately. Either approach de nes a deductive closure of the Default TBox as a set of OWL2 axioms, but we prefer the latter approach to change the formalism for reasoning only as little as possible.

Instead of putting all axioms of the root unsat justi cations into the partitions, we showed in [ 5 ] that we indeed have to put only two axioms of each root unsat justi cation into the partitions|one of each Ukv? and one of each Ukv?| while we may put the remaining axioms into T . While potentially invalidating less inferences, however, nding partitions may become non-deterministic.

We propose to approximate an optimal solution by a (stochastic) search process: On the one hand, the number of possible solutions is exponential in the number of axioms in the justi cations. On the other hand, once the justi cations are known, nding a single valid solution can be performed e ciently, because the complexity of the approach is dominated by the complexity of nding justi cations|a task which has to be performed anyhow. 3

Minimizing Con icts by Minimizing the Entropy By invalidating the inferences of the kind DT j= U v ? we ignore the con icts during reasoning. Yet, inferences such as the co-occurrence of DT j= A and DT j= :A are still possible but not desired. Hence, a performance measure that assesses the quality of a solution must not only take into account the number of inferences invalidated but, even more important, the number of con icts still remaining.

Assume the simple TBox T = fB v A; C v B; C v :A; g which has two Default TBoxes as potential solutions:

DT 0 with T 0 = fC v Bg; U00 = fB v Ag; U10 = fC v :Ag DT 1 with T 1 = fC v :Ag; U01 = fB v Ag; U11 = fC v Bg In contrast to the latter, the rst Default TBox DT 0 preserves the inference C v A. Yet, in the presence of an ABox that infers the assertion C(i), the assertion A(i) as well as its complement :A(i) can be inferred. The second Default TBox DT 1, in contrast, infers only :A(i). It is preferred over DT 0, because it contains fewer con icts than DT 1.

Con icts potentially reduce the information content of a knowledge base. For minimizing the number of con icts as well as the number of inferences invalidated we are currently investigating qualitative measures based on the entropy of a possible solution. As opposed to methods based on the structure of an ontology [ 8 ], we propose that an entropy-measure should take into account the ambiguity of di erent ABoxes.

In information theory, the entropy measures the average information content of a random variable we are missing when the value of the random variable is not known [ 9 ]. If we know the probability mass function p of the random variable X, we may explicitly denote the entropy by H(X) = PnN=0 p(xn) log p(xn). In case p(xn) = 0, then p(xn) log p(xn) = 0. We propose to approximate the probability mass function pA for the axioms B v A 2 DT by counting assertions for the concept (:B tA) found by the instance retrieval service of the reasoning process: pA(B v A) = P

jfx 2 AI DvC2DT jfy 2 AI j T ; A j= (:B t A)(x)gj j T ; A j= (:D t C)(y)gj

The entropy of a Default TBox DT measures the information content of its axioms w.r.t. an ABox A: H(DT ; A) = PBvA2(DT ) pA(B v A) log pA(B v A). For the Default TBoxes in the example above, we obtain an entropy of H(DT 0) = log(1=3) and H(DT 1) = log(1=2) which would make us choose DT 1 rather than DT 0. Our current hypothesis is that a Default TBox with minimal entropy also minimizes the number of explicit con icts w.r.t. an ABox. A prototype implementation is available 4. 4

Conclusion

We recently introduced a framework that never infers any concept to be unsatisable while keeping all originally provided information. This allows plausible reasoning on ontologies that possibly contain controversial information|as it is the case for mapped or dynamic ontologies. Finding solutions is non-deterministic and requires optimization techniques that, in turn, require a performance measure for evaluating the quality of possible solutions.

While reasoning ignores con icts, they are still present in the knowledge base and may lead to sub-optimal results. It was shown that solutions invalidating a minimal number of inferences do not necessarily minimize the number of conicts still present. For minimizing these we proposed to use an entropy-based performance measure. We provided a de nition for the entropy of a solution w.r.t an ABox which is currently being further investigated. 4 http://www.wsl.ch/info/mitarbeitende/scharren/owl-defaults/

References

1. Hitzler , P. , Krotzsch, M. , Parsia , B. , Patel-Schneider , P.F. , Rudolph , S.: OWL 2 Web Ontology Language Primer . W3C Recommendation , W3C ( 2009 )

2. Scharrenbach , T. , Grutter, R., Waldvogel , B. , Bernstein , A. : Structure Preserving TBox Repair using Defaults . In: 23rd Intl. Workshop on Description Logics . ( 2010 )

3. Lehmann , D. : Another perspective on default reasoning . Ann. Math. Artif. Intell 15 ( 1995 ) 61 { 82

4. Lukasiewicz , T. : Expressive probabilistic description logics . Art. Intell . 172 ( 6-7 ) ( 2008 ) 852 { 883

5. Scharrenbach , T., d'Amato , C. , Fanizzi , N. , Grutter, R., Waldvogel , B. , Bernstein , A. : Unsupervised con ict-free ontology evolution without removing axioms . In: 4th International Workshop on Ontology Dynamics (IWOD-2010) . (to appear).

6. Schlobach , S. , Cornet , R.: Non-standard reasoning services for the debugging of description logic terminologies . In: Proc. of IJCAI 2003 . ( 2003 ) 355 { 362

7. Kalyanpur , A. , Parsia , B. , Sirin , E. , Hendler , J.: Debugging unsatis able classes in owl ontologies . Journal of Web Semantics 3 ( 4 ) ( 2005 ) 268 { 293

8. Doran , P.S. , Tamma , V. , Payne , T.R. , Palmisano , I.: An entropy inspired measure for evaluating ontology modularization . In: Proc. of KCAP2009 . ( 2009 ) 73 { 80

9. Shannon , C.E. : A mathematical theory of communication . Bell System Technical Journal 27 379 { 423 , 623 { 656