9512.net

甜梦文库

甜梦文库

当前位置：首页 >> >> # A fuzzy description logic for the semantic web

A Fuzzy Description Logic for the Semantic Web

Umberto Straccia ISTI-CNR Via G. Moruzzi 1, I-56124 Pisa, ITALY straccia@isti.cnr.it

Abstract In this paper we present a fuzzy version of SHOIN (D), the corresponding Description Logic of the ontology description language OWL DL. We show that the representation and reasoning capabilities of fuzzy SHOIN (D) go clearly beyond classical SHOIN (D). Interesting features are: (i) concept constructors are based on t-norm, t-conorm, negation and implication; (ii) concrete domains are fuzzy sets; (iii) fuzzy modi?ers are allowed; and (iv ) entailment and subsumption relationships may hold to some degree in the unit interval [0, 1].

Keywords: description logics, ontoloies, fuzzy logics

1

Introduction

In the last decade a substantial amount of work has been carried out in the context of Description Logics (DLs) [1]. DLs are a logical reconstruction of the so-called frame-based knowledge representation languages, with the aim of providing a simple well-established Tarski-style declarative semantics to capture the meaning of the most popular features of structured representation of knowledge. Nowadays, DLs have gained even more popularity due to their application in the context of the Semantic Web [3, 16]. Semantic Web has recently attracted much attention both from academia and industry, and is widely regarded as the next step in the evolution of the World Wide Web. It aims at enhancing content on the World Wide Web with meta-data, enabling agents (machines or human users) to process, share and interpret Web content. Ontologies [9] play a key role in the Semantic Web and major e?ort has been put by the Semantic Web community into this issue. Informally, an ontology consists of a hierarchical description of important concepts in a particular domain, along with the description of the properties (of the instances) of each concept. DLs play a particular role in this context as they are essentially the theoretical counterpart of the Web Ontology Language OWL DL, the state of the art language to specify ontologies. Web content is then annotated by relying on the concepts de?ned in a speci?c domain ontology. 1

However, OWL DL becomes less suitable in all those domains in which the concepts to be represented have not a precise de?nition. If we take into account that we have to deal with Web content, then it is easily veri?ed that this scenario is, unfortunately, likely the rule rather than an exception. For instance, just consider the case we would like to build an ontology about ?owers. Then we may encounter the problem of representing concepts like 1 “Candia is a creamy white rose with dark pink edges to the petals”, “Jacaranda is a hot pink rose”, “Calla is a very large, long white ?ower on thick stalks”. As it becomes apparent such concepts hardly can be encoded into OWL DL, as they involve so-called fuzzy or vague concepts, like “creamy”, “dark”, “hot”, “large” and “thick”, for which a clear and precise de?nition is not possible (another issue relates to the representation of terms like “very”, which are called fuzzy concepts modi?ers, as we will see later on). The problem to deal with imprecise concepts has been addressed several decades ago by Zadeh [34], which gave birth in the meanwhile to the so-called fuzzy set and fuzzy logic theory and a huge number of real life applications exists. Unfortunately, despite the popularity of fuzzy set theory, relative little work has been carried out in extending DLs towards the representation of imprecise concepts, notwithstanding DLs can be considered as a quite natural candidate for such an extension [4, 12, 13, 25, 27, 29, 30, 32, 33] (see also [7], Chapter 6). In this paper we consider a fuzzy extension of SHOIN (D), the corresponding DL of the ontology description language OWL DL, and present its syntax and semantics. The main feature of fuzzy SHOIN (D) is that it allows us to represent and reason about vague concepts. None of the approaches to fuzzy DLs deal with the expressive power of the fuzzy extension of SHOIN (D) we present here. Our purpose is also to integrate most of these contributions within an unique setting and, thus, hope to de?ne a reference language for fuzzy SHOIN (D). Interesting features are: (i) concept constructors are based on t-norm, t-conorm, negation and implication; (ii) concrete domains are fuzzy sets; (iii) fuzzy modi?ers are allowed; and (iv ) entailment and subsumption relationships may hold to some degree in the unit interval [0, 1]. We will proceed as follows. In the following section we recall the description logic SHOIN (D). In Section 3 we extend SHOIN (D) to the fuzzy case and discuss some properties of it. Section 4 presents related work, while Section 5 concludes and presents some topics for further research.

2

Preliminaries

The ontology language OWL DL is strictly related to the DL SHOIN (D) [16]. Although several XML and RDF syntaxes for OWL-DL exist, in this paper we use the traditional description logic notation. For explicating the relationship between OWL DL and DLs syntax, see e.g. [15, 16]. The purpose of this section is to make the paper self-contained. More importantly it helps in understanding

1 Taken

from a text book on ?owers.

2

the di?erences between classical SHOIN (D) and fuzzy SHOIN (D). The reader con?dent with the SHOIN (D) terminology may skip directly to Section 3.

2.1

Syntax

SHOIN (D) allows to reason with concrete data types, such as strings and integers using so-called concrete domains [2, 21, 22, 23]. Concrete domains. A concrete domain D is a pair ?D , ΦD , where ?D is an interpretation domain and ΦD is the set of concrete domain predicates d with a prede?ned arity n and an interpretation dD ? ?n D . For instance, over the integers ≥20 may be an unary predicate denoting the set of integers greater or equal to 20. For instance, Person ?age. ≥20 will denote a person whose age is greater or equal to 20. Alphabeths. Let C, Ra , Rc , Ia and Ic be non-empty ?nite and pair-wise disjoint sets of concepts names, abstract roles names, concrete roles names, abstract individual names and concrete individual names. RBox. An abstract role is an abstract role name or the inverse S ? of an abstract role name S (concrete role names do not have inverses). An RBox R consists of a ?nite set of transitivity axioms trans(R), and role inclusion axioms of the form R S and T U , where R and S are abstract roles, and T and U are concrete roles. The re?exive-transitive closure of the role inclusion relationship is denoted with ? . A role not having transitive sub-roles is called simple role. Concepts. The set of SHOIN (D) concepts is de?ned by the following syntactic rules, where A is an atomic concept, R is an abstract role, S is an abstract simple role, Ti are concrete roles, d is a concrete domain predicate, ai and ci are abstract and concrete individuals, respectively, and n ∈ N: C ?→ | ⊥ | A | C1 C2 | C1 C2 | ?C | ?R.C | ?R.C | (≥ n S ) | (≤ n S ) | {a1 , . . . , an } | (≥ n T ) | (≤ n T ) | ?T1 , . . . , Tn .D | ?T1 , . . . , Tn .D d | {c1 , ..., cn }

D

?→

For instance, we may write the concept Flower (?hasPetalWidth.(≥20mm ≤40mm )) ?hasColour.Red)

to informally denote the set of ?owers having petal’s dimension within 20mm and 40mm, whose colour is red. Here ≥20mm (and ≤40mm ) is a concrete domain predicate. We use (= 1 S ) as an abbreviation for (≥ 1 S ) (≤ 1 S ).

3

TBox. A TBox T consists of a ?nite set of concept inclusion axioms C D, where C and D are concepts. For ease, we use C = D ∈ T in place of C D, D C ∈ T . An abstract simple role S is called functional if the interpretation of role S is always functional (see later for the semantics). A functional role S can always be obtained from an abstract role by means of the axiom (≤ 1 S ). Therefore, whenever we say that a role is functional, we assume that (≤ 1 S ) is in the TBox. ABox. An ABox A consists of a ?nite set of concept and role assertion axioms and individual (in)equality axioms a:C, (a, b):R, (a, c):T , a ≈ b and a ≈ b, respectively. Knowledge base. A SHOIN (D) knowledge base K = T , R, A consists of a TBox T , an RBox R, and an ABox A.

2.2

Semantics

Interpretation. An interpretation I with respect to a concrete domain D is a pair I = (?I , ·I ) consisting of a non empty set ?I (called the domain), disjoint from ?D , and of an interpretation function ·I that assigns to each C ∈ C a subset of ?I , to each R ∈ Ra a subset of ?I × ?I , to each a ∈ Ia an element in ?I , to each c ∈ Ic an element in ?D , to each T ∈ Rc a subset of ?I × ?D and to each n-ary concrete predicate d the interpretation dD ? ?n D. The mapping ·I is extended to concepts and roles as usual:

I

⊥ I C2 ) I C2 ) I (?C ) I (S ? ) I (?R.C ) I (?R.C ) I (≥ n S ) I (≤ n S ) I {a1 , . . . , an } (C1 (C1

I

= = = = = = = = = = =

?I ? C1 I ∩ C2 I C1 I ∪ C2 I ?I \ C I { y, x : x, y ∈ S I } {x ∈ ?I : RI (x) ? C I } {x ∈ ?I : RI (x) ∩ C I = ?} {x ∈ ?I : |S I (x)| ≥ n} {x ∈ ?I : |S I (x)| ≤ n} {a1 I , . . . , an I }

and similarly for the other constructs, where RI (x) = {y : x, y ∈ RI } and |X | denotes the cardinality of the set X . In particular, (?T1 , . . . , Tn .d) = {x ∈ ?I : [T1 I (x) × . . . × Tn I (x)] ∩ dD = ?} .

I

4

Satis?ability. The satis?ability of an axiom E in an interpretation I = (?I , ·I ), denoted I |= E , is de?ned as follows: I |= C D i? C I ? DI , I I I I I |= R S i? R ? S , I |= T U i? T ? U , I |= trans(R) i? RI is I I transitive, I |= a:C i? a ∈ C , I |= (a, b):R i? aI , bI ∈ RI , I |= (a, c):T i? aI , cI ∈ T I , I |= a ≈ b i? aI = bI , I |= a ≈ b i? aI = bI . For a set of axioms E , we say that I satis?es E i? I satis?es each element in E . If I |= E (resp. I |= E ) we say that I is a model of E (resp. E ). I satis?es (is a model of) a knowledge base K = T , R, A , denoted I |= K, i? I is a model of each component T , R and A, respectively. Logical consequence. An axiom E is a logical consequence of a knowledge base K, denoted K |= E , i? every model of K satis?es E . According to [15], the entailment and subsumption problem can be reduced to knowledge base satis?ability problem (e.g. T , R, A |= a:C i? T , R, A∪{a:?C } unsatis?able), for which decision procedures and reasoning tools exists (e.g. RACER [10] and FACT [14]). Example 1 Let us consider the following excerpt of a simple ontology (TBox T ) about cars, with empty RBox (R = ?): Car (= 1 maker) (= 1 passenger) (= 1 speed) ?maker.Maker ?passenger.N ?speed.Km/h

(= 1 maker) Car (= 1 passenger) Car (= 1 speed) Car

Roadster Cabriolet ?passenger.{2} Cabriolet Car ?topType.SoftTop SportsCar = Car ?speed.≥245km/h In T , the value for speed ranges over the concrete domain of kilometres per hour, Km/h, while the value for passengers ranges over the concrete domain of natural numbers, N. The concrete predicate ≥245km/h is true if the value is greater or equal than to 245km/h. The ABox A contains the following assertions: mgb:Roadster (?maker.{mg}) (?speed.≤170km/h ) enzo:Car (?maker.{ferrari}) (?speed.>350km/h ) tt:Car (?maker.{audi}) (?speed.=243km/h ) Consider the knowledge base K = T , R, A . It is then easily veri?ed that, e.g. K |= Roadster Car K |= enzo:SportsCar K |= mg:Maker K |= tt:?SportsCar . 2

5

The above example illustrates an evident di?culty in de?ning the class of sport cars. Indeed, it is highly questionable why a car whose speed is 243km/h is not a sport car any more. The point is that essentially, the higher the speed the more likely a car is a sports car, which makes the concept of sports car rather a fuzzy concept, i.e. vague concept, rather than a crisp one. In the next section we will see how to represent such concepts more appropriately.

3

Fuzzy OWL DL

Fuzzy sets have been introduced by Zadeh [34] as a way to deal with vague concepts like low pressure, high speed and the like. Formally, a fuzzy set A with respect to a universe X is characterized by a membership function ?A : X → [0, 1], assigning an A-membership degree, ?A (x), to each element x in X . ?A (x) gives us an estimation of the belonging of x to A. Typically, if ?A (x) = 1 then x de?nitely belongs to A, while ?A (x) = 0.8 means that x is “likely” to be an element of A. When we switch to fuzzy logics, the notion of degree of membership ?A (x) of an element x ∈ X w.r.t. the fuzzy set A over X is regarded as the degree of truth in [0, 1] of the statement “x is A”. Accordingly, in our fuzzy DL, (i) a concept C , rather than being interpreted as a classical set, will be interpreted as a fuzzy set and, thus, concepts become imprecise; and, consequently, (ii) the statement “a is C ”, i.e. a:C , will have a truth-value in [0, 1] given by the degree of membership of being the individual a a member of the fuzzy set C . In the following, we present ?rst some preliminaries on fuzzy set theory (for a more complete and comprehensive presentation see e.g. [6, 11, 17, 8]) and then de?ne fuzzy SHOIN (D).

3.1

Preliminaries on fuzzy set theory

Let X be a crisp set and let A be a fuzzy subset of X , with membership function ?A (x), or simply A(x) ∈ [0, 1], x ∈ X . The support of A, supp(A), is the crisp set supp(A) = {x ∈ X : A(x) = 0}. The scalar cardinality of A, |A|, is de?ned as |A| = x∈X A(x). The fuzzy powerset of X , F (X ), is the set of all the fuzzy sets over X . Let A, B ∈ F (X ). We say that A and B are equivalent i? A(x) = B (x), ?x ∈ X . A is a crisp subset of B i? A(x) ≤ B (x), ?x ∈ X . Note that either A is a subset of B or it is not. We will see later on a di?erent notion of subset, in which A is a subset of B to some degree in [0, 1]. We next give the basic de?nitions on fuzzy set operations (complement, intersection and union). The complement of A, ?A, is given by membership function (?A)(x) = n(A(x)), for any x ∈ X . The function n: [0, 1] → [0, 1], called negation, has to satisfy the following conditions and extends boolean negation: ? n(0) = 1 and n(1) = 0; ? ?a, b ∈ [0, 1], a ≤ b implies n(b) ≤ n(a); ? ?a ∈ [0, 1], n(n(a)) = a. 6

Several negation functions have been given in the literature, e.g. Lukasiewicz negation nL (a) = 1 ? a (syntax, ?L ) and G¨ odel negation nG (0) = 1 and n(a) = 0 if a > 0 (syntax, ?G ). The intersection of two fuzzy sets A and B is given (A∧B )(x) = t(A(x), B (x)), where t is a triangular norm, or simply t-norm. A t-norm is, called conjunction, is a function t: [0, 1] × [0, 1] → [0, 1] that has to satisfy the following conditions: ? ?a ∈ [0, 1], t(a, 1) = a; ? ?a, b, c ∈ [0, 1], b ≤ c implies t(a, b) ≤ t(a, c); ? ?a, b ∈ [0, 1], t(a, b) = t(b, a); ? ?a, b, c ∈ [0, 1], t(a, t(b, c)) = t(t(a, b), c). Examples of t-norms are: tL (a, b) = max(a + b ? 1, 0) (Lukasiewicz t-norm, syntax ∧L ), tG (a, b) = min(a, b) (G¨ odel t-norm, syntax ∧G ), and tP (a, b) = a · b (product t-norm, syntax ∧P ). Note that ?a ∈ [0, 1], t(a, 0) = 0. The union of two fuzzy sets A and B is given (A ∨ B )(x) = s(A(x), B (x)), where s is a triangular co-norm, or simply s-norm. A s-norm, called disjunction, is a function s: [0, 1] × [0, 1] → [0, 1] that has to satisfy the following conditions: ? ?a ∈ [0, 1], s(a, 0) = a; ? ?a, b, c ∈ [0, 1], b ≤ c implies s(a, b) ≤ s(a, c); ? ?a, b ∈ [0, 1], s(a, b) = s(b, a); ? ?a, b, c ∈ [0, 1], s(a, s(b, c)) = s(s(a, b), c). Examples of s-norms are: sL (a, b) = min(a + b, 1) (Lukasiewicz s-norm, syntax ∨L ), sG (a, b) = max(a, b) (G¨ odel s-norm, syntax ∨G ), and sP (a, b) = a + b ? a · b (product s-norm, syntax ∨P ). Note that if we consider Lukasiewicz negation, then Lukasiewicz, G¨ odel and product s-norm are related to their respective tnorm according to the De Morgan law: ?a, b ∈ [0, 1], s(a, b) = n(t(n(a), n(b))). Another important operator is implication, denoted →, that gives a truthvalue to the formula A → B , when the truth of A and B are known. A fuzzy implication is a function i: [0, 1] × [0, 1] → [0, 1] that has to satisfy the following conditions: ? ?a, b, c ∈ [0, 1], a ≤ b implies i(a, c) ≥ i(b, c); ? ?a, b, c ∈ [0, 1], b ≤ c implies i(a, b) ≤ i(a, c); ? ?a ∈ [0, 1], i(0, b) = 1; ? ?a ∈ [0, 1], i(a, 1) = 1; ? i(1, 0) = 0.

7

In classical logic, a → b is a shorthand for ?a ∨ b. A generalization to fuzzy logic is, thus, ?a, b ∈ [0, 1], i(a, b) = s(n(a), b). For instance, ?a, b ∈ [0, 1], iKD (a, b, ) = max(1 ? a, b) is the so-called Kleene-Dienes implication (syntax, →KD ). Another approach to fuzzy implication is based on the so-called residuum. His formulation starts from the fact that in classical logic ?a ∨ b can be re-written as max{c ∈ {0, 1}: a ∧ c ≤ b}. Therefore, another generalization of implication to fuzzy logic is ?a, b ∈ [0, 1], i(a, b) = sup{c ∈ [0, 1]: t(a, c) ≤ b} . For residuum based implication, i(a, b) = 1 if a ≤ b. If a > b then, according to the chosen t-norm, we have that e.g. iL (a, b) = 1 ? a + b for Lukasiewicz implication (syntax, →L ), iG (a, b) = b for G¨ odel implication (syntax, →G )) and iP (a, b) = a/b for product implication (syntax, →P ). Note that, for Lukasiewcz implication, s-norm and negation, we have iL (a, b) = sL (nL (a), b). The same holds using Kleene-Dienes implication, Lukasiewicz negation and G¨ odel s-norm. On the other hand iP (a, b) = sP (nG (a), b) (for instance, for 0 < a ≤ b < 1, iP (a, b) = 1, while sP (nG (a), b) = b < 1). Another interesting question is when ?a, b ∈ [0, 1], i(a, b) = n(t(a, n(b)) holds, which in formulae is formulated as a → b ≡ ?(a ∧ ?b). It turns out that e.g., in Zadeh’s logic [34] (i.e. using →KD , ∧G , ?L ) this relation holds. It holds as well in the so-called Lukasiewcz logic (i.e. using →L , ∧L , ?L ), while it does neither hold for G¨ odel logic (i.e. using →G , ∧G , ?G ) nor for the product logic (i.e. using →P , ∧P , ?G ). For them, just consider the case 1 > a > b > 0 to verify the inequality. We will see later on that whenever i(a, b) = n(t(a, n(b)) then under the fuzzy semantics, ?R.C is not equivalent to ??R.?C . Fuzzy implication can also be used to determine the degree of subset relationship between two fuzzy subsets A and B over X . Indeed, we de?ne the degree of subsumption between A and B , denoted A → B , as inf x∈X i(A(x), B (x)), where i is an implication function. Note that if ?x ∈ [0, 1], A(x) ≤ B (x) holds then A → B evaluates to 1. Of course, it may be that A → B evaluates to a value 0 < v < 1 as well. We conclude the discussion on fuzzy implication by noting that we have the following inferences: assume a ≥ n and i(a, b) ≥ m. Then ? under Kleene-Dienes implication we infer that if n > 1 ? m then b ≥ m. Indeed, from i(a, b) = max(1 ? a, b) ≥ m, either 1 ? a ≥ m or b ≥ m. But a ≥ n, so 1 ? a ≥ m implies 1 ? m ≥ a ≥ n > 1 ? m, a contradiction. Therefore, b ≥ m must hold. This has been used in [29]. ? under residuum based implication w.r.t. a t-norm t, we infer that b ≥ t(n, m). Indeed, from i(a, b) = sup{c: t(a, c) ≤ b} ≥ m and a ≥ n we have t(n, m) ≤ t(n, c) ≤ t(a, c) ≤ b. A (binary) fuzzy relation R over two crisp sets X and Y is a function R: X × Y → [0, 1]. The inverse of R is the function R?1 : Y × X → [0, 1] with membership function R?1 (y, x) = R(x, y ), for every x ∈ X and y ∈ Y . The composition

8

of two fuzzy relations R1 : X × Y → [0, 1] and R2 : Y × Z → [0, 1] is de?ned as (R1 ? R2 )(x, z ) = supy∈Y t(R1 (x, y ), R2 (y, z )), where t is a t-norm. A fuzzy relation R is said to be transitive i? (R ? R)(x, z ) ≤ R(x, z ). We conclude this part with fuzzy modi?ers. Fuzzy modi?ers applies to fuzzy sets to change their membership function. Well known examples are modi?ers like very, more or less, slightly, etc. These allow us to de?ne fuzzy sets like very(High) and slightly(Mature). Formally, a modi?er, fm , is a function fm : [0, 1] → [0, √ 1]. For instance, we may de?ne very(x) = x2 , while de?ne slightly(x) = x. In the following, we use ∧, ∨, ? and → in in?x notation, in place of a t-norm t, s-norm s, negation n and implication operator i.

3.2

Fuzzy SHOIN (D)

In this section we give syntax and semantics of fuzzy SHOIN (D), using the fuzzy operators de?ned in the previous section. We generalize the semantics given in [13, 29, 32]. 3.2.1 Syntax

We have seen that SHOIN (D) allows to reason with concrete data types, such as strings and integers using so-called concrete domains. In our fuzzy approach, concrete domains may be based on fuzzy sets as well. Concrete fuzzy domain. A concrete fuzzy domain is a pair ?D , ΦD , where ?D is an interpretation domain and ΦD is the set of concrete fuzzy domain predicates d with a prede?ned arity n and an interpretation dD : ?n D → [0, 1], which is a n-ary fuzzy relation over ?D . For instance, as for SHOIN (D), the predicate ≤18 may be an unary crisp predicate over the natural numbers denoting the set of integers smaller or equal to 18, i.e. ≤18 : Natural → [0, 1] and ≤18 (x) = So, Minor = Person ?age. ≤18 (1) de?nes a person, whose age is less or equal 18, i.e. it de?nes a minor. On the other hand, concerning non crisp fuzzy domain predicates, we recall that in fuzzy set theory and practice there are many membership functions for fuzzy sets membership speci?cation. However, the triangular, the trapezoidal, the L-function and the R-function are simple, yet most frequently used to specify membership degrees. The functions are de?ned over the set of non-negative reals R+ ∪ {0}. The trapezoidal function, trz (x, a, b, c, d), is de?ned as follows: let 1 if x ≤ 18 0 otherwise .

9

(a)

(b)

(c)

(d)

Figure 1: (a) Trapezoidal function; (b) Triangular function; (c) L-function; (d) R-function

a < b ≤ c < d be rational numbers ? ? ? ? ? ? trz (x; a, b, c, d) = ? ? ? ? ?

then (see Figure 1) 0 if x ≤ a (x ? a)/(b ? a) if x ∈ [a, b] 1 if x ∈ [b, c] (d ? x)/(d ? c) if x ∈ [c, d] 0 if x ≥ d .

A triangular function, tri(x; a, b, c), is such that (see Figure 1) ? 0 if x ≤ a ? ? ? (x ? a)/(b ? a) if x ∈ [a, b] tri(x; a, b, c) = (c ? x)/(c ? b) if x ∈ [b, c] ? ? ? 0 if x ≥ c . Note that tri(x; a, b, c) = trz (x; a, b, b, c). The L-function is de?ned as (see Figure 1) ? if x ≤ a ? 1 (b ? x)/(b ? a) if x ∈ [a, b] L(x; a, b) = ? 0 if x ≥ b .

10

Finally, the R-function is de?ned as (see Figure ? ? 0 (x ? a)/(b ? a) R(x; a, b) = ? 1

1) if x ≤ a if x ∈ [a, b] if x ≥ b .

Using these functions, we may then de?ne, for instance, Young: Natural → [0, 1] to be a fuzzy concrete predicate over the natural numbers denoting the degree of youngness of a person’s age. The concrete fuzzy predicate Young may be de?ned as Young(x) = L(x; 10, 30) . So, YoungPerson = Person will denote a young person. Modi?ers. We allow modi?ers in fuzzy SHOIN (D). Fuzzy modi?ers, like very, more or less and slightly, apply to fuzzy sets to change their membership function. Formally, a modi?er is a function fm : [0, 1] → [0 √, 1]. For instance, we may de?ne very(x) = x2 , while de?ne slightly(x) = x. Modi?ers has been considered, for instance, in [13, 32]. From a syntax point of view, if M is a new alphabet for modi?er symbols, m ∈ M is a modi?er and C is a SHOIN (D) concept, then m(C ) is fuzzy SHOIN (D) concept as well. For instance, by referring to Example 1, we may de?ne the concept of sports car as the concept SportsCar = Car ?speed.very(High) , (3) ?age.Young (2)

where very is a concept modi?er, with membership function very(x) = x2 , and High is a fuzzy concrete predicate over the domain of speed expressed in kilometres per hour and may be de?ned as High(x) = R(x; 80, 250) . Similarly, we may represent “Calla is a very large, long white ?ower on thick stalks” as Calla = Flower (?hasSize.very(Large)) (?hasPetalWidth.Long) (?hasColour.White) (?hasStalks.Thick) , where Large, Long and Thick are fuzzy concrete predicates. In summary, the syntax of fuzzy SHOIN (D) concepts is as follows: C ?→ | ⊥ | A | C1 C2 | C1 C2 | ?C | m(C ) ?R.C | ?R.C | (≥ n S ) | (≤ n S ) | {a1 , . . . , an } | (≥ n T ) | (≤ n T ) | ?T1 , . . . , Tn .D | ?T1 , . . . , Tn .D d | {c1 , ..., cn }

D

?→

Concerning axioms and assertions, similarly to [29], we introduce fuzzy axioms. Let be n ∈ (0, 1]. 11

Fuzzy RBox. A fuzzy RBox R is a ?nite set of SHOIN (D) transitivity axioms trans(R) and fuzzy role inclusion axioms of the form α ≥ n , α ≤ n , α > n and α > n , where α is a SHOIN (D) role inclusion axiom. Fuzzy TBox. A fuzzy TBox T consists of a ?nite set of fuzzy concept inclusion axioms of the form α ≥ n , α ≤ n , α > n and α < n where α is a SHOIN (D) concept inclusion axiom; Fuzzy ABox. A fuzzy ABox A consists of a ?nite set of fuzzy concept and fuzzy role assertion axioms of the form α ≥ n , α ≤ n , α > n , or α < n , where α is a SHOIN (D) concept or role assertion. As for the crisp case, A may also contain a ?nite set of individual (in)equality axioms a ≈ b and a ≈ b, respectively. For instance, a:C ≥ 0.1 , (a, b):R ≤ 0.3 , R S ≥ 0.4 , or C D ≤ 0.6 are fuzzy axioms. Informally, from a semantics point of view, a fuzzy axiom α ≤ n constrains the membership degree of α to be less or equal to n (similarly for ≥, >, <). As a consequence, jim:YoungPerson ≥ 0.2 , i.e. jim:Person ?age.Young ≥ 0.2 , dictates that jim is a YoungPerson with degree at least 0.2. On the other hand, a fuzzy concept inclusion axiom of the form C D≥n

dictates that the subsumption degree between C and D is at least n. Fuzzy knowledge base. A SHOIN (D) fuzzy knowledge base K = T , R, A consists of a fuzzy TBox T , a fuzzy RBox R, and a fuzzy ABox A. 3.2.2 Semantics

The semantics extends [29]. The main idea is that concepts and roles are interpreted as fuzzy subsets of an interpretation’s domain. Therefore, SHOIN (D) axioms, rather being satis?ed (true) or unsatis?ed (false) in an interpretation, become a degree of truth in [0, 1]. Fuzzy interpretation. A fuzzy interpretation I with respect to a concrete domain D is a pair I = (?I , ·I ) consisting of a non empty set ?I (called the domain), disjoint from ?D , and of a fuzzy interpretation function ·I that assigns ? to each abstract concept C ∈ C a function C I : ?I → [0, 1]; ? to each abstract role R ∈ Ra a function RI : ?I × ?I → [0, 1];

12

? to each abstract functional role R ∈ Ra a partial function RI : ?I × ?I → [0, 1] such that for all x ∈ ?I there is an unique y ∈ ?I on which RI (x, y ) is de?ned; ? to each abstract individual a ∈ Ia an element in ?I ; ? to each concrete individual c ∈ Ic an element in ?D ; ? to each concrete role T ∈ Rc a function RI : ?I × ?D → [0, 1]; ? to each concrete functional role T ∈ Rc a partial function tI : ?I × ?D → [0, 1] such that for all x ∈ ?I there is an unique v ∈ ?D on which T I (x, v ) is de?ned; ? to each modi?er m ∈ M the modi?er function fm : [0, 1] → [0, 1]; ? to each n-ary concrete fuzzy predicate d the fuzzy relation dD : ?n D → [0, 1]. The mapping ·I is extended to concepts and roles as speci?ed in the following table (where x, y ∈ ?I , v ∈ ?D ): (x) ⊥I (x) I (C1 C2 ) (x) I (C1 C2 ) (x) I (?C ) (x) I (m(C )) (x) I (?R.C ) (x) I (?R.C ) (x) I (≥ n S ) (x) (≤ n S ) (x) I {a1 , . . . , an } (x) d(v ) I {c1 , . . . , cn } (v ) I (?T1 , . . . , Tn .D) (x) I (?T1 , . . . , Tn .D) (x) I (S ? ) (x, y )

I I

= = = = = = = = = = = = = = = =

1 0 C1 I (x) ∧ C2 I (x) C1 I (x) ∨ C2 I (x) ?C I (x)) fm (C I (x)) inf y∈?I RI (x, y ) → C I (y ) supy∈?I RI (x, y ) ∧ C I (y ) n I sup {y1 , . . . , yn } ? ?I i=1 S (x, yi ) ?(≥ n + 1 S ) (x) n I i=1 ai = x D d (v ) n I i=1 ci = v n inf y1 ,...,yn ∈?D I ( i=1 Ti I (x, yi )) → DI (y1 , . . . , yn ) n supy1 ,...,yn ∈?D I ( i=1 Ti I (x, yi )) ∧ DI (y1 , . . . , yn ) S I (y, x) .

|{y1 , . . . , yn }| = n I

We comment brie?y some points. The semantics of ?R.C (?R.C ) (d) =

I

supy∈?I RI (x, y ) ∧ C I (y )

is the result of viewing ?R.C as the open ?rst order formula ?y.FR (x, y ) ∧ FC (y ) (where F is the obvious translation of roles and concepts into First-Order Logic FOL) and the existential quanti?er ? is viewed as a disjunction over the elements of the domain. Similarly, (?R.C ) (x) =

I

inf y∈?I RI (x, y ) → C I (y ) 13

is related to the open ?rst order formula ?y.FR (x, y ) → FC (y ), where the universal quanti?er ? is viewed as a conjunction over the elements of the domain. However, as we already pointed out in Section 3.1, unlike the classical case, in I I general we do not have that (?R.C ) = (??R.?C ) . For instance, it holds in Lukasiewicz logic, but not in G¨ odel logic. Also interesting is that (see [12]) the axiom ?(?R.A) (??R.?A) has no classical model. However, in [12] it is shown that in G¨ odel logic it has no ?nite model, but has an in?nite model. Another point concerns the semantics of number restrictions. The semantics of the concept (≥ n S ) (≥ n S ) (x)

I

= sup

{ y 1 , . . . , yn } ? ? I |{y1 , . . . , yn }| = n

n i=1

S I (x, yi )

is the result of viewing (≥ n S ) as the open ?rst order formula

n

?y1 , . . . , yn .

i=1

S (x, yi ) ∧

1≤i<j ≤n

yi = y j .

That is, there are at least n distinct elements that satisfy to some degree S (x, yi ). This guarantees us that ?S. ≡ (≥ 1 S ). The semantics of (≤ n S ) is de?ned in such a way to guarantee the classical relationship (≤ n S ) ≡ ?(≥ n + 1 S ). An alternative de?nition for the (≥ n S ) and the (≤ n S ) constructs may rely on the scalar cardinality of a fuzzy set. However, we prefer to stick on the formulation, which derives directly from its FOL translation. Finally, the mapping ·I is extended to non-fuzzy axioms as speci?ed in the following table (where a, b ∈ Ia ): S) I U) I D) I (a:C ) I ((a, b):R) (R (T (C

I

= = = = =

inf x,y∈?I RI (x, y ) → S I (x, y ) inf x,y∈?I T I (x, y ) → U I (x, y ) inf x∈?I C I (x) → DI (x) C I (aI ) RI (aI , bI ) .

Note here that e.g. the semantics of a concept inclusion axiom C D is derived directly from its FOL translation, which is of the form ?x.FC (x) → FD (x). This de?nition is novel and is clearly di?erent from the approaches in which C D is viewed as ?x.C (x) ≤ D(x). This latter approach has the e?ect that the subsumption relationship is a classical {0, 1} relationship, while the former has the advantage that subsumption is determined up to a certain degree in [0, 1]. Satis?ability. The notion of satis?ability of a fuzzy axiom E by a fuzzy interpretation I , denoted I |= E , is de?ned as follows: I |= trans(R), i? ?x, y ∈ ?I .RI (x, y ) = supz∈?I RI (x, z ) ∧ RI (z, y ). I |= α ≥ n , where α is a role inclusion or concept inclusion axiom, i? αI ≥ n. Similarly, for the other relations ≤, < and >. I |= α ≥ n , where α is a concept or a role assertion 14

axiom, i? αI ≥ n. Similarly, for the other relations ≤, <, >. Finally, I |= a ≈ b i? aI = bI and I |= a ≈ b i? aI = bI . For a set of fuzzy axioms E , we say that I satis?es E i? I satis?es each element in E . If I |= E (resp. I |= E ) we say that I is a model of E (resp. E ). I satis?es (is a model of) a fuzzy knowledge base K = T , R, A , denoted I |= K, i? I is a model of each component T , R and A, respectively. Logical consequence. A fuzzy axiom E is a logical consequence of a knowledge base K, denoted K |= E i? every model of K satis?es E . The interesting point is that according to our semantics, e.g. a minor is a young person to a certain degree and is obtained without explicitly mentioning it. This inference can not be achieved in classical SHOIN (D). Similarly, by referring to Example 1, we will have that the car tt will be a sports car to a certain degree. Therefore, unlike Example 1, tt is now likely a sport car, as it should be. The following two examples highlight these points. Example 2 Let us consider Example 1, where all axioms of the TBox and ABox are asserted with degree 1, i.e. are of the form α ≥ 1 . We replace the de?nition of SportsCar with De?nition (3). Then we have that (interpreting conjunction as min) K |= SportsCar Car ≥ 1 K |= enzo:SportsCar ≥ 1 K |= mgb:SportsCar ≤ 0.25 K |= tt:SportsCar ≥ 0.82 .

Note how the maximal speed limit of the mgb car (≤170km/h ) induces an upper limit, 0.25, of the membership degree. Neither this inference is possible in classical SHOIN (D), nor the one involving tt. Example 3 Consider the knowledge base K with De?nitions (1) and (2). Then under Lukasiewicz logic we have that (see [31]) K |= Minor YoungPerson ≥ 0.2 ,

which is a relationship not captured with classical SHOIN (D). Best truth value bound. Finally, given K and an axiom α, where α is neither a transitivity axiom, nor an individual (in) equality axiom, it is of interest to compute α’s best lower and upper degree value bounds. The greatest lower bound of α w.r.t. K (denoted glb(K, α)) is glb(K, α) = sup{n: K |= α ≥ n } , while the least upper bound of α with respect to K (denoted lub(K, α) is lub(K, α) = inf {n: K |= α ≤ n } ,

15

where sup ? = 0 and inf ? = 1. Determining the lub and the glb is called the Best Degree Bound (BDB) problem. For instance, the entailments in Examples 2 and 3 are the best possible degree bounds. Furthermore, note that, lub(Σ, a:C ) = ?glb(Σ, a:?C ) , (4)

i.e. the lub can be determined through the glb (and vice-versa). Similarly, lub(Σ, (a, b):R) = ?glb(Σ, a:??R.{b}) holds. Also, note that, Σ |= α ≥ n i? glb(Σ, α) ≥ n, and similarly Σ |= α ≤ n i? lub(Σ, α) ≤ n hold. Concerning the entailment problem, it is quite easily veri?ed that, as for the crisp case, the entailment problem can be reduced to the unsatis?ability problem: T , R, A |= α ≥ n T , R, A |= α ≤ n i? i? T , R, A ∪ { α < n } is not satis?able T , R, A ∪ { α > n } is not satis?able .

3.3

Reasoning

Unfortunately, from a computational point of view, no calculus exists yet checking satis?ability of fuzzy SHOIN (D) knowledge bases. [13, 32] report a calculus for the case of ALC [26] (with concept constructors , ⊥, ?, , , ?, ?) with modi?ers and simple TBox, with min, max and →KD connectives. No indication for the BDB problem is given. [27, 29] reports a calculus for ALC and simple TBox, with min, max and →KD connectives and addresses the BDB problem and, [30] shows how the satis?ability problem and the BDB problem can be reduced to classical ALC and, thus, can be resolved by means of a tools like FACT and RACER. However, despite these negative results, recently [31] reports a calculus for ALC (D) whenever the connectives, the modi?ers and the concrete fuzzy predicates are representable as a bounded Mixed Integer Program. For instance, Lukasiewicz logic satis?es these conditions as well as the membership functions for concrete fuzzy predicates we have presented in this paper. Additionally, modi?ers should be a combination of linear functions. In that case the calculus consists of a set of constraint propagation rules and an invocation to an oracle for bounded Mixed Integer Programming. But, indeed, the computational aspect is de?nitely a point that has to be addressed in forthcoming works.

4

Related work

Several ways of extending DL using the theory of fuzzy logic have been proposed in the literature. The ?rst work is due to Yen [33] who considered a sub-language of ALC , FL? [5]. However, it already informally talks about the use of modi?ers and concrete domains. Though, the unique reasoning facility, the subsumption test, is a crisp yes/no question. Tresp [32] considered fuzzy ALC extended with a special form of modi?ers, which are a combination of two linear functions. min, max and 1 ? x membership functions has been considered

16

and a sound and complete reasoning algorithm testing the subsumption relationship has been presented. Similar to our approach, a linear programming oracle is needed. Assertional reasoning has been considered by Straccia [27, 28, 29], where fuzzy assertion axioms have been allowed in fuzzy ALC (with min, max and 1 ? x functions), concept modi?ers are not allowed however ([28] reports a four-valued variant of fuzzy ALC ). He also introduced the BDB problem and provided a sound and complete reasoning algorithm based on completion rules ([30] provides a translation of fuzzy ALC into classical ALC ). For an application see [24]. In the same spirit [13] extend Straccia’s fuzzy ALC with concept modi?ers of the form fm (x) = xβ , where β > 0. A sound and complete reasoning algorithm for the graded subsumption problem, based on completion rules, is presented. Finally, [25] start addressing the issue of alternative semantics of quanti?ers in fuzzy ALC (without the assertional component). No reasoning algorithm is given. Concerning [31], we already addressed it in the previous section. Finally, [12] considers ALC under arbitrary t-norm and reports, among others, a procedure deciding |= C D ≥ 1 and deciding whether C D ≥ 1 is satis?able, by a reduction to the propositional BL logic.

5

Conclusions and outlook

We have presented a fuzzy extension of SHOIN (D) showing that its representation and reasoning capabilities go clearly beyond classical SHOIN (D). Interestingly, we allow modi?ers, fuzzy concrete domain predicates and fuzzy axioms to appear in a SHOIN (D) knowledge base and the entailment and the subsumption relationship hold to a certain degree. To the best of our knowledge, no other work has yet extended the semantics to SHOIN (D) in such a way. The argument supporting the necessity of such an extension relies on the fact that vague concepts are abundant in human knowledge and, thus, appear likely in Web content. The main direction for future work involves the computational aspect. Currently, we are addressing the fundamental issue to develop a calculus for reasoning within SHOIN (D), extending [31]. Another direction is in extending fuzzy SHOIN (D) with fuzzy quanti?ers (see [19, 20] for an overview on fuzzy quanti?ers), where the ? and ? quanti?ers are replaced with fuzzy quanti?ers like most, some, usually and the like (see [25] for a preliminary work in this direction). This allows to de?ne concepts like TopCustomer = Customer (Usually)buys.ExpensiveItem ExpensiveItem = Item ?price.High . Here, the fuzzy quanti?er Usually replaces the classical quanti?er ? and High is a fuzzy concrete predicate. Fuzzy quanti?ers can be applied to inclusion axioms as well, allowing to express, e.g. (Most)Bird FlyingObject .

17

Here the fuzzy quanti?er Most replaces the classical universal quanti?er ? assumed in the inclusion axioms. The above axiom allows to state that most birds ?y. Ultimately, we believe that the fuzzy extension of SHOIN (D) is of great interest to the Semantic Web community, as it allows to express naturally a wide range of concepts of actual domains, for which a classical SHOIN (D) representation is unsatisfactory.

References

[1] Franz Baader, Diego Calvanese, Deborah McGuinness, Daniele Nardi, and Peter F. Patel-Schneider, editors. The Description Logic Handbook: Theory, Implementation, and Applications. Cambridge University Press, 2003. [2] Franz Baader and Philipp Hanschke. A schema for integrating concrete domains into concept languages. In Proceedings of the 12th International Joint Conference on Arti?cial Intelligence (IJCAI-91), pages 452–457, Sydney, 1991. [3] T. Berners-Lee, J. Hendler, and O. Lassila. The semantic web. The Scienti?c American, 284(5):34–43, 2001. [4] P. Bonatti and A. Tettamanzi. Some complexity results on fuzzy description logics. In A. Petrosino V. Di Ges` u, F. Masulli, editor, WILF 2003 International Workshop on Fuzzy Logic and Applications, LNCS 2955, Berlin, 2004. Springer Verlag. [5] Ronald J. Brachman and Hector J. Levesque. The tractability of subsumption in frame-based description languages. In Proceedings of AAAI-84, 4th Conference of the American Association for Arti?cial Intelligence, pages 34–37, Austin, TX, 1984. [a] An extended version appears as [18]. [6] Didier Dubois and Henri Prade. Fuzzy Sets and Systems. Academic Press, New York, NJ, 1980. [7] Pan et al. Speci?cation of coordination of rule and ontology languages. Technical report, Knowledgeweb Network of Excellence, EU-IST-2004507482, 2004. Deliverable D2.5.1. [8] S. Gottwald. A Treatise on Many-Valued Logics. A Research Studies Press Book, 2000. [9] N. Guarino and R. Poli. Formal ontology in conceptual analysis and knowledge representation. International Journal of Human and Computer Studies, 43(5/6):625–640, 1995. [10] Volker Haarslev and Ralf M¨ oller. RACER system description. In Proceedings of International Joint Conference on Automated Reasoning (IJCAR01), number 2083 in LNAI, pages 701–705, Siene, Italy, 2001. Springer. 18

[11] Petr H? ajek. Metamathematics of Fuzzy Logic. Kluwer, 1998. [12] Petr H? ajek. Making fuzzy description logics more expressive. Fuzzy Sets and Systems, 2005. To appear. [13] Ste?en H¨ olldobler, Hans-Peter St¨ orr, and Tran Dinh Khang. The subsumption problem of the fuzzy description logic ALCF H . In Proceedings of the 10th International Conference on Information Processing and Managment of Uncertainty in Knowledge-Based Systems, (IPMU-04), 2004. [14] Ian Horrocks. Using an expressive description logic: Fact or ?ction? In Proc. of the 8th Int. Conf. on the Principles of Knowledge Representation and Reasoning (KR-98), 1998. [15] Ian Horrocks and Peter Patel-Schneider. Reducing OWL entailment to description logic satis?ability. Journal of Web Semantics, 2004. To Appear. [16] Ian Horrocks, Peter F. Patel-Schneider, and Frank van Harmelen. From SHIQ and RDF to OWL: The making of a web ontology language. Journal of Web Semantics, 1(1):7–26, 2003. [17] George J. Klir and Bo Yuan. Fuzzy sets and fuzzy logic: theory and applications. Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1995. [18] Hector J. Levesque and Ronald J. Brachman. Expressiveness and tractability in knowledge representation and reasoning. Computational Intelligence, 3:78–93, 1987. [19] Yaxin Liu and Etienne E. Kerre. An overview of fuzzy quanti?ers. (i). interpretations. Fuzzy Sets Syst., 95(1):1–21, 1998. [20] Yaxin Liu and Etienne E. Kerre. An overview of fuzzy quanti?ers (ii). reasoning and applications. Fuzzy Sets Syst., 95(2):135–146, 1998. [21] C. Lutz. Description logics with concrete domains—a survey. In Advances in Modal Logics Volume 4. King’s College Publications, 2003. [22] Carsten Lutz. Reasoning with concrete domains. In Proceedings of the Sixteenth International Joint Conference on Arti?cial Intelligence, pages 90–95. Morgan Kaufmann Publishers Inc., 1999. [23] Carsten Lutz. Nexp time-complete description logics with concrete domains. ACM Trans. Comput. Logic, 5(4):669–705, 2004. [24] Carlo Meghini, Fabrizio Sebastiani, and Umberto Straccia. A model of multimedia information retrieval. Journal of the ACM, 48(5):909–970, 2001. [25] D. S? anchez and G.B. Tettamanzi. Generalizing quanti?cation in fuzzy description logics. In Proceedings 8th Fuzzy Days in Dortmund, 2004.

19

[26] Manfred Schmidt-Schau? and Gert Smolka. Attributive concept descriptions with complements. Arti?cial Intelligence, 48:1–26, 1991. [27] Umberto Straccia. A fuzzy description logic. In Proc. of the 15th Nat. Conf. on Arti?cial Intelligence (AAAI-98), pages 594–599, Madison, USA, 1998. [28] Umberto Straccia. A framework for the retrieval of multimedia objects based on four-valued fuzzy description logics. In F. Crestani and Gabriella Pasi, editors, Soft Computing in Information Retrieval: Techniques and Applications, pages 332–357. Physica Verlag (Springer Verlag), Heidelberg, Germany, 2000. [29] Umberto Straccia. Reasoning within fuzzy description logics. Journal of Arti?cial Intelligence Research, 14:137–166, 2001. [30] Umberto Straccia. Transforming fuzzy description logics into classical description logics. In Proceedings of the 9th European Conference on Logics in Arti?cial Intelligence (JELIA-04), number 3229 in Lecture Notes in Computer Science, pages 385–399, Lisbon, Portugal, 2004. Springer Verlag. [31] Umberto Straccia. Fuzzy description logics with concrete domains. Technical Report 2005-TR-03, Istituto di Scienza e Tecnologie dell’Informazione, Consiglio Nazionale delle Ricerche, Pisa, Italy, 2005. [32] C. Tresp and R. Molitor. A description logic for vague knowledge. In Proc. of the 13th European Conf. on Arti?cial Intelligence (ECAI-98), Brighton (England), August 1998. [33] John Yen. Generalizing term subsumption languages to fuzzy logic. In Proceedings of the 12th International Joint Conference on Arti?cial Intelligence (IJCAI-91), pages 472–477, Sydney, Australia, 1991. [34] L. A. Zadeh. Fuzzy sets. Information and Control, 8(3):338–353, 1965.

20

- Towards a fuzzy description logic for the semantic web (preliminary report
- DAML+OIL a description logic for the semantic web
- Well-founded semantics for description logic programs in the semantic web
- Fuzzy Description Logic Programs under the Answer Set Semantics for the Semantic Web
- Logic Foundation and Services for Semantic Web
- A Framework for Ontology Mapping for the Semantic Web
- Tightly integrated probabilistic description logic programs for the semantic web
- A-Defeasible-Logic-Reasoner-for-the-Semantic-Web
- DAML-S Web service description for the semantic web
- Application of Logic Programming and Updates for the Semantic Web
- 学霸百科
- 新词新语