Chương 1. Chúng tôi phát biểu các định nghĩa, định lý, bổ đề mở rộng về mô phỏng hai chiều và chứng minh tính bất biến đối với mô phỏng hai chiều cho các khái niệm, bộ tiên đề thuật ngữ, bộ khẳng định và cơ sở tri thức đối với các logic mô tả đang nghiên cứu. Đặc biệt tính bất biến của khái niệm là 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. Đây là cơ sở cho việc sử dụng ngôn ngữ con trong quá trình xây dựng các thuật toán học khái niệm.
Chương 3 trình bày thuật toán học khái niệm cho các hệ thống thông tin trong logic mô tả với Ngữ cảnh (3) (thể hiện qua Thuật toán 3. Thuật toán này cho phép học một khái niệm từ một hệ thống thông tin huấn luyện trong logic mô tả với tập 5 các mẫu dương và mẫu âm cho trước. Chúng tôi đã sử dụng bộ chọn cơ bản, bộ chọn đơn giản và bộ chọn mở rộng kết hợp với độ đo gia lượng thông tin để phân chia các khối trong quá trình làm mịn các phân hoạch miền của diễn dịch. Ngoài ra, chương này còn trình bày các kết quả thực nghiệm đối với thuật toán đã đề xuất.
Chương 4 trình bày 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), bao gồm thuật toán BBCL, dual-BBCL và BBCL2. Các thuật toán này sử dụng các mô hình của cơ sở tri thức kết hợp với mô phỏng hai chiều trong mô hình đó (để mô hình hóa tính không phân biệt được) và cây quyết định (để phân lớp dữ liệu) cho việc tìm kiếm khái niệm cần học. Chúng tôi cũng chứng minh tính đúng đắn của thuật toán thông qua các mệnh đề liên quan. Cuối cùng, phần kết luận trình bày tóm tắt những đóng góp chính của luận án, hướng phát triển và những vấn đề cần phải giải quyết trong tương lai.
LOGIC MÔ TẢ VÀ CƠ SỞ TRI THỨC 1. Tổng quan về logic mô tả 1. Giới thiệu Các nghiên cứu về biểu diễn tri thức được đặt ra từ những năm 70 của thế kỷ XX. Những công trình nghiên cứu đầu tiên trong lĩnh vực này dựa trên hướng tiếp cận phi logic.
Hướng tiếp cận này sử dụng đồ thị làm nền tảng, trong đó tri thức được biểu diễn bằng những cấu trúc dữ liệu đặc biệt và việc suy luận được thực hiện thông qua các thủ tục thao tác trên những cấu trúc đó. Năm 1967, Quillian [49] đã sử dụng mạng ngữ nghĩa (semantic networks) để biểu diễn và suy luận tri thức thông qua các cấu trúc nhận thức dạng mạng lưới. Sau đó, năm 1974, Minsky giới thiệu hệ thống khung (frame systems) dựa trên các khái niệm về một “khung” như một giao thức và khả năng biểu diễn các mối quan hệ giữa các khung [37]. Hướng tiếp cận như trên không trang bị được ngữ nghĩa dựa trên logic hình thức.
Để khắc phục nhược điểm này, người ta biểu diễn tri thức theo hướng tiếp cận dựa trên logic. Theo đó, ngôn ngữ biểu diễn thường là một biến thể của logic vị từ bậc nhất và việc tính toán, suy luận thường dựa vào các hệ quả logic. Logic mô tả được thiết kế như là một sự mở rộng của mạng ngữ nghĩa và hệ thống khung với ngữ nghĩa dựa trên logic. Nó là một họ các ngôn ngữ hình thức rất thích hợp cho việc biểu diễn và suy luận tri thức trong một miền quan tâm cụ thể [2].
Thuật ngữ “logic mô tả” được sử dụng rộng rãi từ những năm 80 của thế kỷ XX. Ngày nay, cùng với sự phát triển của các hệ thống biểu diễn tri thức, logic mô tả đã trở thành một nền tảng quan trọng của Web ngữ nghĩa do nó được sử dụng để cung cấp mô hình lý thuyết trong việc thiết kế các ontology. 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ể (có thể hiểu như là các đối tượng), tập các khái niệm nguyên tố (có thể hiểu như là các lớp, các vị từ một đối) và tập các vai trò nguyên tố (có thể hiểu như là các quan hệ hai ngôi, các vị từ hai đối). Các logic mô tả khác nhau được đặc trưng bởi tập các tạo tử khái niệm và tạo tử vai trò mà nó được phép sử dụng để xây dựng các khái niệm phức, vai trò phức từ các khái niệm nguyên tố và vai trò nguyên tố.
7 Năm 1985, hệ thống biểu diễn tri thức dựa trên logic mô tả đầu tiên KL-one [56], [7] ra đời đã đánh dấu một sự khởi đầu mạnh mẽ về nghiên cứu logic mô tả. Một số hệ thống biểu diễn tri thức dựa trên logic mô tả khác tiếp tục xuất hiện sau đó là LOOM (1987), BACK (1988), CLASSIC (1991). Các hệ thống này có bộ suy luận sử dụng các thuật toán bao hàm cấu trúc. Gần đây, các hệ thống biểu diễn tri thức sử dụng các ngôn ngữ logic mô tả có khả năng biểu diễn tốt hơn như SHOIN , SHOIQ, SROIQ,.
và các bộ suy luận hiệu quả hơn như FaCT (1998), RACER (2001), CEL (2005), FaCT++ (2005), KAON 2 (2005) và HermiT (2008) [53]. Các bộ suy luận này sử dụng các thuật toán tableaux để giải quyết các bái toán suy luận. Ngôn ngữ logic mô tả ALC Logic mô tả cơ bản ALC được Schmidt-Schaubß và Smolka giới thiệu lần đầu tiên vào năm 1991 [55]. Tên ALC đại diện cho “Attribute concept Language with Complements”.
Trên cơ sở logic mô tả cơ bản ALC, người ta mở rộng nó để có các logic mô tả khác có khả năng biểu diễn tốt hơn bằng cách thêm vào các tạo tử khái niệm và tạo tử vai trò. Các định nghĩa sau đây trình bày cú pháp và ngữ nghĩa của logic mô tả cơ bản ALC [34], [36]. 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 cũng là các khái niệm của ALC. Các ký hiệu và các tạo tử khái niệm trong Định nghĩa 1.1 có ý nghĩa như sau: • > gọi là khái niệm đỉnh, • ⊥ gọi là khái niệm đáy, • ¬C biểu diễn phủ định của khái niệm C, • C u D biểu diễn giao của khái niệm C và D, • C t D biểu diễn hợp của khái niệm C và D, • ∃r.C biểu diễn hạn chế tồn tại của khái niệm C bởi vai trò r, • ∀r.C biểu diễn hạn chế phổ quát của khái niệm C bởi vai trò r. 8 Cú pháp của logic mô tả ALC có thể mô tả một cách vắn tắt bằng các luật sau: C, D −→ A | > | ⊥ | ¬C | C u D | C t D | ∃r. 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 \ C I , (∃r.1 minh họa ngắn gọn cho diễn dịch trong logic mô tả. Mỗi cá thể được diễn dịch thành một đối tượng, mỗi khái niệm được diễn dịch thành một tập các đối tượng và mỗi vai trò được diễn dịch thành một quan hệ hai ngôi giữa các đối tượng [21]. bộ ký tự Tên cá thể Tên khái niệm Tên vai trò. diễn dịch I aI ∆I AI rI Hình 1.1: Diễn dịch của logic mô tả Ví dụ 1.
Giả sử chúng ta có các cá thể, khái niệm nguyên tố và vai trò nguyên tố như sau: LAN, HAI, HUNG là các cá thể, Human là khái niệm chỉ các đối tượng là con người, 9 F emale là khái niệm chỉ các đối tượng là giống cái, Rich là khái niệm chỉ những đối tượng giàu có, hasChild là vai trò chỉ đối tượng này có con là đối tượng kia, hasDescendant là vai trò chỉ đối tượng này có con cháu là đối tượng kia, marriedT o là vai trò chỉ đối tượng này kết hôn với đối tượng kia. Với những khái niệm nguyên tố, vai trò nguyên tố đã cho ở trên và các tạo tử phủ định của khái niệm (¬), giao của các khái niệm (u), hợp của các khái niệm (t), lượng từ hạn chế tồn tại (∃), lượng từ hạn chế với mọi (∀), chúng ta có thể xây dựng các khái niệm phức như sau: Human u F emale là khái niệm chỉ các đối tượng là người phụ nữ, Human u ∃hasChild.F emale là khái niệm chỉ các đối tượng là người có con gái, Human u ∃marriedT o.Human là khái niệm chỉ những người đã kết hôn, Human u F emale u Rich là khái niệm chỉ những người phụ nữ giàu có, Human u ∀hasChild.F emale là khái niệm chỉ những người chỉ có toàn con gái hoặc những người không có con. Ngoài ra chúng ta có thể dùng khái niệm đỉnh (ký hiệu >), khái niệm đại diện cho tất cả các đối tượng và khái niệm đáy (ký hiệu ⊥), khái niệm không đại diện cho bất kỳ đối tượng nào, để xây dựng các khái niệm phức. Chẳng hạn như sau: Human u ∃hasChild.> là khái niệm chỉ các đối tượng là người có con, Human u ∀hasChild.⊥ là khái niệm chỉ những người không có con.
Cho tập các cá thể, khái niệm và vai trò như trong Ví dụ 1. Xét diễn dịch I như sau: LANI = LAN, HAII = HAI, HUNGI = HUNG, ∆I = {LAN, HAI, HUNG}, HumanI = {LAN, HAI, HUNG}, F emaleI = {LAN}, RichI = {HUNG}, hasChildI = {hLAN, HUNGi, hHAI, HUNGi}, marriedT oI = {hLAN, HAIi, hHAI, LANi}, 10 Lúc đó ta có: (Human u F emale)I = {LAN}, (¬F emale)I = {HAI, HUNG}, (Human u ¬F emale)I = {HAI, HUNG}, (Human u ∃hasChild.F emale)I = ∅, (Human u ∃marriedT o.Human)I = {LAN, HAI}. 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ả.