Gradient Descent

Trong nhiều trường hợp chúng ta thường không thể tìm nghiệm của phương trình đạo hàm để từ đó tìm các cực trị địa phương. Một phương pháp hiệu quả là gradient descent.

Hàm một biến

Giả sử \(x^*\) là local extremum (cực trị địa phương) của hàm số \(f(x)\). Khi đó chúng ta xây dựng dãy số \(\{ x_n \}\) hội tụ về \(x^*\). Ý tưởng thực hiện là dựa trên nhận xét, nếu \(x_n\) nằm bên phải \(x^*\) thì \(x_{n+1}\) nằm giữa \(x^*\) và \(x_n\). Ta đã biết nếu \(x^*\) là một điểm cực trị thì \(f'(x) > 0\) với \(x > x^*\) (trường hợp cực tiểu), mà \(x_n\) đi từ bên phải sang bên trái (ngược chiều \(Ox\) nên mang dấu âm). Từ đó chúng ta có công thức chung sau

\[x_{n+1} = x_n - \eta f'(x_n).\]

Trong đó \(\eta\) là một số dương nhỏ, gọi là learning rate (tốc độ học).

Ta chọn \(x_0\) là một điểm bất kì. Tuy nhiên việc chọn \(x_0\) cũng có thể ảnh hưởng đến tốc độ hội tụ.

Ví dụ với hàm số \(f(x) = x^2 + 5 \sin x\). Ta có đạo hàm là \(f'(x) = 2x + 5 \cos x\). Việc giải phương trình đạo hàm bằng \(0\) là điều không dễ dàng. Do đó gradient descent tỏ ra hiệu quả trong trường hợp này.

Chọn \(\eta = 0,1\) và \(x_0 = 5\). Sau đó chọn \(\eta = 0,1\) và \(x_0 = -5\). Ta thấy trường hợp sau tốn ít vòng lặp hơn do \(x_0 = -5\) gần điểm cực trị hơn (\(\approx -1.11\)).

Hàm nhiều biến

Lúc này đầu vào của hàm số là một vector \(\bm{x}\). Đặt \(\nabla f(\bm{x})\) là đạo hàm của hàm \(f\) theo vector \(\bm{x}\). Tương tự, ta xây dựng dãy vector \(\{ \bm{x}_n \}\) hội tụ về cực trị \(\bm{x}^*\). Công thức lúc này là

\[\bm{x}_{n+1} = \bm{x}_n - \eta \cdot \nabla f(\bm{x}_n).\]

Ta đã biết đạo hàm của hàm số theo vector cũng là vector cùng cỡ. Do đó giả sử \(f(\bm{x}) = f(x_1, x_2, \ldots, x_n)\) thì đạo hàm của nó là

\[\nabla f(\bm{x}) = \left( \dfrac{\partial f}{\partial x_1}, \dfrac{\partial f}{\partial x_2}, \ldots, \dfrac{\partial f}{\partial x_n} \right).\]

Với ví dụ là bài toán Linear Regression, lúc này hàm mất mát là

\[\mathcal{L} = \dfrac{1}{2N} \sum_{i=1}^N \lVert y_i - \bm{x}_i \bm{w}^T \rVert^2 = \dfrac{1}{2N} \lVert \bm{y} - \bm{X} \bm{w}^T \rVert^2.\]

Đạo hàm của hàm mất mát là

\[\nabla \mathcal{L} = \dfrac{1}{N} (\bm{w} \bm{X}^T - \bm{y}) \bm{X}.\]

Lúc này, với vector khởi đầu \(\bm{w}_0\) chúng ta xây dựng dãy \(\{ \bm{w}_n \}\) tới khi nhận được \(\bm{w}_n / d < \varepsilon\), với \(d\) là độ dài vector \(\bm{w}\).