Gradient descent

1. Giới thiệu

Gradient descent là một kĩ thuật tối ưu rất quan trọng trong Machine Learning cũng như Deep Learning mà bạn cần phải biết. Mục đích chính của thuật toán này là tối ưu A để tìm được B. Vậy A và B là gì thì chúng ta sẽ lần lượt tìm hiểu rõ trong bài viết này.

Một lưu ý quan trọng là nội dung của bài viết này chỉ áp dụng cho một loại học máy phổ biến nhất trong thực tế là Supervised Learning, các bạn có thể tham khảo tại đây mình đã giới thiệu Supervised Learning là gì rồi. Nên bài viết này mình không trình bày lại nữa.

Nội dung:

• Loss Function
• Gradient Descent
• Implement Gradient Descent sử dụng python

2. Loss Function

Loss Function được gọi là hàm mất mát chính là độ chênh lệch giữa giá trị thực và giá trị dự đoán của model. Một số tài liệu Loss Function còn được gọi với tên gọi khác là Cost Function., hàm này cũng hay được gọi với cái tên là hàm mục tiêu.

Đây chính là A mà mình đã trình bày ở trên đó các bạn. Các bạn có thể quay lại phần tổng quan Machine Learning mình có trình bày: Để tìm được model chúng ta phải tìm parameters $w$ của model đó và ở bài viết đó mình cũng có trình bày là tìm các parameters thỏa mãn một yêu cầu nào đó. Thì yêu cầu ở đây là tìm parameters sao cho Loss Function đạt giá trị nhỏ nhất có thể. Model ở đây chính là 1 hàm $f$ nào đó thôi. Còn parameters chính là bộ tham số của hàm $f$. Để tìm được hàm $f$ ta chỉ cần tìm được parameters $w$.

Các bạn cần lưu ý ở đây là mỗi feature sẽ có 1 parameter, ở trên vector $w = [w_0, w_1, ..., w_m]$ với $m$ là số feature của dữ liệu, $w_0$ được gọi là bias

Giả sử gọi giá trị $w$ tại thời điểm $t = k$ là $w_k$. Như vậy đầu ra của model ứng với $w = w_k$ là $\hat{y}_{ik} = f_k(x_i)$. Với $x_i$ là của điểm dữ liệu thứ $i$, $x_i$ chính là một vector, với các cột chính là các feature. $\hat{y}_{ik}$ là output của model ứng với điểm dữ liệu thứ $i$ tại thời điểm $t = k$. $f_k$ là $f$ ứng với giá trị $w_k$.

Gọi $y_i$ là label cũng như là giá trị thực ứng với vector feature $x_i$. $l_i$ là độ chênh lệch giữa $y_i$ và $\hat{y}_{i}$ được tính như sau: $$l_i = y_i - \hat{y}_{i}$$ 

 Vì Loss Function không âm nên ta có thể viết lại thành $$l_i = (y_i - \hat{y}_{i})^2$$

$l_i$ được gọi là Square Error. Trong thực tế còn có nhiều hàm mất mát khác có thể kể đến như: Absolute Square Error, Square Error, Cross-Entropy... Tùy vào từng bài toán mà chúng ta sử dụng từng loại hàm mất mát khác nhau. Mình sẽ giới thiệu ở một bài khác.

Lưu ý: $l_i$ chỉ là một điểm dữ liệu thứ $i$. Trên thực tế $l$ được tính trên toàn bộ dữ liệu. Nên ta phải tính tổng các $l_i$ sau đó chia cho tổng số điểm dữ liệu.

Gọi $L$ là hàm mất mát trên toàn bộ dữ liệu, $N$ là số điểm dữ liệu: $$L = \frac{\sum_{i=1}^{N} l_i}{N}$$

3. Gradient Descent

Như ở phần đầu mình đã giới thiệu, mục đích của Gradient Descent là tối ưu A để tìm B. Các bạn đã biết A ở đây là Loss Function $L$. Còn B ở đây sẽ là các parameters $w$.

Như vậy Gradient Descent là kĩ thuật tối ưu để tìm các parameters $w$ sao cho $L$ đạt giá trị nhỏ nhất có thể. Như vậy tại sao chúng ta lại sử dụng Gradient Descent nhỉ? Như kiến thức cấp 3 thì chúng ta chỉ cần đạo hàm $L$ theo parameters $w$ sau đó cho đạo hàm này bằng 0 và giải phương trình này là xong. Tuy nhiên, trong thực tế các phương trình này khá phức tạp nên rất khó để giải, vì vậy, Gradient Descent ra đời để giải quyết vấn đề này.

Để tìm parameters $w$ ta áp dụng Gradient Descent dưới dạng công thức sau: $$w = w - \eta \frac{\partial L(X, w)}{\partial w}$$

$w$ trước và sau dấu bằng mang các giá trị khác nhau nhé. Trước dấu bằng là giá trị $w$ ta cần tính tạm gọi là tại thời điểm $t$. Còn sau dấu bằng là giá trị $w$ tại thời điểm trước đó, mình tạm gọi là tại thời điểm $t - 1$

$\eta$ được gọi là Learning rate hay hệ số học là bước nhảy sau mỗi thời điểm.

$\frac{\partial L(X, w)}{\partial w}$ là đạo hàm của hàm Loss Function theo $w$.$L(X, w)$ là Loss Function với đầu vào là ma trận dữ liệu $X$ (Vì $L$ được tính trên toàn bộ dữ liệu nên mình viết dưới dạng ma trận cho dễ nhìn) với parameters là $w$

Lưu ý: $X$ là ma trận có $n$ hàng là số điểm dữ liệu, $m$ cột là tổng số feature

Để đơn giản bạn có thể tưởng tượng việc thả một quả bóng từ trên đỉnh của một thung lũng để lăn xuống đáy của thung lũng.

Nguồn: https://www.kdnuggets.com/2018/06/intuitive-introduction-gradient-descent.html

Từ hình trên bạn quan sát được rằng:

• $\eta \frac{\partial L(X, w)}{\partial w}$ chính là bước nhảy sau mỗi thời điểm.
• Thay đổi $w$ sẽ làm cho $L$ thay đổi, mục đích của model là thay đổi $w$ để $L$ (quả bóng như trong hình) gần điểm global minimum có nhất có thể
• Bạn có để ý dấu "-" phía trước Learning Rate là gì không? Nhớ lại, hồi cấp 3 bạn học. Đạo hàm tại một điểm sẽ mang giá trị âm nếu điểm đó đứng phía bên trái điểm Minimum, ngược lại, nó sẽ mang giá trị dương nếu nó đứng bên phải điểm Minimum. Như vậy ta đưa đến kết luận rằng. Nếu quả bóng nằm bên trái điểm Minimum lúc này đạo hàm sẽ mang giá trị âm, âm của đạo hàm và dấu "-" phía trước nữa âm của âm sẽ thành dương, lúc này biểu thức Gradient Descent sẽ viết lại thành: $$w = w + \eta \frac{\partial L(X, w)}{\partial w}$$ Lúc này viên bi sẽ lăn từ trái sang phải, ngược lại với trường hợp viên bị nằm bên phải đạo hàm thì nó sẽ như công thức Gradient Descent sẽ thành $$w = w - \eta \frac{\partial L(X, w)}{\partial w}$$ Lúc này viên bi sẽ lăn từ phải sang trái

Các bước thực hiện Gradient Descent

• Bước 1: Khởi tạo giá trị $w$ ban đầu, vị trí đặt hòn bi thời điểm ban đầu. $w$ thường dc đặt là random tại thời điểm ban đầu
• Bước 2: Đặt giá trị cho Learning Rate, thường là $1e^{-3}$
• Bước 3: Định nghĩa dạng model, thường được gọi là hàm giả thuyết
• Bước 4: Lặp n lần:
  • Tính $\hat{y}$ với parameters w và đầu vào $X$
  • Tính Loss Function
  • Áp dụng công thức Gradient Descent để cập nhật $w$

Một số điều kiện dừng của Gradient Descent

• Lặp hết số vòng lặp
• Đạo hàm tại 2 thời điểm liên tiếp nhỏ hơn 1 số $\epsilon$
• Giá trị $w$ tại 2 thời điểm liên tiếp nhỏ hơn 1 số $\epsilon$

Một số thuật ngữ cần biết:

• Epochs: Số lần cập nhật $w$, hay các bạn có thể hiểu là số lần công thức Gradient Descent được áp dụng, như trên epochs chính là $n$, lưu ý điều này chỉ đúng khi ta sử dụng toàn bộ dữ liệu cho 1 lần cập nhật. Một định nghĩa chung hơn về 1 epoch là một lần duyệt qua hết các dữ liệu trong tập huấn luyện
• Batch size: Sử dụng bao nhiêu điểm dữ liệu cho mỗi lần cập nhật $w$, Batch size thường là $2^n$ như: 8, 16, 32, 64...
  • Nếu Batch size bằng số điểm dữ liệu thì Gradient Descent được gọi là Batch Gradient Descent.
  • Nếu Batch size bằng 1 thì Gradient Descent được gọi là Stochastic Gradient Descent
  • Nếu Batch size lớn hơn 1 và nhỏ hơn số điểm dữ liệu thì Gradient Descent được gị là Mini Batch Gradient Descent
• Step: Số bước cần thực hiện để hoàn thành 1 epoch. Thường được tính bằng tổng số điểm dữ liệu chia cho batch size

3. Implement Gradient Descent sử dụng Python

Các bạn vào click vào đây để xem source code nhé

Mình xin phép dừng bài viết này tại đây, nếu có thắc mắc gì vui lòng để lại comment phía dưới nhé, xin cảm ơn