Phương pháp Gradient Descent

Mở đầu

  • Trong Machine Learning, chúng ta thường xuyên phải tìm giá trị nhỏ nhất( hay lớn nhất) của một hàm số. Ví dụ như các hàm mất mát trong thuật toán Linear Regression hay K-means Clustering. Nhưng 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. Vậy nên người ta thường cố gắng tìm các điểm local minimum, các điểm local minimum là nghiệm của phương trình đạo hàm bằng 0, và 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, rồi 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. 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.

Gradient Descent cho hàm 1 biến

  • Giả sử xt là điểm ta tìm được sau vòng lặp thứ t.Ta cần tìm một thuật toán để đưa xt về càng gần x* càng tốt.
    Dựa vào hình tên ta thấy:
    – Nếu F’(xt) > 0 thì xt nằm về phía bên phải so với x*(hoặc ngược lại), vì vậy ta cần di chuyển xt về phía bên trái. tức ta cần di chuyển ngược dấu đạo hàm:
    Với Δ là một đại lượng ngược dấu với đạo hàm F’(xt)
xt+1 = xt + Δ
  • Với Δ là một đại lượng ngược dấu với đạo hàm F’(xt) tức là lượng di chuyển Δ, một cách trực quan nhất, là tỉ lệ thuận với -F’(xt)

Từ hai nhận xét trên, ta suy ra:

image

Trong đó η là một số dương gọi là learning rate (tốc độ đọ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.

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

Giả sử ta cần tìm global minimum cho hàm f(θ) trong đó θ là một vector. Đạo hàm của hàm số đó tại một điểm θ bất kỳ được ký hiệu là θ f(θ). 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, sau đó, ở vòng lặp thứ t, quy tắc cập nhật là:

image


với θ f(θ) là đạo hàm của hàm mất mát tại θ.
Với đầu vào là điểm khởi tại θ0 và learning rate η, ta thấy rằng:
  • Điểm khởi tạo ( hay điểm dự đoán ban đầu ) càng gần nghiệm x* thì quá trình hội tụ càng nhành
  • Learning rate càng nhỏ thì tốc độ hội tụ càng chậm, nếu việc tính toán phức tạp, learning rate sẽ ảnh hưởng đến tốc độ của thuật toán rất nhiều, thậm chí không bao giờ tới đích. Mặt khác learning rate càng lớn thì thuật toán tiến nhanh tới gần đích, nhưng thuật toán không hội tụ được vì bước nhảy của nó quá lớn mà chỉ loanh quanh ở đích.

Vì vậy việc lựa chọn learning rate rất quan trọng trong các bài toán thực tế.
Cuối cùng, húng ta sẽ cập nhật θ.cho đến khi kết quả chấp nhận được.
img2_1

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

Momentum

  • Đặt vấn đề:

    Cho một viên bi ở vị trí A và B, và chúng ta mong muốn viên bi sẽ ở vị trí C (global minimum) chứ không phải ở vị trí D (local minimum). Suy nghĩ theo khía cạnh vật lý, nếu vận tốc ban đầu của viên bi đủ lớn để khi viên bi di chuyển đến điểm D có thể vượt dốc tới điểm E rồi lăn xuống C như hình c), chúng ta sẽ thu được kết quả mong muốn. Dựa trên hiện tượng này thì thuật toán Momentum ra đời nhằm khắc phục việc nghiệm của GD (Gradient Descent) rơi vào một điểm local minimum.

Biểu diễn Momentum bằng toán học

Trong GD, chúng ta cần tính lượng thay đổi ở thời điểm t để cập nhật vị trí mới cho nghiệm. vị trí mới của hòn bi sẽ là θt+1t - vt, với vt vừa mang thông tin độ dốc (tức đạo hàm), vừa mang thông tin vận tốc trước đó vt-1 (chúng ta coi như vận tốc ban đầu v0= 0). Ta cộng hai đại lượng này lại (với trọng số tương ứng):

image


Trong đó γ thường được chọn là một giá trị khoảng 0.9, vt là vận tốc tại thời điểm trước đó
θ 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:

θt+1 = θt − vt

Nesterov accelerated gradient (NAG)

Momentum giúp viên vi vượt qua dốc local minimum, nhưng tốn khá nhiều thời gian trước khi dừng lại vì có đà (hay vận tốc ban đầu). Và phương pháp Nesterov accelerated gradient (NAG) giúp thuật toán hội tụ nhanh hơn.
Phương pháp này dự đoán hướng đi trong tương lai, Cụ thể, nếu sử dụng số hạng momentum γ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. Từ đó ta có công thức cập nhật của NAG như sau:

image
LR_NAG_contours

3 Likes

Vấn đề khá thú vị mặc dù khá là rộng :> được cái nhìn cái gif hay thật sự, đăng gif giống đăng ảnh thường thôi hả em? :blush:

1 Like

ảnh thì copy trực tiếp trên mạng rồi paste được nhưng gif phải tải về dưới dạng gif mới được chị ạ

Bài viết thú vị @anon73939363 @@@
Nếu em có thể giải thích tượng hình được phần Momemtum và Nesterov thì anh mới tin là em hiểu hoàn toàn :innocent: :innocent: :innocent:

1 Like

Có chỗ gõ sai kìa em

1 Like