Thuật toán Gradient Descent

Written on March 10, 2019

Giới thiệu thuật toán Gradient Descent

Trong toán học, gradient là một trường hợp tổng quát của đạo hàm. Trong khi đạo hàm được định nghĩa trên các hàm số đơn biến và có giá trị vô hướng, gradient có giá trị là một vector. Giống như đạo hàm, gradient biểu diễn độ dốc tiếp tuyến (tangent) của đồ thị hàm số. Gradient của một hàm đa biến \(f\left( {{x_1},..,{x_M}} \right)\) là một vector chứa tất cả các đạo hàm riêng phần (partial derivatives) của hàm \(f\) và được ký hiệu là \(\nabla f\). Phần tử \(i\) trong gradient là đạo hàm riêng phần của hàm \(f\) theo biến \({x_i}\). Cho hàm \(f:{\mathbb{R}^n} \to \mathbb{R}\) là hàm lồi và khả vi, bài toán chúng ta cần giải quyết là tìm \({x^*}\) sao cho:

\[\begin{align} f\left( {{x^*}} \right) = \min f\left( x \right) \end{align}\]

Xem xét bài toán trên, như chúng ta đã biết rằng để tìm cực tiểu của một hàm lồi, ta cần phải tìm điểm dừng của hàm số đó. Trong toán học, điểm dừng (stationary point) của một hàm khả vi là điểm mà mọi phần tử của gradient tại điểm đó đều bằng \(0\). Ý tưởng của phương pháp gradient descent là chúng ta sẽ bắt đầu tại một điểm tùy ý, sau đó di chuyển dọc theo hướng ngược lại của gradient tại điểm đó, tiếp tục lặp lại quá trình này cho đến khi hy vọng có thể hội tụ tại điểm dừng. Hình bên dưới đã minh họa ý tưởng này.

Ảnh minh họa cho quá trình lặp của thuật toán gradient descent trong không gian 2 chiều
Ảnh minh họa cho quá trình lặp của thuật toán gradient descent trong không gian 2 chiều

Cụ thể hơn, chúng ta sẽ xác định hướng và kích thước di chuyển thông qua mô tả bằng các công thức toán học. Bắt đầu tại một điểm \({x^{\left( 0 \right)}} \in {\mathbb{R}^n}\) bất kỳ, chúng ta sẽ di chuyển theo hướng \(\nabla f\left( {{x^{\left( k \right)}}} \right)\) tại mỗi lần lặp $k \ge 0$ với kích thước lặp ${t_k}$ (step size) tới điểm tiếp theo \({x^{\left( {k + 1} \right)}}\). Quá trình lặp này được tóm gọn trong công thức sau đây:

\[\begin{align} {x^{\left( {k + 1} \right)}} = {x^{\left( k \right)}} - {t_k}\nabla f\left( {{x^{\left( k \right)}}} \right) \end{align}\]

Chúng ta có thể lựa chọn kích thước lặp cố định ${t_k} = t$ với t là một số dương hoặc kích thước lặp được ước lượng tại mỗi lần lặp thông qua công thức sau:

\[\begin{align} {t_k} = \arg {\min _{t \ge 0}}f\left( {{x^{\left( k \right)}} - t\nabla f\left( {{x^{\left( k \right)}}} \right)} \right) \end{align}\]

Quá trình lặp dừng lại tại một số điểm hoặc khi thỏa mãn điều kiện mà bài toán chúng ta cần giải quyết đặt ra. Với độ chính xác $\varepsilon > 0$ cho trước, thuật toán gradient descent có thể được trình bày cụ thể như sau:

\[\begin{array}{l} 1:\,\,{\rm{Guess}}\,\,{x^{\left( 0 \right)}},\,\,{\rm{set}}\,\,k \leftarrow 0\\ 2:\,\,{\rm{while}}\,\,\left\| {\nabla f\left( {{x^{\left( k \right)}}} \right)} \right\| \ge \varepsilon \,\,{\rm{do}}\\ 3:\,\,\,\,\,\,\,\,\,\,\,\,{x^{\left( {k + 1} \right)}} = {x^{\left( k \right)}} - {t_k}\nabla f\left( {{x^{\left( k \right)}}} \right)\\ 4:\,\,\,\,\,\,\,\,\,\,\,\,k \leftarrow k + 1\\ 5:\,\,{\rm{end}}\,{\rm{while}}\\ 6:\,\,{\rm{return}}\,\,{x^{\left( k \right)}} \end{array}\]

