CHƯƠNG 1. CƠ SỞ LÝ THUYẾT CỦA PHƯƠNG PHÁP GRADIENT DESCENT 1. Giới thiệu phương pháp Gradient Descent Gradient Descent [20] là thuật toán học tập được sử dụng nhiều nhất trong ML nói riêng và toán tối ưu nói chung, bởi vì bài toán ML đòi hỏi phải thường xuyên tìm giá trị nhỏ nhất (hoặc đôi khi lớn nhất) của một hàm số nào đó. Để hiểu rõ phương pháp GD, chúng ta cùng xét ví dụ đơn giản, đó là cực tiểu hóa hàm y = x2.
Đây là đồ thị hàm số này Hình 1. Đồ thị hàm số y = x2 (Nguồn: https://ml.com/general/2017/05/28/optimization-algorithms.html) Nhìn vào đồ thị này, ta thấy được giá trị nhỏ nhất của hàm số này là 0, đạt được tại x = 0. Bằng kiến thức về giải tích toán học đã học thì ta biết rằng đạo hàm cấp 1 của một hàm số tại điểm cực trị bằng 0, nên thực tế bài toán tối ưu đưa về việc giải phương trình y′ = 0, trong đó y′ là kí hiệu đạo hàm của hàm y. Việc giải phương trình y′ = 0 không phải lúc nào cũng thực hiện được như ví dụ ở trên do sự phức tạp của phương trình hoặc do sự khó khăn trong việc tính toán đạo hàm.
Do đó, một phương pháp tính toán để tìm được xấp xỉ giá trị của x mà tại đó y đạt giá trị nhỏ nhất là rất cần thiết. Một trong những phương pháp tối ưu hóa số thông dụng làm được điều đó là phương pháp Gradient Descent. SVTH: Hoàng Thị Ly Na 10 Khoá luận tốt nghiệp GVHD: TS. Ngô Thời Nhân Cụ thể hơn, nhiều bài toán trong Machine Learning, đặc biệt là Supervised Learning thường đưa về việc tối ưu một hàm số J(θ) gọi là cost function (hàm chi phí) hoặc loss function (hàm mất mát), tức là ta cần tìm giá trị của tham số θ sao cho hàm J đạt được giá trị nhỏ nhất, trong đó tham số θ là một biến số trong không gian 1 chiều (1 biến) hoặc n chiều (với trường hợp tối ưu hàm nhiều biến).
Để làm được điều này, người ta thường cố gắng tìm các điểm cực tiểu địa phương (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 cấp 1 hay gradient 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. Tuy nhiên, trong nhiều trường hợp, việc giải chính xác phương trình đạo hàm cấp 1 hay gradient 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 của phương pháp GD 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. GD và các biến thể của nó đều áp dụng nguyên lý này để tìm điểm cực tiểu của cost function. Phương pháp Gradient Descent (Nguồn: https://sebastianraschka.com) SVTH: Hoàng Thị Ly Na 11 Khoá luận tốt nghiệp GVHD: TS.
Ngô Thời Nhân Mục đích của Gradient Descent là tìm điểm cực tiểu của hàm cost function bằng cách lặp đi lặp lại để tiếp cận gần hơn điểm cực tiểu, hay nói cách khác nếu ta cứ đi ngược hướng đạo hàm mãi thì ta sẽ tới được điểm cực tiểu của hàm số. Có thể liên hệ một ví dụ thực tế như sau để hiểu về cách thực thi của GD: tưởng tượng rằng ta bị bịt mắt và đang đi qua một thung lũng. Ta muốn đến điểm thấp nhất của thung lũng nhanh với số bước ít nhất. Vậy ta sẽ bước đi như thế nào? Phương án khả thi nhất là bước đầu tiên, ta sẽ đi xuôi theo trên bề mặt nghiêng của thung lũng và di chuyển theo hướng xuống dốc nhất.
Ta lặp lại tiến trình đó cho các bước tiếp theo cho đến khi mặt đất bằng phẳng, lúc đó ta đã ở điểm thấp nhất của thung lũng. Nếu không chọn hướng xuôi dốc nhất mà di chuyển theo một hướng bất kì thì ta không thể đi xuống vị trí thấp nhất với số bước ít nhất hoặc trong trường hợp xấu, ta sẽ bị kẹt ở những nơi có cùng độ cao hoặc thậm chí di chuyển lên cao hơn. Về mặt toán học, bề mặt thung lũng đó được xem là đồ thị của cost function và điểm thấp nhấp của thung lũng là điểm cực tiểu của nó. Gradient Descent với hàm một biến Để hiểu rõ hơn về thuật toán Gradient Descent hoạt động như thế nào trong từng mô hình, dựa vào ví dụ dưới đây ta sẽ phân tích rõ thuật toán GD đối với hàm một biến.
Minh họa cho hàm số đạt giá trị nhỏ nhất (Nguồn: https://machinelearningcoban.com/) SVTH: Hoàng Thị Ly Na 12 Khoá luận tốt nghiệp GVHD: TS. Ngô Thời Nhân Ở trong hình, ta thấy điểm màu xanh lục là local minimum (điểm cực tiểu địa phương), đồng thời nó cũng là điểm cực tiểu toàn bộ (global minimum), điểm làm cho hàm số đạt giá trị nhỏ nhất. Dựa vào hình trên, ta biết được điều đầu tiên là điểm local minimum x* của hàm số là điểm có đạo hàm f 'x* = 0, ngoài ra đạo hàm của các điểm phía bên trái x* có giá trị âm, còn đạo hàm của các điểm phía bên phải x* có giá trị 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ì giá trị tuyệt đối của đạo hàm càng lớn.
Thứ hai là đườ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 đó. Bây giờ, giả sử xk là điểm ta tìm được sau vòng lặp thứ k, việc ta cần làm lúc này là cần tìm một thuận toán để đưa xk về càng gần x* càng tốt. Như vậy, trong hình ban đầu, chúng ta lại có thêm hai nhận xét đó là: Thứ nhất, nếu đạo hàm của hàm số tại xk : f’(xk) > 0 thì xk nằm về phía bên phải so với x*. Để điểm tiếp theo là xk+1 gần với x* hơn thì chúng ta cần di chuyển xk về phía bên trái, có nghĩa là về phía âm.
Ta có lập luận tương tự cho trường hợp f’(xk) < 0. Tóm lại, để tiến gần đến x* chúng ta cần di chuyển sao cho ngược dấu với đạo hàm: xk 1 xk (1) Trong đó, ∆ là một đại lượng ngược dấu với đạo hàm f’(xk). Thứ hai, nếu xk càng xa x* về phía bên phải thì f’(xk) sẽ càng lớn hơn 0 và ngược lại. Vì thế, lượng di chuyển ∆ một cách trực quan nhất đó là tỉ lệ thuận với - f’(xk).
Qua hai nhận xét trên cho chúng ta một công thức tổng quát cuối cùng đó là: xk 1 xk f '( xk ) (2) Trong đó, α > 0 là learning rate (tốc độ học), dấu trừ thể hiện việc chúng ta phải di chuyển ngược hướng đạo hàm. Đây cũng chính là lý do phương pháp này có tên gọi là SVTH: Hoàng Thị Ly Na 13 Khoá luận tốt nghiệp GVHD: TS. Ngô Thời Nhân Gradient Descent, bởi “Descent” có nghĩa là giảm, đi xuống hay đi ngược. Những nhận xét phía trên, mặc dù không phải luôn đúng cho mọi bài toán, nhưng nó được xem như 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ử, bây giờ ta cần tìm global minimum cho hàm f(x) trong đó x là một vectơ, thường được dùng để ký hiệu tập hợp các tham số của một mô hình cần tối ưu. Gradient của hàm số đó tại một điểm x bất kỳ, được ký hiệu là ∇xf(x). Tương tự như hàm một biến, thì thuật toán Gradient Descent cho hàm nhiều biến bắt đầu bằng một điểm dự đoán, x (0) sau đó cứ mỗi vòng lặp k, quy tắc tính đó là: x ( k 1) x ( k ) x f (x) (3) Hay viết dưới dạng đơn giản hơn: x x x f (x) (4) 1. Giải thuật và cách thực thi của phương pháp Gradient Descent Áp dụng những gì đã trình bày ở trên vào bài toán ML, giả sử rằng ta cần tìm tham số n để ta tiến hành tối thiểu hóa cost function J(θ).
Đầu tiên ta sẽ gán θ cho một giá trị bất kì nào đó, sau đó dựa vào gradient J ( ) để cập nhật giá trị mới cho sao cho giá trị của J(θ) ngày càng nhỏ cho đến khi đạt được giá trị cực tiểu. Việc cập nhật các thành phần của tham số θ được thực hiện cùng lúc nhờ vòng lặp sau. Repeat until converge { : J ( ) (5) } Trong đó α > 0, còn J ( ) là gradient của cost function tại θ. Trong vòng lặp trên, ta chú ý đến tham số α, được gọi là learning rate, là tham số điều chỉnh tốc độ học của chương trình ML.
Việc lựa chọn learning rate rất quan trọng trong các bài toán thực tế, lựa chọn giá trị này phụ thuộc nhiều vào từng bài toán và phải làm một vài thí nghiệm SVTH: Hoàng Thị Ly Na 14 Khoá luận tốt nghiệp GVHD: TS. Ngô Thời Nhân để chọn ra giá trị tốt nhất. Ngoài ra, tùy vào một số bài toán, GD có thể làm việc hiệu quả hơn bằng cách chọn ra learning rate phù hợp hoặc chọn learning rate khác nhau ở mỗi vòng lặp. 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 α.
Việc chọn α có ý nghĩa rất lớn trong phương pháp này vì nó quyết định tới độ chính xác và hiệu quả của giải thuật. Việc xác định được các tham số θ nhanh hay chậm phụ thuộc vào tham số này, tuy nhiên nếu như lựa chọn không phù hợp có thể gây ra hệ luỵ nhất định. Cụ thể là, nếu α quá lớn thì ta không hội tụ được về đích, nhưng nếu α quá nhỏ thì tốc độ hội tụ rất chậm, ảnh hưởng tới tốc độ của thuật toán, ta lại mất rất nhiều thời gian để chạy giải thuật này. Ảnh hưởng của Learning Rate (tốc độ học) (Nguồn: https://dominhhai.io/) Ngoài ra, nếu cost function J(θ) không phải là hàm lồi thì kết quả tìm được rất có thể chỉ là điểm cực tiểu địa phương (local minimum) thay vì điểm cực tiểu toàn cục (global minimum).