Name	Name	Last commit message	Last commit date
parent directory ..
SVM_Classify	SVM_Classify
SVM_Regression	SVM_Regression
formula	formula
bia.png	bia.png
coor_de.py	coor_de.py
gap.png	gap.png
noli.png	noli.png
readme.md	readme.md
svm.png	svm.png
svr1.png	svr1.png
svr2.png	svr2.png
svr3.png	svr3.png
the.png	the.png
ying.png	ying.png
zuiyou.png	zuiyou.png

SVM Theory

Name: Machine-Learning-for-Beginner-by-Python3/SVM at master · Anfany/Machine-Learning-for-Beginner-by-Python3 · GitHub
Rating: 4.6 (7814 reviews)

分类
- 引入
如上图左，平面内展示了二维数据样本，正例用“+”号表示，负例用“-”号表示。存在很多的分割线可以分开上述两类(上图右)。但只存在一条最优的：分割线到负例的距离中最小的那个距离，要等于到正例的距离中最小的距离，并且这两个距离的和是所有满足前一个条件的分割线中最大的(见下图左)。
下面定义一个向量W，现在只定义它的方向，就是与分割线垂直。假设这个样本空间中存在一个样本向量U，PP=U·W可看作向量U在W上的投影(因为W未定义长度)。现在规定：如果U是一个负例，则PP的值越小越好；如果是一个正例，则PP的值越大越好(见上图右)。
因此在判断样本属于正例还是负例时，就是判断PP的值是否大于一个数，也就是判断U·W+b>=0。为了求得W和b，需要添加一些约束条件。不失一般性，对于一个正例Xz，可以令Xz·W+b>=1，对于一个负例Xf，可以令Xf·W+b<=-1。数学便利性：对于正例，令Y= 1，对于负例，令Y=-1。因此结合以上式子可得：对于任意的样本h，有Yh(Xh·W+b) >=1，也就是Yh(Xh·W+b)-1 >=0。
现在着重研究下Yh(Xh·W+b)-1 = 0的情况，当样本h在上边缘或者在下边缘时，式子成立。假设正例Xz，负例Xf分别在上边缘、下边缘上。则上边缘与下边缘的距离，也就是分割线的最大间隔为 $g=(Xz-Xf)\cdot\frac{W}{||W||}$
因为Yz=1，Xz·W = 1-b， Yf=-1，Xf·W = -1-b，所以g=2/||W||。
OK，整理下思路。我们需要求得g最大，也就是 $\frac{2}{||W||}$ 最大，也就是 $\frac{1}{||W||}$ 最大，也就是 $||W||$ 最小，也就是 $\frac{1}{2}||W||^{2}$ 最小。
- 线性可分情况：硬间隔
这是一个凸二次优化问题，可以求得其全局最小值。引入拉格朗日乘子，可得到拉格朗日函数：
也就是计算上式的极小值，求极值，就需要求导，并且另导数等于0，得到下面的式子：
将上面的结果带入到拉格朗日函数中，得到：
因为上面的约束条件包含不等式约束，因此需要利用KKT(Karush-Kuhn-Tucker)条件求解(只有等式约束，可利用拉格朗日乘子法求解)。将原始问题转为其对偶问题(在满足KKT条件时，对偶问题的最优解就是原始问题的最优解，理论参见《凸优化》)：
KKT条件是保证取得的解是最优解的必要条件，而对于像本问题这样的凸优化问题，则是充要条件，下面给出KKT条件：
假设得到的解为：
- 线性可分情况：软间隔
上面描述的是线性可分的情形，也就是存在线或者面可以将样本按类别很好的分开。现在看下面存在离群点的2种情况：
情况A：如果依然按着硬间隔进行划分，可能会过拟合；情况B：不存在硬间隔。因此在这种情形下，要适当的对约束条件进行如下的放宽。
对于硬间隔而言，Yh(Xh·W+b) >=0对任何的样本均成立，也就是保证所有的样本均分类正确。而在软间隔中，Yh(Xh·W+b) >=0不是对所有的样本均成立，也就是允许对一些离散的点分类错误。
因为不能无限放宽，因此需要在目标函数里面增加一个惩罚项，问题变为：
上式中C的值越大，离群点的存在会使得目标函数的值变大，为了降低目标函数的值，这时候，得到的结果趋向于硬间隔。
经过和硬间隔同样的变化，得到软间隔的对偶问题：
模型多了αi<=C的限制条件，并且表达式中没有参数ξi，此时b的求值公式也会发生相应的改变。下面给出KKT条件：
- 线性不可分情况：核函数
以上描述的都是线性可分的情形，现在考虑下面的情形(下图左)：
首先上述不存在硬间隔，如果使用软间隔，则和数据分布不符，因此需要对原始的数据进行非线性转换(上图右)。
前面2种情况的最终的对偶问题表达式中，都只是和内积有关。因此只要找到一个函数Ｆ，使得
其中P是非线性转换函数。也就是说F的值恰好是非线性转换后的向量的内积，此时的F称为核函数。
下面介绍几种常用的核函数：
经过核函数的对偶问题为：
- 求解算法：序列最小优化算法SMO
  - 坐标上升/下降算法
  坐标上升用于求极大值，下降用于计算极小值，两者的本质是一样的。对于凸函数而言，这种方法可以获得全局最优值，但对于有多个极值的函数而言，很大可能会获得局部最优值，这和初始值的选取有很大关系。下面用例子说明算法的步骤：
  重复步骤1和2，直到函数的值变化很小。基于Python3实现的上述例子的代码。
  算法总结：对于多未知量的函数求极值，每次都更新一个值，把其他的变量当做已知量。按着变量的顺序或者其他比较好的顺序依次更新每一个变量。直到达到全局最优值。
  图示：
  - SMO算法
  1996年，John Platt发布了SMO算法。SMO算法是将大优化问题分解为多个小优化问题来求解。这点和坐标上升/下降法类似。SMO算法的工作原理：每次循环选择2个变量进行优化处理，一旦找到一对符合条件的变量，那么就增大其中一个通式减小另一个。符合的条件一是这2个变量必须在间隔边界之外，二是这2个变量还没有进行过区间化处理或者不在边界上。伪代码参见。
回归
同样可利用SMO算法解决，说明参见。