Luận án Tiến sĩ Toán học: Nghiên cứu ngữ nghĩa tính toán của từ ngôn ngữ và ứng dụng vào việc xây dựng hệ mờ tối ưu dựa trên luật

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

Thêm vào BST

Báo xấu

76
lượt xem 10
download

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

Luận án gồm các chương: Chương 1 – Một số kiến thức cơ sở; chương 2 – Phát triển các thuật toán xây dựng các LRBS giải bài toán phân lớp, hồi quy; chương 3 – Tính giải nghĩa được của các khung nhận thức ngôn ngữ và biểu diễn ngữ nghĩa tính toán của chúng.

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ĩ Toán học: Nghiên cứu ngữ nghĩa tính toán của từ ngôn ngữ và ứng dụng vào việc xây dựng hệ mờ tối ưu dựa trên luật

BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 49 HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ r HOÀNG VĂN THÔNG NGHIÊN CỨU NGỮ NGHĨA TÍNH TOÁN CỦA TỪ NGÔN NGỮ VÀ ỨNG DỤNG VÀO VIỆC XÂY DỰNG HỆ MỜ TỐI ƯU DỰA TRÊN LUẬT Chuyên ngành: CƠ SỞ TOÁN HỌC CHO TIN HỌC Mã số: 62.46.01.10 LUẬN ÁN TIẾN SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: 1. PGS.TSKH. NGUYỄN CÁT HỒ 2. PGS.TS. NGUYỄN VĂN LONG HÀ NỘI - 2016 1
LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Các kết quả được viết chung với các tác giả khác đều được sự đồng ý của đồng tác giả trước khi đưa vào luận án. Các kết quả trong luận án là trung thực và chưa từng được công bố trong bất kỳ công trình nào khác. Tác giả Hoàng Văn Thông i
LỜI CẢM ƠN Luận án được hoàn thành dưới sự hướng dẫn tận tình của PGS.TSKH. Nguyễn Cát Hồ và PGS.TS Nguyễn Văn Long. Lời đầu tiên, tác giả xin bày tỏ lòng kính trọng và biết ơn sâu sắc nhất tới hai thầy. Tác giả xin gửi lời cảm ơn chân thành đến Ban lãnh đạo Học viện Khoa học và Công nghệ, Viện Công nghệ thông tin, Khoa công nghệ thông tin và truyền thông, Phòng Các hệ chuyên gia và tính toán mềm đã tạo điều kiện thuận lợi trong quá trình học tập, nghiên cứu và hoàn thành luận án. Xin cảm ơn Ban giám hiệu Trường Đại học Giao thông Vận tải, Ban chủ nhiệm khoa Công nghệ thông, Bộ môn Khoa học máy tính đã quan tâm giúp đỡ, tạo điều kiện tốt nhất trong công việc để tác giả có thời gian tập trung nghiên cứu. Cảm ơn các anh chị Phòng Các hệ chuyên gia và tính toán mềm - Viện Công nghệ thông tin, các đồng nghiệp thuộc Khoa Công nghệ thông tin – Trường Đại học Giao thông Vận tải, các anh chị trong nhóm nghiên cứu đại số gia tử đã khích lệ, động viên, trao đổi những kiến thức và kinh nghiệm trong quá trình hoàn thành luận án. Cuối cùng, tác giả xin chân thành cảm ơn Bố mẹ, các anh chị em đặc biệt là vợ và các con, những người luôn dành cho tác giả những tình cảm và chia sẻ những lúc khó khăn trong cuộc sống, luôn động viên giúp đỡ tác giả trong quá trình nghiên cứu. Luận án này là món quà tinh thần mà tác giả trân trọng gửi tặng đến các thành viên trong gia đình. 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 BẢNG BIỂU .................................................................... viii DANH MỤC CÁC HÌNH VẼ ........................................................................... x MỞ ĐẦU ....................................................................................................... 1 CHƯƠNG 1. MỘT SỐ KIẾN THỨC CƠ SỞ ................................................. 9 1.1. Một số kiến thức cơ bản về lý thuyết tập mờ ......................................... 9 1.1.1. Định nghĩa tập mờ ............................................................................ 9 1.1.2. Xây dựng hàm thuộc ....................................................................... 10 1.1.3. Biến ngôn ngữ ............................................................................... 10 1.1.4. Phân hoạch mờ............................................................................ 11 1.2. Một số kiến thức về đại số gia tử ........................................................ 12 1.2.1. Khái niệm đại số gia tử ................................................................ 13 1.2.2. Một số tính chất của đại số gia tử tuyến tính ................................. 14 1.2.3. Độ đo tính mờ của các giá trị ngôn ngữ ........................................ 14 1.2.4. Định lượng ngữ nghĩa của giá trị ngôn ngữ ................................... 16 1.2.5. Khoảng tính mờ .......................................................................... 18 1.2.6. Hệ khoảng tương tự ..................................................................... 19 1.3. Hệ mờ dựa trên luật............................................................................... 20 1.3.1. Các thành phần của hệ mờ ........................................................... 20 1.3.2. Các mục tiêu khi xây dựng FRBS ................................................ 23 iii
1.4. Kết luận chương 1.............................................................................. 26 CHƯƠNG 2. PHÁT TRIỂN CÁC THUẬT TOÁN XÂY DỰNG CÁC LRBS GIẢI BÀI TOÁN PHÂN LỚP, HỒI QUY .................................................... 28 2.1 Phát triển thuật toán giải bài toán phân lớp........................................... 28 2.1.1. Bài toán phân lớp và các phương pháp giải ................................... 28 2.1.2 Thuật toán OPHA-SGERD ........................................................... 32 2.1.3. Kết quả thử nghiệm ..................................................................... 43 2.2. Phát triển thuật toán giải bài toán hồi quy ........................................... 47 2.2.1. Bài toán hồi quy và phương pháp giải .......................................... 47 2.2.2. Thuật toán HA-PAES-SG ............................................................ 50 2.2.3. Thuật toán HA-PAES-MG ........................................................... 65 2.3. Kết luận chương 2.............................................................................. 71 CHƯƠNG 3. TÍNH GIẢI NGHĨA ĐƯỢC CỦA CÁC KHUNG NHẬN THỨC NGÔN NGỮ VÀ BIỂU DIỄN NGỮ NGHĨA TÍNH TOÁN CỦA CHÚNG ... 74 3.1. Vấn đề tính giải nghĩa được của FRBS ............................................... 74 3.2. Khái niệm khung nhận thức và khung nhận thức ngôn ngữ .................. 75 3.2.1. Khung nhận thức và tính giải nghĩa được của nó ........................... 75 3.2.2. Khung nhận thức ngôn ngữ .......................................................... 77 3.3. Đề xuất các ràng buộc tính giải nghĩa được trên các LFoC................... 80 3.3.1. Ràng buộc ngữ nghĩa vốn có của từ.............................................. 80 3.3.2. Ràng buộc phương pháp xác định ngữ nghĩa tính toán của từ ........ 82 3.3.3. Ràng buộc ngữ nghĩa khoảng của từ ............................................. 83 3.3.4. Ràng buộc ngữ nghĩa thứ tự của từ ............................................... 85 3.4. Biểu diễn ngữ nghĩa tính toán dựa trên tập mờ của các từ trong LFoC .. 87 iv
3.4.1. Biểu diễn đơn thể hạt của LFoC ................................................... 88 3.4.2. Biểu diễn đa thể hạt của LFoC ..................................................... 91 3.5. Phát triển thuật toán xây dựng LRBS giải bài toán hồi quy .................. 97 3.5.1. Thiết kế ngữ nghĩa tính toán (phân hoạch mờ) .............................. 97 3.5.2. Mã hóa các cá thể ........................................................................ 98 3.5.3. Thuật toán tiến hóa ...................................................................... 99 3.5.4. Kết quả thử nghiệm ..................................................................... 99 3.6. Kết luận chương 3.............................................................................105 KẾT LUẬN CỦA LUẬN ÁN .....................................................................107 CÁC CÔNG TRÌNH KHOA HỌC CỦA TÁC GIẢ .....................................111 LIÊN QUAN ĐẾN LUẬN ÁN ....................................................................111 TÀI LIỆU THAM KHẢO ...........................................................................112 PHỤ LỤC ..................................................................................................118 v
DANH MỤC CÁC KÝ HIỆU VÀ TỪ VIẾT TẮT Các ký hiệu: AX Đại số gia tử tuyến tính AX * Đại số gia tử tuyến tính đầy đủ  (h) Độ đo tính mờ của gia tử h fm(x) Độ đo tính mờ của hạng từ x 𝔳𝔛 Hàm định lượng ngữ nghĩa của từ ngôn ngữ của biến 𝔛  A(x) Hàm xác định độ thuộc của giá trị x vào tập mờ A l(x) Độ dài của từ ngôn ngữ x fm Khoảng tính mờ của giá trị ngôn ngữ Xk Tập các hạng từ có độ dài đúng bằng k X(k) Tập tất cả các hạng từ có độ dài  k Ik Hệ khoảng tính mờ mức k của các giá trị ngôn ngữ I(k) Hệ khoảng tính mờ từ mức 1 đến mức k của các giá trị ngôn ngữ Comp Độ phức tạp của hệ luật MSE Sai số bình phương trung bình Các từ viết tắt: DB Database ĐSGT Đại số gia tử FoC Frame of Cognition FRBS Fuzzy Rule-based System FRB Fuzzy Rule Base RB Rule Base vi
HA-PAES-MG Hedge Algebra - Pareto Archive Evolution Strategy – Multi Granularity HA-PAES-SG Hedge Algebra - Pareto Archive Evolution Strategy – Single Granularity KB Knowledge Base LRBS Linguistic Rule-based System LRB Linguistic Rule Base LFoC Linguistic Frame of Cognition MF Membership Function M-PAES Modify-Pareto Archive Evolution Strategy PAES Pareto Archive Evolution Strategy PAES(I) Pareto Archive Evolution Strategy (Interpretability) PAES(C) Pareto Archive Evolution Strategy (Complexity) PSO Particle Swarm Optimization SGERD Steady-State Genetic Algorithm for Extracting Fuzzy Classification Rules From Data SPEA Strength Pareto Evolutionary Algorithm SQM Semantically Quantifying Mapping vii
DANH MỤC CÁC BẢNG BIỂU Bảng 2.1 Các tập dữ liệu dùng để thử nghiệm ............................................... 45 Bảng 2.2 Các giá trị của Nrmax trong quá trình tối ưu hệ luật .......................... 45 Bảng 2.3 So sánh kết quả thử nghiệm thuật toán OPHA-SGERD và thuật toán SGERD với tiêu chuẩn (2.3)......................................................................... 45 Bảng 2.4 So sánh kết quả thử nghiệm thuật toán OPHA-SGERD và thuật toán SGERD với tiêu chuẩn (2.4)......................................................................... 45 Bảng 2.5 So sánh kết quả thử nghiệm thuật toán OPHA-SGERD với tiêu chuẩn (2.5) và thuật toán SGERD với tiêu chuẩn (2.4) ............................................ 46 Bảng 2.6 So sánh kết quả thử nghiệm thuật toán OPHA-SGERD với ba tiểu chuẩn (2.3), (2.4), (2.5) .......................................................................................... 46 Bảng 2.7 Các tập dữ liệu được sử dụng thử nghiệm trong [14] ...................... 62 Bảng 2.8 Các tham số thử nghiệm ................................................................ 62 Bảng 2.9 So sánh kết quả thử nghiệm thuật toán HA-PAES-SG với các thuật toán (2+2)M-PAES(I) và (2+2)M-PAES(C) trong [14] tại điểm FIRST................. 63 Bảng 2.10 Các tập dữ liệu được sử dụng thử nghiệm trong [10]..................... 68 Bảng 2.11 Kết quả trung bình đạt được bởi HA-PAES-MG (MG), HA-PAES-SG (SG) và PAESKB (KB) tại điểm FIRST ......................................................... 69 Bảng 2.12 So sánh độ phức tạp (Comp) của hệ luật bằng phương pháp kiểm định giả thuyết Wilcoxon-test với mức α = 0.05 tại ba điểm đại diện ..................... 71 Bảng 2.13 So sánh sai số bình phương trung bình trên tập kiểm tra (MSEts) bằng phương pháp kiểm định giả thuyết Wilcoxon-test với mức α = 0.05 tại ba điểm đại diện ....................................................................................................... 71 Bảng 3.1 Các giá trị 𝖛𝖃 của các từ của X(2)................................................... 89 Bảng 3.2 Kết quả trung bình đạt được bởi HA-PAES-MG-Kmax và HA-PAES- SG-Kmax tại điểm FIRST.............................................................................100 Bảng 3.3 So sánh độ phức tạp (Comp) của hệ luật bằng phương pháp kiểm định giả thuyết Wilcoxon-test với mức α = 0.05 tại ba điểm đại diện ....................101 viii
Bảng 3.4 So sánh MSEts trên tập kiểm tra bằng phương pháp kiểm định giả thuyết Wilcoxon-test với mức α = 0.05 tại ba điểm đại diện ....................................101 Bảng 3.5 Kết quả trung bình đạt được bởi HA-PAES-MG-Kmax (Kmax), HA- PAES-MG-Kopt (Kopt ) và PAESKB (KB) tại điểm FIRST ...............................103 Bảng 3.6 So sánh độ phức tạp của hệ luật (Comp) bằng phương pháp kiểm định giả thuyết Wilcoxon-test với mức α = 0.05 tại ba điểm đại diện ....................105 Bảng 3.7 So sánh MSEts trên tập kiểm tra bằng phương pháp kiểm định giả thuyết Wilcoxon-test với mức α = 0.05 tại ba điểm đại diện ...................................105 Bảng A.1 So sánh kết quả thử nghiệm thuật toán HA-PAES-SG với các thuật toán (2+2)M-PAES(I) và (2+2)M-PAES(C) trong [14] tại điểm MEDIAN ....118 Bảng A.2 So sánh kết quả thử nghiệm thuật toán HA-PAES-SG với các thuật toán (2+2)M-PAES(I) và (2+2)M-PAES(C) trong [14] tại điểm LAST .........118 Bảng A.3 Kết quả trung bình đạt được bởi HA-PAES-MG (MG), HA-PAES-SG (SG) và PAES KB (KB) tại điểm MEDIAN....................................................119 Bảng A.4 Kết quả trung bình đạt được bởi HA-PAES-MG (MG), HAPAES-SG (SG) và PAES KB (KB) tại điểm LAST.........................................................119 Bảng A.5 Kết quả trung bình đạt được bởi HA-PAES-MG-Kmax và HA-PAES- SG-Kmax tại điểm MEDIAN .........................................................................119 Bảng A.6 Kết quả trung bình đạt được bởi HA-PAES-MG-Kmax và HA-PAES- SG-Kmax tại điểm LAST ..............................................................................120 Bảng A.7 Kết quả trung bình đạt được bởi HA-PAES-MG-Kmax (Kmax), HA- PAES-MG-Kopt (Kopt ) và PAESKB (KB) tại điểm MEDIAN ..........................120 Bảng A.8 Kết quả trung bình đạt được bởi HA-PAES-MG-Kmax (Kmax), HA- PAES-MG-Kopt (Kopt ) và PAESKB (KB) tại điểm LAST ................................120 ix
DANH MỤC CÁC HÌNH VẼ Hình 1.1. Một hàm thuộc dạng hình thang của tập mờ A .................................... 10 Hình 1.2. Một cấu trúc phân hoạch mờ dạng đơn thể hạt ............................... 12 Hình 1.3. Một cấu trúc phân hoạch mờ dạng đa thể hạt ................................. 12 Hình 1.4. Độ đo tính mờ của biến TRUTH ................................................... 16 Hình 1.5. Khoảng tính mờ của các hạng từ của biến TRUTH ........................ 19 Hình 1.6. Minh họa hệ khoảng tương tự mức 2............................................. 19 Hình 1.7. Phân hoạch mờ đều và phân hoạch mờ sau khi điều chỉnh tập mờ .. 26 Hình 2.1. Một phân hoạch mờ đơn thể hạt được xây dựng dựa trên ĐSGT..... 33 Hình 2.2. Mô tả không gian quyết định và không gian phủ của luật ............... 34 Hình 2.3. Cấu trúc mã hóa một cá thể........................................................... 55 Hình 2.4. Mặt xấp xỉ tối ưu Pareto trung bình theo độ chính xác MSE và độ phức tạp Comp..................................................................................................... 64 Hình 2.5. Một thiết kế phân hoạch mờ đa thể hạt được đề xuất trong [50] với độ dài tối đa của từ là 2. .................................................................................... 66 Hình 2.6. Một thiết kế phân hoạch mờ đa thể hạt được đề xuất mới với độ dài tối đa của từ là 2. .............................................................................................. 66 Hình 3.1 Một phương pháp gán ngữ nghĩa của khung nhận thức ................... 76 Hình 3.2 Một biểu diễn đơn thể hạt của LFoC được tạo thành từ tập từ X(2) của một thuộc tính của bài toán ELE2 được xây dựng từ các giá trị tham số tính mờ  (L)=0.4020657, fm(c) = 0.6768686............................................................ 89 Hình 3.3 Một biểu diễn đa thể hạt của LFoC được tạo thành từ tập từ X(2) của một thuộc tính của bài toán ELE2 được xây dựng từ các giá trị tham số tính mờ (L)=0.4020657, fm(c) =0.6768686 ............................................................ 93 Hình 3.4 Cấu trúc mã hóa một cá thể ........................................................... 99 Hình 3.5 Đồ thị biểu diễn ba điểm đại diện FIRST, MEDIAN và LAST của mặt Pareto trung bình ........................................................................................104 x
MỞ ĐẦU Chúng ta biết rằng con người nhận biết thế giới thực, giao tiếp với nhau, tư duy lập luận để làm các quyết định dựa trên công cụ nền tảng là ngôn ngữ tự nhiên và cơ sở tri thức được biểu diễn dưới dạng mệnh đề ngôn ngữ. Các mệnh đề này được hình thành trong quá trình tồn tại và phát triển của con người. Lịch sử phát triển của xã hội loài người cho thấy, ngôn ngữ của con người là một công cụ đủ để nhận biết thế giới thực, làm quyết định và giải quyết hiệu quả các vấn đề phát sinh trong cuộc sống hàng ngày. Do thế giới thực là vô hạn trong khi ngôn ngữ tự nhiên của con người lại hữu hạn, vì vậy các từ ngôn ngữ mà con người dùng để nhận thức thế giới thực thường có ngữ nghĩa mờ, không chắc chắn và có tính mơ hồ. Trong khoảng ba thập niên trở lại đây khoa học và công nghệ phát triển rất mạnh mẽ, đã sản sinh ra nhiều thiết bị máy móc hỗ trợ cho con người trong mọi lĩnh vực của cuộc sống. Trong một số lĩnh vực, chúng ta mong muốn máy móc có thể hành xử như con người, thay thế con người làm những công việc đòi hỏi phải có khả năng lập luận hoặc đưa ra những gợi ý tin cậy hỗ trợ cho con người trong quá trình làm quyết định. Một đặc trưng nổi bật của con người là khả năng suy luận trên cơ sở tri thức được hình thành từ cuộc sống và biểu thị bằng ngôn ngữ tự nhiên. Do đó, để máy móc có thể hành xử như con người thì nó phải được trang bị cơ sở tri thức và khả năng lập luận trên ngôn ngữ. Đây là một vấn đề rất phức tạp, vì vậy để giải quyết yêu cầu này các nhà khoa học đã và đang nghiên cứu cả về lý thuyết lẫn ứng dụng để đưa ra các phương pháp nhằm mô phỏng khả năng lập luận của con người trên các thiết bị máy móc. Do đặc trưng của ngôn ngữ là ngữ nghĩa và nó mang tính mờ, vì vậy nhiệm vụ đầu tiên cần phải giải quyết đó là làm thế nào để hình thức hóa toán học các vấn đề ngữ nghĩa và xử lý ngữ nghĩa ngôn ngữ mà con người thao tác trong cuộc sống. Trước những yêu cầu đặt ra đó, năm 1965 Lotfi A. Zadeh là người đầu tiên đặt nền móng trong lĩnh vực này trong [63]. Zadeh đã đưa ra khái niệm tập mờ, ý tưởng của ông là giả thiết U là một tập các phần tử, một tập mờ A trong U được biểu diễn bằng một hàm từ tập U vào đoạn [0, 1] biểu thị cấp độ thuộc của phần tử trong U vào tập A và hàm này còn gọi là tập mờ trên U. Trong 1
[64] Zadeh đưa ra khái niệm biến ngôn ngữ, là biến mà giá trị của nó là các từ ngôn ngữ, và ngữ nghĩa của mỗi từ được biểu diễn bằng một tập mờ. Vì vậy, các từ của biến ngôn ngữ vốn không tính toán được trở thành một đối tượng toán học hoàn toàn có thể tính toán được. Dựa trên lý thuyết tập mờ, hệ mờ dựa trên luật (Fuzzy Rule Based System - FRBS) đã được phát triển và trở thành một trong những công cụ mô phỏng gần gũi phương pháp suy luận và làm quyết định của con người nhất. FRBS đã gặt hái được nhiều thành công trong giải quyết các bài toán thực tiễn như bài toán điều khiển của Mamdani [38], Oliveira [53, 54], Vukadinović [60], Wang [61]; bài toán phân lớp Nguyễn Cát Hồ [2- 4], Dương Thăng Long [6, 7], Cordón [17, 18], Fazzolari [23], Fernandez [24], Gacto [25], García [27], Ishibuchi [28-34], López [37], Mansoori [39], Nauck [44], Nguyễn Cát Hồ [[50, 52], Pulkkinen [55], Trawinski [59]; bài toán hồi quy của Alcalá [8-10], Antonelli [12-15], Cococcioni [16], Márquez [40], Pulkkinen [56], Rodríguez-Fdez [57]. FRBS được phát triển trên nền tảng lý thuyết tập mờ và logic mờ, với thành phần cơ bản là các luật mờ dạng if-then là một trong những phương tiện khá tốt mô phỏng khả năng lập luận của con người trong giải quyết các vấn đề phức tạp với những thông tin không chắc chắn, có tính mơ hồ. Các FRBS thường được xây dựng tự động từ các sự kiện trong thế giới thực hoặc trên cơ sở tri thức của các chuyên gia, hoặc kết hợp cả hai phương pháp. Khi xây dựng các FRBS, chúng ta cần đạt được hai mục tiêu là độ chính xác (accuracy) và tính giải nghĩa được (interpretability). Đây là hai mục tiêu xung đột nhau, làm tăng mục tiêu này thì phải giảm mục tiêu kia. Vì vậy, khi xây dựng các FRBS các phương pháp được đề xuất luôn phải hướng tới đảm bảo sự cân bằng (tradeoff) giữa hai mục tiêu này. Trong những năm đầu ứng dụng FRBS, người ta chủ yếu quan tâm đến độ chính xác. Mục tiêu tính giải nghĩa được của FRBS được quan tâm nhiều hơn khi FRBS được ứng dụng vào các lĩnh vực mà ở đó con người làm trung tâm (human-centric), ví dụ: y tế, tâm lý học, kinh tế, ngôn ngữ học [42]. Trong những lĩnh vực này các FRBS được xem như là các hộp xám (gray-boxes). Và ở đây đặt ra yêu cầu là các FRBS khi được ứng dụng vào thực tế thì người dùng có thể kiểm tra và hiểu được tất cả các thành phần của nó [11]. Vì vậy, trong những năm gần đây vấn đề tính giải 2
nghĩa được của FRBS trở thành một chủ đề “nóng” được nhiều nhà khoa học tập trung nghiên cứu. Ví dụ như Alonso và cộng sự [11], Antonelli và các cộng sự [14], Cordon và các cộng sự [19], Gacto và cộng sự [26], Ishibuchi và Nojima [33], Mencar và các cộng sự [41, 42], Nauck [44], de Oliveira [54], Pulkkinen và Koivisto [56], Zhou và Gan [67]. Tính giải nghĩa được của FRBS liên quan đến nhiều yếu tố khác nhau, hiện tại chúng ta vẫn chưa có một tiêu chuẩn toán học để mô tả chính xác, và còn nhiều quan điểm khác nhau, ngay cả các thuật ngữ để chỉ tính giải nghĩa được cũng chưa thống nhất. Ví dụ như: tính dễ hiểu (intelligibility), tính trong suốt (transparency), tính dễ đọc (readability), …, các thuật ngữ này được sử dụng đồng nghĩa và thay thế cho nhau [19]. Trong [26] Gacto cho rằng hiện tại có hai hướng tiếp cận chính về tính giải nghĩa được của FRBS. Hướng thứ nhất dựa trên độ phức tạp (Complexity-based Interpretability), hướng này tập trung vào việc làm giảm độ phức tạp của FRBS, thường sử dụng các độ đo như: số luật, số biến, độ dài của luật, số từ sử dụng cho một biến,…. càng ít càng tốt. Hướng thứ hai dựa trên ngữ nghĩa (Semantics-based Interpretability), hướng này tập trung vào đảm bảo tính toàn vẹn ngữ nghĩa của các nhãn ngôn ngữ, được biểu diễn bằng các tập mờ và ngữ nghĩa của luật. Theo các hướng tiếp cận này, để đánh giá tính giải nghĩa được của FRBS một số nghiên cứu dựa trên lý thuyết tập mờ đã đề xuất các ràng buộc tính giải nghĩa được của FRBS như Gacto [26], Mencar [41, 42]. Các FRBS thỏa mãn càng nhiều ràng buộc thì tính giải nghĩa được càng cao, hoặc phát triển các chỉ số đánh giá tính giải nghĩa được của FRBS được kết hợp từ một số yếu tố liên quan Alonso [11], Antonelli [14], Nauck [44], Oliveira [53]. Theo hướng tiếp cận tập mờ thiếu một phương pháp hình thức đầy đủ để xác định ngữ nghĩa tính toán của từ với ngữ nghĩa vốn của nó. Do đó các nghiên cứu này phải đưa ra nhiều ràng buộc (trong [41] Mencar đưa ra 37 ràng buộc), và các ràng buộc này đều dựa trên trực quan của người thiết kế. Theo chúng tôi một FRBS giải nghĩa được cao thì ngữ nghĩa tính toán của từ ngôn ngữ sử dụng trong FRBS phải được xác định dựa trên ngữ nghĩa vốn có của nó trong tự nhiên. Vì vậy ngữ nghĩa tính toán của từ là yếu tố quan trọng để đảm bảo tính giải nghĩa được của FRBS. Do đó cần phải tìm kiếm một hướng tiếp cận mới cho vấn đề tính giải nghĩa được của FRBS mà ở đó ngữ nghĩa tính toán của từ được xác định dựa trên ngữ nghĩa vốn có của nó 3
bằng một phương pháp hình thức đầy đủ. Vấn đề xây dựng FRBS, hiện tại rất nhiều nghiên cứu tập trung tìm kiếm các phương pháp xây dựng FRBS cho bài toán phân lớp, tuy nhiên bài toán hồi quy chưa có nhiều nghiên cứu. Các phương pháp xây dựng FRBS phải giải quyết ba vấn đề chính: thiết kế phân hoạch mờ (ngữ nghĩa tính toán của từ), sinh tập các luật mờ ứng cử, tìm kiếm hệ luật mờ tối ưu. Hướng tiếp cận dựa trên lý thuyết tập mờ thường sử dụng các phân hoạch mờ đều với số tập mờ cố định được gán nhãn để phân hoạch mờ miền tham chiếu của biến như trong Cordón [17, 18], Fazzolari [23], Ishibuchi [28-34], Mansoori [39], Trawinski [59]. Việc sử dụng cùng một phân hoạch mờ với các tập mờ cố định trước cho các tập dữ liệu khác nhau là không phù hợp với thực tế, nó làm giảm tính chính xác của hệ luật. Vì trong thực tế ngữ nghĩa của các từ phụ thuộc vào từng ngữ cảnh, tức là phụ thuộc vào từng tập dữ liệu cụ thể. Vì vậy, một yêu cầu tự nhiên là phải phát triển các thuật toán cho phép điều chỉnh ngữ nghĩa tính toán của từ (tập mờ), chẳng hạn như trong Acalá [10], Antonelli [13, 14], Cordón [17], Gacto [25], Nauck [44], Pulkkinen [55]. Hướng tiếp cận dựa trên tập mờ thiếu một phương pháp hình thức toán học đầy đủ để xác định ngữ nghĩa tính toán của từ từ ngữ nghĩa vốn có của chúng, vì vậy để thực hiện điều chỉnh các tập mờ thì thuật toán phải tìm kiếm trong không gian rất lớn. Chẳng hạn với bài toán có n chiều và sử dụng T từ ngôn ngữ cho mỗi biến, trong [10] Acalá sử dụng bộ 2 (2-tuples) để biểu diễn các tập mờ thì không gian tìm kiếm tham số là T*(n+1) chiều, (3T5). Trong [14] Antonelli sử dụng hàm tuyến đổi tuyến từng khúc (piecewise linear transformation) để thực hiện điều chỉnh tham số, khi đó không gian tìm kiếm là (T-2)(n+1) chiều, (5T7). Trong [56] Pulkkinen biểu diễn tập mờ bằng bộ 3 tham số khi đó không gian tìm kiếm tham số là 3Tn chiều (2T4). Để giảm không gian tìm kiếm, các phương pháp dựa trên lý thuyết tập mờ phải đưa ra một số ràng buộc trên tính giải nghĩa được của FRBS được định nghĩa dựa trên độ phức tạp. Chẳng hạn như yêu cầu giới hạn số tập mờ có thể sử dụng T trên mỗi biến không quá 72 Miller [43]. Theo chúng tôi, giới hạn này là không phù hợp, vì trên mỗi biến con người có thể sử dụng nhiều từ ngôn ngữ hơn giới hạn này (khẳng định này được chứng tỏ trong chương 3). Và, với phương pháp thiết kế 4
phân hoạch như vậy thì các từ ngôn ngữ sử dụng trong FRBS chỉ là các nhãn ngôn ngữ. Để khắc phục nhược điểm này Nguyễn Cát Hồ và các cộng sự trong [2-4, 50, 52] đã ứng dụng ĐSGT để sinh từ ngôn ngữ, ở đây xem tập mờ chỉ là một phương pháp biểu diễn ngữ nghĩa tính toán của từ. Tập mờ được xây dựng dựa trên ngữ nghĩa định lượng được xác định bằng ĐSGT. Vì vậy, việc điều chỉnh ngữ nghĩa tính toán của từ ngôn ngữ được thực hiện rất dễ dàng chỉ bằng việc điều chỉnh các tham số tính mờ của ĐSGT. Do đó, không gian tìm kiếm giảm đi nhiều và nó không phụ thuộc vào số từ sử dụng cho mỗi biến. Các từ ngôn ngữ sử dụng trong FRBS là từ ngôn ngữ tự nhiên, khi đó chúng tôi gọi là LRBS thay vì FRBS. Mặc dù phương pháp thiết kế ngữ nghĩa tính toán của từ dựa trên ĐSGT tử mang một số lợi ích so với pháp dựa trên tập mờ. Tuy nhiên nghĩa tính toán của từ lại không bảo toàn được tính khái quát và tính đặc tả của từ, đây là một tính chất quan trọng của từ ngôn ngữ. Vì vậy, chúng ta cần phải tìm kiếm một phương pháp thiết kế mới bảo toàn được những tính chất này. Vấn đề sinh luật ứng cử, các phương pháp tiếp cận dựa trên lý thuyết tập mờ thường sinh luật bằng cách tổ hợp tất cả các giá trị ngôn ngữ sử dụng cho các biến như trong Acalá [10], Antonelli [12-15], Cordón [17, 18], Fazzolari [23], Gacto [25], Ishibuchi [28-34], López [37]. Nhược điểm của hướng tiếp cận này là khi tập dữ liệu có nhiều thuộc tính thì số luật sinh ra cỡ hàm mũ theo số thuộc tính. Một số đề xuất sinh luật từ cây quyết định (decision tree) như trong Pulkkinen [55, 56]. Phương pháp này đã làm giảm đáng kể số luật phải xem xét nhờ vào các kỹ thuật cắt tỉa trên cây, nhưng nếu sử dụng kỹ thuật sinh luật này trong các thuật toán cho phép tối ưu tham số tập mờ thì độ phức tạp thuật toán sẽ rất cao vì mỗi lần điều chỉnh tham số tập mờ ta lại phải xây dựng lại cây quyết định. Hướng tiếp cận theo lý thuyết ĐSGT, trong [2-4, 50, 52] Nguyễn Cát Hồ và cộng sự đề xuất một phương pháp sinh luật từ mẫu dữ liệu. Theo đó, mỗi mẫu dữ liệu sinh ra một luật có độ dài bằng số thuộc tính của tập mẫu dữ liệu (n), từ các luật này sinh các luật có độ dài nhỏ hơn n. Với phương pháp sinh luật ứng cử này thì số luật tối đa phải xem xét giảm đi đáng kể so với phương pháp sinh luật tổ hợp. Đây là phương pháp sinh luật khá tốt, luận án áp dụng phương pháp sinh luật này để phát triển các thuật toán giải bài toán hồi quy. 5
Vấn đề tìm kiếm FRBS tối ưu, đây là bài toán đa mục tiêu, do đó hầu hết các phương pháp đều sử dụng giải thuật tiến hóa để giải quyết vấn đề này như giải thuật GA, PAES, M-PAES, SPEA, SPEA2, NSGA-I, NSGA-2, SGERD, PSO, ... Từ những phân tích ở trên chúng tôi nhận thấy rằng ứng dụng ĐSGT vào việc phát triển các thuật toán xây dựng LRBS giải bài toán phân lớp đã khắc phục được một số hạn chế của hướng tiếp cận dựa trên lý thuyết tập mờ. Tuy nhiên, vẫn còn một số hạn chế như phương pháp thiết kế ngữ nghĩa tính toán được đề xuất không bảo toàn được tính khái quát và tính đặc tả của từ, phương pháp sinh luật cho bài toán phân lớp vẫn còn lớn. Vì vậy, chúng ta cần nghiên cứu phát triển các thuật toán giải bài toán phân lớp hiệu quả hơn (chẳng han sinh ra số luật ứng cử ít hơn). Nghiên cứu ứng dụng ĐSGT vào giải các bài hồi quy, đây là bài toán phức tạp hơn nhiều bài toán phân lớp, hiện chưa có nghiên cứu nào ứng dụng ĐSGT để giải nó. Bên cạnh đó, vấn đề tính giải nghĩa được của LRBS chưa được quan tâm nghiên cứu trong hướng tiếp cận này. Do đó, luận án đặt ra mục tiêu là tập trung vào thực hiện các nội dung sau nhằm khắc phục một số hạn chế của các nghiên cứu đã được đề xuất: 1) Phát triển các thuật toán xây dựng LRBS giải bài toán phân lớp, bài toán hồi quy trong đó ngữ nghĩa tính toán của từ ngôn ngữ được xác định dựa trên ĐSGT và mục tiêu tính giải nghĩa được của LRBS được định nghĩa dựa trên độ phức tạp (bao gồm các yếu tố: số luật, độ dài luật, số từ ngôn ngữ sử dụng trên mỗi biến). 2) Nghiên cứu tìm kiếm một hướng tiếp cận mới về tính giải nghĩa được của LRBS dựa trên ĐSGT và đề xuất một số ràng buộc theo hướng tiếp cận này. 3) Đề xuất phương pháp biểu diễn ngữ nghĩa tính toán của tập các từ ngôn ngữ bảo toàn được những tính chất quan trọng của từ ngôn ngữ, chẳng hạn như ngữ nghĩa thứ tự, tính khái quát và tính đặc tả. 4) Phát triển thuật toán tiến hóa xây dựng LRBS giải các bài toán hồi quy, trong đó ngữ nghĩa tính toán của từ ngôn ngữ được xác định theo 6
phương pháp biểu diễn mới và mục tiêu tính giải nghĩa được của LRBS được định nghĩa theo hướng tiếp cận mới. Với mục tiêu đặt ra ở trên, luận án đã đạt được một số kết quả góp phần chứng minh những lợi ích của lý thuyết ĐSGT khi được áp dụng vào giải các bài toán thực tế. Các kết quả chính có thể khái quát như sau: 1) Phát triển một thuật toán xây dựng LRBS giải bài toán phân lớp và hai thuật toán xây dựng LRBS giải bài toán hồi quy theo hướng tiếp cận dựa trên ĐSGT, trong đó mục tiêu tính giải nghĩa được của LRBS được định nghĩa dựa trên độ phức tạp. 2) Khởi tạo hướng tiếp cận mới cho vấn đề tính giải nghĩa được của LRBS theo hướng tiếp cận dựa trên ĐSGT, đề xuất 4 ràng buộc về tính giải nghĩa được ở mức phân hoạch mờ (hay là mức thấp) của các LRBS. 3) Đưa ra định nghĩa khung nhận thức ngôn ngữ (LFoC) trên cơ sở định nghĩa khung nhận thức (FoC) và ĐSGT. Đề xuất phương pháp thiết kế ngữ nghĩa tính toán của tập từ ngôn ngữ của LFoC dựa trên ngữ nghĩa vốn có của từ được xác định bằng ĐSGT thỏa mãn các ràng buộc tính giải nghĩa được của LRBS được đề xuất trong luận án. 4) Phát biểu các định lý khẳng định tính đúng đắn của phương pháp thiết kế ngữ nghĩa tính toán và những ràng buộc mà nó thỏa mãn. 5) Phát triển thuật toán xây dựng LRBS giải bài toán hồi quy theo hướng tiếp cận dựa trên ĐSGT, trong đó mục tiêu tính giải nghĩa được của LRBS được đánh giá dựa trên hướng tiếp cận mới. Nghiên cứu thử nghiệm trên máy tính các thuật toán đã đề xuất, thực hiện đối sánh bằng phương pháp phân tích thống kê các kết quả đạt được với các kết quả của các thuật toán được đề xuất gần đây theo hướng tiếp cận dựa trên lý thuyết tập mờ. Bố cục của luận án gồm: phần mở đầu, 3 chương, phần kết luận và tài liệu tham khảo. Kết quả chính của luận án tập trung ở chương 2 và 3. Cụ thể: Chương 1 trình bày những kiến thức cơ sở cần thiết làm nền tảng trong quá trình nghiên cứu và những đề xuất mới của luận án. Các khái niệm của lý thuyết tập mờ như: tập mờ, phương pháp xây dựng tập mờ, biến ngôn ngữ, phân hoạch mờ. Trình bày những nội dung cơ bản của lý thuyết ĐSGT như: khái 7
niệm ĐSGT, ĐSGT tuyến tính, ĐSGT tuyến tính đầy đủ, độ đo tính mờ, hàm định lượng ngữ nghĩa (SQM), hệ khoảng tương tự. Trình bày tóm tắt về hệ mờ dựa trên luật ngôn ngữ và bàn luận về tính giải nghĩa được của nó. Chương 2 phát triển 3 thuật toán theo hướng tiếp cận dựa trên ĐSGT xây dựng các LRBS giải bài toán phân lớp, bài toán hồi quy, trong đó mục tiêu tính giải nghĩa được của LRBS được định nghĩa dựa trên độ phức tạp. Các thuật toán này thực hiện học đồng thời tham số tập mờ, số tập từ ngôn ngữ sử dụng cho mỗi biến và RB. Trong đó thuật toán OPHA-SGERD được phát triển dựa trên ĐSGT và thuật toán SGERD để giải bài toán phân lớp. Kết quả thử nghiệm của thuật toán được tổng hợp và đối sánh với các kết quả thử nghiệm của thuật toán SGERD trong [39] của Mansoori. Thuật toán HA-PAES-SG và HA- PAES-MG được phát triển dựa trện ĐSGT và lược đồ tiến hóa (2+2)M-PAES giải bài toán hồi quy. Kết quả thử nghiệm của thuật toán được tổng hợp và đối sánh lần lượt với các kết quả thử nghiệm của các thuật toán trong [14] của Antonelli và trong [10] của Alcalá bằng phân tích thống kê với các phương pháp kiểm định giả thuyết t-test và Wilcoxon-test. Chương 3 bàn luận về vấn đề tính giải nghĩa được của FRBS, trình bày định nghĩa khung nhận thức, phát biểu định nghĩa khung nhận thức ngôn ngữ (LFoC). Khởi tạo một hướng tiếp cận giải quyết vấn đề tính giải nghĩa được của LRBS dựa trên ĐSGT. Đề xuất các ràng buộc trên LFoC, như ràng buộc ngữ nghĩa của từ, ràng buộc phương pháp xác định ngữ nghĩa tính toán của từ, ràng buộc trên ngữ nghĩa khoảng của từ và ràng buộc ngữ nghĩa thứ tự của từ. Cũng trong chương này, luận án đề xuất phương pháp thiết kế ngữ nghĩa tính toán dạng cấu trúc đa thể hạt cho từ ngôn ngữ của LFoC, thỏa mãn những ràng buộc đã được đề xuất. Phát biểu và chứng minh các định lý về tính đúng đắn và sự thỏa mãn các ràng buộc của phương pháp thiết kế ngữ nghĩa tính toán mới. Phát triển thuật toán tiến hóa đa mục tiêu HA-PAES-MG-Kmax dựa trên ĐSGT và lược đồ tiến hóa (2+2)M-PAES để xây dựng các LRBS từ dữ liệu giải bài toán hồi quy, trong đó mục tiêu tính giải nghĩa được của LRBS được đánh giá theo hướng tiếp cận mới. Trình bày các kết quả thử nghiệm trên máy tính, các kết quả này được tổng hợp và đối sánh với các kết quả thử nghiệm của thuật toán HA-PAES-SG-Kmax, thuật toán HA-PAES-MG (HA-PAES-MG- Kopt ) được đề xuất trong chương 2 và thuật toán PAES KB của Alcalá trong [10] bằng phân tích thống kê với phương pháp kiểm định giả thuyết Wilcoxon-test. 8
CHƯƠNG 1. MỘT SỐ KIẾN THỨC CƠ SỞ 1.1. Một số kiến thức cơ bản về lý thuyết tập mờ Lý thuyết tập mờ được Zadeh đề xuất năm 1965 trong [63], Zadeh đã đưa ra khái niệm tập mờ, ý tưởng của ông là: giả thiết U là một tập các phần tử, một tập mờ A trong U được biểu diễn bằng một hàm từ tập U vào đoạn [0, 1] biểu thị cấp độ thuộc của phần tử trong U vào tập A và hàm này còn gọi là tập mờ trên U. Khái niệm tập mờ là một mở rộng của khái niệm của tập cổ điển hay tập rõ và mỗi tập rõ là một trường hợp riêng của khái niệm tập mờ. Tập cổ điển chỉ xem xét một phần tử có thuộc hay không thuộc về nó, với tập mờ thì bất kỳ phần tử nào trong vũ trụ đều có thể thuộc về nó với mức độ thuộc được đo bởi một giá trị trong đoạn [0, 1]. 1.1.1. Định nghĩa tập mờ Định nghĩa 1.1: [63, 66] Cho U là một tập các điểm (đối tượng) với các phần tử ký hiệu bởi x, U={x}. Một tập mờ A trên U là một tập mà mỗi phần tử của nó là một cặp các giá trị ((x,  A(x)), trong đó x U và  A là ánh xạ:  A : U  [0, 1] (1.1) Trong đó ánh xạ  A được gọi là hàm thuộc (membership function) của tập mờ A. Tập U được gọi là cơ sở của tập mờ A, ký hiệu A  ( x,  A ( x)) : x U , hàm  A(x) biểu thị cấp độ thuộc của phần tử x vào tập mờ A, nếu giá trị của  A(x) càng gần 1 thì cấp độ thuộc của x vào A cao hơn. Tập mờ là sự mở rộng của khái niệm tập rõ, khi A là một tập hợp kinh điển hàm thuộc của  A(x) chỉ nhận một trong hai giá trị 1 hoặc 0, tương ứng phần tử x có thuộc hay không thuộc tập A. Ví dụ: Một tập mờ A của các số tự nhiên nhỏ hơn 5 với hàm thuộc  A(x) có dạng như hình 1.1 định nghĩa trên tập vũ trụ U sẽ gồm các phần tử sau: A={(1, 1), (2, 1), (3, 0.8), (4, 0.6), (5, 0.4), (6, 0.2), (7, 0)} Các số tự nhiên 1, 2, 3 và 4 có độ phụ thuộc như sau:  A(1) = 1,  A(2) = 1,  A(3) = 0.8,  A(4) = 0.6,  A(5) = 0.4,  A(6) = 0.2,  A(7) = 0. 9