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

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

1. ĐẠI HỌC HUẾ TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN VĂN TRUNG MỘT SỐ PHƯƠNG PHÁP XỬ LÝ TRI THỨC KHÔNG NHẤT QUÁN TRONG ONTOLOGY LUẬN ÁN TIẾN SĨ KHOA HỌC MÁY TÍNH HUẾ - NĂM 2018
2. ĐẠI HỌC HUẾ TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN VĂN TRUNG MỘT SỐ PHƯƠNG PHÁP XỬ LÝ TRI THỨC KHÔNG NHẤT QUÁN TRONG ONTOLOGY CHUYÊN NGÀNH: KHOA HỌC MÁY TÍNH MÃ SỐ: 62.48.01.01 LUẬN ÁN TIẾN SĨ KHOA HỌC MÁY TÍNH Người hướng dẫn khoa học: PGS. TS. HOÀNG HỮU HẠNH HUẾ - NĂM 2018
3. LỜI CAM ĐOAN Tôi xin cam đoan đây là công trì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
4. 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
5. MỤC LỤC Lời cam đoani 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ở đầu1 Chương 1. TỔNG QUAN VỀ XỬ LÝ TRI THỨC KHÔNG NHẤT QUÁN TRONG ONTOLOGY9 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ÔNG NHẤ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
6. 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 ĐỘT MỨC TIÊN ĐỀ TRONG QUÁ 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 DANH MỤ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
7. 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
8. DANH MỤC KÝ HIỆU Ký hiệu Diễn giải ý nghĩa O Ontology Σ Ontology không nhất quán Σ0, Σ00 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
9. 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
10. 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 −T REE . . . . . . . . . . . . 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
11. 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à OWL 2 (đượ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ỉ 1
12. 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
13. đề 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
14. 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
15. 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
16. 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
17. 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
18. 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
19. 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 hC, I, R, Zi, 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
20. Ở Đị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 Σ = hC, I, R, Zi 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
21. Ý 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à OWL 2 được dựa trên logic mô tả SROIQ(D). Ngữ nghĩa của OWL 2 đượ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 = h∆I, ·Ii gồm một miền diễn dịch khác rỗng 11
22. ∆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 OWL 2 được nêu ở 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 ontology O được viết là “O |= α?” có kết quả “Đúng” nếu α là hệ quả logic của tập tiên đề trong O, viết là O |= α. Khi đó ta cũng nói, α được suy dẫn từ O. Ngược lại, nếu α không phải là hệ quả logic của tập tiên đề trong O, kết quả của truy vấn là “Sai” và ta viết O 6|= α. Theo Giả thiết Thế giới Mở, O 6|= α không đồng nghĩa với O |= ¬α. Chẳng hạn, ở Ví dụ 1.1 ta có: Σ |= Cat v Animal và Σ 6|= AnimalLover(MARY). Điều đặc biệt, khi ontology là không nhất quán, thì mọi tiên đề đều là hệ quả logic của ontology đó [26]. Như vậy, việc truy vấn một ontology không nhất quán là không có nghĩa. Ví dụ 1.2 dưới đây mô tả một ontology không nhất quán và các kết quả truy vấn với ontology này. Ví dụ 1.2 (Ontology không nhất quán và các kết quả truy vấn với ontology không nhất quán). Gọi Σ0 = hC, I, R, Z0i là ontology với C, I, R, Z được định nghĩa như ở Ví dụ 1.1 và Z0 = Z ∪ {Person(TOM)} . Có thể thấy rằng, tập con sau đây gồm các tiên đề của Z0 dưới đây là có chứa mâu thuẫn: { Cat v Pet, Pet u Person v ⊥, Person(TOM), Cat(TOM) } Do vậy, Σ0 là không có mô hình nào, hay Σ0 là ontology không nhất quán. Hình 1.1 mô tả các kết quả truy vấn với ontology không nhất quán Σ0. Kết quả 12
23. cho thấy kết quả các truy vấn này đều là “Đúng”, hay các tiên đề đều là hệ quả logic của ontology không nhất quán Σ0. Hình 1.1: Truy vấn với ontology không nhất quán 13
24.  Người ta phân các phương pháp xử lý tri thức không nhất quán trong ontology làm hai nhóm: (1) chấp nhận tồn tại tri thức không nhất quán trong ontology, và (2) tìm cách loại bỏ tri thức không nhất quán để xây dựng ontology mới, nhất quán. (1) Các phương 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]. 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 thực tế, có nhiều trường hợp người dùng 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 khi được tổng hợp lại) mà không được phép chỉnh sửa hay tạo mới ontology. Để giải quyết vấn đề này, nhóm tác giả Zhisheng Huang, Frank van Harmelen và cộng sự [21] đã đề xuất 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. 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: tập tiên đề này có liên quan với truy vấn theo một tiêu chí xác định trước và có thể trả lời được truy vấn (gọi là tập tiên đề diễn giải truv vấn). Mục 1.2 của chương sẽ trình bày các khái niệm cơ bản và đánh giá một số tiếp cận ứng dụng khung lập luận này. (2) Các phương pháp thuộc nhóm thứ hai tìm cách loại bỏ sự không nhất quán để xây dựng ontology nhất quán 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 và loại bỏ một số tiên đề khỏi ontology theo một tiêu chí cụ thể [25, 29, 51, 54], và chiến lược thứ hai, áp dụng lý thuyết đồng thuận [2] để xây dựng tập tiên đề hợp lý nhất (theo một tiêu chí cụ thể nào đó) 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 14
25. ontology, trong khi đó, chiến lược thứ hai thường được sử dụng để xử lý tri thức không nhất quán xuất hiện do có 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. Mục 1.3 của chương sẽ trình bày các khái niệm cơ bản về biểu diễn và xử lý xung đột tri thức bằng phương pháp đồng thuận. Trên cơ sở này luận án sẽ xây dựng các giải pháp để xử lý tri thức không nhất quán trong quá trình tích hợp ontology. 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 1.2.1. Các khái niệm cơ bản Khung lập luận với ontology không nhất quán được đề xuất bởi Zhisheng Huang, Frank van Harmelen và cộng sự [21]. Khung lập luận này xem một ontology như là một tập hợp các tiên đề và không giới hạn cho loại ngôn ngữ ontology cụ thể nào. Theo đó, gọi L là một ngôn ngữ ontology, chúng ta ký hiệu 2L là tập gồm tất cả các tập tiên đề trên ngôn ngữ L. Ontology Σ có thể xem là một tập tiên đề trên ngôn ngữ L: Σ ∈ 2L. Để phân biệt với phép suy luận chuẩn |=, chúng ta sử dụng |≈ để ký hiệu cho phép suy luận không chuẩn, phép suy luận này có thể được tham số hoá để có thể chấp nhận sự không nhất quán. Với một ontology nhất quán Σ, phép suy luận chuẩn luôn luôn đảm bảo tính đúng, theo nghĩa, nếu một tiên đề được cho là được suy dẫn từ Σ thì điều này sẽ đúng cho mọi mô hình của Σ [26]. Tính đúng như vậy là không thích hợp với một ontology không nhất quán, bởi vì nếu ontology Σ là không nhất quán thì mọi tiên đề đều là hệ quả logic của nó. Trong nhiều tình huống thực tế, sự không nhất quán của một ontology có thể bắt nguồn từ lỗi của một phần nhỏ của nó (một hoặc một số ít tiên đề của ontology bị xây dựng sai), trong khi phần còn lại của ontology thì không có lỗi. Chính vì thế, người ta định nghĩa tính đúng trong một phép suy luận không chuẩn để có thể sử dụng với ontology không nhất quán như sau. Định nghĩa 1.2 (Tính đúng [21]). Một phép suy luận không chuẩn |≈ được gọi là đúng nếu các tiên đề được suy dẫn từ một ontology không nhất quán Σ theo |≈ thì cũng được suy dẫn từ một tập con gồm các tiên đề nhất quán của Σ (gọi là ontology con nhất quán của Σ) bằng phép suy luận chuẩn |=, tức là điều kiện 15
26. sau đây phải được thoả: ∀φ ∈ L :Σ |≈ φ ⇒ (∃Σ0 ⊂ Σ) : (Σ0 6|= > v ⊥) ∧ (Σ0 |= φ)
    (1.1)  Khi Σ |≈ φ, ta nói φ là một hệ quả-|≈ của Σ, hay φ có quan hệ hệ quả |≈ với Σ. Theo định nghĩa về tính đúng ở trên, kết luận Σ |≈ φ được dựa trên một tập con gồm các tiên đề nhất quán Σ0 của Σ. Chúng ta gọi tập tiên đề Σ0 như thế là một tập tiên đề diễn giải cho câu trả lời Σ |≈ φ và ngược lại, câu trả lời Σ |≈ φ được gọi là được diễn giải bởi Σ0 theo phép suy luận |≈. Có thể thấy, câu trả lời Σ |≈ φ có thể có nhiều hơn một tập tiên đề diễn giải. Định nghĩa 1.2 không đề cập đến tính đúng theo chiều ngược lại của mệnh đề. Nghĩa là, nếu có một tập con gồm các tiên đề nhất quán Σ0 ⊂ Σ thoả điều kiện Σ0 |= φ thì chúng ta chưa thể kết luận được rằng Σ |≈ φ. Điều này là nhằm bảo đảm tính chất gọi là tính có nghĩa của phép suy luận không chuẩn |≈. Tính chất này được định nghĩa như sau: Định nghĩa 1.3 (Tính có nghĩa [21]). Một kết quả của phép suy luận không chuẩn được gọi là có nghĩa nếu nó đúng và nhất quán, tức là, nó không chỉ đòi hỏi điều kiện về tính đúng mà còn đòi hỏi thoả mãn thêm điều kiện sau đây: Σ |≈ φ ⇒ Σ 6|≈ ¬φ. (1.2) Phép suy luận |≈ được gọi là có nghĩa nếu mọi kết quả của nó đều là có nghĩa.  Ví dụ đơn giản sau đây minh hoạ một phép suy luận không chuẩn. Ví dụ 1.3 (Một phép suy luận không chuẩn). Cho Σ = {a, ¬a}. Một phép suy luận không chuẩn |≈1 được định nghĩa sao cho: • Σ |≈1 a với tập tiên đề diễn giải là {a}, và • Σ |≈1 ¬a với tập tiên đề diễn giải {¬a}. Chú ý rằng, ở đây chúng ta không đề cập đến việc làm thế nào để chọn ra các tập tiên đề diễn giải. Ngoài ra, theo Định nghĩa 1.3, phép suy luận |≈1 không phải là một phép suy luận có nghĩa.  16
