L1正则与次梯度

L1稀疏权重、解易落在轴上、特征选择应用场景、w0w0w0不可导需次梯度subgradient∂f(x){g∣f(y)≥f(x)gT(y−x),∀ y∈dom f}\partial f(x)\{g|f(y)\geq f(x) g^T(y-x),\forall\ y\in \text{dom}\ f \}∂f(x){g∣f(y)≥f(x)gT(y−x),∀y∈domf}$$\begin{bmatrix}g\-1\end{bmatrix}\begin{pmatrix}\begin{bmatrix}y\t\end{bmatrix}\begin{bmatrix}x\f(x)\end{bmatrix}\end{pmatrix}\leq 0, \forall (y,t)\in \text{epi}\ f$$对于光滑的可导曲线即为其切线对于非光滑不可导的凸函数fff在点xxx处的次梯度不再唯一而是构成一个次微分的凸集合∂f(x)\partial f(x)∂f(x)。每个g∈∂f(x)g \in \partial f(x)g∈∂f(x)都确定一个支撑超平面tf(x)gT(y−x)t f(x) g^{\mathsf T}(y - x)tf(x)gT(y−x)该超平面过点(x,f(x))(x, f(x))(x,f(x))且上镜图epi f\text{epi}\ fepif全部位于该超平面上方。这些支撑超平面构成一个支撑超平面族平面束它们的包络就是函数图像。∂f(x)\partial f(x)∂f(x)越大越宽说明该点越不光滑。几何直观在不可导点处可以作出无穷多条不同斜率的支撑线它们夹成一个锥形区域函数图像在这个锥的尖端处发生转折。∂f(x)\partial f(x)∂f(x)恰是这些支撑超平面法向量的前nnn个分量最后一个分量为−1-1−1保证朝下的全体。支撑超平面分离超平面涉及集合单个凸集两个不相交凸集接触性必接触集合边界至少一点可以不接触任何一个集合几何含义托住凸集集合全在某一侧将两个集合隔开各在一侧唯一性边界光滑点唯一非光滑点不唯一强分离唯一一般若不唯一关系支撑超平面 分离集合与集合外一点的特殊分离超平面一般分离超平面未必是支撑超平面核心关系过凸集边界点x0x_0x0​的支撑超平面等价于分离该凸集与单点集{x0}\{x_0\}{x0​}的分离超平面但分离两个一般凸集的超平面可能不与任一集合接触因此不一定是支撑超平面。支撑超平面 vs 分离超平面示例说明示例 1是支撑超平面也是分离超平面特殊重合考虑凸集为单位圆盘C{(x,y)∣x2y2≤1}C \{(x,y) \mid x^2 y^2 \leq 1\}C{(x,y)∣x2y2≤1}在边界点(1,0)(1,0)(1,0)处直线x1x 1x1满足支撑超平面CCC全部落在x≤1x \leq 1x≤1半空间且直线与CCC接触于点(1,0)(1,0)(1,0)同时它也是分离CCC与外部单点{(1,0)}\{(1,0)\}{(1,0)}的分离超平面非严格分离支撑超平面本质上就是分离「凸集」与「其边界上一点」的分离超平面。示例 2是分离超平面但不是支撑超平面典型区别考虑两个不相交的开圆盘A{(x,y)∣x2y21}A \{(x,y) \mid x^2 y^2 1\}A{(x,y)∣x2y21}B{(x,y)∣(x−3)2y21}B \{(x,y) \mid (x-3)^2 y^2 1\}B{(x,y)∣(x−3)2y21}直线是否分离 A 和 B是否接触 A是否接触 B结论x1.5x 1.5x1.5✅❌ 不接触❌ 不接触纯分离超平面非任何一方的支撑x1x 1x1✅✅ 接触 A❌ 不接触分离超平面且是 A 的支撑超平面x2x 2x2✅❌ 不接触✅ 接触 B分离超平面且是 B 的支撑超平面直观理解分离超平面只需从中间穿过把两边隔开可以不碰任何一方支撑超平面必须托住集合。示例 3非光滑点处的支撑超平面束次梯度可视化考虑f(x)∣x∣f(x) |x|f(x)∣x∣考察点x0x 0x0不可导点。次微分∂f(0)[−1,1]\partial f(0) [-1, 1]∂f(0)[−1,1]其中每一个g∈[−1,1]g \in [-1,1]g∈[−1,1]都对应一个支撑超平面tg⋅(y−0)0gyt g \cdot (y - 0) 0 g ytg⋅(y−0)0gy即直线族{tgy∣−1≤g≤1}\{t gy \mid -1 \leq g \leq 1\}{tgy∣−1≤g≤1}g−1g -1g−1t−yt -yt−y最左侧支撑线斜率−1-1−1g0g 0g0t0t 0t0水平支撑线g1g 1g1tyt yty最右侧支撑线斜率111所有支撑线在(0,0)(0,0)(0,0)处交汇形成一个锥形束上镜图epi f\text{epi}\ fepif位于每条线的上方。这体现了非光滑点处支撑超平面不唯一的特点。示例 4既是双方支撑超平面但不严格分离两个闭圆盘相切A{(x,y)∣x2y2≤1}A \{(x,y) \mid x^2 y^2 \leq 1\}A{(x,y)∣x2y2≤1}B{(x,y)∣(x−2)2y2≤1}B \{(x,y) \mid (x-2)^2 y^2 \leq 1\}B{(x,y)∣(x−2)2y2≤1}在切点(1,0)(1,0)(1,0)处直线x1x 1x1同时是AAA和BBB的支撑超平面也是它们的分离超平面非严格。但不存在严格分离超平面无法让两者分居两侧且都不接触因为A∩B{(1,0)}≠∅A \cap B \{(1,0)\} \neq \varnothingA∩B{(1,0)}∅。