..

NGUYỄN QUỐC TUẤN

BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
---------------------------------------

Học viên: Nguyễn Quốc Tuấn

KHOA HỌC MÁY TÍNH

GIẢI THUẬT TIẾN HĨA ĐA NHIỆM VỤ
TRONG HUẤN LUYỆN MẠNG NƠ-RON TRUYỀN THẲNG

LUẬN VĂN THẠC SĨ KHOA HỌC
KHOA HỌC MÁY TÍNH

2016B
Hà Nội – Năm 2019


BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
---------------------------------------

Học viên: Nguyễn Quốc Tuấn

GIẢI THUẬT TIẾN HÓA ĐA NHIỆM VỤ
TRONG HUẤN LUYỆN MẠNG NƠ-RON TRUYỀN THẲNG

Chuyên ngành : Khoa học máy tính

LUẬN VĂN THẠC SĨ KHOA HỌC
KHOA HỌC MÁY TÍNH

NGƯỜI HƯỚNG DẪN KHOA HỌC :
PGS. TS. Huỳnh Thị Thanh Bình

Hà Nội – Năm 2019


CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM
Độc lập – Tự do – Hạnh phúc

BẢN XÁC NHẬN CHỈNH SỬA LUẬN VĂN THẠC SĨ
Họ và tên tác giả luận văn : Nguyễn Quốc Tuấn .............................................
Đề tài luận văn: Giải thuật tiến hóa đa nhiệm vụ trong huấn luyện mạng nơ-ron
truyền thẳng ........................................................................................................
Chuyên ngành: Khoa học máy tính ...................................................................
Mã số SV: CB160552 ........................................................................................
Tác giả, Người hướng dẫn khoa học và Hội đồng chấm luận văn xác
nhận tác giả đã sửa chữa, bổ sung luận văn theo biên bản họp Hội đồng ngày
27/04/2019 với các nội dung sau:
- Chỉnh sửa các lỗi chính tả, lỗi đánh máy
- Điều chỉnh phông chữ luận văn theo đúng quy định
- Sửa các lỗi tham chiếu chéo hình ảnh và bảng biểu

Ngày 27 tháng 04 năm 2019
Giáo viên hướng dẫn


CHỦ TỊCH HỘI ĐỒNG

Tác giả luận văn


LỜI TRI ÂN
Lời đầu tiên, tôi xin gửi lời cảm ơn chân thành và sâu sắc tới giáo viên hướng
dẫn PGS. TS. Huỳnh Thị Thanh Bình đã tận tình dạy bảo và cung cấp những
gợi ý quý báu giúp tôi nâng cao kiến thức và hoàn thành tốt luận văn này. Tơi
cũng xin bày tỏ lịng biết ơn sâu sắc tới GS. Ong Yew Soon, TS. Abhishek Gupta
của Đại học Công nghệ Nanyang (Singapore) và GS. Katsumi Inoue của Viện
Tin học quốc gia Nhật Bản đã nhiệt tình hỗ trợ và đưa ra những định hướng,
những lời khuyên trong suốt q trình tơi thực hiện đề tài.
Đồng thời, tơi xin bày tỏ lịng biết ơn tới các thầy cơ của trường Đại học
Bách khoa Hà Nội, đặc biệt là các thầy cô của Viện Công nghệ Thông tin và
Truyền thông, là những người thầy cơ mẫu mực ln hết lịng truyền đạt những
kiến thức, kinh nghiệm của mình cho cho các thế hệ sinh viên kỹ thuật chúng
tôi. Những kiến thức và kinh nghiệm đó sẽ ln là hành trang vững chắc cho
mỗi sinh viên trên con đường sự nghiệp sau này.
Tôi cũng xin gửi lời cảm ơn tới các anh chị nghiên cứu sinh và các bạn sinh
viên phòng thí nghiệm Mơ hình hóa, mơ phỏng và tối ưu (Modelling, Simulation
and Optimization lab), những người đã ln nhiệt tình giúp đỡ tơi trong suốt
q trình học tập, nghiên cứu tại trường đại học.
Cuối cùng, với tất cả sự thương yêu và kính trọng, con xin gửi lời biết ơn sâu
sắc nhất tới bố mẹ và những người thân trong gia đình đã ln là chỗ dựa vững
chắc, là nguồn động viên tinh thần vô cùng lớn lao, tạo mọi điều kiện tốt nhất
cho con ăn học nên người, trưởng thành và chín chắn hơn.

III



LỜI CAM ĐOAN
Tôi, Nguyễn Quốc Tuấn - tác giả luận văn này, xin cam đoan:
1. Những nội dung trong luận văn này là cơng trình nghiên cứu của tơi dưới
sự hướng dẫn trực tiếp của PGS. TS. Huỳnh Thị Thanh Bình.
2. Mọi tham khảo dùng trong luận văn đều được trích dẫn rõ ràng tên tác
giả, tên cơng trình, thời gian, địa điểm công bố.
3. Các số liệu, kết quả nêu trong luận vă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.
4. Mọi sao chép không hợp lệ, vi phạm quy chế đào tạo, tơi xin chịu hồn
tồn trách nhiệm.
Tác giả luận văn

IV


MỤC LỤC
TRANG PHỤ BÌA LUẬN VĂN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

I

BẢN XÁC NHẬN CHỈNH SỬA LUẬN VĂN THẠC SĨ . . . . . . . . . . . . . . . . .

II

LỜI TRI ÂN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . III
LỜI CAM ĐOAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

IV


MỤC LỤC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

V

DANH MỤC THUẬT NGỮ VÀ TỪ VIẾT TẮT . . . . . . . . . . . . . . . . . . . . . . VII
DANH MỤC HÌNH ẢNH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

X

DANH MỤC BẢNG BIỂU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

XI

DANH MỤC GIẢI THUẬT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . XII
Chương I:
GIỚI THIỆU TỔNG QUAN
I.1 Tính cấp thiết của đề tài . . . . . . . . . .
I.2 Mục đích và đối tượng nghiên cứu . . . . .
I.3 Phạm vi và phương pháp nghiên cứu . . . .
I.4 Cấu trúc của luận văn . . . . . . . . . . . .

.
.
.
.
.

.
.
.

.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

1
2
2

2
3