27. Tiếp theo, chúng ta định nghĩa hình thức cho việc truy vấn một ontology không nhất quán sử dụng phép suy luận không chuẩn. Định nghĩa 1.4 (Truy vấn ontology không nhất quán sử dụng phép suy luận không chuẩn). Cho Σ là một ontology không nhất quán. Một truy vấn φ với Σ sử dụng phép suy luận không chuẩn |≈ là phép đánh giá các quan hệ hệ quả “Σ |≈ φ?” và “Σ |≈ ¬φ?”. Có thể có bốn câu trả lời cho truy vấn này: “Quá xác định”, “Chấp nhận”, “Bác bỏ” và “Không xác định” tương ứng với bốn trường hợp sau đây. (a) Quá xác định: Σ |≈ φ và Σ |≈ ¬φ. (b) Chấp nhận: Σ |≈ φ và Σ 6|≈ ¬φ. (c) Bác bỏ: Σ 6|≈ φ và Σ |≈ ¬φ. (d) Không xác định: Σ 6|≈ φ và Σ 6|≈ ¬φ.  Định nghĩa 1.3 và Định nghĩa 1.4 cho thấy, nếu |≈ là phép suy luận có nghĩa, nó sẽ bảo đảm kết quả của các truy vấn “Σ |≈ φ?” và “Σ |≈ ¬φ?” là nhất quán với nhau. Như vậy, việc lựa chọn tập tiên đề diễn giải trong phép suy luận không chuẩn đóng vai trò cực kỳ quan trọng khi truy vấn với ontology không nhất quán. Bên cạnh tính đúng và tính có nghĩa, chúng ta định nghĩa thêm tính đầy đủ cục bộ, tính đúng cục bộ và tính cực đại cho phép suy luận không chuẩn |≈ như sau: Định nghĩa 1.5 (Tính đầy đủ cục bộ [21]). Cho Σ là một ontology không nhất quán, Σ0 ⊂ Σ là một ontology con nhất quán của Σ. Với φ là một tiên đề, kết quả suy luận Σ |≈ φ được gọi là đầy đủ cục bộ theo Σ0 nếu: Σ0 |= φ ⇒ Σ |≈ φ (1.3) Phép suy luận |≈ với ontology không nhất quán Σ được gọi là đầy đủ cục bộ theo Σ0 nếu với mọi tiên đề φ, kết quả suy luận Σ |≈ φ là đầy đủ cục bộ theo 0 Σ .  17
28. Do điều kiện (1.3) có thể được biểu diễn dưới dạng Σ 6|≈ φ ⇒ Σ0 6|= φ, nên tính đầy đủ cục bộ có thể được xem là tính chất bù của tính đúng. Định nghĩa 1.6 (Tính đúng cục bộ [21]). Cho Σ là một ontology không nhất quán, Σ0 ⊂ Σ là một ontology con nhất quán của Σ. Với φ là một tiên đề, kết quả suy luận Σ |≈ φ được gọi là đúng cục bộ theo Σ0 nếu: Σ |≈ φ ⇒ Σ0 |= φ. (1.4) Phép suy luận |≈ với ontology không nhất quán Σ được gọi là đúng cục bộ theo Σ0 nếu với mọi tiên đề φ, kết quả suy luận Σ |≈ φ là đúng cục bộ theo Σ0.  Định nghĩa 1.7 (Tính cực đại [21]). Cho Σ là một ontology không nhất quán, Σ0 ⊂ Σ là một ontology con nhất quán của Σ. Phép suy luận |≈ với ontology không nhất quán Σ được gọi là cực đại theo Σ0 nếu: (Σ0 6|= > v ⊥)∧(∀Σ00 ⊂ Σ:Σ00 ⊃ Σ0 ⇒ Σ00 |= > v ⊥)∧(∀φ :Σ0 |= φ ⇔ Σ |≈ φ) (1.5) Khi phép suy luận |≈ với ontology không nhất quán Σ là cực đại theo Σ0, ta cũng 0 nói Σ là tập tiên đề diễn giải cực đại của Σ theo |≈.  Các tính chất có thể suy ra trực tiếp từ các định nghĩa về tính đúng, tính có nghĩa, tính đúng cục bộ, tính đầy đủ cục bộ và tính cực đại được thể hiện ở mệnh đề sau: Mệnh đề 1.1 ([21]). Cho Σ là một ontology không nhất quán, Σ0 ⊂ Σ là ontology con nhất quán của Σ, |≈ là một phép suy luận không chuẩn, φ là một tiên đề bất kỳ. Khi đó: (a) Tính đúng cục bộ kéo theo tính đúng và tính có nghĩa: (Σ |≈ φ là đúng cục bộ theo Σ0) ⇒ (Σ |≈ φ là đúng) ∧ (Σ |≈ φ là có nghĩa). (b) Tính cực đại kéo theo tính đầy đủ cục bộ: Nếu phép suy luận không chuẩn |≈ với ontology không nhất quán Σ là cực đại theo Σ0 thì nó cũng là đầy đủ cục bộ theo Σ0. 18
29. Với một ontology không nhất quán Σ và một phép suy luận không chuẩn |≈, có thể tồn tại nhiều hơn một tập tiên đề diễn giải cực đại của Σ theo |≈. Các tập tiên đề diễn giải cực đại này có thể dẫn đến các kết quả khác nhau (dựa trên hệ quả -|≈) với một truy vấn φ cho trước. Ví dụ 1.4. Xét ontology không nhất quán Σ = {a, ¬a} và phép suy luận không chuẩn |≈1 được định nghĩa như ở Ví dụ 1.3. Có thể thấy rằng có hai tập tiên đề diễn giải cực đại của Σ theo |≈1 là Σ1 = {a} và Σ2 = {¬a}. Hệ quả-|≈1 dựa trên hai tập tiên đề diễn giải Σ1 và Σ2 là khác nhau. Điều này dẫn đến: • “Chấp nhận” truy vấn “Σ |≈1 a?” (với tập tiên đề diễn giải Σ1). • “Bác bỏ” truy vấn “Σ |≈1 a?” (với tập tiên đề diễn giải Σ2).  Các định nghĩa và ví dụ nêu trên cho thấy, tập tiên đề diễn giải và tập tiên đề diễn giải cực đại là đặc trưng của phép suy luận không chuẩn. Phần tiếp theo của chương sẽ trình bày khung xây dựng tập tiên đề diễn giải dựa trên hàm chọn (selection function). 1.2.2. Hàm chọn Cho L là một ngôn ngữ ontology, Σ ∈ 2L là một ontology, φ ∈ L là một tiên đề trên L. Hàm chọn s trả về một tập con của Σ ở bước k > 0 (k ∈ N) trong quá trình đánh giá truy vấn “Σ |≈ φ?” được định nghĩa tổng quát như sau: Định nghĩa 1.8 (Hàm chọn [21]). Hàm chọn s là ánh xạ s: 2L × L × N → 2L L sao cho s(Σ, φ, k) ⊆ Σ với ∀Σ ∈ 2 , φ ∈ L, k ∈ N.  Định nghĩa 1.9 (Hàm chọn đơn điệu [21]). Một hàm chọn s được gọi là đơn điệu nếu các tập con mà nó chọn được là tăng hoặc giảm một cách đơn điệu theo bước lặp. Tức là, với ∀Σ ∈ 2L, φ ∈ L, k ∈ N: s(Σ, φ, k) ⊆ s(Σ, φ, k + 1) (s là đơn điệu tăng theo k) (1.6) hoặc s(Σ, φ, k) ⊇ s(Σ, φ, k + 1) (s là đơn điệu giảm theo k). (1.7) 19
30.  Hàm chọn đơn điệu sẽ là công cụ để xác định tập tiên đề diễn giải trong phép suy luận không chuẩn. Phần tiếp theo sẽ mô tả chiến lược xây dựng tập tiên đề diễn giải theo hàm chọn đơn điệu. 1.2.3. Phép suy luận không chuẩn sử dụng hàm chọn đơn điệu Một phép suy luận không chuẩn sử dụng hàm chọn đơn điệu tăng (tương ứng, đơn điệu giảm) để xây dựng tập tiên đề diễn giải được gọi là phép suy luận sử dụng chiến lược mở rộng tuyến tính (tương ứng, rút gọn tuyến tính) tập tiên đề diễn giải. Chiến lược mở rộng tuyến tính trong phép suy luận không chuẩn được mô tả như ở Hình 1.2: Với Σ là một ontology không nhất quán, s là một hàm chọn đơn điệu tăng, φ là tiên đề cần truy vấn, tập con gồm các tiên đề nhất quán ban đầu được gán là Σ0 (Σ0 ⊂ Σ). Hàm chọn s được gọi để trả về một tập con gồm các tiên đề nhất quán Σ00. Σ00 là mở rộng của Σ0, tức là: Σ0 ⊂ Σ00 ⊂ Σ. Nếu hàm chọn không tìm được một tập tiên đề Σ00 như vậy, quá trình lập luận sẽ trả về câu trả lời là “không xác định” cho truy vấn (theo nghĩa không thể xác định được tính đúng sai của φ dựa vào tập tiên đề Σ). Nếu tồn tại Σ00, chúng ta sẽ kiểm tra Σ00 |= φ? Nếu câu trả lời là “Đúng”, quá trình lập luận sẽ kết luận “Chấp nhận” cho truy vấn “Σ |≈ φ?”. Nếu câu trả lời là “Sai”, quá trình lập luận sẽ tiếp tục bằng việc kiểm tra xem phủ định của truy vấn “Σ00 |= ¬φ?” có được thoả hay không. Nếu câu trả lời là “Đúng”, quá trình lập luận sẽ kết luận “Bác bỏ” cho truy vấn “Σ |≈ φ?”, ngược lại, quá trình lập luận được tiếp tục tập chọn được mở rộng Σ0 := Σ00. Chiến lược mở rộng tuyến tính được áp dụng đối với hàm chọn đơn điệu tăng, xuất phát từ tập rỗng, tức là, s(Σ, φ, 0) = ∅, hoặc một tập tiên đề nhất quán cố định Σ0 (Σ0 ⊂ Σ và Σ0 6|= > v ⊥). Trong khi đó, chiến lược rút gọn tuyến tính được áp dụng với hàm chọn đơn điệu giảm, với xuất phát điểm chính là Σ, nghĩa là, s(Σ, φ, 0) = Σ. Hàm chọn đơn điệu giảm sẽ rút gọn một số tiên đề từ tập không nhất quán theo từng bước cho đến khi chọn được tập nhất quán lớn nhất. Luận án này chỉ xét chiến lược mở rộng tuyến tính để xây dựng phép suy luận không chuẩn. Đối với chiến lược mở rộng tuyến tính, Zhisheng Huang và cộng sự [21] đã 20
31. Hình 1.2: Chiến lược mở rộng tuyến tính [21] chứng minh được các tính chất sau đây: Mệnh đề 1.2 (Tính chất của chiến lược mở rộng tuyến tính [21]). Một phép suy luận sử dụng chiến lược mở rộng tuyến tính sẽ thoả các tính chất sau đây: (a) không bao giờ quá xác định, (b) có thể không xác định, (c) luôn luôn đúng, (d) luôn luôn có nghĩa, (e) luôn luôn đầy đủ cục bộ, 21
32. (f) có thể không cực đại, (g) luôn luôn đúng cục bộ. Như vậy, một phép suy luận không chuẩn sử dụng chiến lược mở rộng tuyến tính để tìm tập tiên đề diễn giải sẽ trả về các câu trả lời đúng và có nghĩa cho các truy vấn. Nó luôn luôn đúng cục bộ và đầy đủ cục bộ theo một tập tiên đề nhất quán Σ0 nếu hàm chọn luôn luôn bắt đầu bằng một tập khởi đầu nhất quán Σ0 = s(Σ, φ, 0). Tính cực đại là không cần thiết trong trường hợp chúng ta chỉ muốn tìm câu trả lời đúng và có nghĩa của truy vấn, tuy nhiên nó là cần thiết trong một số trường hợp – chẳng hạn khi chúng ta cần tìm ra tập tiên đề lớn nhất và nhất quán (của ontology không nhất quán đầu vào) để tiến hoá ontology [16]. Chiến lược mở rộng tuyến tính có thể dẫn đến nhiều câu trả lời “không xác định” cho các truy vấn khi hàm chọn chọn sai chuỗi tập con tăng đơn điệu. Điều này hiển nhiên phụ thuộc vào hàm chọn được sử dụng. Nói cách khác, số lượng câu trả lời “không xác định” là một tiêu chí quan trọng để đánh giá tính chất của hàm chọn trong phép suy luận không chuẩn. Chiến lược mở rộng tập tiên đề được gọi là “tuyến tính” bởi vì hàm chọn chỉ phát triển theo một “chuỗi mở rộng”. Lợi ích của chiến lược tuyến tính là quá trình lập luận chỉ tập trung vào tập tiên đề đang xét Σ0 ở bước hiện tại chứ không quan tâm đến việc mở rộng chuỗi sau đó. Nhược điểm của chiến lược tuyến tính đó là, nó có thể khiến cho phép suy luận là không xác định. Một số cách tiếp cận để khắc phục vấn đề này đó là (1) truy ngược khi gặp câu trả lời “không xác định” và (2) ước lượng heuristic để tìm hướng mở rộng tập tiên đề diễn giải. Độ phức tạp tính toán của chiến lược mở rộng tập tiên đề trong phép suy luận không chuẩn là tuyến tính so với độ phức tạp của bài toán suy luận ontology. Nói cách khác, chiến lược mở rộng tuyến tính không làm tăng nhiều độ phức tạp của phép suy luận ontology. Mệnh đề 1.3 (Độ phức tạp của phép mở rộng tuyến tính [21]). Gọi n ∈ N là số tiên đề của ontology Σ và gọi độ phức tạp tính toán của phép suy luận |= là E. Độ phức tạp của phép suy luận |≈ trong chiến lược mở rộng tuyến tính là n.E. 22
33. Như là một ví dụ cụ thể về một hàm chọn và cách áp dụng chiến lược mở rộng tuyến tính trong khung lập luận với ontology không nhất quán, phần tiếp theo sẽ trình bày hàm chọn dựa trên sự liên quan về cú pháp [21]. 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 Hàm chọn dựa trên sự liên quan cú pháp sSyn Samir Chopra và các cộng sự [7] đã đề xuất khái niệm liên quan về cú pháp để đánh giá mối liên hệ giữa hai công thức trong logic mệnh đề. Zhisheng Huang và cộng sự [21] mở rộng ý tưởng liên quan về cú pháp để áp dụng cho các ontology bằng cách xét đến sự xuất hiện của các tên thực thể trong các tiên đề. Định nghĩa sau đây nói về sự liên quan về cú pháp của hai tiên đề trong ontology. Với một tiên đề φ, chúng ta sử dụng I(φ), C(φ), R(φ) để tương ứng ký hiệu cho tập tên cá thể, tập tên khái niệm và tập tên quan hệ xuất hiện trong tiên đề này. Định nghĩa 1.10 (Liên quan trực tiếp [21]). Hai tiên đề φ, ψ được gọi là liên quan trực tiếp với nhau nếu có ít nhất một tên thực thể xuất hiện trong cả φ và ψ, tức là: I(φ) ∩ I(ψ) 6= ∅
    ∨ C(φ) ∩ C(ψ) 6= ∅
    ∨ R(φ) ∩ R(ψ) 6= ∅
    . (1.8)  Định nghĩa 1.11 (Liên quan trực tiếp với một tập hợp [21]). Một tiên đề φ được gọi là liên quan trực tiếp với một tập tiên đề Σ nếu tồn tại một tiên đề ψ ∈ Σ sao cho φ và ψ là liên quan trực tiếp với nhau.  Định nghĩa 1.12 (Hàm chọn dựa trên sự liên quan cú pháp [21]). Cho L là một ngôn ngữ ontology, Σ ∈ 2L là một ontology không nhất quán, φ ∈ L là một tiên đề trên L. Hàm chọn dựa trên sự liên quan cú pháp sSyn được định nghĩa như sau: L L sSyn : 2 × L × N → 2 (Σ, φ, k) 7→ sSyn(Σ, φ, k) 23
34. với:  ∅ nếu k = 0  sSyn(Σ, φ, k) = {ψ ∈ Σ | ψ có liên quan trực tiếp với φ} nếu k = 1   {ψ ∈ Σ | ψ có liên quan trực tiếp với sSyn(Σ, φ, k − 1)} nếu k > 1  Phép suy luận không chuẩn sử dụng hàm chọn sSyn Hàm chọn sSyn là đơn điệu tăng [21]. Phép suy luận sử dụng hàm chọn sSyn để mở rộng tập tiên đề diễn giải theo chiến lược mô tả ở Tiểu mục 1.2.3 được ký hiệu là |≈Syn. Đặc điểm của sSyn khiến cho tập tiên đề diễn giải thường phát triển đến tập hợp gồm các tiên đề không nhất quán một cách nhanh chóng. Điều này có thể dẫn đến các câu trả lời “không xác định” cho các truy vấn sử dụng phép suy luận |≈Syn. Để cải thiện điều này, người ta điều chỉnh quá trình phát triển tập tiên đề diễn giải ở bước k khi sSyn(Σ, φ, k) là không nhất quán: chọn ra một tập các tiên đề nhất quán Σ00 sao cho: 00 sSyn(Σ, φ, k − 1) ⊂ Σ ⊂ sSyn(Σ, φ, k). Quy trình quay lui như vậy được sử dụng để sửa sai cho chiến lược mở rộng tuyến tính. Các tác giả gọi quy trình này quy trình xử lý quá xác định (overdetermined processing - ODP) của hàm chọn. Quy trình ODP không cần phải vét hết tất cả các tập con của tập sSyn(Σ, φ, k) \ sSyn(Σ, φ, k − 1), bởi vì nếu một tập các tiên đề nhất quán mà không thể khẳng định hay bác bỏ một truy vấn thì tập con của nó cũng vậy! Do đó, một cách tiếp cận của ODP là chỉ cần 00 chọn ra Σ là tập tiên đề nhất quán lớn nhất đầu tiên từ sSyn(Σ, φ, k). Tuy nhiên, quá trình xử lý ODP lại dẫn đến vấn đề gọi là không quyết định được (non-determinism): việc lựa chọn các tập con lớn nhất gồm các tiên đề nhất quán của s(Σ, φ, k) có thể sinh ra các kết quả khác nhau cho truy vấn “Σ |≈Syn φ?”. Một ví dụ tầm thường cho tình huống này là bài toán đánh giá truy vấn “Σ |≈Syn φ?” với Σ = {φ, ¬φ}. Chính vì vậy, ODP là quy trình cần phải tránh trong phép suy luận không chuẩn nói chung, hay nói cách khác, độ tốt của một hàm chọn dùng để xây dựng tập tiên đề diễn giải phụ thuộc vào việc nó có thể làm giảm khả năng phải áp dụng quy trình ODP trong phép suy luận không chuẩn hay không. 24
35. Ví dụ minh hoạ cho phép suy luận |≈Syn Luận án kết thúc mục này với hai ví dụ minh hoạ việc sử dụng phép suy luận |≈Syn để truy vấn với ontology không nhất quán. Ví dụ 1.5. Xét ontology Σ với các phát biểu như sau: Bird v Animal Chim là một loại động vật. Bird v Fly Chim có thể bay. Eagle v Bird Đại bàng là một loại chim. Penguin v Bird Chim cánh cụt là một loại chim. Penguin v ¬Fly Chim cánh cụt không biết bay. Penguin(TWEETY) Tweety là một cá thể chim cánh cụt. Có thể thấy rằng, Σ là một ontology không nhất quán. Bây giờ ta xét cách thức truy vấn “Σ |≈Syn Fly(TWEETY)?” (Cá thể chim cánh cụt Tweety có biết bay không?) hoạt động theo chiến lược mở rộng tuyến tính. 0 • Khởi đầu, Σ := sSyn(Σ, Fly(TWEETY), 0) = ∅. • Bước tiếp theo, bổ sung vào Σ0 những tiên đề liên quan trực tiếp với Fly(TWEETY). Ta có: 0 Σ := sSyn(Σ, Fly(TWEETY), 1) = {Bird v Fly, Penguin v ¬Fly, Penguin(TWEETY)}. 0 Do Σ |= ¬Fly(TWEETY) nên phép suy luận |≈Syn kết thúc tại bước này với kết luận bác bỏ Σ |≈Syn Fly(TWEETY) (bác bỏ mệnh đề “T weety là biết bay”). Một cách tương tự chúng ta có thể thu được kết luận chấp nhận Σ |≈Syn ¬Fly(TWEETY) (chấp nhận mệnh đề “Cá thể T weety là không biết bay”).  Ví dụ truy vấn Fly(TWEETY) với ontology Σ bằng phép suy luận |≈Syn cho thấy được tính “trực giác” của chiến lược mở rộng tuyến tính sử dụng hàm chọn dựa trên độ liên quan cú pháp sSyn. Phép suy luận |≈Syn trong trường hợp này 25
36. trả về kết quả truy vấn đúng và có nghĩa, điều không thể có được nếu áp dụng phép suy luận chuẩn |=. Tuy nhiên, như đã chỉ ra ở Tiểu mục 1.2.4, chiến lược mở rộng tuyến tính sử dụng hàm chọn dựa trên độ liên quan cú pháp sẽ làm cho tập tiên đề diễn giải được mở rộng một cách nhanh chóng, thậm chí mở rộng đến toàn bộ tập tiên đề của ontology Σ chỉ sau ít bước lặp. Điều này dẫn đến khả năng cao phải áp dụng quy trình ODP trong các phép suy luận không chuẩn. Trong trường hợp tổng quát, ODP sẽ làm mất đi tính có nghĩa của phép suy luận không chuẩn, vì thế, đây (mở rộng tập tiên đề nhanh chóng) chính là yếu điểm của hàm chọn dựa trên độ liên quan cú pháp sSyn. Ví dụ sau đây minh hoạ điều này. Ví dụ 1.6 (Nervous System - trích từ ontology DICE [53]). Xét ontology Σ với các phát biểu như sau: Brain v CentralNervousSystem Não bộ là hệ thần kinh trung ương. Brain v BodyPart Não là một bộ phận cơ thể. CentralNervousSystem v NervousSystem Hệ thần kinh trung ương là một Hệ thần kinh. BodyPart v ¬NervousSystem Bộ phận cơ thể không phải là một Hệ thần kinh. Brain(A) A là một cá thể của khái niệm Não bộ. Có thể thấy rằng, ontology trên là không nhất quán. Bây giờ ta xét cách thức hoạt động của truy vấn Σ |≈Syn Brain v NervousSystem? (Não bộ có thuộc loại Hệ thần kinh hay không?). • Khởi tạo: Σ0 := ∅. • Bước 1: Bổ sung vào Σ0 các tiên đề liên quan trực tiếp với truy vấn: 26
37. Σ0 := {Brain v CentralNervousSystem, Brain v BodyPart, Brain(A), CentralNervousSystem v NervousSystem, BodyPart v ¬NervousSystem} 0 = Σ1. Ngay từ bước lặp thứ nhất chúng ta đã nhận được tập tiên đề Σ0 (liên quan trực tiếp với truy vấn Brain v NervousSystem) bằng chính Σ. Hiển nhiên, đây là tập tiên đề không nhất quán và chúng ta cần phải tiến hành quy trình ODP. 0 Chúng ta xét ở đây hai khả năng loại bỏ một tiên đề khỏi Σ1 để thu được tập tiên đề lớn nhất và nhất quán đồng thời có thể trả lời được truy vấn Brain v NervousSystem thông qua phép suy luận chuẩn. 0 − Nếu loại bỏ tiên đề Brain v CentralNervousSystem khỏi Σ1, ta thu được tập tiên đề sau đây: 00 0 Σ1 = Σ1 \{Brain v CentralNervousSystem} = {Brain v BodyPart, Brain(A), CentralNervousSystem v NervousSystem, BodyPart v ¬NervousSystem} . 00 Có thể thấy rằng Σ1 |= ¬NervousSystem(A). 0 Như vậy, nếu loại bỏ Brain v CentralNervousSystem khỏi Σ1, với tập tiên 00 đề diễn giải Σ1 ta kết luận bác bỏ Σ |≈Syn NervousSystem(A). 0 − Nếu loại bỏ tiên đề Brain v BodyPart khỏi Σ1, ta thu được tập tiên đề 27
38. sau đây: 00 0 Σ2 = Σ1 \{Brain v BodyPart} = {Brain v CentralNervousSystem, Brain(A), CentralNervousSystem v NervousSystem, BodyPart v ¬NervousSystem} . 00 Ta thấy rằng Σ2 |= NervousSystem(A). 0 Như vậy, nếu loại bỏ Brain v BodyPart khỏi Σ1, với tập tiên đề diễn giải 00 Σ2 ta kết luận chấp nhận Σ |≈Syn NervousSystem(A). 0 Hai lựa chọn loại bỏ tiên đề khỏi Σ1 đem lại hai câu trả lời khác nhau. Điều này cho thấy trong quy trình ODP, nếu không có tiêu chí cụ thể để đánh giá và hướng dẫn việc rút gọn tập tiên đề thì |≈Syn trở nên không quyết định được.  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 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 là một phần trong kết quả nghiên cứu của dự án châu Âu SEKT (Semantic Knowledge Technologies)1, được thực hiện trong khoảng thời gian từ năm 2004 đến năm 2007. Khung lập luận này sau đó cũng được ứng dụng trong dự án châu Âu khác - LarKC (The Large Knowledge Collider)2 phát triển nền tảng lập luận với dữ liệu lớn, không đầy đủ và phân tán cho web ngữ nghĩa (thực hiện trong khoảng thời gian từ năm 2008 đến năm 2011). Thành phần quan trọng nhất của khung lập luận với ontology không nhất quán chính là hàm chọn thực hiện việc mở rộng tuyến tính tập tiên đề diễn giải theo truy vấn. Hàm chọn đầu tiên được phát triển là hàm chọn dựa trên sự liên quan cú pháp [21] có bản chất đơn giản, nhưng có thể trả về các kết quả có nghĩa cho 1 2 28
39. các truy vấn với ontology không nhất quán. Một số nhược điểm của hàm chọn này là: • Phép suy luận thường xuyên phải áp dụng quy trình ODP để quay lui: Điều này là do với tính chất của hàm chọn, tập tiên đề diễn giải nhanh chóng tiến đến một tập tiên đề không nhất quán chỉ sau một số ít bước lặp – thậm chí tiến đến toàn bộ tập tiên đề của ontology ban đầu như ở Ví dụ 1.6. • Số lượng tiên đề được bổ sung trong một bước lặp lớn. Điều này khiến cho quy trình ODP nếu được áp dụng cũng trở nên phức tạp. Trên thực tế, nếu gọi m ∈ N là số lượng tiên đề được bổ sung cuối cùng trước khi thực hiện ODP thì trong trường hợp xấu nhất, quy trình ODP phải thực hiện 2m − 2 phép thử để tìm ra tập tiên đề lớn nhất và nhất quán3. Hàm chọn dựa trên khoảng cách ngữ nghĩa [23] được đề xuất nhằm khắc phục các nhược điểm trên: hàm chọn này mở rộng tuyến tính tập tiên đề diễn giải dựa vào mức độ liên quan của các tiên đề trong ontology với tiên đề truy vấn: Mức độ liên quan giữa hai tiên đề được đánh giá thông qua khoảng cách ngữ nghĩa của các tên khái niệm (và tổng quát là tên thực thể) xuất hiện trong hai tiên đề. Khoảng cách ngữ nghĩa được sử dụng ở đây là khoảng cách Google được chuẩn hoá NGD (Normalized Google Distance) [8], đánh giá độ liên quan của hai từ khoá x và y dựa trên số lần xuất hiện của các từ khoá này trong các phép tìm kiếm Google: max{log f(x), log f(y)} − log f(x, y) NGD(x, y) = log M − min{log f(x), log f(y)} trong đó f(x) là số kết quả trả về của máy tìm kiếm Google cho từ khoá x, f(y) là số kết quả trả về của máy tìm kiếm Google cho từ khoá y, f(x, y) là số kết quả trả về của máy tìm kiếm Google cho từ khoá x và y, và M là số lượng trang web được đánh chỉ mục bởi máy tìm kiếm Google. Hàm chọn dựa trên khoảng cách ngữ nghĩa NGD khai thác tri thức khổng lồ được đánh chỉ mục của máy tìm kiếm Google, mặt khác có thể định lượng được mức độ liên quan của hai tiên đề4, do đó được nhận xét là tốt hơn so với 3Điều này là bởi, chúng ta phải xem xét loại bỏ tất cả các tập con của tập gồm m tiên đề (2m), và không tính tập rỗng, hay tập gồm cả m tiên đề. 4Mức độ liên quan của hai tiên đề được đánh giá bằng giá trị số thực nằm trong khoảng [0, 1] so 29
40. hàm chọn dựa trên sự liên quan cú pháp: Số lượng tiên đề được bổ sung trong một bước lặp của quá trình mở rộng tập tiên đề diễn giải là thấp hơn rất nhiều so với hàm chọn dựa trên sự liên quan cú pháp. Điều này đem lại hai điểm tích cực: Thứ nhất, khả năng phải áp dụng quy trình ODP trong quá trình lập luận được giảm xuống. Thứ hai, nếu phải áp dụng quy trình ODP thì chi phí tính toán cho quy trình ODP cũng được hạ thấp. Tuy vậy, hàm chọn dựa trên khoảng cách ngữ nghĩa NGD cũng có nhược điểm. Đây cũng là nhược điểm mang tính bản chất của cả hai hàm chọn nêu trên: phụ thuộc cú pháp biểu diễn của các thực thể trong các tiên đề. • Chiến lược mở rộng tập tiên đề diễn giải hoàn toàn phụ thuộc vào cú pháp biểu diễn các thực thể (tên khái niệm, tên vai trò, tên cá thể) trong tiên đề. Ví dụ, nếu dựa vào tên khái niệm, thì hai (biểu thức) khái niệm NervousSystem và ¬NervousSystem được xét là có như nhau trong các tiên đề trong khi về mặt ngữ nghĩa, chúng biểu diễn cho những khái niệm đối lập nhau hoàn toàn. Ngoài ra, việc phụ thuộc vào cú pháp (tên khái niệm) để xét mức độ liên quan giữa các khái niệm cũng là một điểm bất hợp lý bởi xét một cách tổng quát thì không thể mặc định có sự liên hệ ngữ nghĩa giữa tên thực thể với thực thể được biểu diễn ngoài thế giới thực [26]. • Các tên thực thể thường được kết hợp với nhau (theo quy tắc cú pháp được quy định bởi ngôn ngữ ontology cụ thể: tạo tử khái niệm, tạo tử vai trò, . . . ) để tạo nên các biểu thức phức tạp trong các tiên đề. Tuy vậy, chiến lược mở rộng tập tiên đề diễn giải không xét các 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ỳ, Ct¬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
41. kỳ, chúng ta sẽ không thấy sự liên quan nào giữa C t ¬C và D t ¬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
42. 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ụ. Q 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 Q(U) là tập hợp tất cả các bộ lập được từ tập hợp U: Y [ Q
    (U) = k(U) k∈N∗ Mỗi phần tử trong Q(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 n0 lần thì trong hồ sơ 32
43. tổng X ∪˙ Y phần tử này xuất hiện n + n0 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 n0 lần thì trong tập hợp hiệu của chúng X − Y, x xuất hiện n − n0 lần nếu n ≥ n0, 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 ∈ Q(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
44. 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
45. • 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
46. 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: Y 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
47. 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 ∈ Q(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 c(X(n)) = 1 . n→+∞ 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) 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 P − 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 ∈ Q(U), ta có: min{D(X)} min{D(Y)} ≤ ⇒ (c(X) ≥ c(Y)) . card(X) card(Y) P7a. Tiêu chuẩn về cải thiện tính nhất quán: 37
48. Cho a và a0 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(a0, X) = min{d(x, X) | x ∈ U} . Khi đó: c(X − {a}) ≤ c(X) ≤ c(X ∪˙ {a0}). P7b. Tiêu chuẩn thứ hai về cải thiện tính nhất quán: Cho b và b0 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(b0, X) = max{d(x, X) | x ∈ U} . Khi đó: c(X ∪˙ {b0}) ≤ c(X) ≤ c(X − {b}) . P8. Tiêu chuẩn về đơn giản hoá: Cho Y, Z ∈ Q(U) là những hồ sơ và X(n) = (n ∗ Y) ∪˙ Z. Khi đó: lim c(X(n)) = c(Y) . n→+∞  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à:   d(x1, x1) d(x1, x2) ··· d(x1, xM )   X  X   d(x1, x1) d(x1, x2) ··· d(x1, xM )  D = dij =  . . . .  (1.9)  . . .    d(xM , x1) d(xM , x2) ··· d(xM , xM ) • 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à: X X X X W = {w1 , w2 , . . . , wM } (1.10) 38
49. trong đó, M 1 X 1 wX = dX = d(x , x ) + d(x , x ) + ··· + d(x , x )
    i M − 1 ji M − 1 1 i 2 i M i j=1 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ị X trung bình chỉ được tính cho M −1 phần tử với lý do dii = 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 W X: X X Diam(W ) = max{wi | 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à:  M M M 1 P P X 1 P X  M(M−1) dij = M Wi , với M > 1 dmean(X) = i=1 j=1 i=1 (1.13) 0 , với M = 1 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: P d(x, y) M − 1 d (X) = x,y∈X = .d (X) . (1.14) t_mean M(M + 1) M + 1 mean • 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à X d(u, X) = d(u, x) . (1.15) x∈X 39
50. • 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} . X X • c2(X) = 1 − Diam(W ) = 1 − max{wi | 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ẩn P1a, 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
51. đồ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ạ Y C : (U) → 2U U trong đó, 2 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 ∈ Q(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: Y 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
52. 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}, 2 trong đó d2(v, X) ký hiệu cho d(v, X)
    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 ∈ Q(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
53. 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
54. Định nghĩa 1.19 (Tiêu chuẩn khả đồng thuận [45]). Trên không gian nửa- Q 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 −T REE (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 −T REE 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
55. 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
56. 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
57. 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 OWL 2. 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à OWL 2 được dựa trên logic mô tả SROIQ. Các tiên đề bao hàm của ontology OWL 2 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
58. 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 0 0 0 0
    ∧ ∀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
59. Đị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 là δO(c1, c2), được xác định như sau: n µO (c1, c0) + µO (c2, c0) o δO(c1, c2) := min | c0 ∈ LCPO(c1, c2) (2.1) µO (c1, c0) + µO (c2, c0) + 2.µO (c0, >) Trong trường hợp đã xác định rõ ontology O, ta có thể viết δ thay vì δO.  Chúng ta có một số nhận xét rút ra trực tiếp từ Định nghĩa 2.1 và Định nghĩa 2.2. 49
60. Mệnh đề 2.1 (Tính chất của khoảng cách ngữ nghĩa δ giữa hai khái niệm). Với mọi khái niệm có tên c1, c2 trong O: • δ(c1, c2) = δ(c2, c1); • 0 ≤ δ(c1, c2) ≤ 1; • δ(c1, c2) = 0 khi c1 ≡ c2. • δ(c1, c2) = 1 khi LCP(c1, c2) = {>} hoặc c1 = ⊥ hoặc c2 = ⊥; Ví dụ dưới đây minh hoạ khoảng cách ngữ nghĩa giữa hai khái niệm trên cây phân cấp: Ví dụ 2.1. Xét cây phân cấp khái niệm của ontology O như Hình 2.1. Hình 2.1: Cây phân cấp khái niệm minh hoạ a) Khoảng cách ngữ nghĩa của hai khái niệm Lion và Cat trên O được xác định như sau: • LCP(Lion, Cat) = {Animal}; 50
61. • µ(Lion, Animal) = µ(Cat, Animal) = µ(Animal, >) = 1; µ(Lion, Animal) + µ(Cat, Animal) 1 + 1 = = 0.5; µ(Lion, Animal) + µ(Cat, Animal) + 2.µ(Animal, >) 1 + 1 + 2.1 • Như vậy, δ(Lion, Cat) = 0.5. b) Khoảng cách ngữ nghĩa của hai khái niệm Animal và Cat được xác định như sau: • LCP(Animal, Cat) = {Animal}; µ(Animal, Animal) + µ(Cat, Animal) 0 + 1 1 • = = ; µ(Animal, Animal) + µ(Cat, Animal) + 2.µ(Animal, >) 0 + 1 + 2.1 3 1 • Như vậy, δ(Animal, Cat) = 3 . c) δ(Head, Cow) = δ(BodyPart, Cow) = 1.  Ví dụ trên cho thấy một số đặc điểm của cách đánh giá khoảng cách ngữ nghĩa giữa hai khái niệm theo phương pháp được nêu ở [62]. Theo đó, khoảng cách giữa hai khái niệm cha-con sẽ nhỏ hơn khoảng cách giữa hai khái niệm anh-em: δ(Animal, Cat) : δ(Head, Cow) = δ(BodyPart, Cow) = 1. Trên thực tế, chúng ta có thể khắc phục nhược điểm này bằng cách điều chỉnh thông số khoảng cách giữa hai khái niệm trên cây phân cấp như sau: Định nghĩa 2.3 (Số cung nối trực tiếp tối thiểu µ0 giữa hai khái niệm trên cây 0 phân cấp). Số cung nối trực tiếp tối thiểu µ giữa hai khái niệm c1, c2 ∈ CO trên 0 cây phân cấp khái niệm O, ký hiệu là µO (c1, c2), được xác định như sau:  µ (c , c ) với c 6= > , 0  O 1 2 2 µO(c1, c2) = (2.2) µO(c1, c2) + 1 với c2 = > 0 0 Trong trường hợp ontology O đã xác định, chúng ta viết µ thay vì viết µO.  Thay thế µ0 cho µ trong công thức (2.1), chúng ta sẽ có được công thức mới 0 đánh giá khoảng cách ngữ nghĩa δ giữa hai khái niệm có tên c1, c2 trên ontology O như sau: 2.µ0 (c , >) 0 n O 0 o δ O(c1, c2) := min 0 0 0 | c0 ∈ LCP(c1, c2) (2.3) µO (c1, c0) + µO (c2, c0) + 2.µO (c0, >) 51
62. 0 0 Ngoại trừ điều kiện δ (c1, c2) = 1 khi c1 = ⊥ hoặc c2 = ⊥, δ vẫn giữ được các tính chất của δ như ở Mệnh đề 2.1. Bên cạnh đó, δ0 có thể phân biệt được sai khác về khoảng cách ngữ nghĩa giữa các cặp khái niệm có khái niệm cha chung duy nhất là >. Điều này thể hiện như ở ví dụ dưới đây: Ví dụ 2.2. Tính lại khoảng cách ngữ nghĩa dựa trên khoảng cách µ0 của các khái niệm trên cây phân cấp ở Ví dụ 2.1. a) Khoảng cách ngữ nghĩa của hai khái niệm Lion và Cat được xác định như sau: • LCP(Lion, Cat) = {Animal}; • µ0(Lion, Animal) = 1; µ0(Cat, Animal) = 1; µ0(Animal, >) = 2; µ0(Lion, Animal) + µ0(Cat, Animal) 1 + 1 • = ≈ 0.33; µ0(Lion, Animal) + µ0(Cat, Animal) + 2.µ0(Animal, >) 1 + 1 + 2.2 • Như vậy, δ0(Lion, Cat) ≈ 0.33. b) Khoảng cách ngữ nghĩa của hai khái niệm Animal và Cat được xác định như sau: • LCP(Animal, Cat) = {Animal}; µ0(Animal, Animal) + µ0(Cat, Animal) 0 + 1 • = = 0.2; µ0(Animal, Animal) + µ0(Cat, Animal) + 2.µ0(Animal, >) 0 + 1 + 2.2 • Như vậy, δ0(Animal, Cat) = 0.2. c) Khoảng cách ngữ nghĩa của hai khái niệm Head và Cow được xác định như sau: • LCP(Head, Cow) = {>}; µ0(Head, >) + µ0(Cow, >) 3 + 4 • δ0(Head, Cow) = = ≈ 0.78 µ0(Head, >) + µ0(Cow, >) + 2.µ0(>, >) 3 + 4 + 2.1 d) Khoảng cách ngữ nghĩa của hai khái niệm BodyPart và Cow được xác định như sau: • LCP(BodyPart, Cow) = {>}; µ0(BodyPart, >) + µ0(Cow, >) • δ0(BodyPart, Cow) = µ0(BodyPart, >) + µ0(Cow, >) + 2.µ0(>, >) 2 + 4 = ≈ 0.67. 2 + 4 + 2.1 Có thể thấy, bằng cách sử dụng số cung nối trực tiếp tối thiểu µ0 thay cho µ, chúng ta có thể phân biệt được khoảng cách ngữ nghĩa giữa hai cặp khái 52
63. niệm (Head, Cow) và (BodyPart, Cow). Cụ thể: δ0(Head, Cow) ≈ 0.78 > 0.67 = δ0(BodyPart, Cow) Điều này phản ánh đúng với quan sát trực quan rằng: Do vị trí của Head là ở sâu hơn so với vị trí của BodyPart trên cây phân cấp, nên khoảng cách ngữ nghĩa của Head và Cow là lớn hơn so với khoảng cách ngữ nghĩa của BodyPart và Cow.  0 Về mặt bản chất, vai trò của µO và µO trong công thức tính khoảng cách ngữ 0 nghĩa giữa hai khái niệm thuộc ontology O là hoàn toàn như nhau. Do vậy, µO có thể được thay thế cho µO trong tất cả công thức tính khoảng cách ngữ nghĩa của luận án (giữa hai khái niệm, giữa hai biểu thức khái niệm, giữa hai tiên đề). 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 Gọi O là một ontology, CE1, CE2 là hai biểu thức khái niệm bất kỳ. Chúng ta gọi khoảng cách ngữ nghĩa giữa CE1 và CE2 khi đặt chúng trên cây phân cấp khái niệm của O là khoảng cách ngữ nghĩa giữa hai biểu thức khái niệm theo ontology O. Ontology O được gọi là ontology tham chiếu (để tính khoảng cách ngữ nghĩa): chúng ta sử dụng cây phân cấp khái niệm của O để đánh giá mức độ liên quan giữa hai khái niệm hoặc hai biểu thức khái niệm bất kỳ. Chúng ta định nghĩa công thức tính khoảng cách ngữ nghĩa giữa hai biểu thức khái niệm theo ontology tham chiếu bằng cách mở rộng công thức ở Định nghĩa 2.2. Định nghĩa 2.4 (Khoảng cách ngữ nghĩa giữa hai biểu thức khái niệm theo ontology tham chiếu). Cho O là một ontology, CE1, CE2 là các biểu thức khái niệm. Khoảng cách giữa CE1 và CE2 theo ontology tham chiếu O được xác định bởi công thức δO(CE1,CE2) = n µO (CE1, c0) + µO (CE2, c0) o min | c0 ∈ LCPO(CE1,CE2) µO (CE1, c0) + µO (CE2, c0) + 2.µO (c0, >) trong đó: 53
64. • µO (CE1,CE2) là số cung nối trực tiếp tối thiểu giữa hai biểu thức khái niệm CE1, CE2 khi đặt chúng trên cây phân cấp khái niệm của ontology O. • c0 là khái niệm cha chung tối thiểu của CE1 và CE2.  Theo định nghĩa trên, để tính khoảng cách ngữ nghĩa giữa hai biểu thức khái niệm CE1 và CE2 theo ontology tham chiếu O, chúng ta phải xác định được (1) tập khái niệm cha chung tối thiểu của hai biểu thức khái niệm LCPO(CE1,CE2) và (2) số cung nối trực tiếp tối thiểu µO (CE1,CE2) giữa hai biểu thức khái niệm CE1 và CE2 trên cây phân cấp khái niệm của O. (1) Tập khái niệm cha chung tối thiểu LCPO(CE1,CE2) được xác định theo các trường hợp sau đây: (i) Nếu CE1 v CE2 thì LCPO(CE1,CE2) = {CE2}; (ii) Nếu CE1 w CE2 thì LCPO(CE1,CE2) = {CE1}; (iii) Trong những trường hợp còn lại, LCPO(CE1,CE2) được xác định theo định nghĩa về khái niệm cha chung tối thiểu ở Mục 2.1: n LCPO(CE1,CE2) = c ∈ CO | CE1 v c ∧ CE2 v c 0 0 0 0
    o ∧ ∀c ∈ CO : CE1 v c ∧ CE2 v c ⇒ c v c . (2) Chúng ta có thể xác định µO (CE1,CE2) nhờ vào các giá trị µO (c1, c2) với c1, c2 ∈ CO theo nguyên tắc quy hoạch động: chỉ cần có trước thông tin về số cung nối trực tiếp tối thiểu của tất cả các cặp khái niệm có tên của O, chúng ta có thể tính được số cung nối trực tiếp tối thiểu giữa hai biểu thức khái niệm bất kỳ khi đặt chúng trên cây phân cấp khái niệm của ontology tham chiếu. Cụ thể, chúng ta có 4 trường hợp sau đây để tính số cung nối trực tiếp tối thiểu giữa hai biểu thức khái niệm trên ontology tham chiếu. (i) Tồn tại hai khái niệm c1, c2 ∈ CO sao cho c1 ≡ CE1 và c2 ≡ CE2. Đây là trường hợp đơn giản nhất, khi đó: µO (CE1,CE2) = µO (c1, c2) . 54
65. (ii) Tồn tại khái niệm c1 ∈ CO sao cho c1 ≡ CE1, đồng thời không tồn tại khái niệm có tên nào trên O tương đương với CE2. Khi đó: µO (CE1,CE2) = µO (c1,CE2) = min{µO (c1, c) + 1 | c ∈ DCO(CE2)} . (iii) Tồn tại khái niệm c2 ∈ CO sao cho c2 ≡ CE2, đồng thời không có khái niệm có tên nào trên O tương đương với CE1. Khi đó: µO (CE1,CE2) = µO (CE1, c2) = min{µO (c, c2) + 1 | c ∈ DPO(CE1)} . (iv) Không tồn tại khái niệm có tên nào trên O tương đương với các biểu thức khái niệm CE1, CE2. Khi đó: 0 0 µO (CE1,CE2) := min{µO (c, c ) + 2 | c ∈ DPO(CE1), c ∈ DCO(CE2)} . Như vậy, chúng ta luôn xác định được số cung nối trực tiếp tối thiểu giữa hai biểu thức khái niệm bất kỳ khi đặt chúng trên cây phân cấp khái niệm của ontology tham chiếu. Do đó, chúng ta luôn có thể xác định khoảng cách ngữ nghĩa giữa hai biểu thức khái niệm theo ontology tham chiếu theo Định nghĩa 2.4. Đặc biệt, với µO (c1, c2) đã được tính trước với ∀c1, c2 ∈ CO thì việc xác định khoảng cách ngữ nghĩa giữa hai biểu thức khái niệm theo ontology tham chiếu O là rất hiệu quả. 2.3. Khoảng cách ngữ nghĩa giữa hai tiên đề theo ontology tham chiếu Trong phần này, luận án sẽ thực hiện đánh giá khoảng cách ngữ nghĩa giữa hai tiên đề dựa vào khoảng cách ngữ nghĩa của các biểu thức thực thể tồn tại trong chúng. Các biểu thức thực thể trong một tiên đề có thể là biểu thức khái niệm, biểu thức thuộc tính đối tượng hoặc biểu thức thuộc tính dữ liệu. Tuy nhiên, để đơn giản hoá việc thành lập khoảng cách ngữ nghĩa của hai tiên đề, luận án chỉ xét dựa trên khoảng cách ngữ nghĩa giữa hai biểu thức khái niệm. Việc xét thêm khoảng cách ngữ nghĩa của các thuộc tính (thuộc tính đối tượng hoặc thuộc tính dữ liệu) và các cá thể hoàn toàn có thể được thực hiện một cách tương tự. Trước hết, chúng ta định nghĩa khoảng cách ngữ nghĩa giữa hai tập biểu thức khái niệm theo ontology tham chiếu. Khoảng cách này được xác định dựa trên khoảng cách ngữ nghĩa giữa các biểu thức khái niệm trong hai tập hợp đó. 55
66. Định nghĩa 2.5 (Khoảng cách ngữ nghĩa giữa hai tập biểu thức khái niệm theo ontology tham chiếu). Cho O là một ontology, A và B là hai tập hợp khác rỗng gồm các biểu thức khái niệm. Khoảng cách ngữ nghĩa của hai tập này theo ontology tham chiếu O, ký hiệu là dO(A, B), được xác định như sau: X δO(CEa,CEb) CEa∈A,CEb∈B dO(A, B) := . (2.4) card(A).card(B) Ta quy ước, dO(A, B) = 1 khi A = ∅ hoặc B = ∅ .  Giá trị dO(A, B) tính theo (2.4) chính là trung bình cộng các khoảng cách ngữ nghĩa giữa các cặp biểu thức khái niệm lấy từ hai tập hợp. Từ Mệnh đề 2.1 và Định nghĩa 2.4, Định nghĩa 2.5, ta có thể thấy khoảng cách ngữ nghĩa dO giữa hai tập hợp biểu thức khái niệm thoả các tính chất sau đây: Mệnh đề 2.2 (Tính chất của khoảng cách ngữ nghĩa giữa hai tập hợp biểu thức khái niệm). Với mọi tập biểu thức khái niệm bất kỳ A, B ta có: (a) 0 ≤ dO(A, B) ≤ 1 ; (b) dO(A, A) = 0 ; (c) dO(A, B) = dO(B, A); (d) Nếu tất cả các biểu thức khái niệm trong A đều có khoảng cách ngữ nghĩa cực đại đến mọi biểu thức khái niệm trong B thì khoảng cách dO(A, B) cũng đạt cực đại:   ∀CEi ∈ A, ∀CEj ∈ B : δO(CEi,CEj) = 1 ⇒ dO(A, B) = 1 ; (e) Nếu tất cả các biểu thức khái niệm trong A đều có khoảng cách ngữ nghĩa cực tiểu đến mọi biểu thức khái niệm trong B thì khoảng cách dO(A, B) cũng đạt cực tiểu:   ∀CEi ∈ A, ∀CEj ∈ B : δO(CEi,CEj) = 0 ⇒ dO(A, B) = 0 ; (f) Nếu có một số biểu thức cùng xuất hiện trong cả hai tập hợp, đồng thời một số biểu thức khác là có sai khác ngữ nghĩa thì khoảng cách ngữ nghĩa giữa hai tập hợp là không cực tiểu và không cực đại:
    
    
    A ∩ B 6= ∅ ∧ A 6⊆ B ∧ B 6⊆ A ⇒ 0 < dO(A, B) < 1 . 56