[ML Notes] SVM：回归

Author: nex3z 2021-03-14

  在线性回归问题中，给定训练样本 D={(x1,y1),(x2,y2),…,(xm,ym)}，yi∈R，我们希望找到一个模型

f(x)=wTx+b

使得 f(x) 和 y 尽可能接近，定义的损失为 f(x) 与 y 之间的差异，当且仅当二者完全相同时，损失才为零。

  支持向量回归也希望找到形如式 (1) 的模型，但能够容忍 f(x) 与 y 之间存在最多 ϵ 的偏差，当且仅当二者之差的绝对值大于 ϵ 时才计算损失。相当于以 f(x) 为中心，构建了一个宽度为 2ϵ 的间隔带，若训练样本落入此间隔带，则认为预测是正确的。

  SVR 的问题可以写为

minw,b12||w||2+Cm∑i=1lϵ(f(x1)–yi)

如果将 12||w||2 看成是正则化项，则 C 可以看做是正则化系数；lϵ 称为 ϵ-不敏感损失，定义为

lϵ(z)={0,if |z|≤ϵ|z|–ϵ,otherwise

  引入松弛变量 ξi 和 ˆξi，式 (2) 可以写为

minw,b,ξi,ˆξi12||w||2+Cm∑i=1(ξi+ˆξi)s.t.f(xi)–yi≤ϵ+ξiyi–f(xi)≤ϵ+ˆξiξi≥0,ˆξi≥0,i=1,2,…,m

  构造广义拉格朗日函数

L(w,b,ξ,ˆξ,α,ˆα,μ,ˆμ)=12||w||2+Cm∑i=1(ξi+ˆξi)–m∑i=1μiξi–m∑i=1ˆμiˆξi+m∑i=1αi(f(xi)–yi–ϵ–ξi)+m∑i=1ˆαi(f(xi)–yi–ϵ–ˆξi)

  计算式 (4) 对 w、 b、 ξi、 ˆξi 的偏导，有

∇wL=w+m∑i=1(αi–ˆαi)∇wf=w+m∑i=1(αi–ˆαi)xi

dLdb=m∑i=1(αi–ˆαi)dfdb=m∑i=1(αi–ˆαi)

dLdξi=C–μi–αi

dLdˆξi=C–ˆμi–ˆαi

令以上四个偏导为零，得到

w=m∑i=1(ˆαi–αi)xi

0=m∑i=1(ˆαi–αi)

C=μi+αi

C=ˆμi+ˆαi

将以上四式代入式 (4)，得到

L=(w,b,ξ,ˆξ,α,ˆα,μ,ˆμ)=12wTm∑i=1(ˆαi–αi)xi+Cm∑i=1(ξi+ˆξi)–m∑i=1μiξi–m∑i=1ˆμiˆξi–m∑i=1αiξi–m∑i=1ˆαiˆξi–m∑i=1(αi–ˆαi)(yi–ϵ)+m∑i=1(αi–ˆαi)f(xi)=12m∑i=1(ˆαi–αi)wTxi+Cm∑i=1(ξi+ˆξi)–Cm∑i=1(ξi+ˆξi)–m∑i=1(αi–ˆαi)(yi–ϵ)–m∑i=1(ˆαi–αi)wTxi=m∑i=1(ˆαi–αi)(yi–ϵ)–12m∑i=1m∑j=1(ˆαi–αi)(ˆαj–αj)xTixj

于是得到 SVR 的对偶问题

maxα,ˆαm∑i=1(ˆαi–αi)(yi–ϵ)–12m∑i=1m∑j=1(ˆαi–αi)(ˆαj–αj)xTixjs.t.m∑i=1(ˆαi–αi)=0,0≤αi,ˆαi≤C.

  上述过程的 KKT 条件为

{αi(f(xi)–yi–ϵ–ξi)=0(i)αi(yi–f(xi)–ϵ–ˆξi)=0(ii)αiˆαi=0(iii)ξiˆξi=0(iv)(C–αi)ξi=0(v)(C–ˆαi)ˆξi=0(vi)

  由式 (7) 中前两个条件，可知

• 当且仅当 f(xi)–yi–ϵ–ξi=0 时，αi 能取非零值；
• 当且仅当 yi–f(xi)–ϵ–ˆξi 时，ˆαi 能取非零值。

即仅当样本不落入 ϵ-间隔带中，相应的 αi 和 ˆαi 才能取非零值。此外一个样本只能落入间隔带中的一侧，f(xi)–yi–ϵ–ξi=0 和 yi–f(xi)–ϵ–ˆξi 不能同时成立，因此 αi 和 ˆαi 中最少有一个为零。

  将式 (5) 带入式 (1)，得到 SVR 的模型为

f(x)=m∑i=1(ˆαi–αi)xTix

能使上式中 ˆαi–αi≠0 的样本即为支持向量，它们必落在 ϵ-间隔带之外。支持向量只是训练样本的一部分，因此 SVR 仍具有稀疏性。

  求解得到 αi 后，若 0<αi<C，由式 (7) 中条件 (v)，必有 ξi=0，由条件 (i) 可得

f(xi)–yi–ϵ=0

将式 (8) 带入上式，可以解得

b=yi+ϵ–m∑i=1(ˆαi–αi)xTix

虽然通过上式只需一个满足 0<αi<C 的样本即可求得 b，实际中通常选择多个满足条件 0<αi<C 的样本求解 b 后取平均值。

  如果引入特征映射，则式 (5) 变为

w=m∑i=1(ˆαi–αi)ϕ(x)

f(x)=m∑i=1(ˆαi–αi)K(xi,x2)+b

其中 K(xi,x2) 为核函数。