支持向量机基本原理及在基因数据中的实践
这是一个梗，懂的人才能get到笑点
关于这个同学举牌子的典故我知道，我也是CMU的。这是在2009年在Pittsburgh举行的G20峰会现场外面。很多反对G20的，支持G20的都来凑热闹。我们这位同学也来了，鱼目混珠的高举Support Vector Machine的牌子。很多老美就晕了，你说你支持加强控制二氧化碳排放我懂，你支持的的这个Vector Machine是个什么东西啊？然后这个同学搞笑的目的就达到了。
支持向量机(support vector machine)第一次见到这个词可能难以理解这个奇怪的名字，这是一个90年代产生在深度学习出来之前逼格满满的算法，被认为是适应性最广的分类器之一。SVM是一个基于严格的数学推导的算法（但本文不推导），本文只大概介绍基本思想和简单原理及实践过程。
最大间隔分类器
在二维平面上，一条直线可以把平面分成两边；在三维空间中，一个平面可以把空间分成两块……那么同理，在p+1的高维空间中，一个p维的超平面也可以将其成本两部分，超平面的定义：
超平面的定义
根据高中空间几何的知识可知，把一个点代入上式，如果等于0说明正好在超平面上；大于0在其上方，小于0在其下方。
那么就可以根据这个特点来映射二分类问题。只要我们可以构建出超平面方程，再把样本点代入，根据结果的正负就可以进行分类。
超平面分隔
实际上，能把不同类别样本分隔开来的超平面并不止一个，有无数个。如图中蓝色和橙色虚线都能把两类样本分开，那么你认为这两个哪一个分隔效果更好？
如果用蓝色分隔超平面，那上面的白球就被分成橙色，下面的白球则被分成蓝色；如果用橙色分隔超平面，则结果完全相反。可是根据KNN的思想，很容易看出上面的白球应该被分成蓝色，下面的白球应该被分成橙色。
可以观察到，橙色超平面总体上距离两边的球都比蓝色的远，这就是涉及到最大间隔超平面的概念。对于任一个超平面（以实线表示），把它往两边平移，直至与两边的样本相交（以虚线表示，相交点就叫支持向量，现在知道支持向量机这个名字的由来了吧~），如果两边的虚线的距离最大，这个超平面就是最大间隔超平面。因为最大间隔超平面总体上把不同类别的样本分得最大，所以泛化性能最好。
最大间隔超平面
那么SVM算法的优化实际上就是对超平面间距的最大值优化，以数字公式来表达是这样的：
SVM的约束条件及优化目标
其中M是超平面间隔，也是优化目标。β是归一化参数，y取1或-1表示二分类。
优化过程涉及到复杂的数学推导就不细说了。
线性不可分情况
上面的例子中，不同样本之间本来就分隔得挺好，所以很容易被线性超平面分隔开来。但现实中的数据往往不太可能自动地分离得这么好，甚至存在着线性不可分，比如请用一条直线把下面两种类别的点完全区分开来：
线性不可分示例
既然数据本来就是线性不可分，为了使用线性超平面作分割，就要作出一些让步，即可以容忍一部分分错的情况（这样类似于以提高一部分偏差为代价来减小方差），那么优化函数就变成以下：
有调节的优化目标
C是非负调节参数，ε是一个松弛变量，用来进行一定程度的线性不可分调节，有了这个松弛变量，样本就可以不必严格地在虚线一侧，可以有一定的偏移。
非线性SVM
然而现实中的数据往往是根本不可能用线性分类器就能区分，即使再怎么让步调整也没用，这个时候只能用非线性分类器。
之前提到的PCA是把高维降成低维，减少特征间的相关性，只抽象出最主要的分成——虽然说维度越高越复杂，但是反过来，把低维空间投影至高维空间有没有意义？
对于上面那张线性不可分示意图，它是在一维坐标轴上的，如果把它投影到二维平面上，比如：
二维平面上的线性可分.png
现在是不是就能很容易地用一条直线把两种类别的球分开了？
所以低维空间上线性不可分的问题映射至高维空间就有了线性可分的可能，这就是非线性SVM的核心思想。
然而把低维数据映射到高维空间，会不会使计算复杂很多，甚至会产生维度灾难？这就是SVM的另一巧妙之处，通过核函数把低维变量映射成高维变量，高维变量主要是向量的内积计算，却可以转化成低维向量的内积计算。也就是说通过核函数把低维向量映射到高维空间可以解决线性不可分的问题，却不会额外产生复杂的计算代价！
常用的核函数有多项式核函数、径向核函数等等，这个不做专门研究不需要理解太深，会调包解决问题即可。通过核函数复合的非线性SVM的超平面的投影就不是直线了。
多项式核函数与径向核函数
支持向量机与逻辑回归的区别
SVM与LR都是分类器，有联系也有差别。
SVM vs LR
SVM与LR的损失函数曲线
当f(x)>=1时损失函数为0，表示观测点被正确地分到一侧。
此外，LR的拟合是由全部的样本决定的，而SVM的拟合实际上只由少数几个支持向量决定的。
以下是Andrew Ng的《Machine Learning》中给出的SVM与LR的选择技巧：
- 如果相对于样本量m，特征变量个数n很大，选择逻辑回归或者线性核函数的SVM（这种情况下相当于过拟合的状况，适合用简单的逻辑回归或不带核函数的SVM）；
- 如果特征变量个数n很少，样本量m中等，使用带核函数的SVM；
- 如果特征变量个数n很少，样本量m很大（这种情况相当于低拟合的状态），增加更多的特征，然后使用逻辑回归或者不带核函数的SVM。
> library(ISLR)
> library(e1071)
> # 先观查数据
> names(Khan)
[1] "xtrain" "xtest" "ytrain" "ytest"
> dim(Khan$xtrain)
[1] 63 2308
> dim(Khan$xtest)
[1] 20 2308
> length(Khan$ytrain)
[1] 63
> length(Khan$ytest)
[1] 20
> table(Khan$ytrain)
1 2 3 4
8 23 12 20
> table(Khan$ytest)
1 2 3 4
3 6 6 5
>
> dat = data.frame(x = Khan$xtrain,y = as.factor(Khan$ytrain))
> out = svm(y~.,data = dat, kernel = "linear", cost = 10)
> summary(out)
Call:
svm(formula = y ~ ., data = dat, kernel = "linear", cost = 10)
Parameters:
SVM-Type: C-classification
SVM-Kernel: linear
cost: 10
gamma: 0.0004332756
Number of Support Vectors: 58
( 20 20 11 7 )
Number of Classes: 4
Levels:
1 2 3 4
> table(out$fitted,dat$y) # 训练误差为0
1 2 3 4
1 8 0 0 0
2 0 23 0 0
3 0 0 12 0
4 0 0 0 20
>
> dat.ts = data.frame(x = Khan$xtest, y = as.factor(Khan$ytest))
> pred.te = predict(out,newdata = dat.ts)
> table(pred.te,dat.ts$y) # 只有2个被分错
pred.te 1 2 3 4
1 3 0 0 0
2 0 6 2 0
3 0 0 4 0
4 0 0 0 5
