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

ĐẠ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 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ế 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 |= C(a) với mọi a ∈ E+, và 2. KB |= ¬C(a) với mọi a ∈ 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 |= C(a) với mọi a ∈ E+, và 2. KB 6|= C(a) với mọi a ∈ 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 |= C(a) với mọi a ∈ E+, và 2. I |= ¬C(a) với mọi a ∈ E−. Chú ý rằng I |= ¬C(a) tương đồng với I 6|= 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 đã đề 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 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 ∈ Σ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 ∈ ΣR là một vai trò thì >, ⊥, ¬C, C u D, C unionsqD, ∃r.C và ∀r.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 = 〈∆I, ·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 ∈ ΣI thành một phần tử aI ∈ ∆I , mỗi tên khái niệm A ∈ ΣC thành một tập AI ⊆ ∆I và mỗi tên vai trò r ∈ ΣR thành một quan hệ hai ngôi rI ⊆ ∆I ×∆I . 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 \ CI , (∃r.C)I = {x ∈ ∆I | ∃y ∈ ∆I [rI(x, y) ∧ CI(y)]}, (C uD)I = CI ∩DI , (∀r.C)I = {x ∈ ∆I | ∀y ∈ ∆I [rI(x, y)⇒ CI(y)]}, (C unionsqD)I = CI ∪DI .  1.1.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 • 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 ∈ ΣR thì r là một vai trò của ALCreg, • nếu A ∈ Σ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 unionsq S, R∗, C? là các vai trò của ALCreg, – >, ⊥, ¬C, C uD, C unionsqD, ∃R.C và ∀R.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 unionsq S)I = RI ∪ SI , (R∗)I = (RI)∗, εI = {〈x, x〉 | x ∈ ∆I}, (C?)I = {〈x, x〉 | CI(x)}. 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 ∈ ΣoR thì r là một vai trò đối tượng của LΣ,Φ, • nếu A ∈ ΣC thì A là một khái niệm của LΣ,Φ, • nếu A∈ΣA \ΣC và d∈range(A) thì A = d và A 6= d là các khái niệm của LΣ,Φ, • nếu A ∈ ΣnA và d ∈ 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 ∈ ΣoR, σ ∈ ΣdR, a ∈ ΣI và n là một số tự nhiên thì – ε, R ◦ S , R unionsq S, R∗ và C? là các vai trò đối tượng của LΣ,Φ, 4 – >, ⊥, ¬C, C uD, C unionsqD, ∃R.C và ∀R.C là các khái niệm của LΣ,Φ, – nếu d ∈ range(σ) thì ∃σ.{d} là một khái niệm của LΣ,Φ, – nếu I ∈ Φ thì R− là một vai trò đối tượng của LΣ,Φ, – nếu O ∈ Φ thì {a} là một khái niệm của LΣ,Φ, – nếu F ∈ Φ thì ≤1 r là một khái niệm của LΣ,Φ, – nếu {F , I} ⊆ Φ thì ≤1 r− là một khái niệm của LΣ,Φ, – nếu N ∈ Φ thì ≥n r và ≤n r là các khái niệm của LΣ,Φ, – nếu {N , I} ⊆ Φ thì ≥n r− và ≤n r− là các khái niệm của LΣ,Φ, – nếu Q ∈ Φ thì ≥n r.C và ≤n r.C là các khái niệm của LΣ,Φ, – nếu {Q, I} ⊆ Φ thì ≥n r−.C và ≤n r−.C là các khái niệm của LΣ,Φ, – nếu U ∈ Φ thì U là một vai trò đối tượng của LΣ,Φ, – nếu Self ∈ Φ thì ∃r.Self là một khái niệm của LΣ,Φ.  Định nghĩa 1.5 (Ngữ nghĩa củaLΣ,Φ). Một diễn dịch trongLΣ,Φ là một bộ I=〈∆I, ·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 ∈ ΣI thành một phần tử aI ∈ ∆I , mỗi tên khái niệm A ∈ ΣC thành một tập AI ⊆ ∆I , mỗi thuộc tính A ∈ ΣA \ ΣC thành một hàm từng phần AI : ∆I → range(A), mỗi tên vai trò đối tượng r ∈ ΣoR thành một quan hệ hai ngôi rI ⊆ ∆I × ∆I và mỗi vai trò dữ liệu σ ∈ ΣdR thành một quan hệ hai ngôi σI ⊆ ∆I × range(σ). Hàm diễn dịch ·I đượ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 unionsq S)I = RI ∪ SI (C uD)I = CI ∩DI (R∗)I = (RI)∗ (R−)I = (RI)−1 (C unionsqD)I = CI ∪DI (C?)I = {〈x, x〉 | CI(x)} εI = {〈x, x〉 | x ∈ ∆I} {a}I = {aI} UI = ∆I ×∆I (A ≤ d)I = {x ∈ ∆I | AI(x) xác định và AI(x) ≤ d} >I = ∆I ⊥I = ∅ (A ≥ d)I = {x ∈ ∆I | AI(x) xác định và AI(x) ≥ d} (¬C)I = ∆I \ CI (A = d)I = {x ∈ ∆I | AI(x) = d} (A 6= d)I = (¬(A = d))I (A d)I = ((A ≥ d) u (A 6= d))I (∀R.C)I = {x ∈ ∆I | ∀y [RI(x, y)⇒ CI(y)]} (∃r.Self)I = {x ∈ ∆I | rI(x, x)} (∃R.C)I = {x ∈ ∆I | ∃y [RI(x, y) ∧ CI(y)]} (∃σ.{d})I = {x ∈ ∆I | σI(x, d)} (≥nR.C)I = {x ∈ ∆I | #{y | RI(x, y) ∧ CI(y)} ≥ n} (≥nR)I = (≥nR.>)I (≤nR.C)I = {x ∈ ∆I | #{y | RI(x, y) ∧ CI(y)} ≤ n} (≤nR)I = (≤nR.>)I Hình 1.1: 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 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 ∪ {r− | r ∈ ΣoR}. 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 ∈ Σ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 ∈ Σ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 = 〈R, T ,A〉, trong đó R là một RBox, T là một TBox và A là một ABox trong LΣ,Φ.  6 Đị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 |= R (tương ứng, I |= T , I |= 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 = 〈R, T ,A〉, ký hiệu là I |= 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: Φ = {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− v cited_by , cited_by− v cites , Irr(cites)}, T = {> v Pub,UsefulPub ≡ ∃cited_by .>}, A′0 = {Awarded(P1),¬Awarded(P2),¬Awarded(P3),Awarded(P4), ¬Awarded(P5),Awarded(P6),Year(P1) = 2010,Year(P2) = 2009, Year(P3) = 2008,Year(P4) = 2007,Year(P5) = 2006,Year(P6) = 2006, cites(P1,P2), cites(P1,P3), cites(P1,P4), cites(P1,P6), cites(P2,P3), cites(P2,P4), cites(P2,P5), cites(P3,P4), cites(P3,P5), cites(P3,P6), cites(P4,P5), cites(P4,P6)}, A0 =A′0 ∪ {(¬∃cited_by .>)(P1), (∀cited_by .{P2,P3,P4})(P5)}. Lúc đó KB′0 = 〈R, T ,A′0〉 và KB0 = 〈R, T ,A0〉 là các cơ sở tri thức trong LΣ,Φ. Tiên đề > v Pub để chỉ ra rằng miền của bất kỳ mô hình nào của KB′0 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 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à Σ† là các bộ ký tự logic mô tả sao cho Σ† ⊆ Σ, Φ và Φ† là tập các đặc trưng của logic mô tả sao cho Φ† ⊆ Φ, I và I ′ là các diễn dịch trong LΣ,Φ. Một LΣ†,Φ†-mô phỏng hai chiều giữa I và I ′ là một quan hệ hai ngôi Z ⊆ ∆I×∆I′ thỏa các điều kiện sau với mọi a ∈ Σ†I , A ∈ Σ†C , B ∈ Σ†A \Σ†C , r ∈ Σ†oR, σ ∈ Σ†dR, d ∈ range(σ), x, y ∈ ∆I , x′, y′ ∈ ∆I ′ : Z(aI, aI ′ ) (2.1) Z(x, x′)⇒ [AI(x)⇔ AI′(x′)] (2.2) Z(x, x′)⇒ [BI(x) = BI′(x′) hoặc cả hai đều không xác định] (2.3) [Z(x, x′) ∧ rI(x, y)]⇒ ∃y′ ∈ ∆I′ | [Z(y, y′) ∧ rI′(x′, y′)] (2.4) [Z(x, x′) ∧ rI′(x′, y′)]⇒ ∃y ∈ ∆I | [Z(y, y′) ∧ rI(x, y)] (2.5) Z(x, x′)⇒ [σI(x, d)⇔ σI′(x′, d)], (2.6) nếu I ∈ Φ† thì [Z(x, x′) ∧ rI(y, x)]⇒ ∃y′ ∈ ∆I′ | [Z(y, y′) ∧ rI′(y′, x′)] (2.7) [Z(x, x′) ∧ rI′(y′, x′)]⇒ ∃y ∈ ∆I | [Z(y, y′) ∧ rI(y, x)], (2.8) nếu O ∈ Φ† thì Z(x, x′)⇒ [x = aI ⇔ x′ = aI′], (2.9) nếu N ∈ Φ† thì Z(x, x′)⇒ #{y ∈ ∆I | rI(x, y)} = #{y′ ∈ ∆I′ | rI′(x′, y′)}, (2.10) nếu {N , I} ⊆ Φ† thì Z(x, x′)⇒ #{y ∈ ∆I | rI(y, x)} = #{y′ ∈ ∆I′ | rI′(y′, x′)}, (2.11) nếu F ∈ Φ† thì Z(x, x′)⇒ [#{y ∈ ∆I | rI(x, y)} ≤ 1⇔ #{y′ ∈ ∆I′ | rI′(x′, y′)} ≤ 1], (2.12) 8 nếu {F , I} ⊆ Φ† thì Z(x, x′)⇒ [#{y ∈ ∆I | rI(y, x)} ≤ 1⇔ #{y′ ∈ ∆I′ | rI′(y′, x′)} ≤ 1], (2.13) nếu Q ∈ Φ† thì nếu Z(x, x′) thỏa mãn thì với mọi r ∈ Σ†oR, tồn tại một song