ĐẠ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 Cơng trình hồ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: PGS TSKH Nguyễn Anh Linh, Trường Đại học Warsaw, Ba Lan 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 Đồ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 bảo vệ Hội đồng chấm luận án cấp Đại học Huế họp Đại học Huế vào lúc ngày tháng năm 2015 Có thể tìm hiểu luận án 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ế MỞ ĐẦU Vấn đề học khái niệm logic mô tả tương tự phân lớp nhị phân học máy truyền thống Tuy nhiên, việc học khái niệm ngữ cảnh logic mô tả khác với học máy truyền thống điểm, đối tượng không đặc tả thuộc tính mà cịn đặc tả mối quan hệ đối tượng Bài toán học khái niệm đặt theo ba ngữ cảnh sau: • Ngữ cảnh (1): Cho sở tri thức KB logic mô tả L tập cá thể E + , E − Học khái niệm C L cho: KB |= C(a) với a ∈ E + , KB |= ¬C(a) với a ∈ E − đó, tập E + chứa mẫu dương E − chứa mẫu âm C • Ngữ cảnh (2): Ngữ cảnh khác với ngữ cảnh đề cập điều kiện thứ hai thay điều kiện yếu hơn: KB |= C(a) với a ∈ E + , KB |= C(a) với a ∈ E − • Ngữ cảnh (3): Cho diễn dịch I tập cá thể E + , E − Học khái niệm C logic mô tả L cho: I |= C(a) với a ∈ E + , I |= ¬C(a) với a ∈ E − Chú ý I |= ¬C(a) tương đồng với I |= C(a) Học khái niệm logic mô tả nhiều nhà khoa học quan tâm nghiên cứu chia thành ba hướng tiếp cận Hướng tiếp cận thứ tập trung vào khả học logic mô tả [4], [8] Cohen Hirsh nghiên cứu lý thuyết khả học logic mô tả đề xuất thuật toán học khái niệm LCSLearn dựa “bao hàm chung nhỏ nhất” [4] Frazier Pitt nghiên cứu khả học logic mô tả Classic cách sử dụng truy vấ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 logic mô tả sử dụng toán tử làm mịn Badea Nienhuys-Cheng [1] nghiên cứu học khái niệm logic mô tả ALER, Iannone cộng [9] nghiên cứu thuật toán học logic mô tả giàu ngữ nghĩa hơn, ALC Cả hai cơng trình nghiên cứu việc học khái niệm logic mô tả với Ngữ cảnh (1) Fanizzi cộng [?]iới thiệu hệ thống DL-Foil cho việc học khái niệm logic mô tả hỗ trợ ngôn ngữ logic mô tả OWL [7] Lehmann Hitzler đề xuất thuật toán học DL-Learner theo phương pháp lập trình đệ quy có khai thác thêm kỹ thuật lập trình di truyền [10] Các cơng trình nghiên cứu việc học khái niệm 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 logic mô tả sử dụng mô hai chiều [6] Nguyen Szalas áp dụng mô hai chiều vào logic mơ tả để mơ hình hóa tính khơng phân biệt đối tượng [14] Các tác giả đề xuất phương pháp tổng quát để học khái niệm cho hệ thống thông tin logic mô tả Divroodi [5] cộng nghiên cứu khả học logic mô tả sử dụng mơ hai chiều Các cơng trình nghiên cứu tốn học khái niệm logic mơ tả với Ngữ cảnh (3) Ngoại trừ cơng trình Nguyen Szalas [14], Divroodi [5] sử dụng mô hai chiều logic mơ tả để hướng dẫn việc tìm kiếm khái niệm kết quả, tất cơng trình nghiên cứu cịn lại sử dụng tốn tử làm mịn lập trình logic đệ quy và/hoặc chiến lược tìm kiếm dựa vào hàm tính điểm mà khơng sử dụng mơ hai chiều Các cơng trình chủ yếu tập trung vào vấn đề học khái niệm với Ngữ cảnh (1) Ngữ cảnh (2) logic mô tả đơn giản ALER, ALN ALC Trong cơng trình [14] [5] sử dụng mô hai chiều cho việc học khái niệm logic mô tả với Ngữ cảnh (3) Hai cơng trình khơng đề cập đến vấn đề học khái niệm logic mô tả với Ngữ cảnh (1) Ngữ cảnh (2) Từ khảo sát nêu trên, nhận thấy học khái niệm logic mô tả vấn đề quan trọng việc xây dựng khái niệm hữu ích phục vụ cho hệ thống ngữ nghĩa nói chung ontology nói riêng Từ đó, tác động lên nhiều ứng dụng 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 phương pháp học khái niệm logic mô tả dựa mô hai chiều với mục tiêu đặt là: • Nghiên cứu cú pháp, ngữ nghĩa lớp lớn logic mô tả giàu ngữ nghĩa so với cơng trình có cách cho phép sử dụng thuộc tính phần tử ngôn ngữ, quan hệ thông qua vai trò liệu đề cập đến đặc trưng F , N Lớp logic bao phủ logic mơ tả hữu ích ALC , SHIF , SHIQ, SHOIN , SHOIQ, SROIQ, • Xây dựng, mở rộng định nghĩa, định lý, bổ đề mô hai chiều lớp logic mô tả đề cập sử dụng để mơ hình hóa tính khơng phân biệt đối tượng làm sở cho thuật tốn học khái niệm logic mơ tả; • Phát triển thuật tốn học khái niệm dựa mơ hai chiều cho hệ thống thông tin 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 diễn dịch logic mô tả dựa mô hai chiều sử dụng chọn hợp lý độ đo gia lượng thơng tin; • Đề xuất thuật toán học khái niệm cho sở tri thức logic mô tả với Ngữ cảnh (1) Ngữ cảnh (2) sử dụng mô hai chiều Chương LOGIC MÔ TẢ VÀ CƠ SỞ TRI THỨC 1.1 Tổng quan logic mô tả 1.1.1 Giới thiệu Logic mô tả xây dựng dựa vào ba thành phần gồm tập cá thể, tập khái niệm nguyên tố tập vai trò nguyên tố 1.1.2 Biểu diễn tri thức Từ cá thể, khái niệm vai trị, người ta xây dựng hệ thống để biểu diễn suy luận tri thức dựa logic mô tả gồm: tiên đề vai trò, tiên đề thuật ngữ, 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 ALC ) Cho ΣC tập tên khái niệm ΣR tập tên vai trò (ΣC ∩ ΣR = ∅) Các phần tử ΣC gọi khái niệm nguyên tố Logic mô tả ALC cho phép khái niệm định nghĩa cách đệ quy sau: • A ∈ ΣC A khái niệm ALC , • C , D khái niệm r ∈ ΣR vai trị C D, ∃r.C ∀r.C khái niệm ALC , ⊥, ¬C , C D, Định nghĩa 1.2 (Ngữ nghĩa ALC ) Một diễn dịch logic mô tả ALC I = ∆I , ·I , ∆I tập khác rỗng gọi miền I ·I ánh xạ, gọi hàm diễn dịch I , cho phép ánh xạ cá thể a ∈ ΣI thành phần tử aI ∈ ∆I , tên khái niệm A ∈ ΣC thành tập AI ⊆ ∆I tên vai trò r ∈ ΣR thành quan hệ hai ngơi rI ⊆ ∆I × ∆I Diễn dịch khái niệm phức xác định sau: I = ∆I , ⊥I = ∅, (∃r.C)I = {x ∈ ∆I | ∃y ∈ ∆I [rI (x, y) ∧ C I (y)]}, (∀r.C)I = {x ∈ ∆I | ∀y ∈ ∆I [rI (x, y) ⇒ C I (y)]}, (¬C)I = ∆I \ C I , (C D)I = C I ∩ DI , (C D)I = C I ∪ DI 1.1.4 Khả biểu diễn Khả biểu diễn tri thức logic mô tả phụ thuộc vào tạo tử khái niệm tạo tử vai trị mà phép sử dụng Logic sử dụng nhiều tạo tử có khả biểu diễn tốt 1.1.5 Logic mô tả tên gọi • ALC - logic mơ tả ALC ngơn ngữ khái niệm thuộc tính có phủ định • S - ALC + tính chất bắc cầu 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 • 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 ngữ nghĩa logic mô tả 1.2.1 Ngôn ngữ logic mô tả ALC reg Định nghĩa 1.3 (Cú pháp ALC reg ) Cho ΣC tập tên khái niệm ΣR tập tên vai trò (ΣC ∩ ΣR = ∅) Các phần tử ΣC gọi khái niệm nguyên tố phần tử ΣR gọi vai trò nguyên tố Logic mô tả động ALC reg cho phép khái niệm vai trò định nghĩa cách đệ quy sau: • r ∈ ΣR r vai trị ALC reg , • A ∈ ΣC A khái niệm ALC reg , • C , D khái niệm R, S vai trị S , R∗ , C? vai trị ALC reg , , ⊥, ¬C , C D, C D, ∃R.C ∀R.C khái niệm ALC reg – ε, R ◦ S , R – Diễn dịch vai trò phức ALC reg xác định sau: (R ◦ S)I = RI ◦ S I , εI = { x, x | x ∈ ∆I }, (R S)I = RI ∪ S I , (C?)I = { x, x | C I (x)} (R∗ )I = (RI )∗ , 1.2.2 Ngôn ngữ logic mô tả LΣ,Φ Một ký tự logic mô tả tập hữu hạn Σ = ΣI ∪ ΣdA ∪ ΣnA ∪ ΣoR ∪ ΣdR , ΣI tập cá thể, ΣdA tập thuộc tính rời rạc, ΣnA tập thuộc tính số, ΣoR tập tên vai trị đối tượng ΣdR tập vai trò liệu Tất tập ΣI , ΣdA , ΣnA , ΣoR ΣdR rời đôi Xét đặc trưng 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ổ qt), Self (tính phản xạ cục vai trị) Tập đặc trưng logic mô tả Φ tập rỗng tập chứa số đặc trưng nêu Định nghĩa 1.4 (Ngôn ngữ LΣ,Φ ) Cho Σ ký tự logic mô tả, Φ tập đặc trưng logic mô tả L đại diện cho ALC reg Ngôn ngữ logic mơ tả LΣ,Φ cho phép vai trị đối tượng khái niệm định nghĩa cách đệ quy sau: • r ∈ ΣoR r vai trị đối tượng LΣ,Φ , • A ∈ ΣC A khái niệm LΣ,Φ , • A ∈ ΣA \ ΣC d ∈ range(A) A = d A = d khái niệm LΣ,Φ , • A ∈ ΣnA d ∈ range(A) A ≤ d, A < d, A ≥ d A > d khái niệm LΣ,Φ , • R S vai trò đối tượng LΣ,Φ , C D khái niệm LΣ,Φ , r ∈ ΣoR , σ ∈ ΣdR , a ∈ ΣI n số tự nhiên – ε, R ◦ S , R S , R∗ C? vai trò đối tượng LΣ,Φ , – , ⊥, ¬C , C – – – – – – – – – – – D, C D, ∃R.C ∀R.C khái niệm LΣ,Φ , d ∈ range(σ) ∃σ.{d} khái niệm LΣ,Φ , I ∈ Φ R− vai trị đối tượng LΣ,Φ , O ∈ Φ {a} khái niệm LΣ,Φ , F ∈ Φ ≤ r khái niệm LΣ,Φ , {F, I} ⊆ Φ ≤ r− khái niệm LΣ,Φ , N ∈ Φ ≥ n r ≤ n r khái niệm LΣ,Φ , {N , I} ⊆ Φ ≥ n r− ≤ n r− khái niệm LΣ,Φ , Q ∈ Φ ≥ n r.C ≤ n r.C khái niệm LΣ,Φ , {Q, I} ⊆ Φ ≥ n r− C ≤ n r− C khái niệm LΣ,Φ , U ∈ Φ U vai trị đối tượng LΣ,Φ , Self ∈ Φ ∃r.Self khái niệm LΣ,Φ Định nghĩa 1.5 (Ngữ nghĩa LΣ,Φ ) Một diễn dịch LΣ,Φ I = ∆I , ·I , ∆I tập khác rỗng gọi miền I ·I ánh xạ gọi hàm diễn dịch I cho phép ánh xạ cá thể a ∈ ΣI thành phần tử aI ∈ ∆I , tên khái niệm A ∈ ΣC thành tập AI ⊆ ∆I , thuộc tính A ∈ ΣA \ ΣC thành hàm phần AI : ∆I → range(A), tên vai trò đối tượng r ∈ ΣoR thành quan hệ hai rI ⊆ ∆I × ∆I vai trị liệu σ ∈ ΣdR thành quan hệ hai σ I ⊆ ∆I × range(σ) Hàm diễn dịch ·I mở rộng cho vai trò đối tượng phức khái niệm phức Hình 1.1, #Γ ký hiệu cho lực lượng tập Γ (C?)I = { x, x | C I (x)} (R∗ )I = (RI )∗ (R ◦ S)I = RI ◦ S I (R− )I = (RI )−1 εI = { x, x | x ∈ ∆I } (R S)I = RI ∪ S I (C D)I = C I ∩ DI (C D)I = C I ∪ DI {a}I = {aI } U I = ∆I × ∆I I (A ≤ d)I = {x ∈ ∆I | AI (x) xác định AI (x) ≤ d} = ∆I ⊥I = ∅ (A ≥ d)I = {x ∈ ∆I | AI (x) xác định AI (x) ≥ d} (¬C)I = ∆I \ C I (A = d)I = {x ∈ ∆I | AI (x) = d} (A = d)I = (¬(A = d))I (A < d)I = ((A ≤ d) (A = d))I (A > d)I = ((A ≥ d) (A = d))I (∀R.C)I = {x ∈ ∆I | ∀y [RI (x, y) ⇒ C I (y)]} (∃r.Self)I = {x ∈ ∆I | rI (x, x)} (∃R.C)I = {x ∈ ∆I | ∃y [RI (x, y) ∧ C I (y)]} (∃σ.{d})I = {x ∈ ∆I | σ I (x, d)} (≥ n R.C)I = {x ∈ ∆I | #{y | RI (x, y) ∧ C I (y)} ≥ n} (≥ n R)I = (≥ n R )I (≤ n R.C)I = {x ∈ ∆I | #{y | RI (x, y) ∧ C I (y)} ≤ n} (≤ n R)I = (≤ n R )I Hình 1.1: Diễn dịch vai trò phức khái niệm phức 1.3 Các dạng chuẩn 1.3.1 Dạng chuẩn phủ định khái niệm Khái niệm C gọi dạng chuẩn phủ định toán tử phủ định xuất trước tên khái niệm có C 1.3.2 Dạng chuẩn lưu trữ khái niệm Dạng chuẩn lưu trữ khái niệm xây dựng dựa dạng chuẩn phủ định tập hợp Khái niệm dạng biểu diễn dạng tập hợp khái niệm 1.3.3 Dạng chuẩn nghịch đảo vai trò Vai trò đối tượng R gọi dạng chuẩn nghịch đảo tạo tử nghịch đảo áp dụng cho tên vai trị đối tượng có R (khơng xét đến vai trò U ) − Đặt Σ± oR = ΣoR ∪ {r | r ∈ ΣoR } Một vai trò đối tượng phần tử thuộc Σ± oR (tương ứng, ΣoR ) ngôn ngữ 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 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ị ngơn ngữ LΣ,Φ biểu thức có dạng ε r R1 ◦ R2 ◦ · · · ◦ Rk r, k ≥ 1, r ∈ ΣoR R1 , R2 , , Rk vai trò đối tượng LΣ,Φ khác với vai trò phổ quát U Một khẳng định vai trị ngơn ngữ LΣ,Φ biểu thức có dạng Ref(r), Irr(r), Sym(r), Tra(r) Dis(R, S), r ∈ ΣoR R, S vai trò đối tượng LΣ,Φ khác với vai trò phổ quát U Một tiên đề vai trị ngơn ngữ LΣ,Φ tiên đề bao hàm vai trò khẳng định vai trò LΣ,Φ Định nghĩa 1.7 (Bộ tiên đề vai trò) Bộ tiên đề vai trị (RBox) ngơn ngữ LΣ,Φ tập hữu hạn tiên đề vai trò 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 qt ngơn ngữ LΣ,Φ biểu thức có dạng C D, C D khái niệm LΣ,Φ Một tiên đề tương đương khái niệm ngôn ngữ LΣ,Φ biểu thức có dạng C ≡ D, C D khái niệm LΣ,Φ Một tiên đề thuật ngữ ngôn ngữ LΣ,Φ tiên đề bao hàm khái niệm tổng quát tiên đề tương đương khái niệm LΣ,Φ Định nghĩa 1.9 (Bộ tiên đề thuật ngữ) Bộ tiên đề thuật ngữ (TBox) ngôn ngữ LΣ,Φ tập hữu hạn tiên đề thuật ngữ 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ể ngôn ngữ LΣ,Φ biểu thức có dạng C(a), R(a, b), ¬R(a, b), a = b, a = b, C khái niệm R vai trò đối tượng LΣ,Φ Định nghĩa 1.11 (Bộ khẳng định cá thể) Bộ khẳng định cá thể (ABox) ngôn ngữ LΣ,Φ tập hữu hạn khẳng định cá thể LΣ,Φ 1.4.4 Cơ sở tri thức mơ hình sở tri thức Định nghĩa 1.12 (Cơ sở tri thức) Một sở tri thức ngôn ngữ LΣ,Φ ba KB = R, T , A , R RBox, T TBox A ABox LΣ,Φ Định nghĩa 1.13 (Mơ hình) Một diễn dịch I mơ hình RBox R (tương ứng, TBox T , ABox A), ký hiệu I |= R (tương ứng, I |= T , I |= A), I thỏa mãn tất tiên đề vai trò R (tương ứng, tiên đề thuật ngữ T , khẳng định cá thể A) Một diễn dịch I mơ hình sở tri thức KB = R, T , A , ký hiệu I |= KB , mơ hình R, T A Ví dụ 1.1 Ví dụ sau sở tri thức đề cập ấn phẩm khoa học: Φ = {I, O, N , Q}, ΣI = {P1 , P2 , P3 , P4 , P5 , P6 }, ΣC = {Pub, Awarded , UsefulPub, Ad }, ΣdA = ΣC , ΣnA = {Year }, ΣoR = {cites, cited_by}, ΣdR = ∅, − R = {cites cited_by, cited_by − cites, Irr(cites)}, T ={ Pub, UsefulPub ≡ ∃cited_by }, A0 = {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 = A0 ∪ {(¬∃cited_by )(P1 ), (∀cited_by.{P2 , P3 , P4 })(P5 )} Lúc KB = R, T , A0 KB = R, T , A0 sở tri thức LΣ,Φ Tiên đề Pub để miền mô hình KB KB gồm ấn phẩm khoa học 1.5 Suy luận logic mơ tả Có nhiều tốn suy luận đặt hệ thống biểu diễn tri thức dựa logic mô tả Để giải tố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 thuật toán tableaux Thuật toán bao hàm theo tỏ hiệu ngôn ngữ logic mô tả đơn giản FL0 , FL⊥ , ALN , thuật toán tableaux giải toán suy luận với lớp ngôn ngữ logic mô tả rộng ALC [11], ALCI [12], ALCIQ [12], SHIQ [13], Tiểu kết Chương Trong chương này, luận án giới thiệu khái quát logic mô tả, khả biểu diễn tri thức logic mô tả Thông qua cú pháp ngữ nghĩa logic mô tả, luận án trình bày sở tri thức, mơ hình sở tri thức logic mơ tả vấn đề suy luận logic mơ tả Ngồi việc trình bày ngơn ngữ logic mô tả cách tổng quát dựa logic ALC reg với đặ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ổ qt), Self (tính phản xạ cục vai trị), luận án cịn xem xét thuộc tính thành phần ngơn ngữ, bao gồm thuộc tính rời rạc thuộc tính số Cách tiếp cận phù hợp hệ thống thông tin dựa logic mơ tả thường có thực tế Chương MÔ PHỎNG HAI CHIỀU TRONG LOGIC MÔ TẢ VÀ TÍNH BẤT BIẾN 2.1 Giới thiệu Mơ hai chiều nghiên cứu logic hình thái (modal logic) [2], [17] Mô hai chiều quan hệ hai ngơi cho phép đặc tả tính tương tự hai trạng thái tính tương tự mơ hình Kripke Divroodi Nguyen nghiên cứu mơ hai chiều số logic mô tả cụ thể [6] 2.2 Mô hai chiều 2.2.1 Khái niệm Định nghĩa 2.1 (Mô hai chiều) Cho Σ Σ† ký tự logic mô tả cho Σ† ⊆ Σ, Φ Φ† tập đặc trưng logic mô tả cho Φ† ⊆ Φ, I I diễn dịch LΣ,Φ Một LΣ† ,Φ† -mô hai chiều I I quan hệ hai Z ⊆ ∆I × ∆I thỏa điều kiện sau với a ∈ Σ†I , A ∈ Σ†C , B ∈ Σ†A \ Σ†C , r ∈ Σ†oR , σ ∈ Σ†dR , d ∈ range(σ), x, y ∈ ∆I , x , y ∈ ∆I : Z(aI , aI ) Z(x, x ) ⇒ [AI (x) ⇔ AI (x )] Z(x, x ) ⇒ [B I (x) = B I (x ) hai không xác định] [Z(x, x ) ∧ rI (x, y)] ⇒ ∃y ∈ ∆I | [Z(y, y ) ∧ rI (x , y )] [Z(x, x ) ∧ rI (x , y )] ⇒ ∃y ∈ ∆I | [Z(y, y ) ∧ rI (x, y)] Z(x, x ) ⇒ [σ I (x, d) ⇔ σ I (x , d)], (2.1) (2.2) (2.3) (2.4) (2.5) (2.6) I ∈ Φ† [Z(x, x ) ∧ rI (y, x)] ⇒ ∃y ∈ ∆I | [Z(y, y ) ∧ rI (y , x )] [Z(x, x ) ∧ rI (y , x )] ⇒ ∃y ∈ ∆I | [Z(y, y ) ∧ rI (y, x)], (2.7) (2.8) O ∈ Φ† Z(x, x ) ⇒ [x = aI ⇔ x = aI ], (2.9) Z(x, x ) ⇒ #{y ∈ ∆I | rI (x, y)} = #{y ∈ ∆I | rI (x , y )}, (2.10) N ∈ Φ† {N , I} ⊆ Φ† Z(x, x ) ⇒ #{y ∈ ∆I | rI (y, x)} = #{y ∈ ∆I | rI (y , x )}, (2.11) F ∈ Φ† Z(x, x ) ⇒ [#{y ∈ ∆I | rI (x, y)} ≤ ⇔ #{y ∈ ∆I | rI (x , y )} ≤ 1], (2.12) • ≤ r, F ∈ Φ† r ∈ Σ†oR , • ≤ r− , {F, I} ⊆ Φ† r ∈ Σ†oR , • ≥ l r ≤ m r, N ∈ Φ† , r ∈ Σ†oR , < l ≤ #∆I ≤ m < #∆I , • ≥ l r− ≤ m r− , {N , I} ⊆ Φ† , r ∈ Σ†oR , < l ≤ #∆I ≤ m < #∆I , • ≥ l r.Cit ≤ m r.Cit , Q ∈ Φ† , r ∈ Σ†oR , ≤ t ≤ k , < l ≤ #CiIt ≤ m < #CiIt , • ≥ l r− Cit ≤ m r− Cit , {Q, I} ⊆ Φ† , r ∈ Σ†oR , ≤ t ≤ k , < l ≤ #CiIt ≤ m < #CiIt , • ∃r.Self , Self ∈ Φ† r ∈ Σ†oR Định lý 3.1 Cho Σ Σ† ký tự logic mô tả cho Σ† ⊆ Σ, Φ Φ† tập đặc trưng logic mô tả cho Φ† ⊆ Φ, I hệ thống thông tin LΣ,Φ Xuất phát từ phân hoạch {∆I } thực việc làm mịn liên tục chọn ta nhận phân hoạch tương ứng với quan hệ tương đương ∼Σ† ,Φ† ,I Định nghĩa 3.5 (Bộ chọn đơn giản) Giả sử Y1 , Y2 , , Yn khối tạo trình làm mịn phân hoạch {∆I }, Yi đặc trưng khái niệm Ci cho Yi = CiI Một chọn đơn giản LΣ† ,Φ† để phân chia khối chọn khái niệm có dạng sau: • A ≤ d A < d, A ∈ Σ†nA , d ∈ range(A) d phần tử nhỏ range(A), • A ≥ d A > d, A ∈ Σ†nA , d ∈ range(A) d khơng phải phần tử lớn range(A), • ∃r , ∃r.Ci ∀r.Ci , r ∈ Σ†oR ≤ i ≤ n, • ∃r− , ∃r− Ci ∀r− Ci , I ∈ Φ† , r ∈ Σ†oR ≤ i ≤ n, • ≥ l r.Ci ≤ m r.Ci , Q ∈ Φ† , r ∈ Σ†oR , ≤ i ≤ n, < l ≤ #CiI ≤ m < #CiI , • ≥ l r− Ci ≤ m r− Ci , {Q, I} ⊆ Φ† , r ∈ Σ†oR , ≤ i ≤ n, < l ≤ #CiI ≤ m < #CiI Gọi D tập chứa chọn có Cùng với phân hoạch thời Y, tập D = {D1 , D2 , , Dh } gọi tập chọn thời Chúng định nghĩa chọn mở rộng để phục vụ cho trình làm mịn hiệu Định nghĩa 3.6 (Bộ chọn mở rộng) Cho D = {D1 , D2 , , Dh } tập chọn thời Một chọn mở rộng LΣ† ,Φ† để phân chia khối phân hoạch thời khái niệm thuộc dạng sau: • ∃r.Du ∀r.Du , r ∈ Σ†oR Du ∈ D, • ∃r− Du ∀r− Du , I ∈ Φ† , r ∈ Σ†oR Du ∈ D, 15 • ≥ l r.Du ≤ m r.Du , Q ∈ Φ† , r ∈ Σ†oR , Du ∈ D, < l ≤ #DuI ≤ m < #DuI , • ≥ l r− Du ≤ m r− Du , {Q, I} ⊆ Φ† , r ∈ Σ†oR , Du ∈ D, < l ≤ #DuI ≤ m < #DuI 3.2.3 Tính đơn giản khái niệm Định nghĩa 3.7 Cho C khái niệm dạng chuẩn ngôn ngữ LΣ,Φ Độ sâu khả khái niệm C , ký hiệu mdepth(C), xác định sau: • C có dạng , ⊥, A, A = d, A = d, A > d, A ≥ d, A < d A ≤ d, • mdepth(D) C dạng chuẩn ¬D, • C có dạng ∃σ.{d}, ∃r.Self , ≥ n R ≤ n R, • + mdepth(D) C có dạng ∃R.D, ∀R.D, ≥ n R.D ≤ n R.D, • max{mdepth(D1 ), mdepth(D2 ), , mdepth(Dn )} C có dạng {D1 , D2 , , Dn } {D1 , D2 , , Dn } Định nghĩa 3.8 Cho C khái niệm dạng chuẩn ngôn ngữ LΣ,Φ Độ dài khái niệm C , ký hiệu length(C), xác định sau: • C có dạng ⊥, • C có dạng A, A = d, A = d, A > d, A ≥ d, A < d A ≤ d, • length(D) C ≡ D D dạng chuẩn ¬D, • C có dạng ∃σ.{d}, ∃r.Self , ≥ n R ≤ n R, • + length(D) C có dạng ∃R.D ∀R.D, • + length(D) C có dạng ≥ n R.D ≤ n R.D, • 1+ length(D1 )+ length(D2 )+· · ·+ length(Dn ) C có dạng {D1 , D2 , , Dn } {D1 , D2 , , Dn } Khái niệm đơn giản khái niệm có độ dài độ sâu khả nhỏ 3.2.4 Độ đo dựa entropy Cho I hệ thống thông tin, X Y tập ∆I , X đóng vai trị tập mẫu dương, Y đóng vai trị khối phân hoạch Định nghĩa 3.9 (Entropy) Entropy tập Y tập X miền ∆I hệ thống thông tin I , ký hiệu E∆I (Y /X), xác định sau:   0, Y ∩ X = ∅ Y ⊆ X E∆I (Y /X) = (3.1) #XY #XY #XY #XY  log2 − log2 , ngược lại, − #Y #Y #Y #Y XY đại diện cho tập X ∩ Y XY đại diện cho tập X ∩ Y 16 Định nghĩa 3.10 (Gia lượng thông tin) Gia lượng thông tin chọn D việc phân chia tập Y tập X ∆I hệ thống thông tin I , ký hiệu IG∆I (Y /X, D), xác định sau: #DI Y #DI Y I IG∆I (Y /X, D) = E∆I (Y /X) − E∆I (D Y /X)+ E∆I (DI Y /X) (3.2) #Y #Y DI Y đại diện cho tập DI ∩ Y DI Y đại diện cho tập DI ∩ Y Trong ngữ cảnh ∆I X rõ ràng, viết E(Y ) thay cho E∆I (Y /X) IG(Y, D) thay cho IG∆I (Y /X, D) 3.2.5 Thuật tốn học khái niệm 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 logic mô tả mô tả Thuật toán 3.1, thuật toán có sử dụng hàm chooseBlockSelector để định khối chọn cần phân chia trước Function chooseBlockSelector Input : Y, D Output: Yij , Sij cho IG(Yij , Sij ) cực đại, Yij ∈ Y Sij ∈ D BS := ∅; foreach Yij ∈ Y foreach Du ∈ D Tính IG(Yij , Du ); S := arg max{IG(Yij , Du )}; Lấy Sij ∈ S cho Sij khái niệm đơn giản nhất; BS := BS ∪ { Yij , Sij }; Du ∈D Chọn Yij , Sij ∈ BS cho IG(Yij , Sij ) cực đại; return Yij , Sij ; 3.3 Ví dụ minh họa Các ví dụ sau tranh đầy đủ hiệu chọn đơn giản chọn mở rộng đề cập Mục 3.2.2 Đầu tiên xét ví dụ sở tri thức hệ thống thông tin tương ứng với sở tri thức Ví dụ 3.1 Cho sở tri thức KB = R, T , A LΣ,Φ , với Σ = ΣI ∪ ΣdA ∪ ΣnA ∪ ΣoR ∪ ΣdR Φ = {I}, đó: ΣI = {Ava, Britt, Colin, Dave, Ella, F lor, Gigi, Harry}, ΣC = {Human, M ale, F emale, N ephew, N iece}, ΣoR = {hasChild, hasP arent, hasSibling}, ΣdA = ΣC , ΣnA = ∅, ΣdR = ∅ R = {hasP arent ≡ hasChild− , Sym(hasSibling)}, T = {Human ≡ , N iece ≡ F emale N ephew ≡ M ale ∃hasChild− (∃hasSibling ), ∃hasChild− (∃hasSibling )}, 17 Thuật toán 3.1: Học khái niệm cho hệ thống thông tin logic mô tả Input : I, Σ† , Φ† , E = E − , E + Output: Khái niệm C cho: • I |= C(a) với a ∈ E + , • I |= C(a) với a ∈ E − I n := 1; Y1 := ∆ ; C1 := ; Y := {Y1 }; D = ∅; Tạo thêm chọn vào D; /* Định nghĩa 3.4, 3.5 và/hoặc 3.6 */ while (Y không quán với E) Yij , Sij := chooseBlockSelector(Y, D); if (Yij không bị phân chia SiIj ) then break; 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 s := n + 1; t := n + 2; n := n + 2; Ys := Yij ∩ SiIj ; Cs := Cij Sij ; I Yt := Yij ∩ (¬Sij ) ; Ct := Cij ¬Sij ; if (Yij khơng bị phân chia E) then LargestContainer [s] := LargestContainer [ij ]; LargestContainer [t] := LargestContainer [ij ]; else if (Ys không bị phân chia E) then LargestContainer [s] := s; if (Yt không bị phân chia E) then LargestContainer [t] := t; Y := Y ∪ {Ys , Yt } \ {Yij }; Tạo thêm chọn vào D; /* Định nghĩa 3.4, 3.5 và/hoặc 3.6 */ J := ∅; C := ∅; if (Y quán với E) then foreach Yij ∈ Y if (∃a ∈ E + : aI ∈ Yij ) then J := J ∪ {LargestContainer [ij ]} ; foreach l ∈ J C := C ∪ {Cl }; C := C; return Crs :=simplify (C); else return failure; A = {F emale(Ava), F emale(Britt), M ale(Colin), M ale(Dave), F emale(Ella), F emale(F lor), F emale(Gigi), hasChild(Ava, Dave), hasChild(Ava, Ella), M ale(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)} 18 Hệ thống thông tin I sở tri thứ KB xây dựng sau: ∆I = {Ava, Britt, Colin, Dave, Ella, F lor, Gigi, Harry}, HumanI = ∆I , AvaI = Ava, BrittI = Britt, , Harry I = Harry, F emaleI = {Ava, Britt, Ella, F lor, Gigi}, M aleI = {Colin, Dave, Harry}, hasChildI = { Ava, Dave , Ava, Ella , Britt, F lor , Colin, Gigi , Colin, Harry }, hasP arentI = { Dave, Ava , Ella, Ava , F lor, Britt , Gigi, Colin , Harry, Colin }, hasSibling I = { Britt, Colin , Colin, Britt , Dave, Ella , Ella, Dave , Gigi, Harry , Harry, Gigi }, (hasSibling − )I = hasSibling I , N ieceI = {F lor, Gigi}, N ephewI = {Harry} Ví dụ sử dụng chọn đơn giản kết hợp với chọn mở rộng cho kết tốt so với sử dụng chọn đơn giản Ví dụ 3.2 Xét hệ thống thơng tin I cho Ví dụ 3.1, ngôn ngữ LΣ† ,Φ† với Σ† = {F emale, hasChild, hasSibling} Φ† = {I}, tập X = {F lor, Gigi} (nghĩa là, E = E + , E − với E + = {F lor, Gigi} E − = {Ava, Britt, Colin, Dave, Ella, Harry}) Học định nghĩa tập X Chúng ta xem X tập thể khái niệm N iece ≡ F emale ∃hasChild− (∃hasSibling ) I Học định nghĩa X LΣ† ,Φ† cách sử dụng chọn đơn giản Khái niệm kết học rút gọn thành khái niệm Crs sau: Crs ≡ F emale ∀hasChild.⊥ (∀hasChild− (¬F emale) ∀hasSibling.⊥) Học định nghĩa X LΣ† ,Φ† cách sử dụng chọn đơn giản chọn mở rộng Khái niệm kết học Crs ≡ F emale ∃hasChild− (∃hasSibling ) Trong trường hợp thứ hai, khái niệm ∃hasChild− (∃hasSibling ) chọn mở rộng Bộ chọn tạo cách áp dụng luật thứ hai Định nghĩa 3.6 với ∃hasSibling khái niệm có tập chọn thời D 3.4 Kết thực nghiệm Các tập liệu dùng để thử nghiệm WebKB [16], PokerHand [3] Family Chúng tơi trình bày thơng tin chi tiết sau: • độ sâu khả (Dep.) trung bình (Avg.) khái niệm gốc (Org.), • độ dài (Len.) trung bình khái niệm gốc, • độ sâu khả trung bình khái niệm kết (Res.), • độ dài trung bình khái niệm kết quả, • độ đắn (Acc.), tỉ lệ xác (Pre.), tỉ lệ bao phủ (Rec.) độ đo F1, • độ lệch chuẩn, giá trị nhỏ (Min) giá trị lớn (Max) độ đắn, tỉ lệ xác, độ bao phủ độ đo F1 19 Bảng 3.1: Kết ước lượng tập liệu WebKB, PokerHand Family với 100 khái niệm ngẫu nhiên logic mô tả ALCIQ Avg Dep Res./Org Avg Len Res./Org Avg Acc [Min;Max] Avg Pre [Min;Max] Avg Rec [Min;Max] Avg F1 [Min;Max] Bộ chọn đơn giản 0.82/1.02 6.81/4.41 93.84±13.50 [33.69;100.0] 92.09±17.04 [32.08;100.0] 92.82±17.32 [23.08;100.0] 91.59±16.68 [27.69;100.0] Bộ chọn đơn giản mở rộng 0.84/1.02 3.40/4.41 94.60±12.20 [33.69;100.0] 92.81±15.93 [32.08;100.0] 93.14±17.17 [23.08;100.0] 92.33±16.17 [27.69;100.0] Bộ chọn đơn giản 1.41/2.60 37.02/15.97 97.17±08.61 [50.57;100.0] 95.96±14.99 [01.67;100.0] 94.95±14.40 [01.67;100.0] 94.66±14.64 [01.67;100.0] Bộ chọn đơn giản mở rộng 1.23/2.60 3.47/15.97 99.44±02.15 [83.25;100.0] 98.68±09.08 [01.67;100.0] 98.06±09.58 [01.67;100.0] 98.18±09.14 [01.67;100.0] Bộ chọn đơn giản 2.38/3.34 78.50/18.59 88.50±16.65 [27.91;100.0] 90.60±18.57 [04.55;100.0] 85.66±22.36 [07.69;100.0] 86.09±20.10 [08.70;100.0] Bộ chọn đơn giản mở rộng 2.29/3.34 10.20/18.59 92.79±14.35 [27.91;100.0] 91.99±18.40 [04.55;100.0] 91.75 ±19.82 [07.69;100.0] 90.39±19.89 [08.70;100.0] WebKB dataset PokerHand dataset Family dataset Qua quan sát Bảng 3.1 bảng khác luận án, thấy rõ ràng sử dụng thêm chọn mở rộng có hiệu cao việc giảm độ dài khái niệm cho kết phân lớp tốt Chúng kiểm tra khái niệm phổ biến/tập đối tượng cho trước tập liệu Family PokerHand Tiểu kết Chương Chương đề xuất thuật toán học khái niệm logic mô tả với Ngữ cảnh (3) sử dụng mô hai chiều Thuật toán học với chiến lược phân hoạch sử dụng kiểm nghiệm hai khía cạnh lý thuyết thực nghiệm Để q trình phân hoạch miền đạt hiệu cao, ngồi chọn chọn đơn giản, chọn mở rộng sử dụng chương trình cài đặt thuật tốn Các kết thực nghiệm chứng tỏ phương pháp đề xuất có ý nghĩa chọn mở rộng hỗ trợ tốt cho trình làm mịn phân hoạch 20 Chương HỌC KHÁI NIỆM CHO CƠ SỞ TRI THỨC TRONG LOGIC MÔ TẢ 4.1 Giới thiệu Các toán học khái niệm chương đặt theo hai ngữ cảnh sau: • Ngữ cảnh (1): Cho L logic mô tả định LΣ,Φ có tính chất mơ hình nửa hữu hạn, Ad ∈ ΣC khái niệm đại diện cho “thuộc tính định” sở tri thức KB = R, T , A0 logic mô tả L không chứa Ad Với E = E + , E − , E + E − tập không giao ΣI cho sở tri thức KB = R, T , A với A = A0 ∪ {Ad (a) | a ∈ E + } ∪ {¬Ad (a) | a ∈ E − } thỏa mãn Học khái niệm C định nghĩa Ad ngôn ngữ LΣ† ,Φ† , với Σ† ⊆ Σ \ {Ad } Φ† ⊆ Φ cho: KB |= C(a) với a ∈ E + , KB |= ơC(a) vi mi a E ã Ngữ cảnh (2): Ngữ cảnh tương tự Ngữ cảnh (1) với điều kiện thứ hai thay điều kiện yếu hơn: KB |= C(a) với a ∈ E − Lưu ý rằng, hai toán giải theo giả thuyết giới mở 4.2 Phân hoạch miền diễn dịch Chúng tơi xây dựng thuật tốn để làm mịn phân hoạch thông qua Hàm partition Hàm sử dụng hàm chooseBlockSelector để định khối chọn cần phân chia trước Ví dụ 4.1 Xét sở tri thức KB KB cho Ví dụ 1.1 diễn dịch I mơ hình KB KB sau: ∆I = {P1 , P2 , P3 , P4 , P5 , P6 }, xI = x với x ∈ {P1 , P2 , P3 , P4 , P5 , P6 }, Pub I = ∆I , Awarded I = {P1 , P4 , P6 }, UsefulPub I = {P2 , P3 , P4 , P5 , P6 }, cites I = { P1 , P2 , P1 , P3 , P1 , P4 , , P4 , P5 , P4 , P6 }, cited_by I = (cites I )−1 , hàm phần Year I đặc tả theo cá thể Cho E = E + , E − với E + = {P4 , P6 } E − = {P1 , P2 , P3 , P5 }, ngơn ngữ LΣ† ,Φ† , Σ† = {Awarded , cited_by} Φ† = ∅ Các bước làm mịn miền ∆I I theo Hàm partition mô tả sau: Y1 := ∆I , C1 := , Y := {Y1 } Phân chia khối Y1 Awarded thu được: • Y2 := {P1 , P4 , P6 }, C2 := Awarded , • Y3 := {P2 , P3 , P5 }, C3 := ¬Awarded , ⇒ Y := {Y2 , Y3 } 21 Function partition - Làm mịn miền diễn dịch logic mô tả 10 11 12 13 14 15 Input : I, Σ† , Φ† , E = E + , E − Output: Y = {Yi1 , Yi2 , , Yik } phân hoạch miền ∆I cho Y quán với E n := 1; Y1 := ∆I ; C1 := ; Y := {Y1 }; D := ∅; Tạo thêm chọn vào D; /* Định nghĩa 3.4, 3.5 và/hoặc 3.6 */ while (Y không quán với E) Yij , Sij := chooseBlockSelector(Y, D); if (Yij không bị phân chia SiIj ) then break; s := n + 1; t := n + 2; n := n + 2; Ys := Yij ∩ SiIj ; Cs := Cij Sij ; I Yt := Yij ∩ (¬Sij ) ; Ct := Cij ¬Sij ; Y := Y ∪ {Ys , Yt } \ {Yij }; Tạo thêm chọn vào D; /* Định nghĩa 3.4, 3.5 và/hoặc 3.6 */ if (Y quán với E) then return Y; else return failure; Chúng ta sử dụng chọn đơn giản ∃cited_by để phân chia Y2 : • Y4 := {P4 , P6 }, C4 := C2 ∃cited_by , • Y5 := {P1 }, C5 := C2 ¬∃cited_by , ⇒ Y := {Y3 , Y4 , Y5 } Phân hoạch đạt Y = {Y3 , Y4 , Y5 } quán với E 4.3 Học khái niệm logic mô tả với Ngữ cảnh (1) 4.3.1 Thuật toán BBCL Ý tưởng thuật tốn BBCL để giải tốn sử dụng mơ hình KB kết hợp với mơ hai chiều mơ hình định cho việc tìm kiếm khái niệm C Thuật toán sử dụng Hàm partition nêu Mục 4.2 để làm mịn miền ∆I diễn dịch I mơ hình KB 4.3.2 Thuật toán dual-BBCL Thuật toán dual-BBCL sử dụng để học khái niệm logic mô tả với Ngữ cảnh (1) Bằng cách hoán đổi tập E + E − cho nhau, sau áp dụng Thuật tốn BBCL nhận khái niệm Crs lấy kết trả khái niệm ¬Crs 4.3.3 Tính đắn thuật tốn BBCL Mệnh đề 4.1 (Tính đắn thuật tốn BBCL) Thuật tốn BBCL đắn Nghĩa là, thuật toán BBCL trả khái niệm Crs Crs lời giải toán học khái niệm cho sở tri thức logic mô tả với Ngữ cảnh (1) 22 Thuật toán 4.1: BBCL - Học khái niệm logic mô tả với Ngữ cảnh (1) Input : KB, Σ† ⊆ Σ \ {Ad }, Φ† ⊆ Φ, E = E + , E − , k Output: Khái niệm C LΣ† ,Φ† cho: • KB |= C(a) với a ∈ E + , • KB |= ¬C(a) với a ∈ E − 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 C := ∅; C0 := ∅; while not (too hard to extend C) Xây dựng mơ hình hữu hạn (tiếp theo) I KB I = I|k ; Y := partition (I, Σ† , Φ† , E); /* phân hoạch ∆I theo Hàm partition */ foreach Yij ∈ Y cho ∃a ∈ E +: aI ∈ Yij ∀a ∈ E −: aI ∈ Yij if (KB |= ¬Cij (a) với a ∈ E − ) then if (KB |= (Cij C)) then C := C ∪ {Cij }; else C0 := C0 ∪ {Cij }; if (KB |= ( C)(a) với a ∈ E + ) then go to 20; while not (too hard to extend C) D := D1 D2 · · · Dl , với D1 , D2 , , Dl chọn ngẫu nhiên từ C0 ; if (KB |= ¬D(a) với a ∈ E − KB |= (D C)) then C := C ∪ {D}; if (KB |= ( C)(a) với a ∈ E + ) then go to 20; return failure; foreach D ∈ C if (KB |= (C \ {D})(a) với a ∈ E + ) then C := C \ {D}; C := C; 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 sở tri thức KB = R, T , A0 cho Ví dụ 1.1 E = E + , E − với E + = {P4 , P6 }, E − = {P1 , P2 , P3 , P5 }, Σ† = {Awarded , cited_by} Φ† = ∅ Học định nghĩa cho Ad với KB = R, T , A , A = A0 ∪ {Ad (a) | a ∈ E + } ∪ {¬Ad (a) | a ∈ E − } Thuật toán BBCL thực sau: C := ∅, C0 := ∅ KB có nhiều mơ hình, mơ hình I đặc tả Ví dụ 4.1 Áp dụng Hàm partition để {Y3 , Y4 , Y5 } quán với E Y3 = {P2 , P3 , P5 }, C4 ≡ Awarded ∃cited_by làm mịn miền ∆I I , ta phân hoạch Y = tương ứng với khái niệm đặc trưng C3 , C4 , C5 , Y4 = {P4 , P6 }, Y5 = {P1 } C3 ≡ ¬Awarded , , C5 ≡ ¬Awarded ∃cited_by 23 Vì Y4 ⊆ E + nên ta xem xét C4 ≡ Awarded ∃cited_by Vì KB |= ¬C4 (a) với a ∈ E − nên ta thêm C4 vào C Do đó, ta có C ≡ {C4 } C ≡ C4 Vì KB |= ( C)(a) với a ∈ E + nên ta có C ≡ C ≡ Awarded ∃cited_by Do khái niệm C dạng chuẩn đơn giản nên kết trả Crs ≡ Awarded ∃cited_by Ví dụ 4.3 Xét thuật tốn dual-BBCL Ví dụ 4.2 hoán đổi E + E − với Thuật toán dual-BBCL thực ba bước giống Ví dụ 4.2 bước sau: Vì Y3 ⊆ E + nên ta xem xét C3 ≡ ¬Awarded Vì KB |= ¬C3 (a) với a ∈ E − nên ta thêm C3 vào C Do đó, ta có C = {C3 } Vì Y5 ⊆ E + nên ta xem xét C5 ≡ Awarded ¬∃cited_by Vì KB |= ¬C5 (a) với a ∈ E − C5 không bị bao hàm C dựa KB nên ta thêm C5 vào C Do đó, ta có C = {C3 , C5 } C ≡ C3 C5 C)(a) với a ∈ E + nên ta có C ≡ C ≡ ¬Awarded (Awarded ¬∃cited_by ) Chuẩn hóa đơn giản khái niệm C ta kết trả Crs ≡ ¬Awarded ¬∃cited_by Vì KB |= ( Nếu muốn lấy kết Ví dụ 4.2 lấy phủ định Crs Lúc kết ¬Crs ≡ ¬(¬Awarded ¬∃cited_by ) ≡ Awarded ∃cited_by 4.4 Học khái niệm logic mơ tả với Ngữ cảnh (2) 4.4.1 Thuật tốn BBCL2 Phương pháp học khái niệm cho sở tri thức logic mơ tả với Ngữ cảnh (2) trình bày chi tiết thơng qua Thuật tốn 4.2 4.4.2 Tính đắn thuật tốn BBCL2 Mệnh đề 4.2 (Tính đắn thuật toán BBCL2) Thuật toán BBCL2 đắn Nghĩa là, thuật toán BBCL2 trả khái niệm Crs Crs lời giải toán học khái niệm cho sở tri thức logic mô tả với Ngữ cảnh (2) 4.4.3 Ví dụ minh họa Ví dụ 4.4 Xét sở tri thức KB = R, T , A0 cho Ví dụ 1.1 E = E + , E − , Σ† , Φ† Ví dụ 4.2 Đặt KB = R, T , A với A = A0 ∪ {Ad (a) | a ∈ E + } ∪ {¬Ad (a) | a ∈ E − } Thuật toán BBCL2 thực ba bước giống Ví dụ 4.2 (có bổ sung thêm E0− := ∅) bước sau: Vì Y3 ⊆ E − nên ta xem xét C3 ≡ ¬Awarded Vì KB |= ¬C3 (a) với a ∈ E + nên ta thêm ¬C3 vào C thêm phần tử Y3 vào E0− Do đó, ta có C = {C3 } E0− = {P2 , P3 , P5 } Vì Y5 ⊆ E − nên ta xem xét C5 ≡ Awarded ¬∃cited_by Vì KB |= ¬C5 (a) với a ∈ E + C không bị bao hàm C5 dựa KB nên ta thêm ¬C5 vào C Do đó, ta có C = {¬C3 , ¬C5 } E0− = {P1 , P2 , P3 , P5 } Vì E0− = E − nên ta có C ≡ C ≡ ¬¬Awarded ¬(Awarded ¬∃cited_by ) Rút gọn khái niệm C ta kết trả Crs ≡ Awarded ∃cited_by 24 Thuật toán 4.2: BBCL2 - Học khái niệm logic mô tả với Ngữ cảnh (2) Input : KB, Σ† , Φ† , E = E + , E − , k Output: Khái niệm C cho: • KB |= C(a) với a ∈ E + , • KB |= C(a) for all a ∈ E − 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 C := ∅; C0 := ∅; E0− := ∅; while not (too hard to extend C) (E0− = E − ) Xây dựng mơ hình hữu hạn (tiếp theo) I KB I = I|k ; Y :=partition (I, Σ† , Φ† , E); /* phân hoạch ∆I theo Hàm partition */ foreach Yij ∈ Y cho ∃a ∈ E −: aI ∈ Yij ∀a ∈ E +: aI ∈ Yij if (KB |= ¬Cij (a) với a ∈ E + ) then if (KB |= ( C ¬Cij )) then C := C ∪ {¬Cij }; E0− := E0− ∪ {a ∈ E − | aI ∈ Yij }; else C0 := C0 ∪ {¬Cij }; while not (too hard to extend C) (E0− = E − ) D := D1 D2 · · · Dl , với D1 , D2 , , Dl chọn ngẫu nhiên từ C0 ; if (KB |= D(a) với a ∈ E + ) then if (KB |= ( C) D) (∃a ∈ E − \ E0− : KB |= ( C D)(a)) then C := C ∪ {D}; E0− := E0− ∪ {a | a ∈ E − \ E0− , KB |= ( C)(a)}; if (E0− = E − ) then foreach (D ∈ C) if (KB |= (C \ {D})(a) với a ∈ E − ) then C := C \ {D}; C := C; return Crs := simplify (C); else return failure; /* rút gọn khái niệm C */ Tiểu kết Chương Chương trình bày phương pháp làm mịn phân hoạch miền diễn dịch logic mơ tả sở Thuật tốn 3.1 Tiếp đó, chúng tơi đề xuất thuật tốn BBCL, dual-BBCL BBCL2 để giải hai toán học khái niệm cho sở tri thức logic mô tả với Ngữ cảnh (1) Ngữ cảnh (2) Ý tưởng thuật tốn sử dụng mơ hình sở tri thức kết hợp với mơ hai chiều mơ hình định để tìm kiếm khái niệm kết Tính thuật tốn BBCL BBCL2 chứng minh thông qua bổ đề tương ứng Các thuật tốn áp dụng cho lớp lớn logic mô tả mở rộng ALC Σ,Φ có tính chất mơ hình hữu hạn nửa hữu hạn, Φ ⊆ {I, F, N , Q, O, U, Self} 25 KẾT LUẬN Kết luận Logic mơ tả ngày khẳng định vai trị quan trọng hệ thống biểu diễn suy luận tri thức Kể từ logic mô tả xem tảng ngôn ngữ OWL (một ngôn ngữ sử dụng để mơ hình hóa hệ thống ngữ nghĩa ontology theo khuyến nghị W3C), logic mô tả nhiều nhà khoa học quan tâm nghiên cứu Đối với hệ thống ngữ nghĩa, việc tìm kiếm khái niệm phù hợp, xây dựng định nghĩa cho khái niệm để đặc tả hệ thống vấn đề đặt cách tự nhiên Học khái niệm logic mô tả giải pháp để tìm kiếm xây dựng định nghĩa cho khái niệm Với mục đích đó, luận án tập trung nghiên cứu tốn học khái niệm logic mơ tả sử dụng ngữ cảnh khác Kết nghiên cứu luận án tóm tắt sau: Xây dựng ngôn ngữ logic mô tả LΣ,Φ dựa ngôn ngữ ALC reg với tập đặc trưng mở rộng gồm I , O, N , Q, F , U , Self Ngồi ngơn ngữ xây dựng cịn cho phép sử dụng thuộc tính phần tử ngôn ngữ nhằm mô tả hệ thống thông tin phù hợp với thực tế Thông qua ngôn ngữ LΣ,Φ , luận án xây dựng mô hai chiều lớp logic mở rộng nghiên cứu Các định lý, bổ đề, hệ liên quan đến mô hai chiều tính bất biến mơ hai chiều phát triển chứng minh lớp logic mở rộng Phát triển thuật tốn học khái niệm cho hệ thống thơng tin logic mô tả với Ngữ cảnh (3) Các chọn bản, chọn đơn giản chọn mở rộng sử dụng trình làm mịn phân hoạch Các chiến lược tìm kiếm đề xuất dựa vào gia lượng thơng tin tính đơn giản khái niệm Xây dựng thuật toán BBCL, dual-BBCL, BBCL2 nhằm giải toán học khái niệm cho sở tri thức logic mô tả với Ngữ cảnh (1) Ngữ cảnh (2) Những vấn đề cần tiếp tục nghiên cứu Từ kết đạt luận án, vấn đề đặt cần quan tâm nghiên cứu thời gian tới sau: Xây dựng chiến lược học khác thông qua độ đo việc định khối nên phân hoạch trước So sánh chiến lược học với Xây dựng module học khái niệm logic mô tả với ngữ cảnh khác API cho phép tích hợp vào hệ thống khác Nghiên cứu 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ở sở tri thức logic mô tả Nghiên cứu khả học xác khái niệm cho logic mô tả khác 26 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 Programming, 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 description 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 Szalas 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 [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 DANH MỤC CÁC CƠNG TRÌNH CỦA TÁC GIẢ T.-L Tran, Q.-T Ha, T.-L.-G Hoang, L A Nguyen, H S Nguyen, and A Szalas Concept learning for description logic-based information systems In Proceedings of the 2012 Fourth International Conference on Knowledge and Systems Engineering, KSE’2012, pages 65–73 IEEE Computer Society, 2012 (ISBN: 9781-4673-2171-6) Q.-T Ha, T.-L.-G Hoang, L A Nguyen, H S Nguyen, A Szalas, 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) Trần Thanh Lương, Hoàng Thị Lan Giao Áp dụng độ đo entropy để phân hoạch khối cho hệ thống thông tin dựa 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ông nghệ Thông tin Truyền thông, trang 11–18, Nhà xuất Khoa học Kỹ thuật, 2013 T.-L Tran, Q.-T Ha, T.-L.-G Hoang, L A Nguyen, and H S Nguyen Bisimulationbased concept learning in description logics In Proceedings of CS&P’2013, pages 421–433 CEURWS.org, 2013 (ISBN: 978-83-62582-42-6) 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-065694) T.-L Tran, Q.-T Ha, T.-L.-G Hoang, L A Nguyen, and H S Nguyen Bisimulationbased concept learning in description logics Fundam Inform., Vol 133, No 2-3, pages 287–303, 2014 (ISSN: 0169-2968) 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 University, Vol 98, No 8, pages 97–101, 2014 (ISSN: 1859-1388) T.-L Tran, L A Nguyen, and T.-L.-G Hoang Bisimulation-based concept learning 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 ... ngữ cho tốn học máy logic mô tả cách sử dụng mô hai chiều 12 Chương 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... tổng quát để học khái niệm cho hệ thống thông tin logic mô tả Divroodi [5] cộng nghiên cứu khả học logic mô tả sử dụng mô hai chiều Các cơng trình nghiên cứu tốn học khái niệm logic mô tả với Ngữ... lớp logic mô tả đề cập sử dụng để mơ hình hóa tính khơng phân biệt đối tượng làm sở cho thuật toán học khái niệm logic mơ tả; • Phát triển thuật tốn học khái niệm dựa mơ hai chiều cho hệ thống thông