Thuật toán Gradient Descent

Bài viết được sự cho phép của tác giả Kien Dang Chung

Video trong bài viết

Trong các bài toán machine learning hoặc các bài toán tối ưu, chúng ta thường phải làm việc với những điểm cực trị (thường là điểm cực tiểu) của một hàm số. Hẳn bạn còn nhớ trong Phần 1 của khóa học này về dự đoán doanh thu phim với Linear Regression, chúng ta đã phải cố gắng tìm giá trị nhỏ nhất của hàm chi phí (cost function) mà đôi khi còn gọi là hàm mất mát (loss function). Vậy Thuật toán Gradient Descent là gì?, Gradien Descent có liên hệ gì với việc tìm kiếm cực trị bài toán tối ưu?, chúng ta sẽ cùng tìm hiểu trong bài học này nhé.

Tại sao lại dùng Gradle thay thế Maven và Ant

10 PHP Instagram Scripts & Widgets tốt nhất

1. Thuật toán Gradient Descent là gì?

Trong kiến thức toán phổ thông chúng ta đã biết, muốn tìm cực trị một hàm số $y = f (x)$ chúng ta sẽ giải phương trình đạo hàm của hàm số $f (x)$ bằng 0.

f' (x) = 0

Tuy nhiên phương trình trên không phải lúc nào cũng giải được dễ dàng, có những trường hợp việc giải phương trình trên là bất khả thi. Vậy khi gặp những tình huống này, chúng ta phải làm gì? May thay, thuật toán Gradient Descent cho chúng ta cách thức tìm các điểm cực tiểu cục bộ này một cách xấp xỉ sau một số vòng lặp. Trong thực tế, các giá trị dữ liệu không có đúng 100% mà đôi khi chúng ta chỉ cần những con số gần đúng. Khi một người hỏi tôi, xác suất cho lần đầu tư chứng khoán lần này là 72%, tôi có nên đầu tư không? Thật sự mà nói 72% đã là một con số khá ấn tượng, mọi thứ ngoài đời không bao giờ có $1 + 1 = 2$ , nên những cách tính toán xấp xỉ, gần đúng là một giải pháp tuyệt vời.

Trước khi đi vào chi tiết thuật toán Gradient Descent, chúng ta hãy cùng trải nghiệm với một tình huống sau đây. Bạn đang ở trên một ngọn núi đầy sương mù, tầm nhìn bị hạn chế, làm cách nào để có thể xuống được thung lũng một cách nhanh nhất (Ở đây thung lũng chính là những điểm cực tiểu trong bài toán tối ưu). Cách đơn giản là nhìn xung quanh chỗ nào cảm nhận dốc nhất thì bạn bước xuống và từng bước một, cho đến khi bạn không cảm nhận được xung quanh có độ dốc thì đấy chính là thung lũng, nơi bằng phẳng và là điểm cực tiểu của đồ thị.

Tuyệt vời phải không, thuật toán Gradient Descent mô tả chính xác những gì bạn đang trải nghiệm ở tình huống trên. Trong bài viết về Đạo hàm hàm số, độ dốc (slope) của hàm số tại điểm $x_{0}$ chính là đạo hàm của hàm số tại điểm $x_{0}$ . Bước đi xuống từ điểm $x_{0}$ sang điểm $x_{1}$ sẽ bằng $Δ_{0}$ . Ta có:

x 1 = x 0 + Δ 0

Chúng ta sẽ tìm hiểu xem thành phần của $Δ_{0}$ là gì? Để hướng đi xuống chúng ta có

Δ 0 = - η f' (x 0)

Dấu âm trong độ dốc nghĩa là chúng ta đang đi xuống và với hệ số $η$ . Vậy ta có thể viết lại

x 1 = x 0 - η f' (x 0)

Như vậy tại bước thứ n chúng ta có:

x n = x n - 1 + Δ n - 1 = x n - 1 - η f' (x n - 1)

Nhưng đến khi nào thì kết thúc không bước tiếp? Như trong tình huống, khi nào cảm thấy xung quanh không còn dốc, nghĩa là khi đó $x_{n} \approx x_{n - 1}$ hay $x_{n} - x_{n - 1}$ đạt đến một giá trị khá nhỏ mà chúng ta chấp nhận được.

2. Viết code Gradient Descent trong Python

Ví dụ chúng ta có một hàm số $y = x^{2} - 6 \sin x$ , đây là một hàm số mà phương trình $y^{'} = 0$ không tìm được nghiệm bằng cách giải phương trình, do vậy chúng ta cần dùng đến Gradient Descent để tìm cực tiểu.

Chú ý: Phần này có liên quan đến xuất đồ thị động dạng ảnh động trong Python, bạn nên tham khảo bài Vẽ đồ thị dạng ảnh động với Animation trong thư viện Matplotlib trước khi đến phần tiếp theo.

Sử dụng gradient descent với learning rate = 0.1

Đầu tiên chúng ta import các thư viện cần thiết.

import numpy as np
import matplotlib.pyplot as plt
from matplotlib.animation import FuncAnimation

Tiếp đến là định nghĩa hàm f(x) và đạo hàm của nó df(x) trong Python, ở đây chúng ta sử dụng hai quy tắc tính đạo hàm:

y = x n \to y' = n x n - 1

y = sin x \to y' = cos x

Đây là những kiến thức phổ thông bạn đã biết từ hồi cấp 3, do vậy chúng ta có:

y = x 2 - 5 sin x \to y' = 2 x - 5 cos x

def f(x):
    return x**2 - 5*np.sin(x)

def df(x):
    return 2*x - 5*np.cos(x)

Để vẽ đồ thị động chúng ta cần thiết lập một số thông số cho đồ thị như kích thước ảnh, giới hạn các trục tọa độ, một số text sẽ hiển thị trên đồ thị.

fig = plt.figure(figsize=[10, 7])
ax = plt.axes(xlim=(-8, 8), ylim=(-10, 60))
ax.text(-6, 55, 'Hàm số $y=x^2-5\sin{x}$, $step\_multiplier=0.1$, $precision=0.00001$, $start=-10$', fontsize=12)
label_1 = ax.text(-6, 50, '', fontsize=12)
label_2 = ax.text(0, 30, '', fontsize=20)

line, = ax.plot([], [], 'ro-', lw=5)
x = np.linspace(start=-8, stop=8, num=100)
y = f(x)
ax.plot(x,y)

Giờ là lúc sử dụng thuật toán Gradient Descent ở phần 1, chúng ta thiết lập các giá trị ban đầu:

x_1 = -10
x_0 = 0
step_multiplier = 0.1
precision = 0.00001

Ở đây có 4 biến x_0 chứa giá trị trước đó, x_1 là giá trị trong bước tiếp theo, step_multiplier là hệ số kết hợp với độ dốc, ở phần cuối bài chúng ta sẽ biết đến nó với tên gọi tốc độ học (learning rate). Biến precision quyết định khi nào dừng thuật toán, nó là độ chính xác trong phép tính xấp xỉ mà chúng ta mong muốn, ở đây độ chính xác đến 1/100k.

Tiếp theo, chúng ta sẽ cài đặt thuật toán Gradient Descent kết hợp với định nghĩa các phần vẽ hoạt họa:

def animate(i):
    global x_0, x_1
    step_size = abs(x_1 - x_0)

    if step_size > precision:
        x_0 = x_1
        gradient = df(x_0)
        x_1 = x_0 - step_multiplier * gradient
        x = [x_0, x_1]
        y = [f(x_0), f(x_1)]
        line.set_data(x, y)
        label_2.set_text(str(i))
    label_1.set_text('Lần: ' + str(i) + '/50, cost:' + str(f(x_1)) + ', slope:' + str(df(x_1)))
    return line,

Thuật toán dừng lại khi độ chính xác đạt như mong muốn hay $x_{n} - x_{n - 1} < p e r c i s i o n$ . Nếu chưa đạt được độ chính xác tính toán bước tiếp theo $x_{1} = x_{0} - η f^{'} (x_{0})$ với

    x_0 = x_1
    gradient = df(x_0)
    x_1 = x_0 - step_multiplier * gradient

Cuối cùng, chúng ta sử dụng hàm FuncAnimation để xuất ra đồ thị dạng hình ảnh động:

anim = FuncAnimation(fig, animate, frames=50, interval=400, blit=True)
anim.save('gradient_descent.gif', writer='imagemagick')

Bạn có thể tải Code Jupyper Notebook. Kết quả chúng ta được hình ảnh động như sau:

Sử dụng gradient descent với learning rate = 0.1

Một số nhận xét về kết quả:

Những đoạn có độ dốc lớn thuật toán sẽ vượt qua nhanh chóng, những đoạn độ dốc nhỏ, sẽ rất lâu để vượt qua, ví dụ ở dải x[-4,-2] tại đây phải mất hơn 10 vòng lặp để vượt qua.
Khi độ dốc lớn thì bước di chuyển cũng lớn do $Δ = x_{n} - x_{n - 1} = - η f^{'} (x_{n - 1})$ .
Nhìn vào công thức trên, ta có thể kết luận số bước lặp để đi đến kết quả sẽ phụ thuộc các yếu tố:
- Giá trị khởi tạo của thuật toán
- Độ chính xác percision
- Hệ số step_multiplier hay là tốc độ học (learning rate)

3. Điều chỉnh các thông số trong Gradient Descent

Trong kết quả phần trước chúng ta đã nhận xét một số các yếu tố có liên quan đến kết quả của Gradient Descent, chúng ta sẽ cùng tìm hiểu từng yếu tố liên quan này. Công thức cần nhớ là:

Δ = x n - x n - 1 = - η f' (x n - 1)

3.1 Giá trị khởi tạo

Giá trị khởi tạo là điểm $x_{0}$ , nếu điểm này càng gần với điểm cực tiểu thì số bước lặp ít đi. Do bước nhảy phụ thuộc vào độ dốc do đó nếu điểm $x_{0}$ nằm ở phía có độ dốc lớn thì số bước lặp cũng ít đi. Thật vậy, chúng ta điều chỉnh các thông số trong phần 2 như sau:

x_1 = 10

Tức là điểm khởi tạo sẽ ở $x_{0} = 10$ và xuất kết quả ra được hình sau:

Điểm khởi tạo Gradient descent cho sự khác biệt

Bạn có thể thấy với điểm khởi tạo ở -10, thuật toán hội tụ (đạt đến điểm cực tiểu mong muốn) sau 33 bước lặp, trong khi với điểm khởi tạo là 10 thì chỉ cần 15 bước lặp thuật toán đã hội tụ. Do vậy, việc lựa chọn điểm khởi tạo cho Gradient Descent cũng rất quan trọng để đạt được kết quả nhanh.

3.2 Độ chính xác mong muốn

Trong ví dụ chính, chúng ta sử dụng độ chính xác là 1/100k, vậy nếu thử tăng độ chính xác thêm 1 chữ số 0 nữa tức là chính xác đến 1/1 triệu xem thuật toán hội tụ sau bao nhiêu bước.

Độ chính xác 1/1 triệu

Chúng ta thấy cần đến 35 bước lặp mới đạt đến độ chính xác 1/1 triệu trong khi chỉ cần 33 bước lặp với độ chính xác 1/100k. Trong thực tế, tùy vào lĩnh vực và bài toán cụ thể mà cần có độ chính xác cao hay thấp. Ví dụ với một bài toán kinh tế, khi đưa ra xác xuất lựa chọn phương án là 70% (1/trăm) và 72.3473% (1/triệu) là như nhau, vậy nên chúng ta chọn độ chính xác percision = 0.01 thì thuật toán sẽ hội tụ nhanh hơn mà vẫn đạt được kết quả mong muốn.

3.3 Tốc độ học – Learning rate

Tốc độ hội tụ của Gradient Descent phụ thuộc vào nhiều vào learning rate $η$ . Để kiểm tra chúng ta thử tăng tốc độ học $η$ từ 0.1 lên 0.2. Kết quả như hình sau:

Tăng tốc độ học

Chỉ sau 18 bước lặp thuật toán đã hội tụ so với 33 bước khi learning rate tăng từ 0.1 lên 0.2. Câu hỏi đặt ra, vậy có thể tăng tốc độ học lên thật cao không. Trong ví dụ tiếp theo chúng ta sẽ đẩy learning rate lên 0.5 xem thế nào.

Thuật toán không thể hội tụ

Thuật toán nhanh chóng kéo đến điểm cực tiểu nhưng không thể hội tụ, nó chạy qua chạy lại hai bên điểm cực tiểu nhưng không thể tiến đến điểm cực tiêu mặc dù chạy qua hơn 50 bước.

Như vậy có thể thấy việc chọn tốc độ học là rất quan trọng trong Gradient Descent, nếu learning rate bé thì tốc độ hội tụ lâu nhưng nếu chọn lớn quá thì thuật toán không thể hội tụ. Do vậy, trong thực tế để chọn được learning rate phù hợp chúng ta cần thực hiện các tốc độ khác nhau và sau vài lần thực hành, chúng ta sẽ có được con số phù hợp.

Bài viết gốc được đăng tải tại allaravel.com

Có thể bạn quan tâm:

Xem thêm Việc làm Developer hấp dẫn trên TopDev