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 tưu dụa trên luật

1

49

r

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

HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ

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

i

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

ii

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.

iii

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

iv

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

v

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

vi

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

vii

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

viii

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

ix

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à PAESKB (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à PAESKB (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

x

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

1

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

2

[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