绿色健康小清新

耐得住寂寞,守得住繁华

李宏毅机器学习-60-Support Vector Machine

Support Vector Machine

支持向量机(SVM)有两个特点:SVM=铰链损失(Hinge Loss)+核技巧(Kernel Method)

注:建议先看这篇👉 博客 了解SVM基础知识后再看本文的分析

Hinge Loss

Binary Classification

先回顾一下二元分类的做法,为了方便后续推导,这里定义data的标签为-1和+1

  • f(x)>0f(x)>0时,g(x)=1g(x)=1,表示属于第一类别;当f(x)<0f(x)<0时,g(x)=1g(x)=-1,表示属于第二类别

  • 原本用δ(g(xn)y^n)\sum \delta(g(x^n)\ne \hat y^n),不匹配的样本点个数,来描述loss function,其中δ=1\delta=1表示xxy^\hat y相匹配,反之δ=0\delta=0,但这个式子不可微分,无法使用梯度下降法更新参数

    因此使用近似的可微分的l(f(xn),y^n)l(f(x^n),\hat y^n)来表示损失函数

下图中,横坐标为y^nf(x)\hat y^n f(x),我们希望横坐标越大越好:

  • y^n>0\hat y^n>0时,希望f(x)f(x)越正越好
  • y^n<0\hat y^n<0时,希望f(x)f(x)越负越好

纵坐标是loss,原则上,当横坐标y^nf(x)\hat y^n f(x)越大的时候,纵坐标loss要越小,横坐标越小,纵坐标loss要越大

ideal loss

L(f)=nδ(g(xn)y^n)L(f)=\sum\limits_n \delta(g(x^n)\ne \hat y^n)的理想情况下,如果y^nf(x)>0\hat y^n f(x)>0,则loss=0,如果y^nf(x)<0\hat y^n f(x)<0,则loss=1,如下图中加粗的黑线所示,可以看出该曲线是无法微分的,因此我们要另一条近似的曲线来替代该损失函数

square loss

下图中的红色曲线代表了square loss的损失函数:l(f(xn),y^n)=(y^nf(xn)1)2l(f(x^n),\hat y^n)=(\hat y^n f(x^n)-1)^2

  • y^n=1\hat y^n=1时,f(x)f(x)与1越接近越好,此时损失函数化简为(f(xn)1)2(f(x^n)-1)^2
  • y^n=1\hat y^n=-1时,f(x)f(x)与-1越接近越好,此时损失函数化简为(f(xn)+1)2(f(x^n)+1)^2
  • 但实际上整条曲线是不合理的,它会使得y^nf(x)\hat y^n f(x)很大的时候有一个更大的loss

sigmoid+square loss

此外蓝线代表sigmoid+square loss的损失函数:l(f(xn),y^n)=(σ(y^nf(xn))1)2l(f(x^n),\hat y^n)=(\sigma(\hat y^n f(x^n))-1)^2

  • y^n=1\hat y^n=1时,σ(f(x))\sigma (f(x))与1越接近越好,此时损失函数化简为(σ(f(x))1)2(\sigma(f(x))-1)^2
  • y^n=1\hat y^n=-1时,σ(f(x))\sigma (f(x))与0越接近越好,此时损失函数化简为(σ(f(x)))2(\sigma(f(x)))^2
  • 在逻辑回归的时候实践过,一般square loss的方法表现并不好,而是用cross entropy会更好

sigmoid+cross entropy

绿线则是代表了sigmoid+cross entropy的损失函数:l(f(xn),y^n)=ln(1+ey^nf(x))l(f(x^n),\hat y^n)=ln(1+e^{-\hat y^n f(x)})

  • σ(f(x))\sigma (f(x))代表了一个分布,而Ground Truth则是真实分布,这两个分布之间的交叉熵,就是我们要去minimize的loss
  • y^nf(x)\hat y^n f(x)很大的时候,loss接近于0
  • y^nf(x)\hat y^n f(x)很小的时候,loss特别大
  • 下图是把损失函数除以ln2ln2的曲线,使之变成ideal loss的upper bound,且不会对损失函数本身产生影响
  • 我们虽然不能minimize理想的loss曲线,但我们可以minimize它的upper bound,从而起到最小化loss的效果

cross entropy VS square error

为什么cross entropy要比square error要来的有效呢?

  • 我们期望在极端情况下,比如y^n\hat y^nf(x)f(x)非常不匹配导致横坐标非常负的时候,loss的梯度要很大,这样才能尽快地通过参数调整回到loss低的地方

  • 对sigmoid+square loss来说,当横坐标非常负的时候,loss的曲线反而是平缓的,此时去调整参数值对最终loss的影响其实并不大,它并不能很快地降低

    形象来说就是,“没有回报,不想努力”

  • 而对cross entropy来说,当横坐标非常负的时候,loss的梯度很大,稍微调整参数就可以往loss小的地方走很大一段距离,这对训练是友好的

    形象来说就是,“努力可以有回报""

Hinge Loss

紫线代表了hinge loss的损失函数:l(f(xn),y^n)=max(0,1y^nf(x))l(f(x^n),\hat y^n)=\max(0,1-\hat y^n f(x))

  • y^n=1\hat y^n=1,损失函数化简为max(0,1f(x))\max(0,1-f(x))
    • 此时只要f(x)>1f(x)>1,loss就会等于0
  • y^n=1\hat y^n=-1,损失函数化简为max(0,1+f(x))\max(0,1+f(x))
    • 此时只要f(x)<1f(x)<-1,loss就会等于0
  • 总结一下,如果label为1,则当f(x)>1f(x)>1,机器就认为loss为0;如果label为-1,则当f(x)<1f(x)<-1,机器就认为loss为0,因此该函数并不需要f(x)f(x)有一个很大的值

在紫线中,当y^nf(x)>1\hat y^n f(x)>1,则已经实现目标,loss=0;当y^nf(x)>0\hat y^n f(x)>0,表示已经得到了正确答案,但Hinge Loss认为这还不够,它需要你继续往1的地方前进

事实上,Hinge Loss也是Ideal loss的upper bound,但是当横坐标y^nf(x)>1\hat y^n f(x)>1时,它与Ideal loss近乎是完全贴近的

比较Hinge loss和cross entropy,最大的区别在于他们对待已经做得好的样本点的态度,在横坐标y^nf(x)>1\hat y^n f(x)>1的区间上,cross entropy还想要往更大的地方走,而Hinge loss则已经停下来了,就像一个的目标是”还想要更好“,另一个的目标是”及格就好“

在实作上,两者差距并不大,而Hinge loss的优势在于它不怕outlier,训练出来的结果鲁棒性(robust)比较强

Linear SVM

model description

在线性的SVM里,我们把f(x)=iwixi+b=wTxf(x)=\sum\limits_i w_i x_i+b=w^Tx看做是向量[wb]\left [\begin{matrix}w\\b \end{matrix}\right ]和向量[x1]\left [\begin{matrix}x\\1 \end{matrix}\right ]的内积,也就是新的wwxx,这么做可以把bias项省略掉

在损失函数中,我们通常会加上一个正规项,即:

L(f)=nl(f(xn),y^n)+λw2L(f)=\sum\limits_n l(f(x^n),\hat y^n)+\lambda ||w||_2

看这个函数,一共有两项:第一项是Hinge loss的sum,而Hinge loss是一个convex的function;第二项是一个L2-regularization,因此这也是一个convex的function。两者相加,最终的L(f)L(f)就是一个convex的损失函数,它的好处在于无论从哪个地方开始做梯度下降,最终得到的结果都会在最低处,曲线中一些折角处等不可微的点可以参考NN中relu、maxout等函数的微分处理

对比Logistic Regression和Linear SVM,两者唯一的区别就是损失函数不同,前者用的是cross entropy,后者用的是Hinge loss

事实上,SVM并不局限于Linear,尽管Linear可以带来很多好的特质,但我们完全可以在一个Deep的神经网络中使用Hinge loss的损失函数,就成为了Deep SVM,其实Deep Learning、SVM这些方法背后的精神都是相通的,并没有那么大的界限

gradient descent

尽管SVM大多不是用梯度下降训练的,但使用该方法训练确实是可行的,推导过程如下:

another formulation

前面列出的式子可能与你平常看到的SVM不大一样,这里将其做一下简单的转换

L(f)=nmax(0,1y^nf(x))+λw2L(f)=\sum\limits_n \max(0,1-\hat y^n f(x))+\lambda ||w||_2,用L(f)=nϵn+λw2L(f)=\sum\limits_n \epsilon^n+\lambda ||w||_2来表示

其中ϵn=max(0,1y^nf(x))\epsilon^n=\max(0,1-\hat y^n f(x))

ϵn0\epsilon^n\geq0ϵn1y^nf(x)\epsilon^n\geq1-\hat y^n f(x)来说,它与上式原本是不同的,因为max是二选一,而\geq则取到等号的限制

但是当加上取loss function L(f)L(f)最小化这个条件时,\geq就要取到等号,两者就是等价的

此时该表达式就和你熟知的SVM一样了:

L(f)=nϵn+λw2L(f)=\sum\limits_n \epsilon^n+\lambda ||w||_2,且y^nf(x)1ϵn\hat y^n f(x)\geq 1-\epsilon^n,其中y^n\hat y^nf(x)f(x)要同号,ϵn\epsilon^n要大于等于0,这里ϵn\epsilon^n的作用就是放宽1的margin,也叫作松弛变量(slack variable)

这是一个QP问题(Quadradic programming problem),可以用对应方法求解,当然前面提到的梯度下降法也可以解

Kernel Method

explain linear combination

你要先说服你自己一件事:实际上我们找出来的可以minimize损失函数的参数,其实就是data的线性组合

w=nαnxnw^*=\sum\limits_n \alpha^*_n x^n

你可以通过拉格朗日乘数法去求解前面的式子来验证,这里试图从梯度下降的角度来解释:

观察ww的更新过程w=wηncn(w)xnw=w-\eta\sum\limits_n c^n(w)x^n可知,如果ww被初始化为0,则每次更新的时候都是加上data point xx的线性组合,因此最终得到的ww依旧会是xx的Linear Combination

而使用Hinge loss的时候,cn(w)c^n(w)往往会是0,不是所有的xnx^n都会被加到ww里去,而被加到ww里的那些xnx^n,就叫做support vector

SVM解出来的αn\alpha_n是sparse的,因为有很多xnx^n的系数微分为0,这意味着即使从数据集中把这些xnx^n的样本点移除掉,对结果也是没有影响的,这可以增强系统的鲁棒性;而在传统的cross entropy的做法里,每一笔data对结果都会有影响,因此鲁棒性就没有那么好

redefine model and loss function

知道wwxnx^n的线性组合之后,我们就可以对原先的SVM函数进行改写:

w=nαnxn=Xαf(x)=wTx=αTXTx=nαn(xnx)w=\sum_n\alpha_nx^n=X\alpha \\ f(x)=w^Tx=\alpha^TX^Tx=\sum_n\alpha_n(x^n\cdot x)

这里的xx表示新的data,xnx^n表示数据集中已存在的所有data,由于很多αn\alpha_n为0,因此计算量并不是很大

接下来把xnx^nxx的内积改写成Kernel function的形式:xnx=K(xn,x)x^n\cdot x=K(x^n,x)

此时model就变成了f(x)=nαnK(xn,x)f(x)= \sum\limits_n\alpha_n K(x^n,x),未知的参数变成了αn\alpha_n

现在我们的目标是,找一组最好的αn\alpha_n,让loss最小,此时损失函数改写为:

L(f)=nl(nαnK(xn,xn),y^n)L(f)=\sum\limits_n l(\sum\limits_{n'} \alpha_{n'}K(x^{n'},x^n),\hat y^n)

从中可以看出,我们并不需要真的知道xx的vector是多少,需要知道的只是xxzz之间的内积值K(x,z)K(x,z),也就是说,只要知道Kernel function K(x,z)K(x,z),就可以去对参数做优化了,这招就叫做Kernel Trick

Kernel Trick

linear model会有很多的限制,有时候需要对输入的feature做一些转换之后,才能用linear model来处理,假设现在我们的data是二维的,x=[x1x2]x=\left[ \begin{matrix}x_1\\x_2 \end{matrix} \right],先要对它做feature transform,然后再去应用Linear SVM

如果要考虑特征之间的关系,则把特征转换为ϕ(x)=[x122x1x2x22]\phi(x)=\left[ \begin{matrix}x_1^2\\\sqrt{2}x_1x_2\\ x_2^2 \end{matrix} \right],此时Kernel function就变为:

K(x,z)=ϕ(x)ϕ(z)=[x122x1x2x22][z122z1z2z22]=(x1z1+x2z2)2=([x1x2][z1z2])2=(xz)2K(x,z)=\phi(x)\cdot \phi(z)=\left[ \begin{matrix}x_1^2\\\sqrt{2}x_1x_2\\ x_2^2 \end{matrix} \right] \cdot \left[ \begin{matrix}z_1^2\\\sqrt{2}z_1z_2\\ z_2^2 \end{matrix} \right]=(x_1z_1+x_2z_2)^2=(\left[ \begin{matrix}x_1\\x_2 \end{matrix} \right]\cdot \left[ \begin{matrix}z_1\\z_2 \end{matrix} \right])^2=(x\cdot z)^2

可见,我们对xxzz做特征转换+内积,就等同于在原先的空间上先做内积再平方,在高维空间里,这种方式可以有更快的速度和更小的运算量

RBF Kernel(径向基函数核)

在RBF Kernel中,K(x,z)=e12xz2K(x,z)=e^{-\frac{1}{2}||x-z||_2},实际上也可以表示为ϕ(x)ϕ(z)\phi(x)\cdot \phi(z),只不过ϕ()\phi(*)的维数是无穷大的,所以我们直接使用Kernel trick计算,其实就等同于在无穷多维的空间中计算两个向量的内积

将Kernel展开成无穷维如下:

把与xx相关的无穷多项串起来就是ϕ(x)\phi(x),把与zz相关的无穷多项串起来就是ϕ(z)\phi(z),也就是说,当你使用RBF Kernel的时候,实际上就是在无穷多维的平面上做事情,当然这也意味着很容易过拟合

Sigmoid Kernel

Sigmoid Kernel:K(x,z)=tanh(x,z)K(x,z)=\tanh(x,z)

如果使用的是Sigmoid Kernel,那model f(x)f(x)就可以被看作是只有一层hidden layer的神经网络,其中x1x^1~xnx^n可以被看作是neuron的weight,变量xx乘上这些weight,再通过tanh激活函数,最后全部乘上α1\alpha^1~αn\alpha^n做加权和,得到最后的f(x)f(x)

其中neuron的数目,由support vector的数量决定

Design Kernel Function

既然有了Kernel Trick,其实就可以直接去设计Kernel Function,它代表了投影到高维以后的内积,类似于相似度的概念

我们完全可以不去管xxzz的特征长什么样,因为用低维的xxzz加上K(x,z)K(x,z),就可以直接得到高维空间中xxzz经过转换后的内积,这样就省去了转换特征这一步

xx是一个有结构的对象,比如不同长度的sequence,它们其实不容易被表示成vector,我们不知道xx的样子,就更不用说ϕ(x)\phi(x)了,但是只要知道怎么计算两者之间的相似度,就有机会把这个Similarity当做Kernel来使用

我们随便定义一个Kernel Function,其实并不一定能够拆成两个向量内积的结果,但有Mercer’s theory可以帮助你判断当前的function是否可拆分

下图是直接定义语音vector之间的相似度K(x,z)K(x,z)来做Kernel Trick的示例:

SVM vs Deep Learning

这里简单比较一下SVM和Deep Learning的差别:

  • deep learning的前几层layer可以看成是在做feature transform,而后几层layer则是在做linear classifier

  • SVM也类似,先用Kernel Function把feature transform到高维空间上,然后再使用linear classifier

    在SVM里一般Linear Classifier都会采用Hinge Loss


最后​,​这篇​文章​写得还行​,​可以​参考​一下​:👉支持向量机(SVM)——原理篇

-------------本文结束感谢您的阅读-------------
六经蕴籍胸中久,一剑十年磨在手

欢迎关注我的其它发布渠道