11.10. Động lượng

Trong Section 11.8 chúng ta đã thảo luận cách hoạt động của hạ gradient ngẫu nhiên, chỉ sử dụng một mẫu gradient có nhiễu cho việc tối ưu. Cụ thể, khi có nhiễu ta cần cực kỳ cẩn trọng trong việc chọn tốc độ học. Nếu ta giảm tốc độ học quá nhanh, việc hội tụ sẽ ngưng trệ. Nếu tốc độ học giảm chậm, sẽ khó hội tụ tại một kết quả đủ tốt vì nhiễu sẽ đẩy điểm hội tụ ra xa điểm tối ưu.

11.10.1. Kiến thức Cơ bản

Trong phần này, ta sẽ cùng khám phá những thuật toán tối ưu hiệu quả hơn, đặc biệt là cho một số dạng bài toán tối ưu phổ biến trong thực tế.

11.10.1.1. Giá trị Trung bình Rò rỉ

Trong phần trước, ta đã thảo luận về hạ gradient ngẫu nhiên theo minibatch như một cách để tăng tốc độ tính toán. Đồng thời, kỹ thuật này cũng có một tác dụng phụ tốt là giúp giảm phương sai.

(11.10.1)\[\mathbf{g}_{t, t-1} = \partial_{\mathbf{w}} \frac{1}{|\mathcal{B}_t|} \sum_{i \in \mathcal{B}_t} f(\mathbf{x}_{i}, \mathbf{w}_{t-1}) = \frac{1}{|\mathcal{B}_t|} \sum_{i \in \mathcal{B}_t} \mathbf{h}_{i, t-1}.\]

Ở đây để đơn giản kí hiệu, ta đặt \(\mathbf{h}_{i, t-1} = \partial_{\mathbf{w}} f(\mathbf{x}_i, \mathbf{w}_{t-1})\) là gradient của mẫu \(i\) với trọng số tại bước thời gian \(t-1\). Sẽ rất tốt nếu ta có thể tận dụng hơn nữa lợi ích từ việc giảm phương sai, hơn là chỉ lấy trung bình gradient trên minibatch. Một phương pháp để đạt được điều này đó là thay thế việc tính toán gradient bằng một giá trị “trung bình rò rỉ” (leaky average):

(11.10.2)\[\mathbf{v}_t = \beta \mathbf{v}_{t-1} + \mathbf{g}_{t, t-1}\]

với \(\beta \in (0, 1)\). Phương pháp này thay thế gradient tức thời bằng một giá trị được lấy trung bình trên các gradient trước đó. \(\mathbf{v}\) được gọi là động lượng (momentum). Động lượng tích luỹ các gradient trong quá khứ tương tự như cách một quả bóng nặng lăn xuống ngọn đồi sẽ tích hợp hết tất cả các lực tác động lên nó từ lúc bắt đầu. Để hiểu rõ hơn, hãy khai triển đệ quy \(\mathbf{v}_t\) thành

(11.10.3)\[\begin{aligned} \mathbf{v}_t = \beta^2 \mathbf{v}_{t-2} + \beta \mathbf{g}_{t-1, t-2} + \mathbf{g}_{t, t-1} = \ldots, = \sum_{\tau = 0}^{t-1} \beta^{\tau} \mathbf{g}_{t-\tau, t-\tau-1}. \end{aligned}\]

Khi \(\beta\) lớn đồng nghĩa với việc lấy trung bình trong một khoảng rộng, trong khi đó nếu \(\beta\) nhỏ phương pháp này sẽ không khác nhiều so với hạ gradient thông thường. Gradient mới này không còn có hướng đi dốc nhất trong từng trường hợp cụ thể nữa mà thay vào đó đi theo hướng trung bình có trọng số của các gradient trước đó. Điều này giúp chúng ta nhận thêm lợi ích của việc tính trung bình theo batch mà không cần tốn chi phí tính toán gradients trên batch. Chúng ta sẽ xem xét cụ thể hơn quy trình lấy trung bình ở những phần sau.

