從分數到概率模型
仿射分類器計算分數 z = a T θ z = a^{\mathsf T}\theta z = a T θ ,然後按其正負作預測。感知器只用到正負號;邏輯迴歸則更進一步,把分數送進概率模型 ,再選擇使觀察到的標籤具有最大似然的 θ \theta θ 。本節推導所得目標函數、計算導數,並處理一個容易忽略的問題:有限的最佳參數是否存在。
設定。 固定整數 n , d ≥ 1 n, d \ge 1 n , d ≥ 1 、特徵向量 a 1 , … , a n ∈ R d a_1,\dots,a_n \in \mathbb R^d a 1 , … , a n ∈ R d 及觀察到的標籤 y 1 , … , y n ∈ { 0 , 1 } y_1,\dots,y_n \in \{0,1\} y 1 , … , y n ∈ { 0 , 1 } 。令 A ∈ R n × d A \in \mathbb R^{n\times d} A ∈ R n × d 的第 i i i 行為 a i T a_i^{\mathsf T} a i T 。若需要截距,便將每個 a i a_i a i 的某一個分量設為常數 1 1 1 ,使截距成為 θ \theta θ 的一個分量。記 z i = a i T θ z_i = a_i^{\mathsf T}\theta z i = a i T θ ;全文的 log \log log 均為自然對數。
定義 5.2.1
(sigmoid 與 softplus)
sigmoid 與 softplus 函數 R → R \mathbb R\to\mathbb R R → R 定義為
σ ( z ) = 1 1 + e − z , softplus ( z ) = log ( 1 + e z ) . \sigma(z) = \frac{1}{1+e^{-z}}, \qquad \operatorname{softplus}(z) = \log(1+e^{z}). σ ( z ) = 1 + e − z 1 , softplus ( z ) = log ( 1 + e z ) .
sigmoid 把每個分數映到開區間 ( 0 , 1 ) (0,1) ( 0 , 1 ) ,因此可以把它讀作概率。
對參數 θ ∈ R d \theta\in\mathbb R^d θ ∈ R d ,邏輯迴歸模型 假設
P ( Y i = 1 ∣ a i ) = σ ( a i T θ ) . P(Y_i = 1 \mid a_i) = \sigma(a_i^{\mathsf T}\theta). P ( Y i = 1 ∣ a i ) = σ ( a i T θ ) .
這是一項假設,須小心理解:σ ( z i ) \sigma(z_i) σ ( z i ) 是參數為 θ \theta θ 的模型賦予標籤 1 1 1 的概率。數據本身並不能證明真正的數據生成過程具有這個形式。σ ( z i ) \sigma(z_i) σ ( z i ) 接近 1 1 1 表示模型內部 有很高信心,並不代表現實世界中一定如此。
似然與損失
要將似然寫成乘積,我們假設在此模型下,給定固定設計後,Y 1 , … , Y n Y_1,\dots,Y_n Y 1 , … , Y n 條件獨立。每個 y i y_i y i 都是 0 0 0 或 1 1 1 ,所以觀察到該標籤的概率可寫為 σ ( z i ) y i ( 1 − σ ( z i ) ) 1 − y i \sigma(z_i)^{y_i}(1-\sigma(z_i))^{1-y_i} σ ( z i ) y i ( 1 − σ ( z i ) ) 1 − y i :兩個因子中一個等於 1 1 1 ,另一個就是所需的概率。因此似然為
L ( θ ) = ∏ i = 1 n σ ( z i ) y i ( 1 − σ ( z i ) ) 1 − y i . \mathcal L(\theta) = \prod_{i=1}^n \sigma(z_i)^{y_i}\bigl(1-\sigma(z_i)\bigr)^{1-y_i}. L ( θ ) = i = 1 ∏ n σ ( z i ) y i ( 1 − σ ( z i ) ) 1 − y i .
兩個基本恆等式可以簡化對數。首先,1 − σ ( z ) = e − z 1 + e − z = 1 1 + e z = σ ( − z ) 1 - \sigma(z) = \frac{e^{-z}}{1+e^{-z}} = \frac{1}{1+e^{z}} = \sigma(-z) 1 − σ ( z ) = 1 + e − z e − z = 1 + e z 1 = σ ( − z ) ;其次,log σ ( z ) = − log ( 1 + e − z ) = − softplus ( − z ) \log \sigma(z) = -\log(1+e^{-z}) = -\operatorname{softplus}(-z) log σ ( z ) = − log ( 1 + e − z ) = − softplus ( − z ) 。由此亦得 log ( 1 − σ ( z ) ) = − softplus ( z ) \log(1-\sigma(z)) = -\operatorname{softplus}(z) log ( 1 − σ ( z )) = − softplus ( z ) 。所以單個標籤的負對數概率,作為分數的函數,是
ℓ ( z , 1 ) = softplus ( − z ) , ℓ ( z , 0 ) = softplus ( z ) . \ell(z,1) = \operatorname{softplus}(-z), \qquad \ell(z,0) = \operatorname{softplus}(z). ℓ ( z , 1 ) = softplus ( − z ) , ℓ ( z , 0 ) = softplus ( z ) .
再利用 softplus ( − z ) = log e z + 1 e z = softplus ( z ) − z \operatorname{softplus}(-z) = \log\frac{e^{z}+1}{e^{z}} = \operatorname{softplus}(z) - z softplus ( − z ) = log e z e z + 1 = softplus ( z ) − z ,便可把兩種情況合併為
ℓ ( z , y ) = softplus ( z ) − y z . \ell(z,y) = \operatorname{softplus}(z) - yz. ℓ ( z , y ) = softplus ( z ) − y z .
將各樣本損失取平均,得到平均負對數似然
L ( θ ) = − 1 n log L ( θ ) = 1 n ∑ i = 1 n [ softplus ( z i ) − y i z i ] . L(\theta) = -\frac1n \log \mathcal L(\theta) = \frac1n \sum_{i=1}^n \bigl[\operatorname{softplus}(z_i) - y_i z_i\bigr]. L ( θ ) = − n 1 log L ( θ ) = n 1 i = 1 ∑ n [ softplus ( z i ) − y i z i ] .
一旦寫出 L L L ,對於給定的特徵及標籤列表,它就是 θ \theta θ 的確定性函數。以下分析的都是這個函數,並不需要獨立性、同分布抽樣,亦不需要假設模型設定正確。條件似然的解讀需要條件獨立性及上述模型,但不要求不同特徵對應相同的響應概率。
係數只依訓練數據擬合。最小化 L L L 並不保證對新個案的概率校準或樣本外準確率。損失亦沒有上界:ℓ ( z , 1 ) = softplus ( − z ) ≥ − z \ell(z,1) = \operatorname{softplus}(-z) \ge -z ℓ ( z , 1 ) = softplus ( − z ) ≥ − z ,因此對新例子作出非常自信但錯誤的分數,可能招致任意大的損失。
穩定計算。 當 z z z 很大且為正時,直接在浮點數中計算 log ( 1 + e z ) \log(1+e^{z}) log ( 1 + e z ) 會溢出。按符號分情況:若 z ≥ 0 z \ge 0 z ≥ 0 ,則 log ( 1 + e z ) = z + log ( 1 + e − z ) \log(1+e^{z}) = z + \log(1+e^{-z}) log ( 1 + e z ) = z + log ( 1 + e − z ) ;若 z < 0 z \lt 0 z < 0 ,原式已可安全計算。兩種情況可合寫為
softplus ( z ) = max ( z , 0 ) + log ( 1 + e − ∣ z ∣ ) , \operatorname{softplus}(z) = \max(z,0) + \log\bigl(1+e^{-|z|}\bigr), softplus ( z ) = max ( z , 0 ) + log ( 1 + e − ∣ z ∣ ) ,
因此
ℓ ( z , y ) = max ( z , 0 ) − y z + log1p ( exp ( − ∣ z ∣ ) ) . \ell(z,y) = \max(z,0) - yz + \operatorname{log1p}\bigl(\exp(-|z|)\bigr). ℓ ( z , y ) = max ( z , 0 ) − y z + log1p ( exp ( − ∣ z ∣ ) ) .
這裏指數函數的輸入永不為正。
照寫 log ( 1 + exp ( z ) ) \log(1+\exp(z)) log ( 1 + exp ( z )) 的程式在兩端都會出錯。z z z 為很大的正數時,指數溢出;z z z 為很大的負數時,和 1 + e z 1+e^{z} 1 + e z 捨入後恰為 1 1 1 ,對數返回 0 0 0 ,微小的正損失便丟失了。上面的分情況寫法解決第一個問題;log1p \operatorname{log1p} log1p 能對極小的 u u u 準確計算 log ( 1 + u ) \log(1+u) log ( 1 + u ) ,解決第二個問題。
雙精度在約 1.8 × 10 308 1.8\times10^{308} 1.8 × 1 0 308 以上溢出,即 e z e^{z} e z 在 z z z 大於約 709.8 709.8 709.8 時溢出;它在 1 1 1 附近的相對間距約為 2.2 × 10 − 16 2.2\times10^{-16} 2.2 × 1 0 − 16 。
取 z = 800 z=800 z = 800 、y = 0 y=0 y = 0 。字面公式 log ( 1 + e 800 ) \log(1+e^{800}) log ( 1 + e 800 ) 溢出,因為 e 800 ≈ 10 347 e^{800}\approx10^{347} e 800 ≈ 1 0 347 。穩定公式給出 max ( 800 , 0 ) − 0 + log1p ( e − 800 ) = 800 \max(800,0)-0+\operatorname{log1p}(e^{-800})=800 max ( 800 , 0 ) − 0 + log1p ( e − 800 ) = 800 :e − 800 e^{-800} e − 800 下溢為 0 0 0 ,在這裏無害。精確損失比 800 800 800 大不足 10 − 347 10^{-347} 1 0 − 347 。
取 z = 40 z=40 z = 40 、y = 1 y=1 y = 1 。精確損失是 softplus ( − 40 ) = log ( 1 + e − 40 ) \operatorname{softplus}(-40)=\log(1+e^{-40}) softplus ( − 40 ) = log ( 1 + e − 40 ) ,其中 e − 40 ≈ 4.25 × 10 − 18 e^{-40}\approx4.25\times10^{-18} e − 40 ≈ 4.25 × 1 0 − 18 。按字面計算,1 + 4.25 × 10 − 18 1+4.25\times10^{-18} 1 + 4.25 × 1 0 − 18 捨入為 1 1 1 ,結果是 0 0 0 。穩定公式給出 40 − 40 + log1p ( e − 40 ) ≈ 4.25 × 10 − 18 40-40+\operatorname{log1p}(e^{-40})\approx4.25\times10^{-18} 40 − 40 + log1p ( e − 40 ) ≈ 4.25 × 1 0 − 18 ;由於 log ( 1 + u ) = u − u 2 / 2 + ⋯ \log(1+u)=u-u^2/2+\cdots log ( 1 + u ) = u − u 2 /2 + ⋯ ,這個值具有完整的相對精度。
每個損失項都是某個數的 softplus,因此嚴格為正。於是對每個 θ \theta θ 都有 L ( θ ) > 0 L(\theta) \gt 0 L ( θ ) > 0 ;下文會多次用到這點。
導數
對每個實數 z z z ,σ ′ ( z ) = σ ( z ) ( 1 − σ ( z ) ) \sigma'(z) = \sigma(z)\bigl(1-\sigma(z)\bigr) σ ′ ( z ) = σ ( z ) ( 1 − σ ( z ) ) ,而且 0 < σ ( z ) ( 1 − σ ( z ) ) ≤ 1 4 0 \lt \sigma(z)(1-\sigma(z)) \le \tfrac14 0 < σ ( z ) ( 1 − σ ( z )) ≤ 4 1 ,等號恰在 z = 0 z = 0 z = 0 成立。此外,softplus ′ ( z ) = σ ( z ) \operatorname{softplus}'(z) = \sigma(z) softplus ′ ( z ) = σ ( z ) 。
對 σ ( z ) = ( 1 + e − z ) − 1 \sigma(z) = (1+e^{-z})^{-1} σ ( z ) = ( 1 + e − z ) − 1 求導:
σ ′ ( z ) = e − z ( 1 + e − z ) 2 = σ ( z ) ⋅ e − z 1 + e − z = σ ( z ) ( 1 − σ ( z ) ) . \sigma'(z) = \frac{e^{-z}}{(1+e^{-z})^2} = \sigma(z)\cdot\frac{e^{-z}}{1+e^{-z}} = \sigma(z)\bigl(1-\sigma(z)\bigr). σ ′ ( z ) = ( 1 + e − z ) 2 e − z = σ ( z ) ⋅ 1 + e − z e − z = σ ( z ) ( 1 − σ ( z ) ) . 令 p = σ ( z ) ∈ ( 0 , 1 ) p = \sigma(z) \in (0,1) p = σ ( z ) ∈ ( 0 , 1 ) 。則 p ( 1 − p ) > 0 p(1-p) \gt 0 p ( 1 − p ) > 0 ,並且 p ( 1 − p ) = 1 4 − ( p − 1 2 ) 2 ≤ 1 4 p(1-p) = \tfrac14 - (p-\tfrac12)^2 \le \tfrac14 p ( 1 − p ) = 4 1 − ( p − 2 1 ) 2 ≤ 4 1 ;等號成立當且僅當 p = 1 2 p = \tfrac12 p = 2 1 ,亦即 z = 0 z = 0 z = 0 。最後,d d z log ( 1 + e z ) = e z 1 + e z = σ ( z ) \frac{d}{dz}\log(1+e^z) = \frac{e^z}{1+e^z} = \sigma(z) d z d log ( 1 + e z ) = 1 + e z e z = σ ( z ) 。
因此 ∂ z ℓ ( z , y ) = σ ( z ) − y \partial_z \ell(z,y) = \sigma(z) - y ∂ z ℓ ( z , y ) = σ ( z ) − y ,且 ∂ z 2 ℓ ( z , y ) = σ ( z ) ( 1 − σ ( z ) ) \partial_z^2 \ell(z,y) = \sigma(z)(1-\sigma(z)) ∂ z 2 ℓ ( z , y ) = σ ( z ) ( 1 − σ ( z )) 。一階導數是模型概率減去觀察標籤,也就是殘差。
定理 5.2.5
(梯度、Hessian 與曲率界)
對所有 θ ∈ R d \theta \in \mathbb R^d θ ∈ R d ,
∇ L ( θ ) = 1 n ∑ i = 1 n ( σ ( z i ) − y i ) a i , ∇ 2 L ( θ ) = 1 n ∑ i = 1 n σ ( z i ) ( 1 − σ ( z i ) ) a i a i T . \nabla L(\theta) = \frac1n\sum_{i=1}^n \bigl(\sigma(z_i) - y_i\bigr)a_i, \qquad
\nabla^2 L(\theta) = \frac1n\sum_{i=1}^n \sigma(z_i)\bigl(1-\sigma(z_i)\bigr)a_i a_i^{\mathsf T}. ∇ L ( θ ) = n 1 i = 1 ∑ n ( σ ( z i ) − y i ) a i , ∇ 2 L ( θ ) = n 1 i = 1 ∑ n σ ( z i ) ( 1 − σ ( z i ) ) a i a i T . Hessian 滿足 0 ⪯ ∇ 2 L ( θ ) ⪯ ∥ A ∥ 2 2 4 n I 0 \preceq \nabla^2 L(\theta) \preceq \dfrac{\|A\|_2^2}{4n} I 0 ⪯ ∇ 2 L ( θ ) ⪯ 4 n ∥ A ∥ 2 2 I 。因此 L L L 是凸函數。
分數對 θ \theta θ 是線性的,所以 ∇ θ z i = a i \nabla_\theta z_i = a_i ∇ θ z i = a i 。對 ℓ ( z i , y i ) \ell(z_i,y_i) ℓ ( z i , y i ) 使用鏈式法則,得到梯度項 ( σ ( z i ) − y i ) a i (\sigma(z_i)-y_i)a_i ( σ ( z i ) − y i ) a i ;再求導一次,得到 σ ′ ( z i ) a i a i T \sigma'(z_i)\,a_i a_i^{\mathsf T} σ ′ ( z i ) a i a i T 。
記 w i = σ ( z i ) ( 1 − σ ( z i ) ) w_i = \sigma(z_i)(1-\sigma(z_i)) w i = σ ( z i ) ( 1 − σ ( z i )) 。對任意 v ∈ R d v \in \mathbb R^d v ∈ R d ,
v T ∇ 2 L ( θ ) v = 1 n ∑ i = 1 n w i ( a i T v ) 2 . v^{\mathsf T}\nabla^2 L(\theta)v = \frac1n\sum_{i=1}^n w_i\,(a_i^{\mathsf T}v)^2. v T ∇ 2 L ( θ ) v = n 1 i = 1 ∑ n w i ( a i T v ) 2 . 每個 w i w_i w i 為正,所以總和至少為 0 0 0 。每個 w i w_i w i 亦至多為 1 4 \tfrac14 4 1 ,故總和至多為 1 4 n ∑ i ( a i T v ) 2 = ∥ A v ∥ 2 4 n ≤ ∥ A ∥ 2 2 4 n ∥ v ∥ 2 \frac1{4n}\sum\limits_i (a_i^{\mathsf T}v)^2 = \frac{\|Av\|^2}{4n} \le \frac{\|A\|_2^2}{4n}\|v\|^2 4 n 1 i ∑ ( a i T v ) 2 = 4 n ∥ A v ∥ 2 ≤ 4 n ∥ A ∥ 2 2 ∥ v ∥ 2 。
Hessian 處處半正定的函數是凸函數。
凸性不等於嚴格凸性。假設存在 v ≠ 0 v \ne 0 v = 0 使 A v = 0 Av = 0 A v = 0 ;當 A A A 的秩小於 d d d 時便會如此。沿方向 v v v 的所有分數都不變,所以對每個實數 t t t ,L ( θ + t v ) = L ( θ ) L(\theta + tv) = L(\theta) L ( θ + t v ) = L ( θ ) 。若存在最小解,它便是一整條最小解直線上的一點。凸性亦不保證最小解存在,以下例子會展示這兩種情況。
概念視角 代數
駐點條件就是矩匹配 令梯度為零,即 A T ( σ ( A θ ) − y ) = 0 A^{\mathsf T}\bigl(\sigma(A\theta)-y\bigr)=0 A T ( σ ( A θ ) − y ) = 0 :擬合概率減標籤所得的向量與 A A A 的每一列都正交。等價地,∑ i σ ( z i ) a i = ∑ i y i a i \sum\limits_i\sigma(z_i)a_i=\sum\limits_iy_ia_i i ∑ σ ( z i ) a i = i ∑ y i a i ,即每個特徵的擬合總和等於其觀測總和。若有全為一的截距列,平均擬合概率便等於訓練數據中標籤為一的比例。當不同的特徵向量線性無關時(如下面的例題),這些總和相符便迫使每組的擬合概率等於該組的觀測比例。
加懲罰的目標函數
對 λ > 0 \lambda \gt 0 λ > 0 ,定義
L λ ( θ ) = L ( θ ) + λ 2 ∥ θ ∥ 2 , L_\lambda(\theta) = L(\theta) + \frac\lambda2\|\theta\|^2, L λ ( θ ) = L ( θ ) + 2 λ ∥ θ ∥ 2 ,
其中懲罰涵蓋 θ \theta θ 的每個 分量,包括截距分量(若有)。其 Hessian 為 ∇ 2 L ( θ ) + λ I \nabla^2 L(\theta) + \lambda I ∇ 2 L ( θ ) + λ I ,所以
λ I ⪯ ∇ 2 L λ ( θ ) ⪯ ( λ + ∥ A ∥ 2 2 4 n ) I . \lambda I \preceq \nabla^2 L_\lambda(\theta) \preceq \Bigl(\lambda + \frac{\|A\|_2^2}{4n}\Bigr)I. λ I ⪯ ∇ 2 L λ ( θ ) ⪯ ( λ + 4 n ∥ A ∥ 2 2 ) I .
設 λ > 0 \lambda \gt 0 λ > 0 。則 L λ L_\lambda L λ 恰有一個全局最小解 θ ⋆ \theta^\star θ ⋆ 。它滿足 ∥ θ ⋆ ∥ ≤ 2 log 2 / λ \|\theta^\star\| \le \sqrt{2\log 2/\lambda} ∥ θ ⋆ ∥ ≤ 2 log 2/ λ ,並由駐點條件 ∇ L λ ( θ ⋆ ) = 0 \nabla L_\lambda(\theta^\star) = 0 ∇ L λ ( θ ⋆ ) = 0 刻畫,即
λ θ ⋆ = − 1 n A T ( σ ( A θ ⋆ ) − y ) , \lambda\theta^\star = -\frac1n A^{\mathsf T}\bigl(\sigma(A\theta^\star) - y\bigr), λ θ ⋆ = − n 1 A T ( σ ( A θ ⋆ ) − y ) , 其中 σ \sigma σ 對向量逐個分量作用。
存在性。 因為 L ≥ 0 L \ge 0 L ≥ 0 ,所以 L λ ( θ ) ≥ λ 2 ∥ θ ∥ 2 L_\lambda(\theta) \ge \frac\lambda2\|\theta\|^2 L λ ( θ ) ≥ 2 λ ∥ θ ∥ 2 。在 θ = 0 \theta = 0 θ = 0 時,所有分數均為 0 0 0 ,而 softplus ( 0 ) = log 2 \operatorname{softplus}(0) = \log 2 softplus ( 0 ) = log 2 ,故 L λ ( 0 ) = log 2 L_\lambda(0) = \log 2 L λ ( 0 ) = log 2 。
考慮次水平集 S = { θ : L λ ( θ ) ≤ log 2 } S = \{\theta : L_\lambda(\theta) \le \log 2\} S = { θ : L λ ( θ ) ≤ log 2 } 。它包含 0 0 0 ,因而非空;由 L λ L_\lambda L λ 的連續性,它是閉集。它包含於半徑 2 log 2 / λ \sqrt{2\log2/\lambda} 2 log 2/ λ 的球內,因此有界。故 S S S 緊緻,連續函數 L λ L_\lambda L λ 在 S S S 上於某點 θ ⋆ \theta^\star θ ⋆ 取到最小值。S S S 以外的值都大於 log 2 ≥ L λ ( θ ⋆ ) \log 2 \ge L_\lambda(\theta^\star) log 2 ≥ L λ ( θ ⋆ ) ,所以 θ ⋆ \theta^\star θ ⋆ 是全局最小解。
唯一性。 取 θ ≠ θ ′ \theta \ne \theta' θ = θ ′ ,令 g ( t ) = L λ ( θ + t ( θ ′ − θ ) ) g(t) = L_\lambda(\theta + t(\theta'-\theta)) g ( t ) = L λ ( θ + t ( θ ′ − θ )) 。則 g ′ ′ ( t ) ≥ λ ∥ θ ′ − θ ∥ 2 > 0 g''(t) \ge \lambda\|\theta'-\theta\|^2 \gt 0 g ′′ ( t ) ≥ λ ∥ θ ′ − θ ∥ 2 > 0 ,故 g g g 嚴格凸。若 θ \theta θ 和 θ ′ \theta' θ ′ 都是最小解,便有 g ( 1 2 ) < 1 2 ( g ( 0 ) + g ( 1 ) ) g(\tfrac12) \lt \tfrac12(g(0)+g(1)) g ( 2 1 ) < 2 1 ( g ( 0 ) + g ( 1 )) ,右邊正是最小值,矛盾。
刻畫。 可微函數在任何最小解處的梯度均為零。反過來,若 ∇ L λ ( θ ) = 0 \nabla L_\lambda(\theta) = 0 ∇ L λ ( θ ) = 0 ,則通過 θ \theta θ 的每條直線上的限制函數 g g g 都是凸的,且 g ′ ( 0 ) = 0 g'(0) = 0 g ′ ( 0 ) = 0 ,所以 g ( 1 ) ≥ g ( 0 ) g(1) \ge g(0) g ( 1 ) ≥ g ( 0 ) ,故 θ \theta θ 為全局最小解。
證明透視
懲罰項在哪裏起作用 存在性論證只透過兩項事實用到數據:L ≥ 0 L\ge0 L ≥ 0 及 L L L 連續。兩者都不能令次水平集有界:對可分數據,集合 { L ≤ log 2 } \{L\le\log2\} { L ≤ log 2 } 包含一整條射線,下文關於可分數據的一節會說明這點。真正把所有候選困在一個球內的,是不等式 L λ ( θ ) ≥ λ 2 ∥ θ ∥ 2 L_\lambda(\theta)\ge\frac\lambda2\|\theta\|^2 L λ ( θ ) ≥ 2 λ ∥ θ ∥ 2 ;球的緊緻性隨即給出最小解。
唯一性第二次用到懲罰項,透過曲率下界 ∇ 2 L λ ⪰ λ I \nabla^2L_\lambda\succeq\lambda I ∇ 2 L λ ⪰ λ I 。沒有它,A A A 的零空間方向 v v v 使 L L L 沿 θ + t v \theta+tv θ + t v 保持不變,一個最小解便帶著整條直線的其他最小解;練習中有這樣的直線。
刻畫一步完全不用 λ \lambda λ :對任何可微凸函數,駐點都是全局最小解。所以當 λ = 0 \lambda=0 λ = 0 ,∇ L \nabla L ∇ L 的零點仍是最大似然估計;可能失敗的只是這樣的零點是否存在、是否唯一。
此定理不涵蓋不懲罰截距的常見變體。
若截距不在懲罰之內,沿截距方向下界 λ 2 ∥ θ ∥ 2 \frac\lambda2\|\theta\|^2 2 λ ∥ θ ∥ 2 不再成立,最小解可能不存在。例如,設所有標籤均為 1 1 1 ,把所有斜率分量設為 0 0 0 ,令截距 b b b 趨向 ∞ \infty ∞ 。此時目標函數等於 softplus ( − b ) \operatorname{softplus}(-b) softplus ( − b ) ,它恆正並趨向 0 0 0 ,所以其下確界永遠取不到。
梯度下降的保證
設 λ > 0 \lambda \gt 0 λ > 0 、M = λ + ∥ A ∥ 2 2 / ( 4 n ) M = \lambda + \|A\|_2^2/(4n) M = λ + ∥ A ∥ 2 2 / ( 4 n ) 、η = 1 / M \eta = 1/M η = 1/ M ,並迭代 θ k + 1 = θ k − η ∇ L λ ( θ k ) \theta_{k+1} = \theta_k - \eta\nabla L_\lambda(\theta_k) θ k + 1 = θ k − η ∇ L λ ( θ k ) 。記 L λ ⋆ = L λ ( θ ⋆ ) L_\lambda^\star = L_\lambda(\theta^\star) L λ ⋆ = L λ ( θ ⋆ ) ,則
L λ ( θ k ) − L λ ⋆ ≤ ( 1 − λ M ) k ( L λ ( θ 0 ) − L λ ⋆ ) , ∥ θ k − θ ⋆ ∥ 2 ≤ 2 λ ( L λ ( θ k ) − L λ ⋆ ) . L_\lambda(\theta_k) - L_\lambda^\star \le \Bigl(1 - \frac{\lambda}{M}\Bigr)^k\bigl(L_\lambda(\theta_0) - L_\lambda^\star\bigr), \qquad \|\theta_k - \theta^\star\|^2 \le \frac2\lambda\bigl(L_\lambda(\theta_k) - L_\lambda^\star\bigr). L λ ( θ k ) − L λ ⋆ ≤ ( 1 − M λ ) k ( L λ ( θ 0 ) − L λ ⋆ ) , ∥ θ k − θ ⋆ ∥ 2 ≤ λ 2 ( L λ ( θ k ) − L λ ⋆ ) . 若改為 λ = 0 \lambda = 0 λ = 0 且 A ≠ 0 A \ne 0 A = 0 ,令 M 0 = ∥ A ∥ 2 2 / ( 4 n ) M_0 = \|A\|_2^2/(4n) M 0 = ∥ A ∥ 2 2 / ( 4 n ) ,使用步長 1 / M 0 1/M_0 1/ M 0 。則 L ( θ k ) L(\theta_k) L ( θ k ) 的值不遞增,且
min 0 ≤ k ≤ K ∥ ∇ L ( θ k ) ∥ 2 ≤ 2 M 0 L ( θ 0 ) K + 1 . \min_{0\le k\le K}\|\nabla L(\theta_k)\|^2 \le \frac{2M_0 L(\theta_0)}{K+1}. 0 ≤ k ≤ K min ∥∇ L ( θ k ) ∥ 2 ≤ K + 1 2 M 0 L ( θ 0 ) . 在 λ = 0 \lambda = 0 λ = 0 的情況下,這裏不聲稱迭代點收斂。
設 f f f 二次可微,且 ∇ 2 f ⪯ M I \nabla^2 f \preceq MI ∇ 2 f ⪯ M I 。帶積分餘項的 Taylor 公式給出
f ( θ + h ) = f ( θ ) + ∇ f ( θ ) T h + ∫ 0 1 ( 1 − t ) h T ∇ 2 f ( θ + t h ) h d t ≤ f ( θ ) + ∇ f ( θ ) T h + M 2 ∥ h ∥ 2 . f(\theta+h) = f(\theta) + \nabla f(\theta)^{\mathsf T}h + \int_0^1(1-t)\,h^{\mathsf T}\nabla^2 f(\theta+th)h\,dt \le f(\theta) + \nabla f(\theta)^{\mathsf T}h + \frac M2\|h\|^2. f ( θ + h ) = f ( θ ) + ∇ f ( θ ) T h + ∫ 0 1 ( 1 − t ) h T ∇ 2 f ( θ + t h ) h d t ≤ f ( θ ) + ∇ f ( θ ) T h + 2 M ∥ h ∥ 2 . 令 g = ∇ f ( θ ) g = \nabla f(\theta) g = ∇ f ( θ ) ,取 h = − g / M h = -g/M h = − g / M ,便得 f ( θ + h ) ≤ f ( θ ) − ∥ g ∥ 2 / ( 2 M ) f(\theta+h) \le f(\theta) - \|g\|^2/(2M) f ( θ + h ) ≤ f ( θ ) − ∥ g ∥ 2 / ( 2 M ) 。
對 f = L λ f = L_\lambda f = L λ ,Hessian 下界 ∇ 2 f ⪰ λ I \nabla^2 f \succeq \lambda I ∇ 2 f ⪰ λ I 給出 f ( θ ⋆ ) ≥ f ( θ ) + g T u + λ 2 ∥ u ∥ 2 f(\theta^\star) \ge f(\theta) + g^{\mathsf T}u + \frac\lambda2\|u\|^2 f ( θ ⋆ ) ≥ f ( θ ) + g T u + 2 λ ∥ u ∥ 2 ,其中 u = θ ⋆ − θ u = \theta^\star - \theta u = θ ⋆ − θ 。在所有 u u u 中,右邊於 u = − g / λ u = -g/\lambda u = − g / λ 時最小,因此 f ⋆ ≥ f ( θ ) − ∥ g ∥ 2 / ( 2 λ ) f^\star \ge f(\theta) - \|g\|^2/(2\lambda) f ⋆ ≥ f ( θ ) − ∥ g ∥ 2 / ( 2 λ ) ,即 ∥ g ∥ 2 ≥ 2 λ ( f ( θ ) − f ⋆ ) \|g\|^2 \ge 2\lambda(f(\theta) - f^\star) ∥ g ∥ 2 ≥ 2 λ ( f ( θ ) − f ⋆ ) 。
結合兩個不等式,得到 f ( θ k + 1 ) − f ⋆ ≤ ( 1 − λ / M ) ( f ( θ k ) − f ⋆ ) f(\theta_{k+1}) - f^\star \le (1-\lambda/M)(f(\theta_k)-f^\star) f ( θ k + 1 ) − f ⋆ ≤ ( 1 − λ / M ) ( f ( θ k ) − f ⋆ ) ;反覆應用便證得第一個界。把同一曲率下界應用於梯度為零的 θ ⋆ \theta^\star θ ⋆ ,得到 f ( θ ) − f ⋆ ≥ λ 2 ∥ θ − θ ⋆ ∥ 2 f(\theta) - f^\star \ge \frac\lambda2\|\theta-\theta^\star\|^2 f ( θ ) − f ⋆ ≥ 2 λ ∥ θ − θ ⋆ ∥ 2 。
當 λ = 0 \lambda = 0 λ = 0 ,對 k = 0 , … , K k = 0,\dots,K k = 0 , … , K 的下降不等式求和。由於 L > 0 L \gt 0 L > 0 ,下降量之和至多為 L ( θ 0 ) L(\theta_0) L ( θ 0 ) ,所以 ∑ k = 0 K ∥ ∇ L ( θ k ) ∥ 2 ≤ 2 M 0 L ( θ 0 ) \sum\limits_{k=0}^K\|\nabla L(\theta_k)\|^2 \le 2M_0L(\theta_0) k = 0 ∑ K ∥∇ L ( θ k ) ∥ 2 ≤ 2 M 0 L ( θ 0 ) 。K + 1 K+1 K + 1 項中的最小值至多等於其平均值。
例題:只有截距的模型
設 n = 4 n = 4 n = 4 、d = 1 d = 1 d = 1 、每個 a i = 1 a_i = 1 a i = 1 ,標籤為 ( 0 , 1 , 1 , 1 ) (0,1,1,1) ( 0 , 1 , 1 , 1 ) ,且 λ = 0 \lambda = 0 λ = 0 。每個分數都等於純量參數 z z z 。由於 ∑ i y i = 3 \sum\limits_i y_i = 3 i ∑ y i = 3 ,
L ( z ) = softplus ( z ) − 3 4 z , L ′ ( z ) = σ ( z ) − 3 4 , L ′ ′ ( z ) = σ ( z ) ( 1 − σ ( z ) ) > 0. L(z) = \operatorname{softplus}(z) - \tfrac34 z, \qquad L'(z) = \sigma(z) - \tfrac34, \qquad L''(z) = \sigma(z)(1-\sigma(z)) \gt 0. L ( z ) = softplus ( z ) − 4 3 z , L ′ ( z ) = σ ( z ) − 4 3 , L ′′ ( z ) = σ ( z ) ( 1 − σ ( z )) > 0. L L L 嚴格凸,所以至多有一個駐點,而任何駐點都是唯一全局最小解。解 σ ( z ) = 3 4 \sigma(z) = \tfrac34 σ ( z ) = 4 3 :
1 + e − z = 4 3 ⟹ e − z = 1 3 ⟹ z ⋆ = log 3. 1 + e^{-z} = \tfrac43 \;\Longrightarrow\; e^{-z} = \tfrac13 \;\Longrightarrow\; z^\star = \log 3. 1 + e − z = 3 4 ⟹ e − z = 3 1 ⟹ z ⋆ = log 3. 擬合概率 σ ( log 3 ) = 3 4 \sigma(\log 3) = \tfrac34 σ ( log 3 ) = 4 3 ,恰等於訓練數據中標籤為 1 1 1 的比例。由 softplus ( log 3 ) = log 4 \operatorname{softplus}(\log 3) = \log 4 softplus ( log 3 ) = log 4 ,最小值為
L ( log 3 ) = log 4 − 3 4 log 3 ≈ 0.5623 , L(\log 3) = \log 4 - \tfrac34\log 3 \approx 0.5623, L ( log 3 ) = log 4 − 4 3 log 3 ≈ 0.5623 , 低於 L ( 0 ) = log 2 ≈ 0.6931 L(0) = \log 2 \approx 0.6931 L ( 0 ) = log 2 ≈ 0.6931 。
一步梯度下降。 這裏 A A A 是由四個 1 1 1 組成的列向量,所以 ∥ A ∥ 2 2 = 4 \|A\|_2^2 = 4 ∥ A ∥ 2 2 = 4 ,且 M 0 = 4 / 16 = 1 4 M_0 = 4/16 = \tfrac14 M 0 = 4/16 = 4 1 ,與直接得到的界 L ′ ′ ≤ 1 4 L'' \le \tfrac14 L ′′ ≤ 4 1 一致。從 θ 0 = 0 \theta_0 = 0 θ 0 = 0 開始,取步長 η = 1 \eta = 1 η = 1 ,遠小於 1 / M 0 = 4 1/M_0 = 4 1/ M 0 = 4 :
L ′ ( 0 ) = 1 2 − 3 4 = − 1 4 , θ 1 = 0 − 1 ⋅ ( − 1 4 ) = 1 4 . L'(0) = \tfrac12 - \tfrac34 = -\tfrac14, \qquad \theta_1 = 0 - 1\cdot\bigl(-\tfrac14\bigr) = \tfrac14. L ′ ( 0 ) = 2 1 − 4 3 = − 4 1 , θ 1 = 0 − 1 ⋅ ( − 4 1 ) = 4 1 . 現在四個例子都得到模型概率 σ ( 1 4 ) = 1 / ( 1 + e − 1 / 4 ) ≈ 0.5622 \sigma(\tfrac14) = 1/(1+e^{-1/4}) \approx 0.5622 σ ( 4 1 ) = 1/ ( 1 + e − 1/4 ) ≈ 0.5622 ,由 0.5 0.5 0.5 上升。
在下降引理中取 h = − η g h = -\eta g h = − η g ,得
L ( θ 1 ) ≤ L ( 0 ) − η g 2 + M 0 2 η 2 g 2 = log 2 − 1 16 + 1 128 = log 2 − 7 128 ≈ 0.63846. L(\theta_1) \le L(0) - \eta g^2 + \tfrac{M_0}{2}\eta^2 g^2 = \log 2 - \tfrac1{16} + \tfrac1{128} = \log 2 - \tfrac7{128} \approx 0.63846. L ( θ 1 ) ≤ L ( 0 ) − η g 2 + 2 M 0 η 2 g 2 = log 2 − 16 1 + 128 1 = log 2 − 128 7 ≈ 0.63846. 直接計算得 L ( 1 4 ) = softplus ( 1 4 ) − 3 16 ≈ 0.82594 − 0.1875 = 0.63844 L(\tfrac14) = \operatorname{softplus}(\tfrac14) - \tfrac3{16} \approx 0.82594 - 0.1875 = 0.63844 L ( 4 1 ) = softplus ( 4 1 ) − 16 3 ≈ 0.82594 − 0.1875 = 0.63844 ,與上界相符。
正是互相衝突的標籤使這個最小解有限。四行有相同的特徵向量,任何參數都不能給它們不同的分數;模型只能給出一個共同概率。這些相同特徵對應不同標籤 的情況是數據的性質,不能與分數平手 混淆。決策規則「當且僅當 σ ( z ) ≥ 1 2 \sigma(z) \ge \tfrac12 σ ( z ) ≥ 2 1 時預測為 1 1 1 」,等價於「當且僅當 z ≥ 0 z \ge 0 z ≥ 0 」,按慣例把恰為 0 0 0 的分數歸入正類。這是規則的確定性設定,並不說明標籤如何。在擬合結果 θ ⋆ = log 3 \theta^\star=\log 3 θ ⋆ = log 3 下,每行均預測為正類,標籤為 0 0 0 的一行因而被錯誤分類。對任何 θ \theta θ ,由於衝突標籤具有相同分數,至少有一行被錯誤分類。
反例模式
凸,甚至嚴格凸,卻沒有最小解 將標籤改為 ( 1 , 1 , 1 , 1 ) (1,1,1,1) ( 1 , 1 , 1 , 1 ) ,保留 a i = 1 a_i = 1 a i = 1 和 λ = 0 \lambda = 0 λ = 0 。則 L ( z ) = softplus ( − z ) L(z) = \operatorname{softplus}(-z) L ( z ) = softplus ( − z ) 。對每個有限 z z z ,此值均為正,且 L ′ ( z ) = σ ( z ) − 1 < 0 L'(z) = \sigma(z) - 1 \lt 0 L ′ ( z ) = σ ( z ) − 1 < 0 。當 z → ∞ z \to \infty z → ∞ ,L ( z ) → 0 L(z) \to 0 L ( z ) → 0 。下確界 0 0 0 可被逼近但永遠取不到,所以即使處處有 L ′ ′ > 0 L'' \gt 0 L ′′ > 0 ,最大似然估計也不存在。
現在加入 λ > 0 \lambda \gt 0 λ > 0 的懲罰:
L λ ( z ) = softplus ( − z ) + λ 2 z 2 , L λ ′ ( z ) = λ z − σ ( − z ) . L_\lambda(z) = \operatorname{softplus}(-z) + \tfrac\lambda2 z^2, \qquad L_\lambda'(z) = \lambda z - \sigma(-z). L λ ( z ) = softplus ( − z ) + 2 λ z 2 , L λ ′ ( z ) = λ z − σ ( − z ) . 因為 L λ ′ ′ = λ + σ ( z ) ( 1 − σ ( z ) ) > 0 L_\lambda'' = \lambda + \sigma(z)(1-\sigma(z)) \gt 0 L λ ′′ = λ + σ ( z ) ( 1 − σ ( z )) > 0 ,導數 L λ ′ L_\lambda' L λ ′ 嚴格遞增。左端 L λ ′ ( 0 ) = − 1 2 L_\lambda'(0) = -\tfrac12 L λ ′ ( 0 ) = − 2 1 ,右端 L λ ′ ( 1 2 λ ) = 1 2 − σ ( − 1 2 λ ) > 0 L_\lambda'\bigl(\tfrac1{2\lambda}\bigr) = \tfrac12 - \sigma\bigl(-\tfrac1{2\lambda}\bigr) \gt 0 L λ ′ ( 2 λ 1 ) = 2 1 − σ ( − 2 λ 1 ) > 0 ,因此恰有一個根 z λ ⋆ ∈ ( 0 , 1 2 λ ) z^\star_\lambda \in \bigl(0, \tfrac1{2\lambda}\bigr) z λ ⋆ ∈ ( 0 , 2 λ 1 ) 。
此根由 λ z = 1 / ( 1 + e z ) \lambda z = 1/(1+e^{z}) λ z = 1/ ( 1 + e z ) 隱式定義,沒有初等閉式,須以數值方法計算。當 λ = 1 2 \lambda = \tfrac12 λ = 2 1 ,根約為 0.675 0.675 0.675 ,擬合概率約為 0.663 0.663 0.663 。
一般可分數據
若存在某個 θ ˉ ∈ R d \bar\theta\in\mathbb R^d θ ˉ ∈ R d ,使得 y i = 1 y_i = 1 y i = 1 時 a i T θ ˉ > 0 a_i^{\mathsf T}\bar\theta \gt 0 a i T θ ˉ > 0 ,而 y i = 0 y_i = 0 y i = 0 時 a i T θ ˉ < 0 a_i^{\mathsf T}\bar\theta \lt 0 a i T θ ˉ < 0 ,便稱訓練數據嚴格可分 。
若訓練數據嚴格可分,則 inf θ L ( θ ) = 0 \inf\limits_\theta L(\theta)=0 θ inf L ( θ ) = 0 ,此下確界取不到,而且對每個 θ \theta θ 都有 ∇ L ( θ ) ≠ 0 \nabla L(\theta)\ne0 ∇ L ( θ ) = 0 。
沿射線 t θ ˉ t\bar\theta t θ ˉ ,每個標籤為 1 1 1 的項是 softplus ( − t a i T θ ˉ ) \operatorname{softplus}(-t\,a_i^{\mathsf T}\bar\theta) softplus ( − t a i T θ ˉ ) ,在 t → ∞ t \to \infty t → ∞ 時趨向 0 0 0 ;每個標籤為 0 0 0 的項是 softplus ( t a i T θ ˉ ) \operatorname{softplus}(t\,a_i^{\mathsf T}\bar\theta) softplus ( t a i T θ ˉ ) ,其分數為負,同樣趨向 0 0 0 。故 L ( t θ ˉ ) → 0 L(t\bar\theta) \to 0 L ( t θ ˉ ) → 0 。由於處處 L > 0 L \gt 0 L > 0 ,下確界 0 0 0 無法取到,無懲罰問題沒有有限最小解。
L L L 凸且可微,故梯度為零的點必是最小解;因此嚴格可分時 ∇ L \nabla L ∇ L 永不為零。
這裏不聲稱逆命題:最小解不存在本身並不能證明嚴格可分;本節亦不分析較弱的退化情況。
可選 在可分數據上,梯度下降會走向哪裏? 迭代點無界增長,但其方向趨向最大間隔分隔器。
自然延伸的下一個問題
在可分數據上,梯度下降會走向哪裏? 迭代點無界增長,但其方向趨向最大間隔分隔器。
上面 λ = 0 \lambda=0 λ = 0 的保證只控制梯度範數。一個超出本課程的已知結果說得更多:對嚴格可分數據及足夠小的固定步長,L ( θ k ) → 0 L(\theta_k)\to0 L ( θ k ) → 0 ,故 ∥ θ k ∥ → ∞ \|\theta_k\|\to\infty ∥ θ k ∥ → ∞ ,而方向 θ k / ∥ θ k ∥ \theta_k/\|\theta_k\| θ k /∥ θ k ∥ 收斂到使 min i ( 2 y i − 1 ) a i T θ \min\limits_i(2y_i-1)a_i^{\mathsf T}\theta i min ( 2 y i − 1 ) a i T θ 最大的單位向量,即最大間隔分隔器。方向的收斂速度只是 k k k 的對數級。
關閉
例題 5.2.11
(每組一個衝突標籤便恢復有限擬合)
使用截距加斜率的特徵 a = ( 1 , − 1 ) T a=(1,-1)^{\mathsf T} a = ( 1 , − 1 ) T 和 a = ( 1 , 1 ) T a=(1,1)^{\mathsf T} a = ( 1 , 1 ) T ,各三行。第一組標籤為 ( 0 , 0 , 1 ) (0,0,1) ( 0 , 0 , 1 ) ,第二組為 ( 0 , 1 , 1 ) (0,1,1) ( 0 , 1 , 1 ) ,故 n = 6 n=6 n = 6 。兩組都不純,所以沒有 θ ˉ \bar\theta θ ˉ 能嚴格分隔數據。
記 θ = ( b , c ) T \theta=(b,c)^{\mathsf T} θ = ( b , c ) T ;兩個分數是 b − c b-c b − c 和 b + c b+c b + c 。每組對 n ∇ L n\nabla L n ∇ L 的貢獻是 3 σ ( z ) − ( 該組標籤 1 的數目 ) 3\sigma(z)-(\text{該組標籤 }1\text{ 的數目}) 3 σ ( z ) − ( 該組標籤 1 的數目 ) 乘以其特徵向量,所以梯度為零當且僅當 σ ( b − c ) = 1 3 \sigma(b-c)=\tfrac13 σ ( b − c ) = 3 1 且 σ ( b + c ) = 2 3 \sigma(b+c)=\tfrac23 σ ( b + c ) = 3 2 。由 σ ( log 2 ) = 1 / ( 1 + 1 2 ) = 2 3 \sigma(\log2)=1/(1+\tfrac12)=\tfrac23 σ ( log 2 ) = 1/ ( 1 + 2 1 ) = 3 2 及 σ ( − log 2 ) = 1 3 \sigma(-\log2)=\tfrac13 σ ( − log 2 ) = 3 1 ,得 b − c = − log 2 b-c=-\log2 b − c = − log 2 、b + c = log 2 b+c=\log2 b + c = log 2 ,故 θ ⋆ = ( 0 , log 2 ) T \theta^\star=(0,\log2)^{\mathsf T} θ ⋆ = ( 0 , log 2 ) T 。
兩個特徵向量線性無關,而每個權重 σ ( z i ) ( 1 − σ ( z i ) ) \sigma(z_i)(1-\sigma(z_i)) σ ( z i ) ( 1 − σ ( z i )) 均為正,所以 Hessian 正定,θ ⋆ \theta^\star θ ⋆ 是唯一最小解。擬合概率重現各組比例,最小值為 − 2 3 log 2 3 − 1 3 log 1 3 = log 3 − 2 3 log 2 ≈ 0.6365 -\tfrac23\log\tfrac23-\tfrac13\log\tfrac13=\log3-\tfrac23\log2\approx0.6365 − 3 2 log 3 2 − 3 1 log 3 1 = log 3 − 3 2 log 2 ≈ 0.6365 。若從兩組各刪去少數標籤,數據便變得可分,最小解也隨之消失。
擬合概率不是總體概率
反例模式
對公平硬幣作出高信心擬合 假設總體標籤真的是公平硬幣,且與唯一的常數特徵獨立,所以總體中標籤為 1 1 1 的概率是 1 2 \tfrac12 2 1 。三次抽樣均得到 1 1 1 ,發生概率為 1 8 \tfrac18 8 1 。以 λ = 0.01 \lambda = 0.01 λ = 0.01 擬合加懲罰的截距模型。
駐點條件 λ z = σ ( − z ) \lambda z = \sigma(-z) λ z = σ ( − z ) 的根為 z ⋆ ≈ 3.36 z^\star \approx 3.36 z ⋆ ≈ 3.36 。由 σ ( z ⋆ ) = 1 − σ ( − z ⋆ ) = 1 − λ z ⋆ \sigma(z^\star) = 1 - \sigma(-z^\star) = 1 - \lambda z^\star σ ( z ⋆ ) = 1 − σ ( − z ⋆ ) = 1 − λ z ⋆ ,擬合概率約為 1 − 0.0336 ≈ 0.966 1 - 0.0336 \approx 0.966 1 − 0.0336 ≈ 0.966 。
模型對一個總體頻率為 50 % 50\% 50% 的事件給出約 97 % 97\% 97% 的概率。優化並無錯誤,只是訓練樣本缺乏代表性。
當 λ → 0 \lambda \to 0 λ → 0 ,擬合概率趨向 1 1 1 。每個根均為正。若某個序列 λ j ↓ 0 \lambda_j\downarrow0 λ j ↓ 0 的根以 M M M 為上界,則 λ j z λ j ⋆ ≤ M λ j → 0 \lambda_j z^\star_{\lambda_j}\le M\lambda_j\to0 λ j z λ j ⋆ ≤ M λ j → 0 ,但 σ ( − z λ j ⋆ ) ≥ σ ( − M ) > 0 \sigma(-z^\star_{\lambda_j})\ge\sigma(-M)>0 σ ( − z λ j ⋆ ) ≥ σ ( − M ) > 0 ,這與駐點方程矛盾。因此 z λ ⋆ → ∞ z^\star_\lambda\to\infty z λ ⋆ → ∞ 。高擬合概率是這次擬合的性質,並不是對未來個案經過校準的陳述。
練習
練習 5.2.12
(設 n = 2 n = 2 n = 2 、a 1 = ( 1 , 1 ) T a_1 = (1,1)^{\mathsf T} a 1 = ( 1 , 1 ) T 且 y 1 = 1 y_1 = 1 y 1 = 1 ,a 2 = ( 1 , − 1 ) T a_2 = (1,-1)^{\mathsf T} a 2 = ( 1 , − 1 ) T 且 y 2 = 0 y_2 = 0 y 2 = 0 。第一個分量為截距。計算 ∇ L ( 0 ) \nabla L(0) ∇ L ( 0 ) 及 ∇ 2 L ( 0 ) \nabla^2 L(0) ∇ 2 L ( 0 ) ,並將 Hessian 與上界 ∥ A ∥ 2 2 / ( 4 n ) \|A\|_2^2/(4n) ∥ A ∥ 2 2 / ( 4 n ) 比較。)
基礎
解答 (3) 1 計算 θ = 0 \theta = 0 θ = 0 處的梯度
∇ L ( 0 ) = 1 2 [ ( 1 2 − 1 ) ( 1 , 1 ) T + ( 1 2 − 0 ) ( 1 , − 1 ) T ] = ( 0 , − 1 2 ) T . \nabla L(0) = \tfrac12\Bigl[\bigl(\tfrac12 - 1\bigr)(1,1)^{\mathsf T} + \bigl(\tfrac12 - 0\bigr)(1,-1)^{\mathsf T}\Bigr] = \bigl(0,-\tfrac12\bigr)^{\mathsf T}. ∇ L ( 0 ) = 2 1 [ ( 2 1 − 1 ) ( 1 , 1 ) T + ( 2 1 − 0 ) ( 1 , − 1 ) T ] = ( 0 , − 2 1 ) T . 依據: 兩個分數均為 0 0 0 ,所以 σ = 1 2 \sigma = \tfrac12 σ = 2 1 ,每個權重 w i = 1 4 w_i = \tfrac14 w i = 4 1 。
2 計算 Hessian
∇ 2 L ( 0 ) = 1 2 ⋅ 1 4 [ ( 1 1 1 1 ) + ( 1 − 1 − 1 1 ) ] = 1 4 I . \nabla^2 L(0) = \tfrac12\cdot\tfrac14\left[\begin{pmatrix}1&1\\1&1\end{pmatrix} + \begin{pmatrix}1&-1\\-1&1\end{pmatrix}\right] = \tfrac14 I. ∇ 2 L ( 0 ) = 2 1 ⋅ 4 1 [ ( 1 1 1 1 ) + ( 1 − 1 − 1 1 ) ] = 4 1 I . 3 與上界比較
由 A T A = 2 I A^{\mathsf T}A = 2I A T A = 2 I ,得 ∥ A ∥ 2 2 = 2 \|A\|_2^2 = 2 ∥ A ∥ 2 2 = 2 ,故上界 ∥ A ∥ 2 2 / ( 4 n ) = 1 4 \|A\|_2^2/(4n) = \tfrac14 ∥ A ∥ 2 2 / ( 4 n ) = 4 1 。在 θ = 0 \theta = 0 θ = 0 時,每個權重均取得最大值 1 4 \tfrac14 4 1 ,所以此上界恰好取到。
看下一步 (2/3) 全部展開
練習 5.2.13
(證明上一題的數據嚴格可分,求沿一條分隔射線的 L L L ,並推論最大似然估計不存在。)
基礎
解答 (3) 1 給出分隔方向
取 θ ˉ = ( 0 , 1 ) T \bar\theta = (0,1)^{\mathsf T} θ ˉ = ( 0 , 1 ) T 。標籤為 1 1 1 的例子分數是 a 1 T θ ˉ = 1 > 0 a_1^{\mathsf T}\bar\theta = 1 \gt 0 a 1 T θ ˉ = 1 > 0 ;標籤為 0 0 0 的例子分數是 a 2 T θ ˉ = − 1 < 0 a_2^{\mathsf T}\bar\theta = -1 \lt 0 a 2 T θ ˉ = − 1 < 0 。
2 沿射線 θ = ( 0 , t ) T \theta = (0,t)^{\mathsf T} θ = ( 0 , t ) T 計算 L L L
L = 1 2 [ softplus ( − t ) + softplus ( − t ) ] = softplus ( − t ) L = \tfrac12\bigl[\operatorname{softplus}(-t) + \operatorname{softplus}(-t)\bigr] = \operatorname{softplus}(-t) L = 2 1 [ softplus ( − t ) + softplus ( − t ) ] = softplus ( − t ) ,當 t → ∞ t \to \infty t → ∞ 時趨向 0 0 0 。
3 作出結論
下確界 0 0 0 取不到,故最大似然估計不存在。沿射線的梯度為 ( 0 , − σ ( − t ) ) T (0,-\sigma(-t))^{\mathsf T} ( 0 , − σ ( − t ) ) T ,永不為零。
依據: 處處 L > 0 L \gt 0 L > 0 。
看下一步 (2/3) 全部展開
練習 5.2.14
(設 n = 4 n = 4 n = 4 ,每個 a i = ( 1 , 1 ) T a_i = (1,1)^{\mathsf T} a i = ( 1 , 1 ) T (重複的常數特徵),標籤為 ( 0 , 1 , 1 , 1 ) (0,1,1,1) ( 0 , 1 , 1 , 1 ) 。描述 λ = 0 \lambda = 0 λ = 0 時的最小解;再證明每個 λ > 0 \lambda \gt 0 λ > 0 都有唯一最小解,並指出它的位置。)
核心
解答 (4) 1 化為單一分數
每個分數都等於 s = θ 1 + θ 2 s = \theta_1 + \theta_2 s = θ 1 + θ 2 ,所以 L = softplus ( s ) − 3 4 s L = \operatorname{softplus}(s) - \tfrac34 s L = softplus ( s ) − 4 3 s 。由例題可知,恰當 s = log 3 s = \log 3 s = log 3 時取得最小值。
2 描述無懲罰的最小解
λ = 0 \lambda = 0 λ = 0 時,最小解組成整條直線 θ 1 + θ 2 = log 3 \theta_1 + \theta_2 = \log 3 θ 1 + θ 2 = log 3 。A A A 的秩為 1 1 1 ,零空間方向是 ( 1 , − 1 ) T (1,-1)^{\mathsf T} ( 1 , − 1 ) T 。
3 解加懲罰的駐點條件
關鍵一步
駐點條件為 ( σ ( s ) − 3 4 ) ( 1 , 1 ) T + λ θ = 0 (\sigma(s) - \tfrac34)(1,1)^{\mathsf T} + \lambda\theta = 0 ( σ ( s ) − 4 3 ) ( 1 , 1 ) T + λ θ = 0 ,這迫使 θ 1 = θ 2 = t \theta_1 = \theta_2 = t θ 1 = θ 2 = t ,其中 h ( t ) = λ t + σ ( 2 t ) − 3 4 = 0 h(t) = \lambda t + \sigma(2t) - \tfrac34 = 0 h ( t ) = λ t + σ ( 2 t ) − 4 3 = 0 。函數 h h h 嚴格遞增,h ( 0 ) = − 1 4 h(0) = -\tfrac14 h ( 0 ) = − 4 1 ,h ( 1 4 λ ) = σ ( 1 2 λ ) − 1 2 > 0 h\bigl(\tfrac1{4\lambda}\bigr) = \sigma\bigl(\tfrac1{2\lambda}\bigr) - \tfrac12 \gt 0 h ( 4 λ 1 ) = σ ( 2 λ 1 ) − 2 1 > 0 ,所以有唯一根 t ⋆ ∈ ( 0 , 1 4 λ ) t^\star \in \bigl(0, \tfrac1{4\lambda}\bigr) t ⋆ ∈ ( 0 , 4 λ 1 ) 。
依據: 懲罰涵蓋兩個分量,故定理保證唯一最小解。
4 指出最小解的位置
最小解為 ( t ⋆ , t ⋆ ) T (t^\star, t^\star)^{\mathsf T} ( t ⋆ , t ⋆ ) T 。由 σ ( 2 t ⋆ ) = 3 4 − λ t ⋆ < 3 4 \sigma(2t^\star) = \tfrac34 - \lambda t^\star \lt \tfrac34 σ ( 2 t ⋆ ) = 4 3 − λ t ⋆ < 4 3 ,得 2 t ⋆ < log 3 2t^\star \lt \log 3 2 t ⋆ < log 3 :懲罰把擬合分數向零收縮。最小解位於 A A A 的行空間,這也符合駐點方程 λ θ ⋆ = − A T r / n \lambda\theta^\star = -A^{\mathsf T}r/n λ θ ⋆ = − A T r / n 的要求。
看下一步 (2/4) 全部展開
練習 5.2.15
(模型 P 和 Q 分別為四個個案給出分數 ( − 1 , 0 , 1 , 2 ) (-1, 0, 1, 2) ( − 1 , 0 , 1 , 2 ) 和 ( − 2 , 0 , 2 , 4 ) (-2, 0, 2, 4) ( − 2 , 0 , 2 , 4 ) 。比較其排序,以及在概率閾值 1 2 \tfrac12 2 1 和 4 5 \tfrac45 5 4 下的決策。再解釋當假陽性代價為 4 4 4 、假陰性代價為 1 1 1 時,閾值 4 5 \tfrac45 5 4 從何而來。)
核心
解答 (4) 1 比較排序
Q 的分數是 P 的兩倍,因此兩個模型對四個個案的排序完全相同。
2 使用閾值 1 2 \tfrac12 2 1
規則「當且僅當 σ ( z ) ≥ 1 2 \sigma(z) \ge \tfrac12 σ ( z ) ≥ 2 1 時預測為正類」等價於 z ≥ 0 z \ge 0 z ≥ 0 。兩個模型均把個案 2 2 2 、3 3 3 、4 4 4 預測為正類。個案 2 2 2 的分數恰為 0 0 0 ,僅因使用 ≥ \ge ≥ 的慣例才被預測為正類。
3 使用閾值 4 5 \tfrac45 5 4
σ ( z ) ≥ 4 5 \sigma(z) \ge \tfrac45 σ ( z ) ≥ 5 4 當且僅當 e − z ≤ 1 4 e^{-z} \le \tfrac14 e − z ≤ 4 1 ,亦即 z ≥ log 4 ≈ 1.386 z \ge \log 4 \approx 1.386 z ≥ log 4 ≈ 1.386 。P 只標記個案 4 4 4 ;Q 則標記個案 3 3 3 和 4 4 4 。排序相同,決策卻不同。
4 由代價推出閾值
預測為正的期望代價為 4 ( 1 − p ) 4(1-p) 4 ( 1 − p ) ,預測為負的期望代價為 p p p 。選擇正類不較差當且僅當 4 ( 1 − p ) ≤ p 4(1-p) \le p 4 ( 1 − p ) ≤ p ,亦即 p ≥ 4 5 p \ge \tfrac45 p ≥ 5 4 。單靠排序不能在 P 和 Q 之間作選擇,而我們亦不知道兩個擬合對新數據是否已校準。
依據: 此論證把 p p p 當作已校準的概率。
看下一步 (2/4) 全部展開