Hướng dẫn gradient descent python

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é.

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]y=f[x] chúng ta sẽ giải phương trình đạo hàm của hàm số f[x]f[x] bằng 0.

f′[x]=0f′[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=21+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 x0x0 chính là đạo hàm của hàm số tại điểm x0x0. Bước đi xuống từ điểm x0x0 sang điểm x1x1 sẽ bằng Δ0Δ0. Ta có:

x1=x0+Δ0x1=x0+Δ0

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

Δ0=−ηf′[x0]Δ0=−ηf′[x0]

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

x1=x0−ηf′[x0]x1=x0−ηf′[x0]

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

xn=xn−1+Δn−1=xn−1−ηf′[xn−1]xn=xn−1+Δn−1=xn−1−ηf′[xn−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 đó xn≈xn−1xn≈xn−1 hay xn−xn−1xn−xn−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=x2−6sinxy=x2−6sin⁡x, đây là một hàm số mà phương trình y′=0y′=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.

Đầ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=xn→y′=nxn−1y=xn→y′=nxn−1

y=sinx→y′=cosxy=sin⁡x→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=x2−5sinx→y′=2x−5cosxy=x2−5sin⁡x→y′=2x−5cos⁡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 xn−xn−1