从得分到概率模型
仿射分类器计算得分 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 ,对每个 i i i 都有 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 时预测为 1 1 1 ”,按约定把恰好为 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 ,对每个 i i i 都有 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) 全部展开