Giải chính xác gradient descent trên hàm bậc hai

Gradient descent trên hàm bậc hai dương đủ đơn giản để giải chính xác. Vì thế, nó là phép kiểm tra hữu ích cho ba khẳng định dễ bị lẫn: tham số tiến gần điểm cực tiểu, giá trị mục tiêu giảm, và tốc độ học ổn định từ mọi điểm khởi tạo. Ngay trên bài toán hai biến, ba khẳng định ấy vẫn có thể cho câu trả lời khác nhau.

Bài viết dành cho bạn đang học tối ưu hóa, đã biết đạo hàm và cấp số nhân. Ta bắt đầu với một biến rồi thêm hướng có độ cong thứ hai. Mọi hàm mục tiêu và điểm khởi tạo đều là ví dụ giả lập để học. Phép tính dùng phân số chính xác, nên thành công hay thất bại biểu kiến không thể được giải thích bằng sai số làm tròn trong những phép tính này.

Hệ số nhân quyết định toàn bộ trường hợp một biến

Xét hàm mục tiêu f(x) = lambda*x²/2, với độ cong lambda dương. Điểm cực tiểu là không, đạo hàm bằng lambda nhân x. Với tốc độ học eta cố định, gradient descent thỏa mãn:

x_(t+1) = x_t - eta*lambda*x_t = (1-eta*lambda)*x_t
x_t = (1-eta*lambda)^t*x_0
f(x_t) = (1-eta*lambda)^(2t)*f(x_0)

Từ điểm khởi tạo khác không, muốn hội tụ về cực tiểu thì trị tuyệt đối của hệ số nhân phải nhỏ hơn một. Giải bất đẳng thức cho khoảng mở 0 < eta < 2/lambda. Trong mô hình chính xác này, trị tuyệt đối nhỏ hơn nghĩa là khoảng cách co lại nhanh hơn sau mỗi bước.

Khi eta bằng không, tham số đứng yên. Khi eta bằng hai lần nghịch đảo độ cong, tham số đổi dấu mà không giảm độ lớn. Vượt ranh giới ấy, hoặc dùng tốc độ âm, điểm khởi tạo khác không tăng về độ lớn. Khởi tạo đúng tại không là trường hợp đặc biệt: tốc độ nào cũng giữ nó ở đó vì gradient bằng không. Một lần chạy thành công từ chính cực tiểu không nói lên tính ổn định của những điểm lân cận.

Chương tối ưu hóa của Deep Learning phân biệt bài toán tối ưu với bài toán học rộng hơn. Phép suy ra của ta nói về hàm mục tiêu đang tối ưu. Đạt cực tiểu của nó không xác lập khả năng khái quát sang dữ liệu chưa thấy.

Mục tiêu giảm có thể che tham số đổi dấu liên tục

Dùng f(x)=2x², nên độ cong bằng bốn, rồi khởi tạo tại một. Khoảng ổn định từ không đến một nửa, không gồm hai đầu mút. Bốn tốc độ cho các hành vi khác nhau:

Tốc độ	Hệ số nhân	Ba giá trị đầu sau khởi tạo	Hành vi
1/4	0	0, 0, 0	Về không sau một cập nhật
2/5	−3/5	−0,6; 0,36; −0,216	Đổi dấu và hội tụ
1/2	−1	−1; 1; −1	Đổi dấu, giữ nguyên độ lớn
3/5	−7/5	−1,4; 1,96; −2,744	Đổi dấu và phân kỳ

Chạy lần lượt ba khối Python trong cùng một phiên. Chúng chỉ cần thư viện chuẩn. Trong giao diện hàm, giữ tốc độ học và độ cong thành hai đối số riêng: tích của chúng điều khiển truy hồi.

from fractions import Fraction as F

def trajectory(curvature, rate, start, steps):
    x = F(start)
    values = [x]
    for _ in range(steps):
        x = x-rate*curvature*x
        values.append(x)
    return values

rates = [F(1,4), F(2,5), F(1,2), F(3,5)]
for rate in rates:
    values = trajectory(F(4), rate, F(1), 6)
    print(rate, values[:4])
    multiplier = 1-4*rate
    assert values == [multiplier**t for t in range(7)]

Ở tốc độ 2/5, hệ số nhân tham số có dấu là âm 3/5 nhưng hệ số nhân của mục tiêu bằng 9/25. Mỗi giá trị mục tiêu còn 36% giá trị trước trong khi tham số vượt qua cực tiểu ở mọi bước. Dao động không đồng nghĩa với phân kỳ; việc mất dấu khi vẽ mục tiêu có thể che một dao động hoàn toàn ổn định.

Bản chuyển thể thành văn của bài học ngày 16/10/2017 do Grant Sanderson trình bày, được Josh Pullen biên soạn, giới thiệu gradient âm qua hướng giảm nhanh nhất. Hướng là thông tin cục bộ; tốc độ học quyết định một cập nhật hữu hạn đi xa bao nhiêu. Hệ số nhân chính xác ở đây kiểm tra lựa chọn bổ sung ấy.

Lời giải một bước tại tốc độ 1/4 cũng đặc biệt. Nó dùng độ cong chính xác của hàm bậc hai này. Hàm phi tuyến có thể đổi độ cong ở vị trí tiếp theo, nên ước lượng một tốc độ thuận tiện tại một điểm không xác lập cùng truy hồi trong toàn bộ quá trình huấn luyện.

Mở ảnh kích thước đầy đủ ↗

Một tốc độ phải phục vụ mọi hướng đang tham gia

Bây giờ dùng g(x,y)=(x²+9y²)/2. Gradient là (x,9y). Cập nhật đồng thời nhân x với 1-eta và y với 1-9eta. Để hội tụ từ mọi điểm khởi tạo, cả hai trị tuyệt đối phải nhỏ hơn một, đòi hỏi 0 < eta < 2/9.

Từ “mọi” có ý nghĩa. Tọa độ khởi tạo bằng không sẽ luôn bằng không trong hệ chéo chính xác này. Vì vậy, một tốc độ có thể thành công từ điểm nằm đúng trên một hướng đặc biệt nhưng không ổn định theo hướng mà lần chạy chưa hề đi vào.

def plane(rate, start, steps):
    x, y = map(F, start)
    states = [(x,y)]
    for _ in range(steps):
        x, y = x-rate*x, y-9*rate*y
        states.append((x,y))
    return states

def objective(state):
    x, y = state
    return (x*x+9*y*y)/2

aligned = plane(F(1), (1,0), 5)
perturbed = plane(F(1), (1,F(1,1000)), 5)
print('aligned after one update:', aligned[1])
print('perturbed steep coordinate:', [y for x,y in perturbed])
assert aligned[1] == (0,0)
assert abs(perturbed[-1][1]) == F(4096,125)

Tốc độ một đưa điểm (1,0) trực tiếp đến cực tiểu. Chỉ thêm 0,001 theo hướng dốc đã đổi kết quả: tọa độ ấy được nhân với âm tám sau mỗi cập nhật. Sau năm bước, độ lớn của nó là 32,768. Quỹ đạo thành công ban đầu không chứng nhận tính ổn định trong một lân cận.

Với hàm bậc hai có ma trận đối xứng xác định dương tổng quát, cơ sở vector riêng trực chuẩn cho cùng phép tính, với một hệ số nhân ứng với mỗi trị riêng của Hessian. Tính ổn định từ mọi điểm khởi tạo dùng trị riêng lớn nhất. Với một sai lệch khởi tạo chính xác cụ thể, chỉ các hướng có thành phần khác không tham gia. Nhiễu, số học hữu hạn hoặc thay đổi hàm mục tiêu có thể tạo ra thành phần vắng mặt trong phép tính lý tưởng hóa.

Chương tính toán số của Deep Learning giải thích điều kiện số và độ cong trong tối ưu theo gradient. Ví dụ hai hướng làm rõ hình học đó mà không coi độ lớn gradient quan sát được là ước lượng độ cong.

Giá trị giảm nghiêm ngặt vẫn có thể dừng trên cực tiểu

Đặt tốc độ đúng tại ranh giới 2/9 và khởi tạo (1,1). Tọa độ theo hướng thoải co lại với hệ số 7/9, còn tọa độ theo hướng dốc luân phiên giữa một và âm một. Mục tiêu sau t cập nhật bằng 9/2 + (7/9)^(2t)/2.

Dãy này giảm nghiêm ngặt tại mọi bước hữu hạn, nhưng giới hạn là 4,5 trong khi cực tiểu bằng không. Về sau, thay đổi nhỏ của mục tiêu phản ánh thành phần thoải đang tắt dần, không phải hướng dốc đã được tối ưu thành công. Quy tắc dừng chỉ dựa vào thay đổi tổn thất có thể nhầm sự đình trệ trên cực tiểu với hội tụ.

Ngược lại, tốc độ 1/5 cho hệ số tọa độ 4/5 và âm 4/5. Từ (1,1), mục tiêu bằng 5*(16/25)^t và tiến về không. Tọa độ theo hướng dốc vẫn đổi dấu nhưng cả hai thành phần đều co lại.

boundary = plane(F(2,9), (1,1), 12)
stable = plane(F(1,5), (1,1), 12)
for t in range(13):
    assert objective(boundary[t]) == F(9,2)+F(1,2)*F(7,9)**(2*t)
    assert objective(stable[t]) == 5*F(16,25)**t
print('boundary after twelve:', float(objective(boundary[-1])))
print('stable after twelve:', float(objective(stable[-1])))
assert all(objective(boundary[t+1]) < objective(boundary[t]) for t in range(12))

Chuẩn gradient cung cấp chỉ dấu khác ở đây: thành phần theo hướng dốc giữ nguyên độ lớn chín trên quỹ đạo tại ranh giới. Chỉ dấu này cũng cần được hiểu theo thang đo. Gradient nhỏ có thể đến từ việc nhân hàm mục tiêu với hệ số nhỏ, còn cộng hằng số lớn vào mục tiêu làm đổi giá trị hiển thị mà không đổi gradient. Hãy so sánh các đại lượng có ý nghĩa đã xác định, không chỉ các thang biểu đồ thuận tiện.

Mở ảnh kích thước đầy đủ ↗

Tốc độ vững cho mọi hướng khác với bước đầu may mắn

Với hai độ cong một và chín, hệ số co tọa độ trong trường hợp xấu nhất là giá trị lớn hơn giữa |1-eta| và |1-9eta|. Hệ số xấu nhất nhỏ nhất có thể đạt là 4/5, tại eta bằng 1/5. Nếu cả hai trị tuyệt đối đều nhỏ hơn 4/5, hướng thoải buộc eta lớn hơn 1/5 còn hướng dốc buộc eta nhỏ hơn 1/5, dẫn đến mâu thuẫn.

Kết quả này tối thiểu hóa mức co xấu nhất giữa các hướng khởi tạo khi dùng tốc độ cố định. Nó không hứa mục tiêu nhỏ nhất sau mọi số bước cố định từ mọi điểm bắt đầu. Từ (1,0), tốc độ một thắng ngay nhưng thiếu ổn định trước thành phần nhỏ theo hướng dốc. Khẳng định về “tốc độ học tốt nhất” phải nói rõ đang dùng mục tiêu so sánh nào.

Đổi thang đo làm đổi tốc độ số học

Nhân toàn bộ mục tiêu với hằng số dương c sẽ nhân gradient và độ cong với c. Chia tốc độ học cho c giữ nguyên chính xác từng cập nhật. Vì thế, chuyển tổng tổn thất thành trung bình làm thay đổi bước hiệu dụng nếu không điều chỉnh tốc độ nhất quán.

Đổi tọa độ là việc khác. Nếu x=s*u với s khác không, cùng hàm vô hướng viết theo u có độ cong lambda*s². Bước kích thước alpha trong u trở thành bước kích thước alpha*s² trong x sau khi đổi ngược. Muốn khớp quỹ đạo x ban đầu, alpha phải bằng eta chia s bình phương. Chỉ đổi tên đơn vị mà giữ tốc độ dưới dạng cùng một con số sẽ làm đổi thuật toán.

Bài tập: nhân mục tiêu vô hướng với mười rồi kiểm tra các quỹ đạo giống hệt khi chia mọi tốc độ cho mười. Tiếp theo dùng x=2u, khởi tạo u=1/2, và kiểm tra tốc độ 1/10 trong u tái tạo quỹ đạo x tại tốc độ 2/5. Cuối cùng dùng tốc độ ranh giới của bài toán hai biến, lần lượt với (1,0) và (1,1). Trường hợp đầu hội tụ, trường hợp sau không. Hãy ghi hướng khởi tạo, cách chuẩn hóa mục tiêu và tiêu chí hội tụ trước khi dùng một đường cong làm bằng chứng rằng bộ tối ưu ổn định.