深入理解SVM

支持向量机（苏联Vapnik发明）问题

1. 如何在线性可分样本集上画一条直线将其分开（找到最好的直线）。
2. 如何将非线性可分样本集分开。

线性可分样本集就是一条直线能分开的集合，二者有明显界限。

• 首先要找到一个性能指标，然后根据这个性能指标指出某一条线比其他线指标高。
• 将一条线平行地向一侧移动，直到叉到某一个样本为止，然后平行地向另一侧移动，也是叉到某一个样本为止。这个性能指标就是两条平行线的距离。这个距离最大的一条线就是最佳的。同时两条平行线的最中间是唯一的。
• 将平行线间的距离称为d(margin)，支持向量机是最大化平行线距离d(margin)的方法。
• 将平行线叉到的向量称为支持向量，画出这条线的方法只跟支持向量有关系，跟其他向量没关系，这也是为什么支持向量能够用在小样本集上。

1. 定义训练数据和标签：(X1,y1)、(X2, y2)...(Xn, yn)，其中X = [x1, x2 ..]，是多维向量，y是+1或-1的标签。
2. 线性模型 (W, b) WTX+ b = 0，描述超平面的线性方程。W是一个向量，如果X是n维的，那么W也是n维的。b是一个常数。WTX 一个列向量转置然后乘以一个行向量，也是一个数。
3. 线性可分的定义。存在（W，b），使yi =+1时，WTX+ b>=0；yi =-1时，WTX+ b<0。即yi[WTXi+ b] >=0（公式一）

机器学习的过程：

1. 确定一个方程；
2. 确定一些要求取的参数，比如这里的W和B；
3. 训练模型，求出参数

优化问题（凸优化问题、二次规划问题）

1.最小化minimize：||W||2, 即W模的平方。

2.限制条件Subject to：yi[WTXi+ b] >=1，其中i=1~N

如何从最大化margin转化到上面的两个问题？

事实1. WTX+ b = 0与 aWTX+ ab = 0是同一个平面，其中a是一个正实数。也就是若(W, b)满足公式一，那么（aW, ab）也满足公式一，a是负数的话符号就相反了。 事实2. 点(x0, y0)到平面（w1x + w2y +b = 0）的最短距离：d= |w1x0 + w2y0 +b| / √(w12 + w22) 那么高维上，向量X0到超平面WTX+ b = 0的距离，就是：|WTX0+ b|/ || W ||，其中分母W的模就是√(w12 + w22 + w32 ...)

我们可以用a缩放（W，b）得到（aW, ab），最终使所有支持向量X0上，有|WTX0+ b| = 1，那么非支持向量上，|WTX0+ b| >1，从而得证限制条件

此时支持向量与平面的距离d = 1/|| W ||，从而最小化|| W ||可以使d最大，得证最小化条件

注意：

1. 限制条件最后的1可以是2、3、4...等任意整数，它们的区别只是一个常数a。
2. 只要线性可分，一定存在W和b，反之如果线性不可分，找不到W和b满足限制条件

二次规划问题：目标函数是二次项，限制条件是一次项。要么无解，要么只有一个极值。

支持向量机效果好，是因为数学理论漂亮，漂亮在转化为了一个凸优化问题，这类问题在全局上有一个最优解。

SVM处理非线性问题

优化问题：

最小化 ||W||2/2 + C∑εi，

限制条件

1. yi[WTXi+ b] >=1 - εi，

2. εi >= 0 ，其中i=1~N

理解：有上面知道非线性情况下，找不到满足yi[WTXi+ b] >=1的（W，b），因此，放宽条件，当εi很大的时候，1-εi很小，就能满足限制条件，同时又不能让εi很大，否则问题会很发散，所以把它又放在最小化里面。εi称为松弛变量，slack variable.

所以，已知条件有Xi、Yi，即训练样本，要求的有W、b、εi

• C∑εi被称为正则项，regulation term，C的作用是平衡每一项εi，使它们都不要太大。
• C是事先设定的参数，起到平衡前后两项的作用。通常没有固定的值，一般根据经验在某个范围内去一个个试。

为什么要加正则项？

1. 以前没有解，要使其有解，就需要加正则项。
2. 目标函数有解，但其解并不想要的，比如目标函数凹凸不平，也需要加正则项。

低维到高维映射φ(x)

问题：之前的解都是求解直线，但如果最优解其实是圆形怎么办？比如一堆1包围了0。

vapnik一个创意的想法是，不在低维的空间找圆形、椭圆等其他形状，而是在高维的空间还是找直线。x => φ(x)

举例：x1(0, 0)和x2(1,1)属于第一类，x3(1, 0)和x4(0, 1)属于第二类。一个映射方案是[a,b] =>[a2, b2, a, b, ab]

那么x1: [0, 0] => [0, 0, 0, 0, 0], x2: [1, 1] => [1, 1, 1, 1, 1]，x3: [1, 0] => [1, 0, 1, 0, 0] , x4: [0, 1]=>[0, 1, 0, 1, 0]。(转置)

如何求解W和b？一个解是：W = [-1，-1，-1，-1, 6]，b=1

维度越高，被线性分开的可能性越高，如果是无限维，被线性分开的概率为1。

SVM精髓：

我们可以不知道无限维映射φ(x)的显式表达，我们只要知道一个核函数kernal function，K(x1, x2) = φ(x1)Tφ(x2)，那么 ||W||2/2 + C∑εi这个优化式仍然可解。

φ(x1)Tφ(x2)是两个无限维向量的内积，就是一个数，也就是不需要φ(x)的具体表达式，只要知道核函数就行了。

常见的核函数：

1. 高斯核 K(x1, x2) = e^-(||x1-x2||2/2σ2)

2. 多项式核函数 K(x1, x2) = (x1Tx2 + 1)d，其中d是多项式的阶数，由于d有限，所以φ(x)是有限维

K(x1, x2) 能写成 φ(x1)Tφ(x2)的充要条件是（Mercer's Theorem）：

1. 满足交换律 K(x1, x2) = K(x2, x1)

2. 半正定性，对于所有的Ci和Xi， 有∑i∑jCiCjK(Xi, Yi) >= 0。其中Ci是常数，Xi是向量。

原问题与对偶问题

原问题Prime Problem：

1. 最小化f(ω)

2. 限制条件

① gi(ω) <=0，其中i =1~K；

②hi(ω) = 0，其中1 = 1~M

原问题非常普适，最小化可以转为最大化问题，限制条件大于等于可以转为小于等于，后面的h(ω) = 0可以转为h(ω) -C= 0

对偶问题Dual Problem：

先定义函数：

L(ω, α, β) = f(ω) + ∑iαigi(ω) + ∑iβihi(ω) = f(ω) + αTg(ω) + βTh(ω)。其中后面的形式是向量的形式

对偶问题定义：

1. 最大化 θ(α, β) = inf所有ω( L(ω, α, β) )，

2. αi >=0，其中i=1~K

inf指求括号内的最小值，即在限定了α,和β，去遍历所有的ω，求L的最小值。所以每确定一个α,和β，都能算出一个最小值，θ(α, β)只和α, β有关。然后再针对所有的α, β，再求θ的最大值。里面求最小，外面求最大。

定义：G = f(ω*) - θ(α*, β*) >=0，G叫做原问题与对偶问题的间距（Duality Gap）。对于某些特定的优化问题，可以证明G等于0。

