Gradient Descent thần thánh

Như chúng ta đã biết, hiện nay Machine Learning nói riêng, AI nói chung không thể có công thức đúng 100% mà chỉ có thể tối ưu hóa đến khả năng đúng tốt hơn và khẩu hiệu của AI là “tốt hơn” và “tốt hơn”. Nghĩa là trong mạng lưới training với các cặp (x,y) đầu vào là x, đầu ra là y thì nhiệm vụ là đoán đầu ra y so với đầu vào x sao cho “đúng nhiều nhất có thể”. Làm thế nào để biết được là đúng nhiều nhất có thể? “Đúng nhiều nhất có thể” đồng nghĩa với  việc trong quá trình training, điều chỉnh các trọng số để đi tới mục tiêu sai số ít nhất  so với thực tế. Một trong những phương pháp giải quyết vấn đề đó là Gradient Descent. 

1. Gradient Descent là gì?

Là phương pháp điều chỉnh các trọng số (weight) để đi đến mục tiêu sai số, lỗi (error) ít nhất so với thực tế. Như vậy, 02 yếu tố cần quan tâm nhất là trọng số (weight)lỗi (error). Hình vẽ dưới đây mô tả mối quan hệ giữa 02 yếu tố trên và cách hoạt động của Gradient Descent:

Đường parapol màu xanh thể hiện quan hệ giữa lỗi và trọng số. Nhiệm vụ của Gradient Descent là tìm điểm cực tiểu (dấu x màu đen) ở đáy của parapol mà tại đó giá trị sai số là nhỏ nhất. 

Bắt đầu với giá trị ngẫu nhiên w1 (điểm màu đỏ) trên đồ thị, chúng ta cần thay đổi giá trị trọng số w để đi đến điểm cực tiểu x màu đen. Vậy thay đổi trọng số như thế nào, theo chiều nào? Trong 02 từ Gradient Descent thì Gradient nghĩa là tạo độ dốc, còn Descent nghĩa là đi xuống dưới, kết hợp 02 từ nghĩa là dốc xuống dưới, tức là thay đổi trọng số theo chiều dốc xuống dưới. 

Phương pháp Gradient Descent là phương pháp sử dụng đạo hàm để thay đổi trọng số w theo hướng đến điểm error tối thiểu trong đường cong parapol. Đây là quá trình lặp, biểu diễn dưới dạng công thức như sau:

wnew=woldαerror

wnew: trọng số tại thời điểm mới (hiện tại)

wold: trọng số cũ tại thời điểm quá khứ

error: đạo hàm của sai số tại thời điểm wold

α: bước nhảy, xác định tốc độ hội tu đến điểm cực tiểu của error trong đường cong parapol. Việc điều chỉnh giá trị của bước nhảy α rất quan trọng, nếu α quá lớn sẽ dẫn tới không hội tụ vào điểm cực tiểu được (giống như đi tàu vũ trụ để bay từ Hà Nội vào Nghệ An thì phanh không kịp, đến lúc phanh được thì đã ở Hồ Chí Minh rồi), nếu α quá nhỏ thì thời gian đi tới điểm hội tụ lại quá lâu.

Đoạn code mô phỏng quá trình tìm nghiệm w đơn giản bằng Grandient Descent:

Tìm điểm cực tiểu của phương trình: f(x)=x43.x3+2

Đạo hàm của f(x): f(x)=4.x39.x2

Bằng phương pháp tính toán sẽ cho ra nghiệm x = 2.25

x_old = 0 # The value does not matter as long as abs(x_new - x_old) > precision
x_new = 6 # The algorithm starts at x=6
gamma = 0.01 # step size
precision = 0.00001

def df(x):
y = 4 * x**3 - 9 * x**2
return y

while abs(x_new - x_old) > precision:
x_old = x_new
x_new += -gamma * df(x_old)

print("The local minimum occurs at %f" % x_new)

2.  Hàm chi phí

Gradient Descent là quá trình lặp để cực tiểu hóa các sai số error đầu ra bằng việc điều chỉnh các trọng số w. Tuy nhiên còn 01 điểm cần chú ý trước khi đi tìm trọng số w là xác định mô hình dữ liệu cho bài toán, ví dụ có thể là mô hình hồi quy tuyến tính đa thức bậc 1, bậc 2 hoặc có thể là đa thức bậc n. Việc xác định mô hình sẽ ảnh hưởng lớn đến kết quả chính xác của mạng lưới NN của Machine Learning, một trong những vấn đề đó là overfitting và underfitting. Overfitting là xảy ra khi mô hình dự đoán đưa ra đẹp quá, khớp quá với một số dữ liệu ban đầu ít ỏi đến nỗi đánh lừa kết quả, phức tạp quá đến nỗi ảnh hưởng tới quá trình tìm nghiệm. Một trong những cách để khắc phục overfitting là sử dụng hàm chi phí cost function.

J(w,b,x,y)=1/2.yzh(nl)(xz)2=1/2.yzypred(xz)2

 

Biểu diễn của bất kỳ Machine Learning dưới dạng công thức toán học như sau: f(x) = f(b0, b1, b2,…, bn). Gradient Descent là phương pháp được sử dụng để tìm ra các hệ số b0, b1, b2,…, bsao cho giảm thiểu sai lệch (hàm mất mát) so với kết quả thực tế. 

2. Gradient Descent hoạt động như thế nào?

Mô tả ngắn gọn về Gradient Descent như sau: phương pháp tìm các hệ số nghiệm b0, b1, b2,…, bn bằng cách thử nghiệm liên tục theo vòng lặp với các giá trị b0, b1, b2,…, bcho trước rồi tính toán hàm mất mát của các hệ số này để hệ số của lần thử nghiệm sau tốt hơn một chút so với lần thử nghiệm trước, cho đến khi tìm thấy hàm mất mát đạt giá trị nhỏ nhất.

  • Bước 1: gán giá trị default cho các hệ số
  • Bước 2: Tính giá trị hàm mất mát (cost function)
  • Bước 3: lựa chọn giá trị mới cho các hệ số
  • Lặp lại quá trình 03 bước trên với thời gian đủ dài đến khi cảm thấy hàm mất mát đạt giá trị nhỏ nhất.

Tưởng tượng hình ảnh của 1 cái bát ăn cơm cũng chính là hình vẽ của hàm mất mát (cost function), trong đó một điểm bất kỳ trên bề mặt cái bát cũng có thể là giá trị hiện tại của hàm mất mát của các hệ số nghiệm hiện tại, còn đáy của cái bát là nơi mà các hệ số nghiệm cho ra hàm mất mát tốt nhất, nơi mà các nghiệm hội tụ. 

Hình vẽ dưới đây mô phỏng quá trình đi tìm nghiệm của Gradient Descent, đồ thị của hàm mất mát là các vòng tròn đồng tâm, quá trình lặp của Gradient Descent để hội tụ điểm màu đỏ vào điểm giữa, đáy của các vòng tròn đồng tâm đó. 

 

3. Biễu diễn công thức Gradient Descent

  • Bước 1: gán các hệ số với giá trị default: coefficient = 0.0
  • Bước 2: Tính hàm cost = evaluate(f(coefficient)). Tính đạo hàm của cost để xác định hướng di chuyển của các hệ số trong lần lặp tiếp theo: delta = derivative(cost)
  • Bước 3: cập nhật giá trị các hệ số: coefficient = coefficient−(alpha×delta). Trong đó alpha là tốc độ học, việc lựa chọn tốc độ học khá quan trọng, nếu alpha lớn thì bước nhảy của hàm cost lớn dẫn tới không hội tụ đến được điểm chi phí mất mát nhỏ nhất. xt+1=xtη.f(xt)

Ví dụ: giả sử mô hình ML dưới dạng hàm số f(x)=x2+5.sin(x). Khi đó, đạo hàm của hàm số trên là f(x)=2.x+5.cos(x). Giá trị của hệ số tại thời điểm t được biểu diễn như sau:

bt+1 = btη.f(bt) = bt – 2.bt + 5.cos(bt)

4. Gradient Descent quy mô lớn

Chương trình dùng Gradient Descent có thể chạy rất chậm mới cho ra kết quả nếu áp dụng trên lượng dữ liệu lớn bởi mỗi vòng lặp phải tính toán nhiều bước cho mỗi hệ số, sẽ là rất lâu nếu chạy vòng lặp trên hàng triệu dữ liệu training set, thêm vào đó là nhiều hệ số sẽ càng chậm. Do vậy, một trong những cách tối ưu hóa cho Gradient Descent là cập nhật giá trị của các hệ số ngay lập tức trong mỗi vòng lặp thay vì đợi kết thúc mỗi vòng lặp mới cập nhật.

Ví dụ cụ thể: cho tập dữ liệu training set như sau:

xy
11
23
43
32
55