SVM三合一 | SVM优化推导 + 拉格朗日算子讲解(KKT条件) + hingeLoss

站长亦新
站长亦新
站长亦新
81
文章
0
评论
2020年7月26日22:54:33 评论 120 5424字阅读18分4秒

SVM中百分之80的问题,你可以在本文中得到答案。

SVM现在主流的有两个方法。
1. 一个是传统的推导,计算支持向量求解的方法.利用拉格朗日乘子法讲约束问题转化为非约束问题进行求解。本文会先介绍这种方法。
2. 一个是近几年兴起的梯度下降的方法。 梯度下降方法的核心是使用了hinge loss作为损失函数,所以最近也有人提出的深度SVM其实就是使用hinge loss的神经网络。本文在后面会介绍hinge loss的推导过程。

1 SVM的优化推导

1.1 SVM的超平面

SVM模型的基本原理,就是寻找一个合适的超平面,把两类的样本正确分开。单个SVM只能处理二分类,多分类需要多个SVM

【什么是超平面?】
超平面就是n维度空间的n-1维度的子空间。换成人话就是2维空间中的1维度的线,三维立体空间的二维平面。

SVM三合一 | SVM优化推导 + 拉格朗日算子讲解(KKT条件) + hingeLoss
图中总共有5个超平面,那么哪一个是最好的呢?我们认为中间的那个是最好的。因为他对两侧的间隔较大。

1.2 SVM基本型

超平面我们可以用这个方程来表示:
\bm{w^Tx}+b=0

空间中任意一个点x到这个超平面的垂直距离为:
d = \frac{|\bm{w^Tx}+b|}{||\bm{w}||}

这里不得不提到一下逻辑回归,对于逻辑回归来说:
SVM三合一 | SVM优化推导 + 拉格朗日算子讲解(KKT条件) + hingeLoss
就是在超平面一侧的样本,逻辑回归给出的预测类别是1,另外一侧就是0.

但是SVM觉得这样有一些过于绝对了,所以:
SVM三合一 | SVM优化推导 + 拉格朗日算子讲解(KKT条件) + hingeLoss
不仅仅要一个样本在平面的一侧,还要在平面的这一侧足够远的地方,才能算作某一类的样本。

SVM三合一 | SVM优化推导 + 拉格朗日算子讲解(KKT条件) + hingeLoss
从图中可以看到,两条虚线之外的点,才是SVM能确定是正样本还是负样本的点。

【什么是支持向量?】
图中距离超平面最近的几个训练样本,并且这几个训练样本可以让上式的等号成立。这个点就是支持向量。

【什么是SVM的间隔】
两个不同类别的支持向量到超平面的最小距离之和。其实也就是\frac{2}{||w||}


到这里,我们可以隐隐约约的发现,寻找最优的超平面其实等价于寻找一个最大的间隔,或者说让间隔最大化。所以可以得到:
\max_{w,b} \frac{2}{||\bm{w}||}
这个的约束条件就是:让SVM给正样本的打分大于1,给负样本的打分小于-1,也就是:
SVM三合一 | SVM优化推导 + 拉格朗日算子讲解(KKT条件) + hingeLoss

简化一下这个约束条件,可以得到:
y_i(\bm{w^Tx_i}+b)>=1

一般我们都是求取最小化问题,所以把最大化max问题取倒数,变成最小化问题:
\min_{w,b} \frac{||\bm{w}||}{2}
这里为了后续的计算方便,最小化||w||等价于最小化||w||^2,所以得到:
\min_{w,b} \frac{||\bm{w}||^2}{2}

总之SVM的基本型就是:
SVM三合一 | SVM优化推导 + 拉格朗日算子讲解(KKT条件) + hingeLoss

1.3 SVM求解

现在求得了基本型。现在可以来进一步优化这个最小化问题。但是首当其冲的问题便是,如何处理这个约束条件。这里用到的方法是拉格朗日乘子法。将约束条件以\alpha_i的权重加入到优化问题中,所以可以得到:
Loss(\bm{w},b,\bm{\alpha})=\frac{1}{2}||w||^2+\sum^m_{i=1}\alpha_i(1-y_i(w^Tx_i+b))
- 这里的loss就是我们要最小化的对象;
- 这里的m就是支持向量的数量。

为了最小化这个问题,对w和b求偏导数,可以得到:
w = \sum^m_{i=1}{\alpha_iy_ix_i}
0 = \sum^m_{i=1}{\alpha_iy_i}

