Fuzzy ontologies allow the representation of imprecise structured knowledge, typical in many real-world application domains. A key factor in the practical success of fuzzy ontologies is the availability of highly optimized reasoners. This short paper discusses a novel optimization technique: a reduction of the size of the optimization problems obtained during the inference by the fuzzy ontology reasoner fuzzyDL.
In recent years, we have noticed an increase in the number of applications for
mobile devices that could bene t from the use of semantic reasoning services [
However, little e ort has been paid so far to the study and implementation of
optimization techniques for fuzzy ontology reasoning, which is essential to reason
with real-world scenarios in practice (some exceptions are [
We assume the reader to be familiar with the syntax and semantics of fuzzy
Description Logics (DLs) [
This optimization problem has a solution i the fuzzy KB is consistent. In
fuzzyDL, we obtain a bounded Mixed Integer Linear Programming [
Let x; z be [0; 1]-variables, and xu be a rational unbounded variable. fuzzyDL
has to solve some restrictions involving fuzzy connectives, such as x1 = x2,
x1 x2 = z, x1 x2 = z, or x1 ) x2 = z. Furthermore, it also needs to solve
some restrictions d(xu) z involving fuzzy membership functions d such as the
trapezoidal(k1; k2; q1; q2; q3; q4) (see Table 1 (a)), the triangular(k1; k2; q1; q2,
q3), lef t(k1; k2; q1; q2), or right(k1; k2; q1; q2) [
Optimizing Lukasiewicz N-ary Operators Let us start with the case of conjunction concepts in Lukasiewicz fuzzy DLs. An n-ary concept of the form (C1 u C2 u u Cn) can be represented, using associativity, only using binary conjunctions (C1 u(C2 u( uCn)) : : : ). A binary conjunction concept introduces a restriction of the form x1 L x2 = z which, as shown in Section 2, can be encoded adding a new binary variable y. Hence, in order to represent the n-ary conjunction, n 1 new variables yi would be needed. However, it is possible to give a more e cient representation by considering the conjunction as an n-ary operator. Indeed, a restriction of the form x1 L x2 xn = z can be encoded using only one new binary variable and, thus, saves 2n 2 possible alternative assignments to the variables yi. y = 0 encodes the case z = Pin=1 xi (n 1) 0, and y = 1 encodes the case z = 0 and Pin=1 xi (n 1) < 0. Let us consider now disjunction concepts in Lukasiewicz fuzzy DLs. A binary disjunction can be represented adding a new binary variable y as fx1 + x2 z + y; y z; x1 + x2 z; y 2 f0; 1gg. Again, n 1 new binary variables would be needed but, similarly as before, considering the disjunction as an n-ary operator we would need only one new binary variable: An n-ary conjunction can be represented using binary conjunctions adding restrictions of the form x1 G x2 = z, which can be encoded as follows:
The idea is that if y = 0, x1 = z is the minimum; whereas if y = 1, x2 = z is the minimum. This adds a new variable y, so in the case of n-ary conjunctions there would be n 1 new variables. Treating the conjunction as an n-ary operator, a more e cient representation is possible. An n-ary conjunction introduces a restriction of the form x1 G x2 xn = z. To represent that the minimum of n variables xi is equal to z, we can use n binary variables yi such that if yi takes the value 0 then xi (representing the minimum) is equal to z, and such that the sum of the yi is 1, so z takes the value of some xi. Note that the minimum may not be unique. Such a representation is as follows: z
xi; for i 2 f1; : : : ; ng; xi
z + yi; for i 2 f1; : : : ; ng; n X yi = 1; i=1 yi 2 f0; 1g; for i 2 f1; : : : ; ng:
Now, we will show that it is possible to give a more e cient representation, Essentially, we need to encode n possible states. However, n possible states can be encoded using m = dlog2 ne new binary variables only. For instance, for n = 5, only dlog2 5e = 3 binary variables are necessary, where we use the encoding of the n = 5 states in Table 1 (b).
The main point is now to correctly encode the condition xi z + yi of the old encoding. We proceed as follows. Let bi be a string of length m, representing the value i 1 in base 2 (1 i n). For instance, for i = 4, b = 011, as illustrated in the table above. Let us de ne the expression eij (1 i n, 1 j m) as: eij = yj 1
if the jth bit of bi is 0 yj otherwise.
For i = 4, we have b = 011 and, thus, e41 = 1 y1, e42 = 1 y2, and e43 = y3. Now we are ready to provide the whole encoding:
xi
The case of the disjunction in Godel fuzzy DLs is dual. If an n-ary concept of the form (C1 t C2 t t Cn) is represented using binary disjunctions, n 1 new binary variables are needed. However, if we consider it as an n-ary concept, it is possible to use dlog2 ne new binary variables only:
m xi + X eij
j=1
Optimizing Fuzzy Membership Functions Let us start with the case of trapezoidal functions, which introduce a restriction of the form trapezoidal(k1; k2; q1; q2; q3; q4)(xu) z. A restriction of that form can be represented by adding 5 new binary variables yi as follows: xu + (k1 xu + (k1 xu + (k1 xu + (k1 xu + (k2 xu + (k2 xu + (k2 xu + (k2 q1)y2 q2)y3 q3)y4 q4)y5 q1)y1 q2)y2 q3)y3 q4)y4
xu q1)y2 xu 1 y1 k1; k1; k1; k1; k2; k2; k2; k2; y5; y3; k2; xu + (q1 q2)xu + (k2 xu + (q1 q2)xu + (k1 q2)y2
To reduce now the number of binary variables, the idea is to have 5 binary variables encoding the 5 possible states: xu q1 (y1 = 1), xu 2 [q1; q2] (y2 = 1), xu 2 [q2; q3] (y3 = 1), xu 2 [q3; q4] (y4 = 1), and xu q4 (y5 = 1). However, as shown in Table 1 (b), it is possible to represent 5 states using only 3 variables.
The case of other fuzzy membership functions is similar. In triangular functions, a nave encoding introduces 4 new variables to represent the 4 possible states, but it is possible to consider only 2. Finally, in left and right shoulder functions, it is necessary to consider 3 states, which can be achieved by adding 2 new binary variables, instead of the 3 ones needed in the non-optimal encoding.
By considering the fact that even for moderate sized ontologies we may easily generate thousands of such constraints, it is evident that the number of saved binary variables n, and hence the number of saved assignments 2n, is non-negligible.
Acknowledgement This research work has been partially supported by the CICYT project TIN2013-46238-C4-4-R and DGA-FSE.