[Nhập môn Machine Learning] Bài 6: Overshooting và thuật toán Gradient Descent cho hàm nhiều biến

Overshooting

Ở bài trước, tôi có đề cập đến tham số $\alpha$. Đây là tham số giúp ta điều chỉnh độ lớn của đạo hàm hay còn gọi là tham số learning rate trong Gradient Descent. Trong thực tế, không phải lúc nào nâng cấp các trọng số $\theta$ theo độ lớn của đạo hàm cũng đưa chúng ta đến cực tiểu của hàm số. Nếu Cost Function của chúng ta quá hẹp, dẫn đến đạo hàm quá lớn sẽ khiến Gradient Descent đưa chúng ta rời xa cực tiểu. Hiện tượng này gọi là overshooting.

Bạn có thể tự kiểm chứng bằng cách tăng $\alpha$ lên một giá trị lớn (khoảng 2 hoặc 3) và bạn sẽ thấy cả Cost Function dần tiến ra vô cực. Đó cũng là cách nhận biết khi nào bạn đang gặp overshooting. Vậy nên sẽ là tốt nếu chỉ lấy một phần độ lớn này thôi và chúng ta sẽ điều khiển việc này bằng tham số $\alpha$. Từ bây giờ, Gradient Descent của chúng ta sẽ có dạng: $$\theta = \theta - \alpha \frac{d}{d\theta} J(\theta)$$
Tuy nhiên, không phải vì thế mà lúc nào chúng ta cũng phải để learning rate cực nhỏ. Có sự đánh đổi ở đây:

1. Nếu $\alpha$ lớn, Gradient Descent có khả năng gặp overshooting.
2. Nếu $\alpha$ nhỏ, Gradient Descent sẽ đến điểm cực tiểu của Cost Function rất lâu.

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

Chúng ta đều biết dữ liệu chúng ta thu thập sẽ luôn có nhiều feature chứ không chỉ một. Khi đó, $h_\theta (x)$ sẽ có dạng: $$h_\theta (x_1,x_2,\cdots ,x_n) = \theta_0 + \theta_1 x_1 + \theta_2 x_2 + \cdots +\theta_n x_n$$ Với $\theta_j$, $x_j$ là trọng số và dữ liệu của feature thứ j (j chạy từ 0 đến n). Ta mặc định xem $x_0 = 1$ vì $\theta_0$ là một trọng số không phụ thuộc vào x, gọi là interceptor. (Nếu bạn không hiểu tại sao, hãy tham khảo Bài 3)
Cost Function của chúng ta vẫn không thay đổi là: $$J(\theta_0, \theta_1,\cdots ,\theta_n) = \frac{1}{2m}\sum_{i=1}^{m} (h_\theta (x_0^{(i)},\cdots , x_n^{(i)}) - y^{(i)} )^2$$
Tuy nhiên khi nâng cấp các trọng số, ta cần lấy đạo hàm riêng của từng $\theta$ và nâng cấp các trọng số đồng thời với nhau. Tức là ta không thể nâng cấp $\theta_1$ rồi sử dụng giá trị $\theta_1$ mới đó để tính đạo hàm riêng của $\theta_2$. Nói theo một cách toán học thì ở mỗi bước nâng cấp, ta cần lấy giá trị gradient tại vị trí $(\theta_0,\theta_1,\cdots ,\theta_n)$ rồi trừ cho các trọng số tương ứng, $$\theta_j = \theta_j - \alpha \frac{\partial}{\partial \theta_j}J(\theta_0,\cdots ,\theta_n)$$
Tuy nhiên chúng ta có thể tính toán chi tiết hơn công thức của $\frac{\partial}{\partial \theta_j}J(\theta_0,\cdots ,\theta_n)$ bằng cách thực hiện lấy đạo hàm riêng luôn. Bạn có thể thử tự lấy đạo hàm riêng rồi so sánh với kết quả bên dưới.
Ta có công thức tổng quát là: $$\frac{\partial J}{\partial \theta_j} = \frac{1}{m}\sum_{i=1}^{m} (h( x_0^{(i)},\cdots , x_n^{(i)} ) - y^{(i)} )x_j^{(i)}\ \ \ ,\ 0\leq j \leq n$$
Tuy nhiên, tôi tin rằng viết như dưới sẽ giúp ta hình dung rõ hơn: $$\frac{\partial J}{\partial \theta_j} = \frac{1}{m}\sum_{i=1}^{m} (h( x_1^{(i)}, \cdots , x_n^{(i)} ) - y^{(i)} )\ \ \ với\ j=0$$ $$\frac{\partial J}{\partial \theta_j} = \frac{1}{m}\sum_{i=1}^{m} (h( x_1^{(i)}, \cdots , x_n^{(i)} ) - y^{(i)} )x_j^{(i)}\ \ \ với\ 1 \leq j \leq n$$
Cuối cùng, ta được một thuật toán Gradient Descent tổng quát:

1. Khởi đầu bằng cách gán cho các $\theta_0,\theta_1,\cdots,\theta_n$ giá trị ngẫu nhiên.
2. Cập nhập đồng thời các $\theta$ mới bằng cách trừ cho đạo hàm riêng của mỗi trọng số tại vị trí hiện tại. $$\theta_j = \theta_j - \alpha \frac{1}{m}\sum_{i=1}^{m} (h( x_1^{(i)},\cdots , x_n^{(i)} ) - y^{(i)} )\ \ \ với\ j=0$$ $$\theta_j = \theta_j - \alpha \frac{1}{m}\sum_{i=1}^{m} (h( x_1^{(i)},\cdots , x_n^{(i)} ) - y^{(i)} )x_j^{(i)}\ \ \ với\ 1 \leq j \leq n$$
3. Lặp lại bước 2 cho đến khi tất cả đạo hàm riêng tính được bằng 0 hoặc một giá trị cực nhỏ.

Ví dụ

Hãy lấy lại ví dụ trước của chúng ta thêm lần nữa.

Lần này ta sẽ thêm một feature mới, $\theta_0$ vào $h_\theta (x)$ và thực hiện Gradient Descent.
Hypothesis Function mới: $$h_\theta (x) = \theta_0 +\theta_1 x$$
Và ta sẽ thực hiện nâng cấp các trọng số bằng công thức dưới: $$\theta_0 = \theta_0 - \alpha \frac{1}{m}\sum_{i=1}^{m} (h( x^{(i)} ) - y^{(i)} )$$ $$\theta_1 = \theta_1 - \alpha \frac{1}{m}\sum_{i=1}^{m} (h( x^{(i)} ) - y^{(i)} )x_1^{(i)}$$
Tôi đã viết lại chương trình lần trước một chút để minh họa ví dụ này

import matplotlib.pyplot as plt
from random import random

def hypothesis(x, theta_0, theta_1):
    return x*theta_1 + theta_0

def compute_cost(theta_0, theta_1, xs, ys):
    cost = 0
    for i in range(len(xs)):
        error = hypothesis(xs[i], theta_0, theta_1) - ys[i]
        cost = cost + error*error
    return cost/(2*len(xs))

def cal_gradient_1(theta_0, theta_1, xs, ys):
    grad = 0
    for i in range(len(xs)):
        grad = grad + (hypothesis(xs[i], theta_0, theta_1) - ys[i])*xs[i]
    return grad/len(xs)

def cal_gradient_0(theta_0, theta_1, xs, ys):
    grad = 0
    for i in range(len(xs)):
        grad = grad + (hypothesis(xs[i], theta_0, theta_1) - ys[i])
    return grad/len(xs)

if __name__ == "__main__":
    xs = [3, 5, 3.25, 1.5]
    ys = [1.5, 2.25, 1.625, 1.0]

    alpha = 0.1

    theta_0 = 2*random() - 1
    theta_1 = 2*random() - 1
    gradient_0 = cal_gradient_0(theta_0, theta_1, xs, ys)
    gradient_1 = cal_gradient_1(theta_0, theta_1, xs, ys)

    cycle = 1
    while abs(gradient_0) > 0.0005 or abs(gradient_1) > 0.0005 :
        print("====CYCLE {}====".format(cycle))
        print("Theta 0: {}, Theta 1: {}".format(theta_0,theta_1))
        print("Gradient 0: {}, Gradient 1: {}".format(gradient_0,gradient_1))
        print("Cost: {}".format(compute_cost(theta_0, theta_1, xs, ys)))
        cycle = cycle + 1
        theta_0 = theta_0 - alpha*gradient_0
        theta_1 = theta_1 - alpha*gradient_1
        gradient_0 = cal_gradient_0(theta_0, theta_1, xs, ys)
        gradient_1 = cal_gradient_1(theta_0, theta_1, xs, ys)

    print("----------------------")
    print("FOUND THETA 0: {}, THETA 1: {} IS OPTIMUM".format(theta_0,theta_1))
    print("COST: {}".format(compute_cost(theta_0,theta_1, xs, ys)))

Và kết quả thu được

Trọng số tối ưu

Đường thẳng chúng ta tìm được bằng Gradient Descent

Link chương trình trên Google Colab.

Tổng kết

• Cập nhật các trọng số theo độ lớn đạo hàm riêng có thể gặp overshooting. Cách tốt nhất là kiểm soát lượng cập nhật bằng tham số $\alpha$ gọi là learning rate
• Trong trường hợp sử dụng Gradient Descent với nhiều trọng số, ta cập nhật các trọng số đồng thời nhau bằng công thức: $$\theta_j = \theta_j - \alpha \frac{1}{m}\sum_{i=1}^{m} (h( x_1^{(i)},\cdots , x_n^{(i)} ) - y^{(i)} )\ \ \ với\ j=0$$ $$\theta_j = \theta_j - \alpha \frac{1}{m}\sum_{i=1}^{m} (h( x_1^{(i)},\cdots , x_n^{(i)} ) - y^{(i)} )x_j^{(i)}\ \ \ với\ 1 \leq j \leq n$$