Các lập luận trên là cơ sở để hình thành các phương pháp tăng tốc gradient, chẳng hạn như gradient với động lượng. Một lợi ích phụ là chúng hiệu quả hơn rất nhiều trong các trường hợp bài toán tối ưu có điều kiện xấu (ví dụ: khi một vài hướng có tiến trình tối ưu chậm hơn nhiều so với các hướng khác, giống như ở trong một hẻm núi hẹp). Hơn nữa, cách này cho phép lấy trung bình các gradient liền kề để đạt được hướng đi xuống ổn định hơn. Thật vậy, việc tăng tốc ngay cả đối với bài toán lồi không nhiễu là một trong những nguyên nhân chính lý giải vì sao động lượng hoạt động và có hiệu quả rất tốt.

Do tính hiệu quả của nó, động lượng là một chủ đề đã được nghiên cứu kỹ trong tối ưu hóa cho học sâu và hơn thế nữa. Bài báo rất đẹp này của [Goh, 2017] cung cấp phân tích chuyên sâu và minh hoạ sinh động về phương pháp động lượng. Động lượng được đề xuất bởi [Polyak, 1964]. [Nesterov, 2018] có một thảo luận chi tiết về lý thuyết động lượng trong ngữ cảnh tối ưu hóa lồi. Động lượng trong học sâu đã được biết đến từ lâu vì lợi ích mà nó mang lại. Tham khảo [Sutskever et al., 2013] để biết thêm chi tiết.

11.10.1.2. Bài toán với Điều kiện Xấu

Để hiểu hơn về các tính chất hình học của phương pháp động lượng, hãy ôn lại thuật toán hạ gradient sử dụng hàm mục tiêu khó chịu hơn. Trong Section 11.7 ta sử dụng hàm mục tiêu dạng elip \(f(\mathbf{x}) = x_1^2 + 2 x_2^2\). Ta sẽ sửa hàm này một chút để kéo dãn thêm theo hướng \(x_1\) như sau:

(11.10.4)\[f(\mathbf{x}) = 0.1 x_1^2 + 2 x_2^2.\]

Cũng như trước, \(f\) đạt cực tiểu tại điểm \((0, 0)\). Hàm này rất phẳng theo hướng \(x_1\). Hãy xem điều gì sẽ xảy ra khi thực hiện hạ gradient tương tự như trước trên hàm mới định nghĩa. Ta đặt tốc độ học bằng \(0.4\).

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

eta = 0.4
def f_2d(x1, x2):
    return 0.1 * x1 ** 2 + 2 * x2 ** 2
def gd_2d(x1, x2, s1, s2):
    return (x1 - eta * 0.2 * x1, x2 - eta * 4 * x2, 0, 0)

d2l.show_trace_2d(f_2d, d2l.train_2d(gd_2d))
../_images/output_momentum_vn_5c39fa_1_0.svg

Có thể thấy gradient theo hướng \(x_2\) có giá trị lớn hơn nhiều và thay đổi nhanh hơn nhiều so với gradient theo hướng ngang \(x_1\). Vì thế, chúng ta bị mắc kẹt giữa hai lựa chọn không mong muốn: Nếu chọn tốc độ học nhỏ, các nghiệm sẽ không phân kỳ theo hướng \(x_2\), nhưng tốc độ hội tụ sẽ chậm theo hướng \(x_1\). Ngược lại, với tốc độ học lớn mô hình sẽ hội tụ nhanh theo hướng \(x_1\) nhưng phân kỳ theo hướng \(x_2\). Ví dụ dưới đây minh họa kết quả khi tăng nhẹ tốc độ học từ \(0.4\) lên \(0.6\). Sự hội tụ theo hướng \(x_1\) được cải thiện nhưng kết quả cuối cùng tệ hơn rất nhiều.

eta = 0.6
d2l.show_trace_2d(f_2d, d2l.train_2d(gd_2d))
../_images/output_momentum_vn_5c39fa_3_0.svg

11.10.1.3. Phương pháp Động lượng

