Học khái niệm cho các hệ thống thông tin dựa trên logic mô tả

Nội dung tài liệu: Học khái niệm cho các hệ thống thông tin dựa trên logic mô tả

1. ĐẠI HÅC HUẾ TRƯỜNG ĐẠI HÅC KHOA HÅC TRẦN THANH LƯƠNG HÅC KHÁI NIỆM CHO CÁC HỆ THÈNG THÆNG TIN DỰA TRÊN LOGIC MÆ TẢ CHUYÊN NGÀNH: KHOA HÅC MÁY TÍNH MÃ SÈ: 62.48.01.01 LUẬN ÁN TIẾN SĨ MÁY TÍNH HUẾ, NĂM 2015
2. Công tr¼nh này được hoàn thành t¤i: Trường Đại học Khoa học - Đại học Hu¸ Người hướng d¨n khoa học: 1. PGS. TSKH. Nguy¹n Anh Linh, Trường Đại học Warsaw, Ba Lan 2. TS. Hoàng Thị Lan Giao, Trường Đại học Khoa học, Đại học Hu¸ Ph£n bi»n 1: GS. TSKH. Hoàng V«n Ki¸m Trường Đại học CNTT, ĐHQG TP. Hồ Ch½ Minh Ph£n bi»n 2: PGS. TS. Đoàn V«n Ban Vi»n Công ngh» Thông tin, Vi»n Hàn l¥m KH&CN Vi»t Nam Ph£n bi»n 3: PGS. TS. Nguy¹n Mªu H¥n Trường Đại học Khoa học, Đại học Hu¸ Luªn ¡n s³ được b£o v» t¤i Hëi đồng ch§m luªn ¡n c§p Đại học Hu¸ họp t¤i Đại học Hu¸ vào lúc giờ ngày th¡ng n«m 2015 Có thº t¼m hiºu luªn ¡n t¤i thư vi»n: • Thư vi»n Quèc gia Vi»t Nam • Thư vi»n Trường Đại học Khoa học, Đại học Hu¸
3. MÐ ĐẦU V§n đề học kh¡i ni»m trong logic mô t£ tương tự như ph¥n lớp nhị ph¥n trong học m¡y truy·n thèng. Tuy nhi¶n, vi»c học kh¡i ni»m trong ngú c£nh logic mô t£ kh¡c với học m¡y truy·n thèng ở điểm, c¡c đối tượng không ch¿ được đặc t£ b¬ng c¡c thuëc t½nh mà cán được đặc t£ b¬ng c¡c mèi quan h» giúa c¡c đối tượng. Bài to¡n học kh¡i ni»m được đặt ra theo ba ngú c£nh ch½nh như sau: • Ngú c£nh (1): Cho cơ sở tri thùc KB trong logic mô t£ L và c¡c tªp c¡c c¡ thº E+, E−. Học kh¡i ni»m C trong L sao cho: 1. KB j= C(a) với mọi a 2 E+, và 2. KB j= :C(a) với mọi a 2 E−. trong đó, tªp E+ chùa c¡c m¨u dương và E− chùa c¡c m¨u ¥m cõa C. • Ngú c£nh (2): Ngú c£nh này kh¡c với ngú c£nh đã đề cªp ở tr¶n là điều ki»n thù hai được thay b¬ng mët điều ki»n y¸u hơn: 1. KB j= C(a) với mọi a 2 E+, và 2. KB 6j= C(a) với mọi a 2 E−. • Ngú c£nh (3): Cho mët di¹n dịch I và c¡c tªp c¡c c¡ thº E+, E−. Học kh¡i ni»m C trong logic mô t£ L sao cho: 1. I j= C(a) với mọi a 2 E+, và 2. I j= :C(a) với mọi a 2 E−. Chú ý r¬ng I j= :C(a) tương đồng với I 6j= C(a). Học kh¡i ni»m trong logic mô t£ đ¢ được nhi·u nhà khoa học quan t¥m nghi¶n cùu và chia thành ba hướng ti¸p cªn ch½nh. Hướng ti¸p cªn thù nh§t tªp trung vào kh£ n«ng học trong logic mô t£ [4], [8]. Cohen và Hirsh nghi¶n cùu lý thuy¸t v· kh£ n«ng học trong logic mô t£ và đề xu§t thuªt to¡n học kh¡i ni»m LCSLearn dựa tr¶n c¡c “bao hàm chung nhỏ nhất” [4]. Frazier và Pitt đã nghi¶n cùu v· kh£ n«ng học trong logic mô t£ Classic b¬ng c¡ch sû dụng c¡c truy v§n tr¶n mô h¼nh học PAC [8]. Trong hướng ti¸p cªn thù hai nghi¶n cùu học kh¡i ni»m trong logic mô t£ sû dụng to¡n tû làm mịn. Badea và Nienhuys-Cheng [1] nghi¶n cùu học kh¡i ni»m trong logic mô t£ ALER, Iannone và cëng sự [9] cũng nghi¶n cùu c¡c thuªt to¡n học tr¶n mët logic mô t£ giàu ngú nghĩa hơn, ALC. C£ hai công tr¼nh tr¶n đều nghi¶n cùu vi»c học kh¡i ni»m trong logic mô t£ với Ngú c£nh (1). Fanizzi cùng cëng sự [?]iới thi»u h» thèng DL-Foil cho vi»c học kh¡i ni»m trong logic mô t£ hé trñ ngôn ngú logic mô t£ OWL [7]. Lehmann và Hitzler đề xu§t thuªt to¡n học DL-Learner theo phương ph¡p lªp tr¼nh đệ quy và có khai th¡c th¶m c¡c kỹ thuªt v· lªp tr¼nh di truy·n [10]. C¡c công tr¼nh này nghi¶n cùu vi»c học kh¡i ni»m trong logic mô t£ với Ngú c£nh (2). Hướng ti¸p cªn thù ba nghi¶n cùu học kh¡i ni»m trong logic mô t£ sû dụng mô phỏng hai chi·u [6]. Nguyen và Sza las đã ¡p dụng mô phỏng hai chi·u vào trong logic mô t£ để mô h¼nh hóa t½nh không ph¥n bi»t được cõa c¡c đối tượng [14]. C¡c t¡c gi£ 1
4. đã đề xu§t mët phương ph¡p têng qu¡t để học kh¡i ni»m cho c¡c h» thèng thông tin trong logic mô t£. Divroodi [5] và cëng sự đã nghi¶n cùu kh£ n«ng học trong logic mô t£ sû dụng mô phỏng hai chi·u. C¡c công tr¼nh này nghi¶n cùu bài to¡n học kh¡i ni»m trong logic mô t£ với Ngú c£nh (3). Ngo¤i trø công tr¼nh cõa Nguyen và Sza las [14], Divroodi [5] sû dụng mô phỏng hai chi·u trong logic mô t£ để hướng d¨n vi»c t¼m ki¸m kh¡i ni»m k¸t qu£, t§t c£ c¡c công tr¼nh nghi¶n cùu cán l¤i đều sû dụng to¡n tû làm mịn như trong lªp tr¼nh logic đệ quy và/hoặc c¡c chi¸n lược t¼m ki¸m dựa vào c¡c hàm t½nh điểm mà không sû dụng mô phỏng hai chi·u. C¡c công tr¼nh này chõ y¸u tªp trung vào v§n đề học kh¡i ni»m với Ngú c£nh (1) và Ngú c£nh (2) tr¶n c¡c logic mô t£ kh¡ đơn gi£n ALER, ALN và ALC. Trong khi đó công tr¼nh [14] và [5] sû dụng mô phỏng hai chi·u cho vi»c học kh¡i ni»m trong c¡c logic mô t£ ch¿ với Ngú c£nh (3). Hai công tr¼nh tr¶n không đề cªp đến v§n đề học kh¡i ni»m trong logic mô t£ với Ngú c£nh (1) và Ngú c£nh (2). Tø c¡c kh£o s¡t như đã n¶u ở tr¶n, chúng ta nhªn th§y r¬ng học kh¡i ni»m trong logic mô t£ là mët v§n đề quan trọng trong vi»c x¥y dựng c¡c kh¡i ni»m húu ½ch phục vụ cho c¡c h» thèng ngú nghĩa nói chung và ontology nói ri¶ng. Tø đó, nó t¡c động l¶n nhi·u ùng dụng trong thực t¸ có ¡p dụng Web ngú nghĩa vào h» thèng. Do đó, luªn ¡n tªp trung nghi¶n cùu c¡c phương ph¡p học kh¡i ni»m trong logic mô t£ dựa tr¶n mô phỏng hai chi·u với c¡c mục ti¶u ch½nh đặt ra là: • Nghi¶n cùu cú ph¡p, ngú nghĩa đối với mët lớp lớn c¡c logic mô t£ giàu ngú nghĩa hơn so với c¡c công tr¼nh đã có b¬ng c¡ch cho ph²p sû dụng c¡c thuëc t½nh như là c¡c ph¦n tû cơ b£n cõa ngôn ngú, c¡c quan h» thông qua c¡c vai trá dú li»u và đề cªp đến đặc trưng F, N . Lớp c¡c logic này bao phõ nhúng logic mô t£ húu ½ch như ALC, SHIF, SHIQ, SHOIN , SHOIQ, SROIQ, • X¥y dựng, mở rëng c¡c định nghĩa, định lý, bê đề v· mô phỏng hai chi·u trong lớp c¡c logic mô t£ đã đề cªp ở tr¶n và sû dụng nó để mô h¼nh hóa t½nh không ph¥n bi»t được cõa c¡c đối tượng làm cơ sở cho c¡c thuªt to¡n học kh¡i ni»m trong logic mô t£; • Ph¡t triºn thuªt to¡n học kh¡i ni»m dựa tr¶n mô phỏng hai chi·u cho c¡c h» thèng thông tin trong logic mô t£ với Ngú c£nh (3); • X¥y dựng phương ph¡p làm mịn ph¥n ho¤ch mi·n cõa c¡c di¹n dịch trong logic mô t£ dựa tr¶n mô phỏng hai chi·u sû dụng c¡c bë chọn hñp lý và độ đo gia lượng thông tin; • Đề xu§t c¡c thuªt to¡n học kh¡i ni»m cho c¡c cơ sở tri thùc trong logic mô t£ với Ngú c£nh (1) và Ngú c£nh (2) sû dụng mô phỏng hai chi·u. 2
5. Chương 1. LOGIC MÆ TẢ VÀ CƠ SÐ TRI THỨC 1.1. Têng quan v· logic mô t£ 1.1.1. Giới thi»u Logic mô t£ được x¥y dựng dựa vào ba thành ph¦n cơ b£n gồm tªp c¡c c¡ thº, tªp c¡c kh¡i ni»m nguy¶n tè và tªp c¡c vai trá nguy¶n tè. 1.1.2. Biºu di¹n tri thùc Tø c¡c c¡ thº, c¡c kh¡i ni»m và c¡c vai trá, người ta có thº x¥y dựng mët h» thèng để biºu di¹n và suy luªn tri thùc dựa tr¶n logic mô t£ gồm: bë ti¶n đề vai trá, bë ti¶n đề thuªt ngú, bë kh¯ng định, h» thèng suy luªn, giao di»n người dùng. 1.1.3. Ngôn ngú logic mô t£ ALC Định nghĩa 1.1 (Cú ph¡p cõa ALC). Cho ΣC là tªp c¡c t¶n kh¡i ni»m và ΣR là tªp c¡c t¶n vai trá (ΣC \ ΣR = ;). C¡c ph¦n tû cõa ΣC được gọi là kh¡i ni»m nguy¶n tè. Logic mô t£ ALC cho ph²p c¡c kh¡i ni»m được định nghĩa mët c¡ch đệ quy như sau: • n¸u A 2 ΣC th¼ A là mët kh¡i ni»m cõa ALC, • n¸u C, D là c¡c kh¡i ni»m và r 2 ΣR là mët vai trá th¼ >, ?, :C, C u D, C t D, 9r:C và 8r:C cũng là c¡c kh¡i ni»m cõa ALC.  Định nghĩa 1.2 (Ngú nghĩa cõa ALC). Mët di¹n dịch trong logic mô t£ ALC là mët bë I = h∆I; ·Ii, trong đó ∆I là mët tªp kh¡c réng được gọi là mi·n cõa I và ·I là mët ¡nh x¤, được gọi là hàm di¹n dịch cõa I, cho ph²p ¡nh x¤ méi c¡ thº a 2 ΣI I I I I thành mët ph¦n tû a 2 ∆ , méi t¶n kh¡i ni»m A 2 ΣC thành mët tªp A ⊆ ∆ và I I I méi t¶n vai trá r 2 ΣR thành mët quan h» hai ngôi r ⊆ ∆ × ∆ . Di¹n dịch cõa c¡c kh¡i ni»m phùc được x¡c định như sau: >I = ∆I, ?I = ;, (:C)I = ∆I n CI, (9r:C)I = fx 2 ∆I j 9y 2 ∆I [rI(x; y) ^ CI(y)]g, (C u D)I = CI \ DI, I I I I I I I I (8r:C) = fx 2 ∆ j 8y 2 ∆ [r (x; y) ) C (y)]g, (C t D) = C [ D .  1.1.4. Kh£ n«ng biºu di¹n Kh£ n«ng biºu di¹n tri thùc cõa logic mô t£ phụ thuëc vào c¡c t¤o tû kh¡i ni»m và t¤o tû vai trá mà nó được ph²p sû dụng. Logic sû dụng càng nhi·u t¤o tû th¼ càng có kh£ n«ng biºu di¹n tèt. 1.1.5. Logic mô t£ và c¡c t¶n gọi • ALC - logic mô t£ cơ b£n ALC là ngôn ngú kh¡i ni»m thuëc t½nh có phõ định. •S - ALC + t½nh ch§t b­c c¦u cõa vai trá. •F - t½nh ch§t hàm. •N - h¤n ch¸ sè lượng không định t½nh. •R - bao hàm vai trá phùc. 3
6. •H - bao hàm vai trá. •I - vai trá nghịch đảo. •Q - h¤n ch¸ sè lượng có định t½nh. •O - định danh. 1.2. Cú ph¡p và ngú nghĩa cõa logic mô t£ 1.2.1. Ngôn ngú logic mô t£ ALCreg Định nghĩa 1.3 (Cú ph¡p cõa ALCreg). Cho ΣC là tªp c¡c t¶n kh¡i ni»m và ΣR là tªp c¡c t¶n vai trá (ΣC \ ΣR = ;). C¡c ph¦n tû cõa ΣC được gọi là kh¡i ni»m nguy¶n tè và c¡c ph¦n tû cõa ΣR được gọi là vai trá nguy¶n tè. Logic mô t£ động ALCreg cho ph²p c¡c kh¡i ni»m và c¡c vai trá đưñc định nghĩa mët c¡ch đệ quy như sau: • n¸u r 2 ΣR th¼ r là mët vai trá cõa ALCreg, • n¸u A 2 ΣC th¼ A là mët kh¡i ni»m cõa ALCreg, • n¸u C, D là c¡c kh¡i ni»m và R; S là c¡c vai trá th¼ ∗ – ", R ◦ S, R t S, R , C? là c¡c vai trá cõa ALCreg, – >, ?, :C, C u D, C t D, 9R:C và 8R:C là c¡c kh¡i ni»m cõa ALCreg.  Di¹n dịch cõa c¡c vai trá phùc trong ALCreg được x¡c định như sau: (R ◦ S)I = RI ◦ SI, (R t S)I = RI [ SI, (R∗)I = (RI)∗, "I = fhx; xij x 2 ∆Ig, (C?)I = fhx; xij CI(x)g. 1.2.2. Ngôn ngú logic mô t£ LΣ;Φ Mët bë ký tự logic mô t£ là mët tªp húu h¤n Σ = ΣI [ ΣdA [ ΣnA [ ΣoR [ ΣdR, trong đó ΣI là tªp c¡c c¡ thº, ΣdA là tªp c¡c thuëc t½nh rời r¤c, ΣnA là tªp c¡c thuëc t½nh sè, ΣoR là tªp c¡c t¶n vai trá đối tượng và ΣdR là tªp c¡c vai trá dú li»u. T§t c£ c¡c tªp ΣI , ΣdA, ΣnA, ΣoR và ΣdR rời nhau tøng đôi mët. X²t c¡c đặc trưng cõa logic mô t£ gồm I (vai trá nghịch đảo), O (định danh), F (t½nh ch§t hàm), N (h¤n ch¸ sè lượng không định t½nh), Q (h¤n ch¸ sè lượng có định t½nh), U (vai trá phê qu¡t), Self (t½nh ph£n x¤ cục bë cõa vai trá). Tªp c¡c đặc trưng cõa logic mô t£ Φ là mët tªp réng hoặc tªp chùa mët sè c¡c đặc trưng n¶u tr¶n. Định nghĩa 1.4 (Ngôn ngú LΣ;Φ). Cho Σ là bë ký tự logic mô t£, Φ là tªp c¡c đặc trưng cõa logic mô t£ và L đại di»n cho ALCreg. Ngôn ngú logic mô t£ LΣ;Φ cho ph²p c¡c vai trá đối tượng và c¡c kh¡i ni»m được định nghĩa mët c¡ch đệ quy như sau: • n¸u r 2 ΣoR th¼ r là mët vai trá đối tượng cõa LΣ;Φ, • n¸u A 2 ΣC th¼ A là mët kh¡i ni»m cõa LΣ;Φ, • n¸u A2ΣA n ΣC và d2range(A) th¼ A = d và A 6= d là c¡c kh¡i ni»m cõa LΣ;Φ, • n¸u A 2 ΣnA và d 2 range(A) th¼ A ≤ d, A d là c¡c kh¡i ni»m cõa LΣ;Φ, • n¸u R và S là c¡c vai trá đối tượng cõa LΣ;Φ, C và D là c¡c kh¡i ni»m cõa LΣ;Φ, r 2 ΣoR, σ 2 ΣdR, a 2 ΣI và n là mët sè tự nhi¶n th¼ ∗ – ", R ◦ S , R t S, R và C? là c¡c vai trá đối tượng cõa LΣ;Φ, 4
7. – >, ?, :C, C u D, C t D, 9R:C và 8R:C là c¡c kh¡i ni»m cõa LΣ;Φ, – n¸u d 2 range(σ) th¼ 9σ:fdg là mët kh¡i ni»m cõa LΣ;Φ, − – n¸u I 2 Φ th¼ R là mët vai trá đối tượng cõa LΣ;Φ, – n¸u O 2 Φ th¼ fag là mët kh¡i ni»m cõa LΣ;Φ, – n¸u F 2 Φ th¼ ≤1 r là mët kh¡i ni»m cõa LΣ;Φ, − – n¸u fF; Ig ⊆ Φ th¼ ≤1 r là mët kh¡i ni»m cõa LΣ;Φ, – n¸u N 2 Φ th¼ ≥n r và ≤n r là c¡c kh¡i ni»m cõa LΣ;Φ, − − – n¸u fN ; Ig ⊆ Φ th¼ ≥n r và ≤n r là c¡c kh¡i ni»m cõa LΣ;Φ, – n¸u Q 2 Φ th¼ ≥n r:C và ≤n r:C là c¡c kh¡i ni»m cõa LΣ;Φ, − − – n¸u fQ; Ig ⊆ Φ th¼ ≥n r :C và ≤n r :C là c¡c kh¡i ni»m cõa LΣ;Φ, – n¸u U 2 Φ th¼ U là mët vai trá đối tượng cõa LΣ;Φ, – n¸u Self 2 Φ th¼ 9r:Self là mët kh¡i ni»m cõa LΣ;Φ.  I I Định nghĩa 1.5 (Ngú nghĩa cõa LΣ;Φ). Mët di¹n dịch trong LΣ;Φ là mët bë I =h∆ ; · i, trong đó ∆I là mët tªp kh¡c réng được gọi là mi·n cõa I và ·I là mët ¡nh x¤ được gọi là hàm di¹n dịch cõa I cho ph²p ¡nh x¤ méi c¡ thº a 2 ΣI thành mët ph¦n I I I I tû a 2 ∆ , méi t¶n kh¡i ni»m A 2 ΣC thành mët tªp A ⊆ ∆ , méi thuëc t½nh I I A 2 ΣA n ΣC thành mët hàm tøng ph¦n A : ∆ ! range(A), méi t¶n vai trá đối I I I tượng r 2 ΣoR thành mët quan h» hai ngôi r ⊆ ∆ × ∆ và méi vai trá dú li»u I I I σ 2 ΣdR thành mët quan h» hai ngôi σ ⊆ ∆ × range(σ). Hàm di¹n dịch · được mở rëng cho c¡c vai trá đối tượng phùc và c¡c kh¡i ni»m phùc như trong H¼nh 1.1, trong đó #Γ ký hi»u cho lực lượng cõa tªp Γ.  (R ◦ S)I = RI ◦ SI (R∗)I = (RI )∗ (C?)I = fhx; xij CI (x)g (R t S)I = RI [ SI (R−)I = (RI )−1 "I = fhx; xij x 2 ∆I g (C u D)I = CI \ DI (C t D)I = CI [ DI fagI = faI g U I = ∆I × ∆I (A ≤ d)I = fx 2 ∆I j AI (x) x¡c định và AI (x) ≤ dg >I = ∆I ?I = ; (A ≥ d)I = fx 2 ∆I j AI (x) x¡c định và AI (x) ≥ dg (:C)I = ∆I n CI (A = d)I = fx 2 ∆I j AI (x) = dg (A 6= d)I = (:(A = d))I (A d)I = ((A ≥ d) u (A 6= d))I (8R:C)I = fx 2 ∆I j 8y [RI (x; y) ) CI (y)]g (9r:Self)I = fx 2 ∆I j rI (x; x)g (9R:C)I = fx 2 ∆I j 9y [RI (x; y) ^ CI (y)]g (9σ:fdg)I = fx 2 ∆I j σI (x; d)g (≥n R:C)I = fx 2 ∆I j #fy j RI (x; y) ^ CI (y)g ≥ ng (≥n R)I = (≥n R:>)I (≤n R:C)I = fx 2 ∆I j #fy j RI (x; y) ^ CI (y)g ≤ ng (≤n R)I = (≤n R:>)I H¼nh 1.1: Di¹n dịch cõa c¡c vai trá phùc và kh¡i ni»m phùc 1.3. C¡c d¤ng chu©n 1.3.1. D¤ng chu©n phõ định cõa kh¡i ni»m Kh¡i ni»m C được gọi là ở d¤ng chu©n phõ định n¸u to¡n tû phõ định ch¿ xu§t hi»n trước c¡c t¶n kh¡i ni»m có trong C. 5
8. 1.3.2. D¤ng chu©n lưu trú cõa kh¡i ni»m D¤ng chu©n lưu trú kh¡i ni»m được x¥y dựng dựa tr¶n d¤ng chu©n phõ định và tªp hñp. Kh¡i ni»m ở d¤ng này được biºu di¹n dưới d¤ng tªp hñp cõa c¡c kh¡i ni»m con. 1.3.3. D¤ng chu©n nghịch đ£o cõa vai trá Vai trá đối tượng R được gọi ở d¤ng chu©n nghịch đảo n¸u t¤o tû nghịch đảo ch¿ ¡p dụng cho c¡c t¶n vai trá đèi tượng có trong R (không x²t đến vai trá U). ± − Đặt ΣoR = ΣoR [ fr j r 2 ΣoRg. Mët vai trá đối tượng cơ b£n là mët ph¦n tû ± thuëc ΣoR (tương ùng, ΣoR) n¸u ngôn ngú được xem x²t cho ph²p vai trá nghịch đảo (tương ùng, không cho ph²p vai trá nghịch đảo). 1.4. Cơ sở tri thùc trong logic mô t£ 1.4.1. Bë ti¶n đề vai trá Định nghĩa 1.6 (Ti¶n đề vai trá). Mët ti¶n đề bao hàm vai trá trong ngôn ngú LΣ;Φ là mët biºu thùc có d¤ng " v r hoặc R1 ◦ R2 ◦ · · · ◦ Rk v r, trong đó k ≥ 1, r 2 ΣoR và R1;R2;:::;Rk là c¡c vai trá đối tượng cơ b£n cõa LΣ;Φ kh¡c với vai trá phê qu¡t U. Mët kh¯ng định vai trá trong ngôn ngú LΣ;Φ là mët biºu thùc có d¤ng Ref(r), Irr(r), Sym(r), Tra(r) hoặc Dis(R; S), trong đó r 2 ΣoR và R; S là c¡c vai trá đối tượng cõa LΣ;Φ kh¡c với vai trá phê qu¡t U. Mët ti¶n đề vai trá trong ngôn ngú LΣ;Φ là mët ti¶n đề bao hàm vai trá hoặc mët kh¯ng định vai trá trong LΣ;Φ.  Định nghĩa 1.7 (Bë ti¶n đề vai trá). Bë ti¶n đề vai trá (RBox) trong ngôn ngú LΣ;Φ là mët tªp húu h¤n c¡c ti¶n đề vai trá trong LΣ;Φ.  1.4.2. Bë ti¶n đề thuªt ngú Định nghĩa 1.8 (Ti¶n đề thuªt ngú). Mët ti¶n đề bao hàm kh¡i ni»m têng qu¡t trong ngôn ngú LΣ;Φ là mët biºu thùc có d¤ng C v D, trong đó C và D là c¡c kh¡i ni»m cõa LΣ;Φ. Mët ti¶n đề tương đương kh¡i ni»m trong ngôn ngú LΣ;Φ là mët biºu thùc có d¤ng C ≡ D, trong đó C và D là c¡c kh¡i ni»m cõa LΣ;Φ. Mët ti¶n đề thuªt ngú trong ngôn ngú LΣ;Φ là mët ti¶n đề bao hàm kh¡i ni»m têng qu¡t hoặc mët ti¶n đề tương đương kh¡i ni»m trong LΣ;Φ.  Định nghĩa 1.9 (Bë ti¶n đề thuªt ngú). Bë ti¶n đề thuªt ngú (TBox) trong ngôn ngú LΣ;Φ là mët tªp húu h¤n c¡c ti¶n đề thuªt ngú trong LΣ;Φ.  1.4.3. Bë kh¯ng định c¡ thº Định nghĩa 1.10 (Kh¯ng định c¡ thº). Mët kh¯ng định c¡ thº trong ngôn ngú LΣ;Φ là mët biºu thùc có d¤ng C(a), R(a; b), :R(a; b), a = b, a 6= b, trong đó C là mët kh¡i ni»m và R là mët vai trá đối tượng cõa LΣ;Φ.  Định nghĩa 1.11 (Bë kh¯ng định c¡ thº). Bë kh¯ng định c¡ thº (ABox) trong ngôn ngú LΣ;Φ là mët tªp húu h¤n c¡c kh¯ng định c¡ thº trong LΣ;Φ.  1.4.4. Cơ sở tri thùc và mô h¼nh cõa cơ sở tri thùc Định nghĩa 1.12 (Cơ sở tri thùc). Mët cơ sở tri thùc trong ngôn ngú LΣ;Φ là mët bë ba KB = hR; T ; Ai, trong đó R là mët RBox, T là mët TBox và A là mët ABox trong LΣ;Φ.  6
9. Định nghĩa 1.13 (Mô h¼nh). Mët di¹n dịch I là mët mô h¼nh cõa RBox R (tương ùng, TBox T , ABox A), ký hi»u là I j= R (tương ùng, I j= T , I j= A), n¸u I thỏa m¢n t§t c£ c¡c ti¶n đề vai trá trong R (tương ùng, ti¶n đề thuªt ngú trong T , kh¯ng định c¡ thº trong A). Mët di¹n dịch I là mët mô h¼nh cõa cơ sở tri thùc KB = hR; T ; Ai, ký hi»u là I j= KB, n¸u nó là mô h¼nh cõa c£ R, T và A.  V½ dụ 1.1. V½ dụ sau đây là c¡c cơ sở tri thùc đề cªp v· c¡c §n ph©m khoa học: Φ = fI; O; N ; Qg; ΣI = fP1; P2; P3; P4; P5; P6g; ΣC = fPub; Awarded; UsefulPub;Adg; ΣdA = ΣC; ΣnA = fYearg; ΣoR = fcites; cited_byg; ΣdR = ;; R = fcites − v cited_by; cited_by − v cites; Irr(cites)g; T = f> v Pub; UsefulPub ≡ 9cited_by:>g; 0 A0 = fAwarded(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)g; 0 A0 = A0 [ f(:9cited_by:>)(P1); (8cited_by:fP2; P3; P4g)(P5)g: 0 0 Lúc đó KB0 = hR; T ; A0i và KB0 = hR; T ; A0i là c¡c cơ sở tri thùc trong LΣ;Φ. 0 Ti¶n đề > v Pub để ch¿ ra r¬ng mi·n cõa b§t kỳ mô h¼nh nào cõa KB0 hoặc KB0 đều ch¿ gồm c¡c §n ph©m khoa học. 1.5. Suy luªn trong logic mô t£ Có nhi·u bài to¡n suy luªn được đặt ra trong c¡c h» thèng biºu di¹n tri thùc dựa tr¶n logic mô t£. Để gi£i quy¸t c¡c bài to¡n suy luªn, người ta sû dụng hai thuªt đó là: thuªt to¡n bao hàm theo c§u trúc và thuªt to¡n tableaux. Thuªt to¡n bao hàm theo tỏ ra hi»u qu£ đối với c¡c ngôn ngú logic mô t£ đơn gi£n như FL0, FL?, ALN , cán thuªt to¡n tableaux gi£i quy¸t c¡c bài to¡n suy luªn với lớp ngôn ngú logic mô t£ rëng hơn như ALC [11], ALCI [12], ALCIQ [12], SHIQ [13],. . . Tiºu k¸t Chương 1 Trong chương này, luªn ¡n đã giới thi»u kh¡i qu¡t v· logic mô t£, kh£ n«ng biºu di¹n tri thùc cõa c¡c logic mô t£. Thông qua cú ph¡p và ngú nghĩa cõa logic mô t£, luªn ¡n đã tr¼nh bày v· cơ sở tri thùc, mô h¼nh cõa cơ sở tri thùc trong logic mô t£ và nhúng v§n đề cơ b£n v· suy luªn trong logic mô t£. Ngoài vi»c tr¼nh bày ngôn ngú logic mô t£ mët c¡ch têng qu¡t dựa tr¶n logic ALCreg với c¡c đặc trưng mở rëng I (vai trá nghịch đảo), O (định danh), F (t½nh ch§t hàm), N (h¤n ch¸ sè lượng không định t½nh), Q (h¤n ch¸ sè lượng định t½nh), U (vai trá phê qu¡t), Self (t½nh ph£n x¤ cục bë cõa vai trá), luªn ¡n cán xem x²t c¡c thuëc t½nh như là c¡c thành ph¦n cơ b£n cõa ngôn ngú, bao gồm thuëc t½nh rời r¤c và thuëc t½nh sè. C¡ch ti¸p cªn này phù hñp đối với c¡c h» thèng thông tin dựa tr¶n logic mô t£ thường có trong thực t¸. 7
10. Chương 2. MÆ PHÄNG HAI CHIỀU TRONG LOGIC MÆ TẢ VÀ TÍNH BẤT BIẾN 2.1. Giới thi»u Mô phỏng hai chi·u được nghi¶n cùu trong logic h¼nh th¡i (modal logic) [2], [17]. Mô phỏng hai chi·u là mët quan h» hai ngôi cho ph²p đặc t£ t½nh tương tự giúa hai tr¤ng th¡i cũng như t½nh tương tự giúa c¡c mô h¼nh Kripke. Divroodi và Nguyen đã nghi¶n cùu mô phỏng hai chi·u trong mët sè logic mô t£ cụ thº [6]. 2.2. Mô phỏng hai chi·u 2.2.1. Kh¡i ni»m Định nghĩa 2.1 (Mô phỏng hai chi·u). Cho Σ và Σy là c¡c bë ký tự logic mô t£ sao cho Σy ⊆ Σ, Φ và Φy là tªp c¡c đặc trưng cõa logic mô t£ sao cho Φy ⊆ Φ, I và I0 là 0 c¡c di¹n dịch trong LΣ;Φ. Mët LΣy;Φy -mô phỏng hai chi·u giúa I và I là mët quan h» I I0 y y y y hai ngôi Z ⊆ ∆ ×∆ thỏa c¡c điều ki»n sau với mọi a 2 ΣI , A 2 ΣC, B 2 ΣA nΣC, y y I 0 0 I0 r 2 ΣoR, σ 2 ΣdR, d 2 range(σ), x; y 2 ∆ , x ; y 2 ∆ : 0 Z(aI; aI ) (2.1) 0 Z(x; x0) ) [AI(x) , AI (x0)] (2.2) 0 Z(x; x0) ) [BI(x) = BI (x0) hoặc c£ hai đều không x¡c định] (2.3) 0 0 [Z(x; x0) ^ rI(x; y)] ) 9y0 2 ∆I j [Z(y; y0) ^ rI (x0; y0)] (2.4) 0 [Z(x; x0) ^ rI (x0; y0)] ) 9y 2 ∆I j [Z(y; y0) ^ rI(x; y)] (2.5) 0 Z(x; x0) ) [σI(x; d) , σI (x0; d)]; (2.6) n¸u I 2 Φy th¼ 0 0 [Z(x; x0) ^ rI(y; x)] ) 9y0 2 ∆I j [Z(y; y0) ^ rI (y0; x0)] (2.7) 0 [Z(x; x0) ^ rI (y0; x0)] ) 9y 2 ∆I j [Z(y; y0) ^ rI(y; x)]; (2.8) n¸u O 2 Φy th¼ 0 Z(x; x0) ) [x = aI , x0 = aI ]; (2.9) n¸u N 2 Φy th¼ 0 0 Z(x; x0) ) #fy 2 ∆I j rI(x; y)g = #fy0 2 ∆I j rI (x0; y0)g; (2.10) n¸u fN ; Ig ⊆ Φy th¼ 0 0 Z(x; x0) ) #fy 2 ∆I j rI(y; x)g = #fy0 2 ∆I j rI (y0; x0)g; (2.11) n¸u F 2 Φy th¼ Z(x; x0) ) [#fy 2 ∆I j rI(x; y)g ≤ 1 , #fy0 2 ∆I0 j rI0 (x0; y0)g ≤ 1]; (2.12) 8
11. n¸u fF; Ig ⊆ Φy th¼ Z(x; x0) ) [#fy 2 ∆I j rI(y; x)g ≤ 1 , #fy0 2 ∆I0 j rI0 (y0; x0)g ≤ 1]; (2.13) n¸u Q 2 Φy th¼ 0 y n¸u Z(x; x ) thỏa m¢n th¼ với mọi r 2 ΣoR, tồn t¤i mët song ¡nh 0 0 (2.14) h : fy 2 ∆I j rI(x; y)g ! fy0 2 ∆I j rI (x0; y0)g sao cho h ⊆ Z, n¸u fQ; Ig ⊆ Φy th¼ 0 y n¸u Z(x; x ) thỏa m¢n th¼ với mọi r 2 ΣoR, tồn t¤i mët song ¡nh 0 0 (2.15) h : fy 2 ∆I j rI(y; x)g ! fy0 2 ∆I j rI (y0; x0)g sao cho h ⊆ Z, n¸u U 2 Φy th¼ 0 8x 2 ∆I; 9x0 2 ∆I ;Z(x; x0) (2.16) 0 8x0 2 ∆I ; 9x 2 ∆I;Z(x; x0); (2.17) n¸u Self 2 Φy th¼ 0 Z(x; x0) ) [rI(x; x) , rI (x0; x0)]; (2.18) trong đó #Γ ký hi»u cho lực lượng cõa tªp hñp Γ.  Bê đề 2.1. I 1. Quan h» fhx; xij x 2 ∆ g là mët LΣy;Φy -mô phỏng hai chi·u giúa I và I. 0 −1 2. N¸u Z là mët LΣy;Φy -mô phỏng hai chi·u giúa I và I th¼ Z cũng là mët 0 LΣy;Φy -mô phỏng hai chi·u giúa I và I. 3. N¸u Z1 là mët LΣy;Φy -mô phỏng hai chi·u giúa I0 và I1, Z2 là mët LΣy;Φy -mô phỏng hai chi·u giúa I1 và I2 th¼ Z1 ◦ Z2 là mët LΣy;Φy -mô phỏng hai chi·u giúa I0 và I2. 0 S 4. N¸u Z là mët tªp c¡c LΣy;Φy -mô phỏng hai chi·u giúa I và I th¼ Z là mët 0 LΣy;Φy -mô phỏng hai chi·u giúa I và I .  2.2.2. Quan h» tương tự hai chi·u và quan h» tương đương 0 Định nghĩa 2.2. Cho I và I là c¡c di¹n dịch trong ngôn ngú LΣ;Φ. Ta nói r¬ng 0 ILΣy;Φy -tương tự hai chi·u với I n¸u tồn t¤i mët LΣy;Φy -mô phỏng hai chi·u giúa 0 I và I .  0 I Định nghĩa 2.3. Cho I và I là c¡c di¹n dịch trong ngôn ngú LΣ;Φ, x 2 ∆ và 0 I0 0 x 2 ∆ . Ta nói r¬ng x LΣy;Φy -tương tự hai chi·u với x n¸u tồn t¤i mët LΣy;Φy -mô 0 0 phỏng hai chi·u giúa I và I sao cho Z(x; x ) thỏa m¢n.  0 I Định nghĩa 2.4. Cho I và I là c¡c di¹n dịch trong ngôn ngú LΣ;Φ, x 2 ∆ và 0 I0 0 x 2 ∆ . Ta nói r¬ng x LΣy;Φy -tương đương với x n¸u với mọi kh¡i ni»m C cõa LΣy;Φy , I 0 I0 x 2 C khi và ch¿ khi x 2 C .  9
12. 2.3. T½nh b§t bi¸n đối với mô phỏng hai chi·u 2.3.1. Quan h» giúa mô phỏng hai chi·u với c¡c kh¡i ni»m và vai trá 0 Bê đề 2.2. Cho I và I là c¡c di¹n dịch trong ngôn ngú LΣ;Φ, Z là mët LΣy;Φy -mô 0 phỏng hai chi·u giúa I và I . Lúc đó, với mọi kh¡i ni»m C cõa LΣy;Φy , mọi vai trá I 0 0 I0 y đối tượng R cõa LΣy;Φy , mọi đối tượng x; y 2 ∆ , x ; y 2 ∆ và mọi c¡ thº a 2 ΣI , c¡c điều ki»n sau s³ được thỏa m¢n: 0 Z(x; x0) ) [CI(x) , CI (x0)] (2.19) 0 0 [Z(x; x0) ^ RI(x; y)] ) 9y0 2 ∆I j [Z(y; y0) ^ RI (x0; y0)] (2.20) 0 [Z(x; x0) ^ RI (x0; y0)] ) 9y 2 ∆I j [Z(y; y0) ^ RI(x; y)]; (2.21) n¸u O 2 Φy th¼: 0 I I I0 0 I0 Z(x; x ) ) [R (x; a ) , R (x ; a )]:  (2.22) 2.3.2. T½nh b§t bi¸n cõa kh¡i ni»m Định nghĩa 2.5 (Kh¡i ni»m b§t bi¸n). Mët kh¡i ni»m C được gọi là b§t bi¸n đối với 0 I 0 I0 LΣy;Φy -mô phỏng hai chi·u n¸u Z(x; x ) thỏa m¢n th¼ x 2 C khi và ch¿ khi x 2 C 0 với mọi di¹n dịch I, I trong ngôn ngú LΣ;Φ và với mọi LΣy;Φy -mô phỏng hai chi·u Z 0 y y giúa I và I , trong đó Σ ⊆ Σ, Φ ⊆ Φ.  Định lý 2.1. T§t c£ c¡c kh¡i ni»m cõa LΣy;Φy đều b§t bi¸n đối với LΣy;Φy -mô phỏng hai chi·u.  Định lý này cho ph²p mô h¼nh hóa t½nh không ph¥n bi»t được cõa c¡c đối tượng thông qua ngôn ngú con LΣy;Φy . T½nh không ph¥n bi»t cõa c¡c đối tượng là mët trong nhúng đặc trưng cơ b£n trong qu¡ tr¼nh ph¥n lớp dú li»u. 2.3.3. T½nh b§t bi¸n cõa cơ sở tri thùc Định nghĩa 2.6. Mët TBox T (tương ùng, ABox A) trong LΣy;Φy được gọi là b§t 0 bi¸n đối với LΣy;Φy -mô phỏng hai chi·u n¸u với mọi di¹n dịch I và I trong LΣ;Φ tồn 0 t¤i mët LΣy;Φy -mô phỏng hai chi·u giúa I và I sao cho I là mô h¼nh cõa T (tương 0 ùng, A) khi và ch¿ khi I là mô h¼nh cõa T (tương ùng, A).  y H» qu£ 2.1. N¸u U 2 Φ th¼ t§t c£ c¡c TBox trong LΣy;Φy đều b§t bi¸n đối với LΣy;Φy -mô phỏng hai chi·u.  Mët di¹n dịch I trong LΣ;Φ được gọi là k¸t nèi đối tượng được đối với LΣy;Φy n¸u I y I với mọi đối tượng x 2 ∆ tồn t¤i c¡ thº a 2 ΣI , c¡c đối tượng x0; x1; : : : ; xk 2 ∆ I và c¡c vai trá đối tượng cơ b£n R1;R2;:::;Rk cõa LΣy;Φy với k ≥ 0 sao cho x0 = a , I xk = x và Ri (xi−1; xi) thỏa m¢n với mọi 1 ≤ i ≤ k [6]. 0 Định lý 2.2. Cho T là mët TBox trong LΣy;Φy , I và I là c¡c di¹n dịch trong LΣ;Φ thỏa điều ki»n k¸t nèi đối tượng được đối với LΣy;Φy sao cho tồn t¤i mët LΣy;Φy -mô phỏng hai chi·u giúa I và I0. Lúc đó I là mô h¼nh cõa T khi và ch¿ khi I0 là mô h¼nh cõa T .  10
13. y Định lý 2.3. Cho A là mët ABox trong LΣy;Φy . N¸u O 2 Φ hoặc A ch¿ chùa c¡c kh¯ng định d¤ng C(a) th¼ A b§t bi¸n đối với LΣy;Φy -mô phỏng hai chi·u.  H» qu£ 2.2. Cho cơ sở tri thùc KB = hR; T ; Ai trong LΣy;Φy sao cho R = ; và gi£ thi¸t O 2 Φy hoặc A ch¿ chùa c¡c kh¯ng định có d¤ng C(a), I và I0 là c¡c di¹n dịch k¸t nèi đối tượng được trong LΣy;Φy sao cho tồn t¤i mët LΣy;Φy -mô phỏng hai chi·u 0 0 giúa I và I . Lúc đó I là mô h¼nh cõa KB khi và ch¿ khi I là mô h¼nh cõa KB.  2.4. T½nh ch§t Hennessy-Milner đối với mô phỏng hai chi·u Định nghĩa 2.7. Mët di¹n dịch I trong LΣ;Φ được gọi là ph¥n nh¡nh húu h¤n (hay I y húu h¤n £nh) đối với LΣy;Φy n¸u với mọi x 2 ∆ và với mọi vai trá r 2 ΣoR th¼: • tªp fy 2 ∆I j rI(x; y)g là húu h¤n, y I I • n¸u I 2 Φ th¼ tªp fy 2 ∆ j r (y; x)g là húu h¤n.  Định lý 2.4 (T½nh ch§t Hennessy-Milner). Cho Σ và Σy là c¡c bë ký tự logic mô t£ sao cho Σy ⊆ Σ, Φ và Φy là tªp c¡c đặc trưng cõa logic mô t£ sao cho Φy ⊆ Φ, I và 0 I là c¡c di¹n dịch trong LΣ;Φ thỏa m¢n điều ki»n ph¥n nh¡nh húu h¤n đối với LΣy;Φy , y I I0 y sao cho với mọi a 2 ΣI , a LΣy;Φy -tương đương với a . Gi£ thi¸t r¬ng U 62 Φ hoặc y I 0 I0 ΣI 6= ;. Lúc đó, x 2 ∆ LΣy;Φy -tương đương với x 2 ∆ khi và ch¿ khi tồn t¤i mët 0 0 LΣy;Φy -mô phỏng hai chi·u Z giúa I và I sao cho Z(x; x ) thỏa m¢n.  H» qu£ 2.3. Cho Σ và Σy là c¡c bë ký tự logic mô t£ sao cho Σy ⊆ Σ, Φ và Φy là tªp c¡c đặc trưng cõa logic mô t£ sao cho Φy ⊆ Φ, I và I0 là c¡c di¹n dịch trong y LΣ;Φ thỏa điều ki»n ph¥n nh¡nh húu h¤n đối với LΣy;Φy . Gi£ thi¸t r¬ng ΣI 6= ; và với y I I0 0 I I0 mọi a 2 ΣI , a LΣy;Φy -tương đương với a . Lúc đó, quan h» fhx; x i 2 ∆ × ∆ j x 0 0 LΣy;Φy -tương đương với x g là mët LΣy;Φy -mô phỏng hai chi·u giúa I và I .  2.5. Tự mô phỏng hai chi·u Định nghĩa 2.8 (Tự mô phỏng hai chi·u). Cho I là mët di¹n dịch trong LΣ;Φ. Mët LΣy;Φy -tự mô phỏng hai chi·u cõa I là mët LΣy;Φy -mô phỏng hai chi·u giúa I và ch½nh nó. Mët LΣy;Φy -tự mô phỏng hai chi·u Z cõa I được gọi là lớn nh§t n¸u với mọi 0 0 LΣy;Φy -tự mô phỏng hai chi·u Z cõa I th¼ Z ⊆ Z.  Cho I là mët di¹n dịch trong LΣ;Φ, chúng ta ký hi»u LΣy;Φy -tự mô phỏng hai chi·u I lớn nh§t cõa I là ∼Σy;Φy;I, và ký hi»u quan h» hai ngôi ≡Σy;Φy;I tr¶n ∆ là quan h» 0 0 thỏa m¢n t½nh ch§t x ≡Σy;Φy;I x khi và ch¿ khi x LΣy;Φy -tương đương với x . Định lý 2.5. Cho Σ và Σy là c¡c bë ký tự cõa logic mô t£ sao cho Σy ⊆ Σ, Φ và Φy y là tªp c¡c đặc trưng cõa logic mô t£ sao cho Φ ⊆ Φ, I là mët di¹n dịch trong LΣ;Φ. Lúc đó: 1. LΣy;Φy -tự mô phỏng hai chi·u lớn nh§t cõa I tồn t¤i và nó là mët quan h» tương đương, 2. n¸u I là mët ph¥n nh¡nh húu h¤n đối với LΣy;Φy th¼ quan h» ≡Σy;Φy;I là mët LΣy;Φy -tự mô phỏng hai chi·u lớn nh§t cõa I (nghĩa là, quan h» ≡Σy;Φy;I và ∼Σy;Φy;I trùng khớp nhau).  11
14. Chúng ta nói r¬ng tªp Y bị ph¥n chia bởi tªp X n¸u Y n X 6= ; và Y \ X 6= ;. Như vªy, tªp Y không bị ph¥n chia bởi tªp X n¸u hoặc Y ⊆ X hoặc Y \X = ;. Ph¥n ho¤ch Y = fY1;Y2;:::;Yng được gọi là nh§t qu¡n với tªp X n¸u với mọi 1 ≤ i ≤ n, Yi không bị ph¥n chia bởi X. Định lý 2.6. Cho Σ và Σy là c¡c bë ký tự cõa logic mô t£ sao cho Σy ⊆ Σ, Φ và Φy là tªp c¡c đặc trưng cõa logic mô t£ sao cho Φy ⊆ Φ, I là mët di¹n dịch húu h¤n trong I I LΣ;Φ và X ⊆ ∆ . Gọi Y là ph¥n ho¤ch cõa ∆ thông qua quan h» ∼Σy;Φy;I. Lúc đó: I 1. n¸u tồn t¤i kh¡i ni»m C cõa LΣy;Φy sao cho C = X th¼ ph¥n ho¤ch Y nh§t qu¡n với tªp X, 2. n¸u ph¥n ho¤ch Y nh§t qu¡n với tªp X th¼ tồn t¤i kh¡i ni»m C cõa LΣy;Φy sao I cho C = X.  Tiºu k¸t Chương 2 Thông qua ngôn ngú LΣ;Φ và ngôn ngú con LΣy;Φy , chương này đã tr¼nh bày mô phỏng hai chi·u và t½nh b§t bi¸n đối với mô phỏng hai chi·u tr¶n mët lớp c¡c logic mô t£ như đã đề cªp trong Chương 1. C¡c kh¡i ni»m, định nghĩa và c¡c định lý, bê đề cũng như c¡c h» qu£ được ph¡t triºn dựa tr¶n c¡c k¸t qu£ cõa c¡c công tr¼nh [6], [14] với lớp c¡c logic mô t£ lớn hơn. Chúng tôi cũng tr¼nh bày c¡c chùng minh cho nhúng định lý, bê đề, h» qu£ đã n¶u ra trong chương này. T½nh b§t bi¸n, đặc bi»t là t½nh b§t bi¸n cõa kh¡i ni»m là mët trong nhúng n·n t£ng cho ph²p mô h¼nh hóa t½nh không ph¥n bi»t được cõa c¡c đối tượng thông qua ngôn ngú con. T½nh không ph¥n bi»t cõa c¡c đối tượng là mët trong nhúng đặc trưng cơ b£n trong qu¡ tr¼nh x¥y dựng c¡c kỹ thuªt ph¥n lớp dú li»u. Điều này có nghĩa là chúng ta có thº sû dụng ngôn ngú con cho c¡c bài to¡n học m¡y trong logic mô t£ b¬ng c¡ch sû dụng mô phỏng hai chi·u. 12
15. Chương 3. HÅC KHÁI NIỆM CHO HỆ THÈNG THÆNG TIN TRONG LOGIC MÆ TẢ 3.1. H» thèng thông tin 3.1.1. H» thèng thông tin truy·n thèng Mët c¡ch h¼nh thùc, h» thèng thông tin được định nghĩa như sau [15]: Định nghĩa 3.1. H» thèng thông tin là mët bë IS = hU; A; V; ρi, trong đó: • U là mët tªp húu h¤n, kh¡c réng, được gọi là tªp vũ trụ c¡c đối tượng, • A là mët tªp húu h¤n, kh¡c réng, được gọi là tªp thuëc t½nh, S • V = Va, trong đó Va là tªp kh¡c réng c¡c gi¡ trị cõa thuëc t½nh a 2 A và Va a2A được gọi là mi·n gi¡ trị cõa a, • ρ:U×A!V là mët hàm thông tin, sao cho ρ(u; a)2Va với mọi u2U và a2A. H¤n ch¸ cõa h» thèng thông tin truy·n thèng là không thº hi»n được mèi quan h» giúa c¡c đối tượng. 3.1.2. H» thèng thông tin dựa tr¶n logic mô t£ Định nghĩa 3.2 (Cơ sở tri thùc không váng). Cơ sở tri thùc không váng trong ngôn ngú LΣ;Φ là mët bë KB = hR; T ; Ai, trong đó: •R là mët danh s¡ch húu h¤n ( 1; 2; : : : ; m). Méi i là mët ti¶n đề vai trá có d¤ng r ≡ R, trong đó R là mët vai trá đèi tượng cõa LΣ;Φ và r 2 ΣoR là mët t¶n vai trá đối tượng không có mặt trong R, A và 1; 2; : : : ; i−1, •T là mët danh s¡ch húu h¤n ('1;'2;:::;'n). Méi 'i là mët ti¶n đề thuªt ngú có d¤ng A ≡ C, trong đó C là mët kh¡i ni»m cõa LΣ;Φ và A 2 ΣC là mët t¶n kh¡i ni»m không có mặt trong C, A và '1;'2;:::;'i−1, •A là mët tªp húu h¤n chùa c¡c kh¯ng định c¡ thº.  Cho cơ sở tri thùc không váng KB = hR; T ; Ai. Mët mô h¼nh I cõa KB trong LΣ;Φ được gọi là mô h¼nh chu©n n¸u I thỏa m¢n c¡c điều ki»n sau: I • ∆ = ΣI (nghĩa là, mi·n cõa I chùa t§t c£ c¡c t¶n c¡ thº cõa Σ), I • n¸u A 2 ΣC là mët kh¡i ni»m nguy¶n thõy trong KB th¼ A = fa j A(a) 2 Ag, I I • n¸u B 2 ΣA n ΣC th¼ B : ∆ ! range(B) là mët hàm tøng ph¦n sao cho BI(aI) = c n¸u (B(a) = c) 2 A, I • n¸u r 2ΣoR là mët vai trá đối tượng nguy¶n thõy trong KB th¼ r =fha; bijr(a; b)2Ag, I • n¸u σ 2 ΣdR th¼ σ = fha; dij σ(a; d) 2 Ag, 13
16. • n¸u r ≡ R là mët định nghĩa vai trá đối tượng trong R th¼ rI = RI, • n¸u A ≡ C là mët định nghĩa kh¡i ni»m trong T th¼ AI = CI, I • n¸u A 2 ΣC mà A không có mặt trong KB th¼ A = ;, I • n¸u r 2 ΣoR mà r không xu§t hi»n trong KB th¼ r = ;. C¡c định nghĩa kh¡i ni»m và định nghĩa vai trá đối tượng ¡p dụng cho gi£ thi¸t t¶n duy nh§t và gi£ thi¸t th¸ giới đóng. Định nghĩa 3.3. Cho cơ sở tri thùc không váng KB = hR; T ; Ai. H» thèng thông tin dựa tr¶n logic mô t£ được x¡c định bởi mët cơ sở tri thùc không váng KB trong LΣ;Φ là mët mô h¼nh chu©n cõa cơ sở tri thùc đó trong LΣ;Φ. 3.2. Học kh¡i ni»m trong logic mô t£ với Ngú c£nh (3) 3.2.1. Giới thi»u bài to¡n Cho I là mët h» thèng thông tin hu§n luy»n trong LΣ;Φ. Gọi Ad 2 ΣC là mët kh¡i + − + I I ni»m đại di»n cho “thuëc t½nh quy¸t định”, E = hE ;E i với E = fa j a 2 Ad g và − I I E = fa j a 2 (:Ad )g tương ùng là tªp c¡c m¨u dương và m¨u ¥m cõa Ad trong I. Gi£ sû r¬ng Ad có thº được biºu di¹n bởi mët kh¡i ni»m C trong ngôn ngú con y y LΣy;Φy , trong đó Σ ⊆ Σ n fAdg và Φ ⊆ Φ. Học kh¡i ni»m C dựa tr¶n c¡c thông tin + − cơ b£n I, E , E trong ngôn ngú con LΣy;Φy sao cho C thỏa m¢n c¡c điều ki»n sau: •Ij = C(a) với mọi a 2 E+, •Ij = :C(a) với mọi a 2 E−. Lưu ý r¬ng, I j= :C(a) tương đồng với I 6j= C(a). Với E = hE+;E−i, trong đó E+ là tªp chùa c¡c m¨u dương và E− là tªp chùa c¡c m¨u ¥m cho trước, ta nói r¬ng tªp Y ⊆ ∆I bị ph¥n chia bởi E n¸u tồn t¤i a 2 E+ − I I I và b 2 E sao cho fa ; b g ⊆ Y . Mët ph¥n ho¤ch Y = fY1;Y2;:::;Yng cõa ∆ được gọi là nh§t qu¡n với E n¸u với mọi 1 ≤ i ≤ n, Yi không bị ph¥n chia bởi E. Dựa tr¶n ý tưởng cõa phương ph¡p được đ· xu§t bởi Nguyen và Sza las [14], phương ph¡p học kh¡i ni»m trong luªn ¡n này cũng thực hi»n làm mịn ph¥n ho¤ch ∆I b¬ng c¡c bë chọn để đạt được ph¥n ho¤ch tương ùng với ∼Σy;Φy;I. 3.2.2. Bë chọn y y Định nghĩa 3.4. Mët bë chọn cơ b£n trong LΣ ;Φ dùng để ph¥n chia khèi Yij cõa ph¥n ho¤ch Y = fYi1 ;Yi2 ;:::;Yik g là mët kh¡i ni»m thuëc mët trong c¡c d¤ng sau: y • A, trong đó A 2 ΣC, y y • A = d, trong đó A 2 ΣA n ΣC và d 2 range(A), y •9 σ:fdg, trong đó σ 2 ΣdR và d 2 range(σ), y •9 r:Cit , trong đó r 2 ΣoR và 1 ≤ t ≤ k, − y y •9 r :Cit , n¸u I 2 Φ , r 2 ΣoR và 1 ≤ t ≤ k, y y •f ag, n¸u O 2 Φ và a 2 ΣI , 14
17. y y •≤ 1 r, n¸u F 2 Φ và r 2 ΣoR, − y y •≤ 1 r , n¸u fF; Ig ⊆ Φ và r 2 ΣoR, y y I I •≥ l r và ≤m r, n¸u N 2 Φ , r 2 ΣoR, 0 d, trong đó A 2 ΣnA, d 2 range(A) và d không ph£i là ph¦n tû lớn nh§t cõa range(A), y •9 r:>, 9r:Ci và 8r:Ci, trong đó r 2 ΣoR và 1 ≤ i ≤ n, − − − y y •9 r :>, 9r :Ci và 8r :Ci, n¸u I 2 Φ , r 2 ΣoR và 1 ≤ i ≤ n, y y I •≥ l r:Ci và ≤ m r:Ci, n¸u Q 2 Φ , r 2 ΣoR, 1 ≤ i ≤ n, 0 < l ≤ #Ci và I 0 ≤ m < #Ci , − − y y I •≥ l r :Ci và ≤ m r :Ci, n¸u fQ; Ig ⊆ Φ , r 2 ΣoR, 1 ≤ i ≤ n, 0 < l ≤ #Ci I và 0 ≤ m < #Ci .  Gọi D là tªp chùa c¡c bë chọn hi»n có. Cùng với ph¥n ho¤ch hi»n thời Y, tªp D = fD1;D2;:::;Dhg được gọi là tªp c¡c bë chọn hi»n thời. Chúng tôi định nghĩa c¡c bë chọn mở rëng để phục vụ cho qu¡ tr¼nh làm mịn được hi»u qu£ hơn. Định nghĩa 3.6 (Bë chọn mở rëng). Cho D = fD1;D2;:::;Dhg là tªp c¡c bë chọn hi»n thời. Mët bë chọn mở rëng trong LΣy;Φy để ph¥n chia mët khèi cõa ph¥n ho¤ch hi»n thời là mët kh¡i ni»m thuëc mët trong c¡c d¤ng sau: y •9 r:Du và 8r:Du, trong đó r 2 ΣoR và Du 2 D, − − y y •9 r :Du và 8r :Du, n¸u I 2 Φ , r 2 ΣoR và Du 2 D, 15
18. y y I •≥ l r:Du và ≤ m r:Du, n¸u Q 2 Φ , r 2 ΣoR, Du 2 D, 0 , ?, A, A = d, A 6= d, A > d, A ≥ d, A hoặc ?, • 1 n¸u C có d¤ng A, A = d, A 6= d, A > d, A ≥ d, A E∆I (Y=X) = #XY #XY #XY #XY (3.1) − log − log ; n¸u ngược l¤i, :> #Y 2 #Y #Y 2 #Y trong đó XY đại di»n cho tªp X \ Y và XY đại di»n cho tªp X \ Y .  16
19. Định nghĩa 3.10 (Gia lượng thông tin). Gia lượng thông tin cõa bë chọn D trong vi»c ph¥n chia tªp Y đối với tªp X trong ∆I cõa h» thèng thông tin I, ký hi»u là IG∆I (Y=X; D), được x¡c định như sau: ! #DIY #DIY I I IG I (Y=X; D)=E I (Y=X) − E I (D Y=X)+ E I (D Y=X) (3.2) ∆ ∆ #Y ∆ #Y ∆ I I I I trong đó D Y đại di»n cho tªp D \ Y và D Y đại di»n cho tªp D \ Y .  I Trong ngú c£nh ∆ và X đã rã ràng, chúng ta vi¸t E(Y ) thay cho E∆I (Y=X) và IG(Y; D) thay cho IG∆I (Y=X; D). 3.2.5. Thuªt to¡n học kh¡i ni»m trong logic mô t£ với Ngú c£nh (3) Phương ph¡p học kh¡i ni»m cho h» thèng thông tin trong logic mô t£ được mô t£ như trong Thuªt to¡n 3.1, trong thuªt to¡n này có sû dụng hàm chooseBlockSelector để quy¸t định khèi và bë chọn c¦n ph¥n chia trước. Function chooseBlockSelector Input : Y, D Output: Yij ;Sij sao cho IG(Yij ;Sij ) cực đại, trong đó Yij 2 Y và Sij 2 D 1 BS := ;; 2 foreach Yij 2 Y do 3 foreach Du 2 D do 4 T½nh IG(Yij ;Du); 5 S := arg maxfIG(Yij ;Du)g; Du2D 6 L§y Sij 2 S sao cho Sij là kh¡i ni»m đơn gi£n nh§t; 7 BS := BS [ f Yij ;Sij g; 8 Chọn Yi ;Si 2 BS sao cho IG(Yi ;Si ) là cực đại; j j j j 9 return Yij ;Sij ; 3.3. V½ dụ minh họa C¡c v½ dụ sau đây ch¿ ra mët bùc tranh kh¡ đầy đủ v· hi»u qu£ cõa c¡c bë chọn đơn gi£n và bë chọn mở rëng đ¢ đ· cªp trong Mục 3.2.2. Đầu ti¶n chúng ta x²t v½ dụ v· mët cơ sở tri thùc và h» thèng thông tin tương ùng với cơ sở tri thùc đó. V½ dụ 3.1. Cho cơ sở tri thùc KB = hR; T ; Aitrong LΣ;Φ, với Σ = ΣI [ΣdA [ΣnA [ ΣoR [ ΣdR và Φ = fIg, trong đó: ΣI = fAva; Britt; Colin; Dave; Ella; F lor; Gigi; Harryg; ΣC = fHuman; Male; F emale; Nephew; Nieceg; ΣdA = ΣC; ΣnA = ;; ΣoR = fhasChild; hasP arent; hasSiblingg; ΣdR = ;: R = fhasP arent ≡ hasChild−; Sym(hasSibling)g; T = fHuman ≡ >; Niece ≡ F emale u 9hasChild−:(9hasSibling:>); Nephew ≡ Male u 9hasChild−:(9hasSibling:>)g; 17
20. Thuªt to¡n 3.1: Học kh¡i ni»m cho h» thèng thông tin trong logic mô t£ Input : I, Σy, Φy, E = hE−;E+i Output: Kh¡i ni»m C sao cho: •Ij = C(a) với mọi a 2 E+, và • I 6j= C(a) với mọi a 2 E−. I 1 n := 1; Y1 := ∆ ; C1 := >; Y := fY1g; D = ;; 2 T¤o và th¶m c¡c bë chọn vào D; /* Định nghĩa 3.4, 3.5 và/hoặc 3.6 */ 3 while (Y không nh§t qu¡n với E) do 4 Yij ;Sij := chooseBlockSelector(Y, D); I 5 if (Y không bị ph¥n chia bởi S ) then ij ij 6 break; 7 s := n + 1; t := n + 2; n := n + 2; I 8 Y := Y \ S ; C := C u S ; s ij ij s ij ij I 9 Yt := Yij \ (:Sij ) ; Ct := Cij u :Sij ; 10 if (Yij không bị ph¥n chia bởi E) then 11 LargestContainer[s] := LargestContainer[ij]; 12 LargestContainer[t] := LargestContainer[ij]; 13 else 14 if (Ys không bị ph¥n chia bởi E) then 15 LargestContainer[s] := s; 16 if (Yt không bị ph¥n chia bởi E) then 17 LargestContainer[t] := t; 18 Y := Y [ fYs;Ytg n fYij g; 19 T¤o và th¶m c¡c bë chọn vào D; /* Định nghĩa 3.4, 3.5 và/hoặc 3.6 */ 20 J := ;; C := ;; 21 if (Y nh§t qu¡n với E) then 22 foreach Yij 2 Y do + I 23 if (9a 2 E : a 2 Yij ) then 24 J := J [ fLargestContainer[ij]g ; 25 foreach l 2 J do 26 C := C [ fClg; F 27 C := C; 28 return Crs :=simplify (C); 29 else 30 return failure; A = fF emale(Ava); F emale(Britt); Male(Colin); Male(Dave); F emale(Ella); F emale(F lor); F emale(Gigi); hasChild(Ava; Dave); hasChild(Ava; Ella); Male(Harry); hasChild(Britt; F lor); hasChild(Colin; Gigi); hasChild(Colin; Harry); hasSibling(Britt; Colin); hasSibling(Colin; Britt); hasSibling(Dave; Ella); hasSibling(Ella; Dave); hasSibling(Gigi; Harry); hasSibling(Harry; Gigi)g: 18
21. H» thèng thông tin I cõa cơ sở tri thù KB có thº được x¥y dựng như sau: ∆I = fAva; Britt; Colin; Dave; Ella; F lor; Gigi; Harryg; HumanI = ∆I; AvaI = Ava; BrittI = Britt; : : : ; HarryI = Harry; F emaleI= fAva; Britt; Ella; F lor; Gigig; MaleI = fColin; Dave; Harryg; hasChildI = fhAva; Davei;hAva; Ellai;hBritt; F lori;hColin; Gigii;hColin; Harryig; hasP arentI = fhDave; Avai;hElla; Avai;hF lor; Britti;hGigi; Colini;hHarry; Colinig; hasSiblingI = fhBritt; Colini; hColin; Britti; hDave; Ellai; hElla; Davei; hGigi; Harryi; hHarry; Gigiig; − I I I I (hasSibling ) = hasSibling ; Niece = fF lor; Gigig; Nephew = fHarryg:  V½ dụ ti¸p theo ch¿ ra r¬ng sû dụng c¡c bë chọn đơn gi£n k¸t hñp với bë chọn mở rëng cho k¸t qu£ tèt hơn so với ch¿ sû dụng c¡c bë chọn đơn gi£n. V½ dụ 3.2. X²t h» thèng thông tin I như đã cho trong V½ dụ 3.1, ngôn ngú con LΣy;Φy với Σy = fF emale; hasChild; hasSiblingg và Φy = fIg, và tªp X = fF lor; Gigig (nghĩa là, E = hE+;E−ivới E+ = fF lor; Gigig và E− = fAva; Britt; Colin; Dave; Ella; Harryg). Học định nghĩa cõa tªp X. Chúng ta có thº xem X như là tªp c¡c thº hi»n cõa kh¡i ni»m Niece ≡ F emale u 9hasChild−:(9hasSibling:>) trong I. 1. Học định nghĩa cõa X trong LΣy;Φy b¬ng c¡ch sû dụng c¡c bë chọn đơn gi£n. Kh¡i ni»m k¸t qu£ học được rút gọn thành kh¡i ni»m Crs như sau: − Crs ≡ F emale u 8hasChild:? u (8hasChild :(:F emale) t 8hasSibling:?): 2. Học định nghĩa cõa X trong LΣy;Φy b¬ng c¡ch sû dụng c¡c bë chọn đơn gi£n và bë chọn mở rëng. − Kh¡i ni»m k¸t qu£ học được là Crs ≡ F emale u 9hasChild :(9hasSibling:>): Trong trường hñp thù hai, kh¡i ni»m 9hasChild−:(9hasSibling:>) là mët bë chọn mở rëng. Bë chọn này được t¤o ra b¬ng c¡ch ¡p dụng luªt thù hai trong Định nghĩa 3.6 với 9hasSibling:> là mët kh¡i ni»m có trong tªp c¡c bë chọn hi»n thời D. 3.4. K¸t qu£ thực nghi»m C¡c tªp dú li»u dùng để thû nghi»m là WebKB [16], PokerHand [3] và Family. Chúng tôi tr¼nh bày c¡c thông tin chi ti¸t như sau: • độ s¥u kh£ n«ng (Dep.) trung b¼nh (Avg.) cõa c¡c kh¡i ni»m gèc (Org.), • độ dài (Len.) trung b¼nh cõa c¡c kh¡i ni»m gèc, • độ s¥u kh£ n«ng trung b¼nh cõa c¡c kh¡i ni»m k¸t qu£ (Res.), • độ dài trung b¼nh cõa c¡c kh¡i ni»m k¸t qu£, • độ đúng đắn (Acc.), t¿ l» ch½nh x¡c (Pre.), t¿ l» bao phõ (Rec.) và độ đo F1, • độ l»ch chu©n, gi¡ trị nhỏ nh§t (Min) và gi¡ trị lớn nh§t (Max) cõa độ đúng đắn, t¿ l» ch½nh x¡c, đë bao phõ và độ đo F1. 19
22. B£ng 3.1: K¸t qu£ ước lượng tr¶n tªp dú li»u WebKB, PokerHand và Family với 100 kh¡i ni»m ng¨u nhi¶n trong logic mô t£ ALCIQ Avg. Dep. Avg. Len. Avg. Acc. Avg. Pre. Avg. Rec. Avg. F1 Res./Org. Res./Org. [Min;Max] [Min;Max] [Min;Max] [Min;Max] WebKB dataset 93.84±13.50 92.09±17.04 92.82±17.32 91.59±16.68 Bë chọn đơn gi£n 0.82/1.02 6.81/4.41 [33.69;100.0] [32.08;100.0] [23.08;100.0] [27.69;100.0] Bë chọn đơn gi£n 94.60±12.20 92.81±15.93 93.14±17.17 92.33±16.17 0.84/1.02 3.40/4.41 và mở rëng [33.69;100.0] [32.08;100.0] [23.08;100.0] [27.69;100.0] PokerHand dataset 97.17±08.61 95.96±14.99 94.95±14.40 94.66±14.64 Bë chọn đơn gi£n 1.41/2.60 37.02/15.97 [50.57;100.0] [01.67;100.0] [01.67;100.0] [01.67;100.0] Bë chọn đơn gi£n 99.44±02.15 98.68±09.08 98.06±09.58 98.18±09.14 1.23/2.60 3.47/15.97 và mở rëng [83.25;100.0] [01.67;100.0] [01.67;100.0] [01.67;100.0] Family dataset 88.50±16.65 90.60±18.57 85.66±22.36 86.09±20.10 Bë chọn đơn gi£n 2.38/3.34 78.50/18.59 [27.91;100.0] [04.55;100.0] [07.69;100.0] [08.70;100.0] Bë chọn đơn gi£n 92.79±14.35 91.99±18.40 91.75 ±19.82 90.39±19.89 2.29/3.34 10.20/18.59 và mở rëng [27.91;100.0] [04.55;100.0] [07.69;100.0] [08.70;100.0] Qua quan s¡t B£ng 3.1 và c¡c b£ng kh¡c trong luªn ¡n, chúng ta th§y rã ràng r¬ng sû dụng th¶m bë chọn mở rëng có hi»u qu£ cao hơn trong vi»c gi£m độ dài cõa kh¡i ni»m và cho k¸t qu£ ph¥n lớp tèt hơn. Chúng tôi cũng đã kiºm tra đối với c¡c kh¡i ni»m phê bi¸n/tªp đối tượng cho trước tr¶n tªp dú li»u Family và PokerHand. Tiºu k¸t Chương 3 Chương này đề xu§t thuªt to¡n học kh¡i ni»m trong logic mô t£ với Ngú c£nh (3) sû dụng mô phỏng hai chi·u. Thuªt to¡n học này cùng với nhúng chi¸n lược ph¥n ho¤ch được sû dụng đã được kiºm nghi»m tr¶n hai kh½a c¤nh lý thuy¸t và thực nghi»m. Để qu¡ tr¼nh ph¥n ho¤ch mi·n đạt hi»u qu£ cao, ngoài c¡c bë chọn cơ b£n và bë chọn đơn gi£n, c¡c bë chọn mở rëng cũng được sû dụng trong chương tr¼nh cài đặt cõa thuªt to¡n. C¡c k¸t qu£ thực nghi»m đã chùng tỏ r¬ng phương ph¡p đề xu§t có ý nghĩa và c¡c bë chọn mở rëng hé trñ r§t tèt cho qu¡ tr¼nh làm mịn ph¥n ho¤ch. 20
23. Chương 4. HÅC KHÁI NIỆM CHO CƠ SÐ TRI THỨC TRONG LOGIC MÆ TẢ 4.1. Giới thi»u C¡c bài to¡n học kh¡i ni»m trong chương này được đặt ra theo hai ngú c£nh sau: • Ngú c£nh (1): Cho L là mët logic mô t£ quy¸t định được trong LΣ;Φ có t½nh ch§t mô h¼nh nûa húu h¤n, Ad 2 ΣC là kh¡i ni»m đại di»n cho “thuëc t½nh quy¸t định” và cơ sở tri thùc KB0 = hR; T ; A0i trong logic mô t£ L không chùa Ad. Với + − + − E = hE ;E i, trong đó E và E là c¡c tªp con không giao nhau cõa ΣI sao + cho cơ sở tri thùc KB = hR; T ; Aivới A = A0 [ fAd(a) j a 2 E g [ f:Ad(a) j − a 2 E g thỏa m¢n được. Học kh¡i ni»m C như là mët định nghĩa cõa Ad trong y y ngôn ngú con LΣy;Φy , với Σ ⊆ Σ n fAdg và Φ ⊆ Φ sao cho: 1. KB j= C(a) với mọi a 2 E+, và 2. KB j= :C(a) với mọi a 2 E−. • Ngú c£nh (2): Ngú c£nh này tương tự như Ngú c£nh (1) nhưng với điều ki»n thù hai được thay th¸ b¬ng mët điều ki»n y¸u hơn: 2. KB 6j= C(a) với mọi a 2 E−. Lưu ý r¬ng, hai bài to¡n tr¶n được gi£i quy¸t theo gi£ thuy¸t th¸ giới mở. 4.2. Ph¥n ho¤ch mi·n cõa di¹n dịch Chúng tôi x¥y dựng thuªt to¡n để làm mịn ph¥n ho¤ch thông qua Hàm partition. Hàm này cũng sû dụng hàm chooseBlockSelector để quy¸t định khèi và bë chọn c¦n ph¥n chia trước. 0 V½ dụ 4.1. X²t cơ sở tri thùc KB0 và KB0 như đã cho trong V½ dụ 1.1 và di¹n dịch 0 I là mô h¼nh cõa KB và KB0 như sau: I I ∆ = fP1; P2; P3; P4; P5; P6g; x = x với x 2 fP1; P2; P3; P4; P5; P6g; I I I I Pub = ∆ ; Awarded = fP1; P4; P6g; UsefulPub = fP2; P3; P4; P5; P6g; I cites = fhP1; P2i; hP1; P3i; hP1; P4i;:::; hP4; P5i; hP4; P6ig; cited_by I = (cites I)−1; hàm tøng ph¦n Year I được đặc t£ theo tøng c¡ thº. + − + − Cho E = hE ;E i với E = fP4; P6g và E = fP1; P2; P3; P5g, ngôn ngú con y y I LΣy;Φy , trong đó Σ = fAwarded; cited_byg và Φ = ;. C¡c bước làm mịn mi·n ∆ cõa I theo Hàm partition được mô t£ như sau: I 1. Y1 := ∆ , C1 := >, Y := fY1g 2. Ph¥n chia khèi Y1 bởi Awarded chúng ta thu được: • Y2 := fP1; P4; P6g, C2 := Awarded, • Y3 := fP2; P3; P5g, C3 := :Awarded, ) Y := fY2;Y3g 21
24. Function partition - Làm mịn mi·n cõa di¹n dịch trong logic mô t£ Input : I, Σy, Φy, E = hE+;E−i I Output: Y = fYi1 ;Yi2 ;:::;Yik g là mët ph¥n ho¤ch cõa mi·n ∆ sao cho Y nh§t qu¡n với E I 1 n := 1; Y1 := ∆ ; C1 := >; Y := fY1g; D := ;; 2 T¤o và th¶m c¡c bë chọn vào D; /* Định nghĩa 3.4, 3.5 và/hoặc 3.6 */ 3 while (Y không nh§t qu¡n với E) do 4 Yij ;Sij := chooseBlockSelector(Y, D); I 5 if (Y không bị ph¥n chia bởi S ) then ij ij 6 break; 7 s := n + 1; t := n + 2; n := n + 2; I 8 Y := Y \ S ; C := C u S ; s ij ij s ij ij I 9 Yt := Yij \ (:Sij ) ; Ct := Cij u :Sij ; 10 Y := Y [ fYs;Ytg n fYij g; 11 T¤o và th¶m c¡c bë chọn vào D; /* Định nghĩa 3.4, 3.5 và/hoặc 3.6 */ 12 if (Y nh§t qu¡n với E) then 13 return Y; 14 else 15 return failure; 3. Chúng ta sû dụng bë chọn đơn gi£n nh§t 9cited_by:> để ph¥n chia Y2: • Y4 := fP4; P6g, C4 := C2 u 9cited_by:>, • Y5 := fP1g, C5 := C2 u :9cited_by:>, ) Y := fY3;Y4;Y5g Ph¥n ho¤ch đạt được là Y = fY3;Y4;Y5g nh§t qu¡n với E. 4.3. Học kh¡i ni»m trong logic mô t£ với Ngú c£nh (1) 4.3.1. Thuªt to¡n BBCL Ý tưởng ch½nh cõa thuªt to¡n BBCL để gi£i quy¸t bài to¡n này là sû dụng c¡c mô h¼nh cõa KB k¸t hñp với mô phỏng hai chi·u trong mô h¼nh đó và c¥y quy¸t định cho vi»c t¼m ki¸m kh¡i ni»m C. Thuªt to¡n này sû dụng Hàm partition được n¶u ở Mục 4.2 để làm mịn mi·n ∆I cõa di¹n dịch I là mô h¼nh cõa KB. 4.3.2. Thuªt to¡n dual-BBCL Thuªt to¡n dual-BBCL được sû dụng để học kh¡i ni»m trong logic mô t£ với Ngú c£nh (1). B¬ng c¡ch ho¡n đổi c¡c tªp E+ và E− cho nhau, sau đó ¡p dụng Thuªt to¡n 0 0 BBCL chúng ta s³ nhªn được kh¡i ni»m Crs và l§y k¸t qu£ tr£ v· là kh¡i ni»m :Crs. 4.3.3. T½nh đúng đắn cõa thuªt to¡n BBCL M»nh đề 4.1 (T½nh đúng đắn cõa thuªt to¡n BBCL). Thuªt to¡n BBCL là đúng đắn. Nghĩa là, n¸u thuªt to¡n BBCL tr£ v· mët kh¡i ni»m Crs th¼ Crs là mët lời gi£i cõa bài to¡n học kh¡i ni»m cho cơ sở tri thùc trong logic mô t£ với Ngú c£nh (1).  22
25. Thuªt to¡n 4.1: BBCL - Học kh¡i ni»m trong logic mô t£ với Ngú c£nh (1) y y + − Input : KB, Σ ⊆ Σ n fAdg, Φ ⊆ Φ, E = hE ;E i, k Output: Kh¡i ni»m C trong LΣy;Φy sao cho: • KBj= C(a) với mọi a 2 E+, và • KBj= :C(a) với mọi a 2 E−. 1 C := ;; C0 := ;; 2 while not (too hard to extend C) do 0 3 X¥y dựng mô h¼nh húu h¤n (ti¸p theo) I cõa KB hoặc I = Ijk; y y 4 Y := partition (I, Σ , Φ , E); /* ph¥n ho¤ch ∆I theo Hàm partition */ + I − I 5 foreach Yij 2 Y sao cho 9a 2 E : a 2 Yij và 8a 2 E : a 62 Yij do − 6 if (KB j= :Cij (a) với mọi a 2 E ) then 7 F if (KB 6j= (Cij v C)) then 8 C := C [ fCij g; 9 else 10 C0 := C0 [ fCij g; F + 11 if (KB j= ( C)(a) với mọi a 2 E ) then 12 go to 20; 13 while not (too hard to extend C) do 14 D := D1 u D2 u · · · u Dl, với D1;D2;:::;Dl được chọn ng¨u nhi¶n tø C0; − F 15 if (KB j= :D(a) với mọi a 2 E và KB 6j= (D v C)) then 16 C := C [ fDg; F + 17 if (KB j= ( C)(a) với mọi a 2 E ) then 18 go to 20; 19 return failure; 20 foreach D 2 C do F + 21 if (KB j= (C n fDg)(a) với mọi a 2 E ) then 22 C := C n fDg; F 23 C := C; 24 return Crs := simplify (C); /* rút gọn kh¡i ni»m C */ 4.3.4. V½ dụ minh họa V½ dụ 4.2. X²t cơ sở tri thùc KB0 = hR; T ; A0i như đã cho trong V½ dụ 1.1 và + − + − y E = hE ;E i với E = fP4, P6g, E = fP1, P2, P3, P5g, Σ = fAwarded, y cited_byg và Φ = ;. Học định nghĩa cho Ad với KB = hR; T ; Ai, trong đó A = + − A0 [ fAd(a) j a 2 E g [ f:Ad(a) j a 2 E g. Thuªt to¡n BBCL thực hi»n như sau: 1. C := ;, C0 := ;. 2. KB có nhi·u mô h¼nh, trong đó mô h¼nh I được đặc t£ như trong V½ dụ 4.1. I 3. Áp dụng Hàm partition để làm mịn mi·n ∆ cõa I, ta được ph¥n ho¤ch Y = fY3;Y4;Y5g nh§t qu¡n với E tương ùng với c¡c kh¡i ni»m đặc trưng C3;C4;C5, trong đó Y3 = fP2; P3; P5g, Y4 = fP4; P6g, Y5 = fP1g và C3 ≡ :Awarded, C4 ≡ Awarded u 9cited_by:>, C5 ≡ :Awarded u 9cited_by:>. 23
26. + 4. V¼ Y4 ⊆ E n¶n ta xem x²t C4 ≡ Awarded u 9cited_by:>. V¼ KB j= :C4(a) − F với mọi a 2 E n¶n ta th¶m C4 vào C. Do đó, ta có C ≡ fC4g và C ≡ C4. F + F 5. V¼ KB j= ( C)(a) với mọi a 2 E n¶n ta có C ≡ C ≡ Awarded u 9cited_by:>. Do kh¡i ni»m C đã ở d¤ng chu©n và không thº đơn gi£n hơn được núa n¶n k¸t qu£ tr£ v· là Crs ≡ Awarded u 9cited_by:>.  V½ dụ 4.3. X²t thuªt to¡n dual-BBCL đối với V½ dụ 4.2 và ho¡n đổi E+ và E− với nhau. Thuªt to¡n dual-BBCL thực hi»n ba bước đ¦u ti¶n gièng như V½ dụ 4.2 và c¡c bước ti¸p theo như sau: + − 4. V¼ Y3 ⊆ E n¶n ta xem x²t C3 ≡ :Awarded. V¼ KB j= :C3(a) với mọi a 2 E n¶n ta th¶m C3 vào C. Do đó, ta có C = fC3g. + 5. V¼ Y5 ⊆ E n¶n ta xem x²t C5 ≡ Awarded u :9cited_by:>. V¼ KB j= :C5(a) − F với mọi a 2 E và C5 không bị bao hàm bởi C dựa tr¶n KB n¶n ta th¶m C5 F vào C. Do đó, ta có C = fC3;C5g và C ≡ C3 t C5. F + F 6. V¼ KB j= ( C)(a) với mọi a 2 E n¶n ta có C ≡ C ≡ :Awarded t (Awarded u :9cited_by:>). Chu©n hóa và đơn gi£n kh¡i ni»m C ta được k¸t qu£ tr£ v· là Crs ≡ :Awarded t :9cited_by:>.  N¸u muèn l§y k¸t qu£ cõa V½ dụ 4.2 chúng ta l§y phõ định cõa Crs. Lúc đó k¸t qu£ là :Crs ≡:(:Awarded t :9cited_by:>) ≡ Awarded u 9cited_by:>. 4.4. Học kh¡i ni»m trong logic mô t£ với Ngú c£nh (2) 4.4.1. Thuªt to¡n BBCL2 Phương ph¡p học kh¡i ni»m cho cơ sở tri thùc trong logic mô t£ với Ngú c£nh (2) được tr¼nh bày chi ti¸t thông qua Thuªt to¡n 4.2. 4.4.2. T½nh đúng đắn cõa thuªt to¡n BBCL2 M»nh đề 4.2 (T½nh đúng đắn cõa thuªt to¡n BBCL2). Thuªt to¡n BBCL2 là đúng đắn. Nghĩa là, n¸u thuªt to¡n BBCL2 tr£ v· mët kh¡i ni»m Crs th¼ Crs là mët lời gi£i cõa bài to¡n học kh¡i ni»m cho cơ sở tri thùc trong logic mô t£ với Ngú c£nh (2).  4.4.3. V½ dụ minh họa 0 0 V½ dụ 4.4. X²t cơ sở tri thùc KB0 = hR; T ; A0i như đã cho trong V½ dụ 1.1 và + − y y 0 E = hE ;E i, Σ , Φ như trong V½ dụ 4.2. Đặt KB = hR; T ; Ai với A = A0 [ + − fAd(a) j a 2 E g [ f:Ad(a) j a 2 E g. Thuªt to¡n BBCL2 thực hi»n ba bước đầu − ti¶n gièng như V½ dụ 4.2 (có bê sung th¶m E0 := ;) và c¡c bước ti¸p theo như sau: − + 4. V¼ Y3 ⊆ E n¶n ta xem x²t C3 ≡ :Awarded. V¼ KB j= :C3(a) với mọi a 2 E − n¶n ta th¶m :C3 vào C và th¶m c¡c ph¦n tû cõa Y3 vào E0 . Do đó, ta có − C = fC3g và E0 = fP2; P3; P5g. − 5. V¼ Y5 ⊆ E n¶n ta xem x²t C5 ≡ Awarded u :9cited_by:>. V¼ KB j= :C5(a) + với mọi a 2 E và d C không bị bao hàm bởi C5 dựa tr¶n KB n¶n ta th¶m :C5 − vào C. Do đó, ta có C = f:C3; :C5g và E0 = fP1; P2; P3; P5g. − − 6. V¼ E0 = E n¶n ta có C ≡ d C ≡ ::Awarded u:(Awarded u:9cited_by:>). Rút gọn kh¡i ni»m C ta được k¸t qu£ tr£ v· là Crs ≡ Awarded u 9cited_by:>. 24
27. Thuªt to¡n 4.2: BBCL2 - Học kh¡i ni»m trong logic mô t£ với Ngú c£nh (2) Input : KB, Σy, Φy, E = hE+;E−i, k Output: Kh¡i ni»m C sao cho: • KBj= C(a) với mọi a 2 E+, và • KB 6j= C(a) for all a 2 E−. − 1 C := ;; C0 := ;; E0 := ;; − − 2 while not (too hard to extend C) và (E0 6= E ) do 0 3 X¥y dựng mô h¼nh húu h¤n (ti¸p theo) I cõa KB hoặc I = Ijk; y y 4 Y :=partition (I, Σ , Φ , E); /* ph¥n ho¤ch ∆I theo Hàm partition */ − I + I 5 foreach Yij 2 Y sao cho 9a 2 E : a 2 Yij và 8a 2 E : a 62 Yij do + 6 if (KB j= :Cij (a) với mọi a 2 E ) then 7 if (KB 6j= (d C v :Cij )) then 8 C := C [ f:Cij g; − − − I 9 E0 := E0 [ fa 2 E j a 2 Yij g; 10 else 11 C0 := C0 [ f:Cij g; − − 12 while not (too hard to extend C) và (E0 6= E ) do 13 D := D1 t D2 t · · · t Dl, với D1;D2;:::;Dl được chọn ng¨u nhi¶n tø C0; + 14 if (KB j= D(a) với mọi a 2 E ) then − − 15 if (KB 6j= (d C) v D) và (9a 2 E n E0 : KB 6j= (d C u D)(a)) then 16 C := C [ fDg; − − − − 17 E0 := E0 [ fa j a 2 E n E0 ; KB 6j= (d C)(a)g; − − 18 if (E0 = E ) then 19 foreach (D 2 C) do − 20 if (KB 6j= d(C n fDg)(a) với mọi a 2 E ) then 21 C := C n fDg; 22 C := d C; 23 return Crs := simplify (C); /* rút gọn kh¡i ni»m C */ 24 else 25 return failure; Tiºu k¸t Chương 4 Chương này tr¼nh bày phương ph¡p làm mịn ph¥n ho¤ch mi·n cõa di¹n dịch trong logic mô t£ tr¶n cơ sở cõa Thuªt to¡n 3.1. Ti¸p đó, chúng tôi đề xu§t c¡c thuªt to¡n BBCL, dual-BBCL và BBCL2 để gi£i quy¸t hai bài to¡n học kh¡i ni»m cho cơ sở tri thùc trong logic mô t£ với Ngú c£nh (1) và Ngú c£nh (2). Ý tưởng ch½nh cõa c¡c thuªt to¡n này là sû dụng c¡c mô h¼nh cõa cơ sở tri thùc k¸t hñp với mô phỏng hai chi·u trong c¡c mô h¼nh đó và c¥y quy¸t định để t¼m ki¸m kh¡i ni»m k¸t qu£. T½nh đúng cõa c¡c thuªt to¡n BBCL và BBCL2 cũng được chùng minh thông qua c¡c bê đề tương ùng. C¡c thuªt to¡n này có thº ¡p dụng cho mët lớp lớn c¡c logic mô t£ là mở rëng cõa ALCΣ;Φ có t½nh ch§t mô h¼nh húu h¤n hoặc nûa húu h¤n, trong đó Φ ⊆ fI; F; N ; Q; O; U; Selfg. 25
28. KẾT LUẬN K¸t luªn Logic mô t£ ngày càng kh¯ng định được vai trá quan trọng trong c¡c h» thèng biºu di¹n và suy luªn tri thùc. Kº tø khi logic mô t£ được xem là n·n t£ng cõa ngôn ngú OWL (mët ngôn ngú được sû dụng để mô h¼nh hóa c¡c h» thèng ngú nghĩa và ontology theo khuy¸n nghị cõa W3C), logic mô t£ đã được nhi·u nhà khoa học quan t¥m nghi¶n cùu. Đối với c¡c h» thèng ngú nghĩa, vi»c t¼m ki¸m c¡c kh¡i ni»m phù hñp, x¥y dựng nhúng định nghĩa cho c¡c kh¡i ni»m đó để đặc t£ h» thèng là mët v§n đề được đặt ra mët c¡ch tự nhi¶n. Học kh¡i ni»m trong logic mô t£ là mët trong nhúng gi£i ph¡p để t¼m ki¸m và x¥y dựng định nghĩa cho c¡c kh¡i ni»m. Với mục đích đó, luªn ¡n tªp trung nghi¶n cùu bài to¡n học kh¡i ni»m trong logic mô t£ sû dụng c¡c ngú c£nh kh¡c nhau. K¸t qu£ nghi¶n cùu cõa luªn ¡n có thº được tóm t­t như sau: 1. X¥y dựng ngôn ngú logic mô t£ LΣ;Φ dựa tr¶n ngôn ngú ALCreg với tªp c¡c đặc trưng mở rëng gồm I, O, N , Q, F, U, Self. Ngoài ra ngôn ngú được x¥y dựng cán cho ph²p sû dụng c¡c thuëc t½nh như là c¡c ph¦n tû cơ b£n cõa ngôn ngú nh¬m mô t£ c¡c h» thèng thông tin phù hñp với thực t¸ hơn. 2. Thông qua ngôn ngú LΣ;Φ, luªn ¡n đã x¥y dựng mô phỏng hai chi·u tr¶n lớp c¡c logic mở rëng đang nghi¶n cùu. C¡c định lý, bê đề, h» qu£ li¶n quan đến mô phỏng hai chi·u và t½nh b§t bi¸n đối với mô phỏng hai chi·u cũng được ph¡t triºn và chùng minh tr¶n lớp c¡c logic mở rëng này. 3. Ph¡t triºn thuªt to¡n học kh¡i ni»m cho h» thèng thông tin trong logic mô t£ với Ngú c£nh (3). C¡c bë chọn cơ b£n, bë chọn đơn gi£n và bë chọn mở rëng được sû dụng trong qu¡ tr¼nh làm mịn ph¥n ho¤ch. C¡c chi¸n lược t¼m ki¸m cũng được đề xu§t dựa vào gia lượng thông tin và t½nh đơn gi£n cõa kh¡i ni»m. 4. X¥y dựng thuªt to¡n BBCL, dual-BBCL, BBCL2 nh¬m gi£i quy¸t c¡c bài to¡n học kh¡i ni»m cho cơ sở tri thùc trong logic mô t£ với Ngú c£nh (1) và Ngú c£nh (2). Nhúng v§n đề c¦n ti¸p tục nghi¶n cùu Tø nhúng k¸t qu£ đạt được trong luªn ¡n, c¡c v§n đề đặt ra c¦n quan t¥m nghi¶n cùu trong thời gian tới như sau: 1. X¥y dựng c¡c chi¸n lược học kh¡c nhau thông qua c¡c độ đo trong vi»c quy¸t định khèi nào n¶n ph¥n ho¤ch trước. So s¡nh c¡c chi¸n lược học với nhau. 2. X¥y dựng c¡c module học kh¡i ni»m trong logic mô t£ với c¡c ngú c£nh kh¡c nhau như là mët API cho ph²p t½ch hñp vào c¡c h» thèng kh¡c. 3. Nghi¶n cùu c¡c thuªt to¡n học nûa gi¡m s¡t, học không gi¡m s¡t, học theo x¡c su§t cho c¡c cở sở tri thùc trong logic mô t£. 4. Nghi¶n cùu kh£ n«ng học ch½nh x¡c kh¡i ni»m cho c¡c logic mô t£ kh¡c nhau. 26
29. TÀI LIỆU THAM KHẢO [1] L. Badea and S.-H. Nienhuys-Cheng. A refinement operator for description logics. In Proceedings of the 10th International Conference on Inductive Logic Program- ming, ILP'2000, pages 40–59. Springer-Verlag, 2000. [2] P. Blackburn, J. van Benthem, and F. Wolter. Handbook of Modal Logic. Elsevier Science, 2006. [3] R. Cattral, F. Oppacher, and D. Deugo. Evolutionary data mining with automatic rule generalization, 2002. [4] W. W. Cohen and H. Hirsh. Learning the Classic description logic: Theoretical and experimental results. In Proceedings of KR'1994, pages 121–133, 1994. [5] A. Divroodi, Q.-T. Ha, L. A. Nguyen, and H. S. Nguyen. On C-learnability in description logics. In Proceedings of ICCCI'2012 (1), volume 7653 of LNCS, pages 230–238. Springer, 2012. [6] A. R. Divroodi and L. A. Nguyen. On bisimulations for description logics. Inf. Sci., 295:465–493, 2015. [7] N. Fanizzi, C. d'Amato, and F. Esposito. DL-FOIL concept learning in description logics. In Proceedings of ILP'2008, LNCS, pages 107–121. Springer-Verlag, 2008. [8] M. Frazier and L. Pitt. Classic learning. Machine Learning, 25(2-3):151–193, 1996. [9] L. Iannone, I. Palmisano, and N. Fanizzi. An algorithm based on counterfactuals for concept learning in the semantic web. Applied Intelligence, 26(2):139–159, 2007. [10] J. Lehmann and P. Hitzler. Concept learning in description logics using refinement operators. Machine Learning, 78(1-2):203–250, 2010. [11] L. A. Nguyen. An efficient tableau prover using global caching for the description logic ALC. Fundam. Inform., 93(1-3):273–288, 2009. [12] L. A. Nguyen. Cut-free exptime tableaux for checking satisfiability of a knowledge base in the description logic ALCI. In Proceedings of ISMIS'2011, volume 6804 of LNCS, pages 465–475. Springer-Verlag, 2011. [13] L. A. Nguyen. A tableau method with optimal complexity for deciding the de- scription logic SHIQ. In Proceedings of ICCSAMA'2013 (1), volume 479 of Studies in Computational Intelligence, pages 331–342. Springer, 2013. [14] L. A. Nguyen and A. Sza las. Logic-based roughification. In Rough Sets and Intelligent Systems (1), pages 517–543. Springer, 2013. [15] Z. Pawlak. Information systems theoretical foundations. Information Systems, 6(3):205–218, 1981. 27
30. [16] P. Sen, G. M. Namata, M. Bilgic, L. Getoor, B. Gallagher, and T. Eliassi-Rad. Collective classification in network data. AI Magazine, 29(3):93–106, 2008. [17] J. van Benthem. Modal Logic for Open Minds. Center for the Study of Language and Inf, 2010. 28
31. DANH MỤC CÁC CÆNG TRÌNH CỦA TÁC GIẢ 1. T.-L. Tran, Q.-T. Ha, T.-L.-G. Hoang, L. A. Nguyen, H. S. Nguyen, and A. Sza las. Concept learning for description logic-based information systems. In Pro- ceedings of the 2012 Fourth International Conference on Knowledge and Systems Engineering, KSE'2012, pages 65–73. IEEE Computer Society, 2012. (ISBN: 978- 1-4673-2171-6) 2. Q.-T. Ha, T.-L.-G. Hoang, L. A. Nguyen, H. S. Nguyen, A. Sza las, and T.-L. Tran. A bisimulation-based method of concept learning for knowledge bases in description logics. In Proceedings of the Third Symposium on Information and Communication Technology, SoICT'2012, pages 241–249. ACM, 2012. (ISBN: 978-1-4503-1232-5) 3. Tr¦n Thanh Lương, Hoàng Thị Lan Giao. Áp dụng độ đo entropy để ph¥n ho¤ch khèi cho c¡c h» thèng thông tin dựa tr¶n logic mô t£. Kỷ y¸u Hëi th£o quèc gia l¦n thù XV: Mët sè v§n đề chọn lọc cõa Công ngh» Thông tin và Truy·n thông, trang 11–18, Nhà xu§t b£n Khoa học và Kỹ thuªt, 2013. 4. T.-L. Tran, Q.-T. Ha, T.-L.-G. Hoang, L. A. Nguyen, and H. S. Nguyen. Bisimulation- based concept learning in description logics. In Proceedings of CS&P'2013, pages 421–433. CEURWS.org, 2013. (ISBN: 978-83-62582-42-6) 5. T.-L. Tran, L. A. Nguyen, and T.-L.-G. Hoang. A domain partitioning method for bisimulationbased concept learning in description logics. In Proceedings of ICCSAMA'2014, volume 282 of Advances in Intelligent Systems and Computing, pages 297–312. Springer International Publishing, 2014. (ISBN: 978-3-319-06569- 4) 6. T.-L. Tran, Q.-T. Ha, T.-L.-G. Hoang, L. A. Nguyen, and H. S. Nguyen. Bisimulation- based concept learning in description logics. Fundam. Inform., Vol. 133, No. 2-3, pages 287–303, 2014. (ISSN: 0169-2968) 7. T.-L. Tran and T.-L.-G. Hoang. Entropy-based measures for partitioning the domain of an interpretation in description logics. Journal of Science, Hue Uni- versity, Vol. 98, No. 8, pages 97–101, 2014. (ISSN: 1859-1388) 8. T.-L. Tran, L. A. Nguyen, and T.-L.-G. Hoang. Bisimulation-based concept learn- ing for information systems in description logics. Vietnam Journal of Computer Science, Vol. 2, pages 149–167, 2015. (ISSN: 2196-8888 (print version); ISSN: 2196-8896 (electronic version)) 29