学习笔记-支持向量机(SVM)

Support Vector Machines

支持向量机也是一种用于解决分类任务的算法；

从逻辑回归到支持向量机

在逻辑回归算法里，如果一个样本的目标分类为1时，我们希望h(θ)≈1$h(\theta )\approx 1$，并且θTx>>0${\theta }^{T}x>>0$；

但对于SVM，我们的要求更严厉，即当一个样本的目标分类为1时，我们希望h(θ)≈1$h(\theta )\approx 1$，并且θTx>>1${\theta }^{T}x>>1$；同样的，当目标分类为0时，希望h(θ)≈0$h(\theta )\approx 0$，并且θTx<<−1${\theta }^{T}x<<-1$；
观察逻辑回归的损失函数，当只考虑一个样本，并且不考虑系数正则惩罚项时，其公式如下。当y=1$y=1$时，图像形式如左下图，当y=0$y=0$时，图像形式如右下图。

SVM的损失函数稍有不同，y=1$y=1$时，如果θTx≥1${\theta }^{T}x\ge 1$，则cost(θTx)$cost({\theta }^{T}x)$恒等于0，如果y≤1$y\le 1$时，cost(θTx)$cost({\theta }^{T}x)$呈一条直线；相应的，y=0$y=0$时，如果θTx≤−1${\theta }^{T}x\le -1$，cost(θTx)$cost({\theta }^{T}x)$恒等于0，当y>−1$y>-1$时，cost(θTx)$cost({\theta }^{T}x)$呈一条直线。

逻辑回归和SVM的损失函数如下：

两者的形式非常相像，SVM的损失函数公式中虽然没有了1/m，但并不影响求解结果；SVM中的系数C相当于逻辑回归中的1λ$\frac{1}{\lambda }$。

SVM的损失函数满足了，当一个样本的目标分类为1时，我们希望h(θ)≈1$h(\theta )\approx 1$，并且θTx>>1${\theta }^{T}x>>1$；

SVM的决策边界如下图右下角蓝色字：

Large Margin classifier

SVM又称为大边界分类器，当训练样本是线性可分的情况下，它不是随便找一条能把不同类样本分开的线条即可；SVM会找到一条离各类样本距离最远的分类线。

SVM损失函数中的C项，发挥着类似1λ$\frac{1}{\lambda }$的作用，即当C的值很大时，分类边界会尽可能地正确划分所有的样本；当C的值不至于太大时，SVM能够容忍个别分类错误，找到更好的分类边界。

SVM背后的数学原理

基础知识：两个向量的內积等于一个向量在另一个向量上的投影长度（分正负）乘以另一向量本身的长度，即uTv=u1v1+u2v2=P∗∥u∥$u^{T}v=u_1{v}_1+u_2{v}_2=P\ast \Vert u\Vert$

SVM的决策边界公式的主体部分可转换为12∥θ∥2$\frac{1}{2}\Vert \theta {\Vert }^2$，过程与形式如下图：

SVM为什么会表现出大边界分类器的效果呢?

观察SVM的分类边界公式，当y(1)=1$y^{(1)}=1$时，需要使P∗∥θ∥≥1$P\ast \Vert \theta \Vert \ge 1$。如左下图，当随便找了一条线作为分类边界时，训练样本x(i)$x^{(i)}$在θ$\theta$上的投影P(i)$P^{(i)}$的长度很小，当要满足P∗∥θ∥≥1$P\ast \Vert \theta \Vert \ge 1$时，需要使∥θ∥$\Vert \theta \Vert$的值变得很大，而这与损失函数的目标min∥θ∥2$min\Vert \theta {\Vert }^2$相反，因此该线条不是SVM能达到的最佳分类边界。
SVM得到的最佳分类边界如右下图，训练样本x(i)$x^{(i)}$在θ$\theta$上的投影P(i)$P^{(i)}$的长度足够大，当需要满足P∗∥θ∥≥1$P\ast \Vert \theta \Vert \ge 1$时，能够使∥θ∥$\Vert \theta \Vert$达到足够小，这与目标损失函数的要求一致。
通过以上分析，可以发现SVM总能找到最大分类边界。

Kernels 核函数

对于非线性分类任务，逻辑回归需要通过增加多项式特征变量来实现非线性分类。

对于给定x，SVM通过核函数创建新的特征变量。创建过程即，计算给定x与地标(landmarks)的相似值，相似值计算公式为f=exp(−∥x−li∥22σ2)$f=exp(-\frac{\Vert x-l^i{\Vert }^2}{2{\sigma }^2})$。有多少个地标就创建多少个相似值特征变量。

从相似值计算公式我们可以发现，当x与l(i)$l^{(i)}$相近时，相似值f(i)$f(i)$接近于1；当x与l(i)$l^{(i)}$差异很大时，相似值f(i)$f(i)$约等于0。

σ也控制着相似值的变化，即当σ很大时，f(i)$f(i)$的下降会较为缓慢；相反，当σ很小时，f(i)$f(i)$的下降会较为快速。

实际预测过程中，对于每一个样本，首先需要利用核函数对其进行转换，即计算该样本分别与所有地标间的相似性值，然后利用得到的相似性值作为新的特征变量，将特征变量向量乘以参数向量θ，若结果大于等于0，则判断y为1，否则为0。

如何选择landmarks

如何选择landmarks？需要选择多少个landmarks？

最开始时，将每一个训练样本都作为一个独立的landmarks，即有多少个训练样本就有多少个landmarks。

构造特征变量：对于每个训练样本，计算其与每个landmarks之间的相似性，得到n维特征向量（n为训练样本总量）。将特征向量与参数向量相乘，如果乘积θTf${\theta }^{T}f$大于或等于0，则预测y等于1，反之，预测y为0。
训练过程即，一步步优化参数向量集θ，使得损失函数最小。

SVM的参数说明：
C越大，低偏差，高方差；C越小，高偏差，低方差。
σ越大，f平滑，高偏差，低方差；σ越小，f陡峭，低偏差，高方差。

应用SVM

由于SVM的损失函数求导过程比较复杂，一般建议直接挑用现成的包，不建议自己手工一步步构造。
在调用现成的SVM包时，需要设置C值，需要选择核函数计算相似值。也可以不选择任何核函数，也就相当于线性核函数；如果选择高斯核函数，那么还需设置σ值。

选择逻辑回归还是SVM：
当特征变量很多（相对于样本量）时，选择逻辑回归，或者SVM使用线性核；
当特征变量很少，并且样本量中等时，选择SVM并使用高斯核；
当特征变量很少，但是样本量非常多时，创建或者新增更多的特征变量，并且使用逻辑回归或带线性核的SVM。
神经网络对于以上情况可能效果都很好，但是训练过程会较慢。

注：如无特殊说明，以上所有图片均截选自吴恩达在Coursera开设的机器学习课程的课件ppt.

(2018/06/16)偶然发现，对于该主题，https://blog.csdn.net/SCUT_Arucee/article/details/50419229的总结比我的更详细。