Incompleteness and vagueness are inherent properties of knowledge in several real world domains and are particularly pervading in those domains where entities could be better described in natural language. In order to deal with incomplete and vague structured knowledge, several fuzzy extensions of Description Logics (DLs) have been proposed in the literature. In this paper, we address the issues raised by incomplete and vague knowledge in Inductive Logic Programming (ILP). We present a novel ILP method for inducing fuzzy DL inclusion axioms from crisp DL knowledge bases and discuss the results obtained in comparison with related works.
Incompleteness and vagueness are inherent properties of knowledge in several real world domains and are particularly pervading in those domains where entities could be better described in natural language. The issues raised by incomplete and vague knowledge have been traditionally addressed in the field of Knowledge Representation (KR).
Incomplete knowledge. The Open World Assumption (OWA) is used in KR to
codify the informal notion that in general no single agent or observer has complete
knowledge. The OWA limits the kinds of inference and deductions an agent can
make to those that follow from statements that are known to the agent to be
true. In contrast, the Closed World Assumption (CWA) allows an agent to infer,
from its lack of knowledge of a statement being true, anything that follows from
that statement being false. Heuristically, the OWA applies when we represent
knowledge within a system as we discover it, and where we cannot guarantee that
we have discovered or will discover complete information. In the OWA, statements
about knowledge that are not included in or inferred from the knowledge explicitly
recorded in the system may be considered unknown, rather than wrong or false.
Description Logics (DLs) are KR formalisms compliant with the OWA, thus
turning out to be particularly suitable for representing incomplete knowledge [
Mathematical Fuzzy Logic. Fuzzy Logic is the logic of fuzzy sets. A fuzzy set A
over a countable crisp set X is a function A : X → [
Px∈X (A ∩ B)(x)
Px∈X A(x) .
The trapezoidal (Fig. 1 (a)), the triangular (Fig. 1 (b)), the left-shoulder
function, Fig. 1 (c)), and the right-shoulder function, Fig. 1 (d)) are frequently used
to specify membership functions of fuzzy sets. Although fuzzy sets have a greater
expressive power than classical crisp sets, their usefulness depend critically on
the capability to construct appropriate membership functions for various given
concepts in different contexts. The problem of constructing meaningful
membership functions is a difficult one (see, e.g., [8, Chapter 10]). However, one easy
and typically satisfactory method to define the membership functions is to
uniformly partition the range of values into 5 or 7 fuzzy sets using either trapezoidal
functions, or triangular functions. The latter is the more used one, as it has less
parameters and is also the approach we adopt. For instance, the figure below
illustrates salary values (bounded by a minimum and maximum value), partitioned
uniformly into 5 fuzzy sets.
(1)
In Mathematical Fuzzy Logic [
A fuzzy interpretation I maps each atomic statement pi into [
Fuzzy Description Logics. Description Logics (DLs) are a family of decidable First
Order Logic (FOL) fragments that allow for the specification of structured
knowledge in terms of classes (concepts), instances (individuals ), and binary relations
between instances (roles) [
The semantics of DLs can be defined directly with set-theoretic formalizations
(as shown in Table 1 for the case of ALC) or through a mapping to FOL (as
shown in [
The main reasoning task for a DL KB K is the consistency check which tries to prove the satisfiability of K. Another well known reasoning service in DLs is instance check, i.e., the check of whether an ABox assertion is a logical implication of a DL KB. A more sophisticated version of instance check, called instance retrieval, retrieves, for a DL KB K, all (ABox) individuals that are instances of the given (possibly complex) concept expression C, i.e., all those individuals a such that K entails that a is an instance of C.
Concerning fuzzy DLs, several fuzzy extensions of DLs have been proposed
(see the survey in [
A fuzzy concrete domain or fuzzy datatype theory D = hΔD, · Di consists of
a datatype domain ΔD and a mapping · D that assigns to each data value an
element of ΔD, and to every n-ary datatype predicate d an n-ary fuzzy relation
over ΔD. We will restrict to unary datatypes as usual in fuzzy DLs. Therefore, · D
maps indeed each datatype predicate into a function from ΔD to [
In ALC(D), each role is either an object property (denoted with R) or a datatype property (denoted with T ). Complex concepts are built according to the following syntactic rules: C → > | ⊥ | A | C1 u C2 | C1 t C2 | ¬C | C1 → C2 | ∃R.C | ∀R.C | ∃T.d | ∀T.d . (3) Axioms in a fuzzy ALC(D) KB K = hT , Ai are graded, e.g. a GCI is of the form hC1 v C2, αi (i.e. C1 is a sub-concept of C2 to degree at least α). We may omit the truth degree α of an axiom; in this case α = 1 is assumed.
Concerning the semantics, let us fix a fuzzy logic. In fuzzy DLs, I maps
C into a function CI : ΔI → [
Now, ·I is extended to concepts as specified below (where x ∈ ΔI ):
⊥I (x) = 0, >I (x) = 1,
(C u D)I (x) = CI (x) ⊗ DI (x), (C t D)I (x) = CI (x) ⊕ DI (x),
(¬C)I (x) = CI (x), (C → D)I (x) = CI (x) ⇒ DI (x),
(∀R.C)I (x) = infy∈ΔI {RI (x, y) ⇒ CI (y)}, (∃R.C)I (x) = supy∈ΔI {RI (x, y) ⊗ CI (y)},
(∀T.d)I (x) = infy∈ΔD {T I (x, y) ⇒ dD(y)}, (∃T.d)I (x) = supy∈ΔD {T I (x, y) ⊗ dD(y)} .
Hence, for every concept C we get a function CI : ΔI → [
The satisfiability of axioms is then defined by the following conditions: (i) I satisfies an axiom ha:C, αi if CI (aI ) ≥ α; (ii) I satisfies an axiom h(a, b):R, αi if RI (aI , bI ) ≥ α; (iii) I satisfies an axiom hC v D, αi if (C v D)I ≥ α where (C v D)I = infx∈ΔI {CI (x) ⇒ DI (x)}. I is a model of K iff I satisfies each axiom in K. We say that K entails an axiom hτ, αi, denoted K |= hτ, αi, if any model of K satisfies hτ, αi. The best entailment degree of τ w.r.t. K, denoted bed(K, τ ), is defined as bed(K, τ ) = sup{α | K |= hτ, αi} . (4) 3 3.1
The problem considered in this paper concerns the automated induction of fuzzy E L(D) 6 GCI axioms providing a sufficient condition for a given atomic concept H. It can be cast as a rule learning problem, provided that positive and negative examples of H are available. This problem can be formalized as follows.
Given: – a consistent crisp DL KB K = hT , Ai (the background theory ); – an atomic concept H (the target concept ); – a set E = E + ∪ E − of crisp concept assertions labelled as either positive or negative examples for H (the training set ); – a set LH of fuzzy E L(D) GCI axioms (the language of hypotheses ) the goal is to find a set H ⊂ LH (a hypothesis ) such that: ∀e ∈ E +, K ∪ H |= e (completeness), and ∀e ∈ E −, K ∪ H 6|= e (consistency).
Here we assume that K ∩ E = ∅. Also, the language LH is given implicitly by means of syntactic restrictions over a given alphabet. In particular, the alphabet underlying LH is a subset of the alphabet for the language LK of the background 6 EL(D) is a fragment of ALC(D). theory. However, LH differs from LK as for the form of axioms. Please note that we do not make any specific assumption about the DL the background theory refers to. Two further restrictions hold naturally. One is that K 6|= E + since, in such a case, H would not be necessary to explain E +. The other is that K∪H 6|= ⊥, which means that K∪H is a consistent theory, i.e. has a model. An axiom φ ∈ LH covers an example e ∈ E iff K ∪ {φ} |= e.
The training examples. Given the target concept H, the training set E consists of concept assertions of the form a:H, where a is an individual occurring in K. Note that both K and E is crisp. Also, E is split into E + and E −. Note that, under OWA, E − consists of all those individuals which can be proved to be instance of ¬H. On the other hand, under CWA, E − is the collection of individuals, which cannot be proved to be instance of H.
The language of hypotheses. Given the target concept H, the hypotheses to be induced are fuzzy GCIs of the form
B v H , where the left-hand side is defined according to the following E L(D) syntax
B −→ > | A | ∃R.B | ∃T.d | B1 u B2 .
The language LH generated by this syntax is potentially infinite due, e.g., to the nesting of existential restrictions yielding to complex concept expressions such as ∃R1.(∃R2 . . . .(∃Rn.(C)) . . .). LH is made finite by imposing further restrictions on the generation process such as the maximal number of conjuncts and the depth of existential nesting allowed in the left-hand side. Also, note that the learnable GCIs do not have an explicit truth degree. However, as we shall see later on, once we have learned a fuzzy GCI of the form (5), we attach to it a confidence degree that is obtained by means of the cf function (see Eq. (8)). Finally, note that the syntactic restrictions of Eq. (6) w.r.t. Eq. (3) allow for a straightforward translation of the inducible axioms into rules of the kind “if x is a C1 and . . . and x is a Cn then x is an H”, which corresponds to the usual pattern in fuzzy rule induction (in our case, B v H is seen as a rule “if B then H”) . 3.2
The solution proposed for the learning problem defined in Section 3.1 is inspired
by Foil. Foil is a popular ILP algorithm for learning sets of rules which performs
a greedy search in order to maximise a gain function [
In Foil-DL, the learning strategy of Foil (i.e., the so-called sequential covering approach) is kept. The function Learn-Sets-of-Axioms (reported in Figure 2) carries on inducing axioms until all positive examples are covered. When an axiom is induced (step 3.), the positive examples covered by the axiom (step 5.) are removed from E (step 6.). In order to induce an axiom, the function (5) (6) function Learn-Sets-of-Axioms(K, H, E+, E−, LH): H begin 1. H := ∅; + = ∅ do 2. while E 6 3. φ := Learn-One-Axiom(K, H, E+, E−, LH); 4. H := H ∪ {φ}; 5. Eφ+ := {e ∈ E+|K ∪ φ |= e}; 6. E+ := E+ \ Eφ+; 7. endwhile 8. return H end
Learn-One-Axiom (reported in Figure 3) starts with the most general axiom (i.e. > v H) and specializes it by applying the refinement rules implemented in the function Refine (step 7.). The iterated specialization of the axiom continues until the axiom does not cover any negative example and its confidence degree is greater than a fixed threshold (θ). The confidence degree of axioms being generated with Refine allows for evaluating the information gain obtained on each refinement step by calling the function Gain (step 9.).
Due to the peculiarities of the language of hypotheses in Foil-DL, necessary changes are made to Foil as concerns the functions Refine and Gain. Details about these novel features are provided in the next two subsections. The refinement operator. The function Refine implements a specialization operator with the following refinement rules: AddA: adds an atomic concept A Add∃R.>: adds a complex concept ∃R.> by existential role restriction Add∃T.d: adds a complex concept ∃T.d by existential role restriction SubstA: replaces an atomic concept A with another atomic concept A0 s.t. A0 v A At each refinement step (i.e. at each call of Refine), the rules are applied first to the left-hand side of the axiom being specialized and then recursively to the range of all the conjuncts defined with existential role restriction. For example, let us consider that H is the target concept, A, A0, B, R, R0, T are concepts and properties occurring in K, and A0 v A holds in K. Under these assumptions, the axiom ∃R.B v H is specialized into the following axioms: – A u ∃R.B v H, B u ∃R.B v H, A0 u ∃R.B v H; – ∃R0.> u ∃R.B v H, ∃T.d u ∃R.B v H; – ∃R.(B u A) v H, ∃R.(B u A0) v H; – ∃R.(B u ∃R.>) v H, ∃R.(B u ∃R0.>) v H, ∃R.(B u ∃T.d) v H.
The application of the refinement rules is not blind. It takes the background theory into account in order to avoid the generation of redundant or useless function Learn-One-Axiom(K, H, E+, E−, LH): φ begin 1. B := >; 2. φ := B v H; 3. Eφ− := E−; 4. while cf (φ) < θ or Eφ− 6= ∅ do 5. Bbest := B; 6. maxgain := 0; 7. Φ := Refine(φ, LH) 8. foreach φ0 ∈ Φ do 9. gain := Gain(φ0, φ); 10. if gain ≥ maxgain then 11. maxgain := gain; 12. Bbest := B0; 13. endif 14. endforeach 15. φ := Bbest v H; 16. Eφ− := {e ∈ E−|K ∪ φ |= e}; 17. endwhile 18. return φ end hypotheses. For example, if the concept B0 is the range of R0 in K, the function Refine adds the conjunct ∃R0.B0 instead of ∃R0.>. One such “informed” refinement operator is able to perform “cautious” big steps in the search space.
Note that a specialization operator reduces the number of examples covered by a GCI. More precisely, the aim of a refinement step is to reduce the number of covered negative examples, while still keeping some covered positive examples. Since learned GCIs cover only positive examples, K will remain consistent after the addition of a learned GCI.
The heuristic. The function Gain implements an information-theoretic criterion for selecting the best candidate at each refinement step according to the following formula:
Gain(φ0, φ) = p ∗ (log2(cf (φ0)) − log2(cf (φ))) , (7) where p is the number of positive examples covered by the axiom φ that are still covered by φ0. Thus, the gain is positive iff φ0 is more informative in the sense of Shannon’s information theory, i.e. iff the confidence degree (cf ) increases. If there are some refinements, which increase the confidence degree, the function Gain tends to favour those that offer the best compromise between the confidence degree and the number of examples covered. Here, cf for an axiom φ of the form (5) is computed as a sort of fuzzy set inclusion degree (see Eq. (1)) between the fuzzy set represented by concept B and the (crisp) set represented by concept H. More formally: cf (φ) = cf (B v H) =
Pa∈Ind+H (A) bed(K, a:B) |IndH (A)| (8) where Ind+H (A) (resp., IndH (A) ) is the set of individuals occurring in A and involved in Eφ+ (resp., Eφ ∪ Eφ−) such that bed(K, a:B) > 0. We remind the reader + that bed(K, a:B) denotes the best entailment degree of the concept assertion a:B w.r.t. K as defined in Eq. (4). Note that for individuals a ∈ Ind+H (A), K |= a:H holds and, thus, bed(K, a:B u H) = bed(K, a:B). Also, note that, even if K is crisp, the possible occurrence of fuzzy concrete domains in expressions of the form ∃T.d in B may imply that both bed(K, B v H) 6∈ {0, 1} and bed(K, a:B) 6∈ {0, 1}. 3.3
A variant of Foil-DL has been implemented in the fuzzyDL-Learner 7 system and provided with two GUIs: One is a stand-alone Java application, the other is a tab widget plug-in for the ontology editor Prot´eg´e 8 (release 4.2).
Several implementation choices have been made. Notably, fuzzy GCIs in LH are interpreted under G¨odel semantics (see Eq. (2)). However, since K and E are represented in crisp DLs, we have used a classical DL reasoner, together with a specialised code, to compute the confidence degree of fuzzy GCIs. Therefore, the system relies on the services of DL reasoners to solve all the deductive inference problems necessary to Foil-DL to work, namely instance retrieval, instance check and subclasses retrieval. In particular, the sets Ind+H (A) and IndH (A) are computed by posing instance retrieval problems to the DL reasoner. Conversely, bed(K, a:∃T.d) can be computed from the derived T -fillers v of a, and applying the fuzzy membership function of d to v. The examples covered by a GCI, and, thus, the entailment tests in Learn-Sets-of-Axioms and Learn-One-Axiom, have been determined in a similar way.
The implementation of Foil-DL features several optimizations w.r.t. the solution strategy presented in Section 3.2. Notably, the search in the hypothesis space can be optimized by enabling a backtracking mode. This option allows to overcome one of the main limits of Foil, i.e. the sequential covering strategy. Because it performs a greedy search, formulating a sequence of rules without backtracking, Foil does not guarantee to find the smallest or best set of rules that explain the training examples. Also, learning rules one by one could lead to less and less interesting rules. To reduce the risk of a suboptimal choice at any search step, the greedy search can be replaced in Foil-DL by a beam search which maintains a list of k best candidates at each step instead of a single best candidate. Additionally, to guarantee termination, we provide two parameters to limit the search space: namely, the maximal number of conjuncts and the maximal depth of existential nesting allowed in a fuzzy GCI. In fact, the computation may end without covering all positive examples. 7 http://straccia.info/software/FuzzyDL-Learner 8 http://protege.stanford.edu/
In this section we report the results of a comparison between Foil-DL and
DLLearner on a very popular learning task in ILP proposed 20 years ago by Ryszard
Michalski [
For the purpose of this comparative study, we have considered two slightly different versions, trains2 and trains3, of an ontology encoding the original Trains data set. 9 The former has been adapted from the version distributed with DLLearner in order to be compatible with Foil-DL. Notably, the target classes EastTrain and WestTrain have become part of the terminology and several class assertion axioms have been added for representing positive and negative examples. The metrics for trains2 are reported in Table 2. The ontology does not encompass any data property. Therefore, no fuzzy concept can be generated when learning GCIs from trains2 with Foil-DL. However, the ontology can be slightly modified in order to test the fuzzy concept generation feature of FoilDL. Note that in trains2 cars can be classified according to the classes LongCar and ShortCar. Instead of one such crisp classification, we may want a fuzzy classification of cars. This is made possible by removing LongCar and ShortCar (together with the related class assertion axioms) from trains2 and introducing the data property hasLenght with domain Car and range double (together with several data property assertions). The resulting ontology, called trains3, presents the metrics reported in Table 2.
DL-Learner 10 features several algorithms. Among them, the closest to
FoilDL is ELTL since it implements a refinement operator for concept learning in
E L [
Trial with Foil-DL. The settings for this experiment allow for the generation of hypotheses with up to 5 conjuncts and 2 levels of existential nestings. Under 9 http://archive.ics.uci.edu/ml/datasets/Trains 10 http://dl-learner.org/Projects/DLLearner these restrictions, the GCI axioms learned by Foil-DL for the target concept EastTrain are: Confidence Axiom 1,000 3CarTrain and hasCar some (2LoadCar) subclass of EastTrain 1,000 3CarTrain and hasCar some (3WheelsCar) subclass of EastTrain 1,000 hasCar some (ElipseShapeCar) subclass of EastTrain 1,000 hasCar some (HexagonLoadCar) subclass of EastTrain whereas the following GCI axioms are returned by Foil-DL for WestTrain: Confidence Axiom 1,000 2CarTrain subclass of WestTrain 1,000 hasCar some (JaggedCar) subclass of WestTrain The algorithm returns the same GCIs under both OWA and CWA. Note that an important difference between learning in DLs and standard ILP is that the former works under OWA whereas the latter under CWA. In order to complete the Trains example we would have to introduce definitions and/or assertions to model the closed world. However, the CWA holds naturally in this example, because we have complete knowledge of the world, and thus the knowledge completion was not necessary. This explains the behaviour of Foil-DL which correctly induces the same hypotheses in spite of the opposite semantic assumptions. Trial with ELTL. For the target concept EastTrain, the class expression learned by ELTL is the following : EXISTS hasCar.(ClosedCar AND ShortCar) (accuracy: 1.0) whereas the following finding has been returned for the target concept WestTrain: EXISTS hasCar.LongCar (accuracy: 0.8) The latter is not fully satisfactory as for the example coverage.
Trial with CELOE. For the target concept EastTrain, CELOE learns several class expressions of which the most accurate is: hasCar some (ClosedCar and ShortCar) (accuracy: 1.0) whereas, for the target concept WestTrain, the most accurate among the ones found is the following: hasCar only (LongCar or OpenCar) (accuracy: 1.0) Note that the former coincide with the corresponding result obtained with ELTL while the latter is a more accurate variant of the corresponding class expression returned by ELTL. The increase in example coverage is due to the augmented expressive power of the DL supported in CELOE. Trial with Foil-DL. The outcomes for the target concepts EastTrain and WestTrain remain unchanged when Foil-DL is run on trains3 with the same configuration of the first trial. Yet, fuzzy concepts are automatically generated by Foil-DL from the data property hasLenght (see Figure 5). However, from the viewpoint of discriminant power, these concepts are weaker than the other crisp concepts occurring in the ontology. In order to make the fuzzy concepts emerge during the generation of hypotheses, we have appropriately biased the language of hypotheses. In particular, by enabling only the use of object and data properties in LH, Foil-DL returns the following axiom for EastTrain: Confidence Axiom 1,000 hasCar some (hasLenght_fair) and hasCar some (hasLenght_veryhigh) and hasCar some (hasLenght_verylow) subclass of EastTrain Conversely, for WestTrain, a lighter bias is sufficient to make fuzzy concepts appear in the learned axioms. In particular, by disabling the class 2CarTrain in LH, Foil-DL returns the following axioms: Confidence Axiom 1,000 hasCar some (2WheelsCar and 3LoadCar) and hasCar some (3LoadCar and CircleLoadCar) subclass of WestTrain 1,000 hasCar some (0LoadCar) subclass of WestTrain 1,000 hasCar some (JaggedCar) subclass of WestTrain 1,000 hasCar some (2LoadCar and hasLenght_high) subclass of WestTrain 1,000 hasCar some (ClosedCar and hasLenght_fair) subclass of WestTrain Trial with ELTL. For the target class EastTrain, ELTL returns a class expression which leaves some positive example uncovered (incomplete hypothesis): (EXISTS hasCar.TriangleLoadCar AND EXISTS hasCar.ClosedCar) (accuracy: 0.9) whereas, for the target concept WestTrain, it returns an overly general hypothesis which covers also negative examples (inconsistent hypothesis): TOP (accuracy: 0.5) This bad performance of ELTL on trains3 is due to the low expressivity of E L and to the fact that the classes LongCar and ShortCar, which appeared to be discriminant in the first trial, do not occur in trains3 and thus can not be used anymore for building hypotheses.
Trial with CELOE. The most accurate class expression found by CELOE for the target concept EastTrain is: ((not 2CarTrain) and hasCar some ClosedCar) (accuracy: 1.0) However, interestingly, CELOE learns also the following class expressions containing classes obtained by numerical restriction from the data property hasLenght: hasCar some (ClosedCar and hasLenght <= 48.5) (accuracy: 1.0) hasCar some (ClosedCar and hasLenght <= 40.5) (accuracy: 1.0) hasCar some (ClosedCar and hasLenght <= 31.5) (accuracy: 1.0) These “interval classes” are just a step back from the fuzzification which, conversely, Foil-DL is able to do. It is acknowledged that using fuzzy sets in place of “intervall classes” improves the readability of the induced knowledge about the data. As for the target concept WestTrain, the most accurate class expression among the ones found by CELOE is: (2CarTrain or hasCar some JaggedCar) (accuracy: 1.0) Once again, the augmented expressivity increases the effectiveness of DL-Learner. 5
We have described a novel method, named Foil-DL, which addresses the problem of learning fuzzy E L(D) GCI axioms from crisp DL assertions. The method extends Foil in a twofold direction: from crisp to fuzzy and from rules to GCIs. Notably, vagueness is captured by the definition of confidence degree reported in (8) and incompleteness is dealt with the OWA. Also, thanks to the variable-free syntax of DLs, the learnable GCIs are highly understandable by humans and translate easily into natural language sentences. In particular, Foil-DL present the learned axioms according to the user-friendly presentation style of the Manchester OWL syntax 11 (the same used in Prot´eg´e).
We would like to stress the fact that Foil-DL provides a different solution
from SoftFoil [
For the future, we intend to conduct a more extensive empirical evaluation of Foil-DL, which could suggest directions of improvement of the method towards more effective formulations of, e.g., the information gain function and the refinement operator as well as of the search strategy and the halt conditions employed in Learn-One-Axiom. Also, it can be interesting to analyse the impact of the different fuzzy logics on the learning process. Eventually, we shall investigate about learning fuzzy GCI axioms from FuzzyOWL 2 ontologies, by coupling the learning algorithm to the fuzzyDL reasoner, instead of learning from crisp OWL 2 data by using a classical DL reasoner. 11 http://www.w3.org/TR/owl2-manchester-syntax/ 12 Available at http://wiki.aksw.org/Projects/DLLearner/fuzzyTrains.