强对偶定理：若f(ω)为凸函数， g(ω) = aω+b，h(ω）=cω+d，则此优化问题的原问题与对偶问题间距为0。即f(ω*) = θ(α*, β*) => 对于所有的i=1-K，α*i = 0 或者gi(ω*) = 0

凸函数

凸函数：如果在函数图像上任取两点，函数图像在这两点之间的部分都在两点线段的下边，那么就成为凸函数，否则称为凹函数。凸函数只有一个极小值，比如x2，而sinx有多个极值。

对于任意（0,1）中有理数λ，有

如果f连续，那么λ可以改变成区间（0,1）中的任意实数。

几何意义只是一维的，而代数的定义可以是向量，即任意维。

将支持向量机的原问题转为对偶问题

注意转化后的对偶问题中的βi和αi对应着原来对偶问题的一个αi，因为gi(ω) <=0，而支持向量机的不等式的限制条件有两个，所以都写上了。

对向量求偏导，就是对其每个分量求偏导。

WTW，蹦出来个αj，只是个符号，因为写αi不合适了

对于上面的推倒后的式子，已知的是所有的y，和kernal函数，未知的是所有的α。怎么把求α转化为求W和b？根据上面W的公式就可以。

KKT条件对应到SVM上：

SVM算法流程分为训练流程和测试流程，训练时，先求出所有的α，再算b

可见所有的φ(x)都转成了kernel函数

核函数

线性核等于没用，解原问题和解对偶问题的复杂度一样。多项式核函数d是几维，就对应到几维。高斯核是低维映射到高维。

每个核函数都要调参数，多项式核函数要调的参数是d，高斯核要调的是方差。

SVM训练时的一个经验是，必须归一化，一般用高斯归一化，即减掉均值，然后除以平均值，而不是最小最大归一化。

SVM用高斯核的话，只有两个参数要调，一个是C平衡前面的W和后面的εi，另一个是高斯核中的方差。

C范围：2-5~215，方差范围：2-15~23，组合有21*19种

交叉验证的好处：

• 不使用训练样本进行测试，因为无法验出真实水平。
• 尽可能地充分利用训练样本，比如只有5000个样本，分成abcde五组，每次取出4份进行训练，另一份进行测试，保证每一次训练时，样本足够的多。

折数越多，训练模型越多，10折就是10个模型，5折就是训练5次。5000个样本，最多5000折，每次取4999个进行训练，1个进行测试。这种称为leave-one-out cross validation

支持向量20%左右正常，如果特别多，说明没有训练好，或者数据本身就没有规律。

ROC曲线

为什么同一个系统中TP增加，FP也增加？小平同志说，改革开放了，好的东西进来了，蚊子苍蝇也进来了。因为自身性能不变，把更多的正例识别称正例，那么一定也会将更多的反例识别为正例。同理FN增加=>TN增加。

ROC (Receiver Operating Character)曲线， 是一条横坐标FP，纵坐标TP的曲线。

给定一个模型，怎么画出ROC曲线？从小到大变换下面的阈值，每次变换一个阈值，测出TP和FP。FP等于0时，表示把所有的样本判为负例，此时TP也为0，FP等于1表示把所有的样本判为正例。

等错误率 (Equal Error Rate, EER)是两类错误FP和FN相等时候的错误率，可以直观的表示系统性能。

对于不同的应用，判别模型好坏的标准不同。对于人脸开锁的应用而言，容忍错误低，即要FP最小，或者是0情况下，FP的最大值。

ROC下的面积称为AUC，面积越大，一般性能越好。

可以用ROC曲线、EER、AUC，但不要单纯用识别率来判断，识别率高不代表性能就好（这是机器学习领域懂和不懂的人的一个区别）。

SVM处理多类问题

1. 改造优化的目标函数和限制条件，使之能处理多类。论文 SVM-Multiclass Multi-class Support Vector Machine
2. 一类 VS 其他类
3. 一类 VS 另一类

一类 VS 其他类：

如果一个样本被判为C1或C2，那就看哪一个负的多，因为y=-1，说明...是负的，看更偏向于谁。

一类 VS 另一类：

根据经验，改造公式的方法并不好用，因为SVM适合在两类中寻找最大间隔。

如果有N类，一类VS其他类的方法要做N个SVM模型，一类VS另一类要做(N*(N-1))/2个SVM模型。根据经验，后者更佳。