Luận án Tiến sĩ Khoa học máy tính: Nghiên cứu phương pháp lập luận mờ trên đồ thị nhận thức sử dụng đại số gia tử

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

Thêm vào BST

Báo xấu

10
lượt xem 3
download

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

Luận án Tiến sĩ Khoa học máy tính "Nghiên cứu phương pháp lập luận mờ trên đồ thị nhận thức sử dụng đại số gia tử" trình bày các nội dung chính sau: Nghiên cứu dàn mở rộng cùng các phép toán trên miền trị ngôn ngữ; Nghiên cứu phương pháp biểu diễn, các tính chất của đồ thị LCM sử dụng ĐSGT; Nghiên cứu các thuật toán lập luận trên đồ thị LCM; Nghiên cứu tính chất của không gian trạng thái được sinh bởi đồ thị LCM.

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ĩ Khoa học máy tính: Nghiên cứu phương pháp lập luận mờ trên đồ thị nhận thức sử dụng đại số gia tử

ĐẠI HỌC HUẾ TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN VĂN HÁN NGHIÊN CỨU PHƯƠNG PHÁP LẬP LUẬN MỜ TRÊN ĐỒ THỊ NHẬN THỨC SỬ DỤNG ĐẠI SỐ GIA TỬ LUẬN ÁN TIẾN SĨ KHOA HỌC MÁY TÍNH HUẾ, NĂM 2023
ĐẠI HỌC HUẾ TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN VĂN HÁN NGHIÊN CỨU PHƯƠNG PHÁP LẬP LUẬN MỜ TRÊN ĐỒ THỊ NHẬN THỨC SỬ DỤNG ĐẠI SỐ GIA TỬ NGÀNH: KHOA HỌC MÁY TÍNH MÃ SỐ: 9480101 LUẬN ÁN TIẾN SĨ KHOA HỌC MÁY TÍNH Người hướng dẫn khoa học: 1. TS. NGUYỄN CÔNG HÀO 2. PGS. TSKH. NGUYỄN CÁT HỒ HUẾ, NĂM 2023
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 TS. Nguyễn Công Hào và PGS. TSKH. Nguyễn Cát Hồ. Những nội dung trong các công trình đã được 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 thuật toán, các tính chất toán học và kết quả nghiên cứu được 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 kỳ công trình nào khác. Nghiên cứu sinh Nguyễn Văn Hán i
LỜI CẢM ƠN Trước hết tôi xin bày tỏ lòng biết ơn chân thành và sâu sắc đến TS. Nguyễn Công Hào và PGS. TSKH. Nguyễn Cát Hồ là những người Thầy đã tận tình hướng dẫn chỉ bảo, động viên và giúp đỡ để tôi có thể hoàn thành được luận án này. Tôi xin chân thành cảm ơn Quý Thầy Cô Khoa Công nghệ Thông tin - Trường Đại học Khoa học, Đại học Huế đã tạo điều kiện thuận lợi trong công tác để tôi có đủ thời gian hoàn thành luận án này. Tôi xin cảm ơn Quý Thầy Cô, cán bộ quản lý Ban đào tạo - Đại học Huế, phòng Đào tạo Sau Đại học - Trường Đại học Khoa học, Đại học Huế đã giúp đỡ tôi hoàn thành kế hoạch học tập. Cuối cùng tôi xin chân thành cảm ơn Quý Thầy Cô Khoa Công nghệ Thông tin - Trường Đại học Nguyễn Tất Thành, các bạn đồng nghiệp, người thân trong gia đình luôn động viên, giúp đỡ tôi về mọi mặt trong suốt quá trình học tập, nghiên cứu. Nghiên cứu sinh Nguyễn Văn Hán ii
MỤC LỤC Lời cam đoan i Lời cảm ơn ii Mục lục iii Danh mục các ký hiệu v Danh mục các từ viết tắt vi Danh mục các ký hiệu tiếng anh vii Danh mục bảng, biểu viii Danh mục hình vẽ ix MỞ ĐẦU 1 Chương 1. CẤU TRÚC DÀN MỞ RỘNG TRÊN MIỀN TRỊ NGÔN NGỮ SỬ DỤNG ĐẠI SỐ GIA TỬ 10 1.1. Tập mờ và thông tin không chắc chắn . . . . . . . . . . . . . . . . . . . 10 1.1.1. Khái niệm tập hợp mờ . . . . . . . . . . . . . . . . . . . . . . . 11 1.1.2. Kiến thức cơ sở về đại số gia tử . . . . . . . . . . . . . . . . . . 17 1.1.3. Phép biến đổi về miền ngôn ngữ của ĐSGT . . . . . . . . . . . . 20 1.1.4. Hai cấp độ của giá trị chân lý . . . . . . . . . . . . . . . . . . . 22 1.2. Cấu trúc dàn mờ trên miền trị ngôn ngữ . . . . . . . . . . . . . . . . . 23 1.2.1. Cấu trúc từ vựng . . . . . . . . . . . . . . . . . . . . . . . . . . 24 1.2.2. Các cấu trúc dựa trên ĐSGT . . . . . . . . . . . . . . . . . . . . 25 1.2.3. Cấu trúc đại số trên miền ngôn ngữ . . . . . . . . . . . . . . . . 27 1.2.4. Cấu trúc dàn mở rộng trên miền trị ngôn ngữ . . . . . . . . . . . 28 1.2.5. Các phép toán trên dàn ELL . . . . . . . . . . . . . . . . . . . . 29 1.2.6. Các tính chất của dàn ELL . . . . . . . . . . . . . . . . . . . . . 30 1.3. Tiểu kết chương 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 Chương 2. CẤU TRÚC ĐỒ THỊ NHẬN THỨC TRÊN MIỀN TRỊ NGÔN NGỮ 39 2.1. Đồ thị nhận thức và đồ thị nhận thức mờ . . . . . . . . . . . . . . . . . 39 2.2. Đồ thị nhận thức mờ dựa trên ĐSGT . . . . . . . . . . . . . . . . . . . 50 2.2.1. Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 2.2.2. Mô hình LCM từ kế thừa mô hình FCM . . . . . . . . . . . . . . 52 2.2.3. Tính chất của đồ thị LCM . . . . . . . . . . . . . . . . . . . . . . 55 iii
2.2.4. Biểu diễn đồ thị LCM theo theo cấu trúc có thể hiện vào ra . . . 57 2.2.5. Mô hình LCM theo lý thuyết mô hình . . . . . . . . . . . . . . . 59 2.3. Tiểu kết chương 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 Chương 3. PHƯƠNG PHÁP LẬP LUẬN TRÊN ĐỒ THỊ NHẬN THỨC 62 3.1. Lập luận trên đồ thị nhận thức mờ FCM . . . . . . . . . . . . . . . . . 62 3.1.1. Lập luận tĩnh theo nhánh . . . . . . . . . . . . . . . . . . . . . . 62 3.1.2. Lập luận động theo trạng thái . . . . . . . . . . . . . . . . . . . 64 3.2. Lập luận trên đồ thị ngôn ngữ LCM . . . . . . . . . . . . . . . . . . . . 66 3.2.1. Phép biến đổi miền trên tập mờ . . . . . . . . . . . . . . . . . . 67 3.2.2. Lập luận tĩnh theo nhánh . . . . . . . . . . . . . . . . . . . . . . 68 3.2.3. Lập luận động theo biến đổi trạng thái . . . . . . . . . . . . . . 76 3.3. Tiểu kết Chương 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 KẾT LUẬN CHUNG 98 HƯỚNG PHÁT TRIỂN CỦA LUẬN ÁN 99 DANH MỤC CÔNG TRÌNH CỦA TÁC GIẢ . . . . . . . . . . . . . . . . . 100 TÀI LIỆU THAM KHẢO . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 iv
DANH MỤC CÁC KÝ HIỆU Ký hiệu Diễn giải ý nghĩa L Tập giá trị ngôn ngữ G Tập các phần tử sinh c+ Phần tử sinh dương − c Phần tử sinh âm H Tập các gia tử H+ Tập các gia tử dương − H Tập các gia tử âm W Phần tử trung hòa sgn Ký hiệu hàm dấu fm(x) Độ đo tính mờ của hạng từ x µ(h) Độ đo tính mờ của của gia tử h α Tổng độ đo tính mờ của các gia tử âm β Tổng độ đo tính mờ của các gia tử dương θ Giá trị ngữ nghĩa định lượng của phần tử trung hòa ϑ Ký hiệu hàm ánh xạ ngữ nghĩa định lượng Ξ Ký hiệu tập mờ, tập các khái niệm mờ F Ký hiệu Tập các công thức mờ v
DANH MỤC CÁC TỪ VIẾT TẮT Viết tắt Viết đầy đủ CSDL Cơ sở dữ liệu ĐSGT Đại số gia tử vi
DANH MỤC CÁC THUẬT NGỮ TIẾNG ANH Ký hiệu Thuật ngữ tiếng anh Diễn giải ý nghĩa HA Hedge Algebra Đại số gia tử FCM Fuzzy Cognitive Map Đồ thị nhận thức mờ CM Cognitive map Đồ thị nhận thức LCM Linguistic Cognitive Map Đồ thị nhận thức ngôn ngữ OMP Orthomodular poset Dàn trực giao RHA Refined hedge algebra Đại số gia tử mịn hóa SHA Symmetrical refined HA Đại số gia tử đối xứng mịn hóa LQL Linguistic quantum logic Logic lượng tử trên giá trị ngôn ngữ LG Linguistic graph Đồ thị ngôn ngữ FG Fuzzy graph Đồ thị mờ ELL Extended linguistic lattice Dàn mở rộng FAM Fuzzy associative memory Mô hình nhớ kết hợp trên tập mờ SAM Semanticization Associati- Ngữ nghĩa mô hình nhớ kết ive Memory hợp CWW Computing with words Tính toán trên từ FS Fuzzy syste Hệ điều khiển mờ LV Linguistic variable Biến ngôn ngữ LS Linguistic space Không gian ngôn ngữ NL Natural language Ngôn ngữ tự nhiên IoT Internet of thing Internet vạn vật vii
DANH MỤC BẢNG, BIỂU Bảng 1.1. Mờ hóa độ cao [0, 900] fit theo {H, M, S, N Z} từ [19] . . . . . . . . . 21 Bảng 1.2. Chuyển đổi các giá trị tập mờ sang giá trị ngôn ngữ . . . . . . . . . . 22 Bảng 2.1. Các biến khái niệm trong CM của Hình 2.1 . . . . . . . . . . . . . . 40 Bảng 2.2. Chuyển đổi giá trị từ tập {−1, 0, 1} sang tập {0, W, 1} ∈ HA . . . . 54 Bảng 3.1. Các đỉnh của đồ thị trong Hình vẽ 3.1 . . . . . . . . . . . . . . . . . 64 Bảng 3.2. Các cạnh của đồ thị trong Hình vẽ 3.1 . . . . . . . . . . . . . . . . . 64 Bảng 3.3. Bảng chuyển đổi các tập mờ sang giá trị ngôn ngữ trên tập L . . . . 70 Bảng 3.4. Các bước lập luận nhánh trên LCM . . . . . . . . . . . . . . . . . . . 70 Bảng 3.5. Các mệnh đề mờ của mô hình lao động trẻ em trong [75] . . . . . . . 77 Bảng 3.6. Ma trận biến ngôn ngữ . . . . . . . . . . . . . . . . . . . . . . . . . . 77 viii
DANH MỤC HÌNH VẼ Hình 1. Một đồ thị CM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Hình 2. Ma trận trọng số cho đồ thị Hình 1 . . . . . . . . . . . . . . . . . . . 3 Hình 3. Đồ thị FCM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Hình 4. Sơ đồ vào ra dữ liệu cho FCM . . . . . . . . . . . . . . . . . . . . . . 5 Hình 5. Sơ đồ vào ra dữ liệu cho LCM . . . . . . . . . . . . . . . . . . . . . . 6 Hình 1.1. Đồ thị vô hướng thể hiện của cấu trúc g . . . . . . . . . . . . . . . . 24 Hình 1.2. Đồ thị có hướng thể hiện của cấu trúc g . . . . . . . . . . . . . . . . 25 Hình 2.1. Một cognitive map . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 Hình 2.2. Đường đi Ch ; Ck . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 Hình 2.3. Một FCM đơm giản . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 Hình 2.4. Ma trận trọng số của đồ thị Hình 2.3 . . . . . . . . . . . . . . . . . . 44 Hình 2.5. FCM theo [20–22] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 Hình 2.6. Đồ thị FCM với các cạnh vào dữ liệu . . . . . . . . . . . . . . . . . . 47 Hình 2.7. Sơ đồ khối cho FCM . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 Hình 2.8. Sơ đồ khối cho mô hình LCM . . . . . . . . . . . . . . . . . . . . . . . 51 Hình 2.9. Một đồ thị LCM đơn giản . . . . . . . . . . . . . . . . . . . . . . . . 54 Hình 2.10.Đồ thị LCM khởi tạo với C(0) = {true, Mtrue, Ltrue, Vtrue} . . . . . . 54 Hình 2.11.Đồ thị LCM kế thừa từ FCM . . . . . . . . . . . . . . . . . . . . . . . 55 Hình 2.12.Ma trận trọng số của đồ thị Hình 2.11 . . . . . . . . . . . . . . . . . 56 Hình 2.13.Cấu trúc LCM mở rộng . . . . . . . . . . . . . . . . . . . . . . . . . . 58 Hình 2.14.Một LCM đơn giản trên struct[ G] . . . . . . . . . . . . . . . . . . . . 60 Hình 3.1. Đồ thị FCM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 Hình 3.2. Mô hình FCM cho vấn đề liên quan đến đầu gối . . . . . . . . . . . . 68 Hình 3.3. Mô hình LCM tương ứng cho vấn đề liên quan đến đầu gối . . . . . . 68 Hình 3.4. Đồ thị FCM với các biến ngôn ngữ đơn giản . . . . . . . . . . . . . . 69 Hình 3.5. Đồ thị LCM sử dụng các gia tử . . . . . . . . . . . . . . . . . . . . . . 71 Hình 3.6. Khởi tạo nhãn s = C1 = 1 các đỉnh khác có nhãn là 0, tập Q rỗng . . 73 Hình 3.7. Đưa C1 = 1 vào Q, Q = {C1 }, cập nhật lại nhãn cho C2 và C3 . . . . 74 Hình 3.8. Đưa C3 = M vào Q, Q = {C1 , C3 }, cập nhật lại nhãn cho C4 và C5 . . 74 Hình 3.9. Đưa C5 = M vào Q, Q = {C1 , C3 , C5 }, kết thúc thuật toán . . . . . . 75 Hình 3.10.Đồ thị child bour . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 Hình 3.11.Không gian trạng thái C = {C(0), C(1), C(2)} . . . . . . . . . . . . . 80 ix
Hình 3.12.Đồ thị FCM trong [81] . . . . . . . . . . . . . . . . . . . . . . . . . . 85 Hình 3.13.Đồ thị FCM trong [87] . . . . . . . . . . . . . . . . . . . . . . . . . . 87 Hình 3.14.Tìm giá trị ngôn ngữ cho C5 . . . . . . . . . . . . . . . . . . . . . . 89 Hình 3.15.Thiết lập đồ thị nền LCM . . . . . . . . . . . . . . . . . . . . . . . . 90 x
MỞ ĐẦU 1. Lý do chọn đề tài Trong cuộc sống hằng ngày, con người dùng ngôn ngữ tự nhiên NL (Natural Language) để học tập, trao đổi, thảo luận, phân tích, suy diễn và sau cùng, đưa ra quyết định của cá nhân mình. Máy tính, và các thiết bị thông minh, suy cho cùng, sinh ra là để phục vụ con người. Ngày nay, với sự phát triển nhanh chóng của ngành AI (artificial intelligence) các thiết bị IOT (internet of thing) ngày càng trở nên thông minh hơn nhờ hướng đến ngôn ngữ tự nhiên, hiểu được ngôn ngữ tự nhiên. Do đó, việc xử lý ngôn ngữ tự nhiên như biểu diễn, suy diễn, lập luận là một thách thức của ngành thông minh nhân tạo, ngành học máy nói chung và ngành xử lý ngôn ngữ tự nhiên nói riêng. Việc tính toán trực tiếp trên ngôn ngữ tự nhiên là một vấn đề hết sức khó khăn đầy thách thức của ngành AI. Lịch sử ngành tính toán với ngôn ngữ trong khoa học máy tính và trong AI đã có từ rất lâu [5]. Vào những năm của thập niên 1950, dịch máy (machine translation) đã bắt đầu được nghiên cứu, tuy nhiên các kết quả đạt được về tính toán với ngôn ngữ đã kết thúc năm 1965 khi tổ chức US Air Force thông báo về sự thất bại của máy dịch [5]. Một số nhà nghiên cứu vẫn tiếp tục các nghiên cứu về tính toán trên ngôn ngữ nhưng dưới các tên gọi khác nhau như phân tích (parsing), hệ câu hỏi-trả lời (question-answering) hoặc hệ chuyên gia (expert system) tuy nhiên các kết quả đạt được rất hạn chế. Các khám phá quan trọng đã xảy ra trong những năm 1990 bởi Zadeh về tính toán trên từ CWW (computing with words) [28]. Với phương pháp CWW, cuộc cách mạng của tính toán với ngôn ngữ đã quay lại và bắt đầu kỷ nguyên tính toán với ngôn ngữ. Logic mờ hay CWW (Logic mờ = tính toán trên từ [28]) dựa trên lý thuyết tập mờ FS (fuzzy set) [36] và biến ngôn ngữ LV (linguistic variable). Biến ngôn ngữ là các biến mà giá trị của chúng là các giá trị ngôn ngữ. Các giá trị của biến ngôn ngữ được xây dựng từ các phần tử sinh nguyên thủy của biến đó (ví dụ biến Age có các phần tử sinh nguyên thủy tương ứng là old và young) và tác động của các gia tử như 1
more, less, very, ... [33]. L. A. Zadeh đưa ra mô hình toán học để biểu diễn giá trị ngôn ngữ bằng tập mờ và dùng khái niệm "hàm thuộc" (membership function) để chỉ mức độ mà một phần tử thuộc tập hợp. Các thành phần ngôn ngữ mang thông tin không rõ ràng, chỉ mang tính chất mô tả, định tính và được gọi chung là các khái niệm "mờ". Tập mờ cùng với các phép toán logic được phát triển từ tập hợp kinh điển là mô hình toán học cho phép biểu diễn và tính toán trên các giá trị ngôn ngữ. Nhờ đó, giải quyết được lớp bài toán lập luận xấp xỉ trên máy tính mà đã không giải quyết được bằng logic kinh điển. Lập luận xấp xỉ cho lớp bài toán với thông tin vào - ra không chắc chắn được hình thức hóa theo cách tư duy tự nhiên của con người. Phương pháp suy diễn gần đúng từ một họ các tiên đề không chắc chắn. Như vậy, quá trình lập luận xấp xỉ mang các đặc trưng định tính nhiều hơn định lượng. Ứng dụng của tập mờ để biểu diễn tri thức bằng đồ thị lần đầu được đề xuất bởi vào năm 1975 bởi A. Rosenfeld [64]. Theo đó, đồ thị biểu diễn quan hệ mờ gồm tập đỉnh và tập cạnh mà giá trị của chúng nằm trong đoạn [0, 1]. Lý thuyết đầy đủ về đồ thị mờ được nghiên cứu bởi J. N. Mordeson và các cộng sự [66, 67, 78]. J. N. Mordeson hình thức hóa một đồ thị mờ là một bộ ba G = (V, ρ, µ) bao gồm tập không rỗng V cùng với cặp hàm số: µ : V → [0, 1] và ρ : V × V → [0, 1]. µ được gọi là tập đỉnh mờ của G và ρ là tập cạnh mờ của G và ρ là quan hệ mờ trên µ. Các tính chất đặc trưng trong lý thuyết đồ thị cũng được áp dụng trên đồ thị mờ như chu trình, đường đi, cạnh cầu và đỉnh cắt. Tuy nhiên, giá trị của các hàm số µ và ρ là không thay đổi trên đồ thị mờ G. Lớp đồ thị có giá trị của đỉnh thay đổi phụ thuộc theo quan hệ nhân - quả giữa các cặp đỉnh liền kề được đề xuất vào năm 1976 bởi R. Axelrod và được gọi là đồ thị nhận thức, CM (cognitive map) [8]. CM được dùng để biểu diễn tri thức và lập luận trong các vấn đề liên quan đến chính trị và xã hội. Đồ thị nhận thức của R. Axelrod là một đa đồ thị có hướng và có dấu. Trong đó, các đỉnh là các biến mệnh đề và các cạnh thể hiện mối liên kết nhân - quả giữa hai đỉnh liền kề. Có hai kiểu tác động nhân - quả khác nhau là tác động dương và tác động âm. Đỉnh Ci được gọi là tác động dương lên đỉnh Cj nếu giá trị của Ci tăng thì giá trị của Cj cũng tăng và ngược lại nếu giá trị của Ci giảm thì giá trị của Cj cũng giảm. Ký hiệu của tác động dương bằng một cạnh có dấu dương ( dấu +) giữa hai đỉnh liền kề. Ngược lại, đỉnh Ci được gọi là tác động âm lên đỉnh Cj nếu giá trị của Ci tăng thì giá trị của Cj giảm và ngược lại nếu giá trị của Ci giảm thì giá trị của Cj tăng. Ký hiệu của tác động âm bằng một cạnh có dấu âm ( dấu -) giữa hai đỉnh liền kề. Hình 1 là một đồ thị CM đơn giản bao gồm bốn đỉnh Ci , Cj , Ch , Ck và bốn cạnh (Ch , Ci ), (Ch , Cj ), (Ci , Ck ), (Cj , Ck ) được gán nhãn tương ứng là: -, +, +, +. Dấu của các cạnh được biểu diễn bằng một ma trận trọng số M. Với M là ma trận vuông kích thước n × n, trong đó n là số đỉnh của đồ thị CM. Ma 2
trận vuông trong Hình 2 là ma trận trọng số cho đồ thị biểu diễn bởi Hình 1. Ci - + Ch Ck + + Cj Hình 1: Một đồ thị CM Một CM cho phép biểu diễn mối liên hệ nhân - quả một cách định tính giữa các mệnh đề mờ trên đồ thị mà không diễn tả mức độ tác động nhân - quả giữa các đỉnh là nhiều hay ít. Các hạn chế trong biểu diễn tri thức của R. Axelrod đã được B. Kosko khắc phục vào năm 1986 [9]. B. Kosko đề xuất gán giá trị các mệnh đề mờ ở các đỉnh với các giá trị ngôn ngữ hoặc các giá trị trong đoạn [0, 1] và cũng sử dụng các giá trị số trong đoạn [0, 1] hoặc giá trị ngôn ngữ để thể hiện mức độ tác động nhân - quả giữa các cặp đỉnh liền kề. B. Kosko đặt tên cho đồ thị mở rộng từ CM là đồ thị nhận thức mờ FCM (fuzzy cognitive map) [9, 12]. Hình 3 là một đồ thị FCM đơn giản với năm đỉnh và năm cạnh. Trong đó, nhãn của mỗi cạnh được gán hai giá trị, một giá trị là dấu thuộc tập {−1, 0, 1} tương tự như trong đồ thị CM và một giá trị ngôn ngữ thể hiện mức độ phụ thuộc nhân - quả giữa hai đỉnh liền kề. Tập đỉnh nhận giá Ch Ci Ck Cj   Ch 0 −1 0 +1   M = Ci 0 0 +1 0   Ck 0  0 0 0 Cj 0 0 +1 0 Hình 2: Ma trận trọng số cho đồ thị Hình 1 3
trị trên đoạn [0, 1] [19–21] và giá trị của các đỉnh thay đổi theo phương trình:   m11 . . . m1n  . .. .  [C1 C2 . . . Cn ]new = [C1 C2 . . . Cn ]old  .  . . .  .  (1) mn1 . . . mnn Trong đó: [C1 C2 . . . Cn ]new là giá trị mới của các đỉnh ở thời điểm t + 1 được tính truy hồi theo [C1 C2 . . . Cn ]old là giá trị của các đỉnh liền trước đó, ở thời điểm t. Ma trận   m11 . . . m1n  . .. .  vuông  .  . . .  là ma trận trọng số với mij là trọng số cạnh nối hai đỉnh liền .  mn1 . . . mnn kề Ci và Cj . C1 A lot (-1) C2 A lot (-1) A lot (+1) C3 C5 Much (+1) Some (-1) C4 Hình 3: Đồ thị FCM Phương pháp tính toán trên từ trên FCM được đề xuất bởi J. T. Rickard và A. J. Yager vào năm 2015 trong [83,84]. Phương pháp của J. T. Rickard và A. J. Yager thực hiện tính giá trị hàm thành viên µ(x) của biến x theo số mờ hình thang. Từ giá trị hàm µ(x), dựa vào bảng từ vựng để tra ra giá trị ngôn ngữ tương ứng. Một phương 4
pháp tính toán trên từ cho đồ thị FCM được đề xuất bởi Mabel Frias và cộng sự vào năm 2017 [87] dựa trên lý thuyết Bộ hai [86] và dựa trên số mờ tam giác ( triangular fuzzy number) [88, 89]. Phương pháp CWW trên đồ thị nhận thức mờ FCM theo đề xuất của J. T. Rickard và A. J. Yager cũng như của Mabel Frias và cộng sự có thể chia thành bốn giai đoạn như hình theo Hình 4. C1 FCM 1 2 4 5 Từ Số Số Từ C2 C3 3 Hình 4: Sơ đồ vào ra dữ liệu cho FCM Sơ đồ tính toán này cho thấy dữ liệu vào ra là các từ. Ở giai đoạn 1, trước khi vào dữ liệu cho FCM để thực hiện phép lập luận thì phải chuyển sang số. Giai đoạn 2 là vào dữ liệu số cho FCM. Giai đoạn 3 là tính toán, vòng lặp trong sơ đồ cho thấy việc tính toán có thể phải lặp lại nhiều lần. Giai đoạn 4 là sau khi FCM thực hiện xong việc tính toán thì kết quả trả về là số. Sau cùng, giai đoạn 5 là chuyển kết quả từ số sang từ và xuất ra. Vì kết quả vào ra là các giá trị từ, giai đoạn chuyển sang số chỉ là giai đoạn trung gian để thực hiện việc lập luận. Như vậy, việc lập luận trên đồ thị FCM có thể tối ưu hóa nếu có thể tính toán trực tiếp được trên từ. Vấn đề tối ưu hóa cho bài toán FCM được thực hiện nhờ một cấu trúc đại số của miền giá trị là biến ngôn ngữ được đề xuất bởi N. C. Ho và W. Wechler [50]. Theo phương pháp này, mỗi giá trị ngôn ngữ được sinh ra từ một biến ngôn ngữ thuộc một cấu trúc đại số trừu tượng được gọi là đại số gia tử (ĐSGT). Cấu trúc này đã đại số hóa miền giá trị của biến ngôn ngữ để thực hiện phương pháp lập luận trên từ mà không phải chuyển sang số [53]. Dựa trên ĐSGT, đại số gia tử tuyến tính và đại số gia tử đơn điệu được nghiên cứu giúp cho việc tính toán trên từ ngày càng được hoàn thiện hơn [1, 61, 62]. Như vậy, áp dụng phương pháp lập luận trên từ bằng cách sử dụng ĐSGT sẽ giúp 5
đơn giản hóa việc lập luận trên đồ thì FCM vì giảm bớt các phép toán chuyển đổi từ số qua từ và ngược lại. Khi đó, sơ đồ lập luận trong Hình 4 được tối ưu hóa thành sơ đồ thu gọn như Hình 5. Trong đó, các phép toán trên số đã được loại trừ và cấu trúc FCM phải được thay thế bằng một cấu trúc đồ thị dựa trên ĐSGT gọi là LCM (linguistic cognitive map). Với các nhận xét trên, việc nghiên cứu một phương pháp biểu diễn và lập luận trên đồ C1 LCM 1 3 Từ Từ C2 C3 2 Hình 5: Sơ đồ vào ra dữ liệu cho LCM thị sử dụng biến ngôn ngữ là cần thiết, phù hợp với các ứng dụng trong thực tế và suy luận tự nhiên của con người. Đó là lý do để luận án nghiên cứu và phát triển đề tài: Nghiên cứu phương pháp lập luận mờ trên đồ thị nhận thức sử dụng đại số gia tử 2. Đối tượng và phạm vi nghiên cứu Để mô hình hóa, lập luận và kiểm chứng trên đồ thị mờ, luận án bắt đầu từ việc nghiên cứu một dàn mở rộng ELL (extended linguistic lattice) dựa trên biến ngôn ngữ. Dàn ELL thực hiện các phép toán lấy giá trị lớn nhất (Max) và giá trị nhỏ nhất (Min) trên nhiều toán hạng là các giá trị ngôn ngữ. Cấu trúc và các phép toán trên dàn ELL là cơ sở cho các tính toán trên các vector và ma trận các giá trị ngôn ngữ. Các tính toán trên miền trị ngôn ngữ là cơ sở của các thuật toán lập luận theo nhánh, lập luận theo không gian trạng thái và độ phức tạp tính toán. Sự biến đổi của không gian trạng thái và tính hội tụ của nó cũng phụ thuộc vào tính chất của dàn ELL. 3. Phương pháp nghiên cứu Luận án tập trung vào hai phương pháp nghiên cứu chính: • Phương pháp nghiên cứu tài liệu, phân tích, tổng hợp và hệ thống hóa: Thu 6
thập tài liệu về các công trình khoa học đã nghiên cứu và công bố trên các bài báo hội nghị trong nước và quốc tế về cấu trúc đồ thị FCM, phân tích những ưu nhược điểm trong việc mô hình, lập luận và kiểm chứng của đồ thị FCM. Đề xuất cấu trúc đồ thị LCM là một cấu trúc đồ thị mờ, việc mô hình, lập luận và kiểm chứng chỉ thực hiện hoàn toàn trên biến ngôn ngữ. • Phương pháp logic hình thức: Phương pháp này nhằm đặc tả các đối tượng nghiên cứu: dàn ELL, các phép toán trên dàn và quan hệ thứ tự trên dàn. Đồ thị LCM được hình thức hóa thành các tập đỉnh, cạnh và quan hệ giữa các đỉnh. Các tính chất tổ hợp trên đồ thị LCM được phát biểu thành các biểu thức, công thức, tính chất và được chứng minh. Các thuật toán lập luận theo nhánh và theo trạng thái được đánh giá chính xác về độ phức tạp. Tính hội tụ của trạng thái của đồ thị được phát biểu và chứng minh chặt chẽ, logic về mặt toán học. 4. Mục tiêu và nội dung của luận án Với phương pháp nghiên cứu trên về mô hình hóa, lập luận và kiểm chứng trên đồ thị mờ của các nghiên cứu trong và ngoài nước, luận án đưa ra các mục tiêu nghiên cứu chính như sau: • Nghiên cứu dàn mở rộng cùng các phép toán trên miền trị ngôn ngữ. • Nghiên cứu phương pháp biểu diễn, các tính chất của đồ thị LCM sử dụng ĐSGT. • Nghiên cứu các thuật toán lập luận trên đồ thị LCM. • Nghiên cứu tính chất của không gian trạng thái được sinh bởi đồ thị LCM. Để hiện thực các mục tiêu nghiên cứu trên, luận án tập trung nghiên cứu các nội dung chính như sau: 1. Nghiên cứu cấu trúc toán học trừu tượng trên miền trị ngôn ngữ là dàn mở rộng ELL. Các phép toán trên dàn là cơ sở cho các tính toán trên các vector và ma trận các giá trị ngôn ngữ. Các phép toán này cũng là cơ sở cho các lập luận trên đồ thị LCM. 2. Nghiên cứu cấu trúc và các tính chất tổ hợp của đồ thị LCM. 3. Nghiên cứu hai phương pháp lập luận mờ trên đồ thị, bao gồm lập luận tĩnh theo nhánh và lập luận động trên không gian trạng thái. 4. Nghiên cứu độ phức tạp tính toán và tính hội tụ của trạng thái. 7
5. Ý nghĩa khoa học và thực tiễn Ý nghĩa khoa học Những đóng góp chính của luận án về mặt khoa học: • Đề xuất một cấu trúc dàn đặc biệt trên miền trị ngôn ngữ là dàn ELL . Các phép toán trên dàn là cơ sở cho các tính toán trên các vector và ma trận • Xây dựng một cấu trúc đồ thị nhận thức LCM trên miền trị ngôn ngữ và các tính chất tổ hợp của đồ thị. • Xây dựng các thuật toán lập luận trên đồ thị nhận thức trên miền giá trị ngôn ngữ. • Luận án đưa ra và chứng minh các tính chất về sự hội tụ trạng thái của đồ thị. Ý nghĩa thực tiễn Với các tính chất toán học được chứng minh một cách chặt chẽ và logic theo phương pháp hình thức, luận án có ý nghĩa thực tiễn như sau: • Luận án cung cấp một nền tảng lý thuyết toán học về dàn mở rộng trên miền trị ngôn ngữ. • Khẳng định ưu điểm của ĐSGT trong biểu diễn và lập luận trên đồ thị nhận thức trong việc tính toán trực tiếp trên các từ • Phương pháp lập luận tĩnh cho phép lập luận theo đường đi của đồ thị. Trong lập luận động, vector trạng thái luôn luôn hội tụ về một vector cố định. 6. Bố cục của luận án Về bố cục của luận án, ngoài phần mở đầu và phần kết luận, nội dung chính được chia thành 3 chương: Chương 1 - Cấu trúc dàn mở rộng trên miền trị ngôn ngữ sử dụng đại số gia tử; Chương 2 - Cấu trúc đồ thị nhận thức trên miền trị ngôn ngữ; Chương 3 - Phương pháp lập luận trên đồ thị nhận thức. Phần mở đầu và tài liệu tham khảo. Các chương có nội dung chính như sau: • Chương 1: Tổng quan các kiến thức cơ bản đã biết làm cơ sở cho các nghiên cứu trong các chương sau. Đầu tiên là các khái niệm về tập mờ, về ĐSGT, các nghiên cứu về đồ thị FCM. 8