Ứng dụng thuật toán Gradient Descent trong Machine Learning

Trong quá trình huấn luyện các mô hình mạng nơ-ron nhân tạo, thuật toán gradient descent được sử dụng để xác định bộ trọng số $w$ sao cho hàm mất mát \(E\left( w \right)\) đạt cực tiểu. Trong phạm vi của bài viết này, mình sẽ trình bày những ý tưởng tổng quát về quá trình áp dụng thuật toán gradient descent trong machine learning và không tập trung đi quá sâu chi tiết về mặt toán học.

Ảnh minh họa cho quá trình tối ưu hóa hàm mất mát trong machine learning bằng thuật toán gradient descent
Ảnh minh họa cho quá trình tối ưu hóa hàm mất mát đơn giản bằng thuật toán gradient descent. Nguồn: Andrew Ng

Xét hàm mất mát \(E\left( w \right)\) là một hàm khả vi (differentiable) và liên tục (continuously) với tham số là bộ trọng số $w$. Hàm \(E\left( w \right)\) sẽ ánh xạ bộ trọng số $w$ sang số thực. Chúng ta sẽ tìm \(w^*\) thỏa mãn điều kiện:

\[\begin{align} \nabla E\left( {{w^*}} \right) = 0 \end{align}\]

Trong đó, $\nabla$ là toán tử gradient:

\[\begin{align} \nabla = {\left[ {\frac{\partial }{{\partial {w_1}}},\frac{\partial }{{\partial {w_2}}},...,\frac{\partial }{{\partial {w_M}}}} \right]^T} \end{align}\]

\(\nabla E\left( w \right)\) là gradient của hàm mất mát:

\[\begin{align} \nabla {\rm E}\left( w \right) = {\left[ {\frac{{\partial E}}{{\partial {w_1}}},\frac{{\partial E}}{{\partial {w_2}}},...,\frac{{\partial E}}{{\partial {w_M}}}} \right]^T} \end{align}\]

Chúng ta bắt đầu bằng cách tạo một ước đoán ngẫu nhiên ban đầu là \({w_0}\), sau đó cập nhật các trọng số này sao cho giá trị hàm mất mát \({\rm E}\left( w \right)\) được giảm dần tại mỗi lần lặp của thuật toán:

\[\begin{align} E\left( {{w_{n + 1}}} \right) < E\left( {{w_n}} \right) \end{align}\]

Trong đó \({w_{n}}\) là giá trị cũ của bộ trọng số và \(w_{n + 1}\) là giá trị mới được cập nhật. Thuật toán gradient descent sẽ điều chỉnh bộ trọng số $w$ sao cho hàm mất mát ngày càng đạt giá trị tối thiểu. Việc điều chỉnh bộ trọng số $w$ tại mỗi lần lặp của thuật toán được áp dụng theo hướng ngược lại với vector gradient:

\[\begin{align} {w_{n + 1}} = {w_n} - \eta \nabla E\left( {{w_n}} \right) \end{align}\]

Trong đó $\eta$ là một số thực dương được gọi là learning rate hoặc step size và \(\nabla E\left( {{w_n}} \right)\) là vector gradient tại điểm \(w_{n}\). Giá trị learning rate có ảnh hưởng rất lớn đến việc hội tụ của thuật toán gradient descent. Nếu learning rate nhỏ, thuật toán sẽ hội tụ chậm, nếu learning rate lớn, thuật toán sẽ hội tụ tiến nhanh đến mục tiêu. Tuy nhiên khi learning rate vượt qua một ngưỡng quan trọng nhất định, thuật toán sẽ dẫn đến hiện tượng phân kỳ.

Written by Nguyen Truong Long