Bài trước mình đã giới thiệu mọi người cách huấn luyện mô hình học máy, trong đó mục đích của việc huấn luyện là để tìm ra các tham số mà tại đó hàm chi phí [hàm mất mát] đạt giá trị nhỏ nhất
Trong tính toán tối ưu, công việc tìm ra cực trị của hàm số rất phổ biến. Có nhiều phương pháp để tìm cực trị hàm số, trong đó cách phổ biến nhất là tìm đạo hàm rồi giải phương trình hàm số bằng 0, các nghiệm sẽ là hữu hạn và thay vào đó từng nghiệm vào hàm số sẽ được các cực trị.
Tuy nhiên, không phải lúc nào chúng ta cũng có thể tìm ra được đạo hàm cũng như giải phương trình đạo hàm. Lý do là hàm số có đạo hàm phức tạp, dữ liệu có nhiều chiều… Vì vậy người ta nghĩ ra 1 cách để tìm cực trị [cực tiểu/cực đại] bằng phương pháp Gradient Descent
Gradient Descent là gì?Gradient Descent [GD] là thuật toán tìm tối ưu chung cho các hàm số. Ý tưởng chung của GD là điều chỉnh các tham số để lặp lại thông số lặp lại qua mỗi dữ liệu huấn luyện để giảm thiểu hàm chi phí
Giả sử bạn bị lạc trên 1 ngọn núi và trong sương mù dày đặc, bạn chỉ có thể cảm nhận được độ dốc của mặt đất dưới chân bạn. Một cách tốt nhất để nhanh chóng xuống chân núi là xuống dốc theo hướng dốc nhất. Đây chính là ý tưởng của Gradient Descent thực hiện, tại mỗi điểm của hàm số, nó sẽ xác định độ dốc sau đó đi ngược lại với hướng của độ dốc khi độ dốc nào tại chỗ đó bằng 0 [cực nhỏ]
Gradient Descent là một thuật toán tối ưu lặp [thuật toán tối ưu hóa lặp đi lặp lại] được sử dụng trong các bài toán Machine Learning và Deep Learning [thường là các bài toán tối ưu lồi — Convex Optimization] với mục tiêu là tìm kiếm các biến nội dung tập tin tại . in which
- Dốc. is the rate of tilt of the speed [tỷ lệ nghiêng hoặc nghiêng của dốc]. Về mặt toán học, Gradient của một hàm số là đạo hàm của hàm số tương ứng với từng biến của hàm. Đối với hàm số đơn biến, chúng ta sử dụng khái niệm Derivative thay cho Gradient
- Hạ xuống. là từ viết tắt của giảm dần, nghĩa là giảm dần
Gradient Descent có nhiều dạng khác nhau như Stochastic Gradient Descent [SGD], Mini-batch SDG. Nhưng về cơ bản thì đều được thực thi như sau
- Khởi tạo nội dung biến tại
- Mô hình đánh giá dựa trên biến nội tại và hàm mất mát [Loss function]
- Cập nhật các biến nội dung theo hướng tối ưu hàm mất mát [tìm điểm tối ưu]
- lặp lại bước 2, 3 để truy cập khi điều kiện dừng
- Công thức cập nhật cho GD có thể được viết là
trong đó $θ$ là tập các biến cần cập nhật, $η$ là tốc độ học [learning rate], $▽Өf[θ]$ là Gradient của hàm mất mát f theo tập θ
Tỷ lệ họcCó 1 tham số quan trọng trong Gradient Descent đó là giá trị lớn của mỗi lần di chuyển [giống như độ dài của chân khi bạn leo xuống dốc]
Tham số này được gọi là tốc độ học [tốc độ học]. Nếu tốc độ học quá nhỏ, thuật toán sẽ phải thực hiện nhiều bước để hội tụ và sẽ mất nhiều thời gian
Tuy nhiên, nếu tốc độ học tập quá lớn sẽ khiến thuật toán đi qua cực nhỏ, và vượt trội chắc chắn khiến thuật toán không thể hội tụ được.
Trong thực tế, không phải hàm số nào cũng chỉ có 1 cực tiểu. Ta sẽ có khái niệm cực tiểu cục bộ và cực tiểu toàn cục. Hiểu nôm na nó giống như hố hoặc đá tảng ở trên núi khi bạn đang leo xuống núi. Lúc này việc tìm ra cực tiểu sẽ trở nên khó khăn hơn. Xem hình sau để biết chi tiết
Sẽ có 2 vấn đề lúc này đối với GD
Điểm phát có thể ở bên trái hoặc bên phải, nếu phát từ bên trái, thuật toán sẽ hội tụ ở mức tối thiểu cục bộ [cực tiểu địa phương] mà không đi đến mức tối thiểu toàn cầu [cực tiểu toàn cục]
Hoặc nếu xuất phát từ bên phải sẽ mất nhiều thời gian để vượt qua Cao nguyên để đạt mức tối thiểu toàn cầu và nếu kết thúc thuật toán quá sớm thì sẽ không đạt mức tối thiểu toàn cầu
Bài trước chúng ta có sử dụng hàm chi phí MSE cho bài toán hồi quy tuyến tính, rất có thể hàm này là hàm lồi. Nghĩa là nếu 1 đường thẳng nối 2 điểm bất kỳ trên đồ thị hàm lồi thì đường thẳng này sẽ không cắt đồ thị. Điều này có nghĩa là không có cực tiểu địa phương [cục bộ tối thiểu] mà chỉ có 1 cực tiểu toàn cục. Đây cũng là một chức năng liên tục có độ dốc không bao giờ thay đổi đột ngột. Vì vậy, GD ở đây có 1 vấn đề, đó là nó sẽ không tiến gần đến mức tối thiểu toàn cầu [ngoại trừ khi thời gian học đủ lâu và tốc độ học đủ nhỏ]
Trên thực tế, hàm chi phí có dạng đồ thị giống hệt chiếc bát, nếu các tính năng [điểm đặc biệt của đầu vào - thành phần của véc tơ X] có cùng phạm vi giá trị, thì cú đánh răng sẽ tròn và để GD đi xuống đáy bát . Nếu các tính năng khác phạm vi giá trị thì bát mã sẽ bị kéo dài ra và việc đi xuống đáy bát sẽ biến thành thời gian hơn. Đây là lý do tại sao các đặc trưng của vector bắt đầu vào X cần phải được thu nhỏ [căn chỉnh]
Như bạn có thể thấy, ở bên phải thuật toán Gradient Descent đi thẳng về điểm tối thiểu, làm sao để nhanh chóng đạt được cực tiểu toàn cục, trong khi bên trái, nó đi theo hướng gần như trực giao với hướng về cực tiểu toàn cầu . Cuối cùng nó sẽ đạt đến cực tiểu, nhưng sẽ mất nhiều thời gian
Giảm dần hàng loạtKhi bạn thực hiện thuật toán Gradient Descent, bạn nên đưa các tính năng về cùng phạm vi giá trị [sử dụng StandardScaler của thư viện Scikit-Learn
Để thực hiện thuật toán Gradient Descent, chúng ta phải tìm được đạo hàm của hàm chi phí ảnh hưởng đến từng tham số của mô hình $ \theta_j $. Nói khác đi, cần phải xác định giá trị hàm chi phí thay đổi thế nào nếu thay đổi $ \theta_j $. Cái này được gọi là đạo hàm riêng [đạo hàm riêng]
Sau biểu thức sẽ được sử dụng để tính toán hàm riêng của hàm chi phí cho tham số $ \theta_j $, được ký hiệu là $ \frac{\delta}{\delta\theta_j}MSE[\theta] $
\[\frac{\delta}{\delta\theta_j}MSE[\theta] = \frac{2}{m}\sum_{i=1}^m[\theta^Tx^{[i]} - yThay vì tính từng hàm thành phần, bạn có thể sử dụng công thức sau để tính tất cả trong 1 bước. Vectơ độ dốc, ký hiệu $ ∇_\theta MSE[\theta] $ là hàm riêng [vector độ dốc] cho các tham số $ \theta] $ của mô hình
Khi chúng ta có vector độc dốc và vị trí hiện tại, chúng ta chỉ cần đi ngược lại với vector độ dốc. Nghĩa là ta phải loại trừ θ đi 1 value is $ ∇_\theta MSE[\theta] $. Lúc này ta sẽ sử dụng tham số học tỷ lệ $ \eta $ để xác định giá trị của bước xuống dốc bằng cách nhân vào
\[\theta^{[bước tiếp theo]} =\theta - \eta ∇_\theta MSE[\theta]\]Bây giờ chúng ta sẽ thực hiện bài kiểm tra trước bằng Python
eta = 0.1 # learning rate n_iterations = 1000 m=100 theta = np.random.randn[2,1] # random initialization for iteration in range[n_iterations]: gradients = 2/m * X_b.T.dot[X_b.dot[theta] - y] theta = theta - eta * gradients0
Kết quả của theta sẽ như sau
eta = 0.1 # learning rate n_iterations = 1000 m=100 theta = np.random.randn[2,1] # random initialization for iteration in range[n_iterations]: gradients = 2/m * X_b.T.dot[X_b.dot[theta] - y] theta = theta - eta * gradients1
Như vậy là có vẻ GD hoạt động tốt. Nhưng nếu sử dụng học suất khác nhau thì sao?
Ở bên trái, tốc độ học quá thấp. thuật toán cuối cùng sẽ hội tụ, nhưng sẽ mất nhiều thời gian. Ở giữa, tỷ lệ học tập có vẻ khá tốt. chỉ trong vài lần thuật toán hội tụ. Ở bên phải, tốc độ học tập quá cao. thuật toán phân kỳ, nhảy khắp nơi và ngày càng rời xa cực nhỏ ở mỗi bước nhảy
Ở bài sau, mình sẽ hướng dẫn các bạn tìm tỷ lệ học phù hợp với từng bài toán. Còn 1 vấn đề nữa đó là số lần lặp của thuật toán, nếu thực hiện ít bước, thuật toán có thể không đạt cực tiểu, còn nếu nhiều quá thuật toán có thể mất nhiều thời gian thực hiện mà các tham số hầu hết . Giải pháp đơn giản là ta sẽ dừng thuật toán khi giá trị chuẩn của véc tơ độ dốc [gradient vector] đủ nhỏ và nhỏ hơn 1 số ε [được gọi là dung sai] để đảm bảo thuật toán đến điểm hội tụ
Độ dốc ngẫu nhiênKhi hàm chi phí là hàm nổi và độ dốc của nó không thay đổi đột ngột [như trường hợp của hàm MSE], Batch Gradient Descent với tốc độ học cố định cuối cùng sẽ hội tụ đến cực tiểu, tuy nhiên bạn có thể phải chờ đợi . nó có thể mất bước nhảy O[1 /ε] để cực tiểu trong phạm vi ε phụ thuộc vào dạng của hàm chi phí. Nếu bạn chia ε cho 10 để có kết quả tốt hơn thì thuật toán có thể phải chạy lâu hơn khoảng 10 lần
Thay vì sử dụng toàn bộ tập huấn luyện thì Stochastics Gradient Descent [SGD] sẽ lấy ngẫu nhiên 1 phần tử trong tập huấn luyện và thực hiện tính toán lại vector tốc độ dốc chỉ dựa trên 1 điểm dữ liệu, sau đó lặp đi lặp lại . Và việc tính toán dựa trên 1 điểm dữ liệu sẽ làm cho thuật toán chạy nhanh hơn bởi có rất ít dữ liệu cần xử lý ở mỗi vòng lặp. Và điều này cũng giúp mô hình có thể được huấn luyện với những dữ liệu lớn vì mỗi vòng lặp chỉ cần đưa 1 điểm dữ liệu vào trong bộ nhớ
Mặt khác do tính chất ngẫu nhiên của dữ liệu được đưa vào nên trong quá trình huấn luyện, thay vì hàm chi phí giảm từ giống Batch GD thì hàm chi phí của SGD sẽ lúc tăng lúc giảm nhưng sẽ giảm dần theo khoảng thời gian. Dần dần kinh nghiệm của bài toán nó sẽ tiện ích rất gần với cực tiểu nhưng khi đã đạt được cực tiểu thì giá trị hàm chi phí sẽ liên tục thay đổi mà không giữ ổn định. Khi gặp điều kiện dừng lại, ta sẽ được tham số cuối cùng đủ tốt, nhưng chưa thực sự tối ưu
Khi hàm chi phí liên tục thay đổi có thể giúp thuật toán nhảy ra khỏi cực tiểu địa phương. Vì vậy SGD có cơ hội để tìm được cực trị toàn cục hơn là Batch Gradient Descent. Vì vậy nên lựa chọn ngẫu nhiên dữ liệu sẽ giúp thoát khỏi bộ kinh nghiệm cục bộ tối ưu nhưng điều đó có nghĩa là thuật toán cũng không bao giờ có kinh nghiệm cực tiểu
learning rate giảm dần
Người ta nghĩ ra thêm 1 cách giải quyết đó là giảm dần tốc độ học trong quá trình huấn luyện. Các vòng lặp đầu tiên chúng ta sẽ đạt được tốc độ học tập lớn để thoát khỏi cực tiểu địa phương, sau đó giảm dần tốc độ học tập để đạt được cực tiểu địa phương. Hàm xác định tốc độ học tập ở mỗi lần lặp được gọi là hàm lên lịch cho tốc độ học tập
Nếu tốc độ học tập giảm quá nhanh, thuật toán có thể bị dừng lại ở điểm cực tiểu địa phương, hoặc kết thúc ở lưng chừng khi chưa đến điểm cực tiểu. Nếu tốc độ học giảm quá chậm, hàm chi phí có thể thay đổi lên xuống mức tối thiểu trong thời gian dài và kết thúc bằng một kinh nghiệm tối đa nếu bạn ngừng đào tạo quá sớm
Đoạn mã sau mô phỏng việc làm giảm dần tỷ lệ học tập trong quá trình đào tạo
eta = 0.1 # learning rate n_iterations = 1000 m=100 theta = np.random.randn[2,1] # random initialization for iteration in range[n_iterations]: gradients = 2/m * X_b.T.dot[X_b.dot[theta] - y] theta = theta - eta * gradients2
Đánh giá SGD
Thuật toán lặp lại bởi các vòng lặp m, mỗi lần lặp lại được gọi là 1 epoc. Trong bài trước khi sử dụng Batch GD lặp lại 1000 lần thì SGD chỉ cần đến 50 lần là được kết quả khá tốt
eta = 0.1 # learning rate n_iterations = 1000 m=100 theta = np.random.randn[2,1] # random initialization for iteration in range[n_iterations]: gradients = 2/m * X_b.T.dot[X_b.dot[theta] - y] theta = theta - eta * gradients3
Lưu ý với SGD
Vì việc lựa chọn các điểm dữ liệu để huấn luyện là ngẫu nhiên nên 1 vài điểm dữ liệu có thể được chọn nhiều lần ở các epoc khác nhau và 1 số điểm dữ liệu thì không được sử dụng đến. Nên chọn nếu bạn muốn chắc chắn rằng thuật toán đi qua tất cả các điểm dữ liệu thì cách tốt nhất là sắp xếp lại ngẫu nhiên các tập huấn luyện sau mỗi epoc
Để thực hiện Hồi quy tuyến tính sử dụng SGD với Scikit-Learn, bạn có thể sử dụng lớp SGDRegressor. Mặc dù nó sẽ tối ưu hóa bình phương hàm chi phí , mã đoạn sau sẽ chạy tối đa 1000 kỷ nguyên [max_iter=1000] hoặc đến khi hàm mất mát nhỏ hơn 1e-3 [tol=1e-3]. Started with learning rate = 0. 1 [eta0 = 0. 01]. Sử dụng chức năng lên lịch mặc định
eta = 0.1 # learning rate n_iterations = 1000 m=100 theta = np.random.randn[2,1] # random initialization for iteration in range[n_iterations]: gradients = 2/m * X_b.T.dot[X_b.dot[theta] - y] theta = theta - eta * gradients4Mini-batch Gradient Descent
Thuật toán Gradient Descent cuối cùng mà chúng tôi nghiên cứu đó là Mini-batch Gradient Descent. Nếu chúng ta hiểu về lô GD và SGD thì sẽ dễ dàng hiểu về Mini-batch GD. ở mỗi bước, thay vì vector tính toán độ dốc dựa trên toàn bộ tập huấn luyện [như thằng Batch GD] hoặc dựa trên 1 điểm dữ liệu [như thằng Stochastic GD] thì Mini-batch GD tính toán độ dốc dựa trên 1 tệp nhỏ ngẫu nhiên . Ưu điểm chính của Mini-batch GD so với Stochastic GD đó là chúng ta có thể tận dụng tối đa hiệu quả tối đa của phần cứng khi thực hiện các phép toán trên ma trận, ví dụ như GPU [tận dụng khả năng tính toán song song].
Mini-batch GD sẽ tiến tới gần cực tiểu toàn cục hơn SGD nhưng sẽ khó thoát khỏi cực tiểu địa phương hơn. Dù vậy SGD và GD lô nhỏ sẽ tiến tới cực tiểu toàn cục nếu chúng ta áp dụng hợp lý tỷ lệ học tập giảm dần