Phương pháp động lượng cho phép chúng ta giải quyết vấn đề với hạ gradient mô tả ở trên. Nhìn vào các vết tối ưu trên, có thể thấy sẽ tốt hơn nếu lấy trung bình gradient trong quá khứ. Ở chiều \(x_1\) các gradient là cùng hướng, cách làm này sẽ đơn thuần lấy tổng độ lớn, từ đó tăng khoảng cách di chuyển ở từng bước. Ngược lại, gradient dao động mạnh theo hướng \(x_2\), do đó kết hợp các gradient sẽ làm giảm kích thước bước do dao động triệt tiêu lẫn nhau. Sử dụng \(\mathbf{v}_t\) thay vì gradient \(\mathbf{g}_t\), ta có các phương trình cập nhật sau:

(11.10.5)\[\begin{split}\begin{aligned} \mathbf{v}_t &\leftarrow \beta \mathbf{v}_{t-1} + \mathbf{g}_{t, t-1}, \\ \mathbf{x}_t &\leftarrow \mathbf{x}_{t-1} - \eta_t \mathbf{v}_t. \end{aligned}\end{split}\]

Với \(\beta = 0\), phương pháp này tương đương với thuật toán hạ gradient thông thường. Trước khi đi sâu hơn vào các tính chất toán học, hãy xem thuật toán này hoạt động như thế nào.

def momentum_2d(x1, x2, v1, v2):
    v1 = beta * v1 + 0.2 * x1
    v2 = beta * v2 + 4 * x2
    return x1 - eta * v1, x2 - eta * v2, v1, v2

eta, beta = 0.6, 0.5
d2l.show_trace_2d(f_2d, d2l.train_2d(momentum_2d))
../_images/output_momentum_vn_5c39fa_5_0.svg

Có thể thấy, ngay cả với tốc độ học như trước, phương pháp động lượng vẫn hội tụ tốt. Giờ hãy xem điều gì xảy ra khi giảm tham số động lượng. Giảm một nửa động lượng \(\beta = 0.25\) dẫn đến một quỹ đạo chưa thật sự hội tụ. Tuy nhiên, kết quả đó vẫn tốt hơn rất nhiều so với khi không sử dụng động lượng (nghiệm phân kỳ).

eta, beta = 0.6, 0.25
d2l.show_trace_2d(f_2d, d2l.train_2d(momentum_2d))
../_images/output_momentum_vn_5c39fa_7_0.svg

Ta cũng có thể kết hợp động lượng với SGD và đặc biệt là SGD theo minibatch. Thay đổi duy nhất trong trường hợp đó là các gradient \(\mathbf{g}_{t, t-1}\) được thay bằng \(\mathbf{g}_t\). Cuối cùng, để thuận tiện ta khởi tạo \(\mathbf{v}_0 = 0\) tại thời điểm \(t=0\). Hãy xem phép trung bình rò rỉ thực sự làm gì khi cập nhật.

11.10.1.4. Trọng số mẫu hiệu dụng

Hãy nhớ lại rằng \(\mathbf{v}_t = \sum_{\tau = 0}^{t-1} \beta^{\tau} \mathbf{g}_{t-\tau, t-\tau-1}\). Tại giới hạn, tổng các số hạng là \(\sum_{\tau=0}^\infty \beta^\tau = \frac{1}{1-\beta}\). Nói cách khác, thay vì kích thước bước \(\eta\) trong GD hoặc SGD, ta thực hiện bước dài hơn \(\frac{\eta}{1-\beta}\), đồng thời hướng giảm gradient nhiều khả năng cũng tốt hơn. Đây là hai lợi ích trong một. Để minh họa ảnh hưởng của trọng số với các giá trị \(\beta\) khác nhau, hãy xem minh họa dưới đây.

d2l.set_figsize()
betas = [0.95, 0.9, 0.6, 0]
for beta in betas:
    x = np.arange(40).asnumpy()
    d2l.plt.plot(x, beta ** x, label=f'beta = {beta:.2f}')
d2l.plt.xlabel('time')
d2l.plt.legend();
../_images/output_momentum_vn_5c39fa_9_0.svg

11.10.2. Thực nghiệm

Hãy xem động lượng hoạt động như thế nào trong thực tế, khi được sử dụng cùng một bộ tối ưu. Để làm điều này, ta cần các đoạn mã dễ mở rộng hơn.

11.10.2.1. Lập trình từ đầu

So với SGD hoặc SGD theo minibatch, phương pháp động lượng cần duy trì các biến phụ trợ, chính là vận tốc. Nó có kích thước giống gradient (và các biến khác trong bài toán tối ưu). Trong đoạn mã bên dưới, ta gọi các biến vận tốc này là states.

def init_momentum_states(feature_dim):
    v_w = np.zeros((feature_dim, 1))
    v_b = np.zeros(1)
    return (v_w, v_b)

def sgd_momentum(params, states, hyperparams):
    for p, v in zip(params, states):
        v[:] = hyperparams['momentum'] * v + p.grad
        p[:] -= hyperparams['lr'] * v

Hãy xem đoạn mã hoạt động như thế nào trong thực tế.

def train_momentum(lr, momentum, num_epochs=2):
    d2l.train_ch11(sgd_momentum, init_momentum_states(feature_dim),
                   {'lr': lr, 'momentum': momentum}, data_iter,
                   feature_dim, num_epochs)

data_iter, feature_dim = d2l.get_data_ch11(batch_size=10)
train_momentum(0.02, 0.5)
loss: 0.244, 0.041 sec/epoch
../_images/output_momentum_vn_5c39fa_13_1.svg

Khi tăng siêu tham số động lượng momentum lên 0.9, kích thước mẫu hiệu dụng sẽ tăng lên đáng kể thành \(\frac{1}{1 - 0.9} = 10\). Ta giảm tốc độ học xuống còn \(0.01\) để kiểm soát vấn đề.

train_momentum(0.01, 0.9)
loss: 0.246, 0.041 sec/epoch
../_images/output_momentum_vn_5c39fa_15_1.svg

Tiếp tục giảm tốc độ học sẽ giải quyết bất kỳ vấn đề tối ưu không trơn tru nào. Giảm còn \(0.005\) đem lại các đặc tính hội tụ tốt.

train_momentum(0.005, 0.9)
loss: 0.242, 0.041 sec/epoch
../_images/output_momentum_vn_5c39fa_17_1.svg

11.10.2.2. Lập trình Súc tích

Rất đơn giản nếu sử dụng Gluon vì bộ tối ưu sgd tiêu chuẩn đã tích hợp sẵn phương pháp động lượng. Với cùng các tham số, ta có quỹ đạo rất giống khi lập trình từ đầu.

d2l.train_concise_ch11('sgd', {'learning_rate': 0.005, 'momentum': 0.9},
                       data_iter)
loss: 0.244, 0.028 sec/epoch
../_images/output_momentum_vn_5c39fa_19_1.svg

11.10.3. Phân tích Lý thuyết

Cho đến nay, ví dụ hai chiều \(f(x) = 0.1 x_1^2 + 2 x_2^2\) dường như không thực tế cho lắm. Thực tế, hàm này khá tiêu biểu cho các dạng bài toán có thể gặp phải, ít nhất trong trường hợp cực tiểu hóa các hàm mục tiêu lồi bậc hai.

11.10.3.1. Hàm lồi bậc Hai

Xét hàm số

(11.10.6)\[h(\mathbf{x}) = \frac{1}{2} \mathbf{x}^\top \mathbf{Q} \mathbf{x} + \mathbf{x}^\top \mathbf{c} + b.\]

Đây là một hàm bậc hai tổng quát. Với ma trận xác định dương \(\mathbf{Q} \succ 0\), tức ma trận có trị riêng dương, hàm có nghiệm cực tiểu tại \(\mathbf{x}^* = -\mathbf{Q}^{-1} \mathbf{c}\) với giá trị cực tiểu \(b - \frac{1}{2} \mathbf{c}^\top \mathbf{Q}^{-1} \mathbf{c}\). Do đó ta có thể viết lại \(h\) như sau

(11.10.7)\[h(\mathbf{x}) = \frac{1}{2} (\mathbf{x} - \mathbf{Q}^{-1} \mathbf{c})^\top \mathbf{Q} (\mathbf{x} - \mathbf{Q}^{-1} \mathbf{c}) + b - \frac{1}{2} \mathbf{c}^\top \mathbf{Q}^{-1} \mathbf{c}.\]

