Luận án Tiến sĩ Hệ thống thông tin: Khôi phục tính nhất quán và tích hợp tri thức sử dụng mô hình xác suất

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

Thêm vào BST

Báo xấu

12
lượt xem 2
download

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

Luận án đề xuất một sơ đồ nguyên lý chung của hệ thống tích hợp tri thức xác suất. Từ sơ đồ nguyên lý chung này, luận án tiến hành đề xuất các giải pháp để thực hiện hai giai đoạn chính của sơ đồ nguyên lý: Giai đoạn khôi phục tính nhất quán trong cơ sở tri thức xác suất và giai đoạn tích hợp các cơ sở tri thức xác suất.

Chủ đề:

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

Lưu

Nội dung Text: Luận án Tiến sĩ Hệ thống thông tin: Khôi phục tính nhất quán và tích hợp tri thức sử dụng mô hình xác suất

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN VĂN THẨM KHÔI PHỤC TÍNH NHẤT QUÁN VÀ TÍCH HỢP TRI THỨC SỬ DỤNG MÔ HÌNH XÁC SUẤT LUẬN ÁN TIỄN SĨ HỆ THỐNG THÔNG TIN Hà Nội - 2021
ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN VĂN THẨM KHÔI PHỤC TÍNH NHẤT QUÁN VÀ TÍCH HỢP TRI THỨC SỬ DỤNG MÔ HÌNH XÁC SUẤT Chuyên ngành Hệ thống thông tin Mã số: 9480104.01 LUẬN ÁN TIỄN SĨ HỆ THỐNG THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC: 1. GS.TSKH Nguyễn Ngọc Thành 2. TS Trần Trọng Hiếu Hà Nội - 2021
LỜI CAM ĐOAN Tôi xin cam đoan luận án “Khôi phục tính nhất quán và tích hợp tri thức sử dụng mô hình xác suất ” là công trình nghiên cứu của riêng tôi. Các số liệu, kết quả được trình bày trong luận án là hoàn toàn trung thực và chưa từng được công bố trong bất kỳ một công trình nào khác. Tôi đã trích dẫn đầy đủ các tài liệu tham khảo, công trình nghiên cứu liên quan ở trong nước và quốc tế. Ngoại trừ các tài liệu tham khảo này, luận án hoàn toàn là công việc của riêng tôi. Trong các công trình khoa học được công bố trong luận án, tôi đã thể hiện rõ ràng và chính xác đóng góp của các đồng tác giả và những gì do tôi đã đóng góp. Luận án được hoàn thành trong thời gian tôi làm Nghiên cứu sinh tại Bộ môn Các Hệ thống Thông tin, Khoa Công nghệ Thông tin, Trường Đại học Công nghệ, Đại học Quốc gia Hà Nội. Tác giả: Hà Nội: i
ii LỜI CẢM ƠN Trước hết, tôi muốn bày tỏ sự biết ơn vô hạn đến GS.TSKH. Nguyễn Ngọc Thành - Trường Đại học Công nghệ Wroclaw, Ba Lan. Thầy đã truyền cho tôi niềm đam mê nghiên cứu khoa học, luôn tận tâm, động viên, khuyến khích và hướng dẫn tận tình để tôi có thể đạt được những thành công trong lĩnh vực nghiên cứu của mình. Tôi đã học hỏi được rất nhiều điều từ GS.TSKH Nguyễn Ngọc Thành: về những cống hiến không biết mệt mỏi của Thầy cho tri thức nhân loại, về tình yêu đất nước và cả những đóng góp cho quê hương của Thầy. Tôi cũng muốn bày tỏ lòng biết ơn sâu sắc tới TS. Trần Trọng Hiếu - Trường Đại học Công nghệ - Đại học Quốc gia Hà Nội. Thầy không chỉ hướng dẫn cho tôi những kiến thức về học thuật mà Thầy còn luôn đồng hành với tôi cả những khó khăn trên con đường nghiên cứu khoa học cũng như những khó khăn trong cuộc sống đời thường. Tôi xin chân thành cảm ơn tới tập thể các thầy cô giáo, các nhà khoa học thuộc Trường Đại học Công nghệ (đặc biệt là các thành viên của Phòng thí nghiệm khoa học dữ liệu và công nghệ tri thức – DS và KTlab) - Đại học Quốc gia Hà Nội đã giúp đỡ về chuyên môn và tạo điều kiện thuận lợi cho tôi trong suốt thời gian học tập và nghiên cứu. Trong đó, tôi xin trân trọng cảm ơn PGS.TS. Hà Quang Thụy, người Thầy đã luôn có những góp ý quý báu cho tôi trong quá trình tôi nghiên cứu tại Trường. Tôi bày tỏ sự biết ơn đến Ban giám hiệu và Lãnh đạo Khoa Công nghệ Thông tin - Trường Đại học Sư phạm Kỹ thuật Nam Định đã tạo mọi điều kiện thuận lợi cho tôi trong quá trình học tập và nghiên cứu; cảm ơn các đồng nghiệp Khoa Công nghệ Thông tin đã cổ vũ, động viên và sát cánh bên tôi trong suốt quá trình học tập và nghiên cứu. Tôi muốn cảm ơn đến tất cả những người bạn, các anh chị em NCS, những đồng nghiệp của tôi, và đặc biệt là gia đình Thầy Trần Trọng Hiếu. Những người đã luôn chia sẻ với tôi những khó khăn, giúp đỡ tôi rất nhiều cả về tinh thần lẫn vật chất. Cuối cùng, tôi xin bày tỏ lòng biết ơn vô hạn đối với gia đình nội ngoại hai bên của tôi, đã luôn ủng hộ tôi trong thời gian qua. Đặc biệt là mẹ tôi, vợ tôi Kiều Loan, hai con gái tôi Linh Giang và Hoài Giang, những người phụ nữ quan trọng đối với tôi, đã luôn khắc phục mọi khó khăn trong cuộc sống, sát cánh, động viên và là hậu phương vững chắc để tôi có thể hoàn thành được luận án này. NCS. Nguyễn Văn Thẩm
iii TÓM TẮT Trong quá trình phát triển của hệ thống dựa trên tri thức, tích hợp tri thức được hiểu là quá trình tạo ra một tri thức mới từ một tập các tri thức khác nhau; trong đó giữa các tri thức đầu vào có thể không đầy đủ và không nhất quán với nhau, hoặc bản thân mỗi tri thức đầu vào cũng có thể không đầy đủ và tồn tại mâu thuẫn nội tại. Do đó, giải quyết tính không nhất quán của cơ sở tri thức là một nhiệm vụ thiết yếu trước khi tiến hành tích hợp các cơ sở tri thức. Đề xuất các cách tiếp cận để giải quyết bài toán tích hợp cơ sở tri thức trong môi trường xác suất là một nhiệm vụ trọng tâm trong quá trình xây dựng một hệ thống dựa trên cơ sở tri thức xác suất. Luận án đề xuất một sơ đồ nguyên lý chung của hệ thống tích hợp tri thức xác suất. Từ sơ đồ nguyên lý chung này, luận án tiến hành đề xuất các giải pháp để thực hiện hai giai đoạn chính của sơ đồ nguyên lý: Giai đoạn khôi phục tính nhất quán trong cơ sở tri thức xác suất và giai đoạn tích hợp các cơ sở tri thức xác suất. Nội dung của luận án được tóm tắt như sau: (i) Khảo sát về các phương pháp xử lý tính không nhất quán và các phương pháp tích hợp tri thức. - Khảo sát và đánh giá các hệ thống tích hợp tri thức hiện có; đề xuất một sơ đồ nguyên lý chung của hệ thống tích hợp tri thức xác suất và so sánh với hệ thống hiện có. - Khảo sát và đánh giá một số phương pháp xử lý tính không nhất quán và một số phương pháp tích hợp tri thức dạng lôgic, lôgic-xác suất, xác suất. (ii) Đề xuất phương pháp khôi phục tính nhất quán trong cơ sở tri thức xác suất: Mô hình khôi phục tính nhất quán của cơ sở tri thức xác suất theo chuẩn và mô hình khôi phục tính nhất quán của cơ sở tri thức xác suất phi chuẩn; - Phân loại, đánh giá và làm cho lớp độ đo không nhất quán thông dụng nhất của cho cơ sở tri thức dạng lôgic, lôgic-xác suất phù hợp với dạng xác suất bằng cách xem xét các tính chất kỳ vọng mà chúng cần phải thỏa mãn.
iv - Đề xuất toán tử khôi phục theo chuẩn và toán tử khôi phục phi chuẩn cho cơ sở tri thức dạng xác suất; xem xét và chứng minh một tập các tính chất kỳ vọng mà các toán tử khôi phục này nên thỏa mãn. - Phát biểu và chứng minh các bài toán khôi phục tính nhất quán. - Đề xuất các thuật toán khôi phục tính nhất quán; đánh giá độ phức tạp của các thuật toán bằng chứng minh toán học; cài đặt, đánh giá và phân tích về độ tin cậy của các kết quả thu được cũng như chi phí thực hiện các thuật toán trong các mô hình đã đề xuất trên các bộ thực nghiệm. (iii) Đề xuất phương pháp tích hợp các cơ sở tri thức xác suất: Mô hình tích hợp dựa theo khoảng cách và mô hình tích hợp dựa trên giá trị xác suất. Với cách tiếp cận dựa trên khoảng cách: - Khảo sát 21 hàm khoảng cách phân kỳ. - Đề xuất các toán tử tích hợp tri thức xác suất; xem xét và chứng minh một tập các tính chất kỳ vọng mà các toán tử tích hợp tri thức xác suất này nên thỏa mãn. - Phát biểu và chứng minh các bài toán tích hợp tri thức xác suất dựa trên khoảng cách. - Đề xuất các thuật toán tích hợp tri thức xác suất dựa trên khoảng cách; đánh giá độ phức tạp của các thuật toán bằng chứng minh toán học; cài đặt, đánh giá và phân tích về độ tin cậy của các kết quả thu được cũng như chi phí thực hiện các thuật toán trong các mô hình đã đề xuất trên các bộ thực nghiệm. Với cách tiếp cận dựa trên giá trị xác suất: - Đề xuất hai toán tử tích hợp tri thức xác suất; xem xét một tập các tính chất kỳ vọng mà hai toán tử tích hợp tri thức xác suất này nên thỏa mãn. - Đề xuất các thuật toán tích hợp tri thức xác suất dựa trên giá trị xác suất; đánh giá độ phức tạp của các thuật toán bằng chứng minh toán học. Từ khóa: Tích hợp tri thức, cơ sở tri thức xác suất, độ đo không nhất quán, toán tử khôi phục tính nhất quán, toán tử tích hợp.
Mục lục Lời cam đoan i Lời cảm ơn ii Tóm tắt iii Mục lục v Danh mục các từ viết tắt viii Danh mục các bảng x Danh mục các hình vẽ xii Danh mục các kí hiệu xiii MỞ ĐẦU 1 Chương 1. KIẾN THỨC CƠ SỞ 12 1.1 Các phương pháp biểu diễn tri thức . . . . . . . . . . . . . . . 12 1.2 Biểu diễn CSTT xác suất . . . . . . . . . . . . . . . . . . . . . 14 1.2.1 Sự kiện và xác suất . . . . . . . . . . . . . . . . . . . . 14 1.2.2 Cơ sở tri thức xác suất . . . . . . . . . . . . . . . . . . 16 1.3 Hàm khoảng cách . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.4 Biểu diễn tính không nhất quát của CSTT xác suất . . . . . 21 1.5 Mô hình đặc trưng . . . . . . . . . . . . . . . . . . . . . . . . . 24 1.6 Kết chương . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 Chương 2. TỔNG QUAN VỀ XỬ LÝ TÍNH KHÔNG NHẤT QUÁN VÀ TÍCH HỢP TRI THỨC 28 2.1 Xử lý tính không nhất quán . . . . . . . . . . . . . . . . . . . 28 2.1.1 Bài toán xử lý tính không nhất quán . . . . . . . . . . 28 2.1.2 Độ đo không nhất quán . . . . . . . . . . . . . . . . . . 29 2.1.3 Các phương pháp xử lý tính không nhất quán . . . . . 32 v
Mục lục vi 2.2 Tích hợp tri thức . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.2.1 Bài toán tích hợp tri thức . . . . . . . . . . . . . . . . . 35 2.2.2 Các phương pháp tích hợp tri thức . . . . . . . . . . . 36 2.3 Hệ thống tích hợp tri thức . . . . . . . . . . . . . . . . . . . . 40 2.3.1 Các hệ thống tích hợp tri thức . . . . . . . . . . . . . . 40 2.3.2 Hệ thống tích hợp dựa trên tri thức xác suất . . . . . . 42 2.4 Kết luận chương . . . . . . . . . . . . . . . . . . . . . . . . . . 47 Chương 3. PHƯƠNG PHÁP KHÔI PHỤC TÍNH NHẤT QUÁN TRONG CƠ SỞ TRI THỨC XÁC SUẤT 48 3.1 Các độ đo không nhất quán của CSTT xác suất . . . . . . . . 48 3.1.1 Các tính chất của các độ đo không nhất quán . . . . . 48 3.1.2 Lớp độ đo không nhất quán cơ sở . . . . . . . . . . . . 50 3.1.3 Độ đo không nhất quán dựa theo chuẩn . . . . . . . . . 51 3.1.4 Độ đo không nhất quán phi chuẩn . . . . . . . . . . . . 56 3.1.5 Các thuật toán tính độ đo không nhất quán . . . . . . 59 3.2 Khôi phục tính nhất quán của CSTT xác suất . . . . . . . . . 65 3.2.1 Mô hình khôi phục tính nhất quán . . . . . . . . . . . . 65 3.2.2 Các tính chất của toán tử khôi phục tính nhất quán . 68 3.2.3 Lớp các toán tử khôi phục tính nhất quán . . . . . . . 69 3.2.4 Thuật toán tính giá trị xác suất của các RBXS trong CSTT xác suất . . . . . . . . . . . . . . . . . . . . . . . 80 3.2.5 Thuật toán khôi phục tính nhất quán của CSTT xác suất 82 3.3 Kết luận chương . . . . . . . . . . . . . . . . . . . . . . . . . . 85 Chương 4. PHƯƠNG PHÁP TÍCH HỢP CÁC CƠ SỞ TRI THỨC XÁC SUẤT 86 4.1 Phương pháp tích hợp các CSTT xác suất dựa trên khoảng cách 86 4.1.1 Mô hình tích hợp các CSTT xác suất dựa trên khoảng cách 86 4.1.2 Véctơ xác suất thỏa mãn của CSTT xác suất . . . . . 88 4.1.3 Các tính chất của toán tử tích hợp TTXS dựa trên khoảng cách . . . . . . . . . . . . . . . . . . . . . . . . . 92 4.1.4 Lớp các bài toán tích hợp dựa trên khoảng cách . . . . 94 4.1.5 Lớp toán tử tích hợp TTXS dựa trên khoảng cách . . 97 4.1.6 Thuật toán tích hợp các CSTT xác suất dựa trên khoảng cách . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 4.2 Phương pháp tích hợp các CSTT xác suất dựa giá trị xác suất 110 4.2.1 Mô hình tích hợp các CSTT xác suất dựa trên giá trị xác suất . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
Mục lục vii 4.2.2 Các tính chất của toán tử tích hợp TTXS dựa trên giá trị xác suất . . . . . . . . . . . . . . . . . . . . . . . . . 111 4.2.3 Các toán tử tích hợp dựa trên giá trị xác suất . . . . . 112 4.2.4 Thuật toán rút gọn RBXS . . . . . . . . . . . . . . . . 114 4.2.5 Thuật toán tích hợp các CSTT xác suất dựa trên giá trị xác suất . . . . . . . . . . . . . . . . . . . . . . . . . 115 4.3 Thực nghiệm tích hợp các cơ sở tri thức xác suất . . . . . . . 120 4.3.1 Mục đích và giả thiết thực nghiệm . . . . . . . . . . . . 121 4.3.2 Cấu hình thực nghiệm . . . . . . . . . . . . . . . . . . . 122 4.3.3 Triển khai thực nghiệm . . . . . . . . . . . . . . . . . . 124 4.3.4 Kết quả, ý nghĩa thực tiễn và phân tích . . . . . . . . . 125 4.4 Kết luận chương . . . . . . . . . . . . . . . . . . . . . . . . . . 137 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN 138 DANH MỤC CÁC CÔNG TRÌNH KHOA HỌC 142 TÀI LIỆU THAM KHẢO 143 Phụ lục A 1 A.1 Các hình vẽ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 A.2 Các bảng tổng hợp kết quả tính toán . . . . . . . . . . . . . . 3 A.3 Độ phức tạp của các thuật toán . . . . . . . . . . . . . . . . . 14 A.4 Bộ thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . . . . 20
DANH MỤC CÁC TỪ VIẾT TẮT Từ viết tắt Tiếng Việt Tiếng Anh CSTT Cơ sở tri thức Knowledge Base KNQ Không nhất quán Inconsistency THTT Tích hợp tri thức Merging Knowledge RBXS Ràng buộc xác suất Probabilistic Constraint TTXS Tri thức xác suất Probabilistic Knowledge KCPK Khoảng cách phân kỳ Divergence Distance NBOP Bài toán tối ưu dựa Norm Based Optimization theo chuẩn Problems UNOP Bài toán tối ưu phi chuẩn Unnormalized Optimization Problems CIM Tính độ đo không Computing Inconsistency Mea- nhất quán sure FPVPC Tìm giá trị xác suất của Finding the Probability Values các RBXS of Probabilistic Constraints RCK Khôi phục tính nhất quán Restoring the Consistency of a của CSTT xác suất Probabilistic Knowledge Base FSPVK Tìm véctơ xác suất thỏa Finding the Satisfying Proba- mãn của một CSTT bility Vector of a Probabilistic xác suất Knowledge Base FPMV Tìm véctơ tích hợp xác Finding Probability Merging suất của một hồ sơ TTXS Vector of a Probabilistic Know- ledge Base Profile FCKM Tìm CSTT xác suất nhất Finding a Consistent Probabi- quán sau khi tiến trình listic Knowledge Base after the tích hợp Merging Process DPC Rút gọn các RBXS Deducting Probabilistic Constraints viii
Danh mục các từ viết tắt ix Từ viết tắt Tiếng Việt Tiếng Anh MM Tích hợp trung vị Mean Merging CON Tính nhất quán Consistency MON Tính đơn điệu Monotonicity SUA Tính siêu cộng tính Super-Additivity NOR Tính chuẩn hóa Normalization MIS Tính phân tách MI MIS-Separability FCI Tính độc lập của ràng Free-constraint independence buộc tự do SCI Tính độc lập của ràng Safe-constraint independence buộc an toàn SUC Tính thành công Success SPR Tính bảo toàn cấu trúc Structure Presevation VAC Tính bất biến Vacuity IRS Tính không phụ thuộc Irrelevance of Syntax vào cú pháp NOD Tính phi độc tài Non-Dictatorship WIA Tính lựa chọn không phù Weak Irrelevant Alternatives hợp yếu IA Tính lựa chọn không Irrelevant Alternatives phù hợp CP Tính nhất quán Consistency Principle SCP Tính nhất quán mạnh Strong Consistency EIP Tính bất biến rỗng Empty Invariance EP Tính tương đương Equivalence PIP Tính bất biến dương Positive Invariance AP Tính đồng thuận Agreement DP Tính bất đồng Disagreement SDP Tính bất đồng mạnh Strong disagreement CMT Giao hoán Commutativity IDP Lũy đẳng Idempotence MVP Giá trị trung vị Mean Value Property SFS Tự đối xứng Self-Symmetry SM Đối xứng Symmetry SIS Nửa đối xứng Semi-Symmetry
DANH MỤC CÁC BẢNG 1.1 Tri thức của các bác sĩ . . . . . . . . . . . . . . . . . . . . . . . 18 1.2 Các hàm KCPK cơ bản[5, 20, 28, 52, 53, 75, 83]. . . . . . . . 20 1.3 Các hàm KCPK theo hệ số [5, 20, 28, 53] . . . . . . . . . . . . 21 2.1 Các độ đo KNQ của các dạng CSTT . . . . . . . . . . . . . . 30 2.2 Các phương pháp xử lý tính KNQ . . . . . . . . . . . . . . . . 32 2.3 Các phương pháp THTT . . . . . . . . . . . . . . . . . . . . . 36 2.4 So sánh hệ chuyên gia dựa trên luật và dựa trên xác suất. . 42 2.5 So sánh giữa hệ thống THTT đề xuất với hệ thống THTT đã tồn tại . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.1 Các độ đo không nhất quán cơ sở . . . . . . . . . . . . . . . . 50 3.2 Mối liên hệ giữa các thuật toán khôi phục tính nhất quán với các định lý xây dựng và độ phức tạp của các thuật toán . . . 84 3.3 So sánh các phương pháp khôi phục tính nhất quán trên mô hình xác suất . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 4.1 Mối liên hệ giữa các thuật toán đề xuất với các định lý xây dựng và độ phức tạp của các thuật toán . . . . . . . . . . . . 119 4.2 Số biến tối ưu hóa n, số ràng buộc m, ước tính hiệu suất cho các thuật toán khác nhau . . . . . . . . . . . . . . . . . . . . . 122 4.3 Tập các sự kiện biểu diễn mối quan hệ giữa 3 dạng bệnh ung thư và 5 triệu chứng liên quan . . . . . . . . . . . . . . . . . . 123 4.4 So sánh phương pháp THTT trên mô hình xác suất . . . . . 136 A.1 Mối liên hệ giữa các độ đo KNQ của CSTT xác suất và các tính chất kỳ vọng. . . . . . . . . . . . . . . . . . . . . . . . . . 3 A.2 Các độ đo KNQ của CSTT xác suất K1 , K2 , K3 , K4 và K5 . . 4 A.3 Các véctơ vi phạm K1 , K2 , K3 , K4 , K5 theo p-norm . . . . . . . 5 A.4 Xác suất mới của các RBXS trong K1 và K5 dựa trên bài toán tối ưu không ràng buộc . . . . . . . . . . . . . . . . . . . . . . 5 x
Danh mục bảng xi A.5 Các véctơ xác suất khôi phục thỏa mãn theo 1-norm, 2-norm, ∞-norm của K1 và K5 . . . . . . . . . . . . . . . . . . . . . . . 5 A.6 Xác suất mới của các RBXS trong K1 và K5 dựa trên toán tử tích hợp theo chuẩn và phi chuẩn. . . . . . . . . . . . . . . . . 6 A.7 Mối liên hệ giữa toán tử khôi phục tính nhất quán của CSTT xác suất và các tính chất kỳ vọng. . . . . . . . . . . . . . . . . 6 A.8 Các véctơ xác suất thỏa mãn của K1 , K2 , K3 , K4 , K5 . . . . . . 7 A.9 Mối liên hệ giữa các toán tử tích hợp TTXS dựa trên khoảng cách và các tính chất kỳ vọng. . . . . . . . . . . . . . . . . . . 8 A.10Các véctơ tích hợp xác suất của R theo 1-norm . . . . . . . . 9 A.11Các véctơ tích hợp xác suất của R theo 2-norm . . . . . . . . 10 A.12Các véctơ tích hợp xác suất của R theo ∞-norm . . . . . . . 11 A.13Các véctơ tích hợp xác suất của R theo phi chuẩn . . . . . . 12 A.14Cơ sở TTXS mới K∗ sau khi tích hợp theo 1-norm sử dụng các hàm KCPK khác nhau . . . . . . . . . . . . . . . . . . . . 12 A.15Cơ sở TTXS mới K∗ sau khi tích hợp theo 2-norm sử dụng các hàm KCPK khác nhau . . . . . . . . . . . . . . . . . . . . 13 A.16Cơ sở TTXS mới K sau khi tích hợp theo ∞-norm sử dụng các hàm KCPK khác nhau . . . . . . . . . . . . . . . . . . . . 13 A.17Cơ sở TTXS mới K sau khi tích hợp theo phi chuẩn sử dụng các hàm KCPK khác nhau . . . . . . . . . . . . . . . . . . . . 13 A.18CSTT xác suất K0 sau khi sử dụng toán tử tích hợp TTXS MMO và CMMO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 A.19CSTT xác suất K∗ sau khi giảm RBXS . . . . . . . . . . . . . 14 A.20Tri thức của các bác sĩ cho bộ Thực nghiệm 1 . . . . . . . . . 20 A.21Tri thức của các bác sĩ cho bộ Thực nghiệm 2 . . . . . . . . . 20
DANH MỤC CÁC HÌNH VẼ 1 Thống kê công trình khoa học về xử lý tính KNQ và giải quyết bài toán tích hợp trong các hệ thống dựa trên tri thức trên ScienceDirect giai đoạn 1997-2020. . . . . . . . . . . . . . . . . 5 2 Sơ đồ tổng quan về các giải pháp, các công cụ cho các mô hình THTT và hướng nghiên cứu của luận án. . . . . . . . . . 7 3 Cấu trúc luận án. . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.1 Sơ đồ nguyên lý của hệ thống dựa trên tri thức xác suất. . . 43 2.2 Tiến trình tích hợp các CSTT xác suất. . . . . . . . . . . . . . 44 3.1 Mô hình tổng quát khôi phục tính nhất quán . . . . . . . . . 66 3.2 Mô hình khôi phục tính nhất quán dựa theo chuẩn . . . . . . 70 3.3 Mô hình khôi phục tính nhất quán phi chuẩn . . . . . . . . . 77 4.1 Mô hình tổng quát tích hợp các CSTT xác suất dựa theo khoảng cách . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 4.2 Mô hình tổng quát tích hợp các CSTT xác suất dựa theo giá trị xác suất . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 4.3 So sánh chất lượng của các RBXS sau tiến trình tích hợp với Thực nghiệm 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 4.4 So sánh chất lượng của các RBXS sau tiến trình tích hợp với Thực nghiệm 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 4.5 So sánh kết quả tích hợp theo 1-norm với các hệ số khác nhau của hàm KCPK A-Div, NA-Div cho Thực nghiệm 1. . . . . . 130 4.6 So sánh kết quả tích hợp theo 1-norm với các hệ số khác nhau của hàm KCPK AI-Div, NAI-Div và C-Div cho Thực nghiệm 1. 131 4.7 So sánh kết quả tích hợp theo 1-norm với các hệ số khác nhau của hàm KCPK D-Div, CS-Div và R-Div cho Thực nghiệm 1. 132 4.8 Chi phí của các thuật toán cho Thực nghiệm 1. . . . . . . . . 133 4.9 Chi phí của các thuật toán cho Thực nghiệm 2. . . . . . . . . 134 A.1 Mô hình chung cho tiến trình THTT [60] . . . . . . . . . . . . 1 A.2 Các thành phần cơ bản của một hệ thống dựa trên tri thức [17] 2 xii
DANH MỤC CÁC KÍ HIỆU Ký hiệu Diễn giải ý nghĩa F , G; E Các sự kiện; Tập các sự kiện Λ(E) Tập các hội đầy đủ của E E Số lượng các hội đầy đủ của E Θ |= F Hội đầy đủ Θ thỏa mãn F P(E) Tập các hàm xác suất P trên E, (F |G ) [ρ] RBXS với ý nghĩa xác suất sự kiện F xảy ra với điều kiện sự kiện G đã xảy ra là ρ K CSTT xác suất ¯ bK Số lượng các RBXS của CSTT xác suất K P |= K Hàm xác suất P thỏa mãn K (K) Tập tất cả các hàm xác suất thoả mãn K d ϑ (x , y ) Hàm KCPK giữa hai véctơ x , y theo phân kỳ ϑ AEK Ma trận đặc trưng của K E CK ,+ Ma trận hệ số không âm của K E CK ,− Ma trận hệ số không dương của K ¯ AK Ma trận đường chéo kép của K I(K) Độ đo không nhất quán của CSTT K. K |= ⊥ K là nhất quán K |= ⊥ K là không nhất quán R Hồ sơ TTXS B Đa tập hữu hạn các CSTT xác suất B Số lượng các CSTT xác suất trong B η p (K) Toán tử khôi phục tính nhất quán theo p-Norm của K η u (K) Toán tử khôi phục tính nhất quán phi Norm của K Γ(B) Toán tử tích hợp của B ⊕(ρ1 , ρ2 ) Toán tử tích hợp trung vị của ρ1 , ρ2 c (ρ1 , ρ2 ) Toán tử tích hợp trung vị theo hệ số c của ρ1 , ρ2 xiii
MỞ ĐẦU Cơ sở nghiên cứu Tích hợp tri thức (THTT - Knowledge Integration hoặc Merging Know- ledge) là nhiệm vụ quan trọng khi ta muốn kết hợp một số hệ thống dựa trên tri thức (Knowledge-base System) lại thành một hay để làm cho chúng có thể tương tác với nhau. Như vậy, THTT là một lĩnh vực nghiên cứu quan trọng trong quá trình xây dựng một hệ thống dựa trên tri thức. Hệ thống dựa trên tri thức là một hệ thống được máy tính hóa tạo ra và sử dụng cơ sở tri thức (CSTT - Knowledge Base) từ các nguồn dữ liệu và thông tin khác nhau để giải quyết các vấn đề phức tạp. Tương tác giữa các hệ thống dựa trên tri thức muốn thành công phụ thuộc nhiều vào sự nhất quán về tri thức của các hệ thống này. THTT được hiểu là quá trình tạo ra một CSTT chung cho một tập hợp các CSTT có sẵn bằng việc kết hợp các phần khác nhau của tri thức mà trong đó các CSTT này có thể tồn tại sự không nhất quán (KNQ - Inconsistency)[60]. THTT là một nhiệm vụ khó khăn do sự KNQ của tri thức là khó xác định và giải quyết tính KNQ này cũng là một vấn đề phức tạp (thường là bài toán NP-Complete) [60]. Tuy nhiên, sự tương tác giữa các hệ thống dựa trên tri thức không thể thực hiện được nếu không có khả năng tích hợp giữa các CSTT. Đây là một bài toán khó và có nhiều vấn đề cần giải quyết. Vấn đề THTT được phát biểu như sau: Cho một tập hợp các CSTT, các CSTT này có thể mâu thuẫn với nhau hoặc bản thân mỗi CSTT cũng chứa mâu thuẫn, làm thế nào để xây dựng được một CSTT chung đại diện tốt nhất cho CSTT đã cho ? Các ứng dụng sử dụng tiến trình THTT rất nhiều và đa dạng [11]. Ngày nay, THTT được nghiên cứu rộng trong nhiều lĩnh vực của Khoa học máy tính (Computer Science), Trí tuệ nhân tạo (Artificial Inteligence), Hệ thống thông minh hay hệ chuyên gia với các ứng dụng (Expert Systems with Ap- plications), Khoa học thông tin, Tính toán Neuron (Neurocomputing). Việc 1
Mở đầu 2 kết hợp tri thức từ các nguồn khác nhau sẽ tạo ra các lợi ích như mang lại nhiều tri thức hơn, đạt được sự đồng thuận hoặc đạt được sự nhất trí. Tuy nhiên, sự đánh đổi của việc kết hợp này là nó có thể tạo ra tính không chắc chắn (Uncertainty) của tri thức, và việc giải quyết sự không chắc chắn cũng là một trong các mục đích chính của THTT. Do sự đa dạng trong cách biểu diễn tri thức, các cách tiếp cận giải quyết tính KNQ và các phương pháp THTT cũng rất khác nhau để phù hợp cho mỗi cách biểu diễn tri thức này. Các dạng tri thức đã và đang được cộng đồng nghiên cứu là: Tri thức lôgic cổ điển, tri thức lôgic khả năng, tri thức lôgic-xác suất, tri thức xác suất (TTXS - Probabilistic Knowledge). Sự phát triển của các phương pháp xử lý tính KNQ - Phương pháp loại bỏ công thức: Ý tưởng chính của phương pháp này là tìm cách loại khỏi CSTT các thông tin dư thừa sao cho các thông tin còn lại phải nhất quán. Hai hướng chính của cách tiếp cận này là (i) loại bỏ đi một tập KNQ tối thiểu [7, 30, 33, 35–37, 72] và (ii) tìm một tập nhất quán cực đại [51]. Phương pháp loại bỏ công thức được sử dụng hiệu quả đối với CSTT dạng lôgic, lôgic khả năng bởi các CSTT dạng này đều được biểu diễn dựa trên các công thức trên một ngôn ngữ mệnh đề. Tuy nhiên, hạn chế của phương pháp này có thể làm mất đi một số công thức quan trọng trong quá trình xử lý tính KNQ. Hơn nữa, tính hữu hiệu của phương pháp này đối với CSTT xác suất chưa được nghiên cứu kỹ lưỡng. - Phương pháp thay đổi công thức hay thay đổi định tính (Qualitative Modification): Ý tưởng chính của phương pháp này là thay đổi cấu trúc các thành phần của công thức trong CSTT sao cho thu được CSTT nhất quán. Cách tiếp cận này phù hợp với các dạng CSTT dạng lôgic-xác suất, xác suất [41, 73]. Tuy nhiên, việc thay đổi cấu trúc của công thức có thể dẫn đến sự KNQ về mặt định tính với các công thức khác nếu không xem xét kỹ lưỡng mối liên hệ giữa các công thức trong CSTT. - Phương pháp thay đổi xác suất hay thay đổi định lượng (Quantitative modification): Ý tưởng chính của phương pháp này là thay đổi giá trị xác suất của ràng buộc xác suất (RBXS - Probabilistic Constraint) trong CSTT sao cho thu được CSTT nhất quán. Hai hướng tiếp cận chính của phương pháp này là (i) tuân theo mô hình Heuristic [30] và (ii) cực tiểu hóa độ đo KNQ để tìm được xác suất mới [21, 41, 63, 66, 68, 73, 76, 77]. Tuy nhiên, cách tiếp cận này mới chỉ dừng lại ở việc xử lý các CSTT dạng lôgic-xác suất trên một ngôn ngữ mệnh đề.
Mở đầu 3 Sự phát triển của các phương pháp tích hợp tri thức - THTT dạng lôgic cổ điển và lôgic khả năng [7, 9, 34, 47, 48, 70, 71] đã được nghiên cứu một cách kỹ lưỡng. Ý tưởng chính của phương pháp này là xây dựng một họ các toán tử tích hợp thông qua việc tìm một tập thứ tự ưu tiên bằng cách sử dụng hàm kết hợp hoặc hàm khoảng cách. Các kết quả đạt được rất hữu ích đối với các hệ thống hoạt động dựa trên tập luật. Gần đây, có một cách tiếp cận khác đó là đi tìm tập tri thức đồng thuận dựa trên lý thuyết đồng thuận, hàm kết hợp và hàm khoảng cách [46, 61, 80, 90]. Tuy nhiên, trong xu hướng công nghệ hiện tại, các hệ thống dựa trên tri thức đang chủ yếu dựa vào dữ liệu lớn thì tiếp cận này khó có thể áp dụng được. Hơn nữa, theo Potyka [66], THTT dạng lôgic cổ điển có thể được coi là quá trình học rút ra kết luận suy diễn từ các giả định nhất quán. Tuy nhiên, các giá trị chân lý cổ điển đúng và sai thường không đủ cho các ứng dụng trong các miền không chắc chắn. Lôgic-xác suất khắc phục nhược điểm này bằng cách biểu diễn các công thức theo xác suất, trong đó khi xác suất bằng 1 thì công thức đúng và khi xác suất bằng 0 thì công thức sai. - THTT dạng lôgic-xác suất [67] cho phép sử dụng thế mạnh của lý thuyết xác suất trong việc giải quyết tính KNQ đồng thời vẫn giữ được khả năng suy diễn lôgic. Tuy nhiên, các giải pháp cho bài toán tích hợp trên môi trường lôgic-xác suất vẫn còn hạn chế vì cách tiếp cận này phải được xác định bằng các hàm xác suất trên tập vũ trụ (Sample Space hoặc Universal Set) và được xét trong môi trường ngôn ngữ mệnh đề nên sẽ bị ràng buộc bởi công thức lôgic. Hơn nữa, cũng rất khó xác định làm thế nào xác suất mới trong các CSTT có thể được tính toán bởi vì rất khó để tìm các hàm xác suất thỏa mãn tất cả các RBXS trong CSTT. Mô hình cũng sẽ không khả thi đối với các các bài toán có không gian đầu vào lớn. Các cách tiếp cận này mới chỉ dừng lại ở việc giải quyết tính KNQ của các CSTT. - THTT dạng xác suất: Biểu diễn tri thức bằng xác suất là cách làm thuận tiện và phổ biến hiện nay khi mà tri thức của các hệ thống thường được khai phá từ dữ liệu. Hai cách tiếp cận chính để giải quyết bài toán THTT đó là (i) tìm một phân phối xác suất liên hợp (Joint Probability Distribution) từ tập các phân phối xác suất biểu diễn cho các TTXS đầu vào [5, 6, 84, 85, 87, 88, 91] và (ii) dựa trên giá trị xác suất của các RBXS [41–43, 50]. Với cách tiếp cận đi tìm một phân phối xác suất liên hợp thì có ba kỹ thuật được triển khai: sử dụng kỹ thuật lặp [84, 85, 91], sử dụng hàm ứng viên (Candidacy Functions) [21] và sử dụng hàm khoảng cách phân kỳ (KCPK - Divergence Distance) [5, 6, 87, 88]. Tuy nhiên, các cách tiếp cận này yêu cầu các CSTT ban đầu phải đảm bảo tính nhất quán và có cùng một cấu trúc.
Mở đầu 4 Tại Việt Nam, qua khảo sát các công trình khoa học được công bố, THTT đang là một lĩnh vực nghiên cứu khá mới mẻ ở Việt Nam. TS. Trần Thanh Lương, Trường Đại học Khoa học - Đại học Huế đã nghiên cứu về học khái niệm cho các hệ thống thông tin dựa trên logic mô tả [3]. Các nghiên cứu của GS.TS. Cao Hoàng Trụ - Trường Đại học Bách khoa - Đại học quốc gia Hồ Chí Minh về khai thác và tích hợp thông tin dựa trên ontology [15, 16]. TS. Dương Trọng Hải - Trường Đại học Nguyễn Tất Thành nghiên cứu về tích hợp ontology và ứng dụng [25, 26]. TS. Trương Hải Bằng - Trường Đại học Công nghệ Thông tin, Đại học Quốc Gia TP. Hồ Chí Minh nghiên cứu về tích hợp ontology mờ trên cơ sở lý thuyết đồng thuận [1]. TS. Nguyễn Văn Trung, Trường Đại học Khoa học - Đại học Huế nghiên cứu về một số phương pháp xử lý tri thức KNQ trong ontology [4]. Nhóm nghiên cứu của TS. Trần Trọng Hiếu - Đại học Quốc gia Hà Nội đã tập trung giải quyết vấn đề THTT dạng lôgic cho các hệ thống dựa trên tri thức sử dụng các kỹ thuật đàm phán và tranh luận [61, 80]. Gần đây, TS. Nguyễn Thị Hồng Khánh, Trường Đại học Điện lực đã nghiên cứu về xử lý KNQ trong THTT dựa trên lôgic [2]. Chính vì lý do đó, xử lý tính KNQ (khôi phục tính nhất quán) là một trong các nhiệm vụ cần phải giải quyết trước khi tiến hành THTT trong các hệ thống dựa trên tri thức. THTT là một chủ đề nghiên cứu, ứng dụng thu hút một cộng đồng nghiên cứu rộng rãi trên thế giới. Hình 1 tổng hợp số lượng công trình nghiên cứu được công bố trên ScienceDi- rect (https://www.sciencedirect.com) trong giai đoạn 1997-2020 có chứa các cụ từ "Knowledge-base system", "Probabilistic knowledge", "In- consistent knowledge", "Consistency knowledge", "Merging knowledge or Knowledge Integration" trong tiêu đề, tóm tắt và danh sách từ khóa với chủ đề công bố "Expert Systems with Applications", "Information Sciences", "Neurocomputing", "Knowledge-Based Systems" và "Procedia Computer Science". Động lực nghiên cứu - Để có thể giải quyết được bài toán tích hợp thì trước hết đảm bảo tính nhất quán của các hệ thống dựa trên tri thức luôn là một trong các yêu cầu thiết yếu bởi vì nếu tính nhất quán không được đảm bảo thì hầu hết các hệ thống này trở lên vô ích. Bởi vì tầm quan trọng đó, rất nhiều các nghiên cứu đã quan tâm đến việc khôi phục tính nhất quán trong các hệ thống dựa trên tri thức. Các cách tiếp cận chính để khôi phục tính nhất quán của một CSTT là: Loại bỏ công thức, thay đổi công thức, thay đổi xác suất (thay đổi
Mở đầu 5 Hình 1: Thống kê công trình khoa học về xử lý tính KNQ và giải quyết bài toán tích hợp trong các hệ thống dựa trên tri thức trên ScienceDirect giai đoạn 1997-2020. xác suất khoảng, thay đổi xác suất điểm). Tuy nhiên, các phương pháp này mới chỉ dừng lại ở việc xử lý tính KNQ của CSTT dạng lôgic cổ điển, lôgic khả năng, lôgic-xác suất, xác suất trên một ngôn ngữ mệnh đề. Hơn nữa, chưa có một mô hình khôi phục tính nhất quán cũng như thuật toán được đề xuất để giải quyết tính KNQ cho CSTT dạng xác suất trên tập các sự kiện. Đánh giá về tính tin cậy, tính đúng đắn cũng như đảm bảo các nguyên lý xác suất cơ bản khi thay đổi giá trị xác suất của các RBXS trong CSTT xác suất cũng cần được xem xét và chứng minh. - Khi tính nhất quán của các CSTT đầu vào trong hệ thống dựa trên tri thức được đảm bảo thì tiến trình THTT mới có thể được tiến hành và đem lại hiệu quả cao về chất lượng tích hợp cũng như thỏa mãn các tính chất cơ bản của nguyên lý tích hợp. Tùy vào mỗi dạng CSTT mà sẽ có các phương pháp tích hợp phù hợp tương ứng. Với CSTT dạng xác suất, các cách tiếp cận giải quyết bài toán THTT vẫn còn tồn tại một số vấn đề. Thứ nhất, đầu vào và đầu ra của các CSTT xác suất được biểu diễn bằng các phân phối xác suất, trong đó đầu vào của các CSTT xác suất phải nhất quán và có cùng cấu trúc. Thứ hai, chưa có một mô hình cũng như thuật toán được đề xuất để giải quyết bài toán THTT xác suất trên tập các sự kiện. Thứ ba, với cách tiếp cận dựa trên khoảng cách thì mới chỉ có một vài hàm khoảng cách được