Nghiên cứu ngữ nghĩa trong hệ lập trình gen định hướng bởi văn phạm nối cây và ứng dụng trong xấp xỉ hàm Q

i

BỘ GIÁO DỤC VÀ ĐÀO TẠO

TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI

-------***-------

ĐÀO NGỌC PHONG

TÊN ĐỀ TÀI LUẬN ÁN

NGHIÊN CỨU NGỮ NGHĨA TRONG HỆ LẬP TRÌNH

GEN ĐỊNH HƯỚNG BỞI VĂN PHẠM NỐI CÂY VÀ

ỨNG DỤNG TRONG XẤP XỈ HÀM Q

CHUYÊN NGÀNH: HỆ THỐNG THÔNG TIN

MÃ SỐ: 62480104

LUẬN ÁN TIẾN SĨ HỆ THỐNG THÔNG TIN

Hà Nội - 2014

ii

BỘ GIÁO DỤC VÀ ĐÀO TẠO

TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI

-------***-------

ĐÀO NGỌC PHONG

TÊN ĐỀ TÀI LUẬN ÁN

NGHIÊN CỨU NGỮ NGHĨA TRONG HỆ LẬP TRÌNH

GEN ĐỊNH HƯỚNG BỞI VĂN PHẠM NỐI CÂY VÀ

ỨNG DỤNG TRONG XẤP XỈ HÀM Q

CHUYÊN NGÀNH: HỆ THỐNG THÔNG TIN

MÃ SỐ: 62480104

LUẬN ÁN TIẾN SĨ HỆ THỐNG THÔNG TIN

NGƯỜI HƯỚNG DẪN KHOA HỌC

1. GS.TS NGUYỄN THANH THỦY

2. PGS.TS NGUYỄN XUÂN HOÀI

Hà Nội - 2014

iii

MỤC LỤC

LỜI CAM ĐOAN ............................................................................................. vi

LỜI CẢM ƠN .................................................................................................. vii

DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT ....................................... viii

DANH MỤC CÁC BẢNG ................................................................................ ix

DANH MỤC CÁC HÌNH ẢNH, ĐỒ THỊ .......................................................... x

GIỚI THIỆU CHUNG ....................................................................................... 1

MỤC ĐÍCH .................................................................................................... 1

MỤC TIÊU NGHIÊN CỨU ............................................................................ 3

PHƯƠNG PHÁP NGHIÊN CỨU ................................................................... 3

CÁC ĐÓNG GÓP CHÍNH ............................................................................. 4

TỔNG QUAN VỀ CẤU TRÚC CỦA LUẬN ÁN .......................................... 5

CHƯƠNG 1. TỔNG QUAN .............................................................................. 6

1.1 GIẢI THUẬT TIẾN HÓA ..................................................................... 6

1.2 GIẢI THUẬT DI TRUYỀN................................................................... 7

1.3 LẬP TRÌNH GEN.................................................................................. 9

1.3.1 Lập trình Gen chuẩn có cấu trúc cây .............................................. 10

1.3.2 Một số vấn đề với lập trình Gen chuẩn có cấu trúc cây .................. 14

1.3.3 GP với biểu diễn tuyến tính ............................................................ 15

1.4 LẬP TRÌNH GEN ĐỊNH HƯỚNG BỞI VĂN PHẠM ........................ 18

1.4.1 GGGP với biểu diễn dạng cây ........................................................ 20

1.4.2 GGGP với biểu diễn tuyến tính ...................................................... 22

1.4.3 Một số vấn đề gặp phải với GGGP ................................................. 24

1.5 VĂN PHẠM NỐI CÂY VÀ LẬP TRÌNH GEN ĐỊNH HƯỚNG BỞI VĂN

PHẠM NỐI CÂY (TAG3P) .......................................................................... 25

1.5.1 Văn phạm nối cây (Tree-Adjoining Grammar – TAG) ................... 25

1.5.2 Hệ lập trình Gen định hướng bởi văn phạm nối cây ....................... 29

KẾT LUẬN CHƯƠNG ................................................................................ 37

CHƯƠNG 2. NGỮ NGHĨA TRÊN HỆ TAG3P ............................................... 39

iv

2.1 NGỮ NGHĨA TRONG LẬP TRÌNH TIẾN HÓA ................................ 39

2.1.1 Sử dụng văn phạm để biểu diễn ngữ nghĩa ........................................ 41

2.1.2 Sử dụng phương pháp hình thức ....................................................... 43

2.1.3 Sử dụng ngữ nghĩa dựa trên biểu diễn của GP ................................... 43

2.2 NGỮ NGHĨA TRONG TAG3P ........................................................... 45

2.2.1 Định nghĩa ngữ nghĩa của cây con trong TAG3P ........................... 45

2.2.2 Đặc điểm ngữ nghĩa cây con trong TAG3P .................................... 51

KẾT LUẬN CHƯƠNG ................................................................................ 52

CHƯƠNG 3. TOÁN TỬ DI TRUYỀN DỰA TRÊN NGỮ NGHĨA ................ 54

3.1 TỔNG QUAN TOÁN TỬ DI TRUYỀN DỰA TRÊN NGỮ NGHĨA . 54

3.2 TOÁN TỬ LAI GHÉP DỰA TRÊN NGỮ NGHĨA TRONG TAG3P .. 58

3.2.1 Toán tử lai ghép dựa trên ngữ nghĩa trong TAG3P............................ 58

3.2.2 Thử nghiệm ....................................................................................... 61

3.2.3 Toán tử lai cặp cây con có tổng giá trị ngữ nghĩa dương lớn nhất ..... 67

3.2.4 SO SÁNH KẾT QUẢ VỚI CÁC TOÁN TỬ TƯƠNG TỰ ............... 67

3.3 TOÁN TỬ ĐỘT BIẾN DỰA TRÊN NGỮ NGHĨA TRONG TAG3P . 71

3.3.1 Toán tử đột biến dựa trên ngữ nghĩa trong TAG3P ........................... 71

3.3.2 Thử nghiệm ....................................................................................... 74

KẾT LUẬN CHƯƠNG ................................................................................ 78

CHƯƠNG 4. ỨNG DỤNG .............................................................................. 79

4.1 BÀI TOÁN HỌC XẤP XỈ HÀM Q VÀ HÀM NGƯỢC Q .................. 79

4.1.1 Hàm Q .............................................................................................. 79

4.1.2 Một số dạng xấp xỉ do chuyên gia đề xuất ......................................... 81

4.1.3 Hàm ngược Q .................................................................................... 82

4.2 ỨNG DỤNG HỌC XẤP XỈ HÀM Q ................................................... 83

4.2.1 Xác định hàm thích nghi với bài toán học xấp xỉ hàm Q ................... 83

4.2.2 Thiết kế thí nghiệm ........................................................................... 87

4.2.3 Kết quả và nhận xét ........................................................................... 89

4.3 ỨNG DỤNG HỌC XẤP XỈ HÀM NGƯỢC Q .................................... 93

v

4.3.1 Xác định hàm thích nghi với bài toán học xấp xỉ hàm ngược Q ........ 93

4.3.2 Thiết kế thí nghiệm và kết quả .......................................................... 94

KẾT LUẬN CHƯƠNG ................................................................................ 98

KẾT LUẬN ...................................................................................................... 99

HƯỚNG NGHIÊN CỨU VÀ PHÁT TRIỂN CỦA LUẬN ÁN ...................... 101

DANH MỤC CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ CỦA LUẬN ÁN ............ 102

TÀI LIỆU THAM KHẢO .............................................................................. 103

vi

LỜI CAM ĐOAN

Tôi xin cam đoan luận án là công trình nghiên cứu của riêng tác giả. Các

kết quả được công bố 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ả

Đào Ngọc Phong

vii

LỜI CẢM ƠN

Luận án được hoàn thành tại Viện Công nghệ thông tin và Truyền thông,

trường Đại học Bách khoa Hà Nội. Để hoàn thành luận án này, tác giả đã nhận

được sự chỉ bảo tận tình, sự động viên khích lệ, cùng những yêu cầu của GS.TS

Nguyễn Thanh Thủy và PGS.TS Nguyễn Xuân Hoài, những người Thầy đã

truyền đạt rất nhiều kiến thức quí báu cũng như những kinh nghiệm nghiên cứu

khoa học trong suốt thời gian tác giả theo học nghiên cứu sinh. 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 tới các Thầy.

Tác giả xin chân thành gửi lời cảm ơn về sự chia sẻ kiến thức khoa học

của GS Bob McKay, GS Costi và TS Nguyễn Quang Uy đã giúp ích và hỗ trợ

rất nhiều cho tác giả trong suốt quá trình nghiên cứu.

Tác giả xin chân thành cảm ơn Ban lãnh đạo Viện Công nghệ thông tin và

Truyền thông, Viện Đào tạo Sau đại học, trường Đại học Bách khoa Hà Nội,

Ban giám đốc Sở Thông tin và Truyền thông Hà Nội đã tạo điều kiện thuận lợi

cho tác giả trong quá trình học tập, nghiên cứu để hoàn thành luận án.

Qua đây, cho phép tác giả xin cảm ơn Quỹ Phát triển Khoa học và Công

nghệ Quốc gia đã tài trợ một phần cho nghiên cứu này.

Tác giả xin cảm ơn các Thầy, Cô trong Bộ môn Hệ thống thông tin - Viện

Công nghệ thông tin và Truyền thông, Trường Đại học Bách khoa Hà Nội.

Luận án này, như một món quà tinh thần, xin đáp lại những niềm quan

tâm, mong mỏi của mọi thành viên trong gia đình, đó là một trong những nguồn

động viên để tác giả nỗ lực học tập, nghiên cứu.

viii

DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT

Ký hiệu

viết tắt

Ký hiệu đầy đủ Diễn giải

EA Evolutionary Algorithms Giải thuật tiến hóa

ES Evolutionary Strategies Chiến lược tiến hóa

GA Genetic Algorithm Giải thuật di truyền

EP Evolutionary Programming Lập trình tiến hóa

GP Genetic Programming Lập trình Gen

GGGP

Grammar-guided genetic

programming

Lập trình Gen định hướng bởi

văn phạm

CFG Context Free Grammars Văn phạm phi ngữ cảnh

TAG Tree-Adjoining Grammars Văn phạm nối cây

TAG3P

Tree-Adjunct Grammar Guided

Genetic Programming

Lập trình Gen định hướng bởi

văn phạm nối cây

SSC

Semantic Similarity based

Crossover

Toán tử lai ghép dựa trên ngữ

nghĩa tương tự

MSSC

The Most Semantic Similarity

based Crossover

Toán tử lai ghép dựa trên ngữ

nghĩa tương tự nhất

RAE Relative Absolute Error Lỗi tương đối

MAE Mean Absolute Error Lỗi tuyệt đối

Q Q-Function Hàm Q

Q-Inver Q-Inversion-Function Hàm ngược Q

LTAG

Lexicalised Tree-Adjoining

Grammars

Văn phạm nối cây cấu trúc

từ vựng

ix

DANH MỤC CÁC BẢNG

Bảng 3.1. Tập hợp các bài toán làm thí nghiệm 62

Bảng 3.2 Cấu hình thí nghiệm 63

Bảng 3.3. Số lần chạy thí nghiệm thành công 64

Bảng 3.4. Trung bình độ tốt của 100 lần chạy thí nghiệm 65

Bảng 3.5. Trung bình thay đổi độ tốt sau khi thực hiện lai ghép 66

Bảng 3.6. Cấu hình thí nghiệm 67

Bảng 3.7. Số lần chạy thí nghiệm thành công 68

Bảng 3.8. Trung bình độ tốt của 100 lần chạy thí nghiệm 70

Bảng 3.9. Trung bình thay đổi độ tốt sau khi thực hiện lai ghép 70

Bảng 3.10. Cấu hình thí nghiệm 75

Bảng 3.11. Số lần chạy thí nghiệm thành công 76

Bảng 3.12. Trung bình độ tốt của 100 lần chạy thí nghiệm 77

Bảng 4.1. Bảng thông số được cài đặt cho mỗi thí nghiệm 88

Bảng 4.2. Kết quả thí nghiệm học xấp xỉ hàm Q 90

Bảng 4.3. Cấu hình thí nghiệm 95

Bảng 4.4. Kết quả thí nghiệm học xấp xỉ hàm ngược Q 97

x

DANH MỤC CÁC HÌNH ẢNH, ĐỒ THỊ

Hình vẽ 1.1. Sơ đồ khối của thuật giải EA 7

Hình vẽ 1.2. Biểu diễn cá thể trong GA 7

Hình vẽ 1.3 Các toán tử cơ bản trong GA chuẩn 8

Hình vẽ 1.4. Biểu diễn chương trình GP 11

Hình vẽ 1.5. Thao tác lai ghép trong GP 13

Hình vẽ 1.6. Thao tác đột biến trong GP 14

Hình vẽ 1.7. Kiểu Gen và kiểu hình trong GEP 15

Hình vẽ 1.8. Ví dụ về việc thay đổi hoàn toàn của kiểu hình 16

Hình vẽ 1.9. Một cá thể 17

Hình vẽ 1.10 Một ví dụ về ánh xạ giữa kiểu Gen và kiểu hình trong GE 23

Hình vẽ 1.11 Một ví dụ về TAG 26

Hình vẽ 1.12. Phép nối cây trong TAG 27

Hình vẽ 1.13. Phép thế cây trong TAG 28

Hình vẽ 1.14. Ví dụ về cây dẫn xuất và cây phân tích trong TAG 29

Hình vẽ 1.15. Quá trình ánh xạ 31

Hình vẽ 1.16. Thao tác lai ghép trong TAG3P 32

Hình vẽ 1.17. Thao tác đột biến trong TAG3P 33

Hình vẽ 1.18. Toán tử chèn 34

Hình vẽ 1.19 Toán tử xóa 34

Hình vẽ 1.20. Toán tử thay thế 35

Hình vẽ 1.21. Toán tử di chuyển 35

Hình vẽ 1.22. Toán tử sao lưu 36

Hình vẽ 1.23. Toán tử cắt bỏ 36

Hình vẽ 2.1 Văn phạm thuộc tính 41

Hình vẽ 2.2 Văn phạm logic 42

Hình vẽ 2.3. Ngữ cảnh có được bằng cách loại bỏ cây con 44

Hình vẽ 2.4. Ngữ nghĩa trong GP biểu diễn dạng cây biểu thức 46

xi

Hình vẽ 2.5. Một ví dụ về cây cơ bản trong văn phạm TAG 47

Hình vẽ 2.6. Kiểu Gen và kiểu hình trong TAG3P 47

Hình vẽ 2.7. Tính toán độ đóng góp của cây con 48

Hình vẽ 2.8. Quá trình tính toán ngữ nghĩa cây con 49

Hình vẽ 3.1. Cây con tương đồng được lựa chọn 57

Hình vẽ 3.2. Cây con được tạo ra bởi lai ghép hai cây con tương đồng 57

Hình vẽ 4.1. Đồ thị của hàm Q 79

Hình vẽ 4.2. Lỗi tương đối của các xấp xỉ tìm được khi sử dụng hàm

thích nghi MAE và xấp xỉ OPBCS

85

Hình vẽ 4.3. Lỗi tương đối của các xấp xỉ tìm được khi sử dụng hàm

thích nghi RAE và xấp xỉ OPBCS

86

Hình vẽ 4.4. Văn phạm LTAG của TAP3P cho bài toán học xấp xỉ

hàm Q với dạng hàm mũ

89

Hình vẽ 4.5. So sánh lỗi tương đối của xấp xỉ hàm Q 92

Hình vẽ 4.6. Đồ thị hàm ngược Q 93

Hình vẽ 4.7. Văn phạm LTAG của TAP3P cho bài toán xấp xỉ hàm

ngược Q

96

1

GIỚI THIỆU CHUNG

Trong mục này, luận án sẽ giới thiệu khái quát về mục đích của việc

nghiên cứu, mục tiêu, phương pháp nghiên cứu, các đóng góp chính của luận án

và cuối cùng là bố cục các phần của luận án.

MỤC ĐÍCH

Lập trình Gen (Genetic Programming – GP) được đề xuất bởi Koza [1], từ

khi ra đời đã được xem như một phương pháp học máy có tiềm năng. Chính vì

vậy GP đã được áp dụng rộng rãi để giải quyết thành công nhiều bài toán, trong

đó phần nhiều là các bài toán liên quan đến học máy. GP có thể dùng để giải

quyết những bài toán học khi độ phức tạp cấu trúc của lời giải là không biết

trước, GP đòi hỏi ít tri thức nền của bài toán, và cho lời giải dưới dạng tường

minh (cách tiếp cận hộp trắng) cho người dùng.

Có nhiều phương pháp học máy được sử dụng như: cây quyết định, mạng

nơron nhân tạo, máy vectơ hỗ trợ,…. Các phương pháp được tiếp cận theo hai

mô hình là hộp đen (Blackbox) và hộp trắng (Whitebox) hoặc lai ghép giữa hai

mô hình trên. Mạng nơ-ron hay máy véctơ hỗ trợ là một ví dụ về mô hình hộp

đen, do lời giải thích cho kết quả quá phức tạp để có thể hiểu được. Trong khi

đó, lập trình Gen tiếp cận theo mô hình hộp trắng với lời giải có tính giải thích

và ở dạng đóng. So với các mô hình học máy khác thì GP có khá nhiều lợi điểm.

Thứ nhất, GP là phương pháp học quan hệ có khả năng học các tri thức

dưới dạng các chương trình máy tính.

Thứ hai, GP sử dụng cách tiếp cận hộp trắng cung cấp lời giải dưới dạng

tường minh, dễ hiểu hơn đối với người dùng (so với các kỹ thuật học dùng hộp

đen như mạng Neural, máy vector hỗ trợ, mô hình đồ thị,…, trong đó lời giải

thường ẩn trong các trọng số hay xác suất). Sự tường minh của lời giải trong

nhiều trường hợp là cần thiết.

Thứ ba, khi so sánh với các mô hình học hộp trắng, GP sử dụng ít tri thức

nền của bài toán hơn (trong nhiều trường hợp tri thức này không thể thu nạp dễ