1|Page

Bài 7: Gradient Descent (phần 1/2)

1. Giới thiệu

Các bạn hẳn thấy hình vẽ dưới đây quen thuộc:

Điểm màu xanh lục là điểm local minimum (cực tiểu), và cũng là điểm làm cho hàm số đạt giá trị nhỏ
nhất. Từ đây trở đi, tôi sẽ dùng local minimum để thay cho điểm cực tiểu, global minimum để thay
cho điểm mà tại đó hàm số đạt giá trị nhỏ nhất. Global minimum là một trường hợp đặc biệt của local
minimum.

Giả sử chúng ta đang quan tâm đến một hàm số một biến có đạo hàm mọi nơi. Xin cho tôi được nhắc
lại vài điều đã quá quen thuộc:

1. Điểm local minimum x∗x∗ của hàm số là điểm có đạo hàm f′(x∗)f′(x∗) bằng 0. Hơn thế nữa,
trong lân cận của nó, đạo hàm của các điểm phía bên trái x∗x∗ là không dương, đạo hàm của
các điểm phía bên phải x∗x∗ là không âm.
2. Đường tiếp tuyến với đồ thị hàm số đó tại 1 điểm bất kỳ có hệ số góc chính bằng đạo hàm của
hàm số tại điểm đó.

Trong hình phía trên, các điểm bên trái của điểm local minimum màu xanh lục có đạo hàm âm, các
điểm bên phải có đạo hàm dương. Và đối với hàm số này, càng xa về phía trái của điểm local minimum
thì đạo hàm càng âm, càng xa về phía phải thì đạo hàm càng dương.

Gradient Descent

Trong Machine Learning nói riêng và Toán Tối Ưu nói chung, chúng ta thường xuyên phải tìm giá trị
nhỏ nhất (hoặc đôi khi là lớn nhất) của một hàm số nào đó. Ví dụ như các hàm mất mát trong hai
bài Linear Regression và K-means Clustering. Nhìn chung, việc tìm global minimum của các hàm mất
mát trong Machine Learning là rất phức tạp, thậm chí là bất khả thi. Thay vào đó, người ta thường cố
gắng tìm các điểm local minimum, và ở một mức độ nào đó, coi đó là nghiệm cần tìm của bài toán.

Các điểm local minimum là nghiệm của phương trình đạo hàm bằng 0. Nếu bằng một cách nào đó có
thể tìm được toàn bộ (hữu hạn) các điểm cực tiểu, ta chỉ cần thay từng điểm local minimum đó vào
hàm số rồi tìm điểm làm cho hàm có giá trị nhỏ nhất (đoạn này nghe rất quen thuộc, đúng không?).
Tuy nhiên, trong hầu hết các trường hợp, việc giải phương trình đạo hàm bằng 0 là bất khả thi. Nguyên
nhân có thể đến từ sự phức tạp của dạng của đạo hàm, từ việc các điểm dữ liệu có số chiều lớn, hoặc
từ việc có quá nhiều điểm dữ liệu.

Hướng tiếp cận phổ biến nhất là xuất phát từ một điểm mà chúng ta coi là gần với nghiệm của bài toán,
sau đó dùng một phép toán lặp để tiến dần đến điểm cần tìm, tức đến khi đạo hàm gần với 0. Gradient
Descent (viết gọn là GD) và các biến thể của nó là một trong những phương pháp được dùng nhiều
nhất.
2|Page

Vì kiến thức về GD khá rộng nên tôi xin phép được chia thành hai phần. Phần 1 này giới thiệu ý tưởng
phía sau thuật toán GD và một vài ví dụ đơn giản giúp các bạn làm quen với thuật toán này và vài khái
niệm mới. Phần 2 sẽ nói về các phương pháp cải tiến GD và các biến thể của GD trong các bài toán
mà số chiều và số điểm dữ liệu lớn. Những bài toán như vậy được gọi là large-scale.

2. Gradient Descent cho hàm 1 biến

Quay trở lại hình vẽ ban đầu và một vài quan sát tôi đã nêu. Giả sử xtxt là điểm ta tìm được sau vòng
lặp thứ tt. Ta cần tìm một thuật toán để đưa xtxt về càng gần x∗x∗ càng tốt.
Trong hình đầu tiên, chúng ta lại có thêm hai quan sát nữa:

1. Nếu đạo hàm của hàm số tại xtxt: f′(xt)>0f′(xt)>0 thì xtxt nằm về bên phải so với x∗x∗ (và ngược
lại). Để điểm tiếp theo xt+1xt+1 gần với x∗x∗ hơn, chúng ta cần di chuyển xtxt về phía bên trái,
tức về phía âm. Nói các khác, chúng ta cần di chuyển ngược dấu với đạo
hàm:xt+1=xt+Δxt+1=xt+ΔTrong đó ΔΔ là một đại lượng ngược dấu với đạo hàm f′(xt)f′(xt).
2. xtxt càng xa x∗x∗ về phía bên phải thì f′(xt)f′(xt) càng lớn hơn 0 (và ngược lại). Vậy, lượng di
chuyển ΔΔ, một cách trực quan nhất, là tỉ lệ thuận với −f′(xt)−f′(xt).
Hai nhận xét phía trên cho chúng ta một cách cập nhật đơn giản là:xt+1=xt−ηf′(xt)xt+1=xt−ηf′(xt)
Trong đó ηη (đọc là eta) là một số dương được gọi là learning rate (tốc độ học). Dấu trừ thể hiện việc
chúng ta phải đi ngược với đạo hàm (Đây cũng chính là lý do phương pháp này được gọi là Gradient
Descent - descent nghĩa là đi ngược). Các quan sát đơn giản phía trên, mặc dù không phải đúng cho
tất cả các bài toán, là nền tảng cho rất nhiều phương pháp tối ưu nói chung và thuật toán Machine
Learning nói riêng.

Ví dụ đơn giản với Python

Xét hàm số f(x)=x2+5sin(x)f(x)=x2+5sin⁡(x) với đạo hàm f′(x)=2x+5cos(x)f′(x)=2x+5cos⁡(x) (một lý do

tôi chọn hàm này vì nó không dễ tìm nghiệm của đạo hàm bằng 0 như hàm phía trên). Giả sử bắt đầu
từ một điểm x0x0 nào đó, tại vòng lặp thứ tt, chúng ta sẽ cập nhật như
sau:xt+1=xt−η(2xt+5cos(xt))xt+1=xt−η(2xt+5cos⁡(xt))
Như thường lệ, tôi khai báo vài thư viện quen thuộc

# To support both python 2 and python 3

from __future__ import division, print_function, unicode_literals

import math

import numpy as np

import matplotlib.pyplot as plt

Tiếp theo, tôi viết các hàm số :

1. grad để tính đạo hàm

2. cost để tính giá trị của hàm số. Hàm này không sử dụng trong thuật toán nhưng thường được
dùng để kiểm tra việc tính đạo hàm của đúng không hoặc để xem giá trị của hàm số có giảm
theo mỗi vòng lặp hay không.
3. myGD1 là phần chính thực hiện thuật toán Gradient Desent nêu phía trên. Đầu vào của hàm số
này là learning rate và điểm bắt đầu. Thuật toán dừng lại khi đạo hàm có độ lớn đủ nhỏ.

def grad(x):

return 2*x+ 5*np.cos(x)

def cost(x):
3|Page

return x**2 + 5*np.sin(x)

def myGD1(eta, x0):

x = [x0]

for it in range(100):

x_new = x[-1] - eta*grad(x[-1])

if abs(grad(x_new)) < 1e-3:

break

x.append(x_new)

return (x, it)

Điểm khởi tạo khác nhau

Sau khi có các hàm cần thiết, tôi thử tìm nghiệm với các điểm khởi tạo khác nhau
là x0=−5x0=−5 và x0=5x0=5.

(x1, it1) = myGD1(.1, -5)

(x2, it2) = myGD1(.1, 5)

print('Solution x1 = %f, cost = %f, obtained after %d iterations'%(x1[-1], cost(x1[-

1]), it1))

print('Solution x2 = %f, cost = %f, obtained after %d iterations'%(x2[-1], cost(x2[-

1]), it2))

Solution x1 = -1.110667, cost = -3.246394, obtained after 11 iterations

Solution x2 = -1.110341, cost = -3.246394, obtained after 29 iterations

Vậy là với các điểm ban đầu khác nhau, thuật toán của chúng ta tìm được nghiệm gần giống nhau,
mặc dù với tốc độ hội tụ khác nhau. Dưới đây là hình ảnh minh họa thuật toán GD cho bài toán này
(xem tốt trên Desktop ở chế độ full màn hình).
4|Page

Từ hình minh họa trên ta thấy rằng ở hình bên trái, tương ứng với x0=−5x0=−5, nghiệm hội tụ nhanh
hơn, vì điểm ban đầu x0x0 gần với nghiệm x∗≈−1x∗≈−1 hơn. Hơn nữa, với x0=5x0=5 ở hình bên
phải, đường đi của nghiệm có chứa một khu vực có đạo hàm khá nhỏ gần điểm có hoành độ bằng 2.
Điều này khiến cho thuật toán la cà ở đây khá lâu. Khi vượt qua được điểm này thì mọi việc diễn ra rất
tốt đẹp.

Learning rate khác nhau

Tốc độ hội tụ của GD không những phụ thuộc vào điểm khởi tạo ban đầu mà còn phụ thuộc vào learning
rate. Dưới đây là một ví dụ với cùng điểm khởi tạo x0=−5x0=−5 nhưng learning rate khác nhau:

Ta quan sát thấy hai điều:

1. Với learning rate nhỏ η=0.01η=0.01, tốc độ hội tụ rất chậm. Trong ví dụ này tôi chọn tối đa 100
vòng lặp nên thuật toán dừng lại trước khi tới đích, mặc dù đã rất gần. Trong thực tế, khi việc
tính toán trở nên phức tạp, learning rate quá thấp sẽ ảnh hưởng tới tốc độ của thuật toán rất
nhiều, thậm chí không bao giờ tới được đích.
2. Với learning rate lớn η=0.5η=0.5, thuật toán tiến rất nhanh tới gần đích sau vài vòng lặp. Tuy
nhiên, thuật toán không hội tụ được vì bước nhảy quá lớn, khiến nó cứ quẩn quanh ở đích.

Việc lựa chọn learning rate rất quan trọng trong các bài toán thực tế. Việc lựa chọn giá trị này phụ thuộc
nhiều vào từng bài toán và phải làm một vài thí nghiệm để chọn ra giá trị tốt nhất. Ngoài ra, tùy vào một
số bài toán, GD có thể làm việc hiệu quả hơn bằng cách chọn ra learning rate phù hợp hoặc
chọnlearning rate khác nhau ở mỗi vòng lặp. Tôi sẽ quay lại vấn đề này ở phần 2.

3. Gradient Descent cho hàm nhiều biến

Giả sử ta cần tìm global minimum cho hàm f(θ)f(θ) trong đó θθ (theta) là một vector, thường được dùng
để ký hiệu tập hợp các tham số của một mô hình cần tối ưu (trong Linear Regression thì các tham số
chính là hệ số ww). Đạo hàm của hàm số đó tại một điểm θθ bất kỳ được ký hiệu là ∇θf(θ)∇θf(θ) (hình
tam giác ngược đọc là nabla). Tương tự như hàm 1 biến, thuật toán GD cho hàm nhiều biến cũng bắt
đầu bằng một điểm dự đoán θ0θ0, sau đó, ở vòng lặp thứ tt, quy tắc cập nhật là:
θt+1=θt−η∇θf(θt)θt+1=θt−η∇θf(θt)
Hoặc viết dưới dạng đơn giản hơn: θ=θ−η∇θf(θ)θ=θ−η∇θf(θ).
Quy tắc cần nhớ: luôn luôn đi ngược hướng với đạo hàm.

Việc tính toán đạo hàm của các hàm nhiều biến là một kỹ năng cần thiết. Một vài đạo hàm đơn giản có
thể được tìm thấy ở đây.
5|Page

Quay lại với bài toán Linear Regression

Trong mục này, chúng ta quay lại với bài toán Linear Regression và thử tối ưu hàm mất mát của nó
bằng thuật toán GD.

Hàm mất mát của Linear Regression là:L(w)=12N||y−¯Xw||22L(w)=12N||y−X¯w||22

Chú ý: hàm này có khác một chút so với hàm tôi nêu trong bài Linear Regression. Mẫu số có
thêm NN là số lượng dữ liệu trong training set. Việc lấy trung bình cộng của lỗi này nhằm giúp tránh
trường hợp hàm mất mát và đạo hàm có giá trị là một số rất lớn, ảnh hưởng tới độ chính xác của các
phép toán khi thực hiện trên máy tính. Về mặt toán học, nghiệm của hai bài toán là như nhau.
Đạo hàm của hàm mất mát là:∇wL(w)=1N¯XT(¯Xw−y) (1)∇wL(w)=1NX¯T(X¯w−y) (1)

Sau đây là ví dụ trên Python và một vài lưu ý khi lập trình

Load thư viện

# To support both python 2 and python 3

from __future__ import division, print_function, unicode_literals

import numpy as np

import matplotlib

import matplotlib.pyplot as plt

np.random.seed(2)

Tiếp theo, chúng ta tạo 1000 điểm dữ liệu được chọn gần với đường thẳng y=4+3xy=4+3x, hiển thị
chúng và tìm nghiệm theo công thức:

X = np.random.rand(1000, 1)

y = 4 + 3 * X + .2*np.random.randn(1000, 1) # noise added

# Building Xbar

one = np.ones((X.shape[0],1))

Xbar = np.concatenate((one, X), axis = 1)

A = np.dot(Xbar.T, Xbar)

b = np.dot(Xbar.T, y)

w_lr = np.dot(np.linalg.pinv(A), b)

print('Solution found by formula: w = ',w_lr.T)

# Display result

w = w_lr

w_0 = w[0][0]

w_1 = w[1][0]
6|Page

x0 = np.linspace(0, 1, 2, endpoint=True)

y0 = w_0 + w_1*x0

# Draw the fitting line

plt.plot(X.T, y.T, 'b.') # data

plt.plot(x0, y0, 'y', linewidth = 2) # the fitting line

plt.axis([0, 1, 0, 10])

plt.show()

Solution found by formula: w = [[ 4.00305242 2.99862665]]

Đường thẳng tìm được là đường có màu vàng có phương trình y≈4+2.998xy≈4+2.998x.
Tiếp theo ta viết đạo hàm và hàm mất mát:

def grad(w):

N = Xbar.shape[0]

return 1/N * Xbar.T.dot(Xbar.dot(w) - y)

def cost(w):

N = Xbar.shape[0]

return .5/N*np.linalg.norm(y - Xbar.dot(w), 2)**2;

Kiểm tra đạo hàm

Việc tính đạo hàm của hàm nhiều biến thông thường khá phức tạp và rất dễ mắc lỗi, nếu chúng ta tính
sai đạo hàm thì thuật toán GD không thể chạy đúng được. Trong thực nghiệm, có một cách để kiểm
tra liệu đạo hàm tính được có chính xác không. Cách này dựa trên định nghĩa của đạo hàm (cho hàm
1 biến):f′(x)=limε→0f(x+ε)−f(x)εf′(x)=limε→0f(x+ε)−f(x)ε
7|Page

Một cách thường được sử dụng là lấy một giá trị εε rất nhỏ, ví dụ 10−610−6, và sử dụng công
thức:f′(x)≈f(x+ε)−f(x−ε)2ε (2)f′(x)≈f(x+ε)−f(x−ε)2ε (2)
Cách tính này được gọi là numerical gradient.

Câu hỏi: Tại sao công thức xấp xỉ hai phía trên đây lại được sử dụng rộng rãi, sao không sử
dụng công thức xấp xỉ đạo hàm bên phải hoặc bên trái?

Có hai các giải thích cho vấn đề này, một bằng hình học, một bằng giải tích.

Giải thích bằng hình học

Quan sát hình dưới đây:

Trong hình, vector màu đỏ là đạo hàm chính xác của hàm số tại điểm có hoành độ bằng x0x0. Vector
màu xanh lam (có vẻ là hơi tím sau khi convert từ .pdf sang .png) thể hiện cách xấp xỉ đạo hàm phía
phải. Vector màu xanh lục thể hiện cách xấp xỉ đạo hàm phía trái. Vector màu nâu thể hiện cách xấp xỉ
đạo hàm hai phía. Trong ba vector xấp xỉ đó, vector xấp xỉ hai phía màu nâu là gần với vector đỏ nhất
nếu xét theo hướng.
Sự khác biệt giữa các cách xấp xỉ còn lớn hơn nữa nếu tại điểm x, hàm số bị bẻ cong mạnh hơn. Khi
đó, xấp xỉ trái và phải sẽ khác nhau rất nhiều. Xấp xỉ hai bên sẽ ổn định hơn.

Giải thích bằng giải tích

Chúng ta cùng quay lại một chút với Giải tích I năm thứ nhất đại học: Khai triển Taylor.

Với εε rất nhỏ, ta có hai xấp xỉ sau:

f(x+ε)≈f(x)+f′(x)ε+f”(x)2ε2+…f(x+ε)≈f(x)+f′(x)ε+f”(x)2ε2+…
và:f(x−ε)≈f(x)−f′(x)ε+f”(x)2ε2−…f(x−ε)≈f(x)−f′(x)ε+f”(x)2ε2−…
Từ đó ta có:f(x+ε)−f(x)ε≈f′(x)+f”(x)2ε+⋯=f′(x)+O(ε) (3)f(x+ε)−f(x)ε≈f′(x)+f”(x)2ε+⋯=f′(x)+O(ε) (3)
f(x+ε)−f(x−ε)2ε≈f′(x)+f(3)(x)6ε2+⋯=f′(x)+O(ε2) (4)f(x+ε)−f(x−ε)2ε≈f′(x)+f(3)(x)6ε2+⋯=f′(x)+O(ε2) (4)
Từ đó, nếu xấp xỉ đạo hàm bằng công thức (3)(3) (xấp xỉ đạo hàm phải), sai số sẽ là O(ε)O(ε). Trong
khi đó, nếu xấp xỉ đạo hàm bằng công thức (4)(4) (xấp xỉ đạo hàm hai phía), sai số sẽ
là O(ε2)≪O(ε)O(ε2)≪O(ε) nếu εεnhỏ.
Cả hai cách giải thích trên đây đều cho chúng ta thấy rằng, xấp xỉ đạo hàm hai phía là xấp xỉ tốt hơn.

Với hàm nhiều biến

Với hàm nhiều biến, công thức (2)(2) được áp dụng cho từng biến khi các biến khác cố định. Cách tính
này thường cho giá trị khá chính xác. Tuy nhiên, cách này không được sử dụng để tính đạo hàm vì độ
phức tạp quá cao so với cách tính trực tiếp. Khi so sánh đạo hàm này với đạo hàm chính xác tính theo
công thức, người ta thường giảm số chiều dữ liệu và giảm số điểm dữ liệu để thuận tiện cho tính toán.
Một khi đạo hàm tính được rất gần với numerical gradient, chúng ta có thể tự tin rằng đạo hàm tính
được là chính xác.
Dưới đây là một đoạn code đơn giản để kiểm tra đạo hàm và có thể áp dụng với một hàm số (của một
vector) bất kỳ với cost và grad đã tính ở phía trên.
8|Page

def numerical_grad(w, cost):

eps = 1e-4

g = np.zeros_like(w)

for i in range(len(w)):

w_p = w.copy()

w_n = w.copy()

w_p[i] += eps

w_n[i] -= eps

g[i] = (cost(w_p) - cost(w_n))/(2*eps)

return g

def check_grad(w, cost, grad):

w = np.random.rand(w.shape[0], w.shape[1])

grad1 = grad(w)

grad2 = numerical_grad(w, cost)

return True if np.linalg.norm(grad1 - grad2) < 1e-6 else False

print( 'Checking gradient...', check_grad(np.random.rand(2, 1), cost, grad))

Checking gradient... True

(Với các hàm số khác, bạn đọc chỉ cần viết lại hàm grad và cost ở phần trên rồi áp dụng đoạn code
này để kiểm tra đạo hàm. Nếu hàm số là hàm của một ma trận thì chúng ta thay đổi một chút trong
hàm numerical_grad, tôi hy vọng không quá phức tạp).

Với bài toán Linear Regression, cách tính đạo hàm như trong (1)(1) phía trên được coi là đúng vì sai
số giữa hai cách tính là rất nhỏ (nhỏ hơn 10−610−6). Sau khi có được đạo hàm chính xác, chúng ta
viết hàm cho GD:

def myGD(w_init, grad, eta):

w = [w_init]

for it in range(100):

w_new = w[-1] - eta*grad(w[-1])

if np.linalg.norm(grad(w_new))/len(w_new) < 1e-3:

break

w.append(w_new)

return (w, it)

9|Page

w_init = np.array([[2], [1]])

(w1, it1) = myGD(w_init, grad, 1)

print('Solution found by GD: w = ', w1[-1].T, ',\nafter %d iterations.' %(it1+1))

Solution found by GD: w = [[ 4.01780793 2.97133693]] ,

after 49 iterations.

Sau 49 vòng lặp, thuật toán đã hội tụ với một nghiệm khá gần với nghiệm tìm được theo công thức.

Dưới đâ y
là hình động

minh họa thuật toán GD.

Trong hình bên trái, các đường thẳng màu đỏ là nghiệm tìm được sau mỗi vòng lặp.

Trong hình bên phải, tôi xin giới thiệu một thuật ngữ mới: đường đồng mức.
10 | P a g e

Đường đồng mức (level sets)

Với đồ thị của một hàm số với hai biến đầu vào cần được vẽ trong không gian ba chiều, nhều khi chúng
ta khó nhìn được nghiệm có khoảng tọa độ bao nhiêu. Trong toán tối ưu, người ta thường dùng một
cách vẽ sử dụng khái niệm đường đồng mức (level sets).

Nếu các bạn để ý trong các bản độ tự nhiên, để miêu tả độ cao của các dãy núi, người ta dùng nhiều
đường cong kín bao quanh nhau như sau:

Ví dụ về đường đồng mức trong các bản đồ tự nhiên. (Nguồn: Địa lý 6: Đường đồng mức là những
đường như thế nào?)

Các vòng nhỏ màu đỏ hơn thể hiện các điểm ở trên cao hơn.

Trong toán tối ưu, người ta cũng dùng phương pháp này để thể hiện các bề mặt trong không gian hai
chiều.

Quay trở lại với hình minh họa thuật toán GD cho bài toán Liner Regression bên trên, hình bên phải là
hình biểu diễn các level sets. Tức là tại các điểm trên cùng một vòng, hàm mất mát có giá trị như nhau.
Trong ví dụ này, tôi hiển thị giá trị của hàm số tại một số vòng. Các vòng màu xanh có giá trị thấp, các
vòng tròn màu đỏ phía ngoài có giá trị cao hơn. Điểm này khác một chút so với đường đồng mức trong
tự nhiên là các vòng bên trong thường thể hiện một thung lũng hơn là một đỉnh núi (vì chúng ta đang
đi tìm giá trị nhỏ nhất).

Tôi thử với learning rate nhỏ hơn, kết quả như sau:
11 | P a g e

Tốc độ hội tụ đã chậm đi nhiều, thậm chí sau 99 vòng lặp, GD vẫn chưa tới gần được nghiệm tốt nhất.
Trong các bài toán thực tế, chúng ta cần nhiều vòng lặp hơn 99 rất nhiều, vì số chiều và số điểm dữ
liệu thường là rất lớn.

4. Một ví dụ khác

Để kết thúc phần 1 của Gradient Descent, tôi xin nêu thêm một ví dụ khác.

Hàm số f(x,y)=(x2+y−7)2+(x−y+1)2f(x,y)=(x2+y−7)2+(x−y+1)2 có hai điểm local minimum màu xanh lục

tại (2,3)(2,3) và (−3,−2)(−3,−2), và chúng cũng là hai điểm global minimum. Trong ví dụ này, tùy vào
điểm khởi tạo mà chúng ta thu được các nghiệm cuối cùng khác nhau.

5. Thảo luận
12 | P a g e

Dựa trên GD, có rất nhiều thuật toán phức tạp và hiệu quả hơn được thiết kế cho những loại bài toán
khác nhau. Vì bài này đã đủ dài, tôi xin phép dừng lại ở đây. Mời các bạn đón đọc bài Gradient Descent
phần 2 với nhiều kỹ thuật nâng cao hơn.

Bài 8: Gradient Descent (phần 2/2)

1. Các thuật toán tối ưu Gradient Descent

1.1 Momentum

Nhắc lại thuật toán Gradient Descent

Dành cho các bạn chưa đọc phần 1 của Gradient Descent. Để giải bài toán tìm điểm global optimal của
hàm mất mát J(θ)J(θ) (Hàm mất mát cũng thường được ký hiệu là J()J() với θθ là tập hợp các tham số
của mô hình), tôi xin nhắc lại thuật toán GD:

Thuật toán Gradient Descent:

1. Dự đoán một điểm khởi tạo θ=θ0θ=θ0.

2. Cập nhật θθ đến khi đạt được kết quả chấp nhận được:θ=θ−η∇θJ(θ)θ=θ−η∇θJ(θ)

với ∇θJ(θ)∇θJ(θ) là đạo hàm của hàm mất mát tại θθ.

Gradient dưới góc nhìn vật lý

Thuật toán GD thường được ví với tác dụng của trọng lực lên một hòn bi đặt trên một mặt có dạng như
hình một thung lũng giống như hình 1a) dưới đây. Bất kể ta đặt hòn bi ở A hay B thì cuối cùng hòn bi
cũng sẽ lăn xuống và kết thúc ở vị trí C.

Hình 1: So sánh Gradient Descent với các hiện tượng vật lý

Tuy nhiên, nếu như bề mặt có hai đáy thung lũng như Hình 1b) thì tùy vào việc đặt bi ở A hay B, vị trí
cuối cùng của bi sẽ ở C hoặc D. Điểm D là một điểm local minimum chúng ta không mong muốn.

Nếu suy nghĩ một cách vật lý hơn, vẫn trong Hình 1b), nếu vận tốc ban đầu của bi khi ở điểm B đủ lớn,
khi bi lăn đến điểm D, theo đà, bi có thể tiếp tục di chuyển lên dốc phía bên trái của D. Và nếu giả sử
vận tốc ban đầu lớn hơn nữa, bi có thể vượt dốc tới điểm E rồi lăn xuống C như trong Hình 1c). Đây
chính là điều chúng ta mong muốn. Bạn đọc có thể đặt câu hỏi rằng liệu bi lăn từ A tới C có theo đà lăn
13 | P a g e

tới E rồi tới D không. Xin trả lời rằng điều này khó xảy ra hơn vì nếu so với dốc DE thì dốc CE cao hơn
nhiều.

Dựa trên hiện tượng này, một thuật toán được ra đời nhằm khắc phục việc nghiệm của GD rơi vào một
điểm local minimum không mong muốn. Thuật toán đó có tên là Momentum (tức theo đà trong tiếng
Việt).

Gradient Descent với Momentum

Để biểu diễn momentum bằng toán học thì chúng ta phải làm thế nào?

Trong GD, chúng ta cần tính lượng thay đổi ở thời điểm tt để cập nhật vị trí mới cho nghiệm (tức hòn
bi). Nếu chúng ta coi đại lượng này như vận tốc vtvt trong vật lý, vị trí mới của hòn bi sẽ
là θt+1=θt−vtθt+1=θt−vt. Dấu trừ thể hiện việc phải di chuyển ngược với đạo hàm. Công việc của chúng
ta bây giờ là tính đại lượng vtvt sao cho nó vừa mang thông tin của độ dốc (tức đạo hàm), vừa mang
thông tin của đà, tức vận tốc trước đó vt−1vt−1 (chúng ta coi như vận tốc ban đầu v0=0v0=0). Một cách
đơn giản nhất, ta có thể cộng (có trọng số) hai đại lượng này lại:vt=γvt−1+η∇θJ(θ)vt=γvt−1+η∇θJ(θ)
Trong đó γγ thường được chọn là một giá trị khoảng 0.9, vtvt là vận tốc tại thời điểm trước
đó, ∇θJ(θ)∇θJ(θ)chính là độ dốc của điểm trước đó. Sau đó vị trí mới của hòn bi được xác định như
sau:θ=θ−vtθ=θ−vt
Thuật toán đơn giản này tỏ ra rất hiệu quả trong các bài toán thực tế (trong không gian nhiều chiều,
cách tính toán cũng hoàn tòan tương tự). Dưới đây là một ví dụ trong không gian một chiều.

Một ví dụ nhỏ

Chúng ta xem xét một hàm đơn giản có hai điểm local minimum, trong đó 1 điểm là global
minimum:f(x)=x2+10sin(x)f(x)=x2+10sin⁡(x)Có đạo hàm là: f′(x)=2x+10cos(x)f′(x)=2x+10cos⁡(x). Hình
2 dưới đây thể hiện sự khác nhau giữa thuật toán GD và thuật toán GD với Momentum:

Hình 2: Minh họa thuật toán GD với Momentum.

Hình bên trái là đường đi của nghiệm khi không sử dụng Momentum, thuật toán hội tụ sau chỉ 5 vòng
lặp nhưng nghiệm tìm được là nghiệm local minimun.

Hình bên phải là đường đi của nghiệm khi có sử dụng Momentum, hòn bi đã có thể vượt dốc tới khu
vực gần điểm global minimun, sau đó dao động xung quanh điểm này, giảm tốc rồi cuối cùng tới đích.
Mặc dù mất nhiều vòng lặp hơn, GD với Momentum cho chúng ta nghiệm chính xác hơn. Quan sát
đường đi của hòn bi trong trường hợp này, chúng ta thấy rằng điều này giống với vật lý hơn!
14 | P a g e

Nếu biết trước điểm đặt bi ban đầu theta, đạo hàm của hàm mất mát tại một điểm bất kỳ grad(theta),
lượng thông tin lưu trữ từ vận tốc trước đó gamma và learning rate eta, chúng ta có thể viết hàm
số GD_momentum trong Python như sau:

# check convergence

def has_converged(theta_new, grad):

return np.linalg.norm(grad(theta_new))/

len(theta_new) < 1e-3

def GD_momentum(theta_init, grad, eta, gamma):

# Suppose we want to store history of theta

theta = [theta_init]

v_old = np.zeros_like(theta_init)

for it in range(100):

v_new = gamma*v_old + eta*grad(theta[-1])

theta_new = theta[-1] - v_new

if has_converged(theta_new, grad):

break

theta.append(theta_new)

v_old = v_new

return theta

# this variable includes all points in the path

# if you just want the final answer,

# use `return theta[-1]`

1.2. Nesterov accelerated gradient (NAG)

Momentum giúp hòn bi vượt qua được dốc locaminimum, tuy nhiên, có một hạn chế chúng ta có thể
thấy trong ví dụ trên: Khi tới gần đích, momemtum vẫn mất khá nhiều thời gian trước khi dừng lại. Lý
do lại cũng chính là vì có đà. Có một phương pháp khác tiếp tục giúp khắc phục điều này, phương
pháp đó mang tên Nesterov accelerated gradient (NAG), giúp cho thuật toán hội tụ nhanh hơn.

Ý tưởng chính

Ý tưởng cơ bản là dự đoán hướng đi trong tương lai, tức nhìn trước một bước! Cụ thể, nếu sử dụng
số hạng momentum γvt−1γvt−1 để cập nhật thì ta có thể xấp xỉ được vị trí tiếp theo của hòn bi
là θ−γvt−1θ−γvt−1(chúng ta không đính kèm phần gradient ở đây vì sẽ sử dụng nó trong bước cuối
cùng). Vậy, thay vì sử dụng gradient của điểm hiện tại, NAG đi trước một bước, sử dụng gradient của
điểm tiếp theo. Theo dõi hình dưới đây:
15 | P a g e

Ý tưởng của Nesterov accelerated gradient. (Nguồn: CS231n Stanford: Convolutional Neural
Networks for Visual Recognition)

 Với momentum thông thường: lượng thay đổi là tổng của hai vector: momentum vector và
gradient ở thời điểm hiện tại.

 Với Nesterove momentum: lượng thay đổi là tổng của hai vector: momentum vector và gradient
ở thời điểm được xấp xỉ là điểm tiếp theo.

Công thức cập nhật

Công thức cập nhật của NAG được cho như sau:

vt=γvt−1+η∇θJ(θ−γvt−1)θ=θ−vtvt=γvt−1+η∇θJ(θ−γvt−1)θ=θ−vt
Để ý một chút các bạn sẽ thấy điểm được tính đạo hàm đã thay đổi.

Ví dụ minh họa

Dưới đây là ví dụ so sánh Momentum và NAG cho bài toán Linear Regression:

Minh họa thuật toán GD với Momentum và NAG.

Hình bên trái là đường đi của nghiệm với phương pháp Momentum. nghiệm đi khá là zigzag và mất
nhiều vòng lặp hơn. Hình bên phải là đường đi của nghiệm với phương pháp NAG, nghiệm hội tụ
nhanh hơn, và đường đi ít zigzag hơn.
16 | P a g e

(Source code cho hình bên trái và hình bên phải).

1.3. Các thuật toán khác

Ngoài hai thuật toán trên, có rất nhiều thuật toán nâng cao khác được sử dụng trong các bài toán thực
tế, đặc biệt là các bài toán Deep Learning. Có thể nêu một vài từ khóa như Adagrad, Adam, RMSprop,…
Tôi sẽ không đề cập đến các thuật toán đó trong bài này mà sẽ dành thời gian nói tới nếu có dịp trong
tương lai, khi blog đã đủ lớn và đã trang bị cho các bạn một lượng kiến thức nhất định.

Tuy nhiên, bạn đọc nào muốn đọc thêm có thể tìm được rất nhiều thông tin hữu ích trong bài này: An
overview of gradient descent optimization algorithms .

2. Biến thể của Gradient Descent

Tôi xin một lần nữa dùng bài toán Linear Regression làm ví dụ. Hàm mất mát và đạo hàm của nó cho
bài toán này lần lượt là (để cho thuận tiện, trong bài này tôi sẽ dùng ký hiệu XX thay cho dữ liệu mở
rộng ¯XX¯):
J(w)=12N||Xw−y||22J(w)=12N||Xw−y||22 =12NN∑i=1(xiw−yi)2 =12N∑i=1N(xiw−yi)2và:∇wJ(w)=1NN
∑i=1xTi(xiw−yi)∇wJ(w)=1N∑i=1NxiT(xiw−yi)

2.1. Batch Gradient Descent

Thuật toán Gradient Descent chúng ta nói từ đầu phần 1 đến giờ còn được gọi là Batch Gradient
Descent. Batch ở đây được hiểu là tất cả, tức khi cập nhật θ=wθ=w, chúng ta sử dụng tất cả các điểm
dữ liệu xixi.
Cách làm này có một vài hạn chế đối với cơ sở dữ liệu có vô cùng nhiều điểm (hơn 1 tỉ người dùng
của facebook chẳng hạn). Việc phải tính toán lại đạo hàm với tất cả các điểm này sau mỗi vòng lặp trở
nên cồng kềnh và không hiệu quả. Thêm nữa, thuật toán này được coi là không hiệu quả với online
learning.

Online learning là khi cơ sở dữ liệu được cập nhật liên tục (thêm người dùng đăng ký hàng ngày
chẳng hạn), mỗi lần thêm vài điểm dữ liệu mới. Kéo theo đó là mô hình của chúng ta cũng phải thay
đổi một chút để phù hợp với các dữ liệu mới này. Nếu làm theo Batch Gradient Descent, tức tính lại
đạo hàm của hàm mất mát tại tất cả các điểm dữ liệu, thì thời gian tính toán sẽ rất lâu, và thuật toán
của chúng ta coi như không online nữa do mất quá nhiều thời gian tính toán.

Trên thực tế, có một thuật toán đơn giản hơn và tỏ ra rất hiệu quả, có tên gọi là Stochastic Gradient
Descent (SGD).

2.2. Stochastic Gradient Descent.

Trong thuật toán này, tại 1 thời điểm, ta chỉ tính đạo hàm của hàm mất mát dựa trên chỉ một điểm dữ
liệu xixi rồi cập nhật θθ dựa trên đạo hàm này. Việc này được thực hiện với từng điểm trên toàn bộ dữ
liệu, sau đó lặp lại quá trình trên. Thuật toán rất đơn giản này trên thực tế lại làm việc rất hiệu quả.
Mỗi lần duyệt một lượt qua tất cả các điểm trên toàn bộ dữ liệu được gọi là một epoch. Với GD thông
thường thì mỗi epoch ứng với 1 lần cập nhật θθ, với SGD thì mỗi epoch ứng với NN lần cập
nhật θθ với NNlà số điểm dữ liệu. Nhìn vào một mặt, việc cập nhật từng điểm một như thế này có thể
làm giảm đi tốc độ thực hiện 1 epoch. Nhưng nhìn vào một mặt khác, SGD chỉ yêu cầu một lượng
epoch rất nhỏ (thường là 10 cho lần đầu tiên, sau đó khi có dữ liệu mới thì chỉ cần chạy dưới một epoch
là đã có nghiệm tốt). Vì vậy SGD phù hợp với các bài toán có lượng cơ sở dữ liệu lớn (chủ yếu là Deep
Learning mà chúng ta sẽ thấy trong phần sau của blog) và các bài toán yêu cầu mô hình thay đổi liên
tục, tức online learning.
Thứ tự lựa chọn điểm dữ liệu

Một điểm cần lưu ý đó là: sau mỗi epoch, chúng ta cần shuffle (xáo trộn) thứ tự của các dữ liệu để đảm
bảo tính ngẫu nhiên. Việc này cũng ảnh hưởng tới hiệu năng của SGD.

Một cách toán học, quy tắc cập nhật của SGD là:θ=θ−η∇θJ(θ;xi;yi)θ=θ−η∇θJ(θ;xi;yi)
17 | P a g e

trong đó J(θ;xi;yi)J(θ;xi;yi) là hàm mất mát với chỉ 1 cặp điểm dữ liệu (input, label) là (xi,yixi,yi). Chú
ý: chúng ta hoàn toàn có thể áp dụng các thuật toán tăng tốc GD như Momentum, AdaGrad,… vào
SGD.

Ví dụ với bài toán Linear Regression

Với bài toán Linear Regression, θ=wθ=w, hàm mất mát tại một điểm dữ liệu
là:J(w;xi;yi)=12(xiw−yi)2J(w;xi;yi)=12(xiw−yi)2Đạo hàm theo ww tương ứng
là:∇wJ(w;xi;yi)=xTi(xiw−yi)∇wJ(w;xi;yi)=xiT(xiw−yi)Và dưới đây là hàm số trong python để giải Linear
Regression theo SGD:

# single point gradient

def sgrad(w, i, rd_id):

true_i = rd_id[i]

xi = Xbar[true_i, :]

yi = y[true_i]

a = np.dot(xi, w) - yi

return (xi*a).reshape(2, 1)

def SGD(w_init, grad, eta):

w = [w_init]

w_last_check = w_init

iter_check_w = 10

N = X.shape[0]

count = 0

for it in range(10):

# shuffle data

rd_id = np.random.permutation(N)

for i in range(N):

count += 1

g = sgrad(w[-1], i, rd_id)

w_new = w[-1] - eta*g

w.append(w_new)

if count%iter_check_w == 0:

w_this_check = w_new

if np.linalg.norm(w_this_check - w_last_check)/len(w_init) < 1e-3:

return w

w_last_check = w_this_check
18 | P a g e

return w

Kết quả được cho như hình dưới đây (với dữ liệu được tạo giống như ở phần 1).

Trái: đường đi của nghiệm với SGD. Phải: giá trị của loss function tại 50 vòng lặp đầu tiên.

Hình bên trái mô tả đường đi của nghiệm. Chúng ta thấy rằng đường đi khá là zigzag chứ
không mượtnhư khi sử dụng GD. Điều này là dễ hiểu vì một điểm dữ liệu không thể đại diện cho toàn
bộ dữ liệu được. Tuy nhiên, chúng ta cũng thấy rằng thuật toán hội tụ khá nhanh đến vùng lân cận của
nghiệm. Với 1000 điểm dữ liệu, SGD chỉ cần gần 3 epoches (2911 tương ứng với 2911 lần cập nhật,
mỗi lần lấy 1 điểm). Nếu so với con số 49 vòng lặp (epoches) như kết quả tốt nhất có được bằng GD,
thì kết quả này lợi hơn rất nhiều.

Hình bên phải mô tả hàm mất mát cho toàn bộ dữ liệu sau khi chỉ sử dụng 50 điểm dữ liệu đầu tiên.
Mặc dù không mượt, tốc độ hội tụ vẫn rất nhanh.

Thực tế cho thấy chỉ lấy khoảng 10 điểm là ta đã có thể xác định được gần đúng phương trình đường
thẳng cần tìm rồi. Đây chính là ưu điểm của SGD - hội tụ rất nhanh.

2.3. Mini-batch Gradient Descent

Khác với SGD, mini-batch sử dụng một số lượng nn lớn hơn 1 (nhưng vẫn nhỏ hơn tổng số dữ
liệu NNrất nhiều). Giống với SGD, Mini-batch Gradient Descent bắt đầu mỗi epoch bằng việc xáo trộn
ngẫu nhiên dữ liệu rồi chia toàn bộ dữ liệu thành các mini-batch, mỗi mini-batch có nn điểm dữ liệu (trừ
mini-batch cuối có thể có ít hơn nếu NN không chia hết cho nn). Mỗi lần cập nhật, thuật toán này lấy ra
một mini-batch để tính toán đạo hàm rồi cập nhật. Công thức có thể viết dưới
dạng:θ=θ−η∇θJ(θ;xi:i+n;yi:i+n)θ=θ−η∇θJ(θ;xi:i+n;yi:i+n)Với xi:i+nxi:i+n được hiểu là dữ liệu từ thứ ii tới
thứ i+n−1i+n−1 (theo ký hiệu của Python). Dữ liệu này sau mỗi epoch là khác nhau vì chúng cần được
xáo trộn. Một lần nữa, các thuật toán khác cho GD như Momentum, Adagrad, Adadelta,… cũng có thể
được áp dụng vào đây.
Mini-batch GD được sử dụng trong hầu hết các thuật toán Machine Learning, đặc biệt là trong Deep
Learning. Giá trị nn thường được chọn là khoảng từ 50 đến 100.
Dưới đây là ví dụ về giá trị của hàm mất mát mỗi khi cập nhật tham số θθ của một bài toán khác phức
tạp hơn.
19 | P a g e

Hàm mất mát nhảy lên nhảy xuống (fluctuate) sau mỗi lần cập nhật nhưng nhìn chung giảm dần và
có xu hướng hội tụ về cuối. (Nguồn: Wikipedia).

Để có thêm thông tin chi tiết hơn, bạn đọc có thể tìm trong bài viết rất tốt này.

3. Stopping Criteria (điều kiện dừng)

Có một điểm cũng quan trọng mà từ đầu tôi chưa nhắc đến: khi nào thì chúng ta biết thuật toán đã hội
tụ và dừng lại?

Trong thực nghiệm, có một vài phương pháp như dưới đây:

1. Giới hạn số vòng lặp: đây là phương pháp phổ biến nhất và cũng để đảm bảo rằng chương
trình chạy không quá lâu. Tuy nhiên, một nhược điểm của cách làm này là có thể thuật toán
dừng lại trước khi đủ gần với nghiệm.
2. So sánh gradient của nghiệm tại hai lần cập nhật liên tiếp, khi nào giá trị này đủ nhỏ thì dừng
lại. Phương pháp này cũng có một nhược điểm lớn là việc tính đạo hàm đôi khi trở nên quá
phức tạp (ví dụ như khi có quá nhiều dữ liệu), nếu áp dụng phương pháp này thì coi như ta
không được lợi khi sử dụng SGD và mini-batch GD.
3. So sánh giá trị của hàm mất mát của nghiệm tại hai lần cập nhật liên tiếp, khi nào giá trị này
đủ nhỏ thì dừng lại. Nhược điểm của phương pháp này là nếu tại một thời điểm, đồ thị hàm số
có dạng bẳng phẳng tại một khu vực nhưng khu vực đó không chứa điểm local minimum (khu
vực này thường được gọi là saddle points), thuật toán cũng dừng lại trước khi đạt giá trị mong
muốn.
4. Trong SGD và mini-batch GD, cách thường dùng là so sánh nghiệm sau một vài lần cập nhật.
Trong đoạn code Python phía trên về SGD, tôi áp dụng việc so sánh này mỗi khi nghiệm được
cập nhật 10 lần. Việc làm này cũng tỏ ra khá hiệu quả.

4. Một phương pháp tối ưu đơn giản khác: Newton’s method

Nhân tiện đang nói về tối ưu, tôi xin giới thiệu một phương pháp nữa có cách giải thích đơn giản:
Newton’s method. Các phương pháp GD tôi đã trình bày còn được gọi là first-order methods, vì lời giải
tìm được dựa trên đạo hàm bậc nhất của hàm số. Newton’s method là một second-order method, tức
lời giải yêu cầu tính đến đạo hàm bậc hai.

Nhắc lại rằng, cho tới thời điểm này, chúng ta luôn giải phương trình đạo hàm của hàm mất mát bằng
0 để tìm các điểm local minimun. (Và trong nhiều trường hợp, coi nghiệm tìm được là nghiệm của bài
toán tìm giá trị nhỏ nhất của hàm mất mát). Có một thuật toán nối tiếng giúp giải bài toán f(x)=0f(x)=0,
thuật toán đó có tên là Newton’s method.
20 | P a g e

Newton’s method cho giải phương trình f(x)=0f(x)=0

Thuật toán Newton’s method được mô tả trong hình động minh họa dưới đây:

Hình 3: Minh họa thuật toán Newton's method trong giải phương trình. ( Nguồn: Newton's method -
Wikipedia).

Ý tưởng giải bài toán f(x)=0f(x)=0 bằng phương pháp Newton’s method như sau. Xuất phát từ một
điểm x0x0được cho là gần với nghiệm x∗x∗. Sau đó vẽ đường tiếp tuyến (mặt tiếp tuyến trong không
gian nhiều chiều) với đồ thị hàm số y=f(x)y=f(x) tại điểm trên đồ thị có hoành độ x0x0. Giao
điểm x1x1 của đường tiếp tuyến này với trục hoành được xem là gần với nghiệm x∗x∗ hơn. Thuật toán
lặp lại với điểm mới x1x1 và cứ như vậy đến khi ta được f(xt)≈0f(xt)≈0.
Đó là ý nghĩa hình học của Newton’s method, chúng ta cần một công thức để có thể dựa vào đó để lập
trình. Việc này không quá phức tạp với các bạn thi đại học môn toán ở VN. Thật vậy, phương trình tiếp
tuyến với đồ thị của hàm f(x)f(x) tại điểm có hoành độ xtxt là:y=f′(xt)(x−xt)+f(xt)y=f′(xt)(x−xt)+f(xt)Giao
điểm của đường thẳng này với trục xx tìm được bằng cách giải phương trình vế phải của biểu thức
trên bằng 0, tức là:x=xt−f(xt)f′(xt)≜xt+1x=xt−f(xt)f′(xt)≜xt+1

Newton’s method trong bài toán tìm local minimun

Áp dụng phương pháp này cho việc giải phương trình f′(x)=0f′(x)=0 ta
có:xt+1=xt−(f”(xt))−1f′(xt)xt+1=xt−(f”(xt))−1f′(xt)
Và trong không gian nhiều chiều với θθ là biến:θ=θ−H(J(θ))−1∇θJ(θ)θ=θ−H(J(θ))−1∇θJ(θ)trong
đó H(J(θ))H(J(θ)) là đạo hàm bậc hai của hàm mất mất (còn gọi là Hessian matrix). Biểu thức này là
một ma trận nếu θθ là một vector. Và H(J(θ))−1H(J(θ))−1 chính là nghịch đảo của ma trận đó.

Hạn chế của Newton’s method

 Điểm khởi tạo phải rất gần với nghiệm x∗x∗. Ý tưởng sâu xa hơn của Newton’s method là dựa
trên khai triển Taylor của hàm số f(x)f(x) tới đạo hàm thứ
nhất:0=f(x∗)≈f(xt)+f′(xt)(xt−x∗)0=f(x∗)≈f(xt)+f′(xt)(xt−x∗)Từ đó suy
ra: x∗≈xt−f(xt)f′(xt)x∗≈xt−f(xt)f′(xt). Một điểm rất quan trọng, khai triển Taylor chỉ đúng
nếu xtxt rất gần với x∗x∗! Dưới đây là một ví dụ kinh điển trên Wikipedia về việc Newton’s
method cho một dãy số phân kỳ (divergence).
21 | P a g e

Hình 4: Nghiệm là một điểm gần -2. Tiếp tuyến của đồ thị hàm số tại điểm có hoành độ bằng 0 cắt
trục hoành tại 1, và ngược lại. Trong trường hợp này, Newton's method không bao giờ hội tụ.
(Nguồn: Wikipedia).

 Nhận thấy rằng trong việc giải phương trình f(x)=0f(x)=0, chúng ta có đạo hàm ở mẫu số. Khi
