Vì Sao Momentum Thực Sự Hiệu Quả

Ta thường nghĩ momentum chỉ làm giảm dao động và tăng tốc hội tụ. Nhưng trên mô hình bậc hai, nó còn mở rộng miền cỡ bước, tự tạo dao động, và chạm tới những giới hạn sâu của tối ưu hóa bậc nhất.

Momentum β = 0.99

Cỡ bước α = 0.02

Vì Sao Momentum Thực Sự Hiệu Quả

Ta thường nghĩ momentum chỉ làm giảm dao động và tăng tốc hội tụ. Nhưng trên mô hình bậc hai, nó còn mở rộng miền cỡ bước, tự tạo dao động, và chạm tới những giới hạn sâu của tối ưu hóa bậc nhất.

Momentum β = 0.99

Cỡ bước α = 0.02

Một câu chuyện quen thuộc về momentum là thế này: gradient descent giống một người đi bộ xuống dốc, luôn chọn hướng dốc nhất nên tiến đều nhưng chậm. Momentum giống một quả bóng nặng lăn xuống cùng sườn đồi; quán tính làm đường đi mượt hơn, giúp nó băng qua các thung lũng hẹp, gờ nhỏ và vài cực tiểu cục bộ.

Trực giác đó không sai, nhưng nó bỏ sót nhiều hiện tượng quan trọng. Momentum không chỉ “làm mượt dao động”. Nếu nhìn nó qua một mô hình phù hợp, ta có thể mô tả chính xác tốc độ hội tụ, miền ổn định và cách các dao động tự sinh ra.

Mô hình phù hợp nhất để bắt đầu là hàm bậc hai lồi. Nó đủ đơn giản để giải bằng công thức đóng, nhưng vẫn đủ giàu để tái hiện động lực cục bộ của nhiều bài toán tối ưu thực tế. Sự cân bằng này cho ta một kính hiển vi tốt để quan sát thuật toán.

Trước hết hãy xét gradient descent. Thuật toán rất đơn giản: khi tối ưu một hàm trơn, ta bước một bước nhỏ theo hướng ngược gradient.

Nếu cỡ bước đủ nhỏ, mỗi vòng lặp đều cải thiện giá trị mục tiêu và cuối cùng hội tụ về một cực tiểu cục bộ. Với vài giả thiết yếu về độ cong, tốc độ hội tụ còn có dạng mũ.

Nhưng tốc độ mũ trên giấy có thể rất chậm trong thực hành. Ban đầu loss giảm nhanh, rồi càng về sau càng ì ạch. Cảm giác quen thuộc là mô hình vẫn đang học, nhưng không còn tiến triển đáng kể.

Thủ phạm thường là độ cong bệnh lý. Một số hướng trong không gian tham số dốc và hẹp, trong khi các hướng khác phẳng và dài. Gradient descent khi đó hoặc bật qua lại giữa hai vách, hoặc bò từng bước nhỏ về nghiệm.

Momentum thay đổi gradient descent bằng cách thêm một bộ nhớ ngắn hạn. Thay vì chỉ dùng gradient hiện tại, ta tích lũy một vận tốc đã được làm suy giảm rồi cập nhật tham số theo vận tốc đó.

Khi hệ số momentum bằng 0, ta quay lại gradient descent. Khi hệ số này gần 1, các bước lặp thường lấy lại được tốc độ và sự quả quyết đã mất trong các thung lũng hẹp.

Các nhà tối ưu hóa gọi hiện tượng này là tăng tốc.

Bước Đầu: Gradient Descent

Thoạt nhìn, momentum có vẻ chỉ là một mẹo kỹ thuật để né những hành vi khó chịu của gradient descent. Thực ra ngược lại: gradient descent mới là trường hợp thô sơ. Trên nhiều lớp hàm, momentum đem lại cải thiện bậc hai về tốc độ, một mức tăng đáng để nhìn nghiêm túc.

Còn sâu hơn nữa, các cận dưới kiểu Nesterov cho thấy trong một nghĩa hẹp nhưng chính xác, các phương pháp tăng tốc là tối ưu. Điều đó không có nghĩa momentum luôn tốt nhất, nhưng nó sở hữu cấu trúc toán học rất đặc biệt.

Ta bắt đầu với mô hình đơn giản nhất nhưng không tầm thường: hàm bậc hai lồi.

Phân Rã Lỗi

Giả sử ma trận độ cong đối xứng và khả nghịch. Khi đó nghiệm tối ưu được viết trực tiếp bằng nghịch đảo ma trận.

Mô hình này có thể xem như xấp xỉ bậc hai cục bộ của một hàm phức tạp hơn. Ma trận độ cong có thể là Hessian, Fisher information, hoặc một mô hình khác của hình học bài toán.

Có thể xem tối ưu hóa như tổng hợp của nhiều bài toán thành phần, ở đây là 1 2 3 với các trị riêng tương ứng \lambda_1=0.01, \lambda_2=0.1, và \lambda_3=1.

Cỡ bước

Cỡ bước tối ưu

Chọn Cỡ Bước

Mẹo quan trọng là đổi sang cơ sở riêng của ma trận độ cong. Trong cơ sở này, mỗi chiều hoạt động độc lập, và gradient descent tách thành nhiều bài toán một chiều.

Công thức đóng cho thấy lỗi ban đầu được phân rã theo từng vector riêng. Mỗi thành phần lỗi giảm theo một tốc độ riêng, phụ thuộc vào trị riêng tương ứng và cỡ bước.

Những trị riêng lớn thường được sửa rất nhanh; những trị riêng nhỏ thì giảm chậm. Vì vậy quá trình tối ưu có thể nhìn như tổng của nhiều quá trình con, mỗi quá trình có đồng hồ riêng.

Ví Dụ: Hồi Quy Đa Thức

Điều kiện để hội tụ là mọi thành phần đều co lại. Từ đó ta có miền cỡ bước hợp lệ và có thể chọn cỡ bước tối ưu bằng cách cân bằng tốc độ của hướng nhanh nhất và chậm nhất.

Tỉ số điều kiện của bài toán quyết định tốc độ tổng thể. Khi tỉ số này lớn, gradient descent bị kéo chậm bởi hướng khó nhất, dù nhiều hướng khác đã được sửa gần xong.

Trong hồi quy đa thức, các thành phần riêng có diễn giải trực quan. Một số đặc trưng biểu diễn cấu trúc ổn định của dữ liệu, trong khi các đặc trưng khác giống nhiễu hoặc dao động bậc cao.

Gradient descent vô tình đóng vai trò như một bộ lọc phổ: nó học những thành phần mạnh trước và chậm chạm với các thành phần yếu hơn. Vì thế dừng sớm có thể hoạt động giống một dạng chính quy hóa.

So với Tikhonov regularization, dừng sớm không cần thêm tham số phạt sau khi đã chọn cỡ bước. Trong một lần chạy, ta đi qua cả một họ mô hình từ thiếu khớp đến quá khớp.

Bây giờ quay lại momentum. Khi viết cập nhật trên hàm bậc hai và đổi sang cơ sở riêng, mỗi chiều lại tách rời, nhưng mỗi chiều không còn là một truy hồi bậc nhất. Nó trở thành một hệ bậc hai.

Vì có hai trạng thái là vị trí và vận tốc, nghiệm của mỗi chiều được điều khiển bởi hai trị riêng của một ma trận nhỏ. Hai trị riêng này quyết định liệu quá trình hội tụ êm, dao động tắt dần, hay phân kỳ.

Động Lực Học Của Momentum

Biểu đồ tham số cho thấy momentum có một “bản đồ khí hậu” phong phú hơn gradient descent: có vùng hội tụ đơn điệu, vùng dao động, vùng tới hạn, và vùng bất ổn.

Tốc độ hội tụ

Đồ thị của \max\{|\sigma_1|, |\sigma_2|\} cho thấy nhiều vùng tham số riêng biệt, mỗi vùng có một kiểu hội tụ khác nhau.

Một lợi ích xuất hiện ngay: momentum cho phép dùng cỡ bước lớn hơn gradient descent trước khi phân kỳ. Nhưng cỡ bước lớn hơn cũng kéo theo dao động, nên không thể hiểu nó chỉ như một bộ giảm xóc.

Hệ Số Tắt Dần Tới Hạn

Khi cỡ bước nhỏ, momentum có diễn giải vật lý như một dao động tử điều hòa có ma sát. Vị trí là lỗi hiện tại, vận tốc là biến momentum, còn gradient đóng vai trò lực kéo về điểm cân bằng.

Hệ số tắt dần tới hạn là điểm cân bằng đẹp: đủ ma sát để tránh lắc quá mức, nhưng không nhiều đến mức làm chuyển động ì lại. Ở điểm này ta đạt cải thiện căn bậc hai so với gradient descent trên từng hướng riêng.

y_{i}^{k+1} = + \lambda_{i}x_{i}^{k}

và bị nhiễu bởi một trường lực bên ngoài

Có thể xem -y_i^k như vận tốc

\beta y_{i}^{k}

được làm suy giảm ở mỗi bước

x_i^{k+1} = x_i^k - \alpha y_i^{k+1}

Còn x là vị trí của hạt

và ở mỗi bước nó dịch chuyển một lượng nhỏ theo hướng vận tốc y^{k+1}_i.

Để có tốc độ toàn cục, ta phải tối ưu đồng thời cỡ bước và hệ số momentum cho toàn bộ phổ trị riêng. Công thức thu được đưa ra quy tắc thực dụng: khi bài toán điều kiện xấu, chọn momentum rất gần 1 và tăng cỡ bước đến sát ranh giới ổn định.

Các tham số tối ưu theo nghĩa tiệm cận không nhất thiết cho loss giảm nhanh nhất ở vài vòng đầu. Vì thế trong thực hành vẫn cần quan sát quỹ đạo, không chỉ nhìn công thức cuối cùng.

Bài toán tô màu minh họa điều này trên đồ thị. Ta muốn vài điểm đã biết kéo các điểm lân cận về cùng màu, đồng thời làm nghiệm mượt trên cạnh của đồ thị.

Tham Số Tối Ưu

Gradient descent ở đây tương đương với lan truyền thông tin cục bộ. Màu chỉ đi từ đỉnh này sang đỉnh kế bên qua từng vòng lặp, nên trên các đồ thị dài và mảnh, tín hiệu truyền rất chậm.

\frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1}

Tốc độ hội tụ, Momentum

\frac{\kappa-1}{\kappa+1}

Tốc độ hội tụ, Gradient Descent

Phổ của Laplacian đồ thị giải thích khác biệt đó. Đồ thị nhỏ-thế-giới hoặc đồ thị dày có điều kiện tốt; lưới tốt hơn khi số chiều tăng; đường dài mảnh có điều kiện xấu và làm tối ưu khó.

Ta có thể phân rã lỗi với momentum theo các trị riêng. Mức giảm không còn đơn điệu, nhưng nhanh hơn đáng kể.

f(w^k) - f(w^\star)

Tham số tối ưu theo tốc độ tiệm cận không nhất thiết cho hội tụ nhanh nhất ở các vòng đầu.

Cỡ bước α =

Momentum β =

Momentum tăng tốc rõ rệt trong bài toán này, nhưng nó không phá vỡ mọi giới hạn. Nếu thông tin phải lan truyền qua các tương tác cục bộ, không thuật toán bậc nhất tuyến tính nào có thể làm tín hiệu xuất hiện tức thời ở xa.

Ví Dụ: Bài Toán Tô Màu

Để hiểu giới hạn, ta mở rộng lớp thuật toán: gradient descent, momentum, conjugate gradient và nhiều biến thể bậc nhất đều có thể viết như tổ hợp tuyến tính của các gradient trong quá khứ.

\text{minimize} \qquad \frac{1}{2} \sum_{i\in D} (w_i - 1)^2

Bộ tô màu kéo các pixel được đánh dấu về 1

+ \frac{1}{2} \sum_{i,j\in E} (w_i - w_j)^2.

Bộ làm mượt lan truyền màu ra xung quanh

Với một oracle chống đối, có thể xây dựng bài toán trong đó nhiều tọa độ vẫn buộc phải bằng 0 sau một số vòng lặp hữu hạn. Vùng chưa bị ảnh hưởng này tạo thành một “nón ánh sáng” của thông tin.

Các vector riêng của bài toán tô màu tạo thành một cơ sở Fourier tổng quát cho R^n. Trị riêng nhỏ ứng với tần số thấp, nên gradient descent sửa tốt lỗi tần số cao nhưng chậm với lỗi tần số thấp.

Kết quả cận dưới không nên đọc như lời chê momentum. Nó chỉ nói rằng, trong lớp phương pháp rất rộng này, tăng tốc đã gần chạm giới hạn có thể đạt được khi chỉ dùng thông tin gradient bậc nhất.

\text{minimize}

Dạng bậc hai của bộ làm mượt là Laplacian đồ thị

\frac{1}{2}\sum_{i\in D}\left(x^{T}e_{i}e_{i}^{T}x-e_{i}^{T}x\right) + \frac{1}{2}x^{T}L_{G}x

Còn bộ tô màu là một hiệu chỉnh hạng thấp nhỏ kèm một hạng tuyến tính. e_i là vector đơn vị thứ i.

Cuối cùng, ta xét gradient ngẫu nhiên. Trong học máy, gradient thường được ước lượng từ minibatch nên luôn chứa nhiễu.

Đồ thị nhỏ-thế-giới và đồ thị dày có điều kiện rất tốt.

Điều kiện của lưới tốt hơn khi số chiều tăng.

Đồ thị dài và mảnh, như đường thẳng, có điều kiện xấu.

Có thể tách gradient xấp xỉ thành gradient thật cộng với lỗi ngẫu nhiên. Trên hàm bậc hai, lỗi tối ưu cũng tách thành phần tất định và phần nhiễu tích lũy.

Giới Hạn Của Các Phương Pháp Đi Xuống

Điều này tạo ra một đánh đổi khó chịu. Cỡ bước nhỏ làm giảm lỗi ngẫu nhiên nhưng làm hội tụ chậm. Momentum lớn giúp giai đoạn đầu đi nhanh hơn, nhưng cũng có thể làm nhiễu tích tụ mạnh hơn.

Trong thực hành mạng nơ-ron, giai đoạn quá độ ban đầu thường quan trọng hơn giai đoạn tinh chỉnh cuối. Vì vậy momentum vẫn rất hữu ích, ngay cả khi phân tích nhiễu cho thấy nó không miễn phí.

Một Chuyến Đi Trong Không Gian Thuật Toán

Nghiên cứu về tăng tốc đang sống lại với nhiều cách nhìn: phương trình vi phân, đa thức xấp xỉ, hình học lồi và đối ngẫu. Mỗi góc nhìn giải thích một phần của hiện tượng.

Oracle Kháng Cự

Momentum vì thế lớn hơn câu chuyện quả bóng lăn xuống đồi. Đó là một thuật toán nơi phổ, dao động, điều kiện bài toán và nhiễu cùng quyết định hành vi. Khi hiểu được các mảnh này, ta biết rõ hơn lúc nào nên tin vào momentum và lúc nào cần thận trọng.

f^n(w) =

với một bộ tô màu tại một nút

\frac{1}{2}\left(w_{1}-1\right)^{2} + \frac{1}{2}\sum_{i=1}^{n}(w_{i}-w_{i+1})^{2}

các liên kết mạnh giữa những nút kề nhau trên đường,

+ \frac{2}{\kappa-1}\|w\|^{2}.

và một hạng chính quy hóa nhỏ.

Cỡ bước α =

Momentum β =

Năm mươi vòng lặp đầu của momentum trên Convex Rosenbrock với n=25.

Tam giác này là vùng chết: các phần tử lặp vẫn bằng 0 bất kể tham số.

Phần còn lại là nón ảnh hưởng của vòng lặp; momentum hoạt động tốt với tham số tối ưu.

Lỗi

Trọng số

\begin{array}{lllllllll} w^{0} & = & [~~0, & 0, & 0, & \ldots & 0, & 0, & \ldots & 0~]\\[0.35em] w^{1} & = & [~w_{1}^{1}, & 0, & 0, & \ldots & 0, & 0, & \ldots & 0~]\\[0.35em] w^{2} & = & [~w_{1}^{2}, & w_{2}^{2}, & 0, & \ldots & 0, & 0, & \ldots & 0~]\\[0.35em] & ~ \vdots \\ w^{k} & = & [~w_{1}^{k}, & w_{2}^{k}, & w_{3}^{k}, & \ldots & w_{k}^{k}, & 0, & \ldots & 0~].\\ \end{array}

Momentum Với Gradient Ngẫu Nhiên

\nabla f(w)

gradient thật

+ \text{error}(w).

và sai số xấp xỉ.
Nếu bộ ước lượng không chệch, ví dụ \mathbf{E}[\text{error}(w)] = 0

\left(\begin{array}{c} y_{i}^{k}\\ x_{i}^{k} \end{array}\right)

các vòng lặp có nhiễu là tổng của

= R^{k}\left(\begin{array}{c} y_{i}^{0}\\ x_{i}^{0} \end{array}\right)

các vòng lặp tất định không nhiễu và

+ \epsilon^k_i \sum_{j=1}^{k}R^{k-j}\left(\begin{array}{c} 1\\ -\alpha \end{array}\right)

một tổng sai số suy giảm, trong đó \epsilon^k = Q \cdot \text{error}(w^k).

We decompose the expected value of the objective value \mathbf{E} f(w) - f(w^\star) into a deterministic part and a stochastic part .

\mathbf{E} f(w) - f(w^\star)

Các chấm đen nhỏ là một lần chạy gradient ngẫu nhiên.

Cỡ bước α =

Momentum β =

Tối ưu hóa có hai pha: lúc đầu gradient lớn hơn nhiễu nên momentum còn hữu ích; về sau nhiễu lấn át gradient và momentum kém hiệu quả hơn.

Đi Tiếp Và Đi Xuống