Tóm tắt Luận án Summary of doctoral thesis of computer

HUE UNIVERSITY COLLEGE OF SCIENCES TRAN THANH LUONG CONCEPT LEARNING FOR DESCRIPTION LOGIC-BASED INFORMATION SYSTEMS MAJOR: COMPUTER SCIENCE CODE: 62.48.01.01 SUMMARY OF DOCTORAL THESIS OF COMPUTER HUE, 2015 This thesis was completed at: College of Sciences, Hue University Supervisors: 1.Assoc. Prof. Dr.Sc. Nguyen Anh Linh, Warsaw University, Poland 2.Dr. Hoang Thi Lan Giao, College of Sciences, Hue University Reviewer 1: Prof. Dr.Sc. Hoang Van Kiem University of Information Technology, VNU-HCM Reviewer 2: Assoc. Prof. Dr. Doan Van Ban Institute of Information Technology, VAST Reviewer 3: Assoc. Prof. Dr. Nguyen Mau Han College of Sciences, Hue University The thesis will be presented at the Committee of Hue University, to be held by Hue University at .......h........, ........../........../2015 The thesis can be found at the follow libraries: • National Library of Vietnam • Library Information Center College of Science, Hue University PREFACE Concept learning in description logics (DLs) is similar to binary classification in traditional machine learning. However, the problem in the context of DLs differs from the traditional setting in that objects are described not only by attributes but also by binary relations between objects. The major settings of concept learning in DLs are as follows: • Setting (1): Given a knowledge base KB in a DL LΣ,Φ and sets E+, E− of individuals, learn a concept C in LΣ,Φ such that: 1. KB |= C(a) for all a ∈ E+, and 2. KB |= ¬C(a) for all a ∈ E−. The sets E+ and E− contain positive examples and negative ones of C, respec- tively. • Setting (2): This setting differs from the previous one only in that the second condition is replaced by the weaker one: KB 6|= C(a) for all a ∈ E−. • Setting (3): Given an interpretation I and sets E+, E− of individuals, learn a concept C in a DL LΣ,Φ such that: 1. I |= C(a) for all a ∈ E+, and 2. I |= ¬C(a) for all a ∈ E−. Note that I 6|= C(a) is the same as I |= ¬C(a). Concept learning in DLs was studied by a number of researchers. The related work can be divided into three main groups. The first group focuses on learnability in DLs [4, 8]. Cohen and Hirsh studied PAC-learnability of description logic and proposed a concept learning algorithm called LCSLearn, which is based on “least common subsumers” [4]. In [8] Franzier and Pitt provided some results on learnability in the CLASSIC description logic using some kinds of queries and either the exact learning model or the PAC model. The second group studies concept learning in DLs by using refinement operators. Badea and Nienhuys-Cheng [1] studied concept learning in the DL ALER, Iannone et al. [9] also investigated learning algorithms by using refinement operators for the richer DL ALC. The both of works studied concept learning in DLs using Setting (1). In [7] Fanizzi et al. introduced the DL-FOIL system that is adapted to concept learning for DL representations supporting the OWL-DL language. In [10] Lehmann and Hitzler introduced methods from inductive logic programing for concept learning in DL knowl- edge bases. Their algorithm, DL-Learner, exploits genetic programming techniques. All of works studied concept learning in DLs using Setting (2). The last group exploits bisimulation for concept learning in DLs [6]. Nguyen and Sza las applied bisimulation in DLs to model indiscernibility of objects [14]. They pro- posed a general bisimulation-based concept learning method for DL-based information systems. Divroodi et al. [5] studied C-learnability in DLs. These works mentioned con- cept learning in DLs using Setting (3). 1 Apart from the works of Nguyen and Sza las, Divroodi, which are base on bisim- ulation to guide the search for the result, all other works use refinement operators as in inductive logic programming and/or scoring functions-based search strategies. These works focus on concept learning using Setting (1) and Setting (2) for the simple DLs such as ALER, ALN and ALC. The works [14, 5] studied bisimulation-based concept learning in DLs using Setting (3). Both of works did not mentioned concept learning in DLs using Setting (1) and Setting (2). From the surveys as outlined above, we found that concept learning in DLs is a key problem. It is used to build useful concepts for semantic systems and ontologies. Therefore, it impacts on many practical applications which apply Semantic Web for systems. This thesis studies bisimulation-based concept learning methods in DLs. The main goals of the thesis are: • Studying the syntax, semantic of a large richer DLs by allowing to use attributes as basic elements of the language, data roles and DL-features as F , N . This class of DLs covers useful DLs, with well-known DLs like ALC, SHIQ, SHOIQ, SROIQ, . . . ; • Formulating and extending the definitions, theorems, lemmas on bisimulation for the mentioned class of DLs. We use bisimulation notions to model indiscernibility of objects as well as for concept learning in DLs; • Developing bisimulation-based concept learning algorithms for information sys- tems in DLs using Setting (3); • Building a method of granulating partitions of domain of interpretation in DLs. This method is base on bisimulation and using suitable selectors as well as infor- mation gain measure. • Proposing bisimulation-based concept learning algorithms for knowledge bases in DLs using Setting (1) and Setting (2). 2 Chương 1. DESCRIPTION LOGIC AND KNOWLEDGE BASE 1.1. Overview of description logics 1.1.1. Introduction DLs are built from three basic parts include a set of individuals, set of atomic concepts and set of atomic roles. 1.1.2. Description language ALC Definition 1.1 (ALC Syntax). Let ΣC be a set of concept names and ΣR be a set of role names (ΣC ∩ ΣR = ∅). The elements in ΣC are called atomic concepts. The description logic ALC allows concepts defined recursively as follows: • if A ∈ ΣC then A is a concept of ALC, • if C and D are concepts and r ∈ ΣR is a role then >, ⊥, ¬C, C uD, C unionsqD, ∃r.C and ∀r.C are also concepts of ALC.  Definition 1.2 (Semantics). An interpretation in description logic ALC is a pair I = 〈∆I, ·I〉, where ∆I is a non-empty set called the domain of I and ·I is a mapping called the interpretation function of I that associates each individual a ∈ ΣI with an element aI ∈ ∆I , each concept name A ∈ ΣC with a set AI ⊆ ∆I , each role name r ∈ ΣoR with a binary relation rI ⊆ ∆I×∆I . The interpretation of complex concepts as defined as follows: >I = ∆I , ⊥I = ∅, (¬C)I = ∆I \ CI , (∃r.C)I = {x ∈ ∆I | ∃y ∈ ∆I [rI(x, y) ∧ CI(y)]}, (C uD)I = CI ∩DI , (∀r.C)I = {x ∈ ∆I | ∀y ∈ ∆I [rI(x, y)⇒ CI(y)]}, (C unionsqD)I = CI ∪DI .  1.1.3. Knowledge representation From individuals, concepts and roles, one can build a system for representing and reasoning based on DLs include: box of role axioms (RBox), box of terminological ax- ioms (TBox), box of individual assertions (ABox), reasoning system and user interface. 1.1.4. Expressiveness Knowledge expressiveness of a DL depends on concept and role constructors which are allowed to use. DLs mainly differ in their expressive power and syntactic structures. 1.1.5. Description logics nomenclature • ALC - is an abbreviation for attributive language with complements. • S - ALC + transitive roles. • F - functional roles. • N - unqualified number restrictions. • R - complex role inclusions. • H - subroles. • I - inverse roles. • Q - qualified number restrictions. • O - nominals. 3 1.2. Syntax and semantics of description logics 1.2.1. Description language ALCreg Definition 1.3 (ALCreg Syntax). Let ΣC be a set of concept names and ΣR be a set of role names (ΣC ∩ ΣR = ∅). The elements in ΣC are called atomic concepts, while the elements in ΣR are called atomic roles. The description logic ALCreg allows concepts and roles defined recursively as follows: • if A ∈ ΣC then A is a concept of ALCreg, • if r ∈ ΣR then r is a role of ALCreg, • if C and D are concepts, R and S are roles then – ε, R ◦ S, R unionsq S, R∗, C? are roles of ALCreg, – >, ⊥, ¬C, C uD, C unionsqD, ∃R.C and ∀R.C are concepts of ALCreg.  The interpretation of complex roles in ALCreg are defined as follows: (R ◦ S)I = RI ◦ SI , (R unionsq S)I = RI ∪ SI , (R∗)I = (RI)∗, εI = {〈x, x〉 | x ∈ ∆I}, (C?)I = {〈x, x〉 | CI(x)}. 1.2.2. The LΣ,Φ language A DL-signature is a finite set Σ = ΣI ∪ΣdA ∪ΣnA ∪ΣoR ∪ΣdR, where ΣI is a set of individuals, ΣdA is a set of discrete attributes, ΣnA is a set of numeric attributes, ΣoR is a set of object role names, and ΣdR is a set of data roles. All the sets ΣI , ΣdA, ΣnA, ΣoR, ΣdR are pairwise disjoint. We consider some DL-features denoted by I (inverse),O (nominal), F (functional- ity),N (unqualified number restriction),Q (qualified number restriction), U (universal role), Self (local reflexivity of a role). A set of DL-features is a set consisting of zero or some of these names. Definition 1.4 (The LΣ,Φ Language). Let Σ be a DL-signature, Φ be a set of DL- features and L stand for ALCreg. The DL language LΣ,Φ allows object roles and con- cepts defined recursively as follows: • if r ∈ ΣoR then r is an object role of LΣ,Φ, • if A ∈ ΣC then A is concept of LΣ,Φ, • if A ∈ ΣA \ΣC and d ∈ range(A) then A = d and A 6= d are concepts of LΣ,Φ, • if A ∈ ΣnA and d ∈ range(A) then A ≤ d, A d are concepts of LΣ,Φ, • if R and S are object roles of LΣ,Φ, C and D are concepts of LΣ,Φ, r ∈ ΣoR, σ ∈ ΣdR, a ∈ ΣI , and n is a natural number then – ε, R ◦ S, R unionsq S, R∗ and C? are object roles of LΣ,Φ, – >, ⊥, ¬C, C uD, C unionsqD, ∀R.C and ∃R.C are concepts of LΣ,Φ, – if d ∈ range(σ) then ∃σ.{d} is a concept of LΣ,Φ, – if I ∈ Φ then R− is an object role of LΣ,Φ, – if O ∈ Φ then {a} is a concept of LΣ,Φ, 4 – if F ∈ Φ then ≤1 r is a concept of LΣ,Φ, – if {F , I} ⊆ Φ then ≤1 r− is a concept of LΣ,Φ, – if N ∈ Φ then ≥n r and ≤n r are concepts of LΣ,Φ, – if {N , I} ⊆ Φ then ≥n r− and ≤n r− are concepts of LΣ,Φ, – if Q ∈ Φ then ≥n r.C and ≤n r.C are concepts of LΣ,Φ, – if {Q, I} ⊆ Φ then ≥n r−.C and ≤n r−.C are concepts of LΣ,Φ, – if U ∈ Φ then U is an object role of LΣ,Φ, – if Self ∈ Φ then ∃r.Self is a concept of LΣ,Φ.  Definition 1.5 (Semantics of LΣ,Φ). An interpretation in LΣ,Φ is a pair I = 〈∆I, ·I〉, where ∆I is a non-empty set called the domain of I and ·I is a mapping called the interpretation function of I that associates each individual a ∈ ΣI with an element aI ∈ ∆I , each concept name A ∈ ΣC with a set AI ⊆ ∆I , each attribute A ∈ ΣA\ΣC with a partial function AI : ∆I → range(A), each object role name r ∈ ΣoR with a binary relation rI ⊆ ∆I ×∆I , and each data role σ ∈ ΣdR with a binary relation σI ⊆ ∆I × range(σ). The interpretation function ·I is extended to complex object roles and complex concepts as shown in Figure 1.1, where #Γ stands for the cardinality of the set Γ.  (R ◦ S)I = RI ◦ SI (R unionsq S)I = RI ∪ SI (C uD)I = CI ∩DI (R∗)I = (RI)∗ (R−)I = (RI)−1 (C unionsqD)I = CI ∪DI (C?)I = {〈x, x〉 | CI(x)} εI = {〈x, x〉 | x ∈ ∆I} {a}I = {aI} UI = ∆I ×∆I (A ≤ d)I = {x ∈ ∆I | AI(x) xác định và AI(x) ≤ d} >I = ∆I ⊥I = ∅ (A ≥ d)I = {x ∈ ∆I | AI(x) xác định và AI(x) ≥ d} (¬C)I = ∆I \ CI (A = d)I = {x ∈ ∆I | AI(x) = d} (A 6= d)I = (¬(A = d))I (A d)I = ((A ≥ d) u (A 6= d))I (∀R.C)I = {x ∈ ∆I | ∀y [RI(x, y)⇒ CI(y)]} (∃r.Self)I = {x ∈ ∆I | rI(x, x)} (∃R.C)I = {x ∈ ∆I | ∃y [RI(x, y) ∧ CI(y)]} (∃σ.{d})I = {x ∈ ∆I | σI(x, d)} (≥nR.C)I = {x ∈ ∆I | #{y | RI(x, y) ∧ CI(y)} ≥ n} (≥nR)I = (≥nR.>)I (≤nR.C)I = {x ∈ ∆I | #{y | RI(x, y) ∧ CI(y)} ≤ n} (≤nR)I = (≤nR.>)I Hình 1.1: Interpretation of complex object roles and complex concepts 1.3. Normal forms 1.3.1. Negation normal form of concepts A concept C is in negation normal form if negation only occurs in front of concept names in C. 1.3.2. Storage normal form of concepts Storage normal form of concepts is built based on negation normal form and set. Concepts in the storage normal form are represented in a set of sub-concept. 1.3.3. Converse normal form of roles An object role R is in the converse normal form if the inverse constructor is applied in R only to role names in R, which are different from U. 5 Let Σ±oR = ΣoR ∪ {r− | r ∈ ΣoR}. A basic object role is an element in Σ±oR (respectively, ΣoR) if the considered language allows inverse roles (respectively, does not allow inverse roles). 1.4. Knowledge base in description logics 1.4.1. Box of Role Axioms Definition 1.6 (Role axiom). A role inclusion axiom in LΣ,Φ is an expression of the form ε v r or R1◦ . . .◦Rk v r, where k ≥ 1, r ∈ ΣoR and R1, . . . , Rk are basic object roles of LΣ,Φ different from U . A role assertion in LΣ,Φ is an expression of the form Ref(r), Irr(r), Sym(r), Tra(r), or Dis(R, S), where r ∈ ΣoR and R, S are object roles of LΣ,Φ different from U . A role axiom in LΣ,Φ is a role inclusion axiom or a role assertion in LΣ,Φ.  Definition 1.7 (Box of role axioms). A box of role axioms (RBox) in LΣ,Φ is a finite set of role axioms in LΣ,Φ.  1.4.2. Box of terminological axioms Definition 1.8 (Terminological axiom). A general concept inclusion axiom in LΣ,Φ is an expression of the form C v D, where C and D are concepts in LΣ,Φ. A concept equivalent axiom in LΣ,Φ is an expression of the form C ≡ D, where C and D are concepts in LΣ,Φ. A terminological axiom in LΣ,Φ is a general concept inclusion axiom or a concept equivalent axiom in LΣ,Φ.  Definition 1.9 (Box of terminological axioms). A box of terminological (TBox) in LΣ,Φ is a finite set of terminological axioms in LΣ,Φ.  1.4.3. Box of individual assertions Definition 1.10 (Individual assertion). An individual assertion in LΣ,Φ is an expres- sion of the form C(a), R(a, b), ¬R(a, b), a = b and a 6= b, where C is a concept and R is an object role of LΣ,Φ.  Definition 1.11 (Box of individual assertions). A box of individual assertions (ABox) in LΣ,Φ is a finite set of individual assertions in LΣ,Φ.  1.4.4. Knowledge base and model of knowledge base Definition 1.12 (Knowledge base). A knowledge base in LΣ,Φ is a triple KB = 〈R, T ,A〉, where R is an RBox, T is a TBox and A is an ABox in LΣ,Φ.  Definition 1.13 (Model). An interpretation I is a model of RBox R (respectively, TBox T , ABoxA), denoted by I |= R (respectively, I |= T , I |= A) if it validates all the role axioms of R (respectively, terminological axioms of T , individual assertions of A). An interpretation I is a model of knowledge base KB = 〈R, T ,A〉, denoted by I |= KB, if it is a model of R, T , A.  Example 1.1. This example concerns knowledge bases about publications. Let Φ = {I,O,N ,Q}, ΣI = {P1,P2,P3,P4,P5,P6}, ΣC = {Pub,Awarded ,UsefulPub, Ad}, ΣdA = ΣC, ΣnA = {Year}, 6 ΣoR = {cites , cited_by}, ΣdR = ∅, R= {cites− v cited_by , cited_by− v cites , Irr(cites)}, T = {> v Pub,UsefulPub ≡ ∃cited_by .>}, A′0 = {Awarded(P1),¬Awarded(P2),¬Awarded(P3),Awarded(P4), ¬Awarded(P5),Awarded(P6),Year(P1) = 2010,Year(P2) = 2009, Year(P3) = 2008,Year(P4) = 2007,Year(P5) = 2006,Year(P6) = 2006, cites(P1,P2), cites(P1,P3), cites(P1,P4), cites(P1,P6), cites(P2,P3), cites(P2,P4), cites(P2,P5), cites(P3,P4), cites(P3,P5), cites(P3,P6), cites(P4,P5), cites(P4,P6)}, A0 =A′0 ∪ {(¬∃cited_by .>)(P1), (∀cited_by .{P2,P3,P4})(P5)}. Then KB′0 = 〈R, T ,A′0〉and KB0 = 〈R, T ,A0〉are knowledge bases in LΣ,Φ. The axiom > v P states that the domain of any model of KB′0 or KB0 consists of only publications.  1.5. Reasoning in description logic There are a number of reasoning problems in DL-based knowledge bases. One can uses two type of algorithms to solve them include structural subsumption algorithms and tableau algorithms. Structural subsumption algorithms have proved effective for simple DLs such as FL0, FL⊥, ALN , while tableau ones are usually used to solve reasoning problems for a lager class of DLs such asALC [11],ALCI [12],ALCIQ [12], SHIQ [13],. . . Summary of Chapter 1 In this chapter, we have introduced a general of DLs, knowledge expressiveness of DLs. Based on the syntax and semantics of DLs, we have presented about knowledge base, model of knowledge base and the keys of reasoning in DLs. Apart from the general language based on the DLs ALCreg with the features I (inverse role), O (nominal), F (functionally), N (unqualified number restrictions), Q (qualified restriction), U (universal role), Self (local reflexivity of an object role), we also took attributes as basic elements of the language, include discrete and numeric attributes. This approach is suitable for practical information systems based on description logic. 7 Chương 2. BISIMUALTION IN DESCRIPTION LOGICS AND INVARIANCE 2.1. Introduction Bisimulations are studied in modal logics [2], [17]. Bisimulation is viewed as a binary relation associating systems which describe the similar of two states in that one system as well as the similar of Kripke models. Divroodi and Nguyen studied bisimulations for a number of DLs [6]. 2.2. Bisimulation 2.2.1. Preliminary Definition 2.1 (Bisimulation). Let Σ and Σ† be DL-signatures such that Σ† ⊆ Σ, Φ and Φ† be sets of DL-features such that Φ† ⊆ Φ, I and I ′ be interpretations in LΣ,Φ. A binary relation Z ⊆ ∆I × ∆I′ is called an LΣ†,Φ†-bisimulation between I and I ′ if the following conditions hold for every a ∈ Σ†I , A ∈ Σ†C , B ∈ Σ†A \ Σ†C , r ∈ Σ†oR, σ ∈ Σ†dR, d ∈ range(σ), x, y ∈ ∆I , x′, y′ ∈ ∆I ′ : Z(aI, aI ′ ) (2.1) Z(x, x′)⇒ [AI(x)⇔ AI′(x′)] (2.2) Z(x, x′)⇒ [BI(x) = BI′(x′) or both are undefined] (2.3) [Z(x, x′) ∧ rI(x, y)]⇒ ∃y′ ∈ ∆I′[Z(y, y′) ∧ rI′(x′, y′)] (2.4) [Z(x, x′) ∧ rI′(x′, y′)]⇒ ∃y ∈ ∆I[Z(y, y′) ∧ rI(x, y)] (2.5) Z(x, x′)⇒ [σI(x, d)⇔ σI′(x′, d)], (2.6) if I ∈ Φ† then [Z(x, x′) ∧ rI(y, x)]⇒ ∃y′ ∈ ∆I′[Z(y, y′) ∧ rI′(y′, x′)] (2.7) [Z(x, x′) ∧ rI′(y′, x′)]⇒ ∃y ∈ ∆I[Z(y, y′) ∧ rI(y, x)], (2.8) if O ∈ Φ† then Z(x, x′)⇒ [x = aI ⇔ x′ = aI′], (2.9) if N ∈ Φ† then Z(x, x′)⇒ #{y | rI(x, y)} = #{y′ | rI′(x′, y′)}, (2.10) if {N , I} ⊆ Φ† then Z(x, x′)⇒ #{y | rI(y, x)} = #{y′ | rI′(y′, x′)}, (2.11) if F ∈ Φ† then Z(x, x′)⇒ [#{y | rI(x, y)} ≤ 1⇔ #{y′ | rI′(x′, y′)} ≤ 1], (2.12) 8 if {F , I} ⊆ Φ† then Z(x, x′)⇒ [#{y | rI(y, x)} ≤ 1⇔ #{y′ | rI′(y′, x′)} ≤ 1], (2.13) if Q ∈ Φ† then if Z(x, x′) holds then, for every r ∈ Σ†oR, there exists a bijection h : {y | rI(x, y)} → {y′ | rI′(x′, y′)} such that h ⊆ Z, (2.14) if {Q, I} ⊆ Φ† then if Z(x, x′) holds then, for every r ∈ Σ†oR, there exists a bijection h : {y | rI(y, x)} → {y′ | rI′(y′, x′)} such that h ⊆ Z, (2.15) if U ∈ Φ† then ∀x ∈ ∆I ∃x′ ∈ ∆I′ Z(x, x′) (2.16) ∀x′ ∈ ∆I′ ∃x ∈ ∆I Z(x, x′), (2.17) if Self ∈ Φ† then Z(x, x′)⇒ [rI(x, x)⇔ rI′(x′, x′)], (2.18) where #Γ stands for cardinality of the set Γ.  Lemma 2.1. 1. The relation {〈x, x〉 | x ∈ ∆I} is an LΣ†,Φ†-bisimulation between I and I. 2. If Z is an LΣ†,Φ†-bisimulation between I and I ′ then Z−1 is an LΣ†,Φ†-bisimulation between I ′ and I. 3. If Z1 is an LΣ†,Φ†-bisimulation between I0 and I1, Z2 is an LΣ†,Φ†-bisimulation between I1 and I2 then Z1 ◦ Z2 is an LΣ†,Φ†-bisimulation between I0 and I2. 4. If Z is a set of LΣ†,Φ†-bisimulations between I and I ′ then ⋃Z is an LΣ†,Φ†- bisimulation between I and I ′.  2.2.2. Bisimilarity and equivalence relation Definition 2.2. Let I and I ′ be interpretations in LΣ,Φ. We say that I is LΣ†,Φ†- bisimilar to I ′ if there exists an LΣ†,Φ†-bisimulation between I and I ′.  Definition 2.3. Let I and I ′ be interpretations in LΣ,Φ, x ∈ ∆I and x′ ∈ ∆I′. We say that x is LΣ†,Φ†-bisimilar to x′ if there exists an LΣ†,Φ†-bisimulation between I and I ′ such that Z(x, x′) holds.  Definition 2.4. Let I and I ′ be interpretations in LΣ,Φ, x ∈ ∆I and x′ ∈ ∆I′. We say that x is LΣ†,Φ†-equivalent to x′ if, for every concept C of LΣ†,Φ†, x ∈ CI iif x′ ∈ CI′.  9 2.3. Invariant for bisimulation 2.3.1.