动机
平方损失要求预测近似数值标签,分类的直接目标却是符号正确并远离决策边界。铰链损失量度未达指定带符号间隔的程度。它凸但在间隔分界不可微,所以不能只改标签向量便沿用岭回归的法方程。
前面的 RKHS 构造已提供函数空间及有界评估。本节在此基础上证明分类的存在性、有限表示、对偶及支持系数意义,不重做平方损失推导。须分清受正则化的函数、不受惩罚的截距,以及用来表示函数的系数:三者的唯一性并不相同。
软间隔亦容许互相矛盾的观测。优化问题仍可解,但相同输入而标签相反,并不会因求解定理而变得可分辨。完整推导应同时解释成功的分离例子和这项限制。
定义
设 k 为实对称半正定核,RKHS 为 H。给定非空有限样本 (xi,yi)i=1n,其中 yi∈{−1,1}。令 ki=k(xi,⋅)、Kij=k(xi,xj)、Y=diag(yi),并使用前一核空间单元已建立的再生等式与正交投影结果。
分数为 f(x)+b,其中 f∈H,截距 b 是参与优化而不受惩罚的变量;平方范数惩罚只作用于函数。分数非负时预测正类,否则负类,零分数约定不改变训练目标。带符号间隔为 mi=yi(f(xi)+b),铰链为 h(m)=max(0,1−m)。
固定 C>0,软间隔原问题为
f,b,ξmin P(f,b,ξ)=21∥f∥H2+Ci∑ξi,mi+ξi≥1,ξi≥0.
分数固定时,最佳松弛量为 ξi=h(mi),因增加它有正成本。等价目标是 J(f,b)=∥f∥2/2+Ci∑h(mi)。此处用损失总和;若从平均损失 λ∥f∥2/2+n−1i∑h(mi) 出发,乘以 1/λ 后得到 C=1/(nλ),其中 λ>0。
令 V=span{k1,…,kn}。表示 f=i∑ciki 的训练值为 Kc,函数范数平方为 cTKc,一般不是 ∥c∥22。奇异 Gram 矩阵可令不同系数表示同一函数;正则化函数并不等于惩罚任意系数长度。
定理 / 命题
定理 11.1.2
(铰链损失的有限表示及原问题取得)
原问题的最小值可取得。每个最小化函数均在 V 内,而且所有最优三元组的函数 f 相同。截距 b 与系数表示则未必唯一。不要求 K 严格正定,也不要求标签可分离。
对偶是可取得最大值的凹优化问题
αmax D(α)=1Tα−21αTYKYα,0≤αi≤C,yTα=0.其最优值等于原问题最小值。原可行三元组与对偶可行向量同时最优,当且仅当
f=i∑αiyiki,αi(mi+ξi−1)=0,(C−αi)ξi=0对每个下标成立。这是 KKT 的驻点与互补部分;原、对偶可行性也不可省略。
对偶等式来自优化不受惩罚的截距,不是所有核分类器自动具有的性质。先证明主结果,稍后再区分无截距和受惩罚截距。
证明思路
正交分解 f=v+r,v∈V、r⊥V。再生性给 r(xi)=0,而 ∥f∥2=∥v∥2+∥r∥2。移去非零余项不改间隔却严格降低目标,所以一旦最小值取得,每个最优函数都在有限维 V 内。核生成元相依不妨碍 V 本身作为有限维内积空间。
在有界原目标下水平集中,函数范数及每个非负松弛量均有界,再生评估遂界住所有训练值。若正负标签都出现,正类约束给截距下界,负类约束给上界,故极小化序列在 V×R×Rn 有收敛子列,闭约束与连续性给出最小点。若只有同一标签 y,取 f=0,b=y,ξ=0 已达全局下界零。若有两个最优函数不同,平均其可行三元组,平方范数严格下降而松弛成本线性,与最优矛盾。因此函数唯一,但此论证没有保证截距唯一。
对 1−ξi−mi≤0 配非负乘子 αi,对 −ξi≤0 配 βi,得到
21∥f∥2+Ci∑ξi+i∑αi(1−ξi−yi(f(xi)+b))−i∑βiξi.对函数取下确界的点是 fα=i∑αiyiki。对无限制截距,下确界有限当且仅当 yTα=0;对无限制松弛变量,有限当且仅当 C−αi−βi=0。消去 β 得盒形限制和对偶。半正定性保证凹二次目标;盒形切片非空且紧致,所以最大值取得。
有限维约化后,f=0,b=0,ξi=2 使两组不等式都严格成立,正是此凸问题的 Slater 条件。但我们不只引用一般强对偶定理,而直接构造最优乘子。
在 J 的最小点 (f∗,b∗),令 A 是可能铰链权重的盒:mi<1 时固定 αi=C;mi>1 时固定零;mi=1 时可在 [0,C]。在 V×R 定义紧致凸集
S={(f∗−i∑αiyiki, −i∑αiyi):α∈A}.每个元素都是由标量铰链支撑线相加所得的次梯度。更具体地,任意方向 d 的单侧导数等于 s∈Smax⟨s,d⟩:非折点的斜率固定,折点则取两侧线性斜率的较大值;各区间独立,可先各取最大再相加。
若零不在 S,取最小范数点 s0=0。沿集内线段微分距离平方得 ⟨s−s0,s0⟩≥0。方向 d=−s0 的最大方向导数遂不超过 −∥s0∥2<0,与最小性矛盾。因此零在 S,同时给函数驻点及 yTα=0。取最佳铰链松弛量,A 的定义便给全部互补式,包括间隔恰为一的情况。
最后,对任意原、对偶可行对直接展开
P(f,b,ξ)−D(α)=21∥f−fα∥2+i∑αi(mi+ξi−1)+i∑(C−αi)ξi.各项非负。已构造的乘子令每项为零,证明两个已取得最优值相等。反过来,任何最优可行对的间隙为零,各非负项也必为零,故证书既充分又必要。这没有倒置 K,也没有假设铰链可微。
证明透视
强对偶不只是形式计算
论证由三个事实支撑。有限表示一步只用到再生性质:r⊥V 表示 r(xi)=⟨r,ki⟩=0,所以余项对每个间隔都不可见,只徒增代价。存在性需要两种标签同时出现,才能从两边界住不受惩罚的截距;这正是单一标签情形要另行处理的原因。强对偶的关键一步是几何的:每个间隔各自提供一段权重区间,所以铰链次梯度集合 S 紧致且凸;若 0∈/S,其最小范数点给出严格下降方向,与最优性矛盾。严格可行性表明 Slater 理论适用,但证明并不依赖它。间隙等式完成论证:它把 P−D 写成三个非负项之和,所以令三项都为零的乘子给出相等的值,而任何零间隙的可行对都必须满足全部 KKT 条件。单写拉格朗日(Lagrange)函数,只得到候选对偶及弱对偶。
对选定最优对偶向量,正乘子的观测称为支持向量。证书给 αi=0⇒mi≥1、0<αi<C⇒mi=1、αi=C⇒mi≤1。反之,间隔严格大于一必有零乘子,小于一必到上界;恰等于一则容许不同盒形状态。正间隔保证分类正确,即使小于一;负间隔保证错误。间隔为零时依正类平手约定,正标签正确,负标签错误。
例题详解
取线性核 k(x,z)=xz,输入 (−1,1)、标签 (−1,1),则 K=(1−1−11),YKY 全一。等式约束给 α1=α2=t,对偶为区间 [0,C] 上的 2t−2t2。取 C=1/4,最大点为 t=1/4,回复 f(x)=x/2。最优截距集合恰为 [−1/2,1/2],因铰链总和正好在此区间为一。选 b=0,两个间隔、松弛量均为二分之一,原与对偶值均为 3/8。此选择乃至全部 ∣b∣<1/2 下,两点虽有正铰链损失和上界乘子,分类仍正确。取 b=1/2 时负类点分数为零,依本节平手约定便分类错误。
例题 11.1.5
(奇异 Gram 与不唯一的支持系数)
相同核取输入 (1,1,−1)、标签 (1,1,−1)、C=1。K=vvT,其中 v=(1,1,−1)T,YKY 是三乘三全一矩阵。可行性给 α3=α1+α2=t≤1,目标仍为 2t−2t2,在 t=1/2 最大。任何非负分拆 α1+α2=1/2 都最优,皆给 f(x)=x,b=0、零松弛与值二分之一。重复点即使位于间隔边界,也可有零乘子。一般表示系数 (1,0,0)、(0,1,0) 亦代表相同函数;这是任意系数冗余,须与受限制对偶系数分开。
线性核取两个零输入、相反标签,则 K 为零,所有 RKHS 函数在两个观测都为零,最优函数是零。任意 b∈[−1,1] 都最小化 C[h(b)+h(−b)]=2C,松弛量为 (1−b,1+b)。对偶要求两乘子相等,于 α1=α2=C 得最大值 2C。没有严格在盒内的系数可恢复唯一截距。这是合法不唯一,不是矩阵求逆失败或原问题不可行。
概念视角结构
三种截距约定对应三种对偶
固定 b=0 会完全移去对偶等式。若优化截距却加 γb2/2、γ>0,则 b=(yTα)/γ,对偶多出 −(yTα)2/(2γ),不再有等式限制。只有主模型的不受惩罚截距才要求 yTα=0。把常数特征当成普通受惩罚 RKHS 坐标,会改变模型,除非明确调整惩罚约定。
若有严格盒内系数,由间隔一可得 b=yi−f(xi)。没有这种点时,应用其余 KKT 不等式求容许截距范围,不可除奇异矩阵或假造一个自由支持点。乘子不唯一亦使支持向量的选定随最优对偶表示而变,不必对应唯一不可替代的观测子集。
常见错误
第一个错误关乎核本身:对偶的推导在一个确切位置用到半正定性。
反例模式
看似正的相似度可以破坏凸性
矩阵 K=(1221) 对称且元素全正,但 (1,−1)K(1,−1)T=−2,不可能是 RKHS 的 Gram 矩阵。标签 (1,−1) 下,可行线 α=(t,t) 会给 2t+t2,反成凸目标。把这种相似度代入公式,不能保留已证的核分类问题。需要半正定性,不只是对称或元素为正。
驻点条件是函数等式 f=i∑αiyiki。以 f 的系数向量 c 表示,它是 Kc=KYα;当 K 奇异时,不能推出 c=Yα。在三点例子中,c=(1,0,0)T 与 Yα=(a,1/2−a,−1/2)T 都满足 Kc=v=KYα,并表示同一个 f(x)=x。
乘子 αi=0 不代表严格大间隔,αi=C 也不代表分类错误。在三点例子中,恰在间隔上的重复点可以有 αi=0;在第一个例子中,两点都有 αi=C,但当 ∣b∣<1/2 时都分类正确。
二次规划最优只证明指定训练问题的最优,并非总体准确率。核选择、类别权重、数值容差与统计误差界仍需额外分析。
总结
铰链正则化即使在奇异核及矛盾标签下,仍取得有限表示且有唯一 RKHS 函数。截距约定决定对偶限制。有限铰链斜率几何构造乘子,非负间隙证明强对偶与 KKT。精确 Gram 例子说明函数、截距、一般系数与支持乘子须分开理解。
练习
快速检查
(第一个 Gram 例子改为 C=1,求对偶、函数、截距、松弛及共同值。为何系数此时严格在盒内?)
先不理上界,最大化 2t−2t2。
解答 · 答案
最大点为 t=1/2<C,故 f(x)=x,自由系数的间隔式给 b=0,两松弛均零,共同值二分之一。单位间隔可达而不必停在铰链分界之下;严格盒内的精确结论由已解对偶与 KKT 得出。
快速检查
(写三点例子的全部最优 α,选两个不同向量并指出各自的支持向量。)
利用 α3=α1+α2。
解答 · 答案
全族为 (a,1/2−a,1/2),0≤a≤1/2。取零时支持下标二、三;取二分之一时是一、三。函数与所有间隔相同,个别重复边界点可有零乘子,因此支持集合不唯一。
快速检查
(推导加 γb2/2 后的对偶项及截距,证明可在无截距对偶中以 k+1/γ 替换原核。)
解答 · 答案
最小化 γb2/2−byTα 得 b=yTα/γ,最小值 −(yTα)2/(2γ),不要求对偶等式。新二次项是 −αTY(K+γ−111T)Yα/2,正是增广核的无截距对偶。常数特征此时受惩罚,与主模型不同。
快速检查
(原、对偶可行对的间隙至多 ε,证明原问题次优度至多 ε。这可单独控制总体分类误差或任意表示系数间的欧氏(Euclidean)距离吗?)
解答 · 答案
弱对偶给 D(α)≤P∗≤P,因此 P−P∗≤P−D≤ε。以最优对偶证书代入间隙等式,亦得 ∥f−f∗∥H≤2ε。这些控制指定训练问题的优化误差,总体误差仍需统计假设。当 K 奇异时,零系数方向可有任意大欧氏长度而代表同一函数,所以不能控制这类表示间距离;K 正定时则没有此零空间障碍。