Chương II:
CƠ SỞ LÝ THUYẾT . . . . . . . . . . . . . . . . . . . . . . .
II.1 Tổng quan về mạng nơ-ron . . . . . . . . . . . . . . . . . . . . . . . . . . . .
II.1.1 Các thành phần cơ bản của mạng nơ-ron nhân tạo . . . . . . . . . . .
II.1.1.1 Đơn vị xử lý . . . . . . . . . . . . . . . . . . . . . . . . . . .
II.1.1.2 Hàm kích hoạt . . . . . . . . . . . . . . . . . . . . . . . . . .
II.1.2 Lan truyền thông tin trong mạng nơ-ron . . . . . . . . . . . . . . . . .
II.1.3 Hàm mất mát . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
II.1.4 Giải thuật lan truyền ngược trong mạng nơ-ron . . . . . . . . . . . . .
II.2 Tổng quan về tối ưu hóa liên tục . . . . . . . . . . . . . . . . . . . . . . . . .
II.2.1 Bài toán tối ưu liên tục . . . . . . . . . . . . . . . . . . . . . . . . . .
II.2.2 Một số phương pháp giải bài toán tối ưu liên tục . . . . . . . . . . . .
II.2.2.1 Phương pháp đưịng tìm kiếm . . . . . . . . . . . . . . . . .
II.2.2.2 Phương pháp heuristic . . . . . . . . . . . . . . . . . . . . .
II.2.3 Tối ưu đa mục tiêu . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
II.2.4 Tối ưu đa nhiệm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
II.3 Tổng quan về giải thuật tiến hóa đa nhiệm vụ . . . . . . . . . . . . . . . . . .
II.3.1 Giải thuật tiến hóa . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
II.3.1.1 Lai ghép phỏng chéo hóa nhị phân . . . . . . . . . . . . . . .
II.3.1.2 Đột biến đa thức . . . . . . . . . . . . . . . . . . . . . . . . .
II.3.1.3 Phép biến đổi tiến hóa vi phân . . . . . . . . . . . . . . . . .
II.3.2 Giải thuật tiến hóa đa nhiệm vụ . . . . . . . . . . . . . . . . . . . . .
II.3.2.1 Độ đo tương tự . . . . . . . . . . . . . . . . . . . . . . . . . .
II.3.2.2 Sự giao hội tập lời giải tối ưu trong tối ưu hóa đa nhiệm vụ .
II.3.2.3 Độ đo ảnh hưởng đa nhiệm . . . . . . . . . . . . . . . . . . .

.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.

4
4
5
5
6
7
8
8
9
10
11
11
12
13
14
15
15
16
17
17
18
20
21
22

NƠ-RON

. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

25
25
25
26

26
27
27
28

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.

.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.

.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.

.
.
.
.

Chương III:
GIẢI THUẬT TIẾN HÓA HUẤN LUYỆN MẠNG
III.1 Các phương pháp dựa trên đạo hàm . . . . . . . . . . . . . . . . . . .
III.1.1 Gradient Descent . . . . . . . . . . . . . . . . . . . . . . . . . .
III.1.2 Stochastic Gradient Descent . . . . . . . . . . . . . . . . . . . .
III.1.3 Stochastic Gradient Descent với động lực . . . . . . . . . . . .
III.2 Sử dụng giải thuật tiến hóa làm giải thuật học . . . . . . . . . . . . .
III.2.1 Tối ưu trọng số kết nối . . . . . . . . . . . . . . . . . . . . . . .
III.2.2 Tối ưu kiến trúc mạng . . . . . . . . . . . . . . . . . . . . . . .
V

.
.
.
.
.

.
.
.
.
.

.
.

.
.
.


III.3 Tiến hóa đa nhiệm trong huấn luyện mạng nơ-ron . . . . . . . . . . . . . . . . . . . .
ĐỀ XUẤT GIẢI THUẬT HỌC CHO MẠNG NƠ-RON TRUYỀN
THẲNG NHIỀU LỚP DỰA TRÊN THUẬT TỐN TIẾN HĨA
ĐA NHIỆM VỤ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
IV.1 Phương pháp mã hóa mạng nơ-ron nhiều lớp trong khơng gian chung . . . . . . . . . .
IV.2 Tính tốn độ thích nghi đơn nhiệm . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
IV.3 Giải thuật tiến hóa đa nhiệm đề xuất . . . . . . . . . . . . . . . . . . . . . . . . . . .
IV.3.1 Phép lai ghép và đột biến trong không gian chung . . . . . . . . . . . . . . . .
IV.3.2 Chiến lược tự thích nghi xác suất ghép cặp ngẫu nhiên . . . . . . . . . . . . . .

30

Chương IV:

Chương V:
KẾT QUẢ ĐẠT ĐƯỢC
V.1 Thiết lập thực nghiệm . . . . . . . . .
V.1.1 Dữ liệu thực nghiệm . . . . . .
V.1.2 Cấu hình ANN thực nghiệm . .
V.1.3 Cấu hình tham số giải thuật .
V.2 Kết quả thực nghiệm . . . . . . . . . .
V.2.1 Mạng nơ-ron cùng độ sâu . . .
V.2.2 Mạng nơ-ron khác độ sâu . . .
V.3 Nhận xét và bàn luận . . . . . . . . .


34
35
38
38
39
39

.
.
.
.
.
.
.
.
.

41
41
41
42
43
43
44
50
57

KẾT LUẬN VÀ KIẾN NGHỊ . . . . . . . . . . . . . . . . . . . . . . .

59


DANH MỤC TÀI LIỆU THAM KHẢO . . . . . . . . . . . . . . . . . . . . . . . . . . . .

60

PHỤ LỤC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Danh sách các cơng trình đã cơng bố . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

63
63

Chương VI:

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.

VI

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.


DANH MỤC THUẬT NGỮ VÀ TỪ VIẾT TẮT
Các thuật ngữ
accuracy : độ chính xác . 41, 43, 57
activation function : hàm kích hoạt . 6, 9, 28, 30
backpropagation : lan truyền ngược . 8, 26
bias : độ lệch . 6, 8, 9, 34
building block : khối di truyền cơ bản . 16
complete intersection : giao hội hoàn toàn . 21
continuous optimization : tối ưu hóa liên tục . 3, 9, 10, 11, 12, 15, 17, 23, 28
convex optimization : tối ưu lồi . 10, 18
convex function : hàm lồi . 10
cross over : lai ghép . 15, 17, 19, 22, 32, 35, 39
decision variable : biến quyết định . 9
discrete optimization : tối ưu hóa rời rạc . 9
factorial rank : xếp hạng đơn nhiệm . 19
factorial cost : giá trị thích nghi đơn nhiệm . 19, 38
feasible solution : lời giải khả thi . 9, 12, 13, 14, 21
fitness : độ thích nghi . 18, 38, 43
global complemetary : ảnh hưởng toàn cục . 22
global minima : tối ưu toàn cục . 10, 22, 23, 26, 27
hidden layer : lớp ẩn . 9, 30, 34, 41
hidden unit : đơn vị ẩn . 5, 9, 30
input layer : lớp đầu vào . 30, 34, 35
input unit : đơn vị đầu vào . 5, 41

learning rate : tốc độ học . 25
line search : đường tìm kiếm . 11, 15
local complemetary : ảnh hưởng cục bộ . 22
local search : tìm kiếm địa phương . 12
local minima : tối ưu cục bộ . 10, 11, 25, 26, 27, 32
loss function : hàm mất mát . 8, 9, 38
maximization : cực đại hóa . 10
minimization : cực tiểu hóa . 10, 13, 14
multi-variate optimization : tối ưu hóa đa biến . 10
VII


mutation : đột biến . 15, 17, 19, 22, 35, 39
no intersection : không giao hội . 21
non-dominated solution set : tập nghiệm không trội . 14
optimization : tối ưu hóa . 9, 10, 13, 14, 15, 18, 19, 20, 21, 25, 27, 28, 30, 31, 32, 33, 35, 37, 41, 42,
57
output layer : lớp đầu ra . 9, 30, 34, 35
output unit : đơn vị đầu ra . 5
overfit : học tủ . 25
Pareto-optimal front : biên tối ưu Pareto . 14
Pareto-optimal set : tập nghiệm tối ưu Pareto . 14
Pareto front : biên Pareto . 14
Pareto dominant : trội Pareto . 13
partial intersection : giao hội một phần . 21
plateau : bình nguyên . 27
population-based search : tìm kiếm dựa trên quần thể . 12, 18
random mating probability : xác suất ghép cặp ngẫu nhiên . 19, 35, 38, 39, 40
scalar fitness : độ thích nghi vơ hướng . 19, 38
self complemetary : tự ảnh hưởng . 23

skill factor : chỉ số kỹ năng . 19, 37, 38, 39
solution : lời giải . 9, 12, 13, 14, 15, 16, 17, 18, 20, 22
steepest descent : đi ngược hướng đạo hàm với bước nhảy sao cho cực tiểu hóa hàm mục tiêu .
12
transfer optimization : tối ưu hóa có truyền đạt . 31
transfer learning : học có truyền đạt . 31
unified space : không gian chung . 18, 23, 30, 35, 39

Các từ viết tắt
ACO (Ant Colony Optimization) : Tối ưu đàn kiến. 15
ANN (Artificial Neural Network) : Mạng nơ-ron nhân tạo. 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 25, 26, 27,
28, 29, 30, 33, 34, 35, 37, 38, 41, 42, 43, 56, 57, 59
CNN (Convolutional Neural Network) : Mạng nơ-ron tích chập. 4
DE (Differential Evolution) : Tiến hóa vi phân. 15, 17, 18, 28, 39, 43
EA (Evolutionary Algorithm) : Giải thuật tiến hóa. 3, 12, 15, 16, 17, 22, 27, 30, 31, 41, 43, 56,
57, 58
EANN (Evolutionary Artificial Neural Network) : Mạng nơ ron nhân tạo tiến hóa. 27, 28
FNN (Feedforward Neural Network) : Mạng nơ-ron truyền thẳng. 2, 3, 4
VIII


FSM (Functional Synergy Metric) : Độ đo ảnh hưởng đa nhiệm. 22, 23
GD (Gradient Descent) : Đi ngược hướng đạo hàm. 8, 12, 25, 26, 41, 56, 58, 59
MFEA (Multi-Factorial Evolutionary Algorithm) : Giải thuật tiến hóa đa nhiệm vụ. 2, 3, 15,
18, 19, 21, 22, 23, 30, 31, 32, 33, 34, 37, 38, 39, 40, 41, 43, 57, 58
MFO (Multi-Factorial Optimization) : Tối ưu hóa đa nhiệm vụ. 10, 14, 15, 18, 21, 31, 32, 37
ML (Machine Learning) : Học máy. 4, 25
MOO (Multi-Objective Optimization) : Tối ưu hóa đa mục tiêu. 10, 13, 15
MSE (Mean Square Error) : Trung bình của bình phương lỗi. 2, 8, 38, 41, 43, 57
NAG (Nesterov Accelerated Gradient) : Gia tốc cho đạo hàm Nesterov. 27

NEAT (NeuroEvolution through Augmenting Topologies) : Tiến hóa mạng nơ-ron thông
qua tăng cường kiến trúc mạng. 29, 30
PMU (Polynomial Mutation) : Đột biến đa thức. 15, 30, 39, 43
PSO (Particle Swarm Optimization) : Tối ưu bầy đàn. 15
RMSProp (Root Mean Square propagation) : Lan truyền ngược trung bình bình phương lỗi.
27
RNN (Recurrent Neural Network) : Mạng nơ-ron hồi qui. 4
SBX (Simulated Binary Crossover) : Lai ghép phỏng chéo hóa nhị phân. 15, 16, 30, 39, 43
SGD (Stochastic Gradient Descent) : Đi ngược hướng đạo hàm ngẫu nhiên. 26, 27
UCI (University of California, Irvine) : Đại học California, Irvine. 41
UDA (Unified representation for Deep ANN) : Biểu diễn chung cho mạng nơ-ron nhiều lớp.
38, 39, 41, 43, 57, 58

IX


DANH MỤC HÌNH ẢNH
Hình II.1:

Cấu trúc nơ-ron sinh học (trái) và mơ hình tốn học tương ứng (phải). . . . .

4

Hình II.2:

Minh họa bài tốn phân loại. [5] . . . . . . . . . . . . . . . . . . . . . . . . . .

5

Hình II.3:


Minh họa các đơn vị xử lý của mạng nơ-ron nhân tạo. . . . . . . . . . . . . .

5

Hình II.4:

Minh họa mơ hình tốn học của một đơn vị xử lý trong mạng nơ-ron nhân tạo.

6

Hình II.5:

Lan truyền thơng tin trong mạng nơ-ron nhân tạo. [5] . . . . . . . . . . . . . .

7

Hình II.6:

Minh họa hàm khơng lồi Rastrigin trên khơng gian 2 chiều. . . . . . . . . . .

11

Hình II.7:

Minh họa giải thuật tìm kiếm cục bộ. . . . . . . . . . . . . . . . . . . . . . . .

12

Hình II.8:


Các khái niệm trong tối ưu hóa đa mục tiêu. . . . . . . . . . . . . . . . . . . .

14

Hình II.9:

Phân bố con lai theo phép lai ghép phỏng chéo hóa nhị phân. [20] . . . . . . .

17

Hình II.10: Phân bố con sinh ra phép đột biến đa thức. [21] . . . . . . . . . . . . . . . . .

17

Hình II.11: Sự giao hội tập lời giải tối ưu trong tối ưu hóa đa nhiệm vụ. . . . . . . . . . .

21

Hình II.12: Minh họa độ đo ảnh hưởng đa nhiệm. [35] . . . . . . . . . . . . . . . . . . . .

22

Hình III.1:

Minh họa cách cập nhật tham số của GD. . . . . . . . . . . . . . . . . . . . .

25

Hình III.2:


Minh họa GD dưới góc nhìn vật lý. [5] . . . . . . . . . . . . . . . . . . . . . .

27

Hình III.3:

Minh họa một phương pháp mã hóa trực tiếp mạng nơ-ron. [38] . . . . . . . .

29

Hình III.4:

Mã hóa các mạng nơ-ron 1 lớp ẩn trong cùng không gian chung. [54] . . . . .

31

Hình III.5:

Minh họa hiện tượng chia rẽ trong tiến hóa đa nhiệm. [57] . . . . . . . . . . .

32

Hình IV.1:

Mạng nơ-ron 3 lớp với 2 lớp ẩn. . . . . . . . . . . . . . . . . . . . . . . . . . .

34

Hình IV.2:


Mã hóa các mạng nơ-ron nhiều lớp trong cùng không gian chung. . . . . . . .

36

Hình IV.3:

Ý nghĩa của từng gen đối với mỗi tác vụ. . . . . . . . . . . . . . . . . . . . . .

37

Hình V.1:

Kết quả thực nghiệm bài tốn 8-bit, 2 tác vụ, mạng cùng độ sâu. . . . . . . .

45

Hình V.2:

Kết quả thực nghiệm bài toán 8-bit, 3 tác vụ, mạng cùng độ sâu. . . . . . . .

46

Hình V.3:

Kết quả thực nghiệm bài toán 9-bit, 2 tác vụ, mạng cùng độ sâu. . . . . . . .

46

Hình V.4:


Kết quả thực nghiệm bài toán 9-bit, 3 tác vụ, mạng cùng độ sâu. . . . . . . .

47

Hình V.5:

Kết quả thực nghiệm bài toán 10-bit, 2 tác vụ, mạng cùng độ sâu.

. . . . . .

47

Hình V.6:

Kết quả thực nghiệm bài toán 10-bit, 3 tác vụ, mạng cùng độ sâu.

. . . . . .

48

Hình V.7:

Kết quả thực nghiệm bài toán 8-bit, 2 tác vụ, mạng khác độ sâu. . . . . . . .

52

Hình V.8:

Kết quả thực nghiệm bài toán 8-bit, 3 tác vụ, mạng khác độ sâu. . . . . . . .


52

Hình V.9:

Kết quả thực nghiệm bài toán 9-bit, 2 tác vụ, mạng khác độ sâu. . . . . . . .

53

Hình V.10: Kết quả thực nghiệm bài toán 9-bit, 3 tác vụ, mạng khác độ sâu. . . . . . . .

53

Hình V.11: Kết quả thực nghiệm bài tốn 10-bit, 2 tác vụ, mạng khác độ sâu. . . . . . . .

54

Hình V.12: Kết quả thực nghiệm bài tốn 10-bit, 3 tác vụ, mạng khác độ sâu. . . . . . . .

54

X


DANH MỤC BẢNG BIỂU
Bảng II.1: Ví dụ độ tương quan 2 hàm mục tiêu. . . . . . . . . . . . . . . . . . . . . . . .

21

Bảng V.1: Các bài toán phân loại nhị phân dùng trong thực nghiệm. . . . . . . . . . . . .


41

Bảng V.2: Cấu hình mạng nơ-ron tương ứng với mỗi bài toán trong thực nghiệm. . . . . .

42

Bảng V.3: Cấu hình tham số giải thuật đề xuất . . . . . . . . . . . . . . . . . . . . . . . .

43

Bảng V.4: Tổng hợp kết quả bài toán 8-bit, 2 tác vụ và 3 tác vụ, mạng cùng độ sâu. . . .

44

Bảng V.5: Tổng hợp kết quả bài toán 9-bit, 2 tác vụ và 3 tác vụ, mạng cùng độ sâu. . . .

44

Bảng V.6: Tổng hợp kết quả bài toán 10-bit, 2 tác vụ và 3 tác vụ, mạng cùng độ sâu. . .

45

Bảng V.7: Tổng hợp kết quả bộ dữ liệu Breast cancer, 2 tác vụ và 3 tác vụ, mạng cùng độ
sâu. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

48

Bảng V.8: Tổng hợp kết quả bộ dữ liệu Tic tac toe, 2 tác vụ và 3 tác vụ, mạng cùng độ sâu. 49
Bảng V.9: Tổng hợp kết quả bộ dữ liệu Ionosphere, 2 tác vụ và 3 tác vụ, mạng cùng độ sâu. 49

Bảng V.10: Tổng hợp kết quả bộ dữ liệu Credit screening, 2 tác vụ và 3 tác vụ, mạng cùng
độ sâu. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

50

Bảng V.11: Tổng hợp kết quả bài toán 8-bit, 2 tác vụ và 3 tác vụ, mạng khác độ sâu. . . .

50

Bảng V.12: Tổng hợp kết quả bài toán 9-bit, 2 tác vụ và 3 tác vụ, mạng khác độ sâu. . . .

51

Bảng V.13: Tổng hợp kết quả bài toán 10-bit, 2 tác vụ và 3 tác vụ, mạng khác độ sâu. . .

51

Bảng V.14: Tổng hợp kết quả bộ dữ liệu Breast cancer, 2 tác vụ và 3 tác vụ, mạng khác độ
sâu. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

55

Bảng V.15: Tổng hợp kết quả bộ dữ liệu Tic tac toe, 2 tác vụ và 3 tác vụ, mạng khác độ sâu. 55
Bảng V.16: Tổng hợp kết quả bộ dữ liệu Ionosphere, 2 tác vụ và 3 tác vụ, mạng khác độ sâu. 56
Bảng V.17: Tổng hợp kết quả bộ dữ liệu Credit screening, 2 tác vụ và 3 tác vụ, mạng khác
độ sâu. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

56

Bảng V.18: Thời gian chạy trung bình (giây) của các giải thuật cho bài toán 8-bit. . . . . .


58

XI


DANH MỤC GIẢI THUẬT

1

Giải thuật lan truyền tham số mạng nơ-ron nhân tạo L lớp . . . . . . . . . . . . . . . .

9

2

Giải thuật lan truyền ngược cho mạng nơ-ron nhân tạo L lớp . . . . . . . . . . . . . . .

9

3

Các bước chính của giải thuật tiến hóa. . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

4

Các bước chính của giải thuật tiến hóa đa nhiệm vụ.


. . . . . . . . . . . . . . . . . . .

19

5

Ghép cặp tương ứng đa nhiệm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

6

Giải thuật xác định cấu hình mạng nơ-ron chung lớn nhất. . . . . . . . . . . . . . . . .

36

7

Các bước chính của giải thuật MFEA-UDA. . . . . . . . . . . . . . . . . . . . . . . . .

38

8

Phép Lai ghép và Đột biến của MFEA-UDA. . . . . . . . . . . . . . . . . . . . . . . . .

39

9


Chiến lược tự thích nghi xác suất ghép cặp ngẫu nhiên của MFEA-UDA. . . . . . . . .

40

XII


Chương I:
GIỚI THIỆU TỔNG QUAN

Trong những năm gần đây, Mạng nơ-ron nhân tạo (thuật ngữ gốc: Artificial
Neural Network - ANN ) nổi lên như một cơng cụ tốn học hiệu quả trong việc
xây dựng các hệ thống thơng minh có khả năng như thậm chí vượt trội con
người trong nhiều lĩnh vực. Các ví dụ điển hình của ANN có thể được tìm thấy
trong các hệ thống nhận diện (khn mặt, chữ viết tay, số…), hay ở các trò chơi
chiến thuật như cờ vây. ANN về bản chất là một hàm phi tuyến cực kỳ phức
tạp với nhiều lớp và rất nhiều tham số cấu thành. Nhờ đó, ANN có thể xấp xỉ
một hàm mất mát, được xây dựng bằng cách ánh xạ một tập dữ liệu đầu vào
đến một tập dữ liệu đầu ra theo tiêu chuẩn nào đó, với độ chính xác tùy ý và
phụ thuộc vào độ phức tạp của mạng.
Để xây dựng được một ANN, chúng ta cần giải thuật học phù hợp để tìm
được cấu hình mạng cùng bộ tham số tối ưu cho bộ dữ liệu học. Có nhiều
giải thuật dùng để tối ưu trọng số cho một ANN đã biết trước cấu hình như
Backpropagation, Adagrad, RMSprop, Adam… Các giải thuật này đều dựa vào
việc tính đạo hàm để cập nhật tham số và chúng thường có ưu điểm là rất
nhanh chóng hội tụ đến một nghiệm cục bộ hiệu quả nào đó trên khơng gian
tìm kiếm. Tuy nhiên, ưu điểm cũng chính là nhược điểm của các phương pháp
tiếp cận bằng đạo hàm, chúng dễ mắc vào cục bộ khi miền tìm kiếm là đa cực
trị. Hơn thế nữa khi tối ưu trên không gian hàm nhiều biến, tồn tại rất nhiều
những “điểm yên ngựa” nơi mà đạo hàm riêng bằng 0 nhưng lại khơng phải là

cực trị của hàm tại đó. Các thuật toán dựa trên đạo hàm khác nhau đề xuất
các phương pháp riêng để xử lý việc cập nhật tham số khi gặp điểm yên ngựa,
nhưng vẫn không thể tránh khỏi triệt để những vấn đề trong thực nghiệm.
Giải thuật tiến hóa, đã được minh chứng là rất hiệu quả trong các bài toán
tối ưu liên tục, cũng là một ứng cử viên sáng giá trong việc huấn luyện ANN.
Không chỉ loại trừ được những bất lợi của việc cập nhật tham số phải tính đạo
hàm, giải thuật tiến hóa còn giúp việc tối ưu kiến trúc và các thành phần khác
của mạng một cách đồng thời. Giải thuật tiến hóa đa nhiệm, một khái niệm mới
được đề cập gần đây dựa trên cơ sở rằng các bài toán tối ưu có thể có nhiều
điểm chung tương đồng trong tập tối ưu và việc giải cùng lúc nhiều bài tốn
góp phần thúc đẩy tốc độ tìm ra được lời giải tốt nhanh hơn. So với giải thuật
tiến hóa thơng thường, sự trao đổi tri thức dùng chung giữa các nhiệm vụ trong
1


q trình tối ưu góp phần cải thiện tốc độ hội tụ chung của quần thể. Nhờ đó
giải thuật tiến hóa đa nhiệm hứa hẹn là một cơng cụ hiệu quả trong huấn luyện
ANN truyền thẳng.
Các nghiên cứu về giải thuật tiến hóa đa nhiệm cịn nhiều hạn chế và có tiềm
năng phát triển cải tiến. Như vậy, luận văn này tiến hành nghiên cứu tổng quan
về vấn đề huấn luyện ANN truyền thẳng bằng giải thuật tiến hóa đa nhiệm.
Trên cơ sở kết quả đạt được, luận văn tổng kết, đánh giá và đưa ra hướng phát
triển của đề tài trong tương lai.

I.1 Tính cấp thiết của đề tài
Đề tài hướng đến việc phát triển giải thuật học hiệu quả cho việc huấn luyện
ANN, từ đó có ứng dụng to lớn trong các vấn đề thực tiễn đòi hỏi phát triển các
hệ thống thông minh mà ANN là cốt lõi. Kết quả đồ án cũng là minh chứng cho
tính hiệu quả của giải thuật tiến hóa đa nhiệm trong giải quyết các bài toán tối
ưu liên tục phức tạp. Vì các lý do đó mà tơi tin tưởng luận văn này vừa có sự

đóng góp cho cộng đồng nghiên cứu học thuật lại đồng thời có tính ứng dụng
thực tiễn.

I.2 Mục đích và đối tượng nghiên cứu
Luận văn nhằm mục đích nghiên cứu Giải thuật tiến hóa đa nhiệm vụ (thuật
ngữ gốc: Multi-Factorial Evolutionary Algorithm - MFEA) cho bài toán tối ưu
liên tục và vấn đề huấn luyện ANN truyền thẳng nhiều lớp. Trên cơ sở đó, luận
văn đề xuất phương pháp mã hóa trên khơng gian chung cho các ANN truyền
thẳng nhiều lớp đồng thời phát triển và cả tiến giải thuật tiến hóa đa nhiệm để
giải quyết bài tốn. Theo định hướng đó, tác giả cài đặt thực nghiệm giải thuật
đề xuất theo mơ hình đơn nhiệm và đa nhiệm, đồng thời so sánh với các phương
pháp tiếp cận dựa trên đạo hàm để làm cơ sở phân tích tính hiệu quả và tính
thực tiễn của giải thuật đề xuất. Thực nghiệm giải thuật cần chỉ ra và phân tích
được tính hiệu quả của mơ hình đa nhiệm trong huấn luyện đồng thời các ANN
truyền thẳng.

I.3 Phạm vi và phương pháp nghiên cứu
Mơ hình ANN sử dụng trong luận văn là Mạng nơ-ron truyền thẳng (thuật
ngữ gốc: Feedforward Neural Network - FNN ) áp dụng cho bài toán phân loại
nhị phân thực hiện trên bài toán n-bit và bộ dữ liệu phân loại nhị phân của
2


Asuncion and Newman được cung cấp tại [1]. Các giải thuật đề xuất đưọc đánh
giá tính hiệu quả bằng độ đo Trung bình của bình phương lỗi (thuật ngữ gốc:
Mean Square Error - MSE) và tính chính xác của mơ hình phân loại. Việc so
sánh kết quả thực nghiệm là thước đo kiểm chứng tính thực tiễn của giải thuật
đề xuất trong việc phát triển các giải thuật học.

I.4 Cấu trúc của luận văn

Cấu trúc các Chương tiếp theo của luận văn gồm các phần như sau:
• Chương II trình bày các kiến thức tổng quan về ANN, bài toán tối ưu hóa
liên tục (thuật ngữ gốc: continuous optimization), giải thuật Giải thuật tiến
hóa (thuật ngữ gốc: Evolutionary Algorithm - EA) và MFEA.
• Chương III bàn về phương pháp sử dụng EA và MFEA làm giải thuật học
cho ANN cùng các nghiên cứu liên quan.
• Chương IV trình bày chi tiết giải thuật học cho mạng FNN nhiều lớp dựa
trên MFEA.
• Chương V tổng hợp kết quả thực nghiệm giải thuật đề xuất với các phương
pháp tiếp cận dựa trên đạo hàm và EA đơn nhiệm.
• Chương VI đưa ra kết luận về tính hiệu quả và tính thực tiễn của giải thuật
đè xuất, đồng thời bàn luận về các hướng nghiên cứu phát triển của đề tài.

3


Chương II:
CƠ SỞ LÝ THUYẾT
II.1 Tổng quan về mạng nơ-ron
Trong Khoa học máy tính, mạng nơ-ron hay Mạng nơ-ron nhân tạo (thuật
ngữ gốc: Artificial Neural Network - ANN ) là một mơ hình tính tốn, được xây
dựng mơ phỏng theo ý tưởng của các mạng nơ-ron sinh học Hình II.1 (trái).
ANN gồm có một nhóm các nơ-ron nhân tạo (nút) nối với nhau, và xử lý thông
tin bằng cách truyền theo các kết nối và tính giá trị mới tại các nút bằng các
hàm kích hoạt phi tuyến [2]. Hình II.1 (phải) minh họa các thành phần cơ bản
của một nơ-ron trong ANN tương ứng với một nơ-ron sinh học, bao gồm các
đầu vào, trọng số, hàm kích hoạt và đầu ra.

Hình II.1: Cấu trúc nơ-ron sinh học (trái) và mơ hình tốn học tương ứng (phải).


Nguồn: />
Tùy vào lĩnh vực cụ thể và từng dạng dữ liệu đặc thù mà mơ hình của ANN
có thể được phát triển cho phù hợp. Dựa vào kiến trúc mạng mà người ta có
thể phân ra làm 3 dạng ANN chính: Mạng nơ-ron truyền thẳng (thuật ngữ gốc:
Feedforward Neural Network - FNN ), Mạng nơ-ron tích chập (thuật ngữ gốc:
Convolutional Neural Network - CNN ), Mạng nơ-ron hồi qui (thuật ngữ gốc:
Recurrent Neural Network - RNN ). Trong phạm vi nghiên cứu của luận văn,
chúng ta chỉ quan tâm đến FNN. Do đó kể từ đây trở về sau, bất cứ khi nào
nhắc đến thuật ngữ ANN mà khơng có diễn giải gì thêm, chúng ta mặc định
xem nó là FNN.
Một FNN cơ bản bao gồm 3 lớp cấu tạo chính bao gồm: lớp đầu vào (input
layer), lớp đầu ra (output layer) và lớp ẩn (hidden layer). Mục tiêu của FNN là
xấp xỉ một hàm f ∗ sao cho ánh xạ y = f ∗ (x), x ∈ X, y ∈ Y khớp với một bộ dữ
4


liệu X, Y [3]. Khi ấy, lớp đầu vào tương ứng với số chiều của x và tương tự lớp
đầu ra tương ứng với số chiều của y . Để minh họa rõ hơn cách thức hoạt động
của FNN, chúng ta cùng xét đến lớp các bài toán phân loại, vốn là lớp bài toán
kinh điển của lĩnh vực Học máy (thuật ngữ gốc: Machine Learning - ML) [4].
Trong Hình II.2, ta thấy 2 lớp phân loại được gán nhãn dữ liệu xanh và đỏ. Bài
toán đặt ra là khi có một điểm dữ liệu màu xám thì nó được phân vào lớp xanh
hay lớp đỏ?

Hình II.2: Minh họa bài toán phân loại. [5]

Trong mục này, tác giả tổng kết lại cấu trúc và các thành phần cơ bản của
ANN cùng các giải thuật cơ bản cho ANN.
II.1.1 Các thành phần cơ bản của mạng nơ-ron nhân tạo
II.1.1.1 Đơn vị xử lý


Mỗi đơn vị xử lý của ANN là một nút mạng, chúng nhận tín hiệu vào từ các
đơn vị phía trước hay một nguồn bên ngồi và tính tốn tín hiệu ra sẽ được lan
truyền sang các đơn vị khác. Trong một ANN có ba kiểu đơn vị:

Hình II.3: Minh họa các đơn vị xử lý của mạng nơ-ron nhân tạo.

• đơn vị đầu vào (thuật ngữ gốc: input unit): nhận tín hiệu từ bên ngồi.
• đơn vị đầu ra (thuật ngữ gốc: output unit): gửi dữ liệu ra bên ngoài.
5


• đơn vị ẩn (thuật ngữ gốc: hidden unit): tín hiệu vào và ra của nó nằm trong
mạng hay cịn gọi là các đơn vị trung gian.
Mỗi đơn vị có thể có một hoặc nhiều đầu vào, nhưng chỉ có một đầu ra. Một
đầu vào tới một đơn vị có thể là dữ liệu từ bên ngoài mạng, hoặc đầu ra của
một đơn vị khác, hoặc là đầu ra của chính nó. Hình II.4 minh họa chi tiết mơ
hình tốn học của một đơn vị xử lý trong mạng với các thành phần như sau:

Hình II.4: Minh họa mơ hình toán học của một đơn vị xử lý trong mạng nơ-ron nhân tạo.

•
•
•
•

xi : các đầu vào của ANN
wji : các trọng số tương ứng với các đầu vào
θj : độ lệch (thuật ngữ gốc: bias)
σ : hàm kết hợp, được định nghĩa bởi một luật lan truyền cụ thể. Trong


phạm vi luận văn này chúng ta chỉ quan tâm đến luật lan truyền bằng phép
nhân ma trận.
• aj : giá trị trung gian
• g(x) : hàm kích hoạt (thuật ngữ gốc: activation function)
• zj : đầu ra của ANN
II.1.1.2 Hàm kích hoạt

Như minh họa trong Hình II.4, hàm kích hoạt tác động lên giá trị kết hợp
của dữ liệu đầu vào để thu được dữ liệu đầu ra dùng cho lớp tếp theo của ANN.
Thơng thường, hàm kích hoạt được định nghĩa sao cho giá trị đầu ra của nó
được chiếu tương ứng lên khoảng (0, 1) hoặc (−1, 1) và đồng thời đạo hàm của
nó là dễ tính được. Sau đây là tổng hợp một số dạng hàm kích hoạt thường được
sử dụng trong các mơ hình ANN thực tế:
• Hàm đồng nhất (Identity function): f (x) = x
• Hàm bước nhị phân (Binary step function): f (x) = 0 vói x < 0 và f (x) = 1
với x >= 0
1
• Hàm sigmoid (Sigmoid function): f (x) = σ(x) =
1 + exp−x
6


ex − e−x
ex + e−x
• Hàm relu (Rectified linea unit function): f (x) = 0 vói x < 0 và f (x) = x với

• Hàm tanh (Tanh function): f (x) = tanh(x) =
x >= 0


II.1.2 Lan truyền thông tin trong mạng nơ-ron

ANN thực hiện biến đổi thông tin đầu vào thành thông tin đầu ra thông qua
lan truyền thẳng lần lượt qua các lớp ẩn theo như mơ hình tốn học ở Hình II.4.
Xét một ANN L lớp, ta có L ma trận trọng số và độ lệch cho mỗi lớp và ký hiệu
(l)−1
(l)
tương ứng là W (l) ∈ Rd ×d với l = 1, 2, ..., L. Cho rằng lớp đầu tiên là lớp thứ
0 thì W (l) thể hiện các kết nối từ lớp thứ l − 1 đến lớp thứ l. Cụ thể hơn nữa
(l)
thì wij
là trọng số của kết nối từ nút thứ i của lớp l − 1 tới nút thứ j của lớp
(l)
l. Các chỉ số ký hiệu cũng tương tự với độ lệch b(l) ∈ Rd . Xem kỹ minh họa
trong Hình II.5. Tập hợp trọng số cho toàn mạng được ký hiệu là W và b, đây là
tập biến số mà chúng ta phải đi tìm trong quá trình học sao cho thu được một
ANN tốt nhất với bộ dữ liệu [5].

Hình II.5: Lan truyền thơng tin trong mạng nơ-ron nhân tạo. [5]

Mỗi đầu ra của một đơn vị tính tốn (khơng kể đơn vị đầu vào) được tính

7


theo công thức:
(l)

(l)T (l−1)


ai = f (wi

a

(l)

+ bi )

(1)

Khi chuyển sang dạng vec-tơ, ( 1) trở thành:
(l)T (l−1)

a(l) = f (Wi

a

+ b(l) )

(2)

Đầu ra của lớp thứ l khi ấy được tính bằng cơng thức:
a(l) = f (z (l) )

(3)

Hàm f ở đây chính là hàm kích hoạt đã đề cập ở mục trước. Một lưu ý khi
áp dụng hàm kích hoạt cho một vec-tơ, ta áp dụng nó lên từng phần tử để thu
được một vec-tơ tương ứng.
II.1.3 Hàm mất mát


Trong các bài tốn học có giám sát, người ta xây dựng một khái niệm được
gọi là hàm mất mát (thuật ngữ gốc: loss function) để làm mục tiêu cho việc
học [4]. Giả sử với đầu vào x nào đó, thơng qua qua ANN, ta thu được đầu ra
yˆ trong khi đầu ra đúng được gán nhãn là y . Ta ký hiệu ANN bằng một hàm
J(W, b, X, Y ) thì yˆ = J(W, b, X, Y ).
Để đánh giá hiệu quả dự đoán của ANN so với đầu ra chuẩn, ta xây dựng
một hàm mất mát, ký hiệu là L (y, yˆ). Hàm này có nhiệu vụ so sánh, đánh giá
mực độ khớp của đầu ra dự đoán bởi ANN và đầu ra thực tế của nhãn dữ liệu.
Tùy thuộc vào bộ dữ liệu cụ thể và bài toán phân loại khác nhau mà người ta sử
dụng các hàm mất mát kháu nhau. Một ví dụ của hàm mất mát là hàm Trung
bình của bình phương lỗi (thuật ngữ gốc: Mean Square Error - MSE).
1
L (y, yˆ) =
N

N

||yn − yˆn ||22

(4)

n=1

II.1.4 Giải thuật lan truyền ngược trong mạng nơ-ron

Một trong những phương pháp phổ biến để tối ưu hàm mất mát như ở ( 4)
là Đi ngược hướng đạo hàm (thuật ngữ gốc: Gradient Descent - GD). Để làm
được điều đó, ta cần tính được đạo hàm của J theo từng biến cho cả W và b, cụ
∂J

∂J
thể là: ∇W (l) J =
;
∇
với l = 1, 2, .., L. Về cơ bản, giải thuật trải
(l) J =
b
(l)
(l)
∂W

∂b

qua 2 pha chính gồm tính lan truyền tham số chiều thuận (Giải thuật 1) và lan
8


truyền ngược (thuật ngữ gốc: backpropagation) tham số (Giải thuật 2) [3].
Giải thuật 1: Giải thuật lan truyền tham số mạng nơ-ron nhân tạo L lớp

1
2
3
4
5
6
7

Input: Bộ dữ liệu học X, Y ; ANN độ sâu L gồm ma trận trọng số W (l) , l ∈ {1, 2, ...L} và
vec-tơ độ lệch b(l)

Output: Giá trị hàm mất mát
a(0) = x
for l = 1, .., ..L do
(l)
z (l) = W (l)T a(l−1) + bi
a(l) = f (z (l) )
end
yˆ = a(l)
return L (y, yˆ)
Xem hàm mất mát ở Mục II.1.3

Giải thuật 2: Giải thuật lan truyền ngược cho mạng nơ-ron nhân tạo L lớp

1
2
3
4
5
6
7

Input: Bộ dữ liệu học X, Y ; ANN độ sâu L gồm ma trận trọng số W (l) , l ∈ {1, 2, ...L} và
vec-tơ độ lệch b(l) ; giá trị hàm mất mát L (y, yˆ)
Output: Đạo hàm ∇W (l) J và ∇b(l) J theo từng lớp
Tính lan truyền tham số theo Giải thuật 1
Tính đạo hàm cho lớp đầu ra (thuật ngữ gốc: output layer): g ← ∇yˆJ = ∇yˆL (y, yˆ)
for l = L,L-1,...,1 do
Tính đạo hàm theo hàm kích hoạt : g ← ∇z(l) J = g f (z (l) )
Tính đạo hàm theo trọng số: ∇W (l) J = g a(l−1) + ∇W (l) và độ lệch: ∇b(l) J = g + ∇b(l)
Lan truyền ngược: g ← ∇a(l−1) J = W (l)T g

end

Người ta chứng minh rằng, với một hàm liên tục f bất kỳ, tồn tại một ANN
với số lượng lớp ẩn (thuật ngữ gốc: hidden layer) và đơn vị ẩn đủ lớn để có thể
xấp xỉ hàm f với độ chính xác ε tùy ý [3]. Do vậy, vấn đề then chốt là tìm được
bộ tham số W, b thích hợp cho ANN. Việc học của ANN ở đây cũng có thể hiểu
như việc tối ưu bộ trọng số W và độ lệch b sao cho cực tiểu hóa hàm mất mát
L . Theo lẽ đó, tuy có những khác biệt nhất định, việc huấn luyện ANN có thể
được quy về một bài tốn tối ưu trên khơng gian liên tục. Mục tiếp theo sẽ trình
bày tổng quan về bài toán tối ưu liên tục.

II.2 Tổng quan về tối ưu hóa liên tục
Trong tốn học và khoa học máy tính, bài tốn tối ưu hóa (thuật ngữ gốc:
optimization) là bài tốn tìm kiếm lời giải (thuật ngữ gốc: solution) tốt nhất
trong tập tất cả các lời giải khả thi (thuật ngữ gốc: feasible solution). tối ưu hóa
liên tục (thuật ngữ gốc: continuous optimization) [6] là một nhánh của tối ưu
hóa cùng với tối ưu hóa rời rạc (thuật ngữ gốc: discrete optimization) [7], điểm
9


khác nhau giữa chúng duy nhất ở không gian biến quyết định (thuật ngữ gốc:
decision variable) là liên tục hoặc rời rạc.
Về mặt tốn học, tối ưu hóa liên tục là cực tiểu hóa (thuật ngữ gốc: minimization) hoặc cực đại hóa (thuật ngữ gốc: maximization) một hàm liên tục sao
cho thỏa mãn được các ràng buộc của bài toán. Trên thực tế, bài tốn cực tiểu
hóa hay cực đại hóa có thể dễ dàng biến đổi qua lại bằng các phép tốn học đơn
giản. Do vậy, khơng mất tính tổng quát, kể từ đây đến hết luận văn, khi đề cập
đến thuật ngữ tối ưu hóa mà khơng có giải thích bổ sung, ta ngầm định nói về
bài tốn cực tiểu hóa.
Trong phần này, tác giả tổng kết lại định nghĩa bài tốn tối ưu hóa liên tục
cùng một số phương pháp giải và mở rộng sang một số khía cạnh khác của bài

tốn như tối ưu hóa đa biến (thuật ngữ gốc: multi-variate optimization), Tối ưu
hóa đa mục tiêu (thuật ngữ gốc: Multi-Objective Optimization - MOO) và Tối
ưu hóa đa nhiệm vụ (thuật ngữ gốc: Multi-Factorial Optimization - MFO).
II.2.1 Bài tốn tối ưu liên tục

Một cách hình thức, ta có thể định nghĩa bài tốn tối ưu hóa liên tục như
sau [8]:
Định nghĩa 1. Bài toán tối ưu hóa liên tục: cực tiểu hóa hàm f (x), x ∈ Rn ký
hiệu là minn f (x), sao cho gi (x) ≤ 0 với i = 1, ...p và hi (x) = 0 với i = 1, ...q . Trong
x∈R
đó:
• x ∈ Rn là biến quyết định
• f (x) : Rn → R là hàm mục tiêu
• gi (x) ≤ 0 là các ràng buộc bất đẳng thức
• hi (x) = 0 là các ràng buộc đẳng thức
Lời giải của bài toán là nghiệm x∗ ∈ Rn thỏa mãn gi (x∗ ) ≤ 0, hi (x∗ ) = 0 và
f (x∗ ) ≤ f (x)∀x ∈ Rn
Trường hợp p = q = 0 thì ta gọi đó là bài tốn tối ưu hóa liên tục khơng ràng
buộc. Trường hợp hàm f (x) là hàm lồi (thuật ngữ gốc: convex function), tức
thỏa mãn điều kiện: f (αx1 + βx2 ) ≤ αf (x1 ) + βf (x2 ); ∀x1 , x2 ∈ Rn ; ∀α ≥ 0, β ≥
0, α + β = 1, thì ta gọi là bài tốn tối ưu lồi (thuật ngữ gốc: convex optimization)
[9]. Một tính chất quan trọng nhất của bài tốn tối ưu lồi chính là bất kỳ một
điểm tối ưu cục bộ (thuật ngữ gốc: local minima) cũng là một điểm tối ưu toàn
cục (thuật ngữ gốc: global minima). Nói chung, các hàm lồi có thể dễ dàng được
10


tối ưu trong hữu hạn bước với độ phức tạp đa thức [9]. Tuy nhiên các bài toán
thực tế thường không là hàm lồi và phức tạp hơn rất nhiều do chúng thường
có nhiều hơn một tối ưu cục bộ như trong Ví dụ Hình II.2.1. Việc tối ưu ANN

như đã đề cập ở phần trước hầu như đều quy về hàm không lồi. Dẫu vậy các
lý thuyết trong tối ưu lồi vẫn là chìa khóa quan trọng để xây dựng các phương
pháp tối ưu tổng quát.
Ví dụ II.2.1. Hàm Rastrigin: f (x) = An +

n

[x2i − A cos 2πxi ]

i=1

Hình II.6: Minh họa hàm khơng lồi Rastrigin trên khơng gian 2 chiều.

Nguồn: />
II.2.2 Một số phương pháp giải bài toán tối ưu liên tục

Các phương pháp giải quyết bài tốn tối ưu hóa liên tục khơng có ràng buộc
ở dạng tổng quát thường hướng đến coi bài toán ở dạng tìm kiếm hơn là đưa ra
một cơng thức tường minh [8]. Điểm chung của các thuật toán đều xuất phát từ
một lời giải x0 , sau đó thực hiện các chiến lược nhất định để cập nhật x1 , x2 , ...xk
cho tới khi tìm được giá trị f tốt nhất có thể. Các giải thuật chủ yếu khác nhau
về cách thức xây dựng chiến lược cập nhật lời giải từ những lời giải đã duyệt
qua.
II.2.2.1 Phương pháp đưòng tìm kiếm

Phương pháp đường tìm kiếm (thuật ngữ gốc: line search) lựa chọn một hướng
tìm kiếm cố định và cứ theo hướng đó để cập nhật lời giải ở mỗi bước lặp tìm
kiếm theo cơng thức sau:
xk+1 = xk + αk pk


11

(5)


Ở đây, αk là độ dài bước nhảy và pk là hướng cập nhật. Rõ ràng giải thuật có
hiệu quả hay khơng phụ thuộc hồn tồn vào hướng và độ lớn bước nhảy. Theo
lẽ tự nhiên, Phần lớn các giải thuật lựa chọn hướng đi ngược với hướng của đạo
hàm vì điều đó giúp giảm giá trị hàm f cần tối ưu và giúp cho thuật tốn tìm
được một tối ưu cục bộ nhanh nhất có thể [8].
pk = −Bk−1 ∇fk

(6)

Đối với các phương pháp dựa trên GD, Bk là ma trận đơn vị. Trong khi đó đối
với phương pháp Newton, Bk là ma trận Hesian ∇2 f (xk ). Ngoài ra bước nhảy αk
khác nhau cũng tạo nên các thuật tốn khác nhau ví dụ như đi ngược hướng đạo
hàm với bước nhảy sao cho cực tiểu hóa hàm mục tiêu (thuật ngữ gốc: steepest
descent), thay vì sử dụng bước nhảy chỉ theo đạo hàm như trong GD.
II.2.2.2 Phương pháp heuristic

Các phương pháp heuristic được sử dụng rộng rãi trong các bài tốn tối ưu
hóa liên tục bởi tính đơn giản và hiệu quả của chúng trong việc tìm ra một lời
giải khả thi trong khoảng thời gian chấp nhận được.
• Giải thuật tìm kiếm địa phương (thuật ngữ gốc: local search): chiến lưọc
cập nhật lời giải của phương pháp tìm kiếm địa phương được xây dựng dựa
trên việc định nghĩa một vùng cục bộ x − ε, x + ε xung quanh nghiệm hiện
tại. Thông qua các chiến lược lựa chọn một nghiệm trong vùng lân cận này
để cập nhật lời giải mà ta có các phương pháp tìm kiếm cục bộ khác nhau.


Hình II.7: Minh họa giải thuật tìm kiếm cục bộ.

• Giải thuật tiến hóa (thuật ngữ gốc: Evolutionary Algorithm - EA): là một
lớp các thuật tốn tìm kiếm dựa trên quần thể (thuật ngữ gốc: populationbased search) [19]. Khái niệm quần thể ở đây được sử dụng để chỉ một tập
12