（16）监督学习-分类问题-SVM

SVM又称为支持向量机。通过求解最大分类间隔（大间距分类器）实现分类、其损失函数为合页损失（均方误差加松弛变量）。

支持向量是指离分割面最近的点。在决定分离超平面时，只有支持向量起作用，而其他实例点并不起作用。如果移动支持向量，将改变所求的解；但是如果在间隔边界以外移动其他实例点，甚至去掉这些点，则解是不会改变的。

（1）支持向量机与感知机模型的区别

感知机和支持向量机都是通过求解分割超平面进行分类的。感知机通过五分类最小策略，求得分离超平面，但是有多个解。而线性可分支持向量机利用间隔最大化求解最优分离超平面，解是唯一的。

（2）支持向量机的推导

支持向量机是求解最大分类间隔的分类器，其中支持向量是指离分割超平面最近的点。分割超平面可以用公式 $y= W^Tx+b$ ;其中，w表示超平面的法向量，b表示截距。空间中某一点到超平面的距离可以用 $\frac{|W^Tx+b |}{||W||}$ 表示， $W^Tx+b$ 与类别标记y的符号是否一致可以表明分类是否正确。所以可以用用 $y(W^Tx+b )$ 表示分类的正确性和确信度（离决策面越远，确信度越高），即函数间隔。对参数w加上约束，如||w|| = 1,可以使得间隔是确定的，得到几何间隔。（同时同比例增大w,b,超平面没有变，函数间隔却扩大了好多倍）。

我们求解最优超平面就是使得几何间隔最大。设最大分类间隔为r,则对于样本中的所有点，都有 $\frac{y(W^Tx+b )}{||W||}>=r$ 。考虑到几何间隔和函数间隔的关系。最优化问题可表示为

$max\frac{r}{||W||}$ ; ${y(W^Tx+b )}>=r$ ; $max\frac{r}{||W||}$ 表示几何间隔，r表示函数间隔。

函数间隔的数值对该最优化为题没有影响，原因同上；可以假设函数间隔为1.则间隔大小为2/||w||。最优化问题转化为 $max\frac{1}{||W||}$ ; ${y(W^Tx+b )}>=1$ ； $max\frac{1}{||W||}$ 等价于 $min\frac{1}{2} ||W||^2$ ,最终最优化问题为 $min\frac{1}{2} ||W||^2$ ; ${y(W^Tx+b )}>=1$ 。

通过拉格朗日乘子法可以转化为对偶问题，具体方法就是对每个约束调价拉格朗日乘子 $\alpha _{i} \geq 0$ 转化为对偶式后的优化函数为 $L(w,b,\alpha ) = \frac{1}{2} ||w||^2 +\sum_{i=1}^m \alpha _{i} (1-y_{i}(w^Tx_{i}+b ) )$ ,在损失函数的选择上，由于0-1损失函数数学性质不好，不容易求导，一般采用合页损失函数 $hinge(z) = max(0,1-z)$ ;此时的优化函数为 $L(w,b,\alpha ) = \frac{1}{2} ||w||^2 +\sum_{i=1}^m max (0,1-y_{i}(w^Tx_{i}+b ) )$

（3）软间隔和硬间隔

当数据线性可分时，称硬间隔支持向量机；当近似线性可分时，称为软间隔支持向量机；当数据线性不可分时，使用核技巧，学习非线性支持向量机。

软间隔分类相当于最优化问题引入了一个松弛变量（针对每个样本点） $y_{i} (w*x_{i}+b )\geq 1-\xi _{i}$ .

（4）线性不可分问题

核函数用于将数据从低纬度的输入空间映射到高纬度的特征空间（希尔伯特空间），核函数与映射函数的区别在于，核函数用简单的运算代替了映射函数中众多复杂的计算。

将线性不可分的低纬数据映射到线性可分到高纬空间。选择核函数的经验是一般情况下先选择简单的，比如先选择线性核，再选择非线性核，如果选择径向基函数，先选择 $\sigma$ （方差）比较大的核，值越大越接近线性。然后再逐渐减少。支持向量机对核函数的选择不敏感，只要参数合适，不同的核函数可以达到相同的效果。

核函数的选择：对称函数（对称其实就是不变量，是指某特性不随数学转换而变化。），且其对于任意数据的核矩阵是半正定的。

常见的核函数有：

线性核；多项式核；径向基核（径向基函数是一个采用向量作为输入的函数，能够基于向量距离计算出一个标量，其需要设置的参数是到达率 $\sigma$ 。也是网格搜索。径向基是用来度量两个向量距离的函数。）；高斯核。

（5）支持向量机的多分类问题

SVM本身时2分类问题，再求解多分类问题时，可以看作多个2分类，1对多对分类。

1-1 libsvm k类的数据集中，单独为每两类的样本设计SVM，进行分类。最终必须设计k(k-1)/2个分类器，最终用投票的方式进行选择。这也是libsvm采用的方法，但是当类别有1000个的时候;

1- V 将某一类归为正类，其余全部是负类。该方法的最大缺陷是数据集的不平衡，因为某一类的实例往往只占一小部分。当然解决不平衡的问题可以进行降采样或者上采样，但是上采样中数据集过多重合，易导致过拟合，而降采样使得数据利用率不足，不能学习整个模型的特性。

分类树方法—— SVM的二叉树组合

补充：

原始问题转换为对偶问题需要满足KKT条件，KKT条件为： KKT条件是非线性规划（nonlinear programming）有最佳解的必要条件。优化问题是凸优化的话，KKT条件就是极小值点（而且是全局极小）存在的充要条件。不是凸优化的话，KKT条件只是极小值点的必要条件，不是充分条件，KKT点是鞍点，是可能的极值点。也就是说，就算求得的满足KKT条件的点，也不一定是极小值点，只是说极小值点一定满足KKT条件。

设A为实对称矩阵，若对每个非零实向量X。都有 $\dot{X} AX>0$ ;则A为正定矩阵；若 $\dot{X} AX>=0$ ；则为半正定矩阵；若 $\dot{X} AX<0$ ，则为负定矩阵。

正定矩阵的充要条件：A的所有顺序主子式都大于0（对应极小点）；负定矩阵的充要条件为A的奇数阶顺序主子式小于0；偶数阶顺序主子式大于0（对应极大点）；若A的所有顺序主子式小于0，则为不定矩阵，对应鞍点。

LR与SVM的区别

LR和SVM都是分类算法；如果不考虑核函数，LR和SVM都是线性分类算法，也就是说他们的分类决策面都是线性的；LR和SVM都是监督学习算法；LR和SVM都是判别模型。

逻辑回归方法基于概率理论，假设样本为1的概率可以用sigmoid函数来表示，然后通过极大似然估计的方法估计出参数的值，支持向量机基于几何间隔最大化原理；支持向量机只考虑局部的边界线附近的点，而逻辑回归考虑全局（远离的点对边界线的确定也起作用）；SVM的损失函数就自带正则！！！（损失函数中的1/2||w||^2项），这就是为什么SVM是结构风险最小化算法的原因！！！而LR必须另外在损失函数上添加正则项！！！；

线性SVM依赖数据表达的距离测度，所以需要对数据先做normalization，LR不受其影响，LR需要做归一化，这样梯度下降的过程中，效率更高。

（16）监督学习-分类问题-SVM

推荐阅读更多精彩内容