Tóm tắt Luận án Tiến sĩ Máy tính: Học khái niệm cho các hệ thống thông tin dựa trên logic mô tả

Chia sẻ: Na Na | Ngày: | Loại File: PDF | Số trang:31

Thêm vào BST

Báo xấu

52
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận án 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ả. Luận án 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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tóm tắt Luận án Tiến sĩ Máy tính: 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à Szalas đã á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à Szalas [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 t D, ∃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 = h∆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 \ C I , (∃r.C)I = {x ∈ ∆I | ∃y ∈ ∆I [rI (x, y) ∧ C I (y)]}, (C u D)I = C I ∩ DI , (∀r.C)I = {x ∈ ∆I | ∀y ∈ ∆I [rI (x, y) ⇒ C I (y)]}, (C t D)I = C I ∪ 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ả ALC reg Định nghĩa 1.3 (Cú pháp của ALC reg ). 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 ALC reg 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 ALC reg , • nếu A ∈ ΣC thì A là một khái niệm của ALC reg , • 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 ALC reg , – >, ⊥, ¬C , C u D, C t D, ∃R.C và ∀R.C là các khái niệm của ALC reg . Diễn dịch của các vai trò phức trong ALC reg được xác định như sau: (R ◦ S)I = RI ◦ S I , (R t S)I = RI ∪ S I , (R∗ )I = (RI )∗ , εI = {hx, xi | x ∈ ∆I }, (C?)I = {hx, xi | C I (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 ALC reg . 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, A ≥ d và 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 t S , R∗ và C? là các vai trò đối tượng của LΣ,Φ , 4
– >, ⊥, ¬C , C u D, C t D, ∃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ủa LΣ,Φ ). Một diễn dịch trong LΣ,Φ là một bộ I = h∆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 ◦ S I (R∗ )I = (RI )∗ (C?)I = {hx, xi | C I (x)} (R t S)I = RI ∪ S I (R− )I = (RI )−1 εI = {hx, xi | x ∈ ∆I } (C u D)I = C I ∩ DI (C t D)I = C I ∪ DI {a}I = {aI } U I = ∆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 \ C I (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 (A > d)I = ((A ≥ d) u (A 6= 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 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 = hR, T , Ai, 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 = hR, T , Ai, 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.>}, A00 = {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 )}, 0 A0 = A0 ∪ {(¬∃cited_by.>)(P1 ), (∀cited_by.{P2 , P3 , P4 })(P5 )}. Lúc đó KB 00 = hR, T , A00 i và KB 0 = hR, T , A0 i 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 00 hoặc KB 0 đề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 ALC reg 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 0 là các diễn dịch trong LΣ,Φ . Một LΣ† ,Φ† -mô phỏng hai chiều giữa I và I 0 là một quan hệ 0 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 , 0 r ∈ Σ†oR , σ ∈ Σ†dR , d ∈ range(σ), x, y ∈ ∆I , x0 , y 0 ∈ ∆I : 0 Z(aI , aI ) (2.1) 0 Z(x, x0 ) ⇒ [AI (x) ⇔ AI (x0 )] (2.2) 0 Z(x, x0 ) ⇒ [B I (x) = B I (x0 ) hoặc cả hai đều không xác định] (2.3) 0 0 [Z(x, x0 ) ∧ rI (x, y)] ⇒ ∃y 0 ∈ ∆I | [Z(y, y 0 ) ∧ rI (x0 , y 0 )] (2.4) 0 [Z(x, x0 ) ∧ rI (x0 , y 0 )] ⇒ ∃y ∈ ∆I | [Z(y, y 0 ) ∧ rI (x, y)] (2.5) 0 Z(x, x0 ) ⇒ [σ I (x, d) ⇔ σ I (x0 , d)], (2.6) nếu I ∈ Φ† thì 0 0 [Z(x, x0 ) ∧ rI (y, x)] ⇒ ∃y 0 ∈ ∆I | [Z(y, y 0 ) ∧ rI (y 0 , x0 )] (2.7) 0 [Z(x, x0 ) ∧ rI (y 0 , x0 )] ⇒ ∃y ∈ ∆I | [Z(y, y 0 ) ∧ rI (y, x)], (2.8) nếu O ∈ Φ† thì 0 Z(x, x0 ) ⇒ [x = aI ⇔ x0 = aI ], (2.9) nếu N ∈ Φ† thì 0 0 Z(x, x0 ) ⇒ #{y ∈ ∆I | rI (x, y)} = #{y 0 ∈ ∆I | rI (x0 , y 0 )}, (2.10) nếu {N , I} ⊆ Φ† thì 0 0 Z(x, x0 ) ⇒ #{y ∈ ∆I | rI (y, x)} = #{y 0 ∈ ∆I | rI (y 0 , x0 )}, (2.11) nếu F ∈ Φ† thì 0 0 Z(x, x0 ) ⇒ [#{y ∈ ∆I | rI (x, y)} ≤ 1 ⇔ #{y 0 ∈ ∆I | rI (x0 , y 0 )} ≤ 1], (2.12) 8
nếu {F, I} ⊆ Φ† thì 0 0 Z(x, x0 ) ⇒ [#{y ∈ ∆I | rI (y, x)} ≤ 1 ⇔ #{y 0 ∈ ∆I | rI (y 0 , x0 )} ≤ 1], (2.13) nếu Q ∈ Φ† thì nếu Z(x, x0 ) thỏa mãn thì với mọi r ∈ Σ†oR , tồn tại một song ánh 0 0 (2.14) h : {y ∈ ∆I | rI (x, y)} → {y 0 ∈ ∆I | rI (x0 , y 0 )} sao cho h ⊆ Z , nếu {Q, I} ⊆ Φ† thì nếu Z(x, x0 ) thỏa mãn thì với mọi r ∈ Σ†oR , tồn tại một song ánh 0 0 (2.15) h : {y ∈ ∆I | rI (y, x)} → {y 0 ∈ ∆I | rI (y 0 , x0 )} sao cho h ⊆ Z , nếu U ∈ Φ† thì 0 ∀x ∈ ∆I , ∃x0 ∈ ∆I , Z(x, x0 ) (2.16) 0 ∀x0 ∈ ∆I , ∃x ∈ ∆I , Z(x, x0 ), (2.17) nếu Self ∈ Φ† 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. 1. Quan hệ {hx, xi | x ∈ ∆I } là một LΣ† ,Φ† -mô phỏng hai chiều giữa I và I . 2. Nếu Z là một LΣ† ,Φ† -mô phỏng hai chiều giữa I và I 0 thì Z −1 cũng là một LΣ† ,Φ† -mô phỏng hai chiều giữa I 0 và I . 3. Nếu Z1 là một LΣ† ,Φ† -mô phỏng hai chiều giữa I0 và I1 , Z2 là một LΣ† ,Φ† -mô phỏng hai chiều giữa I1 và I2 thì Z1 ◦ Z2 là một LΣ† ,Φ† -mô phỏng hai chiều giữa I0 và I2 . 4. Nếu Z là một tập các LΣ† ,Φ† -mô phỏng hai chiều giữa I và I 0 thì Z là một S LΣ† ,Φ† -mô phỏng hai chiều giữa I và I 0 . 2.2.2. Quan hệ tương tự hai chiều và quan hệ tương đương Định nghĩa 2.2. Cho I và I 0 là các diễn dịch trong ngôn ngữ LΣ,Φ . Ta nói rằng I LΣ† ,Φ† -tương tự hai chiều với I 0 nếu tồn tại một LΣ† ,Φ† -mô phỏng hai chiều giữa I và I 0 . Định nghĩa 2.3. Cho I và I 0 là các diễn dịch trong ngôn ngữ LΣ,Φ , x ∈ ∆I và 0 x0 ∈ ∆I . Ta nói rằng x LΣ† ,Φ† -tương tự hai chiều với x0 nếu tồn tại một LΣ† ,Φ† -mô phỏng hai chiều giữa I và I 0 sao cho Z(x, x0 ) thỏa mãn. Định nghĩa 2.4. Cho I và I 0 là các diễn dịch trong ngôn ngữ LΣ,Φ , x ∈ ∆I và 0 x0 ∈ ∆I . Ta nói rằng x LΣ† ,Φ† -tương đương với x0 nếu với mọi khái niệm C của LΣ† ,Φ† , 0 x ∈ C I khi và chỉ khi x0 ∈ C I . 9
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ò Bổ đề 2.2. Cho I và I 0 là các diễn dịch trong ngôn ngữ LΣ,Φ , Z là một LΣ† ,Φ† -mô phỏng hai chiều giữa I và I 0 . Lúc đó, với mọi khái niệm C của LΣ† ,Φ† , mọi vai trò 0 đối tượng R của LΣ† ,Φ† , mọi đối tượng x, y ∈ ∆I , x0 , y 0 ∈ ∆I và mọi cá thể a ∈ Σ†I , các điều kiện sau sẽ được thỏa mãn: 0 Z(x, x0 ) ⇒ [C I (x) ⇔ C I (x0 )] (2.19) 0 0 [Z(x, x0 ) ∧ RI (x, y)] ⇒ ∃y 0 ∈ ∆I | [Z(y, y 0 ) ∧ RI (x0 , y 0 )] (2.20) 0 [Z(x, x0 ) ∧ RI (x0 , y 0 )] ⇒ ∃y ∈ ∆I | [Z(y, y 0 ) ∧ RI (x, y)], (2.21) nếu O ∈ Φ† thì: 0 0 Z(x, x0 ) ⇒ [RI (x, aI ) ⇔ RI (x0 , aI )]. (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 LΣ† ,Φ† -mô phỏng hai chiều nếu Z(x, x0 ) thỏa mãn thì x ∈ C I khi và chỉ khi x0 ∈ C I với mọi diễn dịch I , I 0 trong ngôn ngữ LΣ,Φ và với mọi LΣ† ,Φ† -mô phỏng hai chiều Z giữa I và I 0 , trong đó Σ† ⊆ Σ, Φ† ⊆ Φ. Định lý 2.1. Tất cả các khái niệm của LΣ† ,Φ† đều bất biến đối với LΣ† ,Φ† -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Σ† ,Φ† . 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Σ† ,Φ† được gọi là bất biến đối với LΣ† ,Φ† -mô phỏng hai chiều nếu với mọi diễn dịch I và I 0 trong LΣ,Φ tồn tại một LΣ† ,Φ† -mô phỏng hai chiều giữa I và I 0 sao cho I là mô hình của T (tương ứng, A) khi và chỉ khi I 0 là mô hình của T (tương ứng, A). Hệ quả 2.1. Nếu U ∈ Φ† thì tất cả các TBox trong LΣ† ,Φ† đều bất biến đối với LΣ† ,Φ† -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Σ† ,Φ† nếu với mọi đối tượng x ∈ ∆I tồn tại cá thể a ∈ Σ†I , các đối tượng x0 , x1 , . . . , xk ∈ ∆I và các vai trò đối tượng cơ bản R1 , R2 , . . . , Rk của LΣ† ,Φ† với k ≥ 0 sao cho x0 = aI , xk = x và RiI (xi−1 , xi ) thỏa mãn với mọi 1 ≤ i ≤ k [6]. Định lý 2.2. Cho T là một TBox trong LΣ† ,Φ† , I và I 0 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Σ† ,Φ† sao cho tồn tại một LΣ† ,Φ† -mô phỏng hai chiều giữa I và I 0 . Lúc đó I là mô hình của T khi và chỉ khi I 0 là mô hình của T . 10
Định lý 2.3. Cho A là một ABox trong LΣ† ,Φ† . Nếu O ∈ Φ† 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Σ† ,Φ† -mô phỏng hai chiều. Hệ quả 2.2. Cho cơ sở tri thức KB = hR, T , Ai trong LΣ† ,Φ† sao cho R = ∅ và giả thiết O ∈ Φ† hoặc A chỉ chứa các khẳng định có dạng C(a), I và I 0 là các diễn dịch kết nối đối tượng được trong LΣ† ,Φ† sao cho tồn tại một LΣ† ,Φ† -mô phỏng hai chiều giữa I và I 0 . Lúc đó I là mô hình của KB khi và chỉ khi I 0 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 hữu hạn ảnh) đối với LΣ† ,Φ† nếu với mọi x ∈ ∆I và với mọi vai trò r ∈ Σ†oR thì: • tập {y ∈ ∆I | rI (x, y)} là hữu hạn, • nếu I ∈ Φ† thì tập {y ∈ ∆I | rI (y, x)} là hữu hạn. Định lý 2.4 (Tính chất Hennessy-Milner). 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 0 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Σ† ,Φ† , 0 sao cho với mọi a ∈ Σ†I , aI LΣ† ,Φ† -tương đương với aI . Giả thiết rằng U 6∈ Φ† hoặc 0 Σ†I 6= ∅. Lúc đó, x ∈ ∆I LΣ† ,Φ† -tương đương với x0 ∈ ∆I khi và chỉ khi tồn tại một LΣ† ,Φ† -mô phỏng hai chiều Z giữa I và I 0 sao cho Z(x, x0 ) thỏa mãn. Hệ quả 2.3. 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 0 là các diễn dịch trong LΣ,Φ thỏa điều kiện phân nhánh hữu hạn đối với LΣ† ,Φ† . Giả thiết rằng Σ†I 6= ∅ và với 0 0 mọi a ∈ Σ†I , aI LΣ† ,Φ† -tương đương với aI . Lúc đó, quan hệ {hx, x0 i ∈ ∆I × ∆I | x LΣ† ,Φ† -tương đương với x0 } là một LΣ† ,Φ† -mô phỏng hai chiều giữa I và I 0 . 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Σ† ,Φ† -tự mô phỏng hai chiều của I là một LΣ† ,Φ† -mô phỏng hai chiều giữa I và chính nó. Một LΣ† ,Φ† -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 LΣ† ,Φ† -tự mô phỏng hai chiều Z 0 của I thì Z 0 ⊆ Z . Cho I là một diễn dịch trong LΣ,Φ , chúng ta ký hiệu LΣ† ,Φ† -tự mô phỏng hai chiều lớn nhất của I là ∼Σ† ,Φ† ,I , và ký hiệu quan hệ hai ngôi ≡Σ† ,Φ† ,I trên ∆I là quan hệ thỏa mãn tính chất x ≡Σ† ,Φ† ,I x0 khi và chỉ khi x LΣ† ,Φ† -tương đương với x0 . Định lý 2.5. Cho Σ và Σ† là các bộ ký tự của logic mô tả sao cho Σ† ⊆ Σ, Φ và Φ† 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Σ† ,Φ† -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Σ† ,Φ† thì quan hệ ≡Σ† ,Φ† ,I là một LΣ† ,Φ† -tự mô phỏng hai chiều lớn nhất của I (nghĩa là, quan hệ ≡Σ† ,Φ† ,I và ∼Σ† ,Φ† ,I trùng khớp nhau). 11
Chúng ta nói rằng tập Y bị phân chia bởi tập X nếu Y \ 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 = {Y1 , Y2 , . . . , Yn } đượ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à Σ† là các bộ ký tự của logic mô tả sao cho Σ† ⊆ Σ, Φ và Φ† là tập các đặc trưng của logic mô tả sao cho Φ† ⊆ Φ, I là một diễn dịch hữu hạn trong LΣ,Φ và X ⊆ ∆I . Gọi Y là phân hoạch của ∆I thông qua quan hệ ∼Σ† ,Φ† ,I . Lúc đó: 1. nếu tồn tại khái niệm C của LΣ† ,Φ† sao cho C I = 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Σ† ,Φ† sao cho C I = X . Tiểu kết Chương 2 Thông qua ngôn ngữ LΣ,Φ và ngôn ngữ con LΣ† ,Φ† , 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
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 ∈ A và Va a∈A đượ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) ∈ Va với mọi u ∈ U và a ∈ A. 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 ∈ Σ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 ∈ Σ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 Σ), • nếu A ∈ ΣC là một khái niệm nguyên thủy trong KB thì AI = {a | A(a) ∈ A}, • nếu B ∈ ΣA \ ΣC thì B I : ∆I → range(B) là một hàm từng phần sao cho B I (aI ) = c nếu (B(a) = c) ∈ A, • nếu r ∈ ΣoR là một vai trò đối tượng nguyên thủy trong KB thì rI= {ha, bi| r(a, b) ∈ A}, • nếu σ ∈ ΣdR thì σ I = {ha, di | σ(a, d) ∈ A}, 13
• 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 = C I , • nếu A ∈ ΣC mà A không có mặt trong KB thì AI = ∅, • nếu r ∈ ΣoR mà r không xuất hiện trong KB thì rI = ∅. 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 ∈ ΣC là một khái niệm đại diện cho “thuộc tính quyết định”, E = hE + , E − i với E + = {a | aI ∈ AId } và E − = {a | aI ∈ (¬AId )} 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 LΣ† ,Φ† , trong đó Σ† ⊆ Σ \ {Ad } 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Σ† ,Φ† sao cho C thỏa mãn các điều kiện sau: • I |= C(a) với mọi a ∈ E + , • I |= ¬C(a) với mọi a ∈ E − . Lưu ý rằng, I |= ¬C(a) tương đồng với I 6|= 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 ∈ E + và b ∈ E − sao cho {aI , bI } ⊆ Y . Một phân hoạch Y = {Y1 , Y2 , . . . , Yn } của ∆I đượ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à Szalas [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 ∼Σ† ,Φ† ,I . 3.2.2. Bộ chọn Đị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 = {Yi1 , Yi2 , . . . , Yik } là một khái niệm thuộc một trong các dạng sau: • A, trong đó A ∈ Σ†C , • A = d, trong đó A ∈ Σ†A \ Σ†C và d ∈ range(A), • ∃σ.{d}, trong đó σ ∈ Σ†dR và d ∈ range(σ), • ∃r.Cit , trong đó r ∈ Σ†oR và 1 ≤ t ≤ k , • ∃r− .Cit , nếu I ∈ Φ† , r ∈ Σ†oR và 1 ≤ t ≤ k , • {a}, nếu O ∈ Φ† và a ∈ Σ†I , 14
• ≤ 1 r, nếu F ∈ Φ† và r ∈ Σ†oR , • ≤ 1 r− , nếu {F, I} ⊆ Φ† và r ∈ Σ†oR , • ≥ l r và ≤ m r, nếu N ∈ Φ† , r ∈ Σ†oR , 0 < l ≤ #∆I và 0 ≤ m < #∆I , • ≥ l r− và ≤ m r− , nếu {N , I} ⊆ Φ† , r ∈ Σ†oR , 0 < l ≤ #∆I và 0 ≤ m < #∆I , • ≥ l r.Cit và ≤ m r.Cit , nếu Q ∈ Φ† , r ∈ Σ†oR , 1 ≤ t ≤ k , 0 < l ≤ #CiIt và 0 ≤ m < #CiIt , • ≥ l r− .Cit và ≤ m r− .Cit , nếu {Q, I} ⊆ Φ† , r ∈ Σ†oR , 1 ≤ t ≤ k , 0 < l ≤ #CiIt và 0 ≤ m < #CiIt , • ∃r.Self , nếu Self ∈ Φ† và r ∈ Σ†oR . Định lý 3.1. Cho Σ và Σ† là các bộ ký tự logic mô tả sao cho Σ† ⊆ Σ, Φ và Φ† là tập các đặc trưng logic mô tả sao cho Φ† ⊆ Φ, I là một hệ thống thông tin trong LΣ,Φ . Xuất phát từ phân hoạch {∆I } và thực hiện việc làm mịn liên tục nó bằng các bộ chọn cơ bản ta sẽ nhận được một 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 là các khối được tạo ra trong quá trình làm mịn phân hoạch {∆I }, trong đó Yi được đặc trưng bởi khái niệm Ci sao cho Yi = CiI . Một bộ chọn đơn giản trong LΣ† ,Φ† để phân chia một khối là một bộ chọn cơ bản hoặc một khái niệm có dạng sau: • A ≤ d và A < d, trong đó A ∈ Σ†nA , d ∈ range(A) và d không phải là phần tử nhỏ nhất của range(A), • A ≥ d và A > d, trong đó A ∈ Σ†nA , d ∈ range(A) và d không phải là phần tử lớn nhất của range(A), • ∃r.>, ∃r.Ci và ∀r.Ci , trong đó r ∈ Σ†oR và 1 ≤ i ≤ n, • ∃r− .>, ∃r− .Ci và ∀r− .Ci , nếu I ∈ Φ† , r ∈ Σ†oR và 1 ≤ i ≤ n, • ≥ l r.Ci và ≤ m r.Ci , nếu Q ∈ Φ† , r ∈ Σ†oR , 1 ≤ i ≤ n, 0 < l ≤ #CiI và 0 ≤ m < #CiI , • ≥ l r− .Ci và ≤ m r− .Ci , nếu {Q, I} ⊆ Φ† , r ∈ Σ†oR , 1 ≤ i ≤ n, 0 < l ≤ #CiI và 0 ≤ m < #CiI . 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 = {D1 , D2 , . . . , Dh } đượ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 = {D1 , D2 , . . . , Dh } là tập các bộ chọn hiện thời. Một bộ chọn mở rộng trong LΣ† ,Φ† để 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: • ∃r.Du và ∀r.Du , trong đó r ∈ Σ†oR và Du ∈ D, • ∃r− .Du và ∀r− .Du , nếu I ∈ Φ† , r ∈ Σ†oR và Du ∈ D, 15
• ≥ l r.Du và ≤ m r.Du , nếu Q ∈ Φ† , r ∈ Σ†oR , Du ∈ D, 0 < l ≤ #DuI và 0 ≤ m < #DuI , • ≥ l r− .Du và ≤ m r− .Du , nếu {Q, I} ⊆ Φ† , r ∈ Σ†oR , Du ∈ D, 0 < l ≤ #DuI và 0 ≤ m < #DuI . 3.2.3. Tính đơn giản của khái niệm Định nghĩa 3.7. Cho C là một khái niệm ở dạng chuẩn trong ngôn ngữ LΣ,Φ . Độ sâu khả năng của khái niệm C , ký hiệu là mdepth(C), được xác định như sau: • 0 nếu C có dạng >, ⊥, A, A = d, A 6= d, A > d, A ≥ d, A < d hoặc A ≤ d, • mdepth(D) nếu C là dạng chuẩn của ¬D, • 1 nếu C có dạng ∃σ.{d}, ∃r.Self , ≥ n R hoặc ≤ n R, • 1 + mdepth(D) nếu C có dạng ∃R.D, ∀R.D, ≥ n R.D hoặc ≤ n R.D, • max{mdepth(D1 ), mdepth(D2 ), . . . , mdepth(Dn )} nếu C có dạng u{D1 , D2 , . . . , Dn } hoặc t{D1 , D2 , . . . , Dn }. Định nghĩa 3.8. Cho C là một khái niệm ở dạng chuẩn trong ngôn ngữ LΣ,Φ . Độ dài của khái niệm C , ký hiệu bởi length(C), được xác định như sau: • 0 nếu C có dạng > hoặc ⊥, • 1 nếu C có dạng A, A = d, A 6= d, A > d, A ≥ d, A < d hoặc A ≤ d, • length(D) nếu C ≡ D và D là dạng chuẩn của ¬D, • 3 nếu C có dạng ∃σ.{d}, ∃r.Self , ≥ n R hoặc ≤ n R, • 2 + length(D) nếu C có dạng ∃R.D hoặc ∀R.D, • 3 + length(D) nếu C có dạng ≥ n R.D hoặc ≤ n R.D, • 1+ length(D1 )+ length(D2 )+· · ·+ length(Dn ) nếu C có dạng u{D1 , D2 , . . . , Dn } hoặc t{D1 , D2 , . . . , Dn }. Khái niệm đơn giản nhất là khái niệm có độ dài và độ sâu khả năng nhỏ nhất. 3.2.4. Độ đo dựa trên entropy Cho I là một hệ thống thông tin, X và Y là các tập con của ∆I , trong đó X đóng vai trò là tập các mẫu dương, Y đóng vai trò là một khối của phân hoạch. Định nghĩa 3.9 (Entropy). Entropy của tập Y đối với tập X trong miền ∆I của hệ thống thông tin I , ký hiệu là E∆I (Y /X), được xác định như sau:  0, nếu Y ∩ X = ∅ hoặc Y ⊆ X  E∆I (Y /X) = #XY #XY #XY #XY (3.1) −  log2 − log2 , nếu ngược lại, #Y #Y #Y #Y trong đó XY đại diện cho tập X ∩ Y và 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 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: ! #DI Y I #DI Y IG∆I (Y /X, D) = E∆I (Y /X) − E∆I (D Y /X)+ E∆I (DI Y /X) (3.2) #Y #Y trong đó DI Y đại diện cho tập DI ∩ Y và DI Y đại diện cho tập DI ∩ Y . Trong ngữ cảnh ∆I 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 ∈ Y và Sij ∈ D 1 BS := ∅; 2 foreach Yij ∈ Y do 3 foreach Du ∈ D do 4 Tính IG(Yij , Du ); 5 S := arg max{IG(Yij , Du )}; Du ∈D 6 Lấy Sij ∈ S sao cho Sij là khái niệm đơn giản nhất; 7 BS := BS ∪ { Yij , Sij }; 8 Chọn Y ij , Sij ∈ BS sao cho IG(Yij , Sij ) là cực đại; 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 , Ai trong LΣ,Φ , với Σ = ΣI ∪ ΣdA ∪ ΣnA ∪ ΣoR ∪ ΣdR và Φ = {I}, trong đó: ΣI = {Ava, Britt, Colin, Dave, Ella, F lor, Gigi, Harry}, ΣC = {Human, M ale, F emale, N ephew, N iece}, ΣdA = ΣC , ΣnA = ∅, ΣoR = {hasChild, hasP arent, hasSibling}, ΣdR = ∅. R = {hasP arent ≡ hasChild− , Sym(hasSibling)}, T = {Human ≡ >, N iece ≡ F emale u ∃hasChild− .(∃hasSibling.>), N ephew ≡ M ale u ∃hasChild− .(∃hasSibling.>)}, 17
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, Σ† , Φ† , E = hE − , E + i Output: Khái niệm C sao cho: • I |= C(a) với mọi a ∈ E + , và • I 6|= C(a) với mọi a ∈ E − . I 1 n := 1; Y1 := ∆ ; C1 := >; Y := {Y1 }; 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); 5 if (Yij không bị phân chia bởi SiIj ) then 6 break; 7 s := n + 1; t := n + 2; n := n + 2; 8 Ys := Yij ∩ SiIj ; Cs := Cij u Sij ; 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 ∪ {Ys , Yt } \ {Yij }; 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 ∈ Y do 23 if (∃a ∈ E + : aI ∈ Yij ) then 24 J := J ∪ {LargestContainer [ij ]} ; 25 foreach l ∈ J do 26 C := C ∪ {Cl }; F 27 C := C; 28 return Crs :=simplify (C); 29 else 30 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