然后把这两个公式代入到:
Loss(\bm{w},b,\bm{\alpha})=\frac{1}{2}||w||^2+\sum^m_{i=1}\alpha_i(1-y_i(w^Tx_i+b))

可以消掉w和b,得到:
SVM三合一 | SVM优化推导 + 拉格朗日算子讲解(KKT条件) + hingeLoss
约束条件为:
SVM三合一 | SVM优化推导 + 拉格朗日算子讲解(KKT条件) + hingeLoss
从而根据这个计算出\alpha_i的取值,然后得到w和b的取值。

【到底如何求解\alpha?】
上面说的最后一部求解alpha,都是理论可以求解,但是实际中如何做到呢?其实这里如何求解\alpha要用到另外一个条件。

就是上述过程要满足一个叫做KKT的条件(KKT具体是什么有点复杂,就不多说了):
SVM三合一 | SVM优化推导 + 拉格朗日算子讲解(KKT条件) + hingeLoss
- 想要第三个公式成立,要么\alpha_i等于0,要么y_if(x_i)-1=0.如果alpha=0,那么意味着这个样本不是支持向量,不应该对SVM超平面起到任何影响,所以是不可能的。所以只有y_if(x_i)-1=0

加上了这个条件,我们可以求解出来\alpha_i的具体数值,然后求解w和b的数值。

假设有3个支持向量,那么就会有三个\alpha_1, \alpha_2, \alpha_3 ,然后根据y_if(x_i)-1=0可以列出3个关于\alpha_1,\alpha_2,\alpha_3的三元一次方程组,然后得到唯一解。

2 拉格朗日乘子法详解

在SVM中,将约束问题转化成非约束问题采用到了拉格朗日乘子法。这个文章就讲一下拉格朗日乘子法与KKT约束是怎么回事。本人不是数学科班出身,但是也只能硬着头皮讲一讲了。

2.1 从零理解

现在我们要解决这样一个问题:
x^2y=3
这个函数距离原点最近的距离是多少。

先画出函数图像:
SVM三合一 | SVM优化推导 + 拉格朗日算子讲解(KKT条件) + hingeLoss

然后想求出最短距离:
SVM三合一 | SVM优化推导 + 拉格朗日算子讲解(KKT条件) + hingeLoss

这里的思路就是,做一个以原点为中心的圆形:
SVM三合一 | SVM优化推导 + 拉格朗日算子讲解(KKT条件) + hingeLoss

不断扩大圆形的半径,直到圆与蓝色的曲线相切:
SVM三合一 | SVM优化推导 + 拉格朗日算子讲解(KKT条件) + hingeLoss

现在。第一次与x^2y=3相交的点就是距离原点最近的那个点:
SVM三合一 | SVM优化推导 + 拉格朗日算子讲解(KKT条件) + hingeLoss

这个,圆形与曲线相切,且切线既是圆形的切线,也是曲线的相切。
SVM三合一 | SVM优化推导 + 拉格朗日算子讲解(KKT条件) + hingeLoss

这时候,这个切线的垂线其实也就是我们所说的梯度,也叫做等高线的法线,看下面两个图可能会好理解一些:
SVM三合一 | SVM优化推导 + 拉格朗日算子讲解(KKT条件) + hingeLoss
SVM三合一 | SVM优化推导 + 拉格朗日算子讲解(KKT条件) + hingeLoss

那么这个梯度怎么计算呢?先看圆形f(x,y)=x^2+y^2的梯度:
SVM三合一 | SVM优化推导 + 拉格朗日算子讲解(KKT条件) + hingeLoss

再看曲线的梯度计算g(x,y)=x^2y的梯度:
SVM三合一 | SVM优化推导 + 拉格朗日算子讲解(KKT条件) + hingeLoss

在相切的时候,两者的梯度方向都在同一条直线上,可以称之为,成比例,这里用比例系数\lambda来表示:
SVM三合一 | SVM优化推导 + 拉格朗日算子讲解(KKT条件) + hingeLoss

所以我们汇总一下所有的已知信息,得到下面的方程组:
SVM三合一 | SVM优化推导 + 拉格朗日算子讲解(KKT条件) + hingeLoss

可以求解得到:
SVM三合一 | SVM优化推导 + 拉格朗日算子讲解(KKT条件) + hingeLoss

这个就是拉格朗日乘子法的直观理解。

2.2 抽象成数学的形式

我们要解决的问题:
\min {x^2+y^2}
s.t. x^2y=3

我们会将约束问题通过拉格朗日乘子法转换成非约束问题:
\min F(x,y)={x^2+y^2+\lambda(x^2y-3)}

【为什么可以这样呢?】
如果求极值,偏导数为0。先对上面的公式进行求偏导数:
\frac{\partial F(x,y)}{\partial x}=2x+\lambda 2xy=0
\frac{\partial F(x,y)}{\partial y}=2y+\lambda x^2=0

这两个等式与这个等价,唯一的不同就是\lambda一个是正数一个是负数:
SVM三合一 | SVM优化推导 + 拉格朗日算子讲解(KKT条件) + hingeLoss

当然,对于x^2y-3=0这个条件,我们也可以写成\frac{\partial F(x,y,\lambda)}{\partial \lambda},所以,可以得到这样的一个方程组:
SVM三合一 | SVM优化推导 + 拉格朗日算子讲解(KKT条件) + hingeLoss

2.3 KKT条件

  • KKT的英文全称:Karush-Kuhn-Tucker

之前的拉格朗日的约束条件是等值的,现在可以通过KKT条件推广到不等式。因为限制条件往往是不大于,小于这样的不等式,所以KKT才是拉格朗日化约束问题为非约束问题的关键。

对于不等式问题,就是有两种情况:
- 可行解在g(x)<0;
- 可行解在g(x)=0。

可行解在g(x)<0,就表示这个约束条件并没有起到约束效果,有根没有事一个效果(下图中的左图);可行解g(x)=0,就表示这个约束条件起到作用了,这就表示g(x)与f(x)相切,也就是下图中右边的图。

SVM三合一 | SVM优化推导 + 拉格朗日算子讲解(KKT条件) + hingeLoss

【g(x)<0的情况】
这种情况下,就是没有限制条件下的情况,其实就是没有约束条件的限制,也就是\lambda=0的情况,所以我们的等式就是直接求解:
\Delta f(x)=0

【g(x)=0的情况】
如果是g(x)=0的情况,那也就是约束条件起到作用了,也就意味着\lambda>0。在这种情况下,存在着:
\Delta f(x) = -\lambda \Delta g(x)
并且两个函数的扩张的方向相反,所以表明两个g(x)和f(x)的梯度一个是正数,一个是负数。所以这个表示\lambda>0

所以综上所述,在这种情况下,我们所有的条件综合起来可以得到,其中x^*就是最优解:
- \lambda >=0
- $\lambda g(x^)=0- g(x^) <= 0$

这三个就是KKT条件。

3 Hinge Loss

【主要讨论的问题】:
- 分类任务中为什么用交叉熵而不是平方差?
- hingeloss是什么?为什么用?

3.1 SVM的基础内容

这里先介绍一下对SVM的部分基础知识,以及本文使用的算法符号。
- SVM是支持向量机,用在分类任务上,一般是二分类任务,如果是多分类任务的话,就需要多个SVM进行集成;
- SVM中的两类样本的真是标签是【+1】,【-1】,而不是神经网络中的0和1。
- y_n表示第n个样本的真实标签,正一或者负一;
- f(x_n)就是第n个样本的SVM预测值;
- x^i_n表示第n个样本的第i个属性(特征)。
这里,如果SVM是一个线性的,那么SVM模型其实就是一个线性分类器:
f(x)=\sum_i {w_i*x_i+b}

基本就这么多了,咱们开始看损失函数吧。

在学这个之前,如果你已经学过了逻辑回归,那就更好了。
一文搞懂:线性回归与逻辑回归(似然参数估计)

3.2 浅谈损失函数

谈到损失函数,我们必须要明确一点:分类任务的目标是什么?

对于SVM来说:
- y_n=1的时候,f(x_n)至少要大于0吧,也许越大越好;
- y_n=-1的时候,f(x_n)至少要小于0吧,也许越小越好;

【为什么用“也许”呢?如果?】
y_n=1的时候,f(x_n)=100f(x_n)=5哪个更好,其实我们并不能得到正确答案。因为两种情况都是分类正确的。

3.3 平方损失和交叉熵

一般的平方损失就是:
loss = \sum_n {(y_n-f(x_n))^2}

但是因为这里的两类是用+1和-1来表示的,所以可以写成这个样子:
loss = \sum_n{(y_nf(x_n)-1)^2}

这样的写法的话,就是希望:
- y_n=1时,f(x_n)=1;
- y_n=-1时,f(x_n)=-1;

