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 trở về 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ảng giải bằng hình học
      • Giảng giải 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ẽ trong tương lai thân thuộc:

Điểm màu xanh lục là vấn đề local minimum (cực tiểu), và cũng là vấn đề 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 quan trọng của local minimum.

Giả sử tất cả 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á thân thuộc:

1. Điểm local minimum (x^*) của hàm số là vấn đề có đạo hàm (f’(x^*)) bằng 0. Hơn thế nữa, trong phụ cận của nó, đạo hàm của những điểm phía bên trái (x^*) là không dương, đạo hàm của những đ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, những điểm bên trái của điểm local minimum màu xanh lục có đạo hàm âm, những điểm bên phải có đạo hàm dương. Và so 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, tất cả chúng ta thường xuyên phải tìm giá trị nhỏ nhất (hoặc thỉnh thoảng là lớn số 1) 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 đa số hàm mất mát trong Machine Learning là rất phức tạp, thậm chí là là bất khả thi. Thay vào đó, người ta thường nỗ lực cố gắng tìm những đ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.

Những đ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) những điểm cực tiểu, ta chỉ việc thay từng điểm local minimum đó vào hàm số rồi tìm điểm làm cho hàm có mức giá trị nhỏ nhất (đoạn này nghe rất thân thuộc, đúng không nào?). Tuy nhiên, trong hồ 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ể tới từ sự phức tạp của dạng của đạo hàm, từ việc những điểm tài liệu có số chiều lớn, hoặc từ việc có quá nhiều điểm tài liệu.

Hướng tiếp cận phổ quát nhất là xuất phát từ một điểm mà tất cả chúng ta xem 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 tới đ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 sử dụng nhiều nhất.

Vì tri 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 tài 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ẽ thuở đầu và một vài quan sát tôi đã nêu. Giả sử (x_{t}) là vấn đề ta tìm được sau vòng lặp thứ (t). Ta cần tìm một thuật toán để mang (x_{t}) về càng gần (x^*) càng tốt.

Trong hình trước nhất, tất cả chúng ta lại sở hữu 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à trái lại). Để điểm tiếp theo (x_{t+1}) gần với (x^*) hơn, tất cả chúng ta cần vận chuyển (x_{t}) về phía bên trái, tức về phía âm. Nói các khác, tất cả chúng ta cần vận chuyển ngược dấu với đạo hàm: [ x_{t+1} = x_{t} + Delta ] Trong số đó (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 to nhiều hơn 0 (và trái lại). Vậy, lượng vận 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 tất cả chúng ta một cách update đơn giản là: [ x_{t+1} = x_{t} – eta f’(x_{t}) ]

Trong số đó (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 tất cả chúng ta phải đi ngược với đạo hàm (Đó cũng đấy là lý do phương pháp này được gọi là Gradient Descent – descent tức 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ả những 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ó rất khó tìm nghiệm của đạo hàm bằng 0 như hàm phía trên). Giả sử bắt nguồn từ một điểm (x_{0}) nào đó, tại vòng lặp thứ (t), tất cả chúng ta sẽ update 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 thân 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 sẽ không sử dụng trong thuật toán nhưng thường được dùng để làm kiểm tra việc tính đạo hàm của đúng không nào hoặc để xem giá trị của hàm số có giảm theo mỗi vòng lặp hay là 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. Nguồn vào của hàm số này là learning rate và điểm mở màn. Thuật toán tạm ngưng khi đạo hàm có độ lớn đủ nhỏ.

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

Sau khoản thời gian có những hàm cấp thiết, tôi thử tìm nghiệm với những điểm khởi tạo khác nhau là (x_{0} = -5) và (x_{0} = 5).

Vậy là với những điểm thuở đầu khác nhau, thuật toán của tất cả chúng ta tìm được nghiệm gần giống nhau, mặc dù với tốc độ quy tụ khác nhau. Ở đâ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 ở quyết sách full màn hình hiển thị).

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 quy tụ nhanh hơn, vì điểm thuở đầ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, lối đ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 độ quy tụ của GD không những phụ thuộc vào điểm khởi tạo thuở đầu mà còn phụ thuộc vào learning rate. Ở đâ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: