In real application scenarios, input data and knowledge is often vague. Likewise, it is often the case that exact reasoning over data is impossible due to complex dependencies between input data and target outputs. For practical applications, however, good approximations often suffice, and efficient calculation of an approximate answer is often preferable over complex processing which may take a long time to come up with an exact answer. Fuzzy logic supports both features by providing fuzzy membership functions and fuzzy IF-THEN rule bases. In this paper, we show how fuzzy membership functions and fuzzy rules can be modeled by means of an appropriate description logic and how this can be employed for query answering.
In the last decade a substantial amount of work has been carried out in the
context of Description Logics (DLs)[
Vague knowledge, i.e. rules based on fuzzy logic, are also important from the perspective of evaluating values of attributes that have very complex dependencies with other attribute values. Such rules play an important role in application domains, where a good approximation of the desired value of an attribute is acceptable. For example, consider the controlling of a train. It is desired, that when a train arrives at station, it halts at a certain fixed position. However, calculating how exactly the brake should be applied at what position in which speed so that the passengers can still sit comfortable etc. is difficult. However, considering that it is acceptable if the train stops a small distance before or after the mark, automatic control of the train is much easier.
Fuzzy logic, first introduced by Zadeh in [
In this paper, we will show how fuzzy IF-THEN rules can be modeled using description logics with concrete domains and aggregates. The exposition serves two purposes. On the one hand, it serves as a modeling example for description logics and the usefulness of concrete domains and aggregates. On the other hand, it provides the first steps toward the implementation of fuzzy rules systems with the description logic knowledge representation paradigm. Due to the advent of the semantic web, this can be seen as a step toward the sharing of sophisticated structured knowledge by means of ontology languages.
The paper is structured as follows. First, we give a short introduction to the description logic with concrete domains and aggregates in section 2. In section 3, we show how fuzzy membership functions can be modeled and how membership can be calculated. In section 4, we show how fuzzy rules can be modeled and how the degree of fulfillment of a fuzzy rule can be calculated. In section 5, we show how the modeled fuzzy rules can be used for answering DL queries. Finally, we conclude in section 7 after discussing some related work in section 6. 2
Description logics with concrete domains was first introduced in [
Definition 1. A concrete domain D = (dom(D), pred(D)) consists of a set dom(D) (the domain), and a set of predicate symbols pred(D). Each predicate symbol Pn ∈ pred(D) is associated with an arity n and an n-ary relation P D ⊆ dom(D) .
Definition 2. Let NC , NR and NF be disjoint sets of concept, role and feature1 names. The set of ALC(D)-concepts is the smallest set such that (1) every concept name is a concept and (2) if C and D are concepts, R is a role or a feature name, P ∈ pred(D) is an n-ary predicate name, and u1, . . . , un are feature chains2, then (C u D), (C t D), (¬C), (∀R.C), (∃R.C) and P (u1, . . . , un) are concepts.
is extended by a set of aggregation functions agg(D), where each Γ ∈ agg(D) is associated with a partial function Γ D from the set of multisets of dom(D) into dom(D). Such an extended concrete domain is denoted by Σ.
The set of concrete features is inductively defined as follows. (1) Each feature
name f ∈ NF is a concrete feature. (2) a feature chain f1 . . . fn is a concrete
features, and (3) an aggregated feature f1 . . . fnΓ (R ◦ f ) is a concrete feature,
where f, f1 . . . fn are feature names, and Γ ∈ agg(Σ) is an aggregation function.
1 Features are just functional roles.
2 A feature chain [
additionally the use of concrete features fi in predicated restrictions P (f1 . . . fn).
Note, that the description logic ALC(Σ) is not decidable. For details about
the semantics of ALC(D) and ALC(Σ), and proof of undecidability of ALC(Σ),
we refer to [
One of the biggest advantages of fuzzy logic is that fuzzy rules appeal to human intuition, as they contain linguistic variables and linguistic terms like temperature = cold rather than precise values like temperature = 5◦C. A fuzzy rule engine mimics human reasoning as it works on such linguistic variables and linguistic terms. Formally, a linguistic term is a membership function that maps each possible value of the linguistic variable to a real number between 0 and 1. Each linguistic term of a linguistic variable covers a range of possible values which the linguistic variable can take, and the real advantage of fuzzy inferencing lies in the smooth transition between linguistic terms covering adjacent value ranges. 3.1
Point v ∃x.R u ∃y.R[
Similarly, we define a concept μ that denotes the set of membership functions. We do this by means of a (non-functional) role p which assigns points to individuals, as follows:5
μ v ∃p.Point. 3 I.e. we allow only membership functions which are piecewise linear. 4 Identifying individuals with real numbers simply serves to make computations simpler, though it may appear to be counterintuitive in some cases. 5 μ v ≥ 2 p.Point would be more precise if qualified number restrictions are available.
For a concept v, being viewed as a linguistic variable and having linguistic terms t1, . . . , tn, we add n instances μtv1 , . . . , μtvn of μ with corresponding roles and points. We interpret the set of points associated with some μtvi as a piecewise linear function. For a concept v being viewed as a linguistic variable, we denote the set of its linguistic terms by v∗. 3.2
Our membership functions are just sets of points in R2. Two points with adjacent x-coordinates can be interpreted as a straight line. For a line between (x1, y1) and (x2, y2), and a given x, we calculate y as6
0, otherwise. y = ( xy11−−yx22 (x − x1) + y1, if x1 ≤ x < x2, (1) We model this by defining a concept YL, to capture the ys as described above. Now suppose that there are k membership functions for a concept v. We define k relations from the concept v to the concept YL as follows:
YL v ∃y.R[
l
i∈{1,...,k}
∃ylμv .YL
ti
An instance of a concept v will be in as many relation instances of ylμv
ti
with instances of YL as there are lines in the membership function μtvi . The
membership of an instance of the concept v to a membership function μtvi is then
just the sum of all such ys over all the lines of μtvi . To capture this information,
we define a functional role mμi from v to R[
l i∈{1,...,k}
∃mμtvi .R[
Finally, to ensure that the membership of an instance of the concept v via a membership function μtvi is equal to the sum of all ys over all the lines of μtvi , we set v v
l i∈{1,...,k}
P=(mμtvi , sum{ylμtvi ◦ y}) (2) where the predicate P=(x, y) is true iff x = y, and sum is the aggregate function which computes the sum of its inputs.
Figure 2 shows the calculation of the membership of a concrete temperature value 12 to the membership functions cold and comfortable. The membership 6 Note, the condition x < x2 (instead of x ≤ x2) ensures that a given x does not lie on more than one line.
mcomf. yl cold
yl comf. yl cold y 0.3 y 0.7 yl comf.
y 0
0.7 yl comf.
y
0 function cold consists of three points (i.e. two lines) and the membership function comfortable consists of four points (i.e. three lines) (cf. figure 1). So, the instance 12 has two relations of type ylcold and three relations of type ylcomfortable to the instances of YL.7 The values connected to an instance of YL via the role y are calculated according to equation 1. Now, the memberships of the instance 12 via membership functions mcold and mcomfortable are calculated according to the equation in axiom 2, i.e. mcold = 0+0.3 = 0.3 and mcomfortable = 0.7+0+0 = 0.7. 4
A fuzzy IF-THEN rule consists of an IF part (antecedent) and a THEN part (consequent). The antecedent is a combination of terms, whereas the consequent is exactly one term. In the antecedent, the terms can be combined by using fuzzy conjunction, disjunction and negation. A term is an expression of the form X = T , where X is a linguistic variable and T is one of its linguistic terms. 4.1
Since terms are the elementary building blocks of a fuzzy rule, we start with modeling terms. As described above, a term consists of two parts, a linguistic variable and a linguistic term. So, we model a concept Term as
Term v ∃r.> u ∃f.μ, where the roles r and m are functional roles assigning linguistic variable resp. linguistic term. 7 To save space, we abbreviate comfortable by comf. and do not show the structure related to the membership function warm.
Terms can be combined via conjunction, disjunction and negation to term expressions. Further, a term expression is fulfilled by an individual to a certain degree. So, we define concepts TermExp, TermExp∧, TermExp∨ and TermExp¬ and extend the definition of the concept Term as follows, introducing also the corresponding roles.
Note that the relation operand is a function role.
A rule has an antecedent and a consequent. The antecedent is a term expression and the consequent is a term. Further, a rule has a degree to which it is fulfilled by an individual. So, we define a concept Rule as
Rule v ∃antecedent.TermExp u ∃consequent.Term u ∃degree.R[
Since terms are the basic building blocks of a rule, the degree of fulfillment of a rule depends ultimately on the degrees of fulfillment of the terms occurring in the rule. Now, an individual connected to a term via the role r fulfills the term with the same degree as the corresponding value of the membership function the term is connected with via the role m. We model this by extending the definition of the concept Term as follows:
Term v P=(degree, r ◦ mf ).
We can calculate the degree of fulfillment of a term expression according to
the semantics suggested by Zadeh in [
(¬μA)(a) = 1 − μA(a) So, we extend the definitions of TermExp∧, TermExp∨ and TermExp¬ as follows.
TermExp∧ v P=(degree, min{conjunct ◦ degree}) TermExp∨ v P=(degree, max{disjunct ◦ degree})
TermExp¬ v P=1−(degree, operand ◦ degree) 8 Certainly, other T-norms and T-conorms could be used.
The predicate P=1−(a, b) is true iff a = 1 − b. min and max are aggregate functions for the concrete domain R.
To interpret a fuzzy IF-THEN rule, we need an interpretation for the implication. In general, one can have a different interpretation of the implication for every rule, which is particularly important when the application domain requires the use of weighted rules. Here, we use a universal interpretation π of the implication in all the rules. However, we do not fix π any further. In most of the cases, it is equal to minimum. So
where Pπ is a ternary predicate from the concrete domain R and represents the interpretation of the implication function π. That is, for given a, b, c ∈ R, Pπ(a, b, c) is true iff a = π(b, c). 5
So far, we have shown how a fuzzy rule can be interpreted. However, for
answering queries that use fuzzy rules, we need an interpretation of fuzzy rules
bases, i.e. of sets of fuzzy rules. Basically, there are two possibilities to interpret
a fuzzy rule base, namely FITA (First Inferencing Then Aggregation) and FATI
(First Aggregation Then Inferencing). In this paper, we will only model FITA
and believe that FATI can be modeled similarly. It has been shown in [
Consider a rule base containing n rules of the form F1 → G1, . . . Fn → Gn.
In FITA, first each rule is interpreted. That is, for each x, y and each rule i,
the value of π(Fi(x), Gi(y)) is calculated. Now, for a given x, the inference step
is performed for each rule. Again, the inference operator can be different for
different rules. However, we use a universal inference operator for all the rules
and call it κ — in many practical cases, κ is equal to minimum. In general,
the inference operator κ is some function that maps the square [
α(κ(F (x), π(F1(x), G1(y))), . . . κ(F (x), π(Fn(x), Gn(y)))) is calculated. We define a concept FITA as:
l i∈{1,...,n}
l i∈{1,...,n}
∃rulei.Rule u
∃xi.R[
Pκ(xi, rulei ◦ degree, x ◦ mf ) u P=(output, α{xi})
where α is an aggregate function and Pκ is a ternary predicate on the concrete
domain R[
The goal of a DL query is to determine the value of an instance. FITA delivers the membership of an arbitrary instance of the target concept to the goal fuzzy concept according to the compositional rule of inference. That is, if we have a sufficient number of instances of the target concept, we can calculate for each instance its membership to the goal fuzzy concept. This way, we obtain a set of points (x, μT (x)), where x is an arbitrary instance of the target concept and μT is the target fuzzy concept.
However, the goal of query answering is to determine an instance of the target concept. This is done by interpreting the set of points (x, μT (x)) as an area in R2 and defuzzifying this area. One of the most common defuzzification methods is the so called center of gravity method, where the geometrical center of gravity of a given area is calculated. The desired instance is then equal to the value of the x-coordinate of the center of gravity of the area. Hence, the desired instance ω can be calculated by the following formula: ω =
R x · μ(x)dx
R μ(x)dx (3)
To model the defuzzification process, we define a concept DefuzInfo as follows:
Finally, consider a concept C v ∃w.W . For a given instance θ of C, to determine an instance ω such that w(θ, ω) holds while considering fuzzy rules, we extend the definition of the concept C as follows: C v ∃di.DefuzInfo u P=(w, x) u Pdiv(x, sum{di ◦ prod}, sum{di ◦ fita ◦ output}). We use the already existing instances of the concept W as the arbitrary instances for determining the area that is defuzzified. If no instances of W are available in the knowledge base, we can always insert some instances which do not need to be in any relation with instances of other concepts. The number and value of such instances depends on the application domain, more precisely on the width of the range (subset of R) and on the value of dx in equation 3.
Although combining fuzzy logic with description logics has gained some interest recently, not much work has been done in this field yet. We mention some of the work which we consider most important.
[
[
Finally, we believe that our work is different from the existing work dealing with combination of fuzzy logic with description logics at a very fundamental level. The existing approaches maintain a fuzzy knowledge base and membership information of fuzzy A-Box assertions must be provided explicitly. In our approach, we model fuzzy membership functions and calculate the membership of an individual to membership functions inside the reasoner. Hence, we do not require extra syntax for supporting fuzzy reasoning. 7
In this paper, we have shown how fuzzy membership functions and fuzzy IFTHEN rules can be modeled with description logics that support the concrete domain R and simple aggregate functions like min, max, sum etc. Thus, we have presented a technique that enables easier modeling of complex dependencies by using fuzzy IF-THEN rules than by using only crisp DL rules. Our modeling technique allows to calculate a good approximate answer to a query inside a crisp DL reasoner. Hence, we have integrated and used fuzzy knowledge in a crisp knowledge base.
In the future, we intend to implement and evaluate our approach in a
concrete scenario. Our aim is to compute and provide fuzzy membership values as
modeled in section 3.2 at runtime in a lazy fashion instead of precomputing the
corresponding ABox entries a priori. A good candidate application could be an
extension by auctions of the semantic matchmaking portal presented in [