gd_vn.md

Hạ Gradient

🏷️sec_gd

Trong phần này chúng tôi sẽ giới thiệu các khái niệm cơ bản trong thuật toán hạ gradient. Nội dung cần thiết sẽ được trình bày ngắn gọn. Độc giả có thể tham khảo :cite:Boyd.Vandenberghe.2004 để có góc nhìn sâu về bài toán tối ưu lồi. Mặc dù tối ưu lồi hiếm khi được áp dụng trực tiếp trong học sâu, kiến thức về thuật toán hạ gradient là chìa khóa để hiểu rõ hơn về thuật toán hạ gradient ngẫu nhiên. Ví dụ, bài toán tối ưu có thể phân kỳ do tốc độ học quá lớn. Hiện tượng này có thể quan sát được trong thuật toán hạ gradient. Tương tự, tiền điều kiện (preconditioning) là một kỹ thuật phổ biến trong thuật toán hạ gradient và nó cũng được áp dụng trong các thuật toán tân tiến hơn. Hãy bắt đầu với một trường hợp đặc biệt và đơn giản.

Hạ Gradient trong Một Chiều

Hạ gradient trong một chiều là ví dụ tuyệt vời để giải thích tại sao thuật toán hạ gradient có thể giảm giá trị hàm mục tiêu. Hãy xem xét một hàm số thực khả vi liên tục $f: \mathbb{R} \rightarrow \mathbb{R}$. Áp dụng khai triển Taylor (:numref:sec_single_variable_calculus), ta có

$$f(x + \epsilon) = f(x) + \epsilon f'(x) + \mathcal{O}(\epsilon^2).$$ :eqlabel:gd-taylor

Trong đó xấp xỉ bậc nhất $f(x+\epsilon)$ được tính bằng giá trị hàm $f(x)$ và đạo hàm bậc nhất $f'(x)$ tại $x$. Có lý khi giả sử rằng di chuyển theo hướng ngược chiều gradient với $\epsilon$ nhỏ sẽ làm suy giảm giá trị $f$. Để đơn giản hóa vấn đề, ta cố định sải bước cập nhật (tốc độ học) $\eta > 0$ và chọn $\epsilon = -\eta f'(x)$. Thay biểu thức này vào khai triển Taylor ở trên, ta thu được

$$f(x - \eta f'(x)) = f(x) - \eta f'^2(x) + \mathcal{O}(\eta^2 f'^2(x)).$$

Nếu đạo hàm $f'(x) \neq 0$ không tiêu biến, quá trình tối ưu sẽ có tiến triển do $\eta f'^2(x)>0$.
Hơn nữa, chúng ta luôn có thể chọn $\eta$ đủ nhỏ để loại bỏ các hạng tử bậc cao hơn trong phép cập nhật. Do đó, ta có

$$f(x - \eta f'(x)) \lessapprox f(x).$$

Điều này có nghĩa là, nếu chúng ta áp dụng

$$x \leftarrow x - \eta f'(x)$$

để cập nhật $x$, giá trị của hàm $f(x)$ có thể giảm. Do đó, trong thuật toán hạ gradient, đầu tiên chúng ta chọn giá trị khởi tạo cho $x$ và hằng số $\eta > 0$, từ đó cập nhật giá trị $x$ liên tục cho tới khi thỏa mãn điều kiện dừng, ví dụ như khi độ lớn của gradient $|f'(x)|$ đủ nhỏ hoặc số lần cập nhật đạt một ngưỡng nhất định.

Để đơn giản hóa vấn đề, chúng ta chọn hàm mục tiêu $f(x)=x^2$ để minh họa cách lập trình thuật toán hạ gradient. Ta sử dụng ví dụ đơn giản này để quan sát cách mà $x$ thay đổi, dù đã biết rằng $x=0$ là nghiệm để cực tiểu hóa $f(x)$. Như mọi khi, chúng ta bắt đầu bằng cách nhập tất cả các mô-đun cần thiết.

%matplotlib inline
from d2l import mxnet as d2l
from mxnet import np, npx
npx.set_np()

#@tab all
f = lambda x: x**2  # Objective function
gradf = lambda x: 2 * x  # Its derivative

Tiếp theo, chúng ta sử dụng $x=10$ làm giá trị khởi tạo và chọn $\eta=0.2$. Áp dụng thuật toán hạ gradient để cập nhật $x$ trong 10 vòng lặp, chúng ta có thể thấy cuối cùng giá trị của $x$ cũng tiệm cận nghiệm tối ưu.

#@tab all
def gd(eta):
    x = 10.0
    results = [x]
    for i in range(10):
        x -= eta * gradf(x)
        results.append(float(x))
    print('epoch 10, x:', x)
    return results
res = gd(0.2)

Đồ thị quá trình tối ưu hóa theo $x$ được vẽ như sau.

#@tab all
def show_trace(res):
    n = max(abs(min(res)), abs(max(res)))
    f_line = d2l.arange(-n, n, 0.01)
    d2l.set_figsize()
    d2l.plot([f_line, res], [[f(x) for x in f_line], [f(x) for x in res]],
             'x', 'f(x)', fmts=['-', '-o'])

show_trace(res)

Tốc độ học

🏷️section_gd-learningrate

Tốc độ học $\eta$ có thể được thiết lập khi thiết kế thuật toán. Nếu ta sử dụng tốc độ học quá nhỏ thì $x$ sẽ được cập nhật rất chậm, đòi hỏi số bước cập nhật nhiều hơn để thu được nghiệm tốt hơn. Để minh họa, hãy xem xét quá trình học trong cùng bài toán tối ưu ở phía trên với $\eta = 0.05$. Như chúng ta có thể thấy, ngay cả sau 10 bước cập nhật, chúng ta vẫn còn ở rất xa nghiệm tối ưu.

#@tab all
show_trace(gd(0.05))

Ngược lại, nếu ta sử dụng tốc độ học quá cao, giá trị $\left|\eta f'(x)\right|$ có thể rất lớn trong khai triển Taylor bậc nhất. Cụ thể, hạng tử $\mathcal{O}(\eta^2 f'^2(x))$ trong :eqref: gd-taylor sẽ có thể có giá trị lớn. Trong trường hợp này, ta không thể đảm bảo rằng việc cập nhật $x$ sẽ có thể làm suy giảm giá trị của $f(x)$. Ví dụ, khi chúng ta thiết lập tốc độ học $\eta=1.1$, $x$ sẽ lệch rất xa so với nghiệm tối ưu $x=0$ và dần dần phân kỳ.

#@tab all
show_trace(gd(1.1))

Cực Tiểu

Để minh họa quá trình học các hàm không lồi, ta xem xét trường hợp $f(x) = x \cdot \cos c x$. Hàm này có vô số cực tiểu. Tùy thuộc vào tốc độ học được chọn và điều kiện của bài toán, chúng ta có thể thu được một trong số rất nhiều nghiệm. Ví dụ dưới đây minh họa việc thiết lập tốc độ học quá cao (không thực tế) sẽ dẫn đến điểm cực tiểu không tốt.

#@tab all
c = d2l.tensor(0.15 * np.pi)
f = lambda x: x * d2l.cos(c * x)
gradf = lambda x: d2l.cos(c * x) - c * x * d2l.sin(c * x)
show_trace(gd(2))

Hạ Gradient Đa biến

Bây giờ chúng ta đã có trực quan tốt hơn về trường hợp đơn biến, ta hãy xem xét trường hợp trong đó $\mathbf{x} \in \mathbb{R}^d$. Cụ thể, hàm mục tiêu $f: \mathbb{R}^d \to \mathbb{R}$ ánh xạ các vector tới các giá trị vô hướng. Gradient tương ứng cũng là đa biến, là một vector gồm $d$ đạo hàm riêng:

$$\nabla f(\mathbf{x}) = \bigg[\frac{\partial f(\mathbf{x})}{\partial x_1}, \frac{\partial f(\mathbf{x})}{\partial x_2}, \ldots, \frac{\partial f(\mathbf{x})}{\partial x_d}\bigg]^\top.$$

Mỗi đạo hàm riêng $\partial f(\mathbf{x})/\partial x_i$ trong gradient biểu diễn tốc độ thay đổi theo $x_i$ của $f$ tại $\mathbf{x}$. Như trong trường hợp đơn biến giới thiệu ở phần trước, ta sử dụng khai triển Taylor tương ứng cho các hàm đa biến. Cụ thể, ta có

$$f(\mathbf{x} + \mathbf{\epsilon}) = f(\mathbf{x}) + \mathbf{\epsilon}^\top \nabla f(\mathbf{x}) + \mathcal{O}(|\mathbf{\epsilon}|^2).$$ :eqlabel:gd-multi-taylor

Nói cách khác, chiều giảm mạnh nhất được cho bởi gradient âm $-\nabla f(\mathbf{x})$, các hạng tử từ bậc hai trở lên trong $\mathbf{\epsilon}$ có thể bỏ qua. Chọn một tốc độ học phù hợp $\eta > 0$, ta được thuật toán hạ gradient nguyên bản dưới đây:

$$\mathbf{x} \leftarrow \mathbf{x} - \eta \nabla f(\mathbf{x}).$$

Để xem thuật toán hoạt động như thế nào trong thực tế, ta hãy xây dựng một hàm mục tiêu $f(\mathbf{x})=x_1^2+2x_2^2$ với đầu vào là vector hai chiều $\mathbf{x} = [x_1, x_2]^\top$ và đầu ra là một số vô hướng. Gradient được cho bởi $\nabla f(\mathbf{x}) = [2x_1, 4x_2]^\top$. Ta sẽ quan sát đường đi của $\mathbf{x}$ được sinh bởi thuật toán hạ gradient bắt đầu từ vị trí $[-5, -2]$. Chúng ta cần thêm hai hàm hỗ trợ. Hàm đầu tiên là hàm cập nhật và được sử dụng $20$ lần cho giá trị khởi tạo ban đầu. Hàm thứ hai là hàm vẽ biểu đồ đường đi của $\mathbf{x}$.

#@tab all
def train_2d(trainer, steps=20):  #@save
    """Optimize a 2-dim objective function with a customized trainer."""
    # s1 and s2 are internal state variables and will
    # be used later in the chapter
    x1, x2, s1, s2 = -5, -2, 0, 0
    results = [(x1, x2)]
    for i in range(steps):
        x1, x2, s1, s2 = trainer(x1, x2, s1, s2)
        results.append((x1, x2))
    return results

def show_trace_2d(f, results):  #@save
    """Show the trace of 2D variables during optimization."""
    d2l.set_figsize()
    d2l.plt.plot(*zip(*results), '-o', color='#ff7f0e')
    x1, x2 = d2l.meshgrid(d2l.arange(-5.5, 1.0, 0.1),
                          d2l.arange(-3.0, 1.0, 0.1))
    d2l.plt.contour(x1, x2, f(x1, x2), colors='#1f77b4')
    d2l.plt.xlabel('x1')
    d2l.plt.ylabel('x2')

Tiếp theo, chúng ta sẽ quan sát quỹ đạo của biến tối ưu hóa $\mathbf{x}$ với tốc độ học $\eta = 0.1$. Chúng ta có thể thấy rằng sau 20 bước, giá trị $\mathbf{x}$ đã đạt cực tiểu tại $[0, 0]$. Quá trình khá tốt mặc dù hơi chậm.

#@tab all
f = lambda x1, x2: x1 ** 2 + 2 * x2 ** 2  # Objective
gradf = lambda x1, x2: (2 * x1, 4 * x2)  # Gradient

def gd(x1, x2, s1, s2):
    (g1, g2) = gradf(x1, x2)  # Compute gradient
    return (x1 - eta * g1, x2 - eta * g2, 0, 0)  # Update variables

eta = 0.1
show_trace_2d(f, train_2d(gd))

Những Phương pháp Thích nghi

Như chúng ta có thể thấy ở :numref:section_gd-learningrate, chọn tốc độ học $\eta$ "vừa đủ" rất khó. Nếu chọn giá trị quá nhỏ, ta sẽ không có tiến triển. Nếu chọn giá trị quá lớn, nghiệm sẽ dao động và trong trường hợp tệ nhất, thậm chí sẽ phân kỳ. Sẽ ra sao nếu chúng ta có thể chọn $\eta$ một cách tự động, hoặc giả như loại bỏ được việc chọn kích thước bước? Các phương pháp bậc hai không chỉ dựa vào giá trị và gradient của hàm mục tiêu mà còn dựa vào "độ cong" của hàm, từ đó có thể điều chỉnh tốc độ học. Dù những phương pháp này không thể áp dụng vào học sâu một cách trực tiếp do chi phí tính toán lớn, chúng đem đến những gợi ý hữu ích để thiết kế các thuật toán tối ưu cao cấp hơn, mang nhiều tính chất mong muốn dựa trên các thuật toán dưới đây.

Phương pháp Newton

Trong khai triển Taylor của $f$, ta không cần phải dừng ngay sau số hạng đầu tiên. Trên thực tế, ta có thể viết lại như sau

$$f(\mathbf{x} + \mathbf{\epsilon}) = f(\mathbf{x}) + \mathbf{\epsilon}^\top \nabla f(\mathbf{x}) + \frac{1}{2} \mathbf{\epsilon}^\top \nabla \nabla^\top f(\mathbf{x}) \mathbf{\epsilon} + \mathcal{O}(|\mathbf{\epsilon}|^3).$$ :eqlabel:gd-hot-taylor

Để tránh việc kí hiệu quá nhiều, ta định nghĩa $H_f := \nabla \nabla^\top f(\mathbf{x})$ là ma trận Hessian của $f$. Đây là ma trận kích thước $d \times d$. Với $d$ nhỏ và trong các bài toán đơn giản, ta sẽ dễ tính được $H_f$. Nhưng với các mạng sâu, kích thước của $H_f$ có thể cực lớn, do chi phí lưu trữ bậc hai $\mathcal{O}(d^2)$. Hơn nữa việc tính toán lan truyền ngược có thể đòi hỏi rất nhiều chi phí tính toán. Tạm thời hãy bỏ qua những lưu ý đó và nhìn vào thuật toán mà ta có được.

Suy cho cùng, cực tiểu của $f$ sẽ thỏa $\nabla f(\mathbf{x}) = 0$. Lấy các đạo hàm của :eqref:gd-hot-taylor theo $\mathbf{\epsilon}$ và bỏ qua các số hạng bậc cao ta thu được

$$\nabla f(\mathbf{x}) + H_f \mathbf{\epsilon} = 0 \text{ vàdođó } \mathbf{\epsilon} = -H_f^{-1} \nabla f(\mathbf{x}).$$

Nghĩa là, ta cần phải nghịch đảo ma trận Hessian $H_f$ như một phần của bài toán tối ưu hóa.

Với $f(x) = \frac{1}{2} x^2$ ta có $\nabla f(x) = x$ và $H_f = 1$. Do đó với $x$ bất kỳ, ta đều thu được $\epsilon = -x$. Nói cách khác, một bước đơn lẻ là đã đủ để hội tụ một cách hoàn hảo mà không cần bất kỳ tinh chỉnh nào! Chúng ta khá may mắn ở đây vì khai triển Taylor không cần xấp xỉ. Hãy xem thử điều gì sẽ xảy ra với các bài toán khác.

#@tab all
c = d2l.tensor(0.5)
f = lambda x: d2l.cosh(c * x)  # Objective
gradf = lambda x: c * d2l.sinh(c * x)  # Derivative
hessf = lambda x: c**2 * d2l.cosh(c * x)  # Hessian

def newton(eta=1):
    x = 10.0
    results = [x]
    for i in range(10):
        x -= eta * gradf(x) / hessf(x)
        results.append(float(x))
    print('epoch 10, x:', x)
    return results
show_trace(newton())

Giờ hãy xem điều gì xảy ra với một hàm không lồi, ví dụ như $f(x) = x \cos(c x)$. Sau tất cả, hãy lưu ý rằng trong phương pháp Newton, chúng ta cuối cùng sẽ phải chia cho ma trận Hessian. Điều này nghĩa là nếu đạo hàm bậc hai là âm thì chúng ta phải đi theo hướng tăng $f$. Đó là khiếm khuyết chết người của thuật toán này. Hãy xem điều gì sẽ xảy ra trong thực tế.

#@tab all
c = d2l.tensor(0.15 * np.pi)
f = lambda x: x * d2l.cos(c * x)
gradf = lambda x: d2l.cos(c * x) - c * x * d2l.sin(c * x)
hessf = lambda x: - 2 * c * d2l.sin(c * x) - x * c**2 * d2l.cos(c * x)

show_trace(newton())

Kết quả trả về là cực kỳ sai. Có một cách khắc phục là "sửa" ma trận Hessian bằng cách lấy giá trị tuyệt đối của nó. Một chiến lược khác là đưa tốc độ học trở lại. Điều này có vẻ sẽ phá hỏng mục tiêu ban đầu nhưng không hẳn. Có được thông tin bậc hai sẽ cho phép chúng ta thận trọng bất cứ khi nào độ cong trở nên lớn và cho phép thực hiện các bước dài hơn mỗi khi hàm mục tiêu phẳng. Hãy xem nó hoạt động như thế nào với một tốc độ học khá nhỏ, $\eta = 0.5$ chẳng hạn. Như ta có thể thấy, chúng ta có một thuật toán khá hiệu quả.

#@tab all
show_trace(newton(0.5))

Phân tích Hội tụ

Chúng ta sẽ chỉ phân tích tốc độ hội tụ đối với hàm $f$ lồi và khả vi ba lần, đây là hàm số có đạo hàm bậc hai tại cực tiểu $x^$ khác không ($f''(x^) > 0$).

Đặt $x_k$ là giá trị của $x$ tại vòng lặp thứ $k$ và $e_k := x_k - x^$ là khoảng cách đến điểm tối ưu. Theo khai triển Taylor, điều kiện $f'(x^) = 0$ được viết lại thành

$$0 = f'(x_k - e_k) = f'(x_k) - e_k f''(x_k) + \frac{1}{2} e_k^2 f'''(\xi_k).$$

Điều này đúng với một vài $\xi_k \in [x_k - e_k, x_k]$. Hãy nhớ rằng chúng ta có công thức cập nhật $x_{k+1} = x_k - f'(x_k) / f''(x_k)$. Chia khai triển Taylor ở trên cho $f''(x_k)$, ta thu được

$$e_k - f'(x_k) / f''(x_k) = \frac{1}{2} e_k^2 f'''(\xi_k) / f''(x_k).$$

Thay vào phương trình cập nhật sẽ dẫn đến ràng buộc $e_{k+1} \leq e_k^2 f'''(\xi_k) / f'(x_k)$. Do đó, khi nằm trong miền ràng buộc $f'''(\xi_k) / f''(x_k) \leq c$, ta sẽ có sai số giảm theo bình phương $e_{k+1} \leq c e_k^2$.

Bên cạnh đó, các nhà nghiên cứu tối ưu hóa gọi đây là hội tụ tuyến tính, còn điều kiện $e_{k+1} \leq \alpha e_k$ được gọi là tốc độ hội tụ không đổi. Lưu ý rằng phân tích này đi kèm với một số lưu ý: Chúng ta không thực sự biết rằng khi nào mình sẽ tiến tới được vùng hội tụ nhanh. Thay vào đó, ta chỉ biết rằng một khi đến được đó, việc hội tụ sẽ xảy ra rất nhanh chóng. Thêm nữa, điều này yêu cầu $f$ được xử lý tốt ở các đạo hàm bậc cao. Nó đảm bảo không có bất cứ một tính chất "bất ngờ" nào của $f$ có thể dẫn đến sự thay đổi giá trị của nó.

Tiền Điều kiện

Không có gì ngạc nhiên khi việc tính toán và lưu trữ toàn bộ ma trận Hessian là rất tốn kém. Do đó ta cần tìm kiếm một phương pháp thay thế. Một cách để cải thiện vấn đề này là tránh tính toán toàn bộ ma trận Hessian, chỉ tính toán các giá trị thuộc đường chéo. Mặc dù cách trên không tốt bằng phương pháp Newton hoàn chỉnh nhưng vẫn tốt hơn nhiều so với không sử dụng nó. Hơn nữa, ước lượng các giá trị đường chéo chính là thứ thúc đẩy sự đổi mới trong các thuật toán tối ưu hóa hạ gradient ngẫu nhiên. Thuật toán cập nhật sẽ có dạng

$$\mathbf{x} \leftarrow \mathbf{x} - \eta \mathrm{diag}(H_f)^{-1} \nabla \mathbf{x}.$$

Để thấy tại sao điều này có thể là một ý tưởng tốt, ta ví dụ có hai biến số biểu thị chiều cao, một biến với đơn vị mm, biến còn lại với đơn vị km. Với cả hai đơn vị đo, khi quy đổi ra mét, chúng ta đều có sự sai lệch lớn trong việc tham số hóa. Sử dụng tiền điều kiện sẽ loại bỏ vấn đề này. Tiền điều kiện một cách hiệu quả cùng hạ gradient giúp chọn ra các tốc độ học khác nhau cho từng trục tọa độ.

Hạ gradient cùng Tìm kiếm Đường thẳng

Một trong những vấn đề chính của hạ gradient là chúng ta có thể vượt quá khỏi mục tiêu hoặc không đạt đủ sự tiến bộ. Có một cách khắc phục đơn giản cho vấn đề này là sử dụng tìm kiếm đường thẳng (line search) kết hợp với hạ gradient.
Chúng ta sử dụng hướng được cho bởi $\nabla f(\mathbf{x})$ và sau đó dùng tìm kiếm nhị phân để tìm ra độ dài bước $\eta$ có thể cực tiểu hóa $f(\mathbf{x} - \eta \nabla f(\mathbf{x}))$.

Thuật toán này sẽ hội tụ nhanh chóng (xem phân tích và chứng minh ở :cite:Boyd.Vandenberghe.2004). Tuy nhiên, đối với mục đích của học sâu thì nó không thực sự khả thi, lý do là mỗi bước của tìm kiếm đường thẳng sẽ yêu cầu chúng ta ước lượng hàm mục tiêu trên toàn bộ tập dữ liệu. Điều này quá tốn kém để có thể thực hiện.

Tổng kết

• Tốc độ học rất quan trọng. Quá lớn sẽ khiến việc tối ưu hóa phân kỳ, quá nhỏ sẽ không thu được sự tiến bộ nào.
• Hạ gradient có thể bị kẹt tại cực tiểu cục bộ.
• Trong bài toán nhiều chiều, tinh chỉnh việc học tốc độ học sẽ phức tạp.
• Tiền điều kiện có thể giúp trong việc tinh chỉnh thang đo.
• Phương pháp Newton nhanh hơn rất nhiều một khi hoạt động trên bài toán lồi phù hợp.
• Hãy cẩn trọng trong việc dùng phương pháp Newton cho các bài toán không lồi mà không tinh chỉnh.

Bài tập

1. Hãy thử các tốc độ học, hàm mục tiêu khác nhau cho hạ gradient.
2. Khởi tạo tìm kiếm đường thẳng để cực tiểu hóa hàm lồi trong khoảng $[a, b]$.
   • Bạn có cần đạo hàm để tìm kiếm nhị phân không, ví dụ, để quyết định xem sẽ chọn $[a, (a+b)/2]$ hay $[(a+b)/2, b]$?
   • Tốc độ hội tụ của thuật toán nhanh chậm thế nào?
   • Hãy khởi tạo thuật toán và áp dụng nó để cực tiểu hóa $\log (\exp(x) + \exp(-2*x -3))$.
3. Thiết kế một hàm mục tiêu thuộc $\mathbb{R}^2$ mà việc hạ gradient rất chậm. Gợi ý: sử dụng trục tọa độ có thang đo khác nhau.
4. Khởi tạo một phiên bản nhỏ gọn của phương pháp Newton sử dụng tiền điều kiện:
   • Dùng ma trận đường chéo Hessian làm tiền điều kiện.
   • Sử dụng các giá trị tuyệt đối của nó thay vì các giá trị có dấu.
   • Áp dụng điều này cho bài toán phía trên.
5. Áp dụng thuật toán phía trên cho các hàm mục tiêu (lồi lẫn không lồi). Điều gì sẽ xảy ra nếu xoay các trục tọa độ một góc $45$ độ?

Thảo luận

• Tiếng Anh - MXNet
• Tiếng Anh - Pytorch
• Tiếng Việt

Những người thực hiện

Bản dịch trong trang này được thực hiện bởi:

• Đoàn Võ Duy Thanh
• Nguyễn Văn Quang
• Nguyễn Lê Quang Nhật
• Nguyễn Văn Quang
• Nguyễn Văn Cường
• Phạm Hồng Vinh
• Phạm Minh Đức
• Nguyễn Thanh Hòa
• Võ Tấn Phát