đạo hàm này gần với 0, ta sẽ được một đường thằng song song hoặc gần song song với trục
hoành. Ta sẽ hoặc không tìm được giao điểm, hoặc được một giao điểm ở vô cùng. Đặc biệt,
khi nghiệm chính là điểm có đạo hàm bằng 0, thuật toán gần như sẽ không tìm được nghiệm!
 Khi áp dụng Newton’s method cho bài toán tối ưu trong không gian nhiều chiều, chúng ta cần
tính nghịch đảo của Hessian matrix. Khi số chiều và số điểm dữ liệu lớn, đạo hàm bậc hai của
hàm mất mát sẽ là một ma trận rất lớn, ảnh hưởng tới cả memory và tốc độ tính toán của hệ
thống.

5. Kết luận

Qua hai bài viết về Gradient Descent này, tôi hy vọng các bạn đã hiểu và làm quen với một thuật toán
tối ưu được sử dụng nhiều nhất trong Machine Learning và đặc biệt là Deep Learning. Còn nhiều biến
thể khác khá thú vị về GD (mà rất có thể tôi chưa biết tới), nhưng tôi xin phép được dừng chuỗi bài về
GD tại đây và tiếp tục chuyển sang các thuật toán thú vị khác.

Bài 9: Perceptron Learning Algorithm

1. Giới thiệu

Trong bài này, tôi sẽ giới thiệu thuật toán đầu tiên trong Classification có tên là Perceptron Learning
Algorithm (PLA) hoặc đôi khi được viết gọn là Perceptron.

Perceptron là một thuật toán Classification cho trường hợp đơn giản nhất: chỉ có hai class (lớp) (bài
toán với chỉ hai class được gọi là binary classification) và cũng chỉ hoạt động được trong một trường
hợp rất cụ thể. Tuy nhiên, nó là nền tảng cho một mảng lớn quan trọng của Machine Learning là Neural
Networks và sau này là Deep Learning. (Tại sao lại gọi là Neural Networks - tức mạng dây thần kinh -
các bạn sẽ được thấy ở cuối bài).
22 | P a g e

Giả sử chúng ta có hai tập hợp dữ liệu đã được gán nhãn được minh hoạ trong Hình 1 bên trái dưới
đây. Hai class của chúng ta là tập các điểm màu xanh và tập các điểm màu đỏ. Bài toán đặt ra là: từ
dữ liệu của hai tập được gán nhãn cho trước, hãy xây dựng một classifier (bộ phân lớp) để khi có một
điểm dữ liệu hình tam giác màu xám mới, ta có thể dự đoán được màu (nhãn) của nó.

Hình 1: Bài toán Perceptron

Hiểu theo một cách khác, chúng ta cần tìm lãnh thổ của mỗi class sao cho, với mỗi một điểm mới, ta
chỉ cần xác định xem nó nằm vào lãnh thổ của class nào rồi quyết định nó thuộc class đó. Để tìm lãnh
thổcủa mỗi class, chúng ta cần đi tìm biên giới (boundary) giữa hai lãnh thổ này. Vậy bài toán
classification có thể coi là bài toán đi tìm boundary giữa các class. Và boundary đơn giản nhât trong
không gian hai chiều là một đường thằng, trong không gian ba chiều là một mặt phẳng, trong không
gian nhiều chiều là một siêu mặt phẳng (hyperplane) (tôi gọi chung những boundary này là đường
phẳng). Những boundary phẳng này được coi là đơn giản vì nó có thể biểu diễn dưới dạng toán học
bằng một hàm số đơn giản có dạng tuyến tính, tức linear. Tất nhiên, chúng ta đang giả sử rằng tồn tại
một đường phẳng để có thể phân định lãnh thổ của hai class. Hình 1 bên phải minh họa một đường
thẳng phân chia hai class trong mặt phẳng. Phần có nền màu xanh được coi là lãnh thổ của lớp xanh,
phần có nên màu đỏ được coi là lãnh thổ của lớp đỏ. Trong trường hợp này, điểm dữ liệu mới hình
tam giác được phân vào class đỏ.

Bài toán Perceptron

Bài toán Perceptron được phát biểu như sau: Cho hai class được gán nhãn, hãy tìm một đường phẳng
sao cho toàn bộ các điểm thuộc class 1 nằm về 1 phía, toàn bộ các điểm thuộc class 2 nằm về phía
còn lại của đường phẳng đó. Với giả định rằng tồn tại một đường phẳng như thế.

Nếu tồn tại một đường phẳng phân chia hai class thì ta gọi hai class đó là linearly separable. Các thuật
toán classification tạo ra các boundary là các đường phẳng được gọi chung là Linear Classifier.

2. Thuật toán Perceptron (PLA)

Cũng giống như các thuật toán lặp trong K-means Clustering và Gradient Descent, ý tưởng cơ bản của
PLA là xuất phát từ một nghiệm dự đoán nào đó, qua mỗi vòng lặp, nghiệm sẽ được cập nhật tới một
ví trí tốt hơn. Việc cập nhật này dựa trên việc giảm giá trị của một hàm mất mát nào đó.

Một số ký hiệu
23 | P a g e

Giả sử X=[x1,x2,…,xN]∈Rd×NX=[x1,x2,…,xN]∈Rd×N là ma trận chứa các điểm dữ liệu mà mỗi

cột xi∈Rd×1xi∈Rd×1 là một điểm dữ liệu trong không gian dd chiều. (Chú ý: khác với các bài trước tôi
thường dùng các vector hàng để mô tả dữ liệu, trong bài này tôi dùng vector cột để biểu diễn. Việc biểu
diễn dữ liệu ở dạng hàng hay cột tùy thuộc vào từng bài toán, miễn sao cách biễu diễn toán học của
nó khiến cho người đọc thấy dễ hiểu).
Giả sử thêm các nhãn tương ứng với từng điểm dữ liệu được lưu trong một vector
hàng y=[y1,y2,…,yN]∈R1×Ny=[y1,y2,…,yN]∈R1×N, với yi=1yi=1 nếu xixi thuộc class 1 (xanh)
và yi=−1yi=−1 nếu xixi thuộc class 2 (đỏ).
Tại một thời điểm, giả sử ta tìm được boundary là đường phẳng có phương
trình:fw(x)=w1x1+⋯+wdxd+w0=wT¯x=0fw(x)=w1x1+⋯+wdxd+w0=wTx¯=0
với ¯xx¯ là điểm dữ liệu mở rộng bằng cách thêm phần tử x0=1x0=1 lên trước vector xx tương tự như
trong Linear Regression. Và từ đây, khi nói xx, tôi cũng ngầm hiểu là điểm dữ liệu mở rộng.
Để cho đơn giản, chúng ta hãy cùng làm việc với trường hợp mỗi điểm dữ liệu có số chiều d=2d=2. Giả
sử đường thẳng w1x1+w2x2+w0=0w1x1+w2x2+w0=0 chính là nghiệm cần tìm như Hình 2 dưới đây:

Hình 2: Phương trình đường thẳng boundary.

Nhận xét rằng các điểm nằm về cùng 1 phía so với đường thẳng này sẽ làm cho hàm
số fw(x)fw(x) mang cùng dấu. Chỉ cần đổi dấu của ww nếu cần thiết, ta có thể giả sử các điểm nằm
trong nửa mặt phẳng nền xanh mang dấu dương (+), các điểm nằm trong nửa mặt phẳng nền đỏ mang
dấu âm (-). Các dấu này cũng tương đương với nhãn yy của mỗi class. Vậy nếu ww là một nghiệm của
bài toán Perceptron, với một điểm dữ liệu mới xx chưa được gán nhãn, ta có thể xác định class của nó
bằng phép toán đơn giản như sau:label(x)=1 if wTx≥0,otherwise−1label(x)=1 if wTx≥0,otherwise−1
Ngắn gọn hơn:label(x)=sgn(wTx)label(x)=sgn(wTx)trong đó, sgnsgn là hàm xác định dấu, với giả sử
rằng sgn(0)=1sgn(0)=1.

Xây dựng hàm mất mát

Tiếp theo, chúng ta cần xây dựng hàm mất mát với tham số ww bất kỳ. Vẫn trong không gian hai chiều,
giả sử đường thẳng w1x1+w2x2+w0=0w1x1+w2x2+w0=0 được cho như Hình 3 dưới đây:
24 | P a g e

Hình 3: Đường thẳng bất kỳ và các điểm bị misclassified được khoanh tròn.

Trong trường hợp này, các điểm được khoanh tròn là các điểm bị misclassified (phân lớp lỗi). Điều
chúng ta mong muốn là không có điểm nào bị misclassified. Hàm mất mát đơn giản nhất chúng ta nghĩ
đến là hàm đếm số lượng các điểm bị misclassied và tìm cách tối thiểu hàm số
này:J1(w)=∑xi∈M(−yisgn(wTxi))J1(w)=∑xi∈M(−yisgn(wTxi))
trong đó MM là tập hợp các điểm bị misclassifed (tập hợp này thay đổi theo ww). Với mỗi
điểm xi∈Mxi∈M, vì điểm này bị misclassified nên yiyi và sgn(wTx)sgn(wTx) khác nhau, và vì
thế −yisgn(wTxi)=1−yisgn(wTxi)=1. Vậy J1(w)J1(w)chính là hàm đếm số lượng các điểm bị
misclassified. Khi hàm số này đạt giá trị nhỏ nhất bằng 0 thì ta không còn điểm nào bị misclassified.
Một điểm quan trọng, hàm số này là rời rạc, không tính được đạo hàm theo ww nên rất khó tối ưu.
Chúng ta cần tìm một hàm mất mát khác để việc tối ưu khả thi hơn.
Xét hàm mất mát sau đây:

J(w)=∑xi∈M(−yiwTxi)J(w)=∑xi∈M(−yiwTxi)
Hàm J()J() khác một chút với hàm J1()J1() ở việc bỏ đi hàm sgnsgn. Nhận xét rằng khi một điểm
misclassified xixinằm càng xa boundary thì giá trị −yiwTxi−yiwTxi sẽ càng lớn, nghĩa là sự sai lệch
càng lớn. Giá trị nhỏ nhất của hàm mất mát này cũng bằng 0 nếu không có điểm nào bị misclassifed.
Hàm mất mát này cũng được cho là tốt hơn hàm J1()J1() vì nó trừng phạt rất nặng những điểm lấn sâu
sang lãnh thổ của class kia. Trong khi đó, J1()J1() trừng phạt các điểm misclassified như nhau (đều =
1), bất kể chúng xa hay gần với đường biên giới.
Tại một thời điểm, nếu chúng ta chỉ quan tâm tới các điểm bị misclassified thì hàm số J(w)J(w) khả vi
(tính được đạo hàm), vậy chúng ta có thể sử dụng Gradient Descent hoặc Stochastic Gradient Descent
(SGD)để tối ưu hàm mất mát này. Với ưu điểm của SGD cho các bài toán large-scale, chúng ta sẽ làm
theo thuật toán này.
Với một điểm dữ liệu xixi bị misclassified, hàm mất mát trở thành:
J(w;xi;yi)=−yiwTxiJ(w;xi;yi)=−yiwTxi
Đạo hàm tương ứng:

∇wJ(w;xi;yi)=−yixi∇wJ(w;xi;yi)=−yixi
Vậy quy tắc cập nhật là:

w=w+ηyixiw=w+ηyixi
với ηη là learning rate được chọn bằng 1. Ta có một quy tắc cập nhật rất gọn
là: wt+1=wt+yixiwt+1=wt+yixi. Nói cách khác, với mỗi điểm xixi bị misclassifed, ta chỉ cần nhân điểm
đó với nhãn yiyi của nó, lấy kết quả cộng vào ww ta sẽ được ww mới.
Ta có một quan sát nhỏ ở
đây:wTt+1xi=(wt+yixi)Txi=wTtxi+yi||xi||22wt+1Txi=(wt+yixi)Txi=wtTxi+yi||xi||22
Nếu yi=1yi=1, vì xixi bị misclassifed nên wTtxi<0wtTxi<0. Cũng
vì yi=1yi=1 nên yi||xi||22=||xi||22≥1yi||xi||22=||xi||22≥1 (chú ý x0=1x0=1), nghĩa
là wTt+1xi>wTtxiwt+1Txi>wtTxi. Lý giải bằng lời, wt+1wt+1 tiến về phía làm cho xixi được phân lớp
đúng. Điều tương tự xảy ra nếu yi=−1yi=−1.
25 | P a g e

