Luận án Một số phương pháp xử lý tri thức không nhất quán trong ontology

ình nghiên cứu do tôi thực hiện dưới sự hướng dẫn của PGS. TS. Hoàng Hữu Hạnh. Những nội dung trong các công trình đã công bố chung với các tác giả khác đã được sự đồng ý của đồng tác giả khi đưa vào luận án. Các số liệu và kết quả nghiên cứu trình bày trong luận án là trung thực, khách quan và chưa được công bố bởi tác giả nào trong bất cứ công trình nào khác. Nghiên cứu sinh Nguyễn Văn Trung i LỜI CẢM ƠN Luận án này được thực hiện và hoàn thành tại Khoa Công nghệ Thông tin, Trường Đại học Khoa học, Đại học Huế. Trong suốt quá trình học tập và thực hiện luận án, tôi đã nhận được rất nhiều sự quan tâm, động viên, giúp đỡ của thầy giáo hướng dẫn, thầy cô giáo trong Khoa Công nghệ Thông tin, Phòng Đào tạo Sau đại học và Ban giám hiệu Trường Đại học Khoa học. Tôi xin bày tỏ lòng biết ơn sâu sắc đến PGS. TS. Hoàng Hữu Hạnh là người thầy tận tình hướng dẫn, động viên và truyền đạt những kinh nghiệm quý báu trong nghiên cứu khoa học để tôi có thể hoàn thành luận án này. Tôi xin chân thành cảm ơn quý thầy cô giáo trong Khoa Công nghệ Thông tin đã tạo điều kiện thuận lợi trong công tác để tôi có thể hoàn thành công việc nghiên cứu của mình. Tôi xin cảm ơn quý thầy cô và cán bộ của Phòng Đào tạo Sau đại học, Ban giám hiệu Trường Đại học Khoa học đã giúp đỡ tôi trong việc hoàn thành kế hoạch học tập. Tôi xin trân trọng cảm ơn quý thầy cô giáo trong Hội đồng Khoa học của Khoa Công nghệ Thông tin đã đọc và đưa ra những góp ý xác đáng cho luận án này. Tôi xin trân trọng cảm ơn quý thầy cô giáo và các anh chị đồng nghiệp trong Khoa Công nghệ Thông tin đã giúp đỡ, chia sẻ trong quá trình công tác, học tập, nghiên cứu và thực hiện luận án. Cuối cùng tôi xin cảm ơn những người thân trong gia đình đã luôn ủng hộ, chia sẻ khó khăn trong suốt quá trình học tập, nghiên cứu và thực hiện luận án. Nghiên cứu sinh Nguyễn Văn Trung ii MỤC LỤC Lời cam đoan i Lời cảm ơn ii Mục lục iii Danh mục từ viết tắt, thuật ngữ v Danh mục ký hiệu vi Danh mục bảng, biểu vii Danh mục hình vẽ viii Mở đầu 1 Chương 1. TỔNG QUAN VỀ XỬ LÝ TRI THỨC KHÔNG NHẤT QUÁN TRONG ONTOLOGY 9 1.1 Ontology và tri thức không nhất quán . . . . . . . . . . . . . . . . . . 9 1.2 Khung lập luận với ontology không nhất quán sử dụng chiến lược phát triển tuyến tính tập tiên đề diễn giải . . . . . . . . . . . . . . . . . . . 15 1.2.1 Các khái niệm cơ bản . . . . . . . . . . . . . . . . . . . . . . . . 15 1.2.2 Hàm chọn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.2.3 Phép suy luận không chuẩn sử dụng hàm chọn đơn điệu . . . . 20 1.2.4 Phép suy luận không chuẩn sử dụng hàm chọn dựa trên sự liên quan cú pháp . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 1.2.5 Các nghiên cứu liên quan đến khung lập luận với ontology không nhất quán sử dụng chiến lược mở rộng tuyến tính tập tiên đề diễn giải . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 1.3 Xử lý tri thức không nhất quán trong quá trình tích hợp ontology theo phương pháp đồng thuận . . . . . . . . . . . . . . . . . . . . . . . . . . 32 1.3.1 Hồ sơ xung đột . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 1.3.2 Sự không nhất quán tri thức . . . . . . . . . . . . . . . . . . . . 33 1.3.3 Hàm đồng thuận . . . . . . . . . . . . . . . . . . . . . . . . . . 40 1.3.4 Các nghiên cứu liên quan xử lý không nhất quán tri thức trong quá trình tích hợp ontology bằng phương pháp đồng thuận . . . 44 1.4 Tiểu kết Chương 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 Chương 2. SUY LUẬN VỚI ONTOLOGY KHÔNGNHẤT QUÁN SỬ DỤNG HÀM CHỌN DỰA TRÊN ĐỘ LIÊN QUAN NGỮ NGHĨA 47 2.1 Khoảng cách ngữ nghĩa giữa hai khái niệm trong ontology . . . . . . . 48 iii 2.2 Khoảng cách ngữ nghĩa giữa hai biểu thức khái niệm theo ontology tham chiếu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 2.3 Khoảng cách ngữ nghĩa giữa hai tiên đề theo ontology tham chiếu . . . 55 2.4 Suy luận với ontology không nhất quán sử dụng hàm chọn dựa trên khoảng cách ngữ nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 2.5 Thực nghiệm và đánh giá kết quả . . . . . . . . . . . . . . . . . . . . . 67 2.6 Tiểu kết Chương 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 Chương 3. XỬ LÝ XUNG ĐỘT MỨC KHÁI NIỆM TRONG QUÁ TRÌNH TÍCH HỢP ONTOLOGY 72 3.1 Mô hình tích hợp tri thức dựa trên lý thuyết đồng thuận . . . . . . . . 72 3.2 Các mức xung đột trong quá trình tích hợp ontology . . . . . . . . . . 75 3.3 Xử lý xung đột mức khái niệm trong quá trình tích hợp ontology . . . 78 3.4 Vấn đề xây dựng hàm đánh giá khoảng cách cho các miền giá trị của các thuộc tính . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 3.4.1 Hàm đánh giá khoảng cách giữa hai biểu thức khái niệm . . . . 85 3.4.2 Hàm đánh giá khoảng cách giữa hai khoảng dữ liệu . . . . . . . 86 3.5 Tiểu kết Chương 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 Chương 4. XỬ LÝ XUNGĐỘTMỨC TIÊN ĐỀ TRONGQUÁ TRÌNH TÍCH HỢP ONTOLOGY 94 4.1 Mô hình xử lý xung đột tri thức cấp độ cú pháp . . . . . . . . . . . . . 95 4.1.1 Bài toán tìm đồng thuận của các công thức hội và các tiêu chuẩn cho đồng thuận . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 4.1.2 Phân tích các tiêu chuẩn đồng thuận . . . . . . . . . . . . . . . 100 4.1.3 Thuật toán xác định đồng thuận . . . . . . . . . . . . . . . . . 109 4.2 Xử lý xung đột mức tiên đề trong quá trình tích hợp ontology . . . . . 115 4.3 Tiểu kết Chương 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 KẾT LUẬN 120 DANHMỤC CÁC CÔNG TRÌNH CỦA TÁC GIẢ LIÊN QUAN ĐẾN LUẬN ÁN 122 TÀI LIỆU THAM KHẢO 123 iv DANH MỤC TỪ VIẾT TẮT, THUẬT NGỮ Từ viết tắt, thuật ngữ Diễn giải ODP Over-determined Processing Quy trình xử lý quá xác định OWL Ontology Web Language Ngôn ngữ ontology dùng cho Web W3C World Wide Web Consortium Tổ chức tiêu chuẩn quốc tế về World Wide Web Conflict profile Hồ sơ xung đột Consensus theory Lý thuyết đồng thuận Data property Thuộc tính dữ liệu Domain Miền xác định (của thuộc tính) Object property Thuộc tính đối tượng Open World Assumption Giả thiết thế giới mở Range Miền giá trị (của thuộc tính) Semantic wiki Wiki ngữ nghĩa v DANH MỤC KÝ HIỆU Ký hiệu Diễn giải ý nghĩa O Ontology Σ Ontology không nhất quán Σ′,Σ′′ Ontology nhất quán với các tiên đề được chọn từ một ontology không nhất quán khác |≈ Phép suy luận không chuẩn |≈Syn Phép suy luận không chuẩn sử dụng hàm chọn dựa trên độ liên quan cú pháp |≈O Phép suy luận không chuẩn sử dụng hàm chọn dựa trên khoảng cách ngữ nghĩa của ontology tham chiếu O R, S Các tên vai trò, thuộc tính A,B Các tên cá thể DPO(C) Tập khái niệm cha trực tiếp của khái niệm trên một ontology DCO(C) Tập khái niệm con trực tiếp của khái niệm trên một ontology LCPO(C,D) Tập khái niệm cha chung tối thiểu của hai khái niệm trên một ontology C,D Các tên khái niệm CE1, CE2 Các biểu thức khái niệm DR1, DR2 Các khoảng dữ liệu DT Kiểu dữ liệu U Tập vũ trụ X,Y Các hồ sơ xung đột P1a,P1b Các tiêu chuẩn cho hàm nhất quán T1,T2 Các tiêu chuẩn cho bộ tri thức tích hợp H1,H2 Các tiêu chuẩn cho công thức hội vi DANH MỤC BẢNG, BIỂU Bảng 1.1. Tính thoả tiêu chuẩn của một số hàm nhất quán thông dụng . . . . . 40 Bảng 2.1. Các tiên đề về biểu thức khái niệm . . . . . . . . . . . . . . . . . . . 58 Bảng 2.2. Các tiên đề về thuộc tính đối tượng . . . . . . . . . . . . . . . . . . . 59 Bảng 2.3. Các tiên đề về thuộc tính dữ liệu, định nghĩa kiểu dữ liệu, khoá của biểu thức khái niệm, phát biểu về dữ kiện . . . . . . . . . . . . . . . 60 Bảng 2.4. Các ontology thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . . 68 Bảng 2.5. So sánh theo số lượng kết quả xác định của truy vấn . . . . . . . . . 69 Bảng 2.6. So sánh sự phát triển tập tiên đề diễn giải . . . . . . . . . . . . . . . 69 Bảng 3.1. Cấu trúc của khái niệm Course trong 5 ontology . . . . . . . . . . . . 91 Bảng 4.1. Ví dụ về các công thức hội của 3 tác tử mô tả tính chất của thuộc tính hasSpouse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 Bảng 4.2. Trạng thái tri thức của các tác tử cho bài toán minh hoạ . . . . . . . 114 vii DANH MỤC HÌNH VẼ Hình 1.1. Truy vấn với ontology không nhất quán . . . . . . . . . . . . . . . . . 13 Hình 1.2. Chiến lược mở rộng tuyến tính [21] . . . . . . . . . . . . . . . . . . . 21 Hình 1.3. Sơ đồ áp dụng hàm đồng thuận . . . . . . . . . . . . . . . . . . . . . 43 Hình 1.4. Trích dẫn của ontology tham chiếu OREF−TREE . . . . . . . . . . . . 44 Hình 1.5. Trích dẫn ontology của 4 chuyên gia . . . . . . . . . . . . . . . . . . . 45 Hình 2.1. Cây phân cấp khái niệm minh hoạ . . . . . . . . . . . . . . . . . . . . 50 Hình 2.2. Ontology tham chiếu O . . . . . . . . . . . . . . . . . . . . . . . . . . 65 viii MỞ ĐẦU 1. Tính cấp thiết của đề tài Năm 2001, Tim Berners Lee cùng cộng sự đã đưa ra phác thảo cho một “dạng thức mới về nội dung web mà dạng thức này có ý nghĩa đối với máy tính” [4]. Thế hệ web sử dụng dạng thức nội dung này – gọi là Web ngữ nghĩa (Semantic Web) – cho phép máy tính có thể “hiểu” tri thức được lưu trữ, theo đó có thể chia sẻ và tái sử dụng các cơ sở tri thức trong các hệ thống thông tin thuộc nhiều lĩnh vực khác nhau. So với Web hiện tại – là một kho tài liệu được liên kết với nhau – Web ngữ nghĩa là một nền tảng dữ liệu mà trong đó thông tin được lưu ở dạng định nghĩa tường minh, cho phép máy tính và con người có thể làm việc được cùng nhau [4]. Web ngữ nghĩa là một lĩnh vực nghiên cứu đang phát triển nhanh và nhận được sự quan tâm của cộng đồng nghiên cứu trong thập niên vừa qua. Công nghệ Web ngữ nghĩa đang được áp dụng vào nhiều lĩnh vực khác nhau trong thực tế như tin-sinh học, tin học trong y tế, quản trị tri thức, công nghệ phần mềm, . . . Thành phần quan trọng trong các ứng dụng web ngữ nghĩa là ontology. Trong một ontology người ta định nghĩa các thực thể (bao gồm khái niệm, thuộc tính, cá thể) và mối quan hệ giữa các thực thể này theo ngữ nghĩa được quy định tường minh bởi một ngôn ngữ logic xác định. Ngôn ngữ ontology được sử dụng phổ biến và chuẩn hoá bởi tổ chức tiêu chuẩn quốc tế W3C (World Wide Web Consortium) là OWL, được xây dựng dựa trên logic mô tả: Phiên bản đầu tiên của OWL (được giới thiệu vào năm 2004) dựa trên logic mô tả SHOIN (D), trong khi đó phiên bản thứ hai là OWL2 (được giới thiệu vào năm 2009) dựa trên logic mô tả SROIQ(D). Các tác vụ lập luận cơ bản với một ontology OWL – bao gồm kiểm tra tính nhất quán và truy vấn tri thức không được phát biểu tường minh trong ontology – đã được cài đặt trong các bộ lập luận RACER [15], FaCT+ [59], Pellet [56], HermiT [36], . . . Danh sách đầy đủ các bộ lập luận dùng với ontology OWL được tổ chức W3C cập nhật thường xuyên tại địa chỉ https://www.w3.org/2001/sw/wiki/OWL/Implementations. 1 Theo [13], vấn đề quan trọng của Web ngữ nghĩa là phải xử lý tri thức không nhất quán trong các ontology. Điều này bắt nguồn từ chính đặc điểm xây dựng và sử dụng ontology trong các ứng dụng Web ngữ nghĩa: Đặc tính có thể mở rộng, có thể chia sẻ, tái sử dụng, phân tán và đa người dùng luôn tiềm ẩn khả năng làm xuất hiện tri thức không nhất quán trong các ontology [22]. Trên thực tế, nếu một ontology là không nhất quán, các truy vấn trên nó là không có nghĩa [26]. Điều này là bởi bất kỳ tiên đề nào cũng là hệ quả logic của một ontology không nhất quán. Nói cách khác, sự không nhất quán làm mất đi ý nghĩa sử dụng của ontology trong các ứng dụng Web ngữ nghĩa. Chính vì vậy, xử lý tri thức không nhất quán trong ontology là bài toán quan trọng, có ý nghĩa thực tiễn và được cộng đồng khoa học máy tính quan tâm nghiên cứu. 2. Động lực nghiên cứu và cách tiếp cận nghiên cứu của luận án Các phương pháp xử lý tri thức không nhất quán trong ontology có thể được phân làm hai nhóm: (1) nhóm phương pháp chấp nhận tồn tại tri thức không nhất quán trong ontology, và (2) nhóm phương pháp tìm cách loại bỏ tri thức không nhất quán khỏi ontology: (1)Các giải pháp thuộc nhóm thứ nhất – chấp nhận tồn tại tri thức không nhất quán trong ontology. Một số tiếp cận thuộc nhóm này định nghĩa các logic mô tả với ngữ nghĩa nửa nhất quán và xây dựng ontology dựa trên các logic đó [31, 32, 38, 50]. Tác vụ truy vấn với các ontology dựa trên logic nửa nhất quán vẫn có thể sử dụng các bộ lập luận dành cho logic mô tả xây dựng nên OWL (bằng cách chuyển các bài toán lập luận trên các logic này về bài toán lập luận trên các logic mô tả của OWL). Việc sử dụng logic với ngữ nghĩa nửa nhất quán để xây dựng ontology, mặc dù tạo ra được mô hình biểu diễn tri thức toàn diện nhưng lại khó triển khai trong thực tế do tính phổ biến của các ngôn ngữ ontology đã được chuẩn hoá và khuyến nghị sử dụng bởi tổ chức W3C. Trong rất nhiều trường hợp thực tế, các ứng dụng Web ngữ nghĩa cần truy vấn thông tin được tổng hợp từ các ontology đến từ nhiều nguồn khác nhau (và có thể không nhất quán) mà không được phép chỉnh sửa hay tạo mới ontology. Một giải pháp phù hợp cho vấn đề này là khung lập luận với ontology không nhất quán sử dụng chiến lược phát triển tuyến tính tập tiên đề diễn giải, được 2 đề xuất bởi nhóm tác giả Zhisheng Huang, Frank van Harmelen và cộng sự [21]. Khung lập luận này tìm câu trả lời có nghĩa cho truy vấn với ontology không nhất quán bằng cách chọn ra một tập con gồm các tiên đề nhất quán từ ontology đầu vào – gọi là tập tiên đề diễn giải truy vấn: tập tiên đề này có liên quan với truy vấn theo một tiêu chí cụ thể cho trước và có thể trả lời được truy vấn. Quá trình chọn tập tiên đề diễn giải có thể được diễn ra trong nhiều bước theo chiến lược gọi là chiến lược mở rộng tuyến tính. Phần quan trọng nhất của khung lập luận với ontology không nhất quán là hàm chọn để xây dựng tập tiên đề diễn giải truy vấn. Hai hàm chọn điển hình được nhóm tác giả phát triển là hàm chọn dựa trên sự liên quan cú pháp [21] và hàm chọn dựa trên khoảng cách ngữ nghĩa theo máy tìm kiếm Google [23]. Hai hàm chọn này đều có chung nhược điểm là phụ thuộc vào cú pháp (tên khái niệm trong tiên đề) trong quá trình phát triển tập tiên đề diễn giải. Khắc phục nhược điểm này chính là một động lực nghiên cứu của luận án: Luận án đề xuất xây dựng tập tiên đề diễn giải theo độ liên quan ngữ nghĩa giữa các tiên đề với truy vấn đầu vào. Độ liên quan này được xác định dựa trên khoảng cách ngữ nghĩa giữa các khái niệm, giữa các biểu thức khái niệm khi đặt chúng trên cây phân cấp khái niệm của một ontology, ontology này được gọi là ontology tham chiếu. (2)Các giải pháp thuộc nhóm thứ hai – tìm cách loại bỏ tri thức không nhất quán thông qua việc xây dựng mới ontology từ một hoặc nhiều ontology đầu vào. Việc tạo mới ontology như vậy diễn ra theo hai chiến lược: chiến lược thứ nhất, dò tìm, đề xuất chỉnh sửa hoặc loại bỏ một số tiên đề gây nên sự không nhất quán khỏi ontology [25, 29, 51, 54]; và chiến lược thứ hai, áp dụng lý thuyết đồng thuận để xây dựng tập tiên đề hợp lý nhất (theo một tiêu chuẩn xác định trước) có thể đại diện cho các ontology đầu vào [39, 40, 41, 43, 45, 46, 47, 48, 49]. Chiến lược thứ nhất thường được sử dụng để duy trì sự nhất quán của một ontology, trong khi đó, chiến lược thứ hai thường được sử dụng để xử lý xung đột trong quá trình tích hợp ontology đến từ nhiều nguồn phân tán, độc lập nhau. Xử lý tri thức không nhất quán theo phương pháp đồng thuận được thực hiện thông qua việc xây dựng mô hình biểu diễn sự không nhất quán tri thức (gọi là xung đột tri thức) – dưới dạng hồ sơ xung đột. Dựa vào độ sai khác giữa các trạng thái tri thức (xác định bởi hàm đánh giá khoảng cách giữa hai trạng 3 thái tri thức) và tập tiêu chuẩn cho tri thức đồng thuận, người ta sẽ đề xuất phương pháp xác định trạng thái tri thức đồng thuận có thể đại diện cho tập trạng thái tri thức đầu vào. Phương pháp này được tác giả Nguyễn Ngọc Thành đề xuất vào năm 2002 [40] và cùng với các cộng sự mở rộng trong các công trình sau đó [42, 43, 46, 47]. • Trong các công trình [44, 45, 48], tác giả Nguyễn Ngọc Thành đã phân loại xung đột trong quá trình tích hợp ontology theo các mức (mức khái niệm, mức quan hệ, mức cá thể) và đề xuất các phương pháp để xử lý xung đột theo các mức này. Xung đột mức khái niệm là chủ đề được đặc biệt quan tâm xử lý bởi các khái niệm là thành phần quan trọng trong ontology. Nhóm tác giả Dương Trọng Hải, Nguyễn Ngọc Thành và cộng sự [9] kết hợp lý thuyết đồng thuận và xét thêm phân loại khái niệm của các ontology đầu vào để cải tiến chất lượng của quá trình tích hợp. Nhóm tác giả Nguyễn Ngọc Thành và Trương Hải Bằng [49, 58], Dương Trọng Hải, Nguyễn Ngọc Thành và Kozierk [9] đã mở rộng các kết quả trên để xử lý xung đột mức khái niệm trong quá trình tích hợp ontology mờ. Trong bài toán xử lý xung đột mức khái niệm, cấu trúc khái niệm được xét theo hai khía cạnh: tập thuộc tính mô tả khái niệm và miền giá trị của thuộc tính. Tuy vậy, các nghiên cứu xử lý xung đột mức khái niệm trong quá trình tích hợp ontology hiện nay chỉ tập trung xây dựng danh sách thuộc tính của khái niệm cần tích hợp. Trong khi đó, miền giá trị của các thuộc tính chỉ được xác định bằng cách lấy hợp của các miền giá trị thành phần. Điều này có nghĩa xung đột về miền giá trị của thuộc tính là chưa được xét đến. Luận án sẽ áp dụng mô hình tổng quát tích hợp tri thức theo phương pháp đồng thuận [45] và đề xuất phương án xử lý xung đột mức khái niệm trong quá trình tích hợp ontology, trong đó có xét đến cả hai khía cạnh: danh sách thuộc tính và miền giá trị của thuộc tính. • Một mức xung đột khác cũng có thể xảy ra trong quá trình tích hợp ontology đó là xung đột mức tiên đề, theo đó, tập tiên đề của các ontology tham gia tích hợp là có sai khác nhau hoặc thậm chí mâu thuẫn nhau. Tình huống này cũng có thể thường xuyên xảy ra trong quá trình xây dựng ontology theo kiểu phân tán, cộng tác, đa người dùng [6, 60, 61] mà 4 trong đó, một ontology có thể được xây dựng bởi nhiều người dùng tự nguyện thông qua một wiki ngữ nghĩa [17, 27, 37] hoặc bởi các chuyên gia được thuê [34]. Tuy nhiên, xung đột mức tiên đề trong quá trình tích hợp ontology hiện vẫn là bài toán chưa có giải pháp tốt và thuyết phục như các mức khái niệm, quan hệ hay cá thể. Bằng cách biểu diễn một tiên đề dưới dạng một literal , mỗi ontology thành phần có thể được biểu diễn dưới dạng hội của các literal đó. Như vậy, bài toán xử lý xung đột tập tiên đề có thể được dẫn về bài toán xử lý xung đột ở cấp độ cú pháp của các công thức hội [45]. Luận án sẽ xây dựng khoảng cách giữa hai công thức hội, phân tích các tiêu chuẩn cho công thức hội đồng thuận và đề xuất phương án tìm công thức hội đồng thuận. Kết quả này có thể áp dụng cho bài toán xử lý xung đột mức tiên đề. 3. Mục tiêu, đối tượng và phạm vi nghiên cứu của luận án Đối tượng nghiên cứu của luận án là ontology, tri thức không nhất quán trong ontology, và các phương pháp xử lý tri thức không nhất quán trong ontology. Trên cơ sở phân tích các động lực nghiên cứu, luận án xác định mục tiêu xử lý tri thức không nhất quán trong ontology theo hai tác vụ truy vấn và tích hợp. Mục tiêu nghiên cứu cụ thể của luận án được giới hạn theo ba bài toán sau đây: • Bài toán thứ nhất: Xác định câu trả lời có nghĩa khi truy vấn với ontology không nhất quán. Trong bài toán này, luận án nghiên cứu đề xuất phương pháp sử dụng ontology tham chiếu để tính khoảng cách ngữ nghĩa giữa hai khái niệm, giữa hai biểu thức khái niệm, giữa hai tiên đề. Khoảng cách ngữ nghĩa này sẽ được dùng để xây dựng hàm chọn của khung lập luận với ontology không nhất quán [21]. • Bài toán thứ hai: Xử lý xung đột mức khái niệm trong quá trình tích hợp ontology. Luận án sẽ áp dụng mô hình tổng quát tích hợp tri thức theo phương pháp đồng thuận [45] để tìm đồng thuận cho cấu trúc khái niệm. Sự không nhất quán trong cấu trúc khái niệm sẽ được giải quyết ở cả danh sách thuộc tính và miền giá trị của các thuộc tính. • Bài toán thứ ba: Xử lý xung đột mức tiên đề trong quá trình tích hợp 5 ontology. Trên cơ sở biểu diễn xung đột mức tiên đề trong quá trình tích hợp ontology dưới dạng xung đột về cú pháp [45], luận án đánh giá độ sai khác của các tập tiên đề và xây dựng phương pháp tìm tập tiên đề đồng thuận theo các tiêu chuẩn dựa trên độ sai khác này. 4. Ý nghĩa khoa học và thực tiễn của luận án Luận án nghiên cứu về các phương pháp xử lý tri thức không nhất quán trong ontology. Các điểm mới trong nghiên cứu của luận án là: • Đề xuất phương pháp sử dụng khoảng cách ngữ nghĩa theo ontology tham chiếu trong hàm chọn của khung lập luận với ontology không nhất quán. Hàm chọn được xây dựng sẽ không bị phụ thuộc cú pháp biểu diễn của các tiên đề trong ontology. • Đề xuất phương pháp dựa trên lý thuyết đồng thuận để xử lý xung đột mức khái niệm trong quá trình tích hợp ontology ở cả hai khía cạnh: danh sách thuộc tính và miền giá trị của các thuộc tính. • Đề xuất phương pháp dựa trên lý thuyết đồng thuận để xử lý xung đột mức tiên đề trong quá trình tích hợp ontology. Các đóng góp về mặt lý thuyết của luận án có ý nghĩa lớn trong các vấn đề thực tiễn: • Góp phần giải quyết bài toán truy vấn với ontology không nhất quán. Đây là vấn đề bức thiết trong thời đại dữ liệu liên kết mở (open linked data), trong đó tri thức không nhất quán được xem là một đặc tính phải chấp nhận. • Góp phần giải quyết xung đột trong quá trình tích hợp ontology theo hướng xây dựng trí tuệ nhóm (collective intelligence): Các kết quả lý thuyết về xử lý xung đột mức khái niệm và về mức tiên đề có thể được áp dụng trong bài toán xây dựng ontology theo kiểu cộng tác, đa người dùng của một wiki hay wiki ngữ nghĩa – một nền tảng đang rất phổ biến hiện nay. 5. Nội dung và bố cục của luận án Chương 1 trình bày tổng quan về xử lý tri thức không nhất quán trong 6 ontology theo hai hướng: (1) lập luận với ontology không nhất quán sử dụng chiến lược mở rộng tuyến tính tập tiên đề diễn giải theo truy vấn đầu vào, và (2) xử lý tri thức không nhất quán trong quá trình tích hợp ontology theo phương pháp đồng thuận. Trong chương này luận án trình bày các khái niệm cơ bản về khung lập luận với ontology không nhất quán sử dụng hàm chọn để mở rộng tuyến tính tập tiên đề diễn giải. Hàm chọn dựa trên sự liên quan cú pháp được giới thiệu trong chương như là ví dụ áp dụng khung lập luận và cũng làm cơ sở để so sánh với hàm chọn dựa trên khoảng cách ngữ nghĩa sẽ được xây dựng trong luận án. Luận án cũng trình bày phương pháp biểu diễn sự không nhất quán tri thức theo mô hình hồ sơ xung đột. Phương pháp xây dựng đồng thuận từ hồ sơ xung đột thông qua hàm đồng thuận cùng với các tiêu chuẩn cho hàm đồng thuận cũng sẽ được trình bày trong chương. Các cơ sở lý thuyết này được liên hệ đến bài toán xử lý tri thức không nhất quán trong quá trình tích hợp ontology theo phương pháp đồng thuận. Trong Chương 2, luận án trình bày cách xác định khoảng cách ngữ nghĩa giữa hai thực thể trên ontology (dựa vào số cung nối của chúng trên cây phân cấp). Trên cơ sở đó luận án xây dựng phương pháp hiệu quả để tính khoảng cách ngữ nghĩa giữa hai biểu thức thực thể bất kỳ khi đặt trên cây phân cấp của ontology này – gọi là ontology tham chiếu. Biểu thức thực thể ở đây có thể là biểu thức lớp, biểu thức thuộc tính đối tượng hoặc thuộc tính dữ liệu trong ontology OWL. Phần nội dung quan trọng của chương trình bày phương pháp xác định tập biểu thức thực thể của một tiên đề trong ontology OWL và xây dựng hàm chọn tập tiên đề diễn giải dựa vào khoảng cách ngữ nghĩa theo ontology tham chiếu. Chương này cũng trình bày các kết quả thực nghiệm cho việc áp dụng hàm chọn được đề xuất của luận án khi truy vấn với một số ontology không nhất quán. Chương 3 trình bày phương pháp đồng thuận xử lý tri thức không nhất quán mức khái niệm trong quá trình tích hợp ontology. Trong chương này, luận án giới thiệu mô hình tổng quát tích hợp tri thức theo phương pháp đồng thuận. Luận án áp dụng mô hình này để xử lý tri thức không nhất quán mức khái niệm theo hai khía cạnh: về danh sách thuộc tính và về miền giá trị của thuộc tính trong đặc tả khái niệm cần tích hợp. Phương pháp xác định khoảng cách 7 giữa hai miền giá trị của thuộc tính đối tượng và thuộc tính dữ liệu trong các ontology OWL cũng được trình bày trong chương này. Trong Chương 4, luận án trình bày mô hình biểu diễn sự không nhất quán tri thức mà trong đó một trạng thái tri thức được biểu diễn bằng một cấu trúc hội của các literal. Sau khi xây dựng hàm đánh giá khoảng cách với cấu trúc này, luận án phân tích các tiêu chuẩn của hàm đồng thuận và đưa ra phương pháp xây dựng đồng thuận của hồ sơ các cấu trúc hội. Áp dụng kết quả này luận án đề xuất phương pháp xử lý sự không nhất quán mức tiên đề trong quá trình tích hợp ontology. 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 giải quyết trong tương lai. 8 Chương 1. TỔNG QUAN VỀ XỬ LÝ TRI THỨC KHÔNG NHẤT QUÁN TRONG ONTOLOGY 1.1. Ontology và tri thức không nhất quán Có nhiều định nghĩa về ontology, nhưng định nghĩa thể hiện rõ bản chất của ontology và được trích dẫn nhiều nhất là của T. Gruber và W. Brost [5, 14]: “Ontology là một đặc tả hình thức, tường minh về một sự khái niệm hoá được chia sẻ”. Một “sự khái niệm hoá” nói đến một mô hình trừu tượng của một hiện tượng, chủ đề cụ thể bằng cách chỉ ra các khái niệm có liên quan của chủ đề đó. Tính “tường minh” được hiểu theo nghĩa, các kiểu khái niệm được sử dụng, các ràng buộc giữa chúng là được định nghĩa rõ ràng. Tính “hình thức” cho phép ontology có thể được sử dụng bởi máy tính. Cuối cùng, tính “được chia sẻ” cho biết, tri thức được mô tả bởi ontology được sự chấp nhận của một cộng đồng chứ không phải một cá nhân đơn lẻ. Các thành phần cấu trúc nên một ontology bao gồm tập các khái niệm, tập các cá thể, tập các quan hệ và tập các tiên đề như định nghĩa dưới đây. Định nghĩa 1.1 (Ontology [45]). Một ontology là một bộ bốn 〈C, I,R,Z〉, trong đó: • C là tập hợp các khái niệm (các lớp). • I là tập hợp các cá thể của các khái niệm. • R là tập hợp các quan hệ. • Z là tập hợp các tiên đề biểu diễn các ràng buộc toàn vẹn dùng để mô tả các thực thể (khái niệm, cá thể, quan hệ).  9 Ở Định nghĩa 1.1, R còn được gọi là tập thuộc tính. Các thuộc tính p ∈ R được định nghĩa bởi ánh xạ p : D → R, trong đó: D ⊆ C được gọi là miền xác định của thuộc tính và R được gọi là miền giá trị của thuộc tính. Người ta phân biệt hai loại thuộc tính: thuộc tính đối tượng dùng để liên kết các cá thể với nhau, và thuộc tính dữ liệu dùng để liên kết các cá thể với các giá trị dữ liệu. Một ontology có thể được xem là một tập tiên đề mô tả một tình huống cụ thể, gọi là một trạng thái tri thức – trong một lĩnh vực đang được quan tâm nào đó [26]. Chẳng hạn, ontology ở ví dụ dưới đây mô tả trạng thái tri thức cụ thể thuộc lĩnh vực sở hữu thú nuôi của con người. Ví dụ 1.1. Xét ontology Σ = 〈C, I,R,Z〉 với: • C = {Animal,Person,AnimalLover,Pet,Cat,Dog }. • I = { TOM,KITTY,MARY, JOHN }. • R = { hasPet, hasAge }. • Z = { Person v Animal, Pet v Animal, Cat v Pet, Dog v Pet, AnimalLover ≡ Person u (>3 hasPet.>), Pet u Person v ⊥, Dog u Cat v ⊥, ∃hasPet.> v Person, > v ∀ hasPet.Pet, ∃hasAge.> v Person, > v ∀hasAge.unsignedInt, Cat(TOM), Cat(KITTY), Person(MARY), Person(JOHN), hasPet(MARY,KITTY), hasAge(MARY,25) }. 10 Ý nghĩa của các tiên đề trong ontology Σ là như sau: • Cat(TOM),Cat(KITTY): TOM và KITTY là các cá thể của khái niệm Cat. • Person(MARY),Person(JOHN): MARY và JOHN là các cá thể của khái niệm Person. • AnimalLover ≡ Person u (>3 hasPet.>): Khái niệm AnimalLover gồm những cá thể thuộc khái niệm Person và có quan hệ với ít nhất 3 cá thể tuỳ ý thông qua thuộc tính hasPet. • ∃hasPet.> v Person: miền xác định của thuộc tính hasPet là khái niệm Person. • > v ∀hasPet.Pet: miền giá trị của thuộc tính hasPet là khái niệm Pet. • ∃hasAge.> v Person: miền xác định của thuộc tính hasAge là khái niệm Person. • > v ∀hasAge.unsignedInt: miền giá trị của thuộc tính hasAge là tập số nguyên không âm. • Pet u Person v ⊥: hai khái niệm Pet và Person không có chung cá thể nào. • Cat u Dog v ⊥: hai khái niệm Cat và Dog không có chung cá thể nào. • hasPet(MARY,KITTY): Cá thể MARY có quan hệ với cá thể KITTY thông qua thuộc tính hasPet. • hasAge(MARY,25): Cá thể MARY có quan hệ với cá thể số không âm 25 thông qua thuộc tính hasAge. Các thuộc tính hasPet, hasAge trong ontology tương ứng là thuộc tính đối tượng và thuộc tính dữ liệu.  Ý nghĩa hình thức của các tiên đề trong ontology được quy định cụ thể bởi ngôn ngữ xây dựng nên ontology. Ngôn ngữ ontology thông dụng nhất hiện nay là OWL2 được dựa trên logic mô tả SROIQ(D). Ngữ nghĩa của OWL2 được định nghĩa thông qua các phép diễn dịch, theo đó, các phép diễn dịch sẽ nêu tường minh mối quan hệ giữa cú pháp và ngữ nghĩa [19]: Một phép diễn dịch I = 〈∆I , ·I〉 gồm một miền diễn dịch khác rỗng 11 ∆I và một hàm diễn dịch ·I . Hàm diễn dịch ánh xạ (1) mỗi tên khái niệm A với một tập AI là tập con của ∆I , (2) mỗi tên thuộc tính p với một tập pI là tập con của một quan hệ nhị phân trên ∆I , và (3) mỗi tên khái niệm a với một đối tượng aI trong miền diễn dịch ∆I . Hàm diễn dịch được mở rộng với các khái niệm phức, vai trò phức (thông qua các tạo tử khái niệm, tạo tử vai trò của ngôn ngữ ontology) cũng như các tiên đề trong ontology. Định nghĩa chi tiết về ngữ nghĩa của OWL2 được nêu ở https://www.w3.org/TR/2012/ REC-owl2-direct-semantics-20121211. Một phép diễn dịch thoả tất cả các tiên đề trong ontology được gọi là một mô hình của ontology đó. Một ontology được gọi là không nhất quán nếu không có mô hình nào. Nguyên nhân dẫn đến điều này là do tập tiên đề của ontology có chứa mâu thuẫn. Tri thức không được phát biểu tường minh bởi các tiên đề trong ontology có thể được kiểm tra bằng cách đánh giá kết quả truy vấn: Gọi α là một tiên đề. Truy vấn α với ontolog... thực thể (tên khái niệm, tên vai trò, tên cá thể) trong tổng thể biểu thức của chúng. Chẳng hạn, với C và D là hai tên khái niệm bất kỳ, Cunionsq¬D được xét theo tập {C,D} thay vì tổng thể biểu thức này! Hơn nữa, máy tìm kiếm Google không thể giúp ích được trong việc đánh giá độ liên quan ngữ nghĩa của các ”từ khoá” vô nghĩa như “C”, “D”! Một ví dụ đơn giản khác cũng chỉ ra sự bất hợp lý khi không xét các thực thể trong tổng thể biểu thức của chúng : Với C và D là hai khái niệm bất với sự liên quan về cú pháp chỉ được đánh giá bằng hai trạng thái “Có liên quan” hoặc “Không liên quan” 30 kỳ, chúng ta sẽ không thấy sự liên quan nào giữa C unionsq ¬C và D unionsq ¬D (do về mặt cú pháp thì “C” 6= “D” ), trong khi về mặt ngữ nghĩa, hai biểu thức khái niệm này cùng biểu diễn khái niệm đỉnh (>). Để khắc phục các nhược điểm nêu trên, luận án đề xuất phương án đánh giá sự liên quan của hai tiên đề trong quá trình mở rộng tuyến tính tập tiên đề diễn giải dựa trên khoảng cách ngữ nghĩa của một ontology tham chiếu: Thay vì sử dụng tri thức đa dụng được đánh chỉ mục bởi Google, luận án sẽ dùng các cây phân cấp khái niệm, cây phân cấp thuộc tính của một ontology – gọi là ontology tham chiếu – để đánh giá khoảng cách giữa hai khái niệm và khoảng cách giữa hai thuộc tính. Luận án sử dụng phương pháp của Wu và Palmer [62] để tính khoảng cách ngữ nghĩa của hai khái niệm trên ontology: phương pháp này tính khoảng cách ngữ nghĩa giữa hai khái niệm dựa vào số cung nối giữa chúng trên cây phân cấp khái niệm của ontology tham chiếu. Cách tiếp cận này của luận án hoàn toàn có thể được áp dụng để tính khoảng cách ngữ nghĩa giữa hai biểu thức khái niệm hoặc hai biểu thức thuộc tính nhờ vậy tránh được nhược điểm của các hàm chọn trước đó (không thể tính được khoảng cách giữa hai biểu thức khái niệm, biểu thức thuộc tính trong các tiên đề). Các vấn đề đặt ra cho luận án để xây dựng hàm chọn dựa trên khoảng cách ngữ nghĩa của ontology tham chiếu là: • Cần phải có phương pháp tính hiệu quả khoảng cách ngữ nghĩa của hai biểu thức khái niệm khi xét chúng trên ontology tham chiếu. Điều này thực sự quan trọng về mặt hiệu năng do việc tính khoảng cách ngữ nghĩa giữa hai biểu thức khái niệm được sử dụng nhiều lần, với nhiều biểu thức khái niệm khác nhau trong quá trình mở rộng tập tiên đề diễn giải. • Cần phải xác định tập biểu thức khái niệm, tập biểu thức thuộc tính trong các tiên đề. • Cần phải xác định độ liên quan ngữ nghĩa của hai tiên đề theo khoảng ngữ nghĩa của các biểu thức khái niệm, biểu thức thuộc tính xuất hiện trong hai tiên đề đó. 31 Những vấn đề này sẽ được phân tích và giải quyết chi tiết trong Chương 2 của luận án. 1.3. Xử lý tri thức không nhất quán trong quá trình tích hợp ontology theo phương pháp đồng thuận Việc tích hợp tri thức đến từ nhiều nguồn độc lập nhau không đơn giản là phép tổng gộp, giữa các nguồn này có thể không nhất quán nhau. Nói cách khác, chúng ta cần phải xử lý tri thức không nhất quán trong quá trình tích hợp. Mục này của luận án sẽ trình bày hồ sơ xung đột [45] như là mô hình hình thức để biểu diễn sự không nhất quán tri thức. Một số công cụ xử lý hồ sơ xung đột thuộc phương pháp đồng thuận sẽ được giới thiệu và làm cơ sở để đề xuất ý tưởng xử lý tri thức không nhất quán trong quá trình tích hợp ontology. 1.3.1. Hồ sơ xung đột Gọi U là một tập hữu hạn các đối tượng biểu diễn các ý kiến tiềm năng về chủ đề xung đột đã xác định trước. U được gọi là tập vũ trụ. Gọi ∏ k(U) là tập hợp tất cả các bộ gồm k phần tử lập được từ tập hợp U, với k ∈ N∗. Gọi ∏ (U) là tập hợp tất cả các bộ lập được từ tập hợp U:∏ (U) = ⋃ k∈N∗ (∏ k(U) ) Mỗi phần tử trong ∏ (U) được gọi là một hồ sơ xung đột, hoặc gọi ngắn gọn là một hồ sơ. Một hồ sơ xung đột biểu diễn một nội dung xung đột về một chủ đề đã được xác định trước. Chúng ta biểu diễn hồ sơ xung đột và sử dụng một số phép toán với các hồ sơ xung đột được định nghĩa bởi Lipski và Marek [30] như mô tả sau đây. Biểu thức X = {x, x, y, y, y, z} biểu diễn một hồ sơ với lực lượng là 6, viết là card(X) = 6. Trong hồ sơ này phần tử x xuất hiện 2 lần, y xuất hiện 3 lần, và z xuất hiện 1 lần. X còn có thể được viết dưới dạng X = {2 ∗ x, 3 ∗ y, 1 ∗ z} . Phép tổng hai hồ sơ được ký hiệu là ∪˙ và được định nghĩa như sau: Nếu phần tử x xuất hiện trong hồ sơ X n lần, trong hồ sơ Y n′ lần thì trong hồ sơ 32 tổng X ∪˙ Y phần tử này xuất hiện n+ n′ lần. Ví dụ, với X = {2 ∗ x, 3 ∗ y, 1 ∗ z} và Y = {4 ∗ x, 2 ∗ y} thì X ∪˙ Y = {6 ∗ x, 5 ∗ y, 1 ∗ z}. Phép hiệu của hai hồ sơ được ký hiệu là − và được định nghĩa như sau: Nếu phần tử x xuất hiện trong X n lần, trong Y n′ lần thì trong tập hợp hiệu của chúng X−Y, x xuất hiện n− n′ lần nếu n ≥ n′, và 0 lần trong trường hợp ngược lại. Chúng ta phân biệt những lớp hồ sơ xung đột theo định nghĩa sau đây. Định nghĩa 1.13 (Phân loại hồ sơ xung đột [45]). Một hồ sơ xung đột X ∈∏(U) được gọi là: (1) Hồ sơ đồng nhất nếu mọi phần tử của nó là giống nhau; nghĩa là X = {n ∗ x} với x ∈ U và n ∈ N. (2) Hồ sơ phân biệt được, nếu các phần tử của nó là khác nhau từng đôi một. (3) Bội của một hồ sơ Y, viết là X = n ∗ Y, nếu Y = {x1, x2, . . . , xk} và X = {n ∗ x1, n ∗ x2, . . . , n ∗ xk} với k, n ∈ N và n > 1. (4) Hồ sơ chính tắc, nếu nó là phân biệt được hoặc là bội của một hồ sơ phân biệt được.  1.3.2. Sự không nhất quán tri thức Giả sử có một tập cho trước A gồm các tác tử hoạt động trong môi trường phân tán. Thuật ngữ “tác tử” ở đây được hiểu theo nghĩa là một chuyên gia hoặc một chương trình máy tính thông minh, có thể hoạt động tự chủ và độc lập. Những tác tử này được giả thiết là có cơ sở tri thức riêng. Một trạng thái của cơ sở tri thức phản ánh một trạng thái của thế giới thực của tác tử tại một mốc thời gian nào đó. Trạng thái này có thể được xem như là một khung nhìn hoặc một ý kiến của tác tử về một vấn đề nào đó. Về mặt tổng quát, cấu trúc của cơ sở tri thức của tác tử có thể khác nhau. 33 Giả sử các tác tử trong tập hợp A làm việc với một tập hợp hữu hạn các chủ đề mà chúng quan tâm. Tập hợp này ký hiệu là S. Gọi U là tập hợp các phần tử biểu diễn tất cả các trạng thái tri thức mà tác tử có thể dùng để đưa ra ý kiến về các chủ đề. Chúng ta giả thiết hai phần tử khác nhau của U sẽ biểu diễn hai trạng thái tri thức với “nội dung” khác nhau. Với mỗi phần tử u ∈ U, ta gọi ngắn gọn “trạng thái u” thay cho “trạng thái tri thức biểu diễn bởi phần tử u”. Một tác tử a ∈ A tham chiếu đến chủ đề s ∈ S có thể sinh ra các loại tri thức sau: • Tri thức khẳng định: một trạng thái u ∈ U được gọi là tri thức khẳng định của tác tử a về chủ đề s nếu theo ý kiến của tác tử, trạng thái u là mô tả hợp lý nhất liên quan đến chủ đề s. • Tri thức phủ định: một trạng thái u ∈ U được gọi là tri thức phủ định của tác tử a về chủ đề s nếu theo ý kiến của tác tử, trạng thái u không thể là mô tả hợp lý nhất liên quan đến chủ đề s. • Tri thức không chắc chắn: một trạng thái u ∈ U được gọi là tri thức không chắc chắn của tác tử a về chủ đề s nếu nó không biết trạng thái u là mô tả hợp lý hay không hợp lý liên quan đến chủ đề s. Tri thức khẳng định biểu diễn loại ý kiến của tác tử mà thứ gì đó phải diễn ra, trong khi đó tri thức phủ định của tác tử diễn đạt ý kiến phản đối của nó. Cùng một tác tử, trạng thái biểu diễn tri thức khẳng định phải khác với trạng thái biểu diễn tri thức phủ định của nó. Theo cách này đối với một chủ đề s ∈ S chúng ta có thể định nghĩa những hồ sơ sau đây: • Hồ sơ khẳng định X+(s): tập hợp các trạng thái tri thức từ U biểu diễn tri thức khẳng định của các tác tử tham chiếu đến chủ đề s. • Hồ sơ phủ định: X−(s): tập hợp các trạng thái tri thức từ U biểu diễn tri thức phủ định của các tác tử tham chiếu đến chủ đề s. • Hồ sơ không chắc chắn X±(s): tập hợp các trạng thái tri thức từ U biểu diễn tri thức không chắc chắn của các tác tử về chủ đề s. Các hồ sơ khẳng định, phủ định và không chắc chắn về chủ đề s phải đảm bảo các điều kiện: • Rời nhau từng đôi một. 34 • Chúng là những bộ có lặp vì một số tác tử có thể sinh ra cùng trạng thái tri thức. Sự không nhất quán tri thức hay xung đột tri thức về một chủ đề cho trước được định nghĩa trên cơ sở hồ sơ xung đột như sau. Định nghĩa 1.14 (Sự không nhất quán tri thức [45]). Chúng ta gọi có sự không nhất quán tri thức hay xung đột tri thức về chủ đề s xuất hiện nếu ít nhất một trong hai hồ sơ X+(s) và X−(s) là không đồng nhất.  Định nghĩa 1.14 cho thấy một xung đột diễn ra nếu tối thiểu có hai tác tử sinh ra các trạng thái tri thức (khẳng định hoặc phủ định) về cùng chủ đề. Định nghĩa này không nói đến hồ sơ không chắc chắn X±(s) với lý do vai trò của tri thức không chắc chắn không quan trọng bằng vai trò của hai loại tri thức kia. Khi nói về một chủ đề, các tác tử có cùng tri thức khẳng định và tri thức phủ định thì mặc dù trạng thái không chắc chắn của chúng là khác nhau, ta có thể nói không có xung đột giữa chúng. Các tập hợp X+(s) và X−(s) còn được gọi tương ứng là hồ sơ xung đột khẳng định và hồ sơ xung đột phủ định của chủ đề s. Ví dụ 1.7. Xét một nhóm chuyên gia phân tích tình hình kinh tế của một quốc gia và dự đoán mức tăng trưởng GDP trong một năm cho trước. Một chuyên gia có thể đưa ra một khoảng giá trị dự đoán sẽ chứa mức tăng trưởng GDP trong năm này. Ông ta cũng có thể đưa ra một khoảng giá trị khác dự đoán không chứa mức tăng trưởng GDP. Chúng ta sử dụng các tập con của tập số thực để định nghĩa trạng thái của tri thức. Bảng sau đây trình bày ý kiến của 5 chuyên gia: Chuyên gia X+ X− X± E1 [3, 5] (−∞, 3), (5,+∞) ∅ E2 [2, 6] (−∞, 2), (6, 8) [8,+∞) E3 4 (1, 3), (7,+∞) (−∞, 1), (3, 4), (4, 7] E4 [3, 5] (−∞, 3), (5,+∞) ∅ E5 [3, 5] (−∞, 3), (10,+∞) (5, 10] Ở đây ta có một xung đột vì các hồ sơ X+ và X− là không đồng nhất. Để ý 35 rằng các ý kiến của các chuyên gia E2, E3, E5 không phủ hết tập số thực. Điều này có nghĩa là, các chuyên gia có thể bỏ qua một số giá trị. Chẳng hạn, chuyên gia E5 không biết liệu mức tăng trưởng GDP có thể thuộc về khoảng (5, 10] hay không.  Để đánh giá khoảng cách giữa hai phần tử trong tập vũ trụ U, người ta sử dụng một nửa-mêtric được định nghĩa như sau. Định nghĩa 1.15 (Hàm đánh giá khoảng cách [45]). Hàm d : U × U → [0, 1] được gọi là hàm đánh giá khoảng cách giữa hai phần tử trong tập vũ trụ U nếu thoả các tính chất: 1) Không âm: ∀x, y ∈ U : d(x, y) ≥ 0 ; 2) Phản xạ: ∀x, y ∈ U : d(x, y) = 0 nếu và chỉ nếu x = y ; 3) Đối xứng: ∀x, y ∈ U : d(x, y) = d(y, x) .  Cặp (U, d) còn được gọi là một không gian nửa-mêtric. Hàm d có thể dùng để đánh giá mức độ sai khác giữa hai trạng thái tri thức trong tập vũ trụ U cũng như dùng để đánh giá độ nhất quán của một hồ sơ xung đột. Việc đánh giá độ nhất quán của hồ sơ xung đột là cần thiết cho rất nhiều tình huống: chẳng hạn, giúp đánh giá mức gắn kết, độ hội tụ tri thức của các phần tử trong một hồ sơ, hoặc giúp so sánh độ nhất quán của hai hồ sơ. Độ nhất quán của hồ sơ xung đột cũng có thể là cơ sở để thực hiện bước xử lý tiếp theo trong quá trình xử lý tri thức [1]. Độ nhất quán của hồ sơ xung đột được đánh giá thông qua hàm c định nghĩa như sau: c : ∏ (U)→ [0, 1]. Định nghĩa dưới đây mô tả bộ tiêu chuẩn cho hàm nhất quán. Định nghĩa 1.16 (Tiêu chuẩn của hàm nhất quán [45]). Giả sử tập vũ trụ U chứa tối thiểu 2 phần tử, (U, d) là một không gian nửa-mêtric. Các tiêu chuẩn cho hàm nhất quán được định nghĩa như sau. 36 P1a. Tiêu chuẩn về độ nhất quán cực đại: Nếu X là hồ sơ đồng nhất thì c(X) = 1. P1b. Tiêu chuẩn mở rộng về độ nhất quán cực đại: Với x ∈ U, Y,Z ∈∏(U), Y = {x} và X(n) = (n ∗Y) ∪˙ Z là hồ sơ có phần tử x xuất hiện ít nhất n lần, số lần xuất hiện của các phần tử khác trong Z là cố định. Khi đó: lim n→+∞ c(X (n)) = 1 . P2a. Tiêu chuẩn về độ nhất quán cực tiểu: Nếu X = {a, b} và d(a, b) = max{d(u, v) | u, v ∈ U} và X 6= n ∗U,∀n ∈ N∗ thì c(X) > 0. P2c. Tiêu chuẩn thay thế cho nhất quán cực tiểu: Nếu X = U thì c(X) = 0. P3. Tiêu chuẩn về độ nhất quán khác 0: Nếu tồn tại các phần tử a, b ∈ X mà d(a, b) < max{d(u, v) | u, v ∈ U} và X 6= n ∗U,∀n ∈ N∗ thì c(X) > 0. P4. Tiêu chuẩn về hồ sơ không đồng nhất: Nếu X là một hồ sơ không đồng nhất thì c(X) < 1. P5. Tiêu chuẩn về hồ sơ bội: Nếu hồ sơ X là bội của hồ sơ Y thì c(X) = c(Y). P6. Tiêu chuẩn về độ tin cậy lớn hơn: Ký hiệu − d(u,X) :=∑x∈X d(u, x) (biểu diễn tổng khoảng cách giữa một phần tử u ∈ U đến các phần tử của hồ sơ X). − D(X) := {d(u,X) | u ∈ U}. Với mọi hồ sơ X,Y ∈∏(U), ta có:( min{D(X)} card(X) ≤ min{D(Y)} card(Y) ) ⇒ (c(X) ≥ c(Y)) . P7a. Tiêu chuẩn về cải thiện tính nhất quán: 37 Cho a và a′ là những phần tử trong tập vụ trụ U sao cho: d(a,X) = min{d(x,X) | x ∈ X} và d(a′,X) = min{d(x,X) | x ∈ U} . Khi đó: c(X− {a}) ≤ c(X) ≤ c(X ∪˙ {a′}). P7b. Tiêu chuẩn thứ hai về cải thiện tính nhất quán: Cho b và b′ là những phần tử trong tập vũ trụ U sao cho: d(b,X) = max{d(x,X) | x ∈ X} và d(b′,X) = max{d(x,X) | x ∈ U} . Khi đó: c(X ∪˙ {b′}) ≤ c(X) ≤ c(X− {b}) . P8. Tiêu chuẩn về đơn giản hoá: Cho Y,Z ∈∏(U) là những hồ sơ và X(n) = (n ∗ Y) ∪˙ Z. Khi đó: lim n→+∞ c(X (n)) = c(Y) .  Gọi X = {x1, x2, . . . , xM} là một hồ sơ xung đột. Các thông số dưới đây thường được dùng để định nghĩa hàm nhất quán [45]: • Ma trận khoảng cách giữa các phần tử của hồ sơ X là: DX = [ dXij ] =  d(x1, x1) d(x1, x2) · · · d(x1, xM ) d(x1, x1) d(x1, x2) · · · d(x1, xM ) ... ... . . . ... d(xM , x1) d(xM , x2) · · · d(xM , xM )  (1.9) • Vector gồm các khoảng cách trung bình giữa một phần tử đến các phần tử còn lại trong hồ sơ (với M > 1) là: WX = {wX1 , wX2 , . . . , wXM} (1.10) 38 trong đó, wXi = 1 M − 1 M∑ j=1 dXji = 1 M − 1 ( d(x1, xi) + d(x2, xi) + · · ·+ d(xM , xi) ) với i = 1, 2, . . . ,M. Lưu ý rằng mặc dù tổng trên cóM phần tử nhưng giá trị trung bình chỉ được tính choM−1 phần tử với lý do dXii = 0 ∀i = 1, 2, . . . ,M . • Đường kính của hồ sơ X được định nghĩa là: Diam(X) = max{d(x, y) | x, y ∈ X} (1.11) và phần tử lớn nhất của vector WX: Diam(WX) = max{wXi | i = 1, 2, . . . ,M} (1.12) biểu diễn phần tử trong hồ sơ X sinh ra tổng khoảng cách lớn nhất đến các phần tử còn lại. Do các giá trị của hàm khoảng cách d thuộc về đoạn [0, 1] nên chúng ta quy ước đường kính của U là 1, nghĩa là: Diam(U) = 1 . • Khoảng cách trung bình trong hồ sơ X là: dmean(X) =  1 M(M−1) M∑ i=1 M∑ j=1 dXij = 1 M M∑ i=1 WXi , với M > 1 0 , với M = 1 (1.13) Giá trị dmean(X) biểu diễn giá trị trung bình của tất cả khoảng cách giữa những phần tử khác nhau của hồ sơ. Lưu ý rằng từ “khác nhau” ở đây có ý nghĩa là “chỉ số khác nhau” chứ không phải “khác nhau về nội dung”. • Khoảng cách trung bình tổng trong hồ sơ X: dt_mean(X) = ∑ x,y∈X d(x, y) M(M + 1) = M − 1 M + 1 .dmean(X) . (1.14) • Tổng khoảng cách của một phần tử u thuộc vũ trụ U đến các phần tử trong hồ sơ X là d(u,X) = ∑ x∈X d(u, x) . (1.15) 39 • Cực tiểu tổng khoảng cách đến các phần tử trong hồ sơ X là dmin(X) = min{d(u,X) | u ∈ U} . (1.16) • Tập hợp các tổng khoảng cách đến hồ sơ X là D(X) = {d(u,X) | u ∈ U} . (1.17) Có 5 hàm nhất quán thường được sử dụng trong thực tế là: • c1(X) = 1−Diam(X) = 1−max{d(x, y) | x, y ∈ X} . • c2(X) = 1−Diam(WX) = 1−max{wXi | i = 1, 2, . . . ,M} . • c3(X) = 1− dmean(X) . • c4(X) = 1− dt_mean(X) . • c5(X) = 1− dmin(X) . Người ta đã chứng minh được rằng, các tiêu chuẩnP1a,P1b,P2a,P2b,P2c, P3, P4, P5, P6, P7a, P7b, P8 là độc lập nhau, theo nghĩa hàm nhất quán nếu thoả tiêu chuẩn này thì không chắc chắn sẽ thoả tiêu chuẩn khác [45]. Bảng 1.1 cho thấy tính thoả của các hàm nhất quán c1, c2, c3, c4, c5 so với bộ tiêu chuẩn này [45], trong đó, ký hiệu + cho biết hàm thoả tiêu chuẩn, ký hiệu - cho biết hàm không thoả tiêu chuẩn, và ký hiệu ± cho biết hàm chỉ thoả một phần tiêu chuẩn tương ứng. Bảng 1.1: Tính thoả tiêu chuẩn của một số hàm nhất quán thông dụng [45] P1a P1b P2a P2b P2c P3 P4 P5 P6 P7a P7b P8 c1 + - + + + - + + - - - - c2 + - + - - - + + - + + - c3 + + + - - + + - - + + + c4 + + - + - + + - + + + + c5 + + - - - + + + + ± ± - 1.3.3. Hàm đồng thuận Với một hồ sơ xung đột thể hiện một sự không nhất quán tri thức, điều người ta quan tâm là cần đánh giá xem liệu có thể tìm được trạng thái tri thức 40 đồng thuận từ các trạng thái tri thức trong hồ sơ hay không, và nếu có thì đồng thuận đó được xác định như thế nào. Khả năng tìm được đồng thuận từ hồ sơ xung đột có thể được quyết định theo độ nhất quán của hồ sơ đó. Trong khi đó hàm đồng thuận thể hiện các lựa chọn đồng thuận dựa trên hồ sơ đầu vào. Định nghĩa 1.17. Hàm đồng thuận trong không gian nửa-mêtric (U, d) là ánh xạ C : ∏ (U)→ 2U trong đó, 2U ký hiệu tập hợp gồm tất cả các tập con của U.  Với mỗi hồ sơ xung đột X ∈∏(U), tập hợp C(X) được gọi là đại diện của X, và một phần tử của C(X) được gọi là một đồng thuận của hồ sơ X. Ký hiệu Con(U) biểu diễn tập tất cả các hàm đồng thuận trong không gian nửa-mêtric (U, d). Định nghĩa dưới đây mô tả bộ tiêu chuẩn cho hàm đồng thuận trong (U, d). Định nghĩa 1.18 (Tiêu chuẩn cho hàm đồng thuận [45]). Gọi U là tập vũ trụ, (U, d) là một không gian nửa-mêtric. Một hàm đồng thuận C ∈ Con(U) cần thoả mãn một hoặc nhiều tiêu chuẩn trong bộ tiêu chuẩn sau đây (gọi là bộ tiêu chuẩn cho hàm đồng thuận): 1. Tính tin cậy (Re - Reliability) nếu: C(X) 6= ∅ với ∀X ∈ ∏ (U), card(X) > 0 . 2. Tính nhất trí (Un - Unanimity) nếu: C{n ∗ u} = {u} với ∀n ∈ N,∀u ∈ U . 3. Tính đơn giản (Sim - Simplification) nếu: (Hồ sơ X là bội của hồ sơ Y)⇒ (C(X) = C(Y)) . 4. Tính gần-nhất trí (Qu - Quasi-Unanimity) nếu: ∀u ∈ U : (u /∈ C(X))⇒ (∃n ∈ N : u ∈ C(X ∪˙ (n ∗ u))) . 41 5. Tính nhất quán (Co - Consistency) nếu: ∀u ∈ U : (u ∈ C(X))⇒ (u ∈ C(X ∪˙ {u})) . 6. Tính nhất quán Condorcet (Cc - Condorcet consistency) nếu: C(X1) ∩ C(X2) 6= ∅ ⇒ C(X1 ∪˙ X2) = C(X1) ∪ C(X2) . 7. Tính nhất quán chung (Gc - General consistency) nếu: C(X1) ∩ C(X2) ⊆ C(X1 ∪˙ X2) ⊆ C(X1) ∪ C(X2) . 8. Tính đồng biến (Pr - Proportion) nếu: (X1 ⊆ X2 ∧ x ∈ C(X1) ∧ y ∈ C(X2))⇒ d(x,X1) ≤ d(x,X2) 9. Tính tối ưu - 1 (Tiêu chuẩn O1) nếu: ∀u ∈ U : u ∈ C(X)⇒ d(u,X) = min{d(v,X) | v ∈ U} . 10. Tính tối ưu - 2 (Tiêu chuẩn O2) nếu: ∀u ∈ U : u ∈ C(X)⇒ d2(u,X) = min{d2(v,X) | v ∈ U}, trong đó d2(v,X) ký hiệu cho ( d(v,X) )2 với v ∈ U.  Tiêu chuẩn O1 thường được áp dụng cho các bài toán trong thực tế khi cần lựa chọn phần tử đại diện từ một hồ sơ xung đột. Hàm C(X), X ∈∏(U) được gọi là hàm đồng thuận-O1 nếu thoả tiêu chuẩn O1, tức là: ∀u ∈ U : u ∈ C(X)⇒ d(u,X) = min{d(v,X) | v ∈ U} . Ví dụ dễ thấy nhất trong thực tế sử dụng tiêu chuẩn O1 là bài toán bầu cử, trong đó, các thành viên cần bầu ra một hội đồng. Rõ ràng, các thành viên trong hội đồng chính là sự đồng thuận được lấy từ các lá phiếu (ý kiến của các thành viên). Tương tự như vậy, hàm đồng thuận C(X) được gọi là hàm đồng thuận-O2 nếu ∀u ∈ U : u ∈ C(X)⇒ d2(u,X) = min{d2(v,X) | v ∈ U} . 42 Hàm đồng thuận-O2 thường được dùng để xác định đồng thuận của các ý kiến xây dựng phương án mà trong đó, phương án cần tìm là độc lập với phương án của các thành viên tham gia. Chẳng hạn, đồng thuận được xác định trong Ví dụ 1.7 cần phải được xác định theo tiêu chuẩn O2 do mức GDP của quốc gia trong một năm cụ thể trên thực tế không bị ảnh hưởng bởi ý kiến của các chuyên gia. Sơ đồ ở Hình 1.3 mô tả chiến lược sử dụng tiêu chuẩn O1 hay O2 trong các bài toán thực tế [45]. Hình 1.3: Sơ đồ áp dụng hàm đồng thuận O1 và O2 Nói chung, không phải từ bất kỳ hồ sơ xung đột nào chúng ta cũng có thể chọn ra được một giải pháp đồng thuận. Định nghĩa dưới đây cho biết tính khả đồng thuận theo tiêu chuẩn O1 của một hồ sơ X. 43 Định nghĩa 1.19 (Tiêu chuẩn khả đồng thuận [45]). Trên không gian nửa- mêtric (U, d), hồ sơ X ∈∏(U) là khả đồng thuận theo tiêu chuẩn O1 nếu và chỉ nếu: dt_mean(X) ≥ dmin(X) . (1.18)  1.3.4. Các nghiên cứu liên quan xử lý không nhất quán tri thức trong quá trình tích hợp ontology bằng phương pháp đồng thuận Đặc tính có thể mở rộng, có thể chia sẻ được của ontology là một trong những nhân tố thúc đẩy cho sự phát triển và hiện thực hoá tầm nhìn của web ngữ nghĩa [4]. Người ta đã xây dựng các ontology mức cao như DOLCE [11], SUMO [28], BFO [12], GFO [18], Cyc [33], . . . đóng vai trò như là tri thức cơ sở để xây dựng các ontology khác. Bằng cách này, cơ sở tri thức có thể được tạo và chia sẻ bởi nhiều tổ chức, trải rộng trên nhiều lĩnh vực mà, về mặt lý thuyết, vẫn đảm bảo được sự nhất quán, không xung đột lẫn nhau. Tuy vậy, trên thực tế, việc tái sử dụng tri thức từ các ontology mức cao lại không làm giảm đi các nguy cơ tiềm tàng gây xung đột. Điều này là bởi trong quá trình xây dựng ontology luôn có yếu tố tự quyết định của các chuyên gia hoặc tác tử tri thức. Chẳng hạn, Hình 1.5 cho thấy bốn chuyên gia khi xây dựng ontology về lĩnh vực đào tạo có thể mô tả khái niệm Course (khoá học) theo những cách khác nhau khi tái sử dụng ontology OREF−TREE (Hình 1.4). Bài toán đặt ra ở đây là: làm thế nào để có thể tích hợp được ý kiến của các chuyên gia này? hay, làm thế nào để giải quyết sự không nhất quán giữa các ontology được mô tả? Hình 1.4: Trích dẫn của ontology tham chiếu OREF−TREE Dạng xung đột ở bài toán nêu trên chính là xung đột mức khái niệm trong quá trình tích hợp ontology. Một mức xung đột khác cũng phổ biến trong quá trình 44 Hình 1.5: Trích dẫn ontology của 4 chuyên gia tích hợp ontology đó là xung đột về tập tiên đề. Xung đột mức tiên đề thường xảy ra trong các môi trường xây dựng ontology theo kiểu cộng tác, đa người dùng [6, 60, 61]. Trong những môi trường này, một ontology có thể được xây dựng bởi nhiều người dùng tự nguyện thông qua một wiki ngữ nghĩa (semantic wiki) [17, 27, 37] hoặc bởi các chuyên gia được thuê [34]. Thách thức lớn nhất trong mô hình xây dựng ontology này nằm ở giai đoạn tổng hợp tri thức: người tổng hợp cần xử lý tình huống mà trong đó một số tiên đề và phủ định của nó cùng được phát biểu bởi các người dùng tham gia xây dựng ontology. Cả hai bài toán nêu trên đều thuộc loại điển hình để có thể giải quyết bằng phương pháp đồng thuận. Các tác giả Nguyễn Ngọc Thành và Trương Hải Bằng [49, 58], Dương Trọng Hải, Nguyễn Ngọc Thành và Kozierk [9] đã đưa ra các phương án xử lý xung đột mức khái niệm trong quá trình tích hợp ontology theo phương pháp đồng thuận. Tuy vậy, các tác giả chỉ tập trung xây dựng danh sách thuộc tính của khái niệm cần tích hợp. Trong khi đó, miền giá trị của các thuộc tính được xác định bằng cách lấy hợp của các miền giá trị thành phần. Điều này có nghĩa sự xung đột về miền giá trị của thuộc tính là chưa được xử lý. Trên cơ sở mô hình tích hợp tri thức tổng quát theo phương pháp đồng thuận [45] luận án sẽ đề xuất phương án xử lý xung đột mức khái niệm trong quá trình tích hợp ontology, trong đó có xét đến cả hai khía cạnh: danh sách thuộc tính và miền giá trị của thuộc tính. Thách thức chính để xử lý xung đột về miền giá trị của các thuộc tính là phải xây dựng được hàm đánh giá khoảng cách cho các miền giá trị. Nội dung này sẽ được trình bày trong Chương 3 của luận án. 45 Hiện nay vẫn chưa có công trình nghiên cứu đầy đủ phương án giải quyết cho bài toán xử lý xung đột về tập tiên đề trong quá trình tích hợp ontology nói chung, cũng như trong quá trình xây dựng ontology cộng tác nói riêng. Luận án đề xuất một phương án đơn giản để có thể giải quyết các bài toán này theo phương pháp đồng thuận. Bằng cách biểu diễn một tiên đề dưới dạng một literal , tri thức đóng góp của mỗi người dùng có thể được biểu diễn dưới dạng hội của các literal đó. Như vậy, bài toán xử lý xung đột về tập tiên đề trong quá trình xây dựng ontology cộng tác có thể được dẫn về bài toán tìm đồng thuận của hồ sơ xung đột gồm các công thức hội của các literal , còn được gọi là bài toán xử lý xung đột ở cấp độ cú pháp [45]. Các thách thức đặt ra của bài toán này là: • Xây dựng hàm đánh giá khoảng cách giữa hai cấu trúc hội của các literal . • Phân tích mối quan hệ của hàm đánh giá khoảng cách này với các tiêu chuẩn đồng thuận, từ đó đề ra phương pháp xây dựng đồng thuận cho một hồ sơ xung đột đầu vào. Chương 4 của luận án sẽ trình bày chi tiết nội dung này. 1.4. Tiểu kết Chương 1 Chương này đã trình bày tổng quan về ontology và sự không nhất quán tri thức trong ontology. Hai vấn đề được luận án đặt ra cần giải quyết liên quan đến sự không nhất quán tri thức với ontology là tìm kết quả có nghĩa khi truy vấn với ontology không nhất quán và xử lý xung đột trong quá trình tích hợp ontology. Các khái niệm cơ bản và tổng quan về các cách tiếp cận để giải quyết các vấn đề này cũng đã được giới thiệu trong chương: (1)Khung lập luận với ontology không nhất quán sử dụng chiến lược phát triển tuyến tính tập tiên đề diễn giải và (2) Phương pháp đồng thuận để xử lý sự không nhất quán tri thức. Chương này cũng phác thảo cách tiếp cận của luận án cũng như thách thức đặt ra cho các tiếp cận để giải quyết các bài toán không nhất quán tri thức trong ontology. 46 Chương 2. SUY LUẬN VỚI ONTOLOGY KHÔNG NHẤT QUÁN SỬ DỤNG HÀM CHỌN DỰA TRÊN KHOẢNG CÁCH NGỮ NGHĨA CỦA ONTOLOGY THAM CHIẾU Trong chương này luận án xây dựng một hàm chọn dựa trên khoảng cách ngữ nghĩa của một ontology tham chiếu để áp dụng vào khung lập luận với ontology không nhất quán. Nội dung của chương được trình bày theo trình tự như sau: Mục 2.1 trình bày phương pháp đánh giá khoảng cách ngữ nghĩa giữa hai thực thể có tên (named entity) trong một ontology. Trên cơ sở đó, Mục 2.2 trình bày phương pháp quy hoạch động để đánh giá khoảng cách ngữ nghĩa giữa hai biểu thức thực thể bất kỳ (biểu thức khái niệm, biểu thức thuộc tính đối tượng, biểu thức thuộc tính dữ liệu) khi đặt chúng trên cây phân cấp tương ứng của một ontology – gọi là ontology tham chiếu. Trong Mục 2.3, bằng cách xét các tiên đề dưới dạng các biểu thức thực thể, luận án trình bày phương pháp đánh giá khoảng cách giữa hai tiên đề theo ontology tham chiếu. Mục này cũng phân loại và trình bày cách xác định tập biểu thức thực thể trong 32 dạng tiên đề của ontology OWL2. Cuối cùng, Mục 2.4 mô tả phép suy luận không chuẩn sử dụng hàm chọn dựa trên khoảng cách ngữ nghĩa của ontology tham chiếu. Ontology có thể được xem là một tập các tiên đề, mà mỗi tiên đề được xây dựng từ các thực thể khái niệm, vai trò, cá thể theo quy tắc cú pháp và ngữ nghĩa được quy định bởi ngôn ngữ ontology cụ thể. Ngôn ngữ ontology thông dụng nhất hiện nay là OWL2 được dựa trên logic mô tả SROIQ. Các tiên đề bao hàm của ontology OWL2 cấu trúc nên các cây phân cấp1 của các thực thể: cây phân cấp của các lớp/khái niệm2, cây phân cấp các thuộc tính đối tượng và 1Trên thực tế, hầu hết các tiên đề của ontology OWL (ngôn ngữ ontology được sử dụng rộng rãi nhất hiện nay) đều có thể biểu diễn được dưới dạng quan hệ bao hàm, tức là có dạng: C v D (với C, D là các biểu thức khái niệm), hoặc R v S (với R, S là các biểu thức thuộc tính). 2Luận án sử dụng hai thuật ngữ “class” và “concept” với nghĩa tương đương nhau, và tương ứng 47 cây phân cấp các thuộc tính dữ liệu. Vì tính tương tự của khái niệm và thuộc tính trên cây phân cấp của chúng nên trong các mục tiếp theo, luận án chỉ phân tích khoảng cách ngữ nghĩa giữa hai khái niệm trên cây phân cấp. Có nhiều phương pháp đánh giá khoảng cách ngữ nghĩa của hai khái niệm. Danh sách các phương pháp và đặc điểm của từng phương pháp đánh giá khoảng cách ngữ nghĩa của hai khái niệm trong ontology có thể xem tại [57]. Luận án sử dụng phương pháp của Wu và Palmer [62] để đánh giá khoảng cách ngữ nghĩa của hai khái niệm có tên trong ontology. Phương pháp này đánh giá khoảng cách ngữ nghĩa của hai khái niệm dựa vào số cung nối thuộc đường đi giữa chúng trên cây phân cấp khái niệm của ontology. Đặc điểm này cho phép luận án có thể áp dụng nguyên lý quy hoạch động để tính khoảng cách ngữ nghĩa giữa hai biểu thức khái niệm bất kỳ. Điều này sẽ được phân tích cụ thể ở các mục tiếp theo của chương. 2.1. Khoảng cách ngữ nghĩa giữa hai khái niệm trong ontology Gọi O là một ontology, CO là tập tất cả khái niệm có tên trong O. Với c1, c2 ∈ CO là hai khái niệm có tên trong ontology O, chúng ta sử dụng một số ký hiệu sau: • DPO(c1) là tập các khái niệm có tên trong O là khái niệm cha trực tiếp (direct parent concept) của c1. • DCO(c1) là tập các khái niệm có tên trong O là khái niệm con trực tiếp (direct child concept) của c1. • LCPO(c1, c2) là tập các khái niệm có tên trong O là khái niệm cha chung tối thiểu (least common parent concept) của c1 và c2: LCPO(c1, c2) = {c ∈ CO | c1 v c ∧ c2 v c ∧ (∀c′ ∈ CO : c1 v c′ ∧ c2 v c′ ⇒ c v c′)} . Khi đã xác định rõ ontology O, chúng ta có thể bỏ qua chỉ số O trong các ký hiệu DPO, DCO, LCPO. với thuật ngữ tiếng Việt là “khái niệm”. 48 Định nghĩa 2.1 (Số cung nối trực tiếp tối thiểu µ giữa hai khái niệm trên ontology). Gọi O là một ontology. Với hai khái niệm c1, c2 ∈ CO, ta nói k ∈ N là số cung nối trực tiếp tối thiểu từ c1 đến c2 trên cây phân cấp khái niệm của O, ký hiệu µO(c1, c2) = k, nếu tồn tại d1, d2, . . . , dk là dãy ngắn nhất các khái niệm có tên trong O sao cho: c1 ≡ d1 c2 ≡ dk di ∈ DCO(di+1) với ∀i = 1, 2, . . . , k − 1. Ta quy ước: • µO(c, c) = 0 với ∀c ∈ CO. • µO(c1, c2) = +∞ khi c1 ≡ ⊥ hoặc O 6|= c1 v c2 (không tồn tại đường đi từ c1 đến c2 trên cây phân cấp khái niệm của O). • Trong trường hợp đã xác định rõ ontology O, ta có thể viết µ thay vì µO .  Với một ontology O cùng với tập khái niệm có tên CO, chúng ta có thể tính được các giá trị µO(c1, c2) (c1, c2 ∈ CO) bằng cách áp dụng các thuật toán như Floyd [10], Ford-Bellman [3], . . . trên đồ thị lập được từ quan hệ bao hàm (@) giữa các khái niệm của ontology. Khoảng cách ngữ nghĩa của hai khái niệm có tên trong ontology được xác định thông qua µO như định nghĩa dưới đây. Định nghĩa 2.2 (Khoảng cách ngữ nghĩa δ của hai khái niệm trên ontology [62]). Khoảng cách ngữ nghĩa δ của hai khái niệm có tên c1, c2 trong ontology O, ký hiệu ...hất, giả sử rằng⋂ x∈X x+ * x∗+; (4.5) Điều này có nghĩa, tồn tại một ký hiệu t ∈ ⋂x∈X x+ sao cho t /∈ x∗+. Khi đó, ta tạo công thức hội x′∗ = (x′∗+, x∗−) với x′∗+ = x∗+ ∪ {t}. Với mỗi x ∈ X, ta có, theo Định nghĩa 4.4 về hàm khoảng cách giữa hai tập hợp: η(x′∗+, x+) = card(x′∗+4 x+) card(L) = card((x∗+ ∪ {t})4 x+) card(L) . Do t /∈ x∗+ và t ∈ ⋂x∈X x+ (theo giả thiết) nên ta có ∀x ∈ X: card((x∗+ ∪ {t})4 x+) = card(x∗+4 x+)− 1 . 102 Như vậy, ∀x ∈ X: η(x′∗+, x+) = card((x∗+ ∪ {t})4 x+) card(L) = card(x∗+4 x+)− 1 card(L) < card(x∗+4 x+) card(L) = η(x∗+, x+) . Do đó: ∑ x∈X η(x′∗+, x+) < ∑ x∈X η(x∗+, x+) d∧(x′∗,X) = ∑ x∈X (1 2 .η(x′∗+, x+) + 1 2 .η(x∗−, x−) ) < ∑ x∈X (1 2 .η(x∗+, x+) + 1 2 .η(x∗−, x−) ) = d∧(x∗,X) Điều này trái với giả thiết (( (x∗+, x∗−) ∈ C(X)) ∧ (C(X) ` H5)). Vậy (4.3) là đúng (đpcm). Chứng minh tương tự ta cũng có (4.4) là đúng. (b) C `H5 ⇒ C `H2 Gọi X ∈ ∏(Conj(L) là một hồ sơ tuỳ ý, C ∈ Cco là một hàm đồng thuận thoả tiêu chuẩn H5. Gọi (x∗+, x∗−) ∈ C(X) là một đồng thuận của hồ sơ X. Để chứng minh H2 cũng thoả bởi C, ta phải chứng minh⋃ x∈X x+ ⊇ x∗+ (4.6) và ⋃ x∈X x− ⊇ x∗− (4.7) Với phụ thuộc thứ nhất, giả sử rằng⋃ x∈X x+ + x∗+; (4.8) Điều này có nghĩa, tồn tại một ký hiệu t ∈ x∗+ sao cho t /∈ ⋃x∈X x+. Khi đó, ta tạo công thức hội x′∗ = (x′∗+, x∗−) với x′∗+ = x∗+ \ {t}. 103 Với mỗi x ∈ X, ta có: η(x′∗+, x+) = card(x′∗+4 x+) card(L) = card((x∗+ \ {t})4 x+) card(L) Do t ∈ x∗+ và t /∈ ⋃x∈X x+ (theo giả thiết) nên ta có ∀x ∈ X: card((x∗+ \ {t})4 x+) = card(x∗+4 x+)− 1 Như vậy, ∀x ∈ X: η(x′∗+, x+) = card((x∗+ \ {t})4 x+) card(L) = card(x∗+4 x+) + 1 card(L) < card(x∗+4 x+) card(L) = η(x∗+, x+) Do đó: ∑ x∈X η(x′∗+, x+) > ∑ x∈X η(x∗+, x+) d∧(x′∗,X) = ∑ x∈X (1 2 .η(x′∗+, x+) + 1 2 .η(x∗−, x−) ) < ∑ x∈X (1 2 .η(x∗+, x+) + 1 2 .η(x∗−, x−) ) = d∧(x∗,X) Điều này trái với giả thiết (( (x∗+, x∗−) ∈ C(X)) ∧ (C(X) ` H5)). Do đó, giả thiết (4.8) là sai. Vậy (4.6) là đúng (đpcm). Chứng minh tương tự ta cũng có (4.7) là đúng. Định lý 4.3. Thành phần khẳng định và thành phần phủ định của một đồng thuận thoả tiêu chuẩn H5 có thể được xác định độc lập nhau; nghĩa là, một công thức hội (x∗+, x∗−) là một đồng thuận của X nếu và chỉ nếu công thức hội (x∗+, ∅) là đồng thuận của X′ = {(xi+, ∅) | i = 1, 2, . . . , n}, và công thức hội (∅, x∗−) là đồng thuận của X′′ = {(∅, xi−) | i = 1, 2, . . . , n}. 104 Chứng minh. Định lý sẽ được chứng minh theo hai chiều (a) và (b) như sau: (a) Nếu (x∗+, x∗−) là một đồng thuận H5 của hồ sơ X thì • (x∗+, ∅) là một đồng thuận H5 của hồ sơ X′ = {(xi+, ∅) | i = 1, 2, . . . , n}, và • (∅, x∗−) là một đồng thuậnH5 của hồ sơ X′′ = {(∅, xi−) | i = 1, 2, . . . , n}; Mệnh đề đầu tiên được chứng minh bằng phản chứng như dưới đây. Với X ∈∏(Conj(L)) là một hồ sơ các công thức hội, (x∗+, x∗−) là một đồng thuận H5 của hồ sơ X. Giả sử (x∗+, ∅) không phải là một đồng thuận H5 của hồ sơ X′ = {(xi+, ∅) : i = 1, 2, . . . , n}. Gọi y∗ = (y∗+, y∗−) là một đồng thuận H5 của hồ sơ X′: y∗ 6= (x∗+, ∅). Do y∗ là đồng thuận H5 của X′ nên theo Định lý 4.2 (C ` H5 ⇒ C ` H2), ta có: y∗− = ∅. Ngoài ra, theo định nghĩa của một đồng thuận H5, ta có: ∑ x∈X′ η(y∗+, x+) + ∑ x∈X′ η(∅, x−) < ∑ x∈X′ η(x∗+, x+) + ∑ x∈X′ η(∅, x−) Điều này có nghĩa:∑ x∈X′ η(y∗+, x+) < ∑ x∈X′ η(x∗+, x+) ⇔ n∑ i=1 η(x′∗+, x+) < n∑ i=1 η(x∗+, xi+) ⇔ n∑ i=1 η(y∗+, xi+) + n∑ i=1 η(x∗−, xi+) < n∑ i=1 η(x∗+, xi+) + n∑ i=1 η(x∗−, xi+) ⇔ d∧ ( (y∗+, x∗−),X ) < d∧ ( (x∗+, x∗−),X ) . Như vậy, tồn tại công thức hội (y∗+, x∗−) mà d∧ ( (y∗+, x∗−),X ) < d∧ ( (x∗+, x∗−),X ) . Điều này mâu thuẫn với giả thiết rằng (x∗+, x∗−) là một đồng thuận H5 của X. Vậy, mệnh đề đầu tiên là đúng. Một cách tương tự, ta cũng chứng minh được mệnh đề thứ hai. (b) Nếu • (x∗+, ∅) là đồng thuận H5 của hồ sơ X′ = {(xi+, ∅) | i = 1, 2, . . . , n}, và • (∅, x∗−) là đồng thuận H5 của hồ sơ X′′ = {(∅, xi−) | i = 1, 2, . . . , n}; 105 thì (x∗+, x∗−) là đồng thuận H5 của hồ sơ X = {(xi+, xi−) | i = 1, 2, . . . , n}. Điều này được chứng minh như sau: Với mỗi công thức hội (y+, y−) ∈ Conj(L), ta có: • d∧ ( (x∗+, ∅),X′() ≤ d∧(((y+, ∅),X′) , và • d∧ ( (∅, x∗−),X′′() ≤ d∧(((∅, y−),X′′) Vì vậy, d∧ ( (x∗+, ∅),X′)+ d∧((∅, x∗−),X′′) ≤ d∧((y+, ∅),X′)+ d∧((∅, y−),X′′) hay là d∧ ( (x∗+, x∗−),X ) ≤ d∧((y+, y−),X) Bất đẳng thức cuối cùng chứng tỏ rằng (x∗+, x∗−) là một đồng thuận H5 của hồ sơ X. Định lý 4.2 cho thấy nếu đồng thuận thoả tiêu chuẩn H5 thì cũng thoả hai tiêu chuẩn H1 và H2. Trong khi đó, Định lý 4.3 chỉ ra rằng hai thành phần khẳng định và phủ định của đồng thuận thoả tiêu chuẩn H5 có thể được xác định độc lập nhau. Định lý dưới đây sẽ chỉ ra cách để xác định đồng thuận thoả tiêu chuẩn H5 của hồ sơ xung đột. Định lý 4.4. Cho X = {xi ∈ Conj(L) | i = 1, 2, . . . , n} là một hồ sơ xung đột gồm các công thức hội, X ∈∏(Conj(L)). Gọi: • Z+ (tương ứng, Z−) là tập hợp tất cả các literal xuất hiện trong các thành phần dương (tương ứng, thành phần âm) của các công thức hội thuộc hồ sơ X. • f+(z) (tương ứng, f−(z)) là số lần xuất hiện của phần tử z trong các thành phần dương (tương ứng, thành phần âm) của các công thức hội thuộc hồ sơ X. Giả sử C(X) là một hàm chọn đồng thuận thoả tiêu chuẩn H5. Khi đó, x∗ = (x∗+, x∗−) ∈ C(X) nếu và chỉ nếu: (a) x∗+ = { z ∈ Z+ | f+(z) >= n 2 } , và 106 (b) x−+ = { z ∈ Z− | f−(z) >= n 2 } . Chứng minh. Theo Định lý 4.3, ta có thể xây dựng đồng thuận x∗ = (x∗+, x∗−) thoả tiêu chuẩn H5 bằng cách xây dựng một cách độc lập hai đồng thuận x∗+ và x∗− của tương ứng hai hồ sơ X+ = {xi+ | i = 1, 2, . . . , n} và X− = {xi− | i = 1, 2, . . . , n}. Ta sẽ phải chứng minh (a) x∗+ = { z ∈ Z+ | f+(z) >= n 2 } . Việc chứng minh (b) là hoàn toàn tương tự. Trước hết, theo Định lý 4.2, x∗+ chỉ có thể chứa các literal thuộc về Z+. Mặt khác, ta sẽ chứng minh thêm, với một công thức hội bất kỳ x ∈ Conj(L), ta có: (i) Nếu z ∈ Z+ thoả f+(z) ≥ n 2 mà z /∈ x+ thì d∧((x+, x−),X+) ≤ d∧ ( (x+ ∪ {z}, x−),X+) . (ii) Nếu z ∈ Z+ thoả f+(z) < n 2 mà z /∈ x+ thì d∧((x+, x−),X+) > d∧ ( (x+ ∪ {z}, x−),X+) . Thật vậy, với X ∈∏(Conj(L)), x ∈ Conj(L), z ∈ L, xét khoảng cách d∧((x+∪ {z}, x−),X): d∧((x+ ∪ {z}, x−),X) = ∑ y∈X ( 1 2 . card((x+ ∪ {z})4 y+) card(L) + 1 2 . card(x−4 y−) card(L) ) . Nhận thấy: card((x+ ∪ {z})4 y+) card(L) =  card(x+4 y+)− 1 card(L) nếu y+ 3 z card(x+4 y+) + 1 card(L) nếu y+ = z Gọi Xz := {x ∈ X | x+ 3 z} và Xz := {x ∈ X | x+ = z}. Ta có, card(Xz) = f+(z) và card(Xz) = n− f+(z). 107 Như vậy: ∑ y∈X card((x+ ∪ {z})4 y+) card(L) = ∑ y∈Xz card((x+ ∪ {z})4 y+) card(L) + ∑ y∈Xz card((x+ ∪ {z})4 y+) card(L) = ∑ y∈Xz card(x+4 y+)− 1 card(L) + ∑ y∈Xz card(x+4 y+) + 1 card(L) = ∑ y∈X card(x+4 y+) card(L) + −f+(z) + n− f+(z) card(L) = ∑ y∈X card(x+4 y+) card(L) + n− 2.f+(z) card(L) . Do đó: d∧((x+ ∪ {z}, x−),X) = ∑ y∈X ( 1 2 . card((x+ ∪ {z})4 y+) card(L) + 1 2 . card(x−4 y−) card(L) ) = ∑ y∈X ( 1 2 .( card(x+4 y+) card(L) + n− 2.f+(z) card(L) ) + 1 2 . card(x−4 y−) card(L) ) =d∧(x,X) + 1 2 . n− 2.f+(z) card(L) . Như vậy, khi n − 2.f+(z) ≤ 0, hay f+(z) ≥ n 2 thì việc bổ sung z vào x+ sẽ không làm tăng tổng khoảng cách của x đến hồ sơ X. Ngược lại, khi f+(z) < n 2 thì việc bổ sung z vào x+ sẽ làm tăng tổng khoảng cách của x đến hồ sơ X. Nói cách khác, (i) và (ii) được chứng minh. Trở lại việc chứng minh (a). Có thể thấy rằng, xuất phát từ tập hợp { z ∈ Z+ | f+(z) >= n 2 } , ta không thể loại bỏ bớt phần thuộc tập hợp này, hoặc bổ sung thêm phần tử ngoài Z+ trong quá trình thành lập thành phần khẳng định của đồng thuận. Nói cách khác, đây chính là thành phần khẳng định của đồng thuận. Do đó (a) là đúng (đpcm). Nhận xét về các tiêu chuẩn đồng thuận Trong mục này, luận án đã phân tích mối liên quan của các tiêu chuẩn đồng thuận, thể hiện qua các định lý 4.1, 4.2, 4.3 và 4.4. Có một điểm lưu ý rằng, các 108 mối liên quan này có được là do cách xây dựng khoảng cách giữa hai tập hợp các ký hiệu trong Định nghĩa 4.4. Trên thực tế, để đánh giá khoảng cách giữa hai tập hợp, người ta có thể sử dụng tiếp cận khác như ở [45]: η(X1,X2) = card(X14X2) card(X1 ∪X2 , (4.9) Cách đánh giá khoảng cách giữa hai tập hợp như công thức (4.9) có ưu điểm là không phụ thuộc vào lực lượng của tập literal . Tuy nhiên nếu áp dụng cách tiếp cận này để tính khoảng cách giữa hai cấu trúc hội thì sẽ bài toán tìm đồng thuận hồ sơ cấu trúc hội trở nên phức tạp: Định lý 4.4 sẽ không còn đúng nữa! Ngoài ra, trong công trình [45] tác giả Nguyễn Ngọc Thành cũng đã chỉ ra rằng bài toán tìm đồng thuận H5 trong trường hợp này là bài toán thuộc lớp NP-đầy đủ! Phần tiếp theo sau đây, luận án sẽ trình thuật toán hiệu quả để xây dựng đồng thuận cho hồ sơ các công thức hội nhờ tận dụng các đặc trưng có được nhờ Định nghĩa 4.4. 4.1.3. Thuật toán xác định đồng thuận Dựa vào các tính chất của các tiêu chuẩn đã được phân tích ở Tiểu mục 4.1.2, phần này sẽ trình bày cách xây dựng đồng thuận x∗ = (x∗+, x∗−) của một hồ sơ xung đột X ∈∏(Conj(L)) theo chiến lược ưu tiên các tiêu chuẩn với thứ tự như sau: H5, H4, H1, H2, H3 và H6. Định lý 4.2 cho thấy điều kiện được định nghĩa trong tiêu chuẩn H5 là rất quan trọng, bởi vì nói chung một đồng thuận thoả tiêu chuẩn này thì cũng thoả tiêu chuẩn H1 và H2. Ngoài ra, theo Định lý 4.3, việc xác định các thành phần dương và âm của một đồng thuận có thể được thực hiện một cách độc lập. Vì thế, việc tính toán công thức hội tối ưu (x∗+, x∗−) ∈ C(X) mà X = {xi = (xi +, xi −) ∈ Conj(L) | i = 1, 2, . . . , n} có thể được chia ra làm 2 việc nhỏ tương tự nhau: xác định thành phần dương của đồng thuận và xác định thành phần âm của đồng thuận: ∑ x∈X η(x∗+, x+) = min {∑ x∈X η(x′+, x+) | x′ ⊆ L } 109 và ∑ x∈X η(x∗−, x−) = min {∑ x∈X η(x′−, x−) | x′ ⊆ L } . Định lý 4.4 chỉ ra cách tìm các thành phần này, tuy nhiên, định lý này lại không đảm bảo được đồng thuận tìm được thoả tiêu chuẩn H4. Trên cơ sở của các phân tích này, luận án đề xuất thuật toán xác định đồng thuận. Ý tưởng của thuật toán là như sau: • Trước hết, chúng ta xác định tập hợp Z+ và Z− gồm tương ứng các literal âm và literal dương có trong các công thức hội thuộc hồ sơ xung đột X. • Với mỗi literal z trong Z+ và Z− thống kê tần số xuất hiện của nó trong các thành phần dương và thành phần âm của các công thức hội thuộc hồ sơ X. • Nếu có literal trong Z+ hoặc Z− xuất hiện quá bán thì sẽ tồn tại đồng thuận thoả tiêu chuẩn P5 cho hồ sơ xung đột. Gọi đồng thuận đó là x∗, khi đó x∗+ sẽ chứa các literal xuất hiện quá bán trong thành phần dương của các công thức hội thuộc hồ sơ X. Tương tự, thành phần âm của đồng thuận, x∗− sẽ chứa các literal xuất hiện quá bán trong các thành phần âm của các công thức hội thuộc X. Tuy nhiên, sẽ có trường hợp mà một literal cùng xuất hiện trong cả hai thành phần x∗+ và x∗− (do literal này cùng xuất hiện quá bán trong các thành phần dương và âm của các công thức hội thuộc hồ sơ X). Để đảm bảo đồng thuận x∗ là nhất quán (thoả tiêu chuẩn P4), chúng ta phải loại các literal đó ra khỏi x∗+ hoặc x∗−. Giả sử z ∈ x∗+ ∩ x∗−. Bằng cách xem xét d+ = d∧ ( (x∗+ \{z}, x∗−),X) và d− = d∧((x∗+, x∗− \{z}),X), nếu d+ > d− thì chúng ta sẽ loại z khỏi thành phần dương của x∗. Trong trường hợp ngược lại, z sẽ bị loại khỏi thành phần âm của x∗. Đồng thuận thu được sẽ thoả các tiêu chuẩn H5 (do đó cũng thoả tiêu chuẩn H1, H2), H4 và H6. • Trong trường hợp không có literal nào xuất hiện quá bán ở hai thành phần âm hoặc dương của các công thức hội thì chúng ta ưu tiên tìm đồng thuận thoả tiêu chuẩn H3 của hồ sơ xung đột: − Nếu Z+ ∩Z− = ∅ thì x∗ = (Z+,Z−) chính là đồng thuận H3 của hồ sơ. 110 − Ngược lại, đồng thuận của hồ sơ xung đột là công thức được chọn ra từ X và có tổng khoảng cách đến các công thức khác đạt cực tiểu. Các ý tưởng này được thể hiện trong Thuật toán 4.1: Thuật toán 4.1: Xác định đồng thuận từ hồ sơ gồm các công thức hội Đầu vào: Hồ sơ xung đột X ∈∏(Conj(L)), X = { (xi +, xi −) | i = 1, 2, . . . , n;n ∈ N∗}, xi + ∩ xi− = ∅ ∀i = 1, 2, . . . , n. Đầu ra: Đồng thuận x∗ ∈ Conj(L) thoả một hoặc nhiều tiêu chuẩn trong tập hợp {H1,H2,H3,H4,H5,H6}. begin Z+ := ⋃ x∈X x+; Z− := ⋃ x∈X x−; foreach z ∈ Z+ do f+(z) := card{x ∈ X | x+ 3 z}; foreach z ∈ Z− do f−(z) := card{x ∈ X | x− 3 z}; Bước 1 x∗+ := {z ∈ Z+ | f+(z) ≥ n 2 }; x∗− := {z ∈ Z− | f−(z) ≥ n 2 }; if (x∗+ ∪ x∗− 6= ∅) then Bước 2 foreach z ∈ x∗+ ∩ x∗− do if d∧ ( (x∗+ \ {z}, x∗−),X) < d∧((x∗+, x∗− \ {z}),X) then x∗+ := x∗+ \ {z}; else x∗− := x∗− \ {z}; else if (Z+ ∩ Z− = ∅) then Bước 3 x∗ := (Z+,Z−); else Bước 4 x∗ := x1; for i := 2 to n do if d∧(x∗,X) > d∧(x,X) then x∗ := xi 111 Chứng minh tính đúng của thuật toán Theo cách hoạt động được chỉ ra ở Thuật toán 4.1, chúng ta bắt đầu tìm đồng thuận thoả tiêu chuẩn H5 (phần (a)). Sau đó: (i) Nếu cả hai thành phần dương và âm của đồng thuận H5 đều rỗng, thuật toán sẽ ưu tiên xét tìm đồng thuận thoả tiêu chuẩn H3 (phần (c)) nếu hồ sơ X là nhất quán. Trong trường hợp hồ sơ là không nhất quán, theo phần (d), chúng ta sẽ chọn từ hồ sơ X một phần tử có tổng khoảng cách đến các phần tử còn lại trong hồ sơ là cực tiểu. Đồng thuận trong trường hợp này luôn luôn thoả tiêu chuẩn H4 (do các xi đều là các công thức hội thoả xi+ ∩ xi− = ∅, ∀i = 1, 2, . . . , n, theo giả thiết). (ii) Nếu ở phần (a) xác định được một trong hai thành phần, phần dương và âm của đồng thuận là khác rỗng, chúng ta phải tìm cách làm mịn hai thành phần này để đảm bảo tiêu chuẩn H4 được thoả, đồng thời cũng đảm bảo tổng khoảng cách từ đồng thuận đến các phần tử trong hồ sơ là cực tiểu. Ngoài ra, trong tất cả các trường hợp xử lý thuộc hai nhánh phân tích (i) và (ii) ở trên, chúng ta đều xây dựng x∗+ (tương ứng, x∗−) từ các phần tử thuộc Z+ (tương ứng, Z−). Vì vậy đồng thuận luôn luôn thoả tiêu chuẩn H2. Đồng thuận cũng luôn luôn thoả tiêu chuẩn H1 vì nó được xây dựng từ đồng thuận thoả tiêu chuẩn H5, sau đó, các phần tử bị loại đi chỉ là những phần tử có tần số xuất hiện ít hơn n 2 . Độ phức tạp của Thuật toán 4.1 Với n là lực lượng của hồ sơ X, m = max { card( ⋃ x∈X x+), card( ⋃ x∈X x−) } . Các bước trong thuật toán có độ phức tạp như sau: • Bước khởi tạo: thống kê tần số xuất hiện các literal trong các thành phần của các công thức hội trong hồ sơ. Độ phức tạp của thủ tục này là O(m.n.m) = O(n.m2). • Bước 1 dùng để tạo ra các tập hợp khởi đầu cho x∗+, x∗− dựa trên tần số xuất hiện của các literal . Độ phức tạp của bước này là O(m). • Trong Bước 2, với mỗi literal chung z của x∗+ và x∗−, chúng ta so sánh 112 khoảng cách với X khi loại bỏ z ở một trong hai thành phần này để tìm được thành phần tốt hơn. Độ phức tạp của bước này là O(m.n.m2) = O(n.m3). • Bước 3 kiểm tra sự giao nhau của hai tập hợp Z+, Z−, có độ phức tạp là O(m2). • Bước 4 tính khoảng cách của từng công thức hội x với hồ sơ xung đột X (để tìm ra công thức hội đạt cực tiểu khoảng cách đến X). Độ phức tạp của bước này là O(n.n.m2) = O(n2.m2). Sau bước khởi tạo và Bước 1, thuật toán chỉ thực hiện một trong ba bước: hoặc Bước 2 hoặc Bước 3 hoặc Bước 4. Độ phức tạp của thuật toán tương ứng cho ba trường hợp này là: • O(max{n.m2,m, n.m3}) = O(n.m3) • O(max{n.m2,m,m2}) = O(n.m2) • O(max{n.m2,m, n2.m2}) = O(n2.m2) Như vậy, độ phức tạp của thuật toán sẽ là O(max{n.m3, n.m2, n2.m2}). Nếu m < n thì độ phức tạp của thuật toán là O(n2.m2). Trong trường hợp còn lại, độ phức tạp của thuật toán là O(n.m3). Ví dụ minh hoạ cho Thuật toán 4.1 Sử dụng các ký hiệu L = {t1, t2, t3, t4} để biểu diễn các tính chất của thuộc tính hasSpouse như ở Ví dụ 4.1, 6 tác tử a1, a2, . . . , a6 đưa ra ý kiến dưới dạng các công thức hội như Bảng 4.2 bên dưới. Chúng ta sẽ áp dụng Thuật toán 4.1 để tìm tri thức đồng thuận từ các ý kiến của các tác tử. Hồ sơ X được thành lập gồm các công thức hội như sau: X = { ({t1, t3, t4}, {t2}), 2 ∗ ({t1}, {t3, t4}), ({t1}, {t3}), ({t3}, {t1}), ({t3}, ∅) } Sau bước (a) của thuật toán, chúng ta có: x∗+ = {t1, t3} và x∗− = {t3, t4}. Do x∗+ ∪ x∗− 6= ∅ nên chúng ta sẽ tìm cách loại những literal chung ở một trong hai thành phần của đồng thuận (theo bước (b)): Với x∗+ ∩ x∗− = {t3}, ta xét hai tổng khoảng cách sau đây: d∧ ( ({t1}, {t3, t4}),X ) và d∧ ( ({t1, t3}, {t4}),X ) 113 Bảng 4.2: Trạng thái tri thức của các tác tử cho bài toán minh hoạ Tác tử Trạng thái tri thức a1 t1 ∧ ¬t2 ∧ t3 ∧ t4 a2 t1 ∧ ¬t3 ∧ ¬t4 a3 t1 ∧ ¬t3 a4 t1 ∧ ¬t3 ∧ ¬t4 a5 ¬t1 ∧ t3 ∧ ¬t4 a6 t3 Với chú ý card(L) = 4, ta lần lượt tính: d∧ ( ({t1}, {t3, t4}), ({t1, t3, t4}, {t2}) ) = 1 2 . card({t1} 4 {t1, t3, t4}) 4 + 1 2 . card({t3, t4} 4 {t2}) 4 = 5 8 Tương tự, • d∧ ( ({t1}, {t3, t4}), ({t1}, {t3, t4}) ) = 0 • d∧ ( ({t1}, {t3, t4}), ({t1}, {t3}) ) = 28 • d∧ ( ({t1}, {t3, t4}), ({t3}, {t1, t4}) ) = 48 • d∧ ( ({t1}, {t3, t4}), ({t3}, ∅) ) = 48 • d∧ ( ({t1, t3}, {t4}), ({t1, t3, t4}, {t2}) ) = 28 • d∧ ( ({t1, t3}, {t4}), ({t1}, {t3, t4}) ) = 28 • d∧ ( ({t1, t3}, {t4}), ({t1}, {t3}) ) = 38 • d∧ ( ({t1, t3}, {t4}), ({t3}, {t1, t4}) ) = 28 • d∧ ( ({t1, t3}, {t4}), ({t3}, ∅) ) = 28 Như vậy: 114 • d∧ ( ({t1}, {t3, t4}),X ) = 5 8 + 2 ∗ 0 + 2 8 + 4 8 + 4 8 = 15 8 • d∧ ( ({t1, t3}, {t4}),X ) = 2 8 + 2 ∗ 2 8 + 3 8 + 2 8 + 2 8 = 13 8 Do d∧ ( ({t1, t3}, {t4}),X ) = 13 8 < 15 8 = d∧ ( ({t1}, {t3, t4}),X ) nên ta quyết định loại t3 khỏi x∗−. Cuối cùng, đồng thuận của hồ sơ X là ({t1, t3}, {t4}), hay là t1 ∧ t3 ∧ ¬t4. 4.2. Xử lý xung đột mức tiên đề trong quá trình tích hợp ontology Một ontology có thể được xem xét như là một tập các tiên đề biểu diễn tri thức về một lĩnh vực cụ thể. Nếu dùng một literal để biểu diễn một tiên đề trong ontology, tri thức của ontology có thể được biểu diễn dưới dạng công thức hội của các literal đó. Chính vì vậy, sự không nhất quán về tập tiên đề của các ontology có thể được biểu diễn như là một hồ sơ xung đột của các công thức hội của các literal . Với nhận xét này, bài toán xử lý xung đột mức tiên đề trong quá trình tích hợp ontology có thể được giải quyết dựa trên kết quả của Mục 4.1. Xét n (n ∈ N∗) ontologyO1,O2, . . . ,On, trong đó mỗi ontologyOi (i = 1, 2, . . . , n) được biểu diễn bằng một bộ bốn 〈Ci, Ii,Ri,Zi〉, với: • Ci là tập khái niệm trong ontology Oi • Ii là tập cá thể trong ontology Oi • Ri là tập mối quan hệ trong ontology Oi • Zi = {zi1, zi2, . . . , zini} là tập tiên đề trong ontology Oi, gồm ni tiên đề. Ontology Oi (i = 1, 2, . . . , n) thể hiện một trạng thái tri thức biểu diễn bằng một công thức zi1 ∧ zi2 ∧ · · · ∧ zini . Việc tích hợp n ontology O1,O2, . . . ,On được hiểu là tìm tập tiên đề có thể đại diện cho n tập tiên đề Z1,Z2, . . . ,Zn. Gọi Z := {t1, t2, . . . , tm} (m ∈ N∗) là tập các literal sao cho mọi tiên đề trong ontology Oi (i = 1, 2, . . . , n) đều có thể biểu diễn dưới dạng literal hoặc phủ định của literal trong Z: ∀α ∈ Zi(i = 1, 2, . . . , n), ∃t ∈ Z : (t ≡ α) ∨ (¬t ≡ α). Với tập hợp Z này, chúng ta có thể xem một ontology Oi là một trạng thái tri thức được biểu diễn bằng một công thức hội xi ∈ Conj(Z) với xi ≡ zi1∧zi2∧· · ·∧zini. Như vậy, với n ontology O1,O2, . . . ,On chúng ta có thể lập được một hồ sơ 115 X = {x1, x2, . . . , xn} trong đó xi ≡ zi1∧zi2∧· · ·∧zini. Đồng thuận x∗ của hồ sơ X xác định được bằng Thuật toán 4.1 sẽ là tập tiên đề tốt nhất về mặt cú pháp từ các ontology đã cho. Tuy nhiên, x∗ có thể là không nhất quán về mặt ngữ nghĩa. Đối với trường hợp này, chúng ta có thể khắc phục bằng chọn ra trong Z1,Z2, . . . ,Zn một tập tiên đề ít sai khác nhất so với x∗ (tập tiên đề có tổng khoảng cách đến x∗ đạt cực tiểu). Từ phân tích nêu trên, luận án đề xuất Thuật toán 4.2 xác định đồng thuận về mặt cú pháp của các tập tiên đề Z1,Z2, . . . ,Zn. Ý tưởng của thuật toán là như sau: • Xây dựng tập literal Z sao cho mọi tập tiên đề của các ontology đều có thể biểu diễn dưới dạng một công thức hội Conj(Z). • Với mỗi tập tiên đề Zi, (i = 1, 2, . . . , n), cho bổ sung α ∈ L nếu α là một hệ quả logic của tập tiên đề Zi (nghĩa là, α có thể suy ra được từ tập hợp các tiên đề Zi). Tương tự như vậy, bổ sung ¬α vào tập tiên đề Zi nếu ¬α là hệ quả logic của tập tiên đề Zi. Việc bổ sung tiên đề α hoặc ¬α vào tập Zi là để đảm bảo tính được tần suất xuất hiện thực sự của các tiên đề còn tiềm ẩn trong ontology. Điều này là quan trọng vì thuật toán xác định đồng thuận (Thuật toán 4.1) có xét đến tần suất xuất hiện của các literal trong các công thức hội thuộc hồ sơ xung đột. Chẳng hạn, nếu β ∧ γ ⇒ α thì chúng ta có thể xem tập tiên đề {β, γ} là có chứa tiên đề α. • Thành lập hồ sơ xung đột X ∈ Conj(Z) từ n tập tiên đề của các ontology O1,O2, . . . ,On: X = {Z1,Z2, . . . ,Zn}. • Sử dụng Thuật toán 4.1 để xây dựng đồng thuận x∗ của hồ sơ X. Nếu x∗ là nhất quán thì kết luận x∗ là tập tiên đề tốt nhất, ngược lại, tìm Zi (i = 1, 2, . . . , n) sao cho tập tiên đề này có khoảng cách nhỏ nhất đến x∗ và kết luận đó là tập tiên đề tốt nhất. 116 Nội dung của thuật toán được trình bày cụ thể như sau: Thuật toán 4.2: Xác định tập tiên đề đồng thuận của các ontology Đầu vào: Ontology O1,O2, . . . ,On với các tập tiên đề Z1,Z2, . . . ,Zn (n ∈ N∗) Đầu ra: Tập tiên đề x∗ đại diện tốt nhất cho tập tiên đề của các ontology O1,O2, . . . ,On begin Bước 1 Z := ∅; foreach Oi ∈ {O1,O2, . . . ,On} do foreach α ∈ Zi do needAdd := true; foreach z ∈ Z do if (z ≡ α) or (¬z ≡ α) then needAdd := false; break; if (needAdd = true) then Z := Z ∪ {α}; Bước 2 foreach Oi ∈ {O1,O2, . . . ,On} do foreach z ∈ Z \ Zi do if (Zi |= z) then Zi := Zi ∪ {z}; if (Zi |= ¬z) then Zi := Zi ∪ {¬z}; Bước 3 Lập hồ sơ xung đột X := {x1, x2, . . . , xn} với xi ∈ Conj(Z) biểu diễn trạng thái tri thức tương ứng tập tiên đề Zi của ontology Oi; Bước 4 Xác định x∗ là đồng thuận của hồ sơ xung đột X theo Thuật toán 4.1; Bước 5 if (x∗ là nhất quán) then Z∗ := x∗; else Z∗ := Z1; foreach Z′ ∈ {Z2,Z3, . . . ,Zn} do if ( η(x∗,Z′) < η(x∗,Z∗) ) then Z∗ := Z′; 117 Chúng ta phân tích độ phức tạp của Thuật toán 4.2. Gọi: • m = card(Z) là số lượng literal dùng để biểu diễn các tiên đề trong các ontology đầu vào; • O(f(m)) là độ phức tạp của thuật toán lập luận với ontology có chứa m tiên đề. Độ phức tạp của các bước trong thuật toán được xác định như sau: • Bước 1 dùng để xác định tập hợp Z, là tập cực tiểu các literal mà có thể dùng để biểu diễn mọi tiên đề trong các ontology Oi(i = 1, 2, . . . , n). Độ phức tạp của bước này là O(n.m2). • Trong Bước 2, với mỗi ontology Oi, chúng ta xem xét bổ sung các tiên đề z ∈ Z nếu z là một hệ quả logic của tập tiên đề Zi (kiểm tra xem z có thể suy ra được từ tập hợp các tiên đề Zi hay không). Độ phức tạp của bước này là O ( n.m.f(m) ) . • Bước 3 lập hồ sơ xung đột X có độ phức tạp O(n). • Bước 4 xác định đồng thuận của hồ sơ các công thức hội X với n công thức hội sử dụng m literal bằng cách sử dụng Thuật toán 4.1. Độ phức tạp của bước này sẽ là O ( max{n.m3, n2.m2}). • Bước 5 của thuật toán kiểm tra sự nhất quán của x∗ tìm được. Nếu x∗ là không nhất quán, thuật toán sẽ phải duyệt qua n tập tiên đề để tìm ra tập tiên đề có tổng khoảng cách đến các tập tiên đề còn lại đạt cực tiểu. − Độ phức tạp của thủ tục kiểm tra sự nhất quán của tập tiên đề tương ứng với x∗ là O(f(m)). − Độ phức tạp của thủ tục tìm tập tiên đề có khoảng cách cực tiểu đến các tập tiên đề còn lại là O(n.m2) Do đó, độ phức tạp của Bước 5 là O(max{f(m), n.m2}). Các bước nêu trên của thuật toán được thực hiện tuần tự. Do đó độ phức tạp của thuật toán sẽ là: O ( max { n.m2, n.m.f(m), n, n.m3, n2.m2, f(m), n.m2 }) = O ( max { n.m.f(m), n.m3, n2.m2 }) 118 Độ phức tạp của thuật toán lập luận ontology có m tiên đề (chẳng hạn như HermiT [55], Pellet [56]) là lớn hơn so với O(m2). Do đó độ phức tạp của thuật toán có thể viết lại thành O ( max{n.m.f(m), n2.m2}): Nếu f(m) < n.m thì độ phức tạp của thuật toán là O(n2.m2), ngược lại thuật toán sẽ có độ phức tạp là O(n.m.f(m)). 4.3. Tiểu kết Chương 4 Trong chương này, luận án đã trình bày mô hình xác định đồng thuận của tri thức biểu diễn dưới dạng hội của các literal . Sau khi định nghĩa khoảng cách giữa hai tập hợp (là tập con của tập ký hiệu L cho trước), luận án đã phân tích tính chất và chứng minh một số định lý thể hiện mối quan hệ giữa các tiêu chuẩn xác định đồng thuận của hồ sơ công thức hội. Trên cơ sở đó luận án đề xuất thuật toán xác định đồng thuận của hồ sơ công thức hội. Từ mô hình xác định đồng thuận của tri thức biểu diễn dưới dạng hội của các literal , luận án đã đề xuất một phương pháp xử lý xung đột cấp độ cú pháp trong quá trình tích hợp ontology. Phương pháp này có thể được áp dụng để hỗ trợ xác định phiên bản tốt nhất từ những đóng góp của các tác tử phân tán trong quá trình xây dựng ontology dạng cộng tác [61]. Kết quả của chương này đã được trình bày ở Hội thảo Artificial Intelligence in Theory and Practice IV (2015) [CT4] và đăng ở tạp chí Khoa học Đại học Huế (2015) [CT3]. 119 KẾT LUẬN Kết luận Ontology là thành phần quan trọng trong nền tảng ứng dụng web ngữ nghĩa. Đặc trưng có thể mở rộng, có thể tái sử dụng của ontology một mặt giúp các hệ thống có thể trao đổi và chia sẻ tri thức, nhưng mặt khác cũng tiềm ẩn khả năng làm xuất hiện tri thức không nhất quán. Xử lý tri thức không nhất quán nói chung và xử lý tri thức không nhất quán trong ontology nói riêng là bài toán phức tạp của khoa học máy tính. Hai tình huống điển hình về xử lý tri thức không nhất quán trong ontology là: (1) xác định kết quả có nghĩa khi truy vấn với ontology không nhất quán, và (2) tích hợp các ontology không nhất quán đến từ nhiều nguồn độc lập nhau. Luận án đã đề xuất các phương án giải quyết cho hai tình huống nêu trên. Các kết quả chính của luận án có thể được tóm tắt như sau: 1) Xây dựng hàm chọn sOSem dựa trên khoảng cách ngữ nghĩa theo ontology tham chiếu và áp dụng hàm chọn này vào khung lập luận với ontology không nhất quán. Kết quả thực nghiệm đã chỉ ra rằng việc áp dụng hàm chọn sOSem vào khung lập luận với ontology không nhất quán sẽ giúp trả về nhiều kết quả xác định hơn so với các hàm chọn đã được công bố trước đó. Trong quá trình xây dựng hàm chọn, Luận án đã trình bày phương pháp quy hoạch động để tính khoảng cách ngữ nghĩa theo ontology tham chiếu giữa hai biểu thức khái niệm, đồng thời phân loại và trình bày cách xác định tập biểu thức khái niệm trong các tiên đề của ontology OWL2 – ngôn ngữ ontology thông dụng nhất hiện nay và được chuẩn hoá bởi tổ chức W3C [CT6]. 2) Xây dựng phương pháp đồng thuận để xử lý xung đột mức khái niệm trong quá trình tích hợp ontology. Cấu trúc khái niệm đồng thuận được xác định với danh sách thuộc tính và miền giá trị của các thuộc tính tương ứng. Luận án đã đề xuất thuật toán và chứng minh tính thoả các tiêu chuẩn của đồng thuận được xây dựng bởi thuật toán. Luận án cũng trình bày 120 phương pháp xây dựng hàm đánh giá khoảng cách cho các miền giá trị của thuộc tính kiểu dữ liệu và thuộc tính đối tượng trong ontology OWL2 [CT1, CT2, CT5]. 3) Xây dựng phương pháp đồng thuận để xử lý xung đột cấp độ cú pháp trong quá trình tích hợp tri thức. Luận án đề xuất sử dụng một phương pháp tính khoảng cách giữa hai tập ký hiệu, khoảng cách giữa hai cấu trúc hội của các literal và chứng minh được một số mối quan hệ của các tiêu chuẩn đồng thuận dựa theo các khoảng cách này. Trên cơ sở đó, luận án đề xuất thuật toán xác định đồng thuận của hồ sơ xung đột gồm các cấu trúc hội. Bằng cách áp dụng thuật toán tìm đồng thuận của hồ sơ xung đột gồm các cấu trúc hội của các literal , luận án đề xuất phương án để xử lý xung đột mức tiên đề trong quá trình tích hợp ontology [CT3, CT4]. Những vấn đề cần tiếp tục nghiên cứu Kết quả của luận án có thể được mở rộng theo những hướng sau đây: • Nghiên cứu thêm về các dạng truy vấn khác với ontology không nhất quán, đặc biệt là truy vấn SPARQL với ontology OWL không nhất quán. • Xét thêm mối quan hệ của các literal trong quá trình xử lý xung đột cấp độ cú pháp. • Đề xuất khung xử lý xung đột tri thức trong ontology. Khung xử lý như vậy áp dụng các chiến lược khác nhau cho từng tác vụ khác nhau với ontology: tích hợp, truy vấn, tiến hoá ontology. 121 DANH MỤC CÁC CÔNG TRÌNH CỦA TÁC GIẢ LIÊN QUAN ĐẾN LUẬN ÁN CT1. Nguyễn Văn Trung, Phan Bá Trí, Hoàng Hữu Hạnh. Tích hợp ontology với tiếp cận lý thuyết đồng thuận. Tạp chí Tin học và Điều khiển học T.30, S.3 (2014), 239-252. CT2. Trung Van Nguyen, Hanh Huu Hoang. A Consensus-based Method for Solving Concept- level Conflict in Ontology Integration, In Proceeding of 6th International Conference on Computational Collective Intelligence Technologies and Applications, Seoul, Korea, 2014, LNCS 8733, Springer (2014). p414-423. CT3. Nguyễn Văn Trung, Hoàng Hữu Hạnh. Một phương pháp xử lý không nhất quán tri thức ở mức cú pháp. Tạp chí Khoa học Đại học Huế, T.106, S.7 (2015), 241-251. CT4. Trung Van Nguyen, Jason J. Jung, Hanh Huu Hoang. A Novel Approach for Resolving Knowledge Inconsistency on Ontology Syntactic Level. In Proceeding of Artificial Intel- ligence in Theory and Practice IV (IFIP Advances in Information and Communication Technology), Springer (2015) p39-49. CT5. Trung Van Nguyen, Hanh Huu Hoang. A Consensus-Based Method for Solving Concept- Level Conflict in Ontology Integration. Transactions of Computational Collective In- telligence XXII, LNCS 9655, Springer (2016) p106-124. CT6. Nguyễn Văn Trung, Hoàng Hữu Hạnh. Một phương pháp truy vấn ontology không nhất quán sử dụng độ liên quan ngữ nghĩa. Tạp chí Khoa học và Công nghệ Trường Đại học Khoa học, Đại học Huế, T.9. S.1 (2017), 51-62. 122