Learning rate decay là gì

Vicohub

Nội dung chính Show

Thuật Toán Tối Ưu Gradient Descent
1. Gradient Descent là gì?
2. Sample, Epoch, Batch và Iterations
2.4 Iterations
3. Một số vấn đề trong Gradient Descent
3.1 Momentum và Nesterovs Acceleration
3.2 Vanishing và Exploding Gradient
3.3 Regularization

Aug 25, 2019

10 min read

Thuật Toán Tối Ưu Gradient Descent

Author: Cuong Tran (Vicohub)

Nearly all of deep learning is powered by one very important algorithm: Stochastic Gradient Descent (SGD) Goodfellow.

Trong bài viết này mình sẽ đề cập đến một thuật toán rất quan trọng cho các bài toán tối ưu trong Machine Learning, Neural Network và Deep Learning mà bất cứ Data Scientist, Computer Vision hay AI Engineer đều phải biết, đó là Gradient Descent (GD). Đồng thời chúng ta sẽ phân biệt và làm rõ một số khái niệm có liên quan tới GD thường hay lẫn lộn là Sample, Epoch, Batch và Iterations, cũng như một số vấn đề có liên quan tới GD.

Trước khi đi vào tìm hiểu về GD, chúng ta cần hiểu thế nào là thuật toán tối ưu (Optimization Algorithm) trong Artificial Neural Networks (ANN). Về cơ bản, các thuật toán tối ưu chính là các engine cơ sở để xây dựng các mô hình neural network với mục tiêu là học được các đặc điểm (features hay patterns) từ dữ liệu đầu vào, từ đó có thể tìm một tập các weights W và bias b (hay internal model parameters) để tối ưu hóa độ chính xác của models (obtaining a high accuracy models).

Nhưng vấn đề là học như thế nào? Cụ thể hơn là làm sao để tìm W và b một cách hiệu quả! Có phải chỉ cần random W và b một số lần hữu hạn và hy vọng ở một bước nào đó chúng ta sẽ tìm ra được tập lời giải. Rõ ràng là không khả thi và lãng phí tài nguyên! Chúng ta cần một thuật toán để cải thiện W và b theo từng bước (iterative improving), và đó là lý do GD ra đời.

1. Gradient Descent là gì?

Gradient Descent là một thuật toán tối ưu lặp (iterative optimization algorithm) đượ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 một tập các biến nội tại (internal parameters) cho việc tối ưu models. Trong đó:

Gradient: là tỷ lệ độ nghiêng của đường dốc (rate of inclination or declination of a slope). 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 mỗi 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.

Descent: là từ viết tắt của descending, 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 biến nội tại.
Đánh giá model dựa vào 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 tại theo hướng tối ưu hàm mất mát (finding optimal points).
Lặp lại bước 2, 3 cho tới khi thỏa đ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 θ.

Gradient Descent có thể được minh họa như trong hình:

Nguồn: https://medium.com/onfido-tech/machine-learning-101-be2e0a86c96a

Tối ưu hàm mất mát là việc tìm các điểm optimal points mà ở đó hàm mất mát đạt cực đại (maximum) hoặc cực tiểu (minimum). Nếu hàm mất mát không phải là hàm lồi thì sẽ có các local maximum hoặc local minimum points bên cạnh các global maximum hoặc global minimum points như hình bên dưới. Mục tiêu của GD là tìm được các global minimum points. Tuy nhiên trong các bài toán tối ưu lồi áp dụng GD thì các local minimum points của hàm mất mát cũng chính là global minimum points của nó.

Nguồn: https://www.quora.com/What-is-the-local-minimum-and-global-minimum-in-machine-learning-Why-are-these-important-in-machine-learning

Điều kiện dừng của GD có thể là:

Kết thúc tất cả các epochs đã được định sẵn.

Giá trị của hàm mất mát đủ nhỏ và độ chính xác của model đủ lớn.

Hàm mất mát có giá trị không thay đổi sau một số lần hữu hạn epochs.

Các bài toán trong thực tế áp dụng GD thường khó tìm được các global minimum points, đa phần rơi vào các local minimum points hoặc không phải các optimal points (not converging), tuy nhiên chúng ta vẫn có thể chấp nhận các kết quả của GD trả về khi model đã đủ tốt (good enough).

[An] optimization algorithm may not be guaranteed to arrive at even a local minimum in a reasonable amount of time, but it often finds a very low value of the [loss] function quickly enough to be useful. Goodfellow.

2. Sample, Epoch, Batch và Iterations

2.1 Sample

Sample là một dòng dữ liệu bao gồm các inputs để đưa vào thuật toán, một output (ground-truth) để so sánh với giá trị dự đoán và tính giá trị của hàm mất mát. Dữ liệu huấn luyện thường bao gồm nhiều samples. Sample còn được gọi là instance, an observation, an input vector, hay a feature vector.

2.2 Epoch

Epoch là một hyperparameter trong ANN, được dùng để định nghĩa số lần learning algorithm hoạt động trên model, một epoch hoàn thành là khi tất cả dữ liệu training được đưa vào mạng neural network một lần (đã bao gồm cả 2 bước forward và backward cho việc cập nhật internal model parameters).

Tuy nhiên khi dữ liệu training là quá lớn (ví dụ training images từ ImageNet, Google Open Images), việc đưa tất cả training data vào trong 1 epoch là không khả thi và không hiệu quả. Trường hợp số epoch nhỏ thì dễ dẫn đến underfitting vì model không học được nhiều từ GD để cập nhật các biến nội tại. Đối với các trường hợp này thì giải pháp là chia nhỏ training dataset ra thành các batches cho mỗi epoch thì cơ hội model học được từ GD sẽ nhiều hơn và tốc độ tính toán sẽ tối ưu hơn.

Chọn số epoch như thế nào? Thường chúng ta cần một số lượng lớn epoch để training cho ANN (10, 100, 500, 1000) tuy nhiên cũng còn tùy thuộc vào bài toán và tài nguyên máy tính. Một cách khác là sử dụng Learning Curve để tìm số epoch.

2.3 Batch

Như đã nói, một tập training dataset có thể được chia nhỏ thành các batches (sets, parts). Một batch sẽ chứa các training samples, và số lượng các samples này được gọi là batch size. Cần lưu ý có 2 khái niệm khác nhau là batch size và number of batches (số lượng các batches) or iterations. Tùy thuộc vào batch size mà GD sẽ có các biến thể khác nhau:

Batch Gradient Descent: Batch Size = Size of Training Dataset

Stochastic Gradient Descent: Batch Size = 1

Mini-Batch Gradient Descent: 1 < Batch Size < Size of Training Set

Thông thường thi Mini-Batch Gradient Descent được sử dụng nhiều cho các bài toán tối ưu vì tính hội tụ ổn định hơn so với Stochastic Gradient Descent. Dữ liệu trước khi đưa vào 2 dạng này thường được chọn một cách ngẫu nhiên từ training dataset. Đối với Mini-Batch Gradient Descent thì batch size thường được chọn là lũy thừa của 2 (32, 64, 128, 256) vì tốc độ tính toán sẽ tối ưu cho các arithmetic algorithms của CPU và GPU. Cách chọn batch size cũng tùy theo yêu cầu của bài toán. Trường hợp chia không chẵn số batch size theo training dataset thì batch cuối cùng sẽ có ít samples hơn các batches khác.

2.4 Iterations

Iteration là số lượng batches (number of batches) cần thiết để hoàn thành một epoch. Công thức tính là iterations = training samples/batch size. Ví dụ: một dataset có 200 samples, chọn batch size là 5, số epochs là 1000 thì trong 1 epoch số iterations sẽ là 200/5 = 40, model sẽ có cơ hội cập nhật các biến nội tại 40 lần, nhân với số epochs thì số lần cập nhật của model sẽ là 40*1000 = 40000 lần (tương ứng với 40000 batches).

3. Một số vấn đề trong Gradient Descent

3.1 Momentum và Nesterovs Acceleration

Nhắc lại công thức cập nhật của GD, một tham số rất quan trọng cần lưu ý đến là tốc độ học η (learning rate), η sẽ quy định số bước học cần thiết cho models. Việc chọn η phù hợp sẽ tùy thuộc vào model và dataset. Nếu η quá nhỏ thì model sẽ mất rất nhiều steps hay iterations để tiến tới các điểm optimal points. Trường hợp η quá lớn thì biến cập nhật sẽ nhảy quanh (bounding around) các điểm optimal points và không hội tụ. Có thể minh hoạt như trong hình:

Nguồn: https://www.jeremyjordan.me/nn-learning-rate/

Có 2 cách để điều chỉnh quá trình cập nhật của GD:

Sử dụng Momentum: ý tưởng cơ bản của momentum là gia tốc học khi cùng hướng với chiều của gradient và giảm tốc học khi ngược hướng với gradient. Khi momentum của GD đủ lớn thì các biến cập nhật có thể vượt qua các local optimal points để hướng đến các điểm global như trong hình. Một tham số quan trọng khi sử dụng momentum là γ, γ trong thực nghiệm thường được chọn là 0.9, hoặc ban đầu chọn γ = 0.5 tới khi ổn định và tăng dần lên 0.9.

Nguồn: https://machinelearningcoban.com/2017/01/16/gradientdescent2/

Sử dụng Nesterovs Acceleration: ý tưởng của Nesterovs Acceleration là cập nhật momentum theo đúng hướng đi của nó hay dự đoán hướng đi của momentum trước một bước. Có thể minh hoạt như trong hình:

Nguồn: https://cs231n.github.io/neural-networks-3/

Trong các bài toán thực tế với large-scale dataset như ImageNet hay Google Open Images thì GD with momentum thường được sử dụng nhiều hơn so với Nesterovs Acceleration. Còn đối với những dataset nhỏ hơn thì chúng ta có thể sử dụng Nesterovs Acceleration.

3.2 Vanishing và Exploding Gradient

Thuật toán lan truyền ngược (Backpropagation Algorithm) là một thuật toán thường được sử dụng trong quá trình huấn luyện các mô hình học sâu. Ý tưởng cơ bản là thuật toán sẽ từ output layer đi ngược trở lại input layer, tính toán gradient của hàm mất mất tương ứng với các biến nội tại (weight, bias) cho các hidden layers rồi dùng GD để cập nhật lại các biến này. Thuật toán được mong đợi sẽ hội tụ sau một số lần hữu hạn epochs nhưng thường sẽ có sự đánh đổi giữa độ chính xác của model và thời gian training.

Thực tế khi tiến hành training với backpropagation thì gradient của hàm mất mất sẽ nhỏ dần do tiến hành nhân các số hạng nhỏ liên tiếp với nhau, nếu mô hình đủ sâu (nhiều hidden layers) thì giá trị gradient sẽ tiến dần đến 0 sau một số layers nhất định và làm cho model không thể hội tụ -> không thể cập nhật được các biến nội tại như mong đợi. Hiện tượng này gọi là Vanishing Gradient.

Tuy nhiên gradient cũng có khả năng lớn dần trong quá trình backpropagation (như mô hình RNNs) do nhân nhiều số hạng lớn liên tiếp nhau dẫn tới các giá trị cập nhật quá lớn và cũng làm cho model không thể hội tụ (bounding around). Hiện tượng này gọi là Exploding Gradient.

Có 2 nguyên nhân chính dẫn tới các hiện tượng trên là do việc khởi tạo các biến nội tại (weight initialization) và việc chọn activation function cho các layers. Có nhiều kỹ thuật khác nhau để giảm thiểu 2 hiện tượng này như Xavier and He Initialization Techniques, Nonsaturating Activation Functions, Batch Normalization và Gradient Clipping.

3.3 Regularization

Many strategies used in machine learning are explicitly designed to reduce the test error, possibly at the expense of increased training error. These strategies are collectively known as regularization. Goodfellow

Regularization được dùng để điều chỉnh khả năng học của model để đảm bảo rằng model của chúng ta đủ tốt để đưa ra dự đoán cho các dữ liệu mới (control the ability to generalize). Nếu không sử dụng regularization thì model rất dễ trở nên phức tạp (complex) và overfitting training data và vì thế không có khả năng tổng quan hóa cho dữ liệu mới. Nhưng nếu sử dụng quá nhiều regularization thì model sẽ trở nên đơn giản (simple) và không học được nhiều từ dữ liệu training.

Trong quá trình cập nhật biến của GD, regularization thường được cộng vào hàm mất mất dưới dạng L1 regularization, L2 regularization (còn gọi là weight decay) hoặc Elastic Net để làm cho các giá trị trong weights matrix không quá lớn, do đó sẽ hạn chế khả năng bị overfitting của model. Ngoài ra còn có các kỹ thuật regularization khác như dropout, data augmentation và early stopping.

Conclusion

Trong bài viết này mình đã giới thiệu cho các bạn về Gradient Descent thuật toán tối ưu rất quan trọng dùng trong các mô hình học sâu. Đây là nền tảng để các bạn có thể hiểu thêm về các thuật toán tối ưu khác như AdaGrad, AdaDelta, RMSProp, Adam. Đồng thời chúng ta đã làm rõ một số khái niệm cũng như một số vấn đề có liên quan tới GD. Với những kiến thức này mình tin rằng các bạn sẽ đủ tự tin để làm việc trên các mô hình học sâu về sau! Happy Learning!