Đến đây, cảm nhận của chúng ta với thuật toán này là: cứ chọn đường boundary đi. Xét từng điểm
một, nếu điểm đó bị misclassified thì tiến đường boundary về phía làm cho điểm đó được classifed
đúng. Có thể thấy rằng, khi di chuyển đường boundary này, các điểm trước đó được classified đúng
có thể lại bị misclassified. Mặc dù vậy, PLA vẫn được đảm bảo sẽ hội tụ sau một số hữu hạn bước (tôi
sẽ chứng minh việc này ở phía sau của bài viết). Tức là cuối cùng, ta sẽ tìm được đường phẳng phân
chia hai lớp, miễn là hai lớp đó là linearly separable. Đây cũng chính là lý do câu đầu tiên trong bài này
tôi nói với các bạn là: “Cứ làm đi, sai đâu sửa đấy, cuối cùng sẽ thành công!”.

Tóm lại, thuật toán Perceptron có thể được viết như sau:

Tóm tắt PLA

1. Chọn ngẫu nhiên một vector hệ số ww với các phần tử gần 0.

2. Duyệt ngẫu nhiên qua từng điểm dữ liệu xixi:
o Nếu xixi được phân lớp đúng, tức sgn(wTxi)=yisgn(wTxi)=yi, chúng ta không cần làm
gì.
o Nếu xixi bị misclassifed, cập nhật ww theo công thức:w=w+yixiw=w+yixi
3. Kiểm tra xem có bao nhiêu điểm bị misclassifed. Nếu không còn điểm nào, dừng thuật toán.
Nếu còn, quay lại bước 2.

3. Ví dụ trên Python

Như thường lệ, chúng ta sẽ thử một ví dụ nhỏ với Python.

Load thư viện và tạo dữ liệu

Chúng ta sẽ tạo hai nhóm dữ liệu, mỗi nhóm có 10 điểm, mỗi điểm dữ liệu có hai chiều để thuận tiện
cho việc minh họa. Sau đó, tạo dữ liệu mở rộng bằng cách thêm 1 vào đầu mỗi điểm dữ liệu.

# generate data

# list of points

import numpy as np

import matplotlib.pyplot as plt

from scipy.spatial.distance import cdist

np.random.seed(2)

means = [[2, 2], [4, 2]]

cov = [[.3, .2], [.2, .3]]

N = 10

X0 = np.random.multivariate_normal(means[0], cov, N).T

X1 = np.random.multivariate_normal(means[1], cov, N).T

X = np.concatenate((X0, X1), axis = 1)

y = np.concatenate((np.ones((1, N)), -1*np.ones((1, N))), axis = 1)

# Xbar
26 | P a g e

X = np.concatenate((np.ones((1, 2*N)), X), axis = 0)

Sau khi thực hiện đoạn code này, biến X sẽ chứa dữ liệu input (mở rộng), biến y sẽ chứa nhãn của mỗi
điểm dữ liệu trong X.

Các hàm số cho PLA

Tiếp theo chúng ta cần viết 3 hàm số cho PLA:

1. h(w, x): tính đầu ra khi biết đầu vào x và weights w.

2. has_converged(X, y, w): kiểm tra xem thuật toán đã hội tụ chưa. Ta chỉ cần so sánh h(w,
X) với ground truth y. Nếu giống nhau thì dừng thuật toán.
3. perceptron(X, y, w_init): hàm chính thực hiện PLA.

def h(w, x):

return np.sign(np.dot(w.T, x))

def has_converged(X, y, w):

return np.array_equal(h(w, X), y)

def perceptron(X, y, w_init):

w = [w_init]

N = X.shape[1]

d = X.shape[0]

mis_points = []

while True:

# mix data

mix_id = np.random.permutation(N)

for i in range(N):

xi = X[:, mix_id[i]].reshape(d, 1)

yi = y[0, mix_id[i]]

if h(w[-1], xi)[0] != yi: # misclassified point

mis_points.append(mix_id[i])

w_new = w[-1] + yi*xi

w.append(w_new)

if has_converged(X, y, w[-1]):

break
27 | P a g e

return (w, mis_points)

d = X.shape[0]

w_init = np.random.randn(d, 1)

(w, m) = perceptron(X, y, w_init)

Dưới đây là hình minh họa thuật toán PLA cho bài toán nhỏ này:

Hình 4: Minh họa thuật toán PLA

Sau khi cập nhật 18 lần, PLA đã hội tụ. Điểm được khoanh tròn màu đen là điểm misclassified tương
ứng được chọn để cập nhật đường boundary.

Source code cho phần này (bao gồm hình động) có thể được tìm thấy ở đây.

4. Chứng minh hội tụ

Giả sử rằng w∗w∗ là một nghiệm của bài toán (ta có thể giả sử việc này được vì chúng ta đã có giả
thiết hai class là linearly separable - tức tồn tại nghiệm). Có thể thấy rằng, với mọi α>0α>0, nếu w∗w∗ là
nghiệm, αw∗αw∗ cũng là nghiệm của bài toán. Xét dãy số không
âm uα(t)=||wt−αw∗||22uα(t)=||wt−αw∗||22. Với xixi là một điểm bị misclassified nếu dùng nghiệm wtwt ta
có:
uα(t+1)=||wt+1−αw∗||22=||wt+yixi−αw∗||22=||wt−αw∗||22+y2i||xi||22+2yixTi(w−αw∗)<uα(t) +||xi||22−2αyixTiw
∗uα(t+1)=||wt+1−αw∗||22=||wt+yixi−αw∗||22=||wt−αw∗||22+yi2||xi||22+2yixiT(w−αw∗)<uα(t) +||xi||22−2α
yixiTw∗
Dấu nhỏ hơn ở dòng cuối là vì y2i=1yi2=1 và 2yixTiwt<02yixiTwt<0. Nếu ta đặt:
β2=maxi=1,2,…,N||xi||22γ=mini=1,2,…,NyixTiw∗β2=maxi=1,2,…,N||xi||22γ=mini=1,2,…,NyixiTw∗
và chọn α=β2γα=β2γ, ta có:0≤uα(t+1)<uα(t)+β2−2αγ=uα(t)−β20≤uα(t+1)<uα(t)+β2−2αγ=uα(t)−β2
Điều này nghĩa là: nếu luôn luôn có các điểm bị misclassified thì dãy uα(t)uα(t) là dãy giảm, bị chặn
dưới bởi 0, và phần tử sau kém phần tử trước ít nhất một lượng là β2>0β2>0. Điều vô lý này chứng tỏ
28 | P a g e

đến một lúc nào đó sẽ không còn điểm nào bị misclassified. Nói cách khác, thuật toán PLA hội tụ sau
một số hữu hạn bước.

5. Mô hình Neural Network đầu tiên

Hàm số xác định class của Perceptron label(x)=sgn(wTx)label(x)=sgn(wTx) có thể được mô tả như hình
vẽ (được gọi là network) dưới đây:

Hình 5: Biểu diễn của Perceptron dưới dạng Neural Network.

Đầu vào của network xx được minh họa bằng các node màu xanh lục với node x0x0 luôn luôn bằng 1.
Tập hợp các node màu xanh lục được gọi là Input layer. Trong ví dụ này, tôi giả sử số chiều của dữ
liệu d=4d=4. Số node trong input layer luôn luôn là d+1d+1 với một node là 1 được thêm vào.
Node x0=1x0=1 này đôi khi được ẩn đi.
Các trọng số (weights) w0,w1,…,wdw0,w1,…,wd được gán vào các mũi tên đi tới
node z=d∑i=0wixi=wTxz=∑i=0dwixi=wTx. Node y=sgn(z)y=sgn(z) là output của network. Ký hiệu hình
chữ Z ngược màu xanh trong node yy thể hiện đồ thị của hàm số sgnsgn.
Trong thuật toán PLA, ta phải tìm các weights trên các mũi tên sao cho với mỗi xixi ở tập các điểm dữ
liệu đã biết được đặt ở Input layer, output của network này trùng với nhãn yiyi tương ứng.
Hàm số y=sgn(z)y=sgn(z) còn được gọi là activation function. Đây chính là dạng đơn giản nhất của
Neural Network.
Các Neural Networks sau này có thể có nhiều node ở output tạo thành một output layer, hoặc có thể
có thêm các layer trung gian giữa input layer và output layer. Các layer trung gian đó được gọi là hidden
layer. Khi biểu diễn các Networks lớn, người ta thường giản lược hình bên trái thành hình bên phải.
Trong đó node x0=1x0=1 thường được ẩn đi. Node zz cũng được ẩn đi và viết gộp vào trong node yy.
Perceptron thường được vẽ dưới dạng đơn giản như Hình 5 bên phải.
Để ý rằng nếu ta thay activation function bởi y=zy=z, ta sẽ có Neural Network mô tả thuật toán Linear
Regression như hình dưới. Với đường thẳng chéo màu xanh thể hiện đồ thị hàm số y=zy=z. Các trục
tọa độ đã được lược bỏ.
29 | P a g e

Hình 6: Biểu diễn của Linear Regression dưới dạng Neural Network.

Mô hình perceptron ở trên khá giống với một node nhỏ của dây thân kinh sinh học như hình sau đây:

Hình 7: Mô tả một neuron thần kinh sinh học. (Nguồn: Single-Layer Neural Networks and Gradient
Descent)

Dữ liệu từ nhiều dây thần kinh đi về một cell nucleus. Thông tin được tổng hợp và được đưa ra ở output.
Nhiều bộ phận như thế này kết hợp với nhau tạo nên hệ thần kinh sinh học. Chính vì vậy mà có tên
Neural Networks trong Machine Learning. Đôi khi mạng này còn được gọi là Artificial Neural Networks
(ANN) tức hệ neuron nhân tạo.

6. Thảo Luận

PLA có thể cho vô số nghiệm khác nhau

Rõ ràng rằng, nếu hai class là linearly separable thì có vô số đường thằng phân cách 2 class đó. Dưới
đây là một ví dụ:

Hình 8: PLA có thể cho vô số nghiệm khác nhau.

30 | P a g e

Tất cả các đường thẳng màu đen đều thỏa mãn. Tuy nhiên, các đường khác nhau sẽ quyết định điểm
hình tam giác thuộc các lớp khác nhau. Trong các đường đó, đường nào là tốt nhất? Và định nghĩa “tốt
nhất” được hiểu theo nghĩa nào? Có một thuật toán khác định nghĩa và tìm đường tốt nhất như thế, tôi
sẽ giới thiệu trong 1 vài bài tới. Mời các bạn đón đọc.

PLA đòi hỏi dữ liệu linearly separable

Hai class trong ví dụ dưới đây tương đối linearly separable. Mỗi class có 1 điểm coi như nhiễu nằm
trong khu vực các điểm của class kia. PLA sẽ không làm việc trong trường hợp này vì luôn luôn có ít
nhất 2 điểm bị misclassified.

Hinhf 9: PLA không làm việc nếu chỉ có một nhiễu nhỏ.

Trong một chừng mực nào đó, đường thẳng màu đen vẫn có thể coi là một nghiệm tốt vì nó đã giúp
phân loại chính xác hầu hết các điểm. Việc không hội tụ với dữ liệu gần linearly separable chính là một
nhược điểm lớn của PLA.

Để khắc phục nhược điểm này, có một cải tiến nhỏ như thuật toán Pocket Algorithm dưới đây:

Pocket Algorithm

Một cách tự nhiên, nếu có một vài nhiễu, ta sẽ đi tìm một đường thẳng phân chia hai class sao cho có
ít điểm bị misclassified nhất. Việc này có thể được thực hiện thông qua PLA với một chút thay đổi nhỏ
như sau:

1. Giới hạn số lượng vòng lặp của PLA.

2. Mỗi lần cập nhật nghiệm ww mới, ta đếm xem có bao nhiêu điểm bị misclassified. Nếu là lần
đầu tiên, giữ lại nghiệm này trong pocket (túi quần). Nếu không, so sánh số điểm misclassified
này với số điểm misclassified của nghiệm trong pocket, nếu nhỏ hơn thì lôi nghiệm cũ ra, đặt
nghiệm mới này vào.

Thuật toán này giống với thuật toán tìm phần tử nhỏ nhất trong 1 mảng.

7. Kết luận

Hy vọng rằng bài viết này sẽ giúp các bạn phần nào hiểu được một số khái niệm trong Neural Networks.
Trong một số bài tiếp theo, tôi sẽ tiếp tục nói về các thuật toán cơ bản khác trong Neural Networks
trước khi chuyển sang phần khác.

Trong tương lai, nếu có thể, tôi sẽ viết tiếp về Deep Learning và chúng ta sẽ lại quay lại với Neural
Networks.
31 | P a g e

Bài 10: Logistic Regression

1. Giới thiệu

Nhắc lại hai mô hình tuyến tính

Hai mô hình tuyến tính (linear models) Linear Regression và Perceptron Learning Algorithm (PLA)
chúng ta đã biết đều có chung một dạng:y=f(wTx)y=f(wTx)
trong đó f()f() được gọi là activation function, và xx được hiểu là dữ liệu mở rộng với x0=1x0=1 được
thêm vào để thuận tiện cho việc tính toán. Với linear regression thì f(s)=sf(s)=s, với PLA
thì f(s)=sgn(s)f(s)=sgn(s). Trong linear regression, tích vô hướng wTxwTx được trực tiếp sử dụng để dự
đoán output yy, loại này phù hợp nếu chúng ta cần dự đoán một giá trị thực của đầu ra không bị chặn
trên và dưới. Trong PLA, đầu ra chỉ nhận một trong hai giá trị 11 hoặc −1−1, phù hợp với các bài
toán binary classification.
Trong bài này, tôi sẽ giới thiệu mô hình thứ ba với một activation khác, được sử dụng cho các bài
toán flexible hơn. Trong dạng này, đầu ra có thể được thể hiện dưới dạng xác suất (probability). Ví dụ:
xác suất thi đỗ nếu biết thời gian ôn thi, xác suất ngày mai có mưa dựa trên những thông tin đo được
trong ngày hôm nay,… Mô hình mới này của chúng ta có tên là logistic regression. Mô hình này giống
với linear regression ở khía cạnh đầu ra là số thực, và giống với PLA ở việc đầu ra bị chặn (trong
đoạn [0,1][0,1]). Mặc dù trong tên có chứa từ regression, logistic regression thường được sử dụng
nhiều hơn cho các bài toán classification.

Một ví dụ nhỏ

Tôi xin được sử dụng một ví dụ trên Wikipedia:

Một nhóm 20 sinh viên dành thời gian trong khoảng từ 0 đến 6 giờ cho việc ôn thi. Thời gian ôn thi này
ảnh hưởng đến xác suất sinh viên vượt qua kỳ thi như thế nào?
Kết quả thu được như sau:

Hours Pass Hours Pass

.5 0 2.75 1

.75 0 3 0

1 0 3.25 1

1.25 0 3.5 0

1.5 0 4 1

1.75 0 4.25 1

1.75 1 4.5 1

2 0 4.75 1

2.25 1 5 1

2.5 0 5.5 1

Mặc dù có một chút bất công khi học 3.5 giờ thì trượt, còn học 1.75 giờ thì lại đỗ, nhìn chung, học càng
nhiều thì khả năng đỗ càng cao. PLA không thể áp dụng được cho bài toán này vì không thể nói một
người học bao nhiêu giờ thì 100% trượt hay đỗ, và thực tế là dữ liệu này cũng không linearly
separable(điệu kiện để PLA có thể làm việc). Chú ý rằng các điểm màu đỏ và xanh được vẽ ở hai tung
độ khác nhau để tiện cho việc minh họa. Các điểm này được vẽ dùng cả dữ liệu đầu vào xx và đầu ra
\(y). Khi ta nói linearly seperable là khi ta chỉ dùng dữ liệu đầu vào xx.
Chúng ta biểu diễn các điểm này trên đồ thị để thấy rõ hơn:
32 | P a g e

Hình 1: Ví dụ về kết quả thi dựa trên số giờ ôn tập.

Nhận thấy rằng cả linear regression và PLA đều không phù hợp với bài toán này, chúng ta cần một mô
hình flexible hơn.

Mô hình Logistic Regression

Đầu ra dự đoán của:

 Linear Regression:f(x)=wTxf(x)=wTx
 PLA:f(x)=sgn(wTx)f(x)=sgn(wTx)

Đầu ra dự đoán của logistic regression thường được viết chung dưới dạng:f(x)=θ(wTx)f(x)=θ(wTx)
Trong đó θθ được gọi là logistic function. Một số activation cho mô hình tuyến tính được cho trong hình
dưới đây:

Hình 2: Các activation function khác nhau.

 Đường màu vàng biểu diễn linear regression. Đường này không bị chặn nên không phù hợp
cho bài toán này. Có một trick nhỏ để đưa nó về dạng bị chặn: cắt phần nhỏ hơn 0 bằng cách
cho chúng bằng 0, cắt các phần lớn hơn 1 bằng cách cho chúng bằng 1. Sau đó lấy điểm trên
đường thẳng này có tung độ bằng 0.5 làm điểm phân chia hai class, đây cũng không phải là
một lựa chọn tốt. Giả sử có thêm vài bạn sinh viên tiêu biểu ôn tập đến 20 giờ và, tất nhiên, thi
đỗ. Khi áp dụng mô hình linear regression như hình dưới đây và lấy mốc 0.5 để phân lớp, toàn
bộ sinh viên thi trượt vẫn được dự đoán là trượt, nhưng rất nhiều sinh viên thi đỗ cũng được
dự đoán là trượt (nếu ta coi điểm x màu xanh lục là ngưỡng cứng để đưa ra kết luận). Rõ ràng
đây là một mô hình không tốt. Anh chàng sinh viên tiêu biểu này đã kéo theo rất nhiều bạn
khác bị trượt.
33 | P a g e

Hình 3: Tại sao Linear Regression không phù hợp?

 Đường màu đỏ (chỉ khác với activation function của PLA ở chỗ hai class là 0 và 1 thay vì -1 và
1) cũng thuộc dạng ngưỡng cứng (hard threshold). PLA không hoạt động trong bài toán này vì
dữ liệu đã cho không linearly separable.
 Các đường màu xanh lam và xanh lục phù hợp với bài toán của chúng ta hơn. Chúng có một
vài tính chất quan trọng sau:

o Là hàm số liên tục nhận giá trị thực, bị chặn trong khoảng (0,1)(0,1).
o Nếu coi điểm có tung độ là 1/2 làm điểm phân chia thì các điểm càng xa điểm này về
phía bên trái có giá trị càng gần 0. Ngược lại, các điểm càng xa điểm này về phía phải
có giá trị càng gần 1. Điều này khớp với nhận xét rằng học càng nhiều thì xác suất đỗ
càng cao và ngược lại.
o Mượt (smooth) nên có đạo hàm mọi nơi, có thể được lợi trong việc tối ưu.

Sigmoid function

Trong số các hàm số có 3 tính chất nói trên thì hàm sigmoid:f(s)=11+e−s≜σ(s)f(s)=11+e−s≜σ(s)được
sử dụng nhiều nhất, vì nó bị chặn trong khoảng (0,1)(0,1). Thêm
nữa:lims→−∞σ(s)=0; lims→+∞σ(s)=1lims→−∞σ(s)=0; lims→+∞σ(s)=1Đặc biệt hơn
nữa:σ′(s)=e−s(1+e−s)2=11+e−se−s1+e−s=σ(s)(1−σ(s))σ′(s)=e−s(1+e−s)2=11+e−se−s1+e−s=σ(s)(1−σ(s))
Công thức đạo hàm đơn giản thế này giúp hàm số này được sử dụng rộng rãi. Ở phần sau, tôi sẽ lý
giải việc người ta đã tìm ra hàm số đặc biệt này như thế nào.
Ngoài ra, hàm tanh cũng hay được sử dụng:tanh(s)=es−e−ses+e−stanh(s)=es−e−ses+e−s
Hàm số này nhận giá trị trong khoảng (−1,1)(−1,1) nhưng có thể dễ dàng đưa nó về khoảng (0,1)(0,1).
Bạn đọc có thể chứng minh được:tanh(s)=2σ(2s)−1tanh(s)=2σ(2s)−1

2. Hàm mất mát và phương pháp tối ưu

Xây dựng hàm mất mát

Với mô hình như trên (các activation màu xanh lam và lục), ta có thể giả sử rằng xác suất để một điểm
dữ liệu xx rơi vào class 1 là f(wTx)f(wTx) và rơi vào class 0 là 1−f(wTx)1−f(wTx). Với mô hình được giả
sử như vậy, với các điểm dữ liệu training (đã biết đầu ra yy), ta có thể viết như sau:
P(yi=1|xi;w)=f(wTxi) (1)P(yi=0|xi;w)=1−f(wTxi) (2)P(yi=1|xi;w)=f(wTxi) (1)P(yi=0|xi;w)=1−f(wTxi) (2)tr
ong đó P(yi=1|xi;w)P(yi=1|xi;w) được hiểu là xác suất xảy ra sự kiện đầu ra yi=1yi=1 khi biết tham số
mô hình ww và dữ liệu đầu vào xixi. Bạn đọc có thể đọc thêm Xác suất có điều kiện. Mục đích của
chúng ta là tìm các hệ số ww sao cho f(wTxi)f(wTxi) càng gần với 1 càng tốt với các điểm dữ liệu thuộc
class 1 và càng gần với 0 càng tốt với những điểm thuộc class 0.
Ký hiệu zi=f(wTxi)zi=f(wTxi) và viết gộp lại hai biểu thức bên trên ta
có:P(yi|xi;w)=zyii(1−zi)1−yiP(yi|xi;w)=ziyi(1−zi)1−yi
Biểu thức này là tương đương với hai biểu thức (1)(1) và (2)(2) ở trên vì khi yi=1yi=1, phần thứ hai của
vế phải sẽ triệt tiêu, khi yi=0yi=0, phần thứ nhất sẽ bị triệt tiêu! Chúng ta muốn mô hình gần với dữ liệu
đã cho nhất, tức xác suất này đạt giá trị cao nhất.
34 | P a g e

Xét toàn bộ training set

với X=[x1,x2,…,xN]∈Rd×NX=[x1,x2,…,xN]∈Rd×N và y=[y1,y2,…,yN]y=[y1,y2,…,yN], chúng ta cần
tìm ww để biểu thức sau đây đạt giá trị lớn nhất:P(y|X;w)P(y|X;w)ở đây, ta cũng ký hiệu X,yX,y như
các biến ngẫu nhiên (random variables). Nói cách khác:w=argmaxwP(y|X;w)w=arg⁡maxwP(y|X;w)
Bài toán tìm tham số để mô hình gần với dữ liệu nhất trên đây có tên gọi chung là bài toán maximum
likelihood estimation với hàm số phía sau argmaxarg⁡max được gọi là likelihood function. Khi làm việc
với các bài toán Machine Learning sử dụng các mô hình xác suất thống kê, chúng ta sẽ gặp lại các bài
toán thuộc dạng này, hoặc maximum a posteriori estimation, rất nhiều. Tôi sẽ dành 1 bài khác để nói
về hai dạng bài toán này.
Giả sử thêm rằng các điểm dữ liệu được sinh ra một cách ngẫu nhiên độc lập với nhau (independent),
ta có thể
viết:P(y|X;w)=N∏i=1P(yi|xi;w)=N∏i=1zyii(1−zi)1−yiP(y|X;w)=∏i=1NP(yi|xi;w)=∏i=1Nziyi(1−zi)1−yivới
∏∏ là ký hiệu của tích. Bạn đọc có thể muốn đọc thêm về Độc lập thống kê.
Trực tiếp tối ưu hàm số này theo ww nhìn qua không đơn giản! Hơn nữa, khi NN lớn, tích của NN số
nhỏ hơn 1 có thể dẫn tới sai số trong tính toán (numerial error) vì tích là một số quá nhỏ. Một phương
pháp thường được sử dụng đó là lấy logarit tự nhiên (cơ số ee) của likelihood function biến phép nhân
thành phép cộng và để tránh việc số quá nhỏ. Sau đó lấy ngược dấu để được một hàm và coi nó là
hàm mất mát. Lúc này bài toán tìm giá trị lớn nhất (maximum likelihood) trở thành bài toán tìm giá trị
nhỏ nhất của hàm mất mát (hàm này còn được gọi là negative log
likelihood):J(w)=−logP(y|X;w)=−N∑i=1(yilogzi+(1−yi)log(1−zi))J(w)=−log⁡P(y|X;w)=−∑i=1N(yilog⁡zi+(1
−yi)log⁡(1−zi))với chú ý rằng zizi là một hàm số của ww. Bạn đọc tạm nhớ biểu thức vế phải có tên gọi
là cross entropy, thường được sử dụng để đo khoảng cách giữa hai phân phối (distributions). Trong
bài toán đang xét, một phân phối là dữ liệu được cho, với xác suất chỉ là 0 hoặc 1; phân phối còn lại
được tính theo mô hình logistic regression. Khoảng cách giữa hai phân phối nhỏ đồng nghĩa với việc
(có vẻ hiển nhiên là) hai phân phối đó rất gần nhau. Tính chất cụ thể của hàm số này sẽ được đề cập
trong một bài khác mà tầm quan trọng của khoảng cách giữa hai phân phối là lớn hơn.
Chú ý: Trong machine learning, logarit thập phân ít được dùng, vì vậy loglog thường được dùng để ký
hiệu logarit tự nhiên.

Tối ưu hàm mất mát

Chúng ta lại sử dụng phương pháp Stochastic Gradient Descent (SGD) ở đây (Bạn đọc được khuyến
khích đọc SGD trước khi đọc phần này) . Hàm mất mát với chỉ một điểm dữ
liệu (xi,yi)(xi,yi) là:J(w;xi,yi)=−(yilogzi+(1−yi)log(1−zi))J(w;xi,yi)=−(yilog⁡zi+(1−yi)log⁡(1−zi))
Với đạo
hàm:∂J(w;xi,yi)∂w=−(yizi−1−yi1−zi)∂zi∂w=zi−yizi(1−zi)∂zi∂w (3)∂J(w;xi,yi)∂w=−(yizi−1−yi1−zi)∂zi∂w=
zi−yizi(1−zi)∂zi∂w (3)
Để cho biểu thức này trở nên gọn và đẹp hơn, chúng ta sẽ tìm hàm z=f(wTx)z=f(wTx) sao cho mẫu số
bị triệt tiêu. Nếu đặt s=wTxs=wTx, chúng ta sẽ có:∂zi∂w=∂zi∂s∂s∂w=∂zi∂sx∂zi∂w=∂zi∂s∂s∂w=∂zi∂sxMột
cách trực quan nhất, ta sẽ tìm hàm số z=f(s)z=f(s) sao cho:∂z∂s=z(1−z) (4)∂z∂s=z(1−z) (4)để triệt tiêu
mẫu số trong biểu thức (3)(3). Chúng ta cùng khởi động một chút với phương trình vi phân đơn giản
này. Phương trình (4)(4) tương đương
với:∂zz(1−z)=∂s⇔(1z+11−z)∂z=∂s⇔logz−log(1−z)=s⇔logz1−z=s⇔z1−z=es⇔z=es(1−z)⇔z=es1+es=11+e−s
=σ(s)∂zz(1−z)=∂s⇔(1z+11−z)∂z=∂s⇔log⁡z−log⁡(1−z)=s⇔log⁡z1−z=s⇔z1−z=es⇔z=es(1−z)⇔z=es
1+es=11+e−s=σ(s)Đến đây, tôi hy vọng các bạn đã hiểu hàm số sigmoid được tạo ra như thế nào.
Chú ý: Trong việc giải phương trình vi phân ở trên, tôi đã bỏ qua hằng số khi lấy nguyên hàm hai vế.
Tuy vậy, việc này không ảnh hưởng nhiều tới kết quả.

Công thức cập nhật cho logistic sigmoid regression

Tới đây, bạn đọc có thể kiểm tra rằng:∂J(w;xi,yi)∂w=(zi−yi)xi∂J(w;xi,yi)∂w=(zi−yi)xiQúa đẹp!

Và công thức cập nhật (theo thuật toán SGD) cho logistic regression
là:w=w+η(yi−zi)xiw=w+η(yi−zi)xiKhá đơn giản! Và, như thường lệ, chúng ta sẽ có vài ví dụ với Python.

3. Ví dụ với Python

Ví dụ với dữ liệu 1 chiều

35 | P a g e

Quay trở lại với ví dụ nêu ở phần Giới thiệu. Trước tiên ta cần khai báo vài thư viện và dữ liệu:

# To support both python 2 and python 3

from __future__ import division, print_function, unicode_literals

import numpy as np

import matplotlib.pyplot as plt

np.random.seed(2)

X = np.array([[0.50, 0.75, 1.00, 1.25, 1.50, 1.75, 1.75, 2.00, 2.25, 2.50,

2.75, 3.00, 3.25, 3.50, 4.00, 4.25, 4.50, 4.75, 5.00, 5.50]])

y = np.array([0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1])

# extended data

X = np.concatenate((np.ones((1, X.shape[1])), X), axis = 0)

Các hàm cần thiết cho logistic sigmoid regression

def sigmoid(s):

return 1/(1 + np.exp(-s))

def logistic_sigmoid_regression(X, y, w_init, eta, tol = 1e-4, max_count = 10000):

w = [w_init]

it = 0

N = X.shape[1]

d = X.shape[0]

count = 0

check_w_after = 20

while count < max_count:

# mix data

mix_id = np.random.permutation(N)

for i in mix_id:

xi = X[:, i].reshape(d, 1)

yi = y[i]

zi = sigmoid(np.dot(w[-1].T, xi))

w_new = w[-1] + eta*(yi - zi)*xi

36 | P a g e

count += 1

# stopping criteria

if count%check_w_after == 0:

if np.linalg.norm(w_new - w[-check_w_after]) < tol:

return w

w.append(w_new)

return w

eta = .05

d = X.shape[0]

w_init = np.random.randn(d, 1)

w = logistic_sigmoid_regression(X, y, w_init, eta)

print(w[-1])

[[-4.092695 ]

[ 1.55277242]]

Với kết quả tìm được, đầu ra yy có thể được dự đoán theo công thức: y = sigmoid(-4.1 + 1.55*x).
Với dữ liệu trong tập training, kết quả là:

print(sigmoid(np.dot(w[-1].T, X)))

[[ 0.03281144 0.04694533 0.06674738 0.09407764 0.13102736 0.17961209

0.17961209 0.24121129 0.31580406 0.40126557 0.49318368 0.58556493

0.67229611 0.74866712 0.86263755 0.90117058 0.92977426 0.95055357

0.96541314 0.98329067]]

Biểu diễn kết quả này trên đồ thị ta có:

X0 = X[1, np.where(y == 0)][0]

y0 = y[np.where(y == 0)]

X1 = X[1, np.where(y == 1)][0]

y1 = y[np.where(y == 1)]

plt.plot(X0, y0, 'ro', markersize = 8)

plt.plot(X1, y1, 'bs', markersize = 8)

xx = np.linspace(0, 6, 1000)
37 | P a g e

w0 = w[-1][0][0]

w1 = w[-1][1][0]

threshold = -w0/w1

yy = sigmoid(w0 + w1*xx)

plt.axis([-2, 8, -1, 2])

plt.plot(xx, yy, 'g-', linewidth = 2)

plt.plot(threshold, .5, 'y^', markersize = 8)

plt.xlabel('studying hours')

plt.ylabel('predicted probability of pass')

plt.show()

Hình 4: Dữ liệu và hàm sigmoid tìm được.

Nếu như chỉ có hai output là ‘fail’ hoặc ‘pass’, điểm trên đồ thị của hàm sigmoid tương ứng với xác suất
0.5 được chọn làm hard threshold (ngưỡng cứng). Việc này có thể chứng minh khá dễ dàng (tôi sẽ bàn
ở phần dưới).

Ví dụ với dữ liệu 2 chiều

Chúng ta xét thêm một ví dụ nhỏ nữa trong không gian hai chiều. Giả sử chúng ta có hai class xanh-
đỏ với dữ liệu được phân bố như hình dưới.
38 | P a g e

Hình 5: Hai class với dữ liệu hai chiều.

Với dữ liệu đầu vào nằm trong không gian hai chiều, hàm sigmoid có dạng như thác nước dưới đây:

Hình 6: Hàm sigmoid với dữ liệu có chiều là 2. (Nguồn: Biased and non biased neurons)

Kết quả tìm được khi áp dụng mô hình logistic regression được minh họa như hình dưới với màu nền
khác nhau thể hiện xác suất điểm đó thuộc class đỏ. Đỏ hơn tức gần 1 hơn, xanh hơn tức gần 0 hơn.
39 | P a g e

Hình 7: Logistic Regression với dữ liệu hai chiều.

Nếu phải lựa chọn một ngưỡng cứng (chứ không chấp nhận xác suất) để phân chia hai class, chúng
ta quan sát thấy đường thẳng nằm nằm trong khu vực xanh lục là một lựa chọn hợp lý. Tôi sẽ chứng
minh ở phần dưới rằng, đường phân chia giữa hai class tìm được bởi logistic regression có dạng một
đường phẳng, tức vẫn là linear.

4. Một vài tính chất của Logistic Regression

Logistic Regression thực ra được sử dụng nhiều trong các bài toán Classification.

Mặc dù có tên là Regression, tức một mô hình cho fitting, Logistic Regression lại được sử dụng nhiều
trong các bài toán Classification. Sau khi tìm được mô hình, việc xác định class yy cho một điểm dữ
liệu xxđược xác định bằng việc so sánh hai biểu thức xác
suất:P(y=1|x;w); P(y=0|x;w)P(y=1|x;w); P(y=0|x;w)Nếu biểu thức thứ nhất lớn hơn thì ta kết luận điểm
dữ liệu thuộc class 1, ngược lại thì nó thuộc class 0. Vì tổng hai biểu thức này luôn bằng 1 nên một
cách gọn hơn, ta chỉ cần xác định xem P(y=1|x;w)P(y=1|x;w)lớn hơn 0.5 hay không. Nếu có, class 1.
Nếu không, class 0.

Boundary tạo bởi Logistic Regression có dạng tuyến tính

Thật vậy, theo lập luận ở phần trên thì chúng ta cần kiểm tra:

P(y=1|x;w)>0.5⇔11+e−wTx>0.5⇔e−wTx<1⇔wTx>0P(y=1|x;w)>0.5⇔11+e−wTx>0.5⇔e−wTx<1⇔wTx
>0
Nói cách khác, boundary giữa hai class là đường có phương trình wTxwTx. Đây chính là phương trình
của một siêu mặt phẳng. Vậy Logistic Regression tạo ra boundary có dạng tuyến tính.

5. Thảo luận

 Một điểm cộng cho Logistic Regression so với PLA là nó không cần có giả thiết dữ liệu hai
class là linearly separable. Tuy nhiên, boundary tìm được vẫn có dạng tuyến tính. Vậy nên mô
hình này chỉ phù hợp với loại dữ liệu mà hai class là gần với linearly separable. Một kiểu dữ
liệu mà Logistic Regression không làm việc được là dữ liệu mà một class chứa các điểm nằm
trong 1 vòng tròn, class kia chứa các điểm bên ngoài đường tròn đó. Kiểu dữ liệu này được
gọi là phi tuyến (non-linear). Sau một vài bài nữa, tôi sẽ giới thiệu với các bạn các mô hình
khác phù hợp hơn với loại dữ liệu này hơn.
 Một hạn chế nữa của Logistic Regression là nó yêu cầu các điểm dữ liệu được tạo ra một
cách độc lập với nhau. Trên thực tế, các điểm dữ liệu có thể bị ảnh hưởng bởi nhau. Ví dụ: có
40 | P a g e

một nhóm ôn tập với nhau trong 4 giờ, cả nhóm đều thi đỗ (giả sử các bạn này học rất tập
trung), nhưng có một sinh viên học một mình cũng trong 4 giờ thì xác suất thi đỗ thấp hơn.
Mặc dù vậy, để cho đơn giản, khi xây dựng mô hình, người ta vẫn thường giả sử các điểm dữ
liệu là độc lập với nhau.
 Khi biểu diễn theo Neural Networks, Linear Regression, PLA, và Logistic Regression có dạng
như sau:

Hình 8: Biểu diễn Linear Regression, PLA, và Logistic Regression theo Neural network.

 Nếu hàm mất mát của Logistic Regression được viết dưới
dạng:J(w)=N∑i=1(yi−zi)2J(w)=∑i=1N(yi−zi)2thì khó khăn gì sẽ xảy ra? Các bạn hãy coi đây như
một bài tập nhỏ.
 Source code cho các ví dụ trong bài này có thể tìm thấy ở đây.