这里放一个loss function的函数图:
SVM三合一 | SVM优化推导 + 拉格朗日算子讲解(KKT条件) + hingeLoss

然后上面的平方损失,就是途中的红色的曲线。
我们先品一品y_nf(x_n)是什么?
- 当y_nf(x_n)大于0的时候,其实就是f(x_n)y_n同符号,也就是预测正确了。
- y_nf(x_n)越大的时候,也就是模型预测也稳。比较抽象哈。相当于考试的时候,你刚好61分和70分,肯定是70分的学生及格更稳一点。

回到平方损失,可以看到,平方损失在y_nf(x_n)大于1的时候,损失越来越大。这个不合理呀。你考试,肯定是越高越好,不可能只要求你考70分。你考80分怎么还比70分得到更大的损失。

【这也是分类问题为什么不使用平方损失的原因。因为回归的时候,要预测的是一个数值,高了低了都不好。但是回归的时候,是一个阈值,距离这个阈值越远,越好,没有上限。】

来看一下交叉熵损失。交叉熵需要把模型的结果归一化到0~1中间,所以先对y_nf(x_n)的结果,加上一个sigmoid函数。

看一下交叉熵的SVM损失函数:
loss = -ln(\sigma(y_nf(x_n)))
SVM三合一 | SVM优化推导 + 拉格朗日算子讲解(KKT条件) + hingeLoss
这个绿色的损失看起来不错,比平方损失强多了。


目前:交叉熵完爆平方损失。


有人提出,假设使用sigmoid将y_nf(x_n)限制在0~1内,那么,就可以避免平方损失在大于1的区间内出现的问题。

损失函数变成:
loss = \sum_n{(\sigma(y_nf(x_n))-1)^2}

图像是下图中的蓝色的线。
SVM三合一 | SVM优化推导 + 拉格朗日算子讲解(KKT条件) + hingeLoss

但是sigmoid+平方损失还是不如交叉熵。举个例子:
假如一个样本的y_nf(x_n)非常小,那么交叉熵的梯度就会非常大而sigmoid+平方损失的梯度却非常小。非常小的梯度意味着小的变化,如果使用sigmoid+平方损失作为损失函数,会让模型收敛的非常慢。
SVM三合一 | SVM优化推导 + 拉格朗日算子讲解(KKT条件) + hingeLoss

总之,分类问题,用交叉熵非常的好。

3.4 hinge loss

那么SVM的hinge loss是什么呢?

hingeloss = max(0,1-y_nf(x_n))

其实这个的函数图像与交叉熵非常的像:
SVM三合一 | SVM优化推导 + 拉格朗日算子讲解(KKT条件) + hingeLoss
图中紫色的就是hinge loss的图像了,为了让其更加明显,用红色的箭头来凸显了。

【PS:有一点点像ReLu的翻转】


【Hinge Loss vs CrossEntropy】
- Hinge Loss:当y_nf(x_n)大于1的时候,就达到了最好的情况,类似于,考试考及格就行了,不用最高分;
- CrossEntroy要求尽可能地得分高。我个人感觉,如果尽可能地得分高的话,可能会造成一定程度的过拟合,模型不太会兼顾全部的样本。

Hinge loss感觉就会把更多的注意力放在没有分类分的很好的那些样本上,不会再注意y_nf(x_n)>1的样本了。像是focal loss的感觉。


最后,可以感觉到。如果线性SVM使用交叉熵损失函数的那,那就是Logistic Regression逻辑回归了。所以SVM与其他模型区分的关键就是Hinge Loss损失函数。

所以有的时候,对于一个多层感知机,使用了Hinge Loss的话,也会被成为深度SVM模型。

weinxin
我的微信
微信扫一扫
站长亦新
  • 本文由 发表于 2020年7月26日22:54:33
  • 转载请务必保留本文链接:http://helloworld2020.net/677/
公告
Week 1 | 1 介绍¶ 第 1 题¶一个计算机程序从经验E中学习任务T,并用P来衡量表现。并且,T的表现P随着经验E的增加而提高。 假设我们给一个学习算法输入了很多历史天气的数据,让它学会预测天...
凉经算法题反思 | 单调栈与DP二分法 公告

凉经算法题反思 | 单调栈与DP二分法

算法题1: 一个数组nums,大小为n,返回数组同等大小的数组,返回数组满意以下条件: - 对于数组nums中第i个元素,找到nums从i+1到第n个元素中第一个大于nums的元素,值为j,如果不存在...
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: