On the Problem of Weighted Max-DL-SAT and its Application to Image Labeling Carsten Saathoff, Stefan Scheglmann, and Steffen Staab Institute for Web Science and Technologies University of Koblenz-Landau, Germany http://west.uni-koblenz.de saathoff,schegi,staab@uni-koblenz.de Abstract. For a number of problems, such as ontology learning or image label- ing, we need to handle uncertainty and inconsistencies in an appropriate way. Fuzzy and Probabilistic Description Logics are the two major approaches for performing reasoning with uncertainty in Description Logics, but modeling prob- lems such as image labeling still remains difficult and handling inconsistencies is only supported to a limited extent. In this paper, we propose Max-DL-SAT and Weighted Max-DL-SAT as new reasoning services for Description Logics knowledge bases, which applies the idea behind Weighted Max-SAT to Descrip- tion Logics and leads to a more intuitive representation of certain problems. It supports handling of uncertainty and inconsistencies. The contribution of this paper is threefold: We define a novel reasoning service on Description Logics knowledge bases, introduce an algorithm for solving such problems, and show the application of it to the problem of image labeling. 1 Introduction Solutions to a number of real world problems are often subject to a set of potentially contradicting constraints, for which a completely satisfying solution does not exist, e.g., in Computer Aided Design or information extraction from text. In Max-SAT, these problem are modeled as a boolean a formula for which one seeks an assignment of truth values that satisfies a maximal number of clauses. In Weighted Max-SAT clauses are associated with weights that model the importance or reliability of certain clauses and the goal is to maximize the accumulated weight of the satisfied clauses in a solution. However, Max-SAT and Weighted Max-SAT are both limited to propositional logic and finding an appropriate problem representation is often hardly intuitive. Ontologies, on the other hand, allow for modeling domains in a more intuitive manner. Description Logics have widely been adopted to model ontologies and to provide reasoning ser- vices in a variety of domains. In problems like image labeling [13, 2], we encounter assertions that are associated with a degree and we have to cope with many, potentially contradicting assertions produced by automatic and not fully reliable methods. In order to apply ontological reasoning to such problems, we require new reasoning services. State of the art extensions to Description Logics, such as Fuzzy [15] or Probabilistic Description Logics [8] cover most of these aspects, but other problems still need to be solved. Reasoning on Probabilistic Description Logics still has difficulties regarding the efficiency of the reasoning process. Fuzzy Description Logics can be reasoned about efficiently under min/max co-norm. In this paper, we introduce a novel reasoning service for handling uncertainty and inconsistencies in Description Logic knowledge bases, called Weighted Max-DL-SAT. We consider Description Logic knowledge bases containing a set of weighted and po- tentially contradicting axioms. Based on this, we compute a set of consistent axioms with a maximal, accumulated weight. Weighted Max-DL-SAT allows for the almost di- rect reuse of existing ontologies and provides a very intuitive way of modeling problems that have a Max-SAT like structure, e.g., the aforementioned image labeling problem. In summary, the paper provides a threefold contribution: 1. We define a novel type of reasoning problem, called Weighted Max-DL-SAT. 2. We introduce an algorithm for solving Weighted Max-DL-SAT problems based on the Hitting Set Tree algorithm [12, 6]. 3. We apply Weighted Max-DL-SAT to the problem of image labeling. The rest of the paper is structured as follows: In the next section we give a for- mal introduction to the Description Logic ALC and extend its definition to weighted ontologies. Then, we introduce the problem of Weighted Max-DL-SAT. Based on this formalizations, we introduce our approach to solve Weighted Max-DL-SAT problems. Afterwards, we introduce an example where we applied Weighted Max-DL-SAT to the domain of spatial reasoning in the context of image labeling, and finally discuss the related work and conclude the paper. 2 Knowledge Representation Using Description Logics Description Logics constitutes a class of knowledge representation languages that allow for expressing complex concepts in terms of a set of basic constructors. In this section, we specifically introduce the Description Logic ALC, the Attributive Concept Lan- guage with Complements. Let NC and NR be two disjoint sets of symbols, called the set of concept and role names, respectively. We will write A, B for concept names, and R for role names. > and ⊥ are special concepts, called Top and Bottom, respectively. A concept description C in ALC is syntactically defined by the following abstract syntax rule: C → >|⊥|A|∀R.C|∃R.C|C u D|C t D|¬C}. (1) The semantics of a concept description is given by an interpretation I = (∆I , ·I ), where ∆I = {ai , . . . , an } is called the domain of I and ·I is called the interpretation function. The interpretation function maps each concept name A to a set AI ⊆ ∆I , and each role name to a binary relation RI ⊆ ∆I × ∆I . The semantics of the constructors are defined as follows. – >I = ∆ I – ⊥I = ∅ – (C u D)I = C I ∩ DI – (C t D)I = C I ∪ DI – (¬C)I = ∆I \ C I – (∀R.C)I = {x ∈ ∆I |∀y ∈ ∆I : (x, y) ∈ RI → y ∈ C I } – (∃R.C)I = {x ∈ ∆I |∃y ∈ ∆I : (x, y) ∈ RI ∧ y ∈ C I } Furthermore, we define a T-Box T as a set of terminological axioms of the form C v D, whereby C and D are concepts. We say that D subsumes C, and an interpre- tation I satisfies an axiom C v D iff C I ⊆ DI . We define a disjointness between two axioms C and D as C||D = C v ¬D. The A-Box A is defined as a set of con- cept assertions a : C, where a is an individual name and C a concept description, and role assertions (a, b) : R with a, b individual names and R a role name. Both concept and role assertions area also called assertional axioms. A Description Logics ontology O = T ∪ A consists of a T -Box T and an A-Box A. We extend this definition of an ontology to a weighted ontology: Definition 1 (Weighted ontology). A weighted ontology is an ontology O := {α1 , . . . , αn } such that for every T -Box or A-Box axiom α ∈ O an associated weight wα ∈ R+ exists. In case of concrete axioms, we specify the weight in square brackets, i.e., C v D[w] for T -Box axioms, a : C[w] for concept assertions, and (a, b) : R[w] for role assertions. We can now define the reasoning problem Weighted Max-DL-SAT. Our basis is a weighted Description Logic ontology O = T ∪ A. Each axiom in O is associated with a weight, which represents the importance or reliability of this axiom to be satisfied. The problem is to find a consistent subset of the ontology with a maximal summed weight. Formally, we define the Weighted Max-DL-SAT problem as an optimization problem as follows: X argmaxS⊆O s.t. S consistent ( wα ) (2) α∈S The result is Or = Tr ∪ Ar , a maximal consistent sub-ontology, such that Or ⊆ O, Or is consistent, and the accumulated weight of all axioms αi ∈ Or is maximal. In Or we call Ar the consistent Sub-A-Box and Tr the consistent Sub-T -Box. 3 Solving Weighted Max-DL-SAT Problems In order to obtain a consistent sub-ontology, we need to resolve all inconsistencies in O. To do so, we have to calculate the weight-minimal set of axioms O− , such that Or = O \ O− is consistent. This problem has strong relations to axiom-pinpointing [14], which identifies and eliminates inconsistencies in ontologies. Axiom-pinpointing algo- rithms compute a minimal set of axioms causing a single inconsistency in an ontology O. Such a set, we call a minimal inconsistent sub-ontology [3] M and it is defined as follows: Definition 2 (Minimal Inconsistent Sub-Ontology). A Minimal Inconsistent Sub- Ontology (M ) of an ontology O, is defined as a subset M ⊆ O, such that M is in- consistent and ∀α ∈ M : M \ {α} is consistent. Every M causes a single inconsistency in a particular O. If we remove one axiom of such a M from O, we eliminate this cause of inconsistency in O. We can formulate this problem as a Weighted Hitting Set Problem. We first give the definition of this set of problems and then explain how Weighted Max-DL-SAT maps to a Weighted Hitting Set Problem: Definition 3 (Weighted Hitting Set Problem [12]). Given a set G and a set of subsets M1 , M2 , ..., Mn ⊆ G Each element in G has a positive weight wa , a ∈ G We are looking for a hitting set H ⊆ G such that – H ∩ Mi 6= ∅, i = 1, ..., n P – a∈H wa is minimal Now let O be our ground set, M1 , M2 , ..., Mn the set of all minimal inconsistent sub- ontologies, and the hitting set H the set O− of axioms to be removed from O. Obviously Or is weight maximal, when O− is weight minimal. To calculate O− for inconsistent ontologies, we propose an adaptation of the Hitting Set Tree (HST) algorithm. The HST algorithm produces a tree T starting with our O as root node N1 . It calculates a minimal inconsistent Sub-Ontology (MISO) Mj for every node Nj ∈ T . For every axiom αi in Mj of Nj the algorithm introduces a new sub- node Nji ∈ T . The edge to Nji is labeled with αi and wαi and the current ontology for a node Nji is Oj \ {αi }. To solve our Weighted Max-DL-SAT problem, we have to calculate the cheapest path w.r.t the accumulated weights from the root to a leaf in T . The accumulated axioms of this path represent O− . Algorithm 1 Weighted Hitting Set Tree algorithm for computing a solution to Weighted Max-DL-SAT problems. 1: O− ← ∅ . initialize result with empty set 2: wO− ← ∞ . set upper bound to infinity 3: function WHST(O, P P ) 4: wP ← α∈P wP . accumulate path weight 5: if wP < wO− then . check upper bound 6: M ← calcSingleMISO(O) . calculate M for current ontology 7: if M 6= ∅ then 8: M0 ← M 9: . ∀α ∈ M in decreasing order call WHST 10: . for O \ {α}, P ∪ {α} 11: while M 0 6= ∅ do 12: Select α ∈ M 0 s.t. ∀α0 ∈ M 0 → wα0 > wα 13: M 0 ← M 0 \ {α} 14: WHST(O \ {α}, P ∪ {α}) 15: end while 16: else . if current path weight < upper bound 17: O− ← P . set result to path 18: wO − ← wP . set upper bound to path weight 19: end if 20: end if 21: end function In [6] Kalyanpur et. al have shown the completeness of the Hitting Set Tree algo- rithm regarding the calculation of all justifications for an ontology. Algorithm 1 depicts the concrete W HST algorithm used in our implementation. To increase efficiency, we use a branch & bound like strategy to prune subtrees where no further improvements of the results could be achieved. We use the accumulated weight of an already calculated root-to-leaf path as upper bound, line 19. Initially this bound is set to infinity, line 2. With this lower bound, we can prune any branch of the subtree that could not contain a smaller total path weight. Only if the weight of the current path is lower than this upper bound, a branch has to be considered, line 5. Algorithm 2 depicts the minimal inconsistent sub-ontology (MISO) calculation [3]. It iteratively adds the axioms α with the smallest weight wα to the intermediate on- tology O until it becomes inconsistent, lines 3 − 6. Then, we shrink O by iteratively removing the axioms α with the biggest weight wα if this does not turn O consistent again, lines 8 − 14. Thus, we are guaranteed to end up with an M , a small, still incon- sistent set of axioms in O. Algorithm 2 Black-box algorithm for computing a minimal inconsistent sub-ontology for O. 1: function CALC S INGLE MISO(O) 2: O←∅ . initialize intermediate ontology 3: while O is consistent do . grow intermediate ontology until inconsistency 4: Select axiom α ∈ O \ O s.t. ∀α0 ∈ O \ O → wα0 ≥ wα 5: O ← O ∪ {α} 6: end while 7: O0 ← O 8: while O0 6= ∅ do . shrink intermediate ontology to minimal inconsistent set 9: Select axiom α ∈ O0 s.t. ∀α0 ∈ O0 → wα0 ≤ wα 10: O0 ← O0 \ {α} 11: if O \ {α} is inconsistent then 12: O ← O \ {α} 13: end if 14: end while 15: return O 16: end function 4 Applying Weighted Max-DL-SAT to Automatic Image Labeling As an example, we present the application of Weighted Max-DL-SAT to the interesting problem of automatically assigning labels to image regions. Typically, these labels refer to ”semantic” concepts and provide the means to index regions within an image based on terms understandable for humans. Determining the right labels for a given region is a hard problem, since there is no direct mapping of computable low-level features to the meaning of a region. Automatic methods model regions within images using a set of features and then usually apply machine learning methods in order to learn and subsequently detect a set of possible semantic concepts. These methods exploit only low-level features extracted from regions of the image, but do not take any context, e.g., spatial context, into account. However, context and background knowledge play a crucial role in automatic image labeling [13, 2]. In our experiments, we utilize spatial relations between image regions as background knowl- edge to validate the semantic concepts given for specific region. Figure 1 shows an example of an image (a) and the associated regions with simpli- fied, but still ambiguous hypotheses (b) produced by a classifier. The output of the machine-learning-based classification is used as input to our reasoning process. As background knowledge, we consider knowledge about feasible spatial relations between the semantic concepts, such as above, below, left, right. For example, a valid relation might be that sea is never depicted above sky. (a) input image (b) output from ML-based classification Fig. 1. Input to the reasoning process 4.1 Data Set The data set consists of 922 images depicting outdoor scenes and was split into 400 training and 522 test images. These images have been segmented using an automatic segmentation algorithm and manually assigned a label from the set of concepts: Sky, Sea, Sand, Road, Building, Foliage, Person, Boat, Mountain, Snow. This dataset has been published1 and used in previous experiments [13, 10] for the task of spatial reason- ing. In addition, the data set also contains different low-level features for each region, different hypotheses generated based on the training data using different classification methods, and a set of extracted fuzzy spatial relations. For our experiment, we used the labels produced by the maximum-likelihood classifier as input to our reasoner. 4.2 Representing Image Labeling with Weighted Max-DL-SAT The background knowledge is depicted as a T -Box. For each label, we create an atomic concept L. Furthermore, we make all label concepts disjoint and add an axiom L1 || . . . ||Ln [wn ]. The background knowledge about spatial relations has been modeled as a set of binary constraints defining for each label L to which other labels L01 , . . . , L0n it might be related by the spatial relation S. To present such knowledge about spatial relations 1 http://mklab.iti.gr/project/scef in a Description Logic T -Box, we use universal quantification, like L v ∀S.(L01 t . . . t L0n )[wn ]. Thus, for the two labels Sky and Sea used in figure 1, we would add two axioms sky v ∀above.(sea t sky t sand t . . .)[wm ] and sea v ∀above.(sea t sand t . . .)[wm ]. These axioms assure, that sea might only be depicted above other sea regions, while sky might be depicted above sky or sea regions. They are all associated with an very high weight, since we consider the background knowledge as crisp, and therefore do not accept any solutions where any of these axioms is removed. Obviously, this requires that the T -Box is consistent, which is the case in our experiments. Furthermore, the axioms are learned following the approach presented in [13]. Each image i is modeled in a separate A-Box. To generate the A-Box, we use the hypothesis generated by the machine-learning classification process. For each region, we create a single individual ri . Now, let wi,l be the degree of confidence in the dataset for region ri labeled with label l. Then we add the concept assertion ri : L[wi,l ] to the knowledge base for each label produced by the classifier for the region. For the two regions region1 and region2 depicted in figure 1 this will result in: region1 : sky[wregion1,sky ], region1 : sea[wregion1,sea ], region2 : sky[wregion2,sky ] and region2 : sea[wregion2,sea ]. Additionally to the hypothesis about associated seman- tic concepts the classification process also generates knowledge about spatial relations between the single regions. To present the spatial knowledge in our ontology, we add for all known relations role assertions like (ri , rj ) : S[wm ] to the knowledge base. We set the weight of such assertions to very high value, because we do not the accept a solution where one of the spatial relations was removed in order to find a solution. For the regions region1 and region2 from figure 1, this will lead to the two role as- sertion (region1, region2) : above[wm ] and (region2, region1) : below[wm ]. To- gether with the T -Box depicting the background knowledge, this A-Box results in an individual ontology Oi for each image i. As we can see this ontology contains contra- dicting statements with: sea v ∀above.(sea)[wm ], (region1, region2) : above[wm ], region1 : sea[wregion1,sea ] and region2 : sky[wregion2,sky ]. Such an inconsistent ontology Oi is the input to our reasoning process. 4.3 Results In Table 4.3, we have summarized the accuracy of the classifier, Weighted Max-DL- SAT, and the binary integer programming approach presented in [13]. Using Weighted Max-DL-SAT, we can significantly improve the classification rate as provided by the classifier based solely on low-level features. However, we also see that a more spe- cialized method performs clearly better. The latter observation was expected. The BIP approach can employ a more specialized objective function that incorporate the degree of confidence provided with the fuzzy spatial relations, and it employ all fuzzy spatial relations available, not only the one with the highest degree. This information is not used in our modeling of the problem. Nevertheless, the experiments show that a generic approach based on Description Logics can be applied to a problem like spatial reasoning and leads to a clear improve- ment. Furthermore, the difference between the specialized method and Weighted Max- DL-SAT is not very large. Specifically, the parameters used for the knowledge extrac- tion have not been optimized in our experiments for Weighted Max-DL-SAT, while Classifier Max-DL-SAT BIPs building 0.92 0.90 0.96 foliage 0.70 0.85 0.90 mountain 0.74 0.92 0.91 person 0.58 0.77 0.84 road 0.75 0.56 0.92 sailing-boat 0.49 0.47 0.93 sand 0.67 0.69 0.63 sea 0.71 0.78 0.75 sky 0.17 0.52 0.51 snow 0.71 0.81 0.85 overall 0.62 0.75 0.79 Table 1. Per concept and overall accuracy of the classifier, Weighted Max-DL-SAT, and the Binary Integer Programming approach [13]. in [13] experiments with optimized parameters were reported. The gained generality of the approach comes at the cost of a loss in accuracy. The figures in 2 show the system performance results from our experiment. In each figure, we compare two different values (left and right y-axies) per image (x-axis). We sorted the images in increasing order by the first value (left). In figure 2 (a), we show the relation between the over all calculation time per image and the number of nodes per image. In our Experiments, we limited the calculation time per image to 300sec. We can observe only a weak relationship between calculation time and the number of visited nodes, a tendency towards the more nodes are visited the longer the calculation takes. We can observe multiple outliers especially images with a relative small number of visited sodes compared to the calculation time. Due to the heuristic character of Branch & Bound and because of the calculation of an NP-complete problem like the Weighted Hitting Set Tree, we have to expect such outliers. Figure 2 (b) shows the number of A-Box axioms per image in increasing oder and over all calculation time. Again we can observe multiple outlier but the relation seems to be stronger. Images with more axioms in the A-Box more often tend to exceed the calculation time cap. In figure 2 (c), we show the relation between the over all system performance per image and the time consumption for MISO calculation per image. The MISO calculation time seems to represent a relatively large proportion of the over all system performance. This could be a interesting point for further optimizations. The system could benefit from more detailed studies to increase the efficiency of the MISO calculation. The last figure, 2 d shows the relation between the time consumption for MISO calculation per image and the number of MISOs per image. Here we can also observe an clear relationship. This observation also indicates that where is a potential for further optimizations of the MISO calculation. All these behavior result give clear hints about further optimizations of the systems performance. A promising starting point for further optimizations seems to be the MISO calculation. The MISO calculation takes an important part of the over all calculation time and the calculation time for all MISO increases similar to the number of MISOs. 5 Related Work The issues of integrating uncertainty into Description Logics and reasoning with such uncertainty in Description Logics have already been addressed in different ways by 350 90000 1000 350 Time per Image [sec] Axioms in Abox Nodes calculated 80000 875 Time per Image [sec] 300 300 70000 750 250 250 60000 Time [Sec] Time [Sec] 625 Axioms Nodes 200 50000 200 500 150 40000 150 375 30000 100 100 250 20000 50 50 10000 125 0 0 0 0 0 100 200 300 400 500 0 100 200 300 400 500 Images Images (a) Calculation time in increasing oder and (b) Axioms per ABox in increasing oder and visited Nodes per Image calculation time 350 350 350 4500 Time per Image [sec] Time for all Misos per Image [sec] Time for all Misos per Image [sec] MISOs calculated 4000 300 300 300 Time for MISOs[Sec] 3500 250 250 250 3000 Time [Sec] Time [sec] MISOs 200 200 200 2500 150 150 150 2000 1500 100 100 100 1000 50 50 50 500 0 0 0 0 0 100 200 300 400 500 0 100 200 300 400 500 Images Images (c) Calculation time in increasing oder and (d) Calculation time for all MISOs in MISO Time increasing oder and MISOs per Image Fig. 2. System performance several researchers. [5, 8, 7] present probabilistic extensions to OWL or investigations on reasoning services for such extension. Some of these approaches allow only for ter- minological knowledge like [5] others for terminological as well as assertional knowl- edge [8]. The approaches also differ in the underlying probabilistic reasoning formal- ism. Two reasoning formalisms could be found in these publications, a formalism based on reasoning in probabilistic logics [5, 8] and a formalism based on inferencing in Bayesian networks [7]. But unfortunately all of these approaches suffer from serve problems regarding the efficiency of reasoning on such knowledge bases. Another ap- proach to uncertainty extension to Description Logics is the use of fuzzy set theory to express the uncertainty. In [16, 15] Straccia presents a general approach to a fuzzy ver- sion of SHOIN (D), the underlying Description Logic of OW L − DL. He shows the representation and reasoning capabilities of fuzzy SHOIN (D). As mentioned in the introduction, reasoning on fuzzy Description Logics can be performed quite efficiently. However, the fuzzy semantics are often mislead by single axioms with a high or low weight, repsectively. In general, both approaches are able to handle degrees associated with axioms, but they are not suitable for handling inconsistencies in every respect. Reasoning under inconsistency plays a role in the field of ontology learning [4] and ontology debugging [3]. One important method, about finding explanations for a given consequence, e.g., a minimal subset of an ontology that has a particular incon- sistency in that ontology as consequence, is axiom pinpointing. Generally, we can dis- tinguish axiom pinpointing methods into two different categories glass-box approaches and black-box approaches. In [1] Baader et al. introduce a glassbox approach for axiom pinpointing. In this paper, we focus on a black-box approach inspired by the work of Kalyanpur et. al. [6]. Interpreting images and extraction of deep-level semantics, can not be done suffi- ciently only on low-level features. Images often show scenes illustrating abstract con- cepts like events. To perceive such an event concept, additional background knowledge about the whole scene is required. In [11] Möller et .al introduced abduction as a new inferencing service on Description Logic A-Boxes that enables able to reason from effects (observations/features) to causes (explanations/semantics). In contrast to the ap- proach of Möller where new knowledge is extracted through abduction, our approach focuses on verification of knowledge against a specific model. The approach presented in [2] aims to enhance the semantic image description with the use of fuzzy Description Logics. Based on fuzzy Description Logic knowledge bases specialized reasoning ser- vices are used to, e.g. solve inconsistencies resulting from the classification process or extract implicit semantics but all these approaches suffer from the particularities coming with the use of fuzzy Description Logics. 6 Conclusions We have introduced Weighted Max-DL-SAT as a service for modeling and solving problems with inconsistencies and uncertainty using Description Logics. A core fea- ture of our approach is the ability to handle uncertainty similar to fuzzy or probabilistic Description Logics whereas inconsistency is handled like in a crisp Description Logics manner. This combination of features is useful to many different problems, like ontol- ogy learning, semantic information extraction or image labeling. The evaluation on im- age labeling indicates that we achieve a slightly improvement of the results compared to a classifier based solely on low-level features. Compared to a highly specialized method Weighted Max-DL-SAT looses a bit of accuracy but this was the expected price for the gain of generality of the method. With optimized parameters used for the knowledge extraction and a adjusted modeling, we expect further improvements. In our future work, we will concentrate on the improvement of the performance of maximal consistent sub-ontology calculation. Our experience has shown that it could be promising to improve the MISO calcualtions in this context. The multiple outlier observed in our results showed us that it might be useful to consider approaches other than out WHST based black box method. On this account, we work on an glass box approach to be able to compare it to our black box method. Some of our results also indicate that the consistency checking in approach is a large cost factor, so the integra- tion of Description Logic approximation techniques, like in [9] could be promising. In the next implementations, we will focus on these three promising optimization strate- gies for Weighted Max-DL-SAT. In addition, we will apply Weighted Max-DL-SAT to different other interesting problems. References 1. Baader, F., Pealoza, R.: Axiom pinpointing in general tableaux. J. Log. Com- put. 20(1), 5–34 (2010), \url{http://dblp.uni-trier.de/db/journals/ logcom/logcom20.html#BaaderP10} 2. Dasiopoulou, S., Kompatsiaris, I., Strintzis, M.: Investigating fuzzy DLs-based reasoning in semantic image analysis. Multimedia Tools and Applications 49(1), 167–194 (2010) 3. Haase, P., van Harmelen, F., Huang, Z., Stuckenschmidt, H., Sure, Y.: A framework for han- dling inconsistency in changing ontologies. In: Gil, Y., Motta, E., Benjamins, V.R., Musen, M.A. (eds.) Proceedings of the 4th International Semantic Web Conference (ISWC’05). LNCS, vol. 3729, pp. 353–367. Springer, Galway, Ireland (November, 6–10 2005) 4. Haase, P., Völker, J.: Ontology learning and reasoning – dealing with uncertainty and incon- sistency. In: Proceedings of the Workshop on Uncertainty Reasoning for the Semantic Web (URSW) (November 2005) 5. Heinsohn, J.: Probabilistic description logics. In: UAI. pp. 311–318 (1994) 6. Kalyanpur, A., Parsia, B., Horridge, M., Sirin, E.: Finding all justifications of owl dl entail- ments. In: ISWC/ASWC. pp. 267–280 (2007) 7. Koller, D., Levy, A., Pfeffer, A.: P-classic: A tractable probabilistic description logic. In: Proceedings of AAAI-97. pp. 390–397 (1997) 8. Lukasiewicz, T.: Expressive probabilistic description logics. Artificial Intelligence 172(6- 7), 852 – 883 (2008), http://www.sciencedirect.com/science/article/ B6TYF-4R1MF4C-1/2/36132fd965af5a169b53a197616f4721 9. Pan, J.Z., Thomas, E.: Approximating owl-dl ontologies. In: AAAI. pp. 1434–1439. AAAI Press (2007), http://dblp.uni-trier.de/db/conf/aaai/aaai2007.html# PanT07 10. Papadopoulos, G.T., Saathoff, C., Grzegorzek, M., Mezaris, V., Kompatsiaris, Y., Staab, S., Strintzis, M.G.: Comparative evaluation of spatial context techniques for semantic image analysis. In: Proceedings of 10th International Workshop on Image Analysis for Multimedia Interactive Services (WIAMIS) (2009), http://kodemaniak.de/publications/ wiamis2009_submission_81.pdf 11. Peraldi, I.S.E., Kaya, A., Mller, R.: Formalizing multimedia interpretation based on abduc- tion over description logic aboxes. In: Grau, B.C., Horrocks, I., Motik, B., Sattler, U. (eds.) Description Logics. CEUR Workshop Proceedings, vol. 477. CEUR-WS.org (2009), http: //dblp.uni-trier.de/db/conf/dlog/dlog2009.html#PeraldiKM09 12. Reiter, R.: A theory of diagnosis from first principles. Artif. Intell. 32(1), 57–95 (1987), http://dblp.uni-trier.de/db/journals/ai/ai32.html#Reiter87 13. Saathoff, C., Grzegorzek, M., Staab, S.: Labelling image regions using wavelet features and spatial prototypes. In: Semantic Multimedia, Third International Conference on Seman- tic and Digital Media Technologies, SAMT 2008, Koblenz, Germany. pp. 89–104 (2008), http://www.uni-koblenz.de/˜saathoff/publications/samt08.pdf 14. Schlobach, S.: Debugging and semantic clarification by pinpointing. In: ESWC. pp. 226–240 (2005) 15. Straccia, U.: A fuzzy description logic. In: Proceedings of AAAI-98, 15th Conference of the American Association for Artificial Intelligence. Madison, US (1998), citeseer.nj. nec.com/straccia98fuzzy.html 16. Straccia, U.: Towards a fuzzy description logic for the semantic web (preliminary report). In: 2nd European Semantic Web Conference (ESWC-05). pp. 167–181. No. 3532 in Lecture Notes in Computer Science, Springer Verlag, Crete (2005), http://faure.iei.pi. cnr.it/˜straccia/download/papers/ESWC05/ESWC05.pdf