Gradient được tính bởi \(\partial_{\mathbf{x}} f(\mathbf{x}) = \mathbf{Q} (\mathbf{x} - \mathbf{Q}^{-1} \mathbf{c})\). Nghĩa là bằng khoảng cách giữa \(\mathbf{x}\) và nghiệm cực tiểu nhân với \(\mathbf{Q}\). Do đó, động lượng cũng là tổ hợp tuyến tính của \(\mathbf{Q} (\mathbf{x}_t - \mathbf{Q}^{-1} \mathbf{c})\).

\(\mathbf{Q}\) là xác định dương nên nó có thể được phân tích thành hệ riêng thông qua \(\mathbf{Q} = \mathbf{O}^\top \boldsymbol{\Lambda} \mathbf{O}\), với \(\mathbf{O}\) là ma trận trực giao (xoay vòng) và \(\boldsymbol{\Lambda}\) là ma trận đường chéo của các trị riêng dương. Điều này cho phép ta đổi biến \(\mathbf{x}\) thành \(\mathbf{z} := \mathbf{O} (\mathbf{x} - \mathbf{Q}^{-1} \mathbf{c})\) để có biểu thức đơn giản hơn nhiều:

(11.10.8)\[h(\mathbf{z}) = \frac{1}{2} \mathbf{z}^\top \boldsymbol{\Lambda} \mathbf{z} + b'.\]

Ở đây \(c' = b - \frac{1}{2} \mathbf{c}^\top \mathbf{Q}^{-1} \mathbf{c}\). Vì \(\mathbf{O}\) chỉ là một ma trận trực giao nên điều này không làm nhiễu các gradient một cách có ý nghĩa. Biểu diễn theo \(\mathbf{z}\), ta có hạ gradient

(11.10.9)\[\mathbf{z}_t = \mathbf{z}_{t-1} - \boldsymbol{\Lambda} \mathbf{z}_{t-1} = (\mathbf{I} - \boldsymbol{\Lambda}) \mathbf{z}_{t-1}.\]

Một điểm quan trọng trong biểu thức này là hạ gradient không trộn lẫn các không gian riêng khác nhau. Nghĩa là, khi được biểu diễn dưới dạng hệ riêng của \(\mathbf{Q}\), việc tối ưu được thực hiện theo từng trục tọa độ. Điều này cũng đúng với phương pháp động lượng.

(11.10.10)\[\begin{split}\begin{aligned} \mathbf{v}_t & = \beta \mathbf{v}_{t-1} + \boldsymbol{\Lambda} \mathbf{z}_{t-1} \\ \mathbf{z}_t & = \mathbf{z}_{t-1} - \eta \left(\beta \mathbf{v}_{t-1} + \boldsymbol{\Lambda} \mathbf{z}_{t-1}\right) \\ & = (\mathbf{I} - \eta \boldsymbol{\Lambda}) \mathbf{z}_{t-1} - \eta \beta \mathbf{v}_{t-1}. \end{aligned}\end{split}\]

Khi thực hiện điều này, ta đã chứng minh định lý sau: Hạ Gradient có và không có động lượng cho hàm lồi bậc hai có thể được phân tích thành bài toán tối ưu theo hướng các vector riêng của ma trận bậc hai theo từng trục tọa độ.

11.10.3.2. Hàm vô hướng

Với kết quả trên hãy xem điều gì xảy ra khi cực tiểu hóa hàm \(f(x) = \frac{\lambda}{2} x^2\). Ta có hạ gradient

(11.10.11)\[x_{t+1} = x_t - \eta \lambda x_t = (1 - \eta \lambda) x_t.\]

Với \(|1 - \eta \lambda| < 1\), sau \(t\) bước ta có \(x_t = (1 - \eta \lambda)^t x_0\), do đó tốc độ hội tụ sẽ theo hàm mũ. Tốc độ hội tụ sẽ tăng khi tăng tốc độ học \(\eta\) cho đến khi \(\eta \lambda = 1\). Khi \(\eta \lambda > 2\), bài toán tối ưu sẽ phân kỳ.

lambdas = [0.1, 1, 10, 19]
eta = 0.1
d2l.set_figsize((6, 4))
for lam in lambdas:
    t = np.arange(20).asnumpy()
    d2l.plt.plot(t, (1 - eta * lam) ** t, label=f'lambda = {lam:.2f}')
d2l.plt.xlabel('time')
d2l.plt.legend();
../_images/output_momentum_vn_5c39fa_21_0.svg

Để phân tích tính hội tụ khi sử dụng động lượng, ta viết lại các phương trình cập nhật theo hai số vô hướng: \(x\) và động lượng \(v\). Ta có:

(11.10.12)\[\begin{split}\begin{bmatrix} v_{t+1} \\ x_{t+1} \end{bmatrix} = \begin{bmatrix} \beta & \lambda \\ -\eta \beta & (1 - \eta \lambda) \end{bmatrix} \begin{bmatrix} v_{t} \\ x_{t} \end{bmatrix} = \mathbf{R}(\beta, \eta, \lambda) \begin{bmatrix} v_{t} \\ x_{t} \end{bmatrix}.\end{split}\]

Ta kí hiệu \(\mathbf{R}\) là ma trận chi phối hội tụ, kích thước \(2 \times 2\). Sau \(t\) bước thì giá trị ban đầu \([v_0, x_0]\) sẽ là \(\mathbf{R}(\ beta, \eta, \lambda)^t [v_0, x_0]\). Do đó, các trị riêng của \(\mathbf{R}\) sẽ quyết định tốc độ hội tụ. Độc giả có thể xem hình ảnh động tại bài viết của Distill của [Goh, 2017] và đọc thêm [Flammarion & Bach, 2015] để biết phân tích chi tiết. Có thể chỉ ra rằng phương pháp động lượng hội tụ với \(0 < \eta \lambda < 2 + 2 \beta\), có khoảng tham số khả thi lớn hơn khoảng \(0 < \eta \lambda <2\) của hạ gradient. Điều này cũng gợi ý rằng nhìn chung ta mong muốn \(\beta\) có giá trị lớn. Chi tiết kỹ thuật đòi hỏi nền tảng kiến thức sâu hơn, bạn đọc quan tâm có thể tham khảo các bài báo gốc.

11.10.4. Tóm tắt

  • Phương pháp động lượng thay thế gradient bằng trung bình rò rỉ của các gradient trong quá khứ, giúp tăng tốc độ hội tụ đáng kể.
  • Phương pháp này có thể sử dụng cho cả hạ gradient không nhiễu và hạ gradient ngẫu nhiên (có nhiễu).
  • Phương pháp động lượng giúp tránh việc tối ưu bị ngưng trệ, điều nhiều khả năng xảy ra đối với hạ gradient ngẫu nhiên.
  • Số lượng gradient hiệu dụng là \(\frac{1}{1-\beta}\), được tính bằng giới hạn của tổng cấp số nhân.
  • Trong trường hợp các bài toán lồi bậc hai, hạ gradient (có và không có động lượng) có thể được phân tích chi tiết một cách tường minh.
  • Việc lập trình khá đơn giản nhưng cần lưu trữ thêm một vector trạng thái (động lượng \(\mathbf{v}\)).

11.10.5. Bài tập

  1. Quan sát và phân tích kết quả khi sử dụng các tổ hợp động lượng và tốc độ học khác nhau.
  2. Hãy thử dùng hạ gradient có động lượng cho bài toán bậc hai có nhiều trị riêng, ví dụ: \(f(x) = \frac{1}{2} \sum_i \lambda_i x_i^2\), e.g., \(\lambda_i = 2^{-i}\). Vẽ đồ thị biểu diễn sự giảm của \(x\) khi khởi tạo \(x_i = 1\).
  3. Tính giá trị và nghiệm cực tiểu của \(h(\mathbf{x}) = \frac{1}{2} \mathbf{x}^\top \mathbf{Q} \mathbf{x} + \mathbf{x}^\top \mathbf{c} + b\).
  4. Điều gì thay đổi khi ta thực hiện SGD và SGD theo minibatch có động lượng? Thử nghiệm với các tham số.

11.10.6. Thảo luận

11.10.7. 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 Thanh Hòa
  • Nguyễn Văn Quang
  • Trần Yến Thy
  • Lê Khắc Hồng Phúc
  • Phạm Minh Đức
  • Phạm Hồng Vinh
  • Nguyễn Văn Cường