動機
最小二乘把數據擬合化為最佳化問題。正規方程直接描述最優參數，梯度下降則由一個初始估計出發，逐步接近答案。兩種觀點應當互相配合：方程指出目的地，迭代說明每一步如何改變目前的誤差。
二次目標函數的梯度是參數的仿射函數，曲率在各點相同，而特徵向量可以把更新拆成互不干擾的一維遞推。因此，我們能精確算出哪些步長令誤差縮小、哪些令誤差來回擺動，以及哪些令迭代發散。這也解釋了為何把損失乘上一個常數，雖然不會改變擬合結果，卻會改變合適的學習率。
本節把參數向量及梯度都寫成列向量。「最陡」是相對於歐幾里得長度而言，背後仍是投影與主成分分析所用的內積幾何。我們會直接使用實對稱矩陣的譜分解，重點放在特徵值如何控制更新，而不是重新介紹求特徵向量的算法。
定義
定義
二次目標函數與梯度 設參數向量 θ ∈ R d \theta\in\mathbb R^d θ ∈ R d
f ( θ ) = 1 2 θ ⊤ Q θ − b ⊤ θ + c , Q = Q ⊤ . f(\theta)=\frac12\theta^\top Q\theta-b^\top\theta+c,
\qquad Q=Q^\top. f ( θ ) = 2 1 θ ⊤ Qθ − b ⊤ θ + c , Q = Q ⊤ . 其中 Q Q Q d × d d\times d d × d b ∈ R d b\in\mathbb R^d b ∈ R d c c c
∇ f ( θ ) = Q θ − b , ∇ 2 f ( θ ) = Q . \nabla f(\theta)=Q\theta-b,\qquad \nabla^2 f(\theta)=Q. ∇ f ( θ ) = Qθ − b , ∇ 2 f ( θ ) = Q . 若每個非零向量 z z z z ⊤ Q z > 0 z^\top Qz>0 z ⊤ Q z > 0 Q Q Q μ = λ min ( Q ) \mu=\lambda_{\min}(Q) μ = λ m i n ( Q ) L = λ max ( Q ) L=\lambda_{\max}(Q) L = λ m a x ( Q )
把 θ \theta θ θ + h \theta+h θ + h Q Q Q h h h h ⊤ ( Q θ − b ) h^\top(Q\theta-b) h ⊤ ( Qθ − b ) h ⊤ Q h / 2 h^\top Qh/2 h ⊤ Q h /2 1 / 2 1/2 1/2 2 2 2
定義
固定步長的梯度下降 選取初始參數 θ 0 \theta_0 θ 0 η > 0 \eta>0 η > 0
θ k + 1 = θ k − η ∇ f ( θ k ) = θ k − η ( Q θ k − b ) , k = 0 , 1 , 2 , … . \theta_{k+1}=\theta_k-\eta\nabla f(\theta_k)
=\theta_k-\eta(Q\theta_k-b),
\qquad k=0,1,2,\ldots. θ k + 1 = θ k − η ∇ f ( θ k ) = θ k − η ( Q θ k − b ) , k = 0 , 1 , 2 , … . 每一步先在目前的向量 θ k \theta_k θ k
令 g = ∇ f ( θ ) g=\nabla f(\theta) g = ∇ f ( θ ) v v v g ⊤ v g^\top v g ⊤ v − ∥ g ∥ 2 -\|g\|_2 − ∥ g ∥ 2 g ≠ 0 g\ne0 g = 0 v = − g / ∥ g ∥ 2 v=-g/\|g\|_2 v = − g /∥ g ∥ 2 − g -g − g η ∥ g ∥ 2 \eta\|g\|_2 η ∥ g ∥ 2
定理/命題
定理
唯一最小值與精確的目標差距 若 Q Q Q f f f
θ ⋆ = Q − 1 b . \theta_\star=Q^{-1}b. θ ⋆ = Q − 1 b . 設 e = θ − θ ⋆ e=\theta-\theta_\star e = θ − θ ⋆
f ( θ ) − f ( θ ⋆ ) = 1 2 e ⊤ Q e , μ 2 ∥ e ∥ 2 2 ≤ f ( θ ) − f ( θ ⋆ ) ≤ L 2 ∥ e ∥ 2 2 . f(\theta)-f(\theta_\star)=\frac12e^\top Qe,
\qquad
\frac{\mu}{2}\|e\|_2^2
\le f(\theta)-f(\theta_\star)
\le\frac{L}{2}\|e\|_2^2. f ( θ ) − f ( θ ⋆ ) = 2 1 e ⊤ Q e , 2 μ ∥ e ∥ 2 2 ≤ f ( θ ) − f ( θ ⋆ ) ≤ 2 L ∥ e ∥ 2 2 . 常數 c c c b b b Q Q Q
定理
固定步長收斂的精確條件 設 Q Q Q e k = θ k − θ ⋆ e_k=\theta_k-\theta_\star e k = θ k − θ ⋆ η \eta η
e k + 1 = ( I − η Q ) e k . e_{k+1}=(I-\eta Q)e_k. e k + 1 = ( I − η Q ) e k . 對每一個初始向量都收斂至 θ ⋆ \theta_\star θ ⋆
0 < η < 2 L . 0<\eta<\frac2L. 0 < η < L 2 . 在這個範圍內，記
ρ = max i ∣ 1 − η λ i ( Q ) ∣ < 1. \rho=\max_i|1-\eta\lambda_i(Q)|<1. ρ = i max ∣1 − η λ i ( Q ) ∣ < 1. 則 ∥ e k ∥ 2 ≤ ρ k ∥ e 0 ∥ 2 \|e_k\|_2\le\rho^k\|e_0\|_2 ∥ e k ∥ 2 ≤ ρ k ∥ e 0 ∥ 2 f ( θ k ) − f ( θ ⋆ ) ≤ ρ 2 k ( f ( θ 0 ) − f ( θ ⋆ ) ) f(\theta_k)-f(\theta_\star)\le
\rho^{2k}\bigl(f(\theta_0)-f(\theta_\star)\bigr) f ( θ k ) − f ( θ ⋆ ) ≤ ρ 2 k ( f ( θ 0 ) − f ( θ ⋆ ) )
「每一個初始向量」是條件的一部分。如果某次初始誤差在不穩定的特徵向量方向剛好為零，那次計算仍可能成功。定理給出的步長範圍則同時控制所有可能出現的誤差方向，不能單憑一次成功的數值結果擴大它。
證明思路
先展開 f ( θ ⋆ + e ) f(\theta_\star+e) f ( θ ⋆ + e ) Q θ ⋆ = b Q\theta_\star=b Q θ ⋆ = b e e e e ⊤ Q e / 2 e^\top Qe/2 e ⊤ Q e /2 Q = V Λ V ⊤ Q=V\Lambda V^\top Q = V Λ V ⊤ V V V z = V ⊤ e z=V^\top e z = V ⊤ e e ⊤ Q e = ∑ i λ i z i 2 e^\top Qe=\sum_i\lambda_i z_i^2 e ⊤ Q e = ∑ i λ i z i 2 μ \mu μ L L L
接着從更新式減去駐點方程：
e k + 1 = θ k − η ( Q θ k − b ) − θ ⋆ = e k − η Q e k . \begin{aligned}
e_{k+1}
&=\theta_k-\eta(Q\theta_k-b)-\theta_\star\\
&=e_k-\eta Qe_k.
\end{aligned} e k + 1 = θ k − η ( Q θ k − b ) − θ ⋆ = e k − η Q e k . 轉到特徵向量座標 z k = V ⊤ e k z_k=V^\top e_k z k = V ⊤ e k
z k + 1 , i = ( 1 − η λ i ) z k , i , z k , i = ( 1 − η λ i ) k z 0 , i . z_{k+1,i}=(1-\eta\lambda_i)z_{k,i},
\qquad
z_{k,i}=(1-\eta\lambda_i)^kz_{0,i}. z k + 1 , i = ( 1 − η λ i ) z k , i , z k , i = ( 1 − η λ i ) k z 0 , i . 每個座標都是等比數列。要讓任意起始值都趨近零，必須且只須 ∣ 1 − η λ i ∣ < 1 |1-\eta\lambda_i|<1 ∣1 − η λ i ∣ < 1 0 < η λ i < 2 0<\eta\lambda_i<2 0 < η λ i < 2 0 < η < 2 / L 0<\eta<2/L 0 < η < 2/ L λ i / 2 \lambda_i/2 λ i /2
當 η = 2 / L \eta=2/L η = 2/ L − 1 -1 − 1 η > 2 / L \eta>2/L η > 2/ L η = 0 \eta=0 η = 0
曲率、進度與條件數
還可以直接計算一步之後的目標變化。令 g = ∇ f ( θ ) g=\nabla f(\theta) g = ∇ f ( θ )
f ( θ − η g ) − f ( θ ) = − η ∥ g ∥ 2 2 + η 2 2 g ⊤ Q g ≤ − η ( 1 − η L 2 ) ∥ g ∥ 2 2 . f(\theta-\eta g)-f(\theta)
=-\eta\|g\|_2^2+\frac{\eta^2}{2}g^\top Qg
\le-\eta\left(1-\frac{\eta L}{2}\right)\|g\|_2^2. f ( θ − η g ) − f ( θ ) = − η ∥ g ∥ 2 2 + 2 η 2 g ⊤ Q g ≤ − η ( 1 − 2 η L ) ∥ g ∥ 2 2 . 所以在 0 < η < 2 / L 0<\eta<2/L 0 < η < 2/ L η = 1 / L \eta=1/L η = 1/ L 0 0 0 1 − μ / L 1-\mu/L 1 − μ / L μ \mu μ L L L
正定二次函數的條件數為 κ = L / μ \kappa=L/\mu κ = L / μ 1 − η μ = − ( 1 − η L ) 1-\eta\mu=-(1-\eta L) 1 − η μ = − ( 1 − η L ) η = 2 / ( μ + L ) \eta=2/(\mu+L) η = 2/ ( μ + L ) ρ = ( κ − 1 ) / ( κ + 1 ) \rho=(\kappa-1)/(\kappa+1) ρ = ( κ − 1 ) / ( κ + 1 )
收縮因子描述的是反覆更新的進度。若 ρ = 3 / 4 \rho=3/4 ρ = 3/4 ( 3 / 4 ) 10 (3/4)^{10} ( 3/4 ) 10 ( 3 / 4 ) 20 (3/4)^{20} ( 3/4 ) 20
在狹長的二次曲面谷地中，移離陡峭側面可以很快消除一大部分初始損失。此後，剩餘誤差主要沿平坦方向，進度看來就會放慢。每一步仍遵守同一條固定遞推；變化的是誤差中各方向分量的比例，而不是算法突然改變。
例題
例題
1. 一維誤差的縮小、交替與發散 設 f ( t ) = 2 ( t − 3 ) 2 f(t)=2(t-3)^2 f ( t ) = 2 ( t − 3 ) 2 4 ( t − 3 ) 4(t-3) 4 ( t − 3 ) t ⋆ = 3 t_\star=3 t ⋆ = 3 L = 4 L=4 L = 4 0 < η < 1 / 2 0<\eta<1/2 0 < η < 1/2
由 t 0 = − 1 t_0=-1 t 0 = − 1 η = 1 / 8 \eta=1/8 η = 1/8 1 − 4 η = 1 / 2 1-4\eta=1/2 1 − 4 η = 1/2
t 0 = − 1 , t 1 = 1 , t 2 = 2 , t 3 = 5 2 . t_0=-1,\quad t_1=1,\quad t_2=2,\quad t_3=\frac52. t 0 = − 1 , t 1 = 1 , t 2 = 2 , t 3 = 2 5 . 損失依次為 32 32 32 8 8 8 2 2 2 1 / 2 1/2 1/2
若改取 η = 1 / 2 \eta=1/2 η = 1/2 − 1 -1 − 1 − 1 -1 − 1 7 7 7 32 32 32 η = 3 / 4 \eta=3/4 η = 3/4 − 2 -2 − 2 − 1 -1 − 1 11 11 11 − 13 -13 − 13 32 32 32 128 128 128 512 512 512
例題
2. 兩個特徵向量方向有不同的進度 考慮
f ( u , v ) = 1 2 ( ( u − 1 ) 2 + 4 ( v + 1 ) 2 ) . f(u,v)=\frac12\bigl((u-1)^2+4(v+1)^2\bigr). f ( u , v ) = 2 1 ( ( u − 1 ) 2 + 4 ( v + 1 ) 2 ) . 此時 Q = diag ( 1 , 4 ) Q=\operatorname{diag}(1,4) Q = diag ( 1 , 4 ) θ ⋆ = ( 1 , − 1 ) ⊤ \theta_\star=(1,-1)^\top θ ⋆ = ( 1 , − 1 ) ⊤ η = 1 / 4 \eta=1/4 η = 1/4 3 / 4 3/4 3/4 0 0 0 ( u 0 , v 0 ) = ( 3 , 1 ) (u_0,v_0)=(3,1) ( u 0 , v 0 ) = ( 3 , 1 )
( u 1 , v 1 ) = ( 5 2 , − 1 ) , ( u 2 , v 2 ) = ( 17 8 , − 1 ) . (u_1,v_1)=\left(\frac52,-1\right),\qquad
(u_2,v_2)=\left(\frac{17}{8},-1\right). ( u 1 , v 1 ) = ( 2 5 , − 1 ) , ( u 2 , v 2 ) = ( 8 17 , − 1 ) . 第二座標一步到達最優值，第一座標則以等比方式逐漸接近 1 1 1 f 0 = 10 f_0=10 f 0 = 10 f 1 = 9 / 8 f_1=9/8 f 1 = 9/8 f 2 = 81 / 128 f_2=81/128 f 2 = 81/128 η = 2 / 5 \eta=2/5 η = 2/5 3 / 5 3/5 3/5 − 3 / 5 -3/5 − 3/5
以下 Python 程式先計算兩個梯度分量，再同時更新參數。將輸出與上述精確分數比較，便能逐步核對座標遞推。
u, v = 3.0, 1.0
eta = 0.25
for k in range(4):
loss = 0.5 * ((u - 1.0) ** 2 + 4.0 * (v + 1.0) ** 2)
print(f"{k}: ({u:.6f}, {v:.6f}) f={loss:.6f}")
grad_u, grad_v = u - 1.0, 4.0 * (v + 1.0)
u, v = u - eta * grad_u, v - eta * grad_v
輸出為
0: (3.000000, 1.000000) f=10.000000
1: (2.500000, -1.000000) f=1.125000
2: (2.125000, -1.000000) f=0.632812
3: (1.843750, -1.000000) f=0.355957
例題
3. 梯度下降與回歸方程得到相同擬合 取三筆觀測資料：
A = [ 1 − 1 1 0 1 1 ] , y = [ 0 1 3 ] , f ( θ ) = 1 2 n ∥ A θ − y ∥ 2 2 , n = 3. A=\begin{bmatrix}1&-1\\1&0\\1&1\end{bmatrix},
\qquad y=\begin{bmatrix}0\\1\\3\end{bmatrix},
\qquad f(\theta)=\frac{1}{2n}\|A\theta-y\|_2^2,\quad n=3. A = 1 1 1 − 1 0 1 , y = 0 1 3 , f ( θ ) = 2 n 1 ∥ A θ − y ∥ 2 2 , n = 3. 第一個參數是截距，第二個是斜率。展開可得 Q = A ⊤ A / n = diag ( 1 , 2 / 3 ) Q=A^\top A/n=\operatorname{diag}(1,2/3) Q = A ⊤ A / n = diag ( 1 , 2/3 ) b = A ⊤ y / n = ( 4 / 3 , 1 ) ⊤ b=A^\top y/n=(4/3,1)^\top b = A ⊤ y / n = ( 4/3 , 1 ) ⊤ θ ⋆ = ( 4 / 3 , 3 / 2 ) ⊤ \theta_\star=(4/3,3/2)^\top θ ⋆ = ( 4/3 , 3/2 ) ⊤ A A A Q Q Q L = 1 L=1 L = 1
由 θ 0 = ( 0 , 0 ) ⊤ \theta_0=(0,0)^\top θ 0 = ( 0 , 0 ) ⊤ η = 1 \eta=1 η = 1 − b -b − b θ 1 = ( 4 / 3 , 1 ) ⊤ \theta_1=(4/3,1)^\top θ 1 = ( 4/3 , 1 ) ⊤ A θ 1 − y = ( 1 / 3 , 1 / 3 , − 2 / 3 ) ⊤ A\theta_1-y=(1/3,1/3,-2/3)^\top A θ 1 − y = ( 1/3 , 1/3 , − 2/3 ) ⊤ f ( θ 1 ) = 1 / 9 f(\theta_1)=1/9 f ( θ 1 ) = 1/9 θ 2 = ( 4 / 3 , 4 / 3 ) ⊤ \theta_2=(4/3,4/3)^\top θ 2 = ( 4/3 , 4/3 ) ⊤ f ( θ 2 ) = 1 / 27 f(\theta_2)=1/27 f ( θ 2 ) = 1/27
在最小點，殘差為 ( − 1 / 6 , 1 / 3 , − 1 / 6 ) ⊤ (-1/6,1/3,-1/6)^\top ( − 1/6 , 1/3 , − 1/6 ) ⊤ 1 / 36 1/36 1/36 1 / 3 1/3 1/3
對一般設計矩陣 A ∈ R n × d A\in\mathbb R^{n\times d} A ∈ R n × d
∇ f ( θ ) = 1 n A ⊤ ( A θ − y ) , Q = 1 n A ⊤ A . \nabla f(\theta)=\frac1nA^\top(A\theta-y),\qquad
Q=\frac1nA^\top A. ∇ f ( θ ) = n 1 A ⊤ ( A θ − y ) , Q = n 1 A ⊤ A . 滿列秩正是 Q Q Q z ⊤ Q z = ∥ A z ∥ 2 2 / n z^\top Qz=\|Az\|_2^2/n z ⊤ Q z = ∥ A z ∥ 2 2 / n z z z A A A L = σ max ( A ) 2 / n L=\sigma_{\max}(A)^2/n L = σ m a x ( A ) 2 / n A ⊤ A^\top A ⊤ n n n
這裏的觀測索引與參數索引有不同角色：預測及殘差各有一個分量對應每筆觀測，梯度則每個分量對應一個參數。乘以 A ⊤ A^\top A ⊤ 1 1 1
因此，迭代收斂時殘差未必趨近零。殘差可以保留一個垂直於 A A A
實作時分別計算 A θ A\theta A θ A ⊤ r A^\top r A ⊤ r A ⊤ A A^\top A A ⊤ A A A A
損失尺度與停止條件
把 f f f F = α f F=\alpha f F = α f α > 0 \alpha>0 α > 0 α \alpha α α \alpha α F = 2 n f = 6 f F=2nf=6f F = 2 n f = 6 f 6 6 6 0 < η < 1 / 3 0<\eta<1/3 0 < η < 1/3 1 / 6 1/6 1/6 1 1 1
梯度長度 ∥ ∇ f ( θ k ) ∥ 2 \|\nabla f(\theta_k)\|_2 ∥∇ f ( θ k ) ∥ 2 ∇ f = Q e k \nabla f=Qe_k ∇ f = Q e k μ \mu μ ∥ e k ∥ 2 ≤ ∥ ∇ f ( θ k ) ∥ 2 / μ \|e_k\|_2\le\|\nabla f(\theta_k)\|_2/\mu ∥ e k ∥ 2 ≤ ∥∇ f ( θ k ) ∥ 2 / μ η \eta η
常見錯誤
常見錯誤
把負梯度方向當作任意長步都會下降 負梯度在非駐點給出局部下降方向，有限長的步則同時受曲率影響。二次函數的每個誤差分量由 1 − η λ i 1-\eta\lambda_i 1 − η λ i
常見錯誤
改變損失尺度後沿用原來的學習率 ∥ A θ − y ∥ 2 2 \|A\theta-y\|_2^2 ∥ A θ − y ∥ 2 2 ∥ A θ − y ∥ 2 2 / ( 2 n ) \|A\theta-y\|_2^2/(2n) ∥ A θ − y ∥ 2 2 / ( 2 n ) 2 n 2n 2 n
總結
正定二次函數的駐點方程給出唯一最小點。從更新式減去駐點方程，會得到誤差的精確線性遞推。在特徵向量座標中，每個誤差分量乘以 1 − η λ i 1-\eta\lambda_i 1 − η λ i 0 < η < 2 / L 0<\eta<2/L 0 < η < 2/ L
練習
思考檢查
1. 設 Q = diag ( 2 , 5 ) Q=\operatorname{diag}(2,5) Q = diag ( 2 , 5 ) b = ( 4 , − 5 ) ⊤ b=(4,-5)^\top b = ( 4 , − 5 ) ⊤ θ 0 = ( 0 , 1 ) ⊤ \theta_0=(0,1)^\top θ 0 = ( 0 , 1 ) ⊤ η = 1 / 5 \eta=1/5 η = 1/5 思考檢查
2. 設 f ( t ) = 3 ( t + 2 ) 2 f(t)=3(t+2)^2 f ( t ) = 3 ( t + 2 ) 2 t 0 = 0 t_0=0 t 0 = 0 η = 1 / 3 \eta=1/3 η = 1/3 η = 1 / 4 \eta=1/4 η = 1/4 思考檢查
3. 在回歸例題中，把 f f f F = 6 f F=6f F = 6 f f f f η = 1 \eta=1 η = 1 F F F 同時追蹤梯度的倍率與 Hessian 的最大特徵值。
思考檢查
4. 設 f ( θ ) = ( θ 1 − 1 ) 2 / 2 f(\theta)=(\theta_1-1)^2/2 f ( θ ) = ( θ 1 − 1 ) 2 /2 θ 0 = ( 0 , 7 ) ⊤ \theta_0=(0,7)^\top θ 0 = ( 0 , 7 ) ⊤ η = 1 \eta=1 η = 1 解答
解答 · 1. 解駐點方程，再套用兩個誤差乘數 最小點為 θ ⋆ = ( 2 , − 1 ) ⊤ \theta_\star=(2,-1)^\top θ ⋆ = ( 2 , − 1 ) ⊤ L = 5 L=5 L = 5 0 < η < 2 / 5 0<\eta<2/5 0 < η < 2/5 ( − 4 , 10 ) ⊤ (-4,10)^\top ( − 4 , 10 ) ⊤ θ 1 = ( 0 , 1 ) ⊤ − 1 5 ( − 4 , 10 ) ⊤ = ( 4 / 5 , − 1 ) ⊤ \theta_1=(0,1)^\top-\frac15(-4,10)^\top=(4/5,-1)^\top θ 1 = ( 0 , 1 ) ⊤ − 5 1 ( − 4 , 10 ) ⊤ = ( 4/5 , − 1 ) ⊤ 3 / 5 3/5 3/5 0 0 0
解答 · 2. 區分邊界交替與逐漸縮小的交替 導數為 6 ( t + 2 ) 6(t+2) 6 ( t + 2 ) 1 − 6 η 1-6\eta 1 − 6 η η = 1 / 3 \eta=1/3 η = 1/3 − 1 -1 − 1 t 1 = − 4 t_1=-4 t 1 = − 4 t 2 = 0 t_2=0 t 2 = 0 η = 1 / 4 \eta=1/4 η = 1/4 − 1 / 2 -1/2 − 1/2 t 1 = − 3 t_1=-3 t 1 = − 3 t 2 = − 3 / 2 t_2=-3/2 t 2 = − 3/2 − 2 -2 − 2 0 < η < 1 / 3 0<\eta<1/3 0 < η < 1/3
解答 · 3. 學習率與目標倍率成反比 由 ∇ F = 6 ∇ f \nabla F=6\nabla f ∇ F = 6∇ f η F = 1 / 6 \eta_F=1/6 η F = 1/6 L F = 6 L_F=6 L F = 6 0 < η F < 2 / 6 = 1 / 3 0<\eta_F<2/6=1/3 0 < η F < 2/6 = 1/3
解答 · 4. 平坦方向會保留初始座標 梯度為 ( θ 1 − 1 , 0 ) ⊤ (\theta_1-1,0)^\top ( θ 1 − 1 , 0 ) ⊤ ( 1 , 7 ) ⊤ (1,7)^\top ( 1 , 7 ) ⊤ ( 1 , s ) ⊤ (1,s)^\top ( 1 , s ) ⊤ s ∈ R s\in\mathbb R s ∈ R diag ( 1 , 0 ) \operatorname{diag}(1,0) diag ( 1 , 0 )
可接着閱讀最小二乘與殘差 、
SVD 與主成分 ，
或查看課程閱讀書目 。
