1.软间隔支持向量机的模型
之前讨论的支持向量机的一个重要的假设前提是它的数据集是线性可分的。然而在现实任务中,线性不可分的情形才是最常见的,因此需要允许支持向量机犯错。这就是接下来要说的软间隔的支持向量机。
2.软间隔支持向量机的策略
从数学角度来说,软间隔就是允许部分样本(但是要尽可能的少)不满足下式中的约束条件
min w , b 1 2 ∣ ∣ w ∣ ∣ 2 s . t . y i ( w T x i + b ) ≥ 1 , i = 1 , 2 , . . . , m \begin{align*} &\min_{w,b} \frac12||w||^2 \\ &\operatorname s.t. \space \space y_i(w^Tx_i+b) \geq 1,\space i=1,2,...,m \end{align*} w,bmin21∣∣w∣∣2s.t. yi(wTxi+b)≥1, i=1,2,...,m
考虑损失函数,因为我们知道损失函数是有一定的灵活性的,损失函数的值不可能总是0,这就体现了一定的软间隔的意味,因此我们应该定义以下一个损失函数:
- 当满足约束条件时,损失为0;
- 当不满足约束条件时,损失不为0;
- (可选)当不满足约束条件时,损失与其违反约束条件的程度成正比;
只有满足以上要求,才能实现我们的设想:尽可能少的不满足约束条件的样本的同时,损失最小化。
接下来我们就基于支持向量机得到了软间隔支持向量机的损害函数:
min w , b 1 2 ∣ ∣ w ∣ ∣ 2 + C ∑ i = 1 m l 0 / 1 ( y i ( w T x i + b ) − 1 ) \min_{w,b} \frac12||w||^2 +C\sum^m_{i=1}l_{0/1}(y_i(w^Tx_i+b)-1) w,bmin21∣∣w∣∣2+Ci=1∑ml0/1(yi(wTxi+b)−1)
其中, l 0 / 1 l_{0/1} l0/1是0/1损失函数
l 0 / 1 ( z ) = { 1 z < 0 0 z ≥ 0 l_{0/1}(z)= \begin{cases} 1\hspace{5mm}&z<0\\ 0 & z\geq0 \end{cases} l0/1(z)={10z<0z≥0
C>0是一个常数,用来调节损失的权重,显然当C → + ∞ \rightarrow +\infty →+∞时,会迫使所有样本的损失为0(因为你要最小化上面的式子),进而退化为严格执行的约束条件,退化为硬间隔,因此,本式子可以看作支持向量机的一般化形式。
进一步的,由于 l 0 / 1 l_{0/1} l0/1非凸、非连续,数学性质不好,使得上式不易求解,因此常用一些数学性质较好的替代函数来替换这个函数。软间隔支持向量机通常采用的是hinge(合页)损失来替代:
l h i n g e ( z ) = max ( 0 , 1 − z ) l_{hinge}(z)=\max(0,1-z) lhinge(z)=max(0,1−z)
进一步得到替换后软间隔支持向量机的损失函数:
min w , b 1 2 ∣ ∣ w ∣ ∣ 2 + C ∑ i = 1 m max ( 0 , 1 − y i ( w T x i + b ) \min_{w,b}\frac12||w||^2+C\sum^m_{i=1}\max(0,1-y_i(w^Tx_i+b) w,bmin21∣∣w∣∣2+Ci=1∑mmax(0,1−yi(wTxi+b)
可以看到合页函数还满足第三个条件。
在确定了软间隔支持向量机的损失函数后,我们还可以进一步转换,将其从损失函数的形式再写回优化问题的形式。
我们引入一个松弛变量 ξ i \xi_i ξi,上述优化问题便和下述优化问题等价
min w , b , ξ i 1 2 ∣ ∣ w ∣ ∣ 2 + C ∑ i = 1 m ξ i s . t . y i ( w T x i + b ) ≥ 1 − ξ i ξ i ≥ 0 , i = 1 , 2 , . . . , m \begin{align*} &\min_{w,b,\xi_i}\space \frac12||w||^2+C\sum^m_{i=1}\xi_i \\ &\operatorname s.t. \space \space y_i(w^Tx_i+b) \geq 1-\xi_i \\ &\hspace{8mm} \xi_i \geq0 , i=1,2,...,m \end{align*} w,b,ξimin 21∣∣w∣∣2+Ci=1∑mξis.t. yi(wTxi+b)≥1−ξiξi≥0,i=1,2,...,m
我们会发现这个优化问题的这个松弛变量 ξ i \xi_i ξi可以较为直观的体现软间隔。
3.支持向量回归
支持向量回归(SVR)用一个以 f ( x ) = w T x + b f(x)=w^Tx+b f(x)=wTx+b为中心,宽度为 2 ϵ 2\epsilon 2ϵ的间隔带来拟合训练样本。落在带上的样本不计算损失,不在带上的计算损失,然后最小化损失使得间隔带从样本最密集的地方穿过,达到拟合训练样本的目的。
SVR的损失函数可以写为
min w , b 1 2 ∣ ∣ w ∣ ∣ 2 + C ∑ i = 1 m l ϵ ( f ( x i ) − y i ) \min_{w,b}\frac12||w||^2+C\sum^m_{i=1}l_\epsilon(f(x_i)-y_i) w,bmin21∣∣w∣∣2+Ci=1∑mlϵ(f(xi)−yi)
其中,
(1) l ϵ ( z ) l_\epsilon(z) lϵ(z)为“ ϵ \epsilon ϵ不敏感损失函数"(类比均方误差损失)
l ϵ ( z ) = { 0 i f ∣ z ∣ ≤ ϵ ∣ z ∣ − ϵ i f ∣ z ∣ > ϵ l_\epsilon(z)= \begin{cases} 0\hspace{5mm}&if |z|\leq\epsilon\\ |z|-\epsilon & if |z|>\epsilon \end{cases} lϵ(z)={0∣z∣−ϵif∣z∣≤ϵif∣z∣>ϵ
(2) 1 2 ∣ ∣ w ∣ ∣ 2 \frac12||w||^2 21∣∣w∣∣2为L2正则项,此处引入正则项除了起到正则化的作用外,也是为了和(软间隔)支持向量机的优化目标保持形式上的一致,这样就可以导出对偶问题引入核函数。
(3)C为调节损失权重的常数。
同样的,和软间隔支持向量机类似,我们将损失函数写为优化问题的形式:
引入松弛变量,令
l ϵ ( f ( x i ) − y i ) = ξ i l_\epsilon(f(x_i)-y_i)=\xi_i lϵ(f(xi)−yi)=ξi
显然, ξ i ≥ 0 \xi_i\geq0 ξi≥0,并且
当 ∣ f ( x i ) − y i ∣ ≤ ϵ |f(x_i)-y_i|\leq\epsilon ∣f(xi)−yi∣≤ϵ时,得到 ξ i = 0 \xi_i=0 ξi=0
当 ∣ f ( x i ) − y i ∣ > ϵ |f(x_i)-y_i|>\epsilon ∣f(xi)−yi∣>ϵ时,得到 ξ i = ∣ f ( x i ) − y i ∣ − ϵ \xi_i=|f(x_i)-y_i|-\epsilon ξi=∣f(xi)−yi∣−ϵ
所以得到,
∣ f ( x i ) − y i ∣ − ϵ ≤ ξ i |f(x_i)-y_i|-\epsilon\leq\xi_i ∣f(xi)−yi∣−ϵ≤ξi
即
− ξ i − ϵ ≤ f ( x i ) − y i ≤ ξ i + ϵ -\xi_i-\epsilon\leq f(x_i)-y_i\leq\xi_i+\epsilon −ξi−ϵ≤f(xi)−yi≤ξi+ϵ
进一步SVR可以改写为如下形式,
min w , b , ξ i 1 2 ∣ ∣ w ∣ ∣ 2 + C ∑ i = 1 m ξ i s . t . − ξ i − ϵ ≤ f ( x i ) − y i ≤ ξ i + ϵ ξ i ≥ 0 , i = 1 , 2 , . . . , m \begin{align*} &\min_{w,b,\xi_i}\space \frac12||w||^2+C\sum^m_{i=1}\xi_i \\ &\operatorname s.t. \space \space-\xi_i-\epsilon\leq f(x_i)-y_i\leq\xi_i+\epsilon\\ &\hspace{8mm} \xi_i \geq0 , i=1,2,...,m \end{align*} w,b,ξimin 21∣∣w∣∣2+Ci=1∑mξis.t. −ξi−ϵ≤f(xi)−yi≤ξi+ϵξi≥0,i=1,2,...,m
如果考虑两边的不同的松弛程度:
min w , b , ξ i 1 2 ∣ ∣ w ∣ ∣ 2 + C ∑ i = 1 m ( ξ i + ξ ^ i ) s . t . − ξ ^ i − ϵ ≤ f ( x i ) − y i ≤ ξ i + ϵ ξ i ≥ 0 , ξ ^ i ≥ 0 , i = 1 , 2 , . . . , m \begin{align*} &\min_{w,b,\xi_i}\space \frac12||w||^2+C\sum^m_{i=1}(\xi_i+\hat\xi_i) \\ &\operatorname s.t. \space \space-\hat\xi_i-\epsilon\leq f(x_i)-y_i\leq\xi_i+\epsilon\\ &\hspace{8mm} \xi_i \geq0 ,\hat\xi_i \geq0 , i=1,2,...,m \end{align*} w,b,ξimin 21∣∣w∣∣2+Ci=1∑m(ξi+ξ^i)s.t. −ξ^i−ϵ≤f(xi)−yi≤ξi+ϵξi≥0,ξ^i≥0,i=1,2,...,m