Bài 7: Gradient Descent (phần 1/2) | Hỏi gì?

Trong trang này:

• 1. Giới thiệu
  • Gradient Descent
• 2. Gradient Descent cho hàm 1 biến
  • Ví dụ đơn giản với Python
    • Điểm khởi tạo khác nhau
    • Learning rate khác nhau
• 3. Gradient Descent cho hàm nhiều biến
  • Quay lại với bài toán Linear Regression
  • Sau đây là ví dụ trên Python và một vài lưu ý khi lập trình
    • Kiểm tra đạo hàm
      • Giải thích bằng hình học
      • Giải thích bằng giải tích
      • Với hàm nhiều biến
    • Đường đồng mức (level sets)
• 4. Một ví dụ khác
• 5. Thảo luận
• 6. Tài liệu tham khảo

1. Giới thiệu

Các bạn hẳn thấy hình vẽ dưới đây quen thuộc:

Điểm màu xanh lục là điểm local minimum (cực tiểu), và cũng là điểm làm cho hàm số đạt giá trị nhỏ nhất. Từ đây trở đi, tôi sẽ dùng local minimum để thay cho điểm cực tiểu, global minimum để thay cho điểm mà tại đó hàm số đạt giá trị nhỏ nhất. Global minimum là một trường hợp đặc biệt của local minimum.

Giả sử chúng ta đang quan tâm đến một hàm số một biến có đạo hàm mọi nơi. Xin cho tôi được nhắc lại vài điều đã quá quen thuộc:

1. Điểm local minimum (x^*) của hàm số là điểm có đạo hàm (f’(x^*)) bằng 0. Hơn thế nữa, trong lân cận của nó, đạo hàm của các điểm phía bên trái (x^*) là không dương, đạo hàm của các điểm phía bên phải (x^*) là không âm.

2. Đường tiếp tuyến với đồ thị hàm số đó tại 1 điểm bất kỳ có hệ số góc chính bằng đạo hàm của hàm số tại điểm đó.

Trong hình phía trên, các điểm bên trái của điểm local minimum màu xanh lục có đạo hàm âm, các điểm bên phải có đạo hàm dương. Và đối với hàm số này, càng xa về phía trái của điểm local minimum thì đạo hàm càng âm, càng xa về phía phải thì đạo hàm càng dương.

Gradient Descent

Trong Machine Learning nói riêng và Toán Tối Ưu nói chung, chúng ta thường xuyên phải tìm giá trị nhỏ nhất (hoặc đôi khi là lớn nhất) của một hàm số nào đó. Ví dụ như các hàm mất mát trong hai bài Linear Regression và K-means Clustering. Nhìn chung, 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. Thay vào đó, người ta thường cố gắng tìm các điểm local minimum, và ở một mức độ nào đó, coi đó là nghiệm cần tìm của bài toán.

Các điểm local minimum là nghiệm của phương trình đạo hàm bằng 0. Nếu 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, ta chỉ cần 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 (đoạn này nghe rất quen thuộc, đúng không?). 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.

Vì kiến thức về GD khá rộng nên tôi xin phép được chia thành hai phần. Phần 1 này giới thiệu ý tưởng phía sau thuật toán GD và một vài ví dụ đơn giản giúp các bạn làm quen với thuật toán này và vài khái niệm mới. Phần 2 sẽ nói về các phương pháp cải tiến GD và các biến thể của GD trong các bài toán mà số chiều và số điểm dữ liệu lớn. Những bài toán như vậy được gọi là large-scale.

2. Gradient Descent cho hàm 1 biến

Quay trở lại hình vẽ ban đầu và một vài quan sát tôi đã nêu. Giả sử (x_{t}) 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 (x_{t}) về càng gần (x^*) càng tốt.

Trong hình đầu tiên, chúng ta lại có thêm hai quan sát nữa:

1. Nếu đạo hàm của hàm số tại (x_{t}): (f’(x_{t}) > 0) thì (x_{t}) nằm về bên phải so với (x^*) (và ngược lại). Để điểm tiếp theo (x_{t+1}) gần với (x^*) hơn, chúng ta cần di chuyển (x_{t}) về phía bên trái, tức về phía âm. Nói các khác, chúng ta cần di chuyển ngược dấu với đạo hàm: [ x_{t+1} = x_{t} + Delta ] Trong đó (Delta) là một đại lượng ngược dấu với đạo hàm (f’(x_{t})).

2. (x_{t}) càng xa (x^*) về phía bên phải thì (f’(x_{t})) càng lớn hơn 0 (và ngược lại). Vậy, lượng di chuyển (Delta), một cách trực quan nhất, là tỉ lệ thuận với (-f’(x_{t})).

Hai nhận xét phía trên cho chúng ta một cách cập nhật đơn giản là: [ x_{t+1} = x_{t} – eta f’(x_{t}) ]

Trong đó (eta) (đọc là eta) là một số dương được gọi là learning rate (tốc độ học). Dấu trừ thể hiện việc chúng ta phải đi ngược với đạo hàm (Đây cũng chính là lý do phương pháp này được gọi là Gradient Descent – descent nghĩa là đi ngượ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.

Ví dụ đơn giản với Python

Xét hàm số (f(x) = x^2 + 5sin(x)) với đạo hàm (f’(x) = 2x + 5cos(x)) (một lý do tôi chọn hàm này vì nó không dễ tìm nghiệm của đạo hàm bằng 0 như hàm phía trên). Giả sử bắt đầu từ một điểm (x_{0}) nào đó, tại vòng lặp thứ (t), chúng ta sẽ cập nhật như sau: [ x_{t+1} = x_{t} – eta(2x_{t} + 5cos(x_{t})) ]

Như thường lệ, tôi khai báo vài thư viện quen thuộc

Tiếp theo, tôi viết các hàm số :

1. grad để tính đạo hàm
2. cost để tính giá trị của hàm số. Hàm này không sử dụng trong thuật toán nhưng thường được dùng để kiểm tra việc tính đạo hàm của đúng không hoặc để xem giá trị của hàm số có giảm theo mỗi vòng lặp hay không.
3. myGD1 là phần chính thực hiện thuật toán Gradient Desent nêu phía trên. Đầu vào của hàm số này là learning rate và điểm bắt đầu. Thuật toán dừng lại khi đạo hàm có độ lớn đủ nhỏ.

Điểm khởi tạo khác nhau

Sau khi có các hàm cần thiết, tôi thử tìm nghiệm với các điểm khởi tạo khác nhau là (x_{0} = -5) và (x_{0} = 5).

Vậy là với các điểm ban đầu khác nhau, thuật toán của chúng ta tìm được nghiệm gần giống nhau, mặc dù với tốc độ hội tụ khác nhau. Dưới đây là hình ảnh minh họa thuật toán GD cho bài toán này (xem tốt trên Desktop ở chế độ full màn hình).

Từ hình minh họa trên ta thấy rằng ở hình bên trái, tương ứng với (x_{0} = -5), nghiệm hội tụ nhanh hơn, vì điểm ban đầu (x_0) gần với nghiệm ( x^* approx -1) hơn. Hơn nữa, với (x_{0} = 5 ) ở hình bên phải, đường đi của nghiệm có chứa một khu vực có đạo hàm khá nhỏ gần điểm có hoành độ bằng 2. Điều này khiến cho thuật toán la cà ở đây khá lâu. Khi vượt qua được điểm này thì mọi việc diễn ra rất tốt đẹp.

Learning rate khác nhau

Tốc độ hội tụ của GD không những phụ thuộc vào điểm khởi tạo ban đầu mà còn phụ thuộc vào learning rate. Dưới đây là một ví dụ với cùng điểm khởi tạo (x_{0} = -5) nhưng learning rate khác nhau: