Bài giảng Học máy - Bài 8: Các phương pháp học có giám sát (Phần 5) - Nguyễn Nhật Quang

Học Máy
(IT 4862)
ễ hậNguy n N t Quang
quangnn-fit@mail.hut.edu.vn
Trường Đại học Bách Khoa Hà Nội
Viện Công nghệ thông tin và truyền thông
Năm học 2011-2012
Nội d ô hung m n ọc:
„ Giới thiệu chung
„ Đánh giá hiệu năng hệ thống học máy
„ Các phương pháp học dựa trên xác suất 
„ Các phương pháp học có giám sát
„ Học mạng nơron nhân tạo (Artificial neural network) 
„ Các phương pháp học không giám sát
L ộ tᄠọc c ng c
„ Học tăng cường
2
Học Máy – IT 4862 
Mạng nơ-ron nhân tạo – Giới thiệu (1)
„ Mạng nơ-ron nhân tạo (Artificial neural network – ANN)
‰ Mô phỏng các hệ thống nơ-ron sinh học (các bộ não con người) 
‰ ANN là một cấu trúc (structure/network) được tạo nên bởi một số 
lượng các nơ-ron (artificial neurons) liên kết với nhau
„ Mỗi nơ-ron
‰ Có một đặc tính vào/ra
Th hiệ ột tí h t á bộ ( ột hà bộ)‰ ực n m n o n cục m m cục 
„ Giá trị đầu ra của một nơ-ron được xác định bởi
Đặc tính vào/ra của nó‰ 
‰ Các liên kết của nó với các nơ-ron khác
‰ (Có thể) các đầu vào bổ sung
3Học Máy – IT 4862 
Mạng nơ-ron nhân tạo – Giới thiệu (2)
„ ANN có thể được xem như một cấu trúc xử lý thông tin một 
cách phân tán và song song ở mức cao
„ ANN có khả năng học (learn), nhớ lại (recall), và khái quát hóa 
(generalize) từ các dữ liệu học –bằng cách gán và điều chỉnh 
ố(thích nghi) các giá trị trọng s (mức độ quan trọng) của các 
liên kết giữa các nơ-ron
Chứ ă (hà tiê ) ủ ột ANN đ á đị h bởi„ c n ng m mục u c a m ược x c n 
‰ Kiến trúc (topology) của mạng nơ-ron
‰ Đặc tính vào/ra của mỗi nơ ron -
‰ Chiến lược học (huấn luyện)
‰ Dữ liệu học
4Học Máy – IT 4862 
ANN – Các ứng dụng điển hình (1)
„ Xử lý ảnh và Computer vision
‰ Ví dụ: So khớp tiền xử lý phân đoạn và phân tích ảnh computer vision , , , , 
nén ảnh, xử lý và hiểu các ảnh thay đổi theo thời gian
„ Xử lý tín hiệu
Ví d Phâ tí h tí hiệ à hì h thái đị hấ độ đất‰ ụ: n c n u v n a c n, ng 
„ Nhận dạng mẫu
‰ Ví dụ: Trích chọn thuộc tính, phân loại và phân tích tín hiệu ra-đa, nhận 
dạng và hiểu giọng nói, nhận dạng dấu vân tay, nhận dạng ký tự (chữ 
hoặc số), nhận dạng mặt người, và phân tích chữ viết tay
„ Y tế 
‰ Ví dụ: Phân tích và hiểu tín hiệu điện tim, chẩn đoán các loại bệnh, và xử 
lý các ảnh trong lĩnh vực y tế
5Học Máy – IT 4862 
ANN – Các ứng dụng điển hình (2)
„ Các hệ thống quân sự
‰ Ví dụ: Phát hiện thủy lôi phân loại nhiễu ra-đa , 
„ Các hệ thống tài chính
‰ Ví dụ: Phân tích thị trường chứng khoán, đánh giá giá trị bất động sản, 
kiểm tra truy cập thẻ tín dụng kinh doanh cổ phiếu, 
„ Lập kế hoạch, điều khiển, và tìm kiếm
‰ Ví dụ: Cài đặt song song các bài toán thỏa mãn ràng buộc, tìm lời giải
h bài t á ời đ hà điề khiể à kh h hiê ứ ềc o o n ngư ưa ng, u n v oa ọc ng n c u v
người máy (robotics)
„ Các hệ thống năng lượng
‰ Ví dụ: Đánh giá trạng thái hệ thống, phát hiện và khắc phục sự cố, dự
đoán tải (khối lượng) công việc, và đánh giá mức độ an toàn
„ ...(và nhiều lĩnh vực bài toán khác!)
6Học Máy – IT 4862 
Cấu trúc và hoạt động của một nơ-ron
„ Các tín hiệu đầu vào (input 
signals) của nơ-ron (xi, 
i=1 m)
x0=1..
‰ Mỗi tín hiệu đầu vào xi gắn 
với một trọng số wi
„ Trọng số điều chỉnh (bias)
x1
Σx2
w0
w1
w2
Giá trị 
đầw0 (với x0=1)
„ Đầu vào tổng thể (Net 
input) là một hàm tích hợp 
ủ á tí hiệ đầ à
xm
wm
 u ra 
của 
nơ-ron 
(Out)c a c c n u u v o –
Net(w,x)
„ Hàm tác động/truyền 
(Activation/transfer Các tín Đầu vào Hàm tác 
function) tính giá trị đầu ra 
của nơ-ron – f(Net(w,x))
„ Giá trị đầu ra (Output) của 
hiệu đầu 
vào của 
nơ-ron 
( )
tổng thể 
(Net)
động 
(truyền) 
(f)
7Học Máy – IT 4862 
nơ-ron: Out=f(Net(w,x)) x
Đầu vào tổng thể và dịch chuyển
∑∑ mm
„ Đầu vào tổng thể (net input) thường được tính toán bởi một 
hàm tuyến tính
==
=+=++++=
i
ii
i
iimm xwxwwxwxwxwwNet
01
022110 1....
„ Ý nghĩa của tín hiệu dịch chuyển (bias) w0
Họ các hàm phân tách N t không thể phân tách đ ợc các→ e =w1x1 ư 
ví dụ thành 2 lớp (two classes)
→Nhưng: họ các hàm Net=w1x1+w0 có thể!
Net = w1x1
Net Net
Net = w1x1 + w0
x1 x1
8Học Máy – IT 4862 
Hàm tác động: Giới hạn cứng (Hard-limiter)
„ Còn được gọi là hàm ngưỡng 
(threshold function)
ầ ấ ⎩
⎨⎧ ≥== lainguocnêu0
nêu ,1
),(1)(
θθ NetNethlNetOut
„ Giá trị đ u ra l y một trong 2 giá trị
„ θ là giá trị ngưỡng
„ Nhược điểm: không liên tục, đạo 
 ,
),(),(2)( θθ NetsignNethlNetOut ==
OutBinary Out
hàm không liên tục
hard-limiter
1
1
Bipolar 
hard-limiter
θ 0 Net Net0θ
-1
9Học Máy – IT 4862 
Hàm tác động: Logic ngưỡng (Threshold logic)
⎪⎪
⎪
⎨
⎧
−≤≤−+
−<
== θθθα
θ
θα 1if)(
 if ,0
)()( NetNet
Net
NettlNetOut
O t
⎪⎪
⎪
⎩ −> θα
α
1 if ,1
,,,
Net
(α >0)u
1
)))(,1min(,0max( θα += Net
„ Còn được gọi là hàm tuyến tính 
bã hò ( t ti li f ti )
0 Net-θ (1/α)-θ
o a sa ura ng near unc on
„ Kết hợp của 2 hàm tác động: 
tuyến tính và giới hạn chặt
ố
1/α
„ α xác định độ d c của khoảng 
tuyến tính
„ Nhược điểm: Liên tục – nhưng 
đ hà khô liê t
10Học Máy – IT 4862 
ạo m ng n ục
Hàm tác động: Xích-ma (Sigmoidal)
)(1
1),,()( θαθα +−+== NetNetsfNetOut
Out
e
„Được dùng phổ biến nhất
1
„Tham số α xác định độ dốc
„Giá trị đầu ra trong khoảng (0,1)
0-θ Net
0.5
„Ưu điểm
‰ Liên tục, và đạo hàm liên tục
Đ hà ủ ột hà í h‰ ạo m c a m m x c -ma 
được biểu diễn bằng một hàm 
của chính nó
11Học Máy – IT 4862 
Hàm tác động: Hyperbolic tangent
1
1
2
1
1),,tanh()( )()(
)(
−=−== ++
+−
θαθα
θα
θα NetNet
NeteNetNetOut ++ −− ee
Out„ Cũng hay được sử dụng
1
„ Tham số α xác định độ dốc
„ Giá trị đầu ra trong khoảng (-1,1)
0-θ Net
„ Ưu điểm
‰ Liên tục, và đạo hàm liên tục
‰Đạo hàm của một hàm tanh có thể
-1
được biểu diễn bằng một hàm của
chính nó
12Học Máy – IT 4862 
ANN – Kiến trúc mạng (1)
input
bias„Kiến trúc của một ANN được x/đ bởi:
‰ Số lượng các tín hiệu đầu vào và đầu ra
hidden 
layer
‰ Số lượng các tầng
‰ Số lượng các nơ-ron trong mỗi tầng
‰ Số lượng các trọng số (các liên kết) đối 
ỗ
output 
layer
output
với m i nơ-ron
‰Cách thức các nơ-ron (trong một tầng, 
hoặc giữa các tầng) liên kết với nhau
Nhữ à hậ á tí hiệ‰ ng nơ-ron n o n n c c n u 
điều chỉnh lỗi
„Một ANN phải có
ầ ầ
Ví dụ: Một ANN với một tầng ẩn
• Đầu vào: 3 tín hiệu
‰Một t ng đ u vào (input layer)
‰Một tầng đầu ra (output layer)
‰ Không, một, hoặc nhiều tầng ẩn (hidden 
l ( ))
• Đầu ra: 2 giá trị
• Tổng cộng, có 6 neurons
- 4 ở tầng ẩn
13Học Máy – IT 4862 
ayer s - 2 ở tầng đầu ra
ANN – Kiến trúc mạng (2)
„ Một tầng (layer) chứa một nhóm các nơ-ron
„ Tầng ẩn (hidden layer) là một tầng nằm ở giữa tầng đầu
vào (input layer) và tầng đầu ra (output layer)
Cá út ở tầ ẩ (hidd d ) khô t tá t„ c n ng n en no es ng ương c rực
tiếp với môi trường bên ngoài (của mạng nơ-ron)
„ Một ANN được gọi là liên kết đầy đủ (fully connected) 
nếu mọi đầu ra từ một tầng liên kết với mọi nơ-ron của
tầng kế tiếp
14Học Máy – IT 4862 
ANN – Kiến trúc mạng (3)
„ Một ANN được gọi là mạng lan truyền tiến (feed-
forward network) nếu không có bất kỳ đầu ra của một
nút là đầu vào của một nút khác thuộc cùng tầng (hoặc
thuộc một tầng phía trước)
„ Khi các đầu ra của một nút liên kết ngược lại làm các đầu
vào của một nút thuộc cùng tầng (hoặc thuộc một tầng
phía trước) thì đó là một mạng phản hồi (feedback, 
network)
‰ Nếu phản hồi là liên kết đầu vào đối với các nút thuộc cùng tầng, 
thì đó là phản hồi bên (lateral feedback) 
„ Các mạng phản hồi có các vòng lặp kín (closed loops) 
được gọi là các mạng hồi quy (recurrent networks)
15Học Máy – IT 4862 
Kiến trúc mạng – Ví dụ
Mạng lan 
truyền tiến 
ầ
Một nơ-ron với 
phản hồi đến 
một t ng chính nó
Mạng hồi 
quy một 
tầng
Mạng lan 
truyền tiến 
nhiều tầng Mạng hồi 
quy nhiều 
tầng
16Học Máy – IT 4862 
ANN – Các quy tắc học
„ 2 kiểu học trong các mạng nơ-ron nhân tạo
‰ Học tham số (Parameter learning)
→ Mục tiêu là thay đổi thích nghi các trọng số (weights) của các 
liên kết trong mạng nơ-ron
‰ Học cấu trúc (Structure learning) 
→ Mục tiêu là thay đổi thích nghi cấu trúc mạng, bao gồm số 
lượng các nơ-ron và các kiểu liên kết giữa chúng
„ 2 kiểu học này có thể được thực hiện đồng thời hoặc 
riêng rẽ
ầ ắ ể„ Ph n lớn các quy t c học trong ANN thuộc ki u học tham 
số
ố„ Trong bài học này, chúng ta sẽ chỉ xét việc học tham s
17Học Máy – IT 4862 
Quy tắc học trọng số tổng quát
x0= 1
„ Tại bước học (t), mức độ điều
chỉnh vec-tơ trọng số w tỷ lệ
Δw
a neuron
x ...
w0
wj
w1
xj
x1
Out
thuận với tích của tín hiệu học r(t)
và đầu vào x(t)
Δw(t) ~ r(t).x(t)
η
xwmxm
... Learning 
signal 
generator
d
Δw(t) = η.r(t).x(t)
trong đó η (>0) là tốc độ học
(learning rate) 
„ Tín hiệu học r là một hàm của w, 
x, và giá trị đầu ra mong muốn d Lưu ý: xj có thể là:
• một tín hiệu đầu vào, hoặc
r = g(w,x,d) 
„Quy tắc học trọng số tổng quát
Δw(t) = η.g(w(t),x(t),d(t)).x(t)
• một giá trị đầu ra của một nơ-
ron khác
18Học Máy – IT 4862 
Perceptron
x0=1
„ Một perceptron là một kiểu 
đơn giản nhất của ANNs 
x1
x2
w0
w1
Out
(chỉ gồm duy nhất một nơ-
ron)
Σ
xm
w2
wm
⎞⎛ m
„ Sử dụng hàm tác động 
giới hạn chặt
( ) ⎟⎟⎠⎜⎜⎝== ∑=j jj xwsignxwNetsignOut 0),(
„ Đối với một ví dụ x, giá trị 
đầu ra của perceptron là
‰1, nếu Net(w,x)>0
1 ế l i
19Học Máy – IT 4862 
‰ - , n u ngược ạ
Perceptron – Minh họa
Mặt phẳng phân tách 
w0+w1x1+w2x2=0x1
Đầu ra = 1
Đầu ra = -1 
x2
20Học Máy – IT 4862 
Perceptron – Giải thuật học
„ Với một tập các ví dụ học D= {(x,d)}
‰ x là vectơ đầu vào
‰ d là giá trị đầu ra mong muốn (-1 hoặc 1)
„ Quá trình học của perceptron nhằm xác định một vectơ trọng 
số cho phép perceptron sinh ra giá trị đầu ra chính xác ( 1 - 
hoặc 1) cho mỗi ví dụ học
„ Với một ví dụ học x được perceptron phân lớp chính xác, thì 
vectơ trọng số w không thay đổi
„ Nếu d=1 nhưng perceptron lại sinh ra -1 (Out=-1), thì w cần 
được thay đổi sao cho giá trị Net(w x) tăng lên , 
„ Nếu d=-1 nhưng perceptron lại sinh ra 1 (Out=1), thì w cần 
được thay đổi sao cho giá trị Net(w,x) giảm đi
21Học Máy – IT 4862 
Perceptron incremental(D, η)_
Initialize w (wi ← an initial (small) random value)
do
for each training instance (x,d)∈D
Compute the real output value Out
if (Out≠d)
w ← w + η(d-Out)x
end for 
until all the training instances in D are correctly classified
return w
22
Học Máy – IT 4862 
Perceptron batch(D, η)_
Initialize w (wi ← an initial (small) random value)
do
∆w ← 0
for each training instance (x,d)∈D
Compute the real output value Out
if (Out≠d)
∆w ← ∆w + η(d Out)x -
end for
w ← w + ∆w
until all the training instances in D are correctly classified
return w
23
Học Máy – IT 4862 
Perceptron – Giới hạn
„ Giải thuật học cho perceptron được chứng 
minh là hội tụ (converge) nếu: Một perceptron không 
‰ Các ví dụ học là có thể phân tách tuyến 
tính (linearly separable)
‰ Sử dụng một tốc độ học η đủ nhỏ
thể phân lớp chính xác 
đối với tập học này!
„ Giải thuật học perceptron có thể không hội 
tụ nếu như các ví dụ học không thể phân 
tách tuyến tính (not linearly separable)
„ Khi đó, áp dụng quy tắc delta (delta rule)
‰ Đảm bảo hội tụ về một xấp xỉ phù hợp 
nhất của hàm mục tiêu 
‰ Quy tắc delta sử dụng chiến lược 
gradient descent để tìm trong không gian 
giả thiết (các vectơ trọng số) một vectơ 
ố ấ
24Học Máy – IT 4862 
trọng s phù hợp nh t với các ví dụ học
Hàm đánh giá lỗi (Error function)
„ Xét một ANN có n nơ-ron đầu ra
Đối ới ột í d h ( d) iá t ị lỗi h (t i i )
2
„ v m v ụ ọc x, , g r ọc ra n ng error
gây ra bởi vectơ trọng số (hiện tại) w:
( )
12
1)( ∑
=
−=
n
i
ii OutdE wx
Lỗi h â bởi t t ố (hiệ t i) đối ới
∑1
„ ọc g y ra vec ơ rọng s n ạ w v 
toàn bộ tập học D:
∈
=
D
D ED
E
x
x ww )()(
25Học Máy – IT 4862 
Gradient descent
„ Gradient của E (ký hiệu là ∇E) là một vectơ
‰ Có hướng chỉ đi lên (dốc)
⎞⎛
‰ Có độ dài tỷ lệ thuận với độ dốc
„ Gradient ∇E xác định hướng gây ra việc tăng nhanh nhất (steepest 
increase) đối với giá trị lỗi E
⎟⎟⎠⎜
⎜
⎝ ∂
∂
∂
∂
∂
∂=∇
Nw
E
w
E
w
EE ,...,,)(
21
w
trong đó N là tổng số các trọng số (các liên kết) trong mạng
E∂
„ Vì vậy, hướng gây ra việc giảm nhanh nhất (steepest decrease) là
giá trị phủ định của gradient của E
Ni
w
w
i
i ..1 , =∀∂−=Δ ηΔw = -η.∇E(w);
„ Yêu cầu: Các hàm tác động được sử dụng trong mạng phải là các
hàm liên tục đối với các trọng số và có đạo hàm liên tục
26Học Máy – IT 4862 
 , 
Gradient descent – Minh họa
Không gian một chiều Không gian 2 chiều 
E(w) E(w1,w2)
27Học Máy – IT 4862 
Gradient_descent_incremental (D, η)
Initialize w (wi ← an initial (small) random value)
do
for each training instance (x,d)∈D
Compute the network output
for each weight component w i
wi ← wi – η(∂Ex/∂wi)
end for
end for
until (stopping criterion satisfied)
return w
Stopping criterion: Số chu kỳ học (epochs) Ngưỡng lỗi
28
 , , ...
Học Máy – IT 4862 
ANN nhiều tầng và giải thuật lan truyền ngược
„ Một perceptron chỉ có thể biểu diễn một hàm phân tách tuyến tính 
(linear separation function)
„ Một mạng nơ-ron nhiều tầng (multi-layer NN) được học bởi giải thuật 
lan truyền ngược (back-propagation -BP- algorithm) có thể biểu diễn 
một hàm phân tách phi tuyến phức tạp (highly non-linear separation 
function)
„ Giải thuật học BP được sử dụng để học các trọng số của một mạng 
nơ-ron nhiều tầng 
‰ Cấu trúc mạng cố định (các nơ-ron và các liên kết giữa chúng là cố định)
‰ Đối với mỗi nơ-ron, hàm tác động phải có đạo hàm liên tục
Giải th ật BP á d hiế l di t d t t tắ ậ„ u p ụng c n ược gra en escen rong quy c c p 
nhật các trọng số
‰ Để cực tiểu hóa lỗi (khác biệt) giữa các giá trị đầu ra thực tế và các giá trị 
đầu ra mong muốn đối với các ví dụ học
29Học Máy – IT 4862 
 , 
Giải thuật học lan truyền ngược (1)
„ Giải thuật học lan truyền ngược tìm kiếm một vectơ các trọng 
số (weights vector) giúp cực tiểu hóa lỗi tổng thể của hệ
thố đối ới tậ hng v p ọc
„ Giải thuật BP bao gồm 2 giai đoạn (bước)
‰ Giai đoạn lan truyền tiến tín hiệu (Signal forward). Các tín hiệu 
đầu vào (vectơ các giá trị đầu vào) được lan truyền tiến từ tầng
đầu vào đến tầng đầu ra (đi qua các tầng ẩn)
‰ Giai đoạn lan truyền ngược lỗi (Error backward)
„ Căn cứ vào giá trị đầu ra mong muốn của vectơ đầu vào, hệ thống tính
toán giá trị lỗi
„ Bắt đầu từ tầng đầu ra, giá trị lỗi được lan truyền ngược qua mạng, từ
tầng này qua tầng khác (phía trước), cho đến tầng đầu vào
„ Việc lan truyền ngược lỗi (error back-propagation) được thực hiện
thông qua việc tính toán (một cách truy hồi) giá trị gradient cục bộ của
mỗi nơ ron
30Học Máy – IT 4862 
-
Giải thuật học lan truyền ngược (2)
Giai đoạn lan truyền tiến 
tín hiệu:
• Kích hoạt (truyền tín hiệu
qua) mạng 
Giai đoạn lan truyền
ngược lỗi:
• Tính toán lỗi ở đầu ra
• Lan truyền (ngược) lỗi
31Học Máy – IT 4862 
Giải thuật BP – Cấu trúc mạng
x1 xj xm... ...Input xj
„ Xét mạng nơ-ron 3 tầng (trong 
hình vẽ) để minh họa giải thuật 
học BP
Hidden
wqj
(j=1..m)
„ m tín hiệu đầu vào xj (j=1..m)
„ l nơ-ron tầng ẩn zq (q=1..l)
„ n nơ ron đầu ra y (i=1 n) 
neuron zq
(q=1..l)
wiq
Outq
... ...
- i ..
„ wqj là trọng số của liên kết từ 
tín hiệu đầu vào xj tới nơ-ron 
tầng ẩn zq
Out
... ...Output 
neuron yi
(i=1 n)
„ wiq là trọng số của liên kết từ 
nơ-ron tầng ẩn zq tới nơ-ron 
đầu ra yi
i..„ Outq là giá trị đầu ra (cục bộ)
của nơ-ron tầng ẩn zq
„ Outi là giá trị đầu ra của mạng
tương ứng với nơ ron đầu ra y
32Học Máy – IT 4862 
 - i
Giải thuật BP – Lan truyền tiến (1)
„ Đối với mỗi ví dụ học x
‰ Vectơ đầu vào x được lan truyền từ tầng đầu vào đến tầng đầu ra
‰ Mạng sẽ sinh ra một giá trị đầu ra thực tế (actual output) Out (là 
một vectơ của các giá trị Outi, i=1..n)
ố ầ ầ ẩ
m
„ Đ i với một vectơ đ u vào x, một nơ-ron zq ở t ng n sẽ 
nhận được giá trị đầu vào tổng thể (net input) bằng:
∑
=
=
j
jqjq xwNet
1
và sinh ra một giá trị đầu ra (cục bộ) bằng:
⎟⎟⎠
⎞
⎜⎜⎝
⎛== ∑
=
m
j
jqjqq xwfNetfOut
1
)(
trong đó f( ) là hàm tác động (activation function) của nơ ron z
33Học Máy – IT 4862 
 . - q
Giải thuật BP – Lan truyền tiến (2)
„ Giá trị đầu vào tổng thể (net input) của nơ-ron yi ở tầng 
đầu ra
∑ ∑∑
= == ⎟
⎟
⎠
⎞
⎜⎜⎝
⎛==
l
q
m
j
jqjiq
l
q
qiqi xwfwOutwNet
1 11
⎞⎛ ⎞⎛⎞⎛ ll
„ Nơ-ron yi sinh ra giá trị đầu ra (là một giá trị đầu ra của 
mạng)
⎟⎟⎠⎜
⎜
⎝ ⎟
⎟
⎠⎜
⎜
⎝
=⎟⎟⎠⎜
⎜
⎝
== ∑ ∑∑
= == q
m
j
jqjiq
q
qiqii xwfwfOutwfNetfOut
1 11
)(
„ Vectơ các giá trị đầu ra Outi (i=1..n) chính là giá trị đầu ra 
thực tế của mạng, đối với vectơ đầu vào x
34Học Máy – IT 4862 
Giải thuật BP – Lan truyền ngược (1)
„ Đối với mỗi ví dụ học x
‰ Các tín hiệu lỗi (error signals) do sự khác biết giữa giá trị đầu ra 
mong muốn d và giá trị đầu ra thực tế Out được tính toán
‰ Các tín hiệu lỗi này được lan truyền ngược (back-propagated) từ 
tầng đầu ra tới các tầng phía trước, để cập nhật các trọng số 
(weights)
„ Để xét các tín hiệu lỗi và việc lan truyền ngược của 
( ) ( ) ( )[ ]∑∑ −=−= n iin ii NetfdOutdwE 22 2121
chúng, cần định nghĩa một hàm đánh giá lỗi
== ii 11
∑ ∑ ⎥⎥⎦
⎤
⎢⎢⎣
⎡
⎟⎟⎠
⎞
⎜⎜⎝
⎛−=
n
i
l
q
qiqi Outwfd
1
2
12
1
= =
35Học Máy – IT 4862 
Giải thuật BP – Lan truyền ngược (2)
„ Theo phương pháp gradient-descent, các trọng số của các liên
kết từ tầng ẩn tới tầng đầu ra được cập nhật bởi
iq
iq w
Ew ∂
∂−=Δ η
Sử d tắ h ỗi đ hà đối ới ∂E/∂ t ó
[ ] ( )[ ][ ] qiqiii
iq
i
i
i
i
iq OutOutNetfOutdw
Net
Net
Out
Out
Ew ηδηη =−=⎥⎥⎦
⎤
⎢⎢⎣
⎡
∂
∂⎥⎦
⎤⎢⎣
⎡
∂
∂⎥⎦
⎤⎢⎣
⎡
∂
∂−=Δ '
„ ụng quy c c u ạo m v wiq, a c
(Lưu ý: dấu “–” đã được kết hợp với giá trị ∂E/∂Outi)
„ δi là tín hiệu lỗi (error signal) của nơ-ron yi ở tầng đầu ra
[ ] ( )[ ]iii
i
i
ii
i NetfOutdNet
Out
Out
E
Net
E '−=⎥⎦
⎤⎢⎣
⎡
∂
∂⎥⎦
⎤⎢⎣
⎡
∂
∂−=∂
∂−=δ
trong đó Neti là đầu vào tổng thể (net input) của nơ-ron yi ở tầng
36Học Máy – IT 4862 
đầu ra, và f'(Neti)=∂f(Neti)/∂Neti
Giải thuật BP – Lan truyền ngược (3)
„ Để cập nhật các trọng số của các liên kết từ tầng đầu
vào tới tầng ẩn chúng ta cũng áp dụng phương pháp
⎤⎡∂⎤⎡∂⎤⎡ ∂∂ N tO tEE
, 
gradient-descent và quy tắc chuỗi đạo hàm
⎥⎥⎦⎢
⎢
⎣ ∂⎥
⎥
⎦⎢
⎢
⎣ ∂⎥
⎥
⎦⎢
⎢
⎣∂
−=∂−=Δ qj
q
q
q
qqj
qj w
e
Net
u
Outw
w ηη
ỗ ấ ằ ỗ
2
„ Từ công thức tính hàm l i E(w), ta th y r ng m i thành
phần lỗi (di-yi) (i=1..n) là một hàm của Outq
∑ ∑
= = ⎥⎥⎦
⎤
⎢⎢⎣
⎡
⎟⎟⎠
⎞
⎜⎜⎝
⎛−=
n
i
l
q
qiqi OutwfdE
1 12
1)(w
37Học Máy – IT 4862 
Giải thuật BP – Lan truyền ngược (4)
n
„ Áp dụng quy tắc chuỗi đạo hàm, ta có
( ) ( )[ ] ( ) jq
i
iqiiiqj xNetfwNetfOutdw ''
1
∑
=
−=Δ η
[ ] ( )n xxNetfw ηδδη∑ ' jqjq
i
iqi ==
=1
„ δq là tín hiệu lỗi (error signal) của nơ-ron zq ở tầng ẩn
( ) iqn
i
iq
q
q
qq
q wNetfNet
Out
Out
E
Net
E ∑
=
=⎥⎥⎦
⎤
⎢⎢⎣
⎡
∂
∂
⎥⎥⎦
⎤
⎢⎢⎣
⎡
∂
∂−=∂
∂−=
1
' δδ
trong đó Netq là đầu vào tổng thể (net input) của nơ-ron zq ở tầng 
ẩn, và f'(Netq)=∂f(Netq)/∂Netq
38Học Máy – IT 4862 
Giải thuật BP – Lan truyền ngược (5)
„ Theo các công thức tính các tín hiệu lỗi δi và δq đã nêu, thì tín 
hiệu lỗi của một nơ-ron ở tầng ẩn khác với tín hiệu lỗi của một 
nơ-ron ở tầng đầu ra
„ Do sự khác biệt này, thủ tục cập nhật trọng số trong giải thuật 
BP được gọi là quy tắc học delta tổng quát 
„ Tín hiệu lỗi δq của nơ-ron zq ở tầng ẩn được xác định bởi
‰ Các tín hiệu lỗi δi của các nơ-ron yi ở tầng đầu ra (mà nơ-ron zq
liên kết tới) và , 
‰ Các hệ số chính là các trọng số wiq
„ Đặc điểm quan trọng của giải thuật BP: Quy tắc cập 
nhật trọng số có tính cục bộ
‰ Để tính toán thay đổi (cập nhật) trọng số của một liên kết, hệ 
thống chỉ cần sử dụng các giá trị ở 2 đầu của liên kết đó!
39Học Máy – IT 4862 
Giải thuật BP – Lan truyền ngược (6)
„ Quá trình tính toán tín hiệu lỗi (error signals) như trên có 
thể được mở rộng (khái quát) dễ dàng đối với mạng nơ-
ron có nhiều hơn 1 tầng ẩn
„ Dạng tổng quát của quy tắc cập nhật trọng số trong giải 
thuật BP là:
Δwab = ηδaxb
‰ b và a là 2 chỉ số tương ứng với 2 đầu của liên kết (b→a) (từ một 
nơ-ron (hoặc tín hiệu đầu vào) b đến nơ-ron a)
‰ xb là giá trị đầu ra của nơ-ron ở tầng ẩn (hoặc tín hiệu đầu vào) b , 
‰ δa là tín hiệu lỗi của nơ-ron a
40Học Máy – IT 4862 
Back_propagation_incremental(D, η)
Mạng nơ-ron gồm Q tầng, q = 1,2,...,Q
qNeti và qOuti là đầu vào tổng thể (net input) và giá trị đầu ra của nơ-ron i ở tầng q
Mạng có m tín hiệu đầu vào và n nơ-ron đầu ra
qwij là trọng số của liên kết từ nơ-ron j ở tầng (q-1) đến nơ-ron i ở tầng q
Bước 0 (Khởi tạo)
Chọn ngưỡng lỗi Ethreshold (giá trị lỗi có thể chấp nhận được)
Khởi tạo giá trị ban đầu của các trọng số với các giá trị nhỏ ngẫu nhiên 
Gán E=0
Bước 1 (Bắt đầu một chu kỳ học)
Á d t đầ à ủ í d h k đối ới tầ đầ à ( 1)p ụng vec ơ u v o c a v ụ ọc v ng u v o q=
qOuti = 1Outi = xi(k), ∀i
Bước 2 (Lan truyền tiến)
( ) ⎟⎟⎞⎜⎜⎛== ∑ − jqijqiqiq OutwfNetfOut 1
Lan truyền tiến các tín hiệu đầu vào qua mạng, cho đến khi nhận được các
giá trị đầu ra của mạng (ở tầng đầu ra) QOuti
⎠⎝ j
41
Học Máy – IT 4862 
Bước 3 (Tính toán lỗi đầu ra)
Tính toán lỗi đầu ra của mạng và tín hiệu lỗi Qδi của mỗi nơ-ron ở tầng đầu ra
∑
=
−+=
n
i
i
Qk
i OutdEE
1
2)( )(
2
1
)Net'()fOut(dδ QQ(k)Q −= iiii
Bước 4 (Lan truyền ngược lỗi)
Lan truyền ngược lỗi để cập nhật các trọng số và tính toán các tín hiệu lỗi q-1δi
cho các tầng phía trước
2,...,1, allfor ;11 −== ∑−− QQqδw)Net'(fδ jqjiqiqiq
Δqwij = η.(qδi).(q-1Outj); qwij = qwij + Δqwij
jBước 5 (Kiểm tra kết thúc một chu kỳ học – epoch)
Kiểm tra xem toàn bộ tập học đã được sử dụng (đã xong một chu kỳ học – epoch)
Nếu toàn bộ tập học đã được dùng, chuyển đến Bước 6; ngược lại, chuyển đến Bước 1
Bước 6 (Kiểm tra lỗi tổng thể)
Nếu lỗi tổng thể E nhỏ hơn ngưỡng lỗi chấp nhận được (<Ethreshold), thì quá trình học kết
thúc và trả về các trọng số học được;
42
Học Máy – IT 4862 
Ngược lại, gán lại E=0, và bắt đầu một chu kỳ học mới (quay về Bước 1)
Giải thuật BP – Lan truyền tiến (1)
f(Net1)
1x f(Net4)
f(Net2)
Out6f(Net6)
2x f(Net5)
f(Net3)
43Học Máy – IT 4862 
Giải thuật BP – Lan truyền tiến (2)
11 xw
f(Net1)
1x
1x
21 2
xw x f(Net4)
Out6
f(Net2)
f(Net6)
2x f(Net5)
)( 21111 21 xwxwfOut xx +=f(Net3)
44Học Máy – IT 4862 
Giải thuật BP – Lan truyền tiến (3)
f(Net1)
1x f(Net4)
12 1
xw x
Out6
f(Net2)
f(Net6)
2x
22 2
xw x f(Net5)
)( 22122 21 xwxwfOut xx +=f(Net3)
45Học Máy – IT 4862 
Giải thuật BP – Lan truyền tiến (4)
f(Net1)
1x f(Net4)
Out6
f(Net2)
f(Net6)
2x 13 1 xw x f(Net5)
23 2
xw x )( 23133 21 xwxwfOut xx +=f(Net3)
46Học Máy – IT 4862 
Giải thuật BP – Lan truyền tiến (5)
Outwf(Net1)
1x
242Outw
141
f(Net4)
343Outw
Out6
f(Net2)
f(Net6)
2x f(Net5)
)( 3432421414 OutwOutwOutwfOut ++=
f(Net3)
47Học Máy – IT 4862 
Giải thuật BP – Lan truyền tiến (6)
f(Net1)
1x 151Outw f(Net4)
O t
Out6
f(Net2)
f(Net6)
2x
252 uw
f(Net5)
353Outw
)( 3532521515 OutwOutwOutwfOut ++=
f(Net3)
48Học Máy – IT 4862 
Giải thuật BP – Lan truyền tiến (7)
f(Net1)
1x
464Outw
f(Net4)
Out6
f(Net2)
f(Net6)
2x
565Outwf(Net5)
)( 5654646 OutwOutwfOut +=f(Net3)
49Học Máy – IT 4862 
Giải thuật BP – Tính toán lỗi
f(Net1)
1x f(Net4) δ6
Out6
f(Net2)
f(Net6)
2x f(Net5) d is the desired
[ ] ( )[ ]6666 ' NetfOutdN t
Out
O t
E
N t
E −=⎥⎦
⎤⎢⎣
⎡
∂
∂⎥⎦
⎤⎢⎣
⎡
∂
∂−=∂
∂−=δ
f(Net3)
output value
666 eue
50Học Máy – IT 4862 
Giải thuật BP – Lan truyền ngược (1)
δf(Net1)
1x
64w δ
4
f(Net4)
6
Out6
f(Net2)
f(Net6)
2x f(Net5)
)δ)(w(Netfδ 66444 '=
f(Net3)
51Học Máy – IT 4862 
Giải thuật BP – Lan truyền ngược (2)
f(Net1)
1x δ6f(Net4)
δ5
Out6
f(Net2)
f(Net6)
2x
65w
f(Net5)
)δ)(w'(Netfδ 66555 =f(Net3)
52Học Máy – IT 4862 
Giải thuật BP – Lan truyền ngược (3)
δ1
f(Net )
1x
41w
51w
δ41
f(Net4)
Out6
f(Net ) f(Net6)
x
δ52
f(Net5)
2
)δwδ)(w'(Netfδ 55144111 +=f(Net3)
53Học Máy – IT 4862 
Giải thuật BP – Lan truyền ngược (4)
δ4f(Net1)
1x
42wδ
f(Net4)
52w δ
2 Out6
f(Net2)
f(Net6)
2x
5
f(Net5)
)δwδ)(w'(Netfδ 55244222 +=f(Net3)
54Học Máy – IT 4862 
Giải thuật BP – Lan truyền ngược (5)
δ4f(Net1)
1x f(Net4)
43w δ
Out6
f(Net2)
f(Net6)
2x 53w
5
δ
f(Net5)
)δwδ)(w'(Netfδ 55344333 +=
3
f(Net3)
55Học Máy – IT 4862 
Giải thuật BP – Cập nhật trọng số (1)
1w
δ1
f(Net1)
1x
1x
1xw f(Net4)2
Out6
f(Net2)
f(Net6)
2x f(Net5)
1111 11
xww
xww xx
ηδ
ηδ
+=
+=
f(Net3)
2111 22 xx
56Học Máy – IT 4862 
Giải thuật BP – Cập nhật trọng số (2)
f(Net1)
1x
δ
f(Net4)
12x
w 2 Out6
f(Net2)
f(Net6)
2x
22x
w
f(Net5)
2222
1222 11
xww
xww xx
ηδ
ηδ
+=
+=
f(Net3)
22 xx
57Học Máy – IT 4862 
Giải thuật BP – Cập nhật trọng số (3)
f(Net1)
1x f(Net4)
Out6
f(Net2)
f(Net6)
2x 13xw δ3
f(Net5)
23x
w
2333
1333 11
xww
xww
xx
xx
ηδ
ηδ
+=
+=
f(Net3)
22
58Học Máy – IT 4862 
Giải thuật BP – Cập nhật trọng số (4)
w δ4
f(Net1)
1x
42w
41
f(Net4)
43w
Out6
f(Net2)
f(Net6)
2x
Outww ηδ+
f(Net5)
244242
144141
Outww
Outww
ηδ
ηδ
+=
+=
=
f(Net3)
344343
59Học Máy – IT 4862 
Giải thuật BP – Cập nhật trọng số (5)
f(Net1)
1x f(Net4)
51w δ5
Out6
f(Net2)
f(Net6)
2x 52
w
Outww ηδ+
f(Net5)
53w
255252
155151
Outww
Outww
ηδ
ηδ
+=
+=
=
f(Net3)
355353
60Học Máy – IT 4862 
Giải thuật BP – Cập nhật trọng số (6)
f(Net1)
1x
64w δ6
f(Net4)
Out6
f(Net2)
f(Net6)
2x
65w
f(Net5)
466464
Outηδww
Outηδww
+=
+=f(Net3)
566565
61Học Máy – IT 4862 
BP: Khởi tạo giá trị của các trọng số
„ Thông thường, các trọng số được khởi tạo với các giá trị nhỏ
ngẫu nhiên
„ Nếu các trọng số có các giá trị ban đầu lớn
‰ Các hàm xích-ma (sigmoid functions) sẽ đạt trạng thái bão hòa sớm
‰ Hệ thống sẽ tắc ở một điểm cực tiểu cục bộ (local minimum) hoặc ở 
một trạng thái không đổi (very flat plateau) gần điểm bắt đầu
„ Các gợi ý cho w0 b (liên kết từ nơ-ron b tới nơ-ron a) a
‰ Ký hiệu na là số lượng các nơ-ron ở cùng tầng với nơ-ron a
w0ab ∈ [−1/na, 1/na]
]k/k/[w ab 330 −∈
‰ Ký hiệu ka là số lượng các nơ-ron có liên kết (tiến) đến nơ-ron a
(=số lượng các liên kết đầu vào của nơ-ron a)
, aa
62Học Máy – IT 4862 
BP: Tốc độ học (Learning rate)
„ Ảnh hưởng quan trọng đến hiệu quả và khả năng hội tụ của giải thuật học
BP
Một iá t ị lớ ó thể đẩ h h hội t ủ á t ì h h h ó‰ g r η n c y n an sự ụ c a qu r n ọc, n ưng c
thể làm cho hệ thống bỏ qua điểm tối ưu toàn cục hoặc rơi vào điểm tối
ưu cục bộ
‰ Một giá trị η nhỏ có thể làm cho quá trình học kéo dài rất lâu 
„ Thường được chọn theo thực nghiệm (experimentally) đối với mỗi bài toán
„ Các giá trị tốt của tốc độ học ở lúc bắt đầu (quá trình học) có thể không tốt ở 
một thời điểm sau đấy
‰ Nên sử dụng một tốc độ học thích nghi (động)
„ Sau khi cập nhật các trọng số, kiểm tra xem việc cập nhật các trọng số có
giúp làm giảm giá trị lỗi
Δη =
a , if ΔE < 0 consistently
-bη , if ΔE > 0 (a, b > 0)
0 , otherwise.
63Học Máy – IT 4862 
BP: Momentum
-η∇E(t’+1) + αΔw(t’)
αΔw(t’) -η∇E(t’+1)
Δw(t’) B
„ Phương pháp Gradient descent có
thể rất chậm nếu η nhỏ, và có thể
d độ h ế á lớ 
A’ A
Δw(t)
ao ng mạn n u η qu n
„ Để giảm mức độ dao động, cần
đưa vào một thành phần
B’
∇E(t+1) + Δ (t)
αΔw(t)
-η∇E(t+1)
momentum
Δw(t) = -η∇E(t) + αΔw(t-1)
trong đó α (∈[0,1]) là một tham số -η α w
Gradient descent đối với một hàm
lỗi bậc 2 đơn giản.
momentum (thường lấy =0.9)
„ Một quy tắc, dựa trên các thí
nghiệm để chọn các giá trị hợp lý
Quỹ đạo bên trái không sử dụng
momentum.
Quỹ đạo bên phải có sử dụng
, 
cho tốc độ học và momentum là:
(η+α) >≈ 1; trong đó α>η để tránh
dao động
momentum.
64Học Máy – IT 4862 
BP: Số lượng các nơ-ron ở tầng ẩn
„ Kích thước (số nơ-ron) của tầng ẩn là một câu hỏi quan trọng 
đối với việc áp dụng các mạng nơ-ron lan truyền tiến nhiều tầng
ể ế ếđ giải quy t các bài toán thực t
„ Trong thực tế, rất khó để xác định chính xác số lượng các nơ-
ron cần thiết để đạt được một độ chính xác mong muốn của hệ
thống
„ Kích thước của tầng ẩn thường được xác định qua thí nghiệm
(experimentally/trial and test) 
„ Gợi ý
‰ Bắt đầu với số lượng nhỏ các nơ-ron ở tầng ẩn (=tỷ lệ nhỏ so với số
lượng các tín hiệu đầu vào)
‰ Nếu mạng không thể hội tụ, bổ sung thêm các nơ-ron vào tầng ẩn
‰ Nếu mạng hội tụ có thể xem xét sử dụng ít hơn các nơ-ron tầng ẩn
65Học Máy – IT 4862 
, 
ANNs – Giới hạn học
„ Các hàm nhị phân (Boolean functions)
ấ ể‰ B t kỳ hàm nhị phân nào cũng có th học được bởi một ANN sử 
dụng 1 tầng ẩn
Cá hà liê t (C ti f ti )„ c m n ục on nuous unc ons
‰ Bất kỳ một hàm liên tục bị giới hạn (bounded continuous function) 
nào cũng có thể học được (xấp xỉ) bởi một ANN sử dụng 1 tầng 
ẩn [Cybenko, 1989; Hornik et al., 1989]
‰ Bất kỳ một hàm mục tiêu nào cũng có thể học được (xấp xỉ) bởi 
một ANN sử dụng 2 tầng ẩn [Cybenko 1988] , 
66Học Máy – IT 4862 
ANNs – Ưu điểm, Nhược điểm
„ Các ưu điểm
‰ Bản chất (về cấu trúc) hỗ trợ tính toán song song ở mức (rất) cao 
‰ Khả năng chịu nhiễu/lỗi, nhờ kiến trúc tính toán song song
‰ Có thể được thiết kế để tự thích nghi (các trọng số, cấu trúc mạng)
„ Các nhược điểm
‰ Không có quy tắc tổng quát để xác định cấu trúc mạng và các 
th ố h tối h ột (lớ ) bài t á hất đị ham s ọc ưu c o m p o n n n
‰ Không có phương pháp tổng quát để đánh giá hoạt động bên 
trong của ANN (vì vậy, hệ thống ANN bị xem như một “hộp đen”)
‰ Rất khó (không thể) đưa ra giải thích cho người dùng
‰ Rất khó để dự đoán hiệu năng của hệ thống trong tương lai (khả 
năng khái quát hóa của hệ thống học)
67Học Máy – IT 4862 
ANNs – Khi nào?
„ Mỗi ví dụ được biểu diễn bởi một tập gồm (rất) nhiều 
thuộc tính kiểu rời rạc hoặc kiểu số 
„ Miền giá trị đầu ra của hàm mục tiêu có kiểu số thực, hoặc 
kiểu rời rạc, hoặc kiểu vectơ 
„ Tập dữ liệu có thể chứa nhiễu/lỗi
„ Dạng của hàm mục tiêu không xác định (biết) trước 
„ Không cần thiết (hoặc không quan trọng) phải đưa ra giải 
thích cho người dùng đối với các kết quả
„ Chấp nhận thời gian (khá) lâu cho quá trình huấn luyện
„ Yêu cầu thời gian (khá) nhanh cho việc phân loại/dự đoán 
68Học Máy – IT 4862