SVM(Support Vector Machine)读书笔记二（支持向量和Kernel方法）

在一个线性不可分的样本中，用添加多次项特征可以将两类样本分开，具体原理请参考这里，用SVM分类器也是同样道理。如果两类样本交叉越多，需要越高次的特征，模型就越复杂，这在存储上和计算资源上都是很大的开销。SVM用kernel方法就解决了这个问题，kernel方法是将高维度的计算放到低维度来做，最后得到的是高纬度上的模型。具体原理请看下面的推导。

特征转换

如果样本在低纬度空间不可分，那么可以将样本的特征从低维度空间投影到高纬度空间，如下图所示
SVM(Support Vector Machine)读书笔记二（支持向量和Kernel方法）
而一般从低纬度空间向高纬度空间投影的方法就是往已有的特征中添加多项式特征项，再来看下面一个图

上面三个图中，在(x1x1,x2x2)这个空间中，两类样本线性不可分，即在(x1x1,x2x2)空间中的所有线性模型都无法将这两类样本区分开。如果把这个空间投影到比如(x1x1,x2x2,x21x12,x21x2x12x2,x21x22x12x22,x21x32x12x23,x31x2x13x2,…)这样的一个空间中就变得线性可分了（当然有过拟合的风险），在这个高纬度的空间中的超平面表现在(x1,x2x1,x2)空间中就是图三所示的一条曲线，图二则是将(x1,x2x1,x2)投影到二次项组成的4维空间中。

SVM的对偶问题

假设已经通过ϕ(x)ϕ(x)将样本投影到了能够将两类样本分开的zz空间，那么需要解决的优化问题为：

m i n w, b 12 w T w; s . t . y n (w T ϕ (x) + b) \geq 1, n = 1... N minw,b12wTw;s.t.yn(wTϕ(x)+b)\geq1,n=1...N

上一篇中讲到可以用二次规划解这个问题，只要把Q,p,A,c丢进解二次规划的软件里就可以得到解，这里对应的特征是投影之后的高纬度特征。

Q = [0 0 T d 0 d I d]; p = 0; A = ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ y 1 y n x T 1 y 2 y 2 x T 2 . . . . . . . y n y n x T n ⎤ ⎦ ⎥ ⎥ ⎥ ⎥, c = 1 Q=[00dT0dId];p=0;A=[y1ynx1Ty2y2x2T.......ynynxnT],c=1

问题是，这里的Q是和投影之后的维度有关的，如果投影到的空间是很高维甚至无穷维，这个问题就没法解了。为了解这个问题，就需要把原来的问题转化成它的对偶形式，让这个问题的求解和转换后的维度没有关系，只和输入的样本的个数有关。

SVM的求解是一个带约束的最佳化问题：

m i n w 12 w T w; s . t . y n (w T x n + b) \geq 1, n = 1, 2... N minw12wTw;s.t.yn(wTxn+b)\geq1,n=1,2...N

解上面这个带约束的最佳化问题可参考Lagrange乘子法（可参考https://en.wikipedia.org/wiki/Lagrange_multiplier），把约束放进式子中，写成Lagrange表达式为：

L (b, w, α) = 12 w T w + \sum i = 1 i = N α i (1 - y n (w T z n + b)) L(b,w,α)=12wTw+\sumi=1i=Nαi(1-yn(wTzn+b))

首先，用 Lagrange 乘子法可以将上面的最优化问题写成下面的形式：

m i n w, b m a x α L (b, w, α) = m i n w, b 12 w T w + m a x α i \geq 0, i = 1.. N \sum i = 1 i = N α i (1 - y n (w T z n + b)) minw,bmaxαL(b,w,α)=minw,b12wTw+maxαi\geq0,i=1..N\sumi=1i=Nαi(1-yn(wTzn+b))

这里，为什么这个最优化问题和上面的n个不等式约束的优化问题是等价的呢？
上面优化过程中，先固定住w,b,根据αα来进行最大化，在w,b满足(1−yn(wTzn+b))≥0(1−yn(wTzn+b))≥0时候，最大化αα那项最大是无穷（这里w,b的集合假设为s1）；w,b满足(1−yn(wTzn+b))≤0(1−yn(wTzn+b))≤0时候，最大化是αα那项是0（这里w,b的集合假设为s2）。第二次是找到最小化那个表达式的w,b, 当然选取的w,b肯定是s2里面的，因为s1根本不可能最小化，所以在最后的解里(1−yn(wTzn+b))≤0(1−yn(wTzn+b))≤0肯定成立。

上式中，把w,bw,b固定住，变动αα，要得到最大的那个αα，那么minw,bL(b,w,α)minw,bL(b,w,α)比任何αα的项要大，那么minw,bmaxαL(b,w,α)≥minw,bL(b,w,α)minw,bmaxαL(b,w,α)≥minw,bL(b,w,α)，当然也比这里面变动αα取最大的那个要大即

m i n w, b m a x α L (b, w, α) \geq m a x α m i n w, b L (b, w, α) minw,bmaxαL(b,w,α)\geqmaxαminw,bL(b,w,α)

上面这个问题叫做Lagrange对偶问题，在满足KKT条件的时候，不等号可以改成等号，即这两个问题是等价的。在SVM这个问题中，刚好满足KKT条件（后面会讲到），因此求解不等号前面的问题可以转换为求解不等号后边的问题。这样的转换好处是，右边的问题是关于w,bw,b的没有约束的问题，而αα是带约束的，w,b没有约束可以直接通过求偏导等于0解出w,bw,b。
求解问题写成下面的形式：

m a x α m i n w, b 12 w T w + \sum n = 1 n = N α n (1 - y n (w T z n + b)) maxαminw,b12wTw+\sumn=1n=Nαn(1-yn(wTzn+b))

先对bb求偏导，可以得到：

\sum n = 1 n = N α n y n = 0 \sumn=1n=Nαnyn=0

把上面得到的条件代入原式子中得到

m a x α m i n w, b 12 w T w + \sum n = 1 n = N α n (1 - y n w T z n) maxαminw,b12wTw+\sumn=1n=Nαn(1-ynwTzn)

再对ww求偏导，让偏导等于0，得出

w = \sum n = 1 n = N α n y n z n w=\sumn=1n=Nαnynzn

再把上面得到的ww加入原问题中，可以得到:

m a x α m i n w, b 12 w T w + \sum n = 1 n = N α n - \sum n = 1 n = N α n y n w T z n) maxαminw,b12wTw+\sumn=1n=Nαn-\sumn=1n=NαnynwTzn)

m a x α m i n w, b - 12 (\sum n = 1 n = N α n y n z n) 2 + \sum n = 1 n = N α n) maxαminw,b-12(\sumn=1n=Nαnynzn)2+\sumn=1n=Nαn)

代入之后发现，w,bw,b都消失了，因此，就可以专心对αα求解了，写成如下：

m a x α \geq 0, w = \sum n = N n = 1 α n y n z n, \sum n = N n = 1 α n y n = 0 (- 12 (\sum n = 1 n = N α n y n z n) 2 + \sum n = 1 n = N α n) maxα\geq0,w=\sumn=1n=Nαnynzn,\sumn=1n=Nαnyn=0(-12(\sumn=1n=Nαnynzn)2+\sumn=1n=Nαn)

等价于

m i n α \geq 0 (12 \sum n = 1 N \sum m = 1 N α n α m y n y m z T n z m - \sum n = 1 n = N α n) minα\geq0(12\sumn=1N\summ=1NαnαmynymznTzm-\sumn=1n=Nαn)

s . t \sum n = 1 N y n α n = 0; α n \geq 0, n = 1, 2, 3... N s.t\sumn=1Nynαn=0;αn\geq0,n=1,2,3...N

KKT条件

原问题的条件：yn(wTϕ(x)+b)≥1yn(wTϕ(x)+b)≥1
对偶问题的条件：α≥0α≥0
对偶问题推导中需要满足的条件：∑n=Nn=1αnyn=0;w=∑n=Nn=1αnynzn∑n=1n=Nαnyn=0;w=∑n=1n=Nαnynzn
对偶问题中：αn(1−yn(wTzn+b)=0αn(1−yn(wTzn+b)=0(这里，最优化后，这个条件一定是满足的，0是最大值)。这里，αnαn和1−yn(wTzn+b)1−yn(wTzn+b)这两个项里必须有一个是0

满足了上面的KKT条件，这个问题就是原问题的对偶形式了，解这个问题就等于解原问题。而上面的最小化αα式子就是QP问题的标准形式了，对应的，只要求出Q,p,A,c，然后丢到解二次规划的软件中就可以解得所有的αα。
化简整理一下，对应的对偶问题是

m i n α 12 α T Q α + p T α; s u b j e c t t o . a T i α \geq c i minα12αTQα+pTα;subjectto.aiTα\geqci

Q矩阵是N乘N的矩阵，其中的每一项qn,m=ynymzTnzmqn,m=ynymznTzm, 其他几个参数表示过程这边就省略了。在这个Q矩阵中如果z是很高维的话，，而且这个Q不是一个稀疏矩阵，N很大的话会消耗非常多的计算和存储资源，z空间维度很高加上N很大，这个QP问题就解不出来了。（注：kernel技巧就是为了解决这个问题诞生的，后面会讲到）

Support Vector

上面KKT条件中，有一个αn(1−yn(wTzn+b)=0αn(1−yn(wTzn+b)=0，要使得它成立，那么αα和1−yn(wTzn+b)1−yn(wTzn+b)必须有一个为0。如果αnαn不为0，那么yn(wTzn+b)=1yn(wTzn+b)=1肯定成立，而这样的点刚好是在margin上面。因此从解得的答案中看出，αn>0αn>0的那些点都是Support Vector。

因此w可以表示成Support Vector的形式,w=∑SVαnynznw=∑SVαnynzn,即支持向量的线性组合。而b则只需要将任意一个支持向量代入yn(wTzn+b)=1yn(wTzn+b)=1中即可求解

b = y i - w T z i = y i - (\sum S V α n y n z n) z i = y i - \sum S V α n y n z n z i b=yi-wTzi=yi-(\sumSVαnynzn)zi=yi-\sumSVαnynznzi

w和b都代入最佳超平面方程中，得到：

g s v m (x) = w z + b = \sum s v α n y n z T n z + b = \sum s v α n y n k (x n, x) + b gsvm(x)=wz+b=\sumsvαnynznTz+b=\sumsvαnynk(xn,x)+b

Kernel技巧

上面推导过程中，在解二次规划问题中的qn,m=ynymzTnzmqn,m=ynymznTzm，由于这是一个dense矩阵，并且在z空间很高维的情况下，会消耗巨大的计算和存储资源。kernel要解决的问题就是把z空间中的计算放到x空间来做，同时z空间的计算和x空间的计算是等价的。
x空间通过特征转换变到z空间，z空间是长这个样子：

ϕ (x) = (1, x 1, x 2 . . . x d, x 21, x 1 x 2 . x 1 x d, x 2 x 1, x 22, . . . x 2 d) ϕ(x)=(1,x1,x2...xd,x12,x1x2.x1xd,x2x1,x22,...xd2)

d维的x空间，变到z空间维度就达到了d的指数次方个，在z空间的两个向量内积，可以写成下面的形式

ϕ (x 1) ϕ (x 2) = 1 + \sum i = 1 d x 1 x 2 + \sum i = 1 d \sum j = 1 d x 1 i x 1 j x 2 i x 2 j = 1 + \sum i = 1 d x 1 x 2 + \sum i = 1 d x 1 i x 2 i \sum j = 1 d x 1 j x 2 j = 1 + x T x + (x T x) 2 ϕ(x1)ϕ(x2)=1+\sumi=1dx1x2+\sumi=1d\sumj=1dx1ix1jx2ix2j=1+\sumi=1dx1x2+\sumi=1dx1ix2i\sumj=1dx1jx2j=1+xTx+(xTx)2

上面这个公式说明，在z空间的内积可以放在x空间进行，得到的结果是一样的。
假设k(x1,x2)=1+xT1x2+(xT1x2)2k(x1,x2)=1+x1Tx2+(x1Tx2)2，之前推导出来的qn,m=ynymzTnzm=ynymk(xn,xm)qn,m=ynymznTzm=ynymk(xn,xm)，原来的zTnzmznTzm需要在很高维进行，现在利用这个kernel方法，简化了这个计算。

Kernel的类型

上面的空间变换中，ϕ(x)=(1,x1,x2…xd,x21,x1x2.x1xd,x2x1,x22,…x2d)ϕ(x)=(1,x1,x2…xd,x12,x1x2.x1xd,x2x1,x22,…xd2)
如果在常数项前加上一些值，在一次项上加上一些值，在两次项上加上一些值，那么可以表示成两次的kernel。

ϕ (x) = (β + φ x T 1 x 2) 2 ϕ(x)=(β+φx1Tx2)2

另外还有高次的kernel,可以表示成

ϕ (x) = (β + φ x T 1 x 2) Q ϕ(x)=(β+φx1Tx2)Q

多次项kernel也有限制，比如真实的模型如果高于指定的次数，那么就不太会得到非常好的模型。
高斯核函数（又叫RBF Kernel）就解决了这个问题，它可以将x空间的向量投影到无穷维（又叫西伯尔特空间）。定义如下：

k (x 1, x 2) = e x p (- | x 1 - x 2 | 2) k(x1,x2)=exp(-|x1-x2|2)

那么它是如何映射到无穷维的呢，可以通过泰勒展开推导如下：

k (x 1, x 2) = e x p (- x 21 + 2 x 1 x 2 - x 22) = e x p (- x 21) e x p (2 x 1 x 2) e x p (- x 22) = e x p (- x 21) e x p (- x 22) \sum i = 0 \infty (2 x 1 x 2) i i! = \sum i = 0 \infty e x p (- x 21) 2 x i 1 i! - - - - \sqrt e x p (- x 22) 2 x i 2 i! - - - - \sqrt = ϕ (x 1) T ϕ (x 2) k(x1,x2)=exp(-x12+2x1x2-x22)=exp(-x12)exp(2x1x2)exp(-x22)=exp(-x12)exp(-x22)\sumi=0\infty(2x1x2)ii!=\sumi=0\inftyexp(-x12)2x1ii!exp(-x22)2x2ii!=ϕ(x1)Tϕ(x2)

ϕ (x) = e x p (- x 2) (1, 2 x - - \sqrt, 2 x 2 2! - - - - \sqrt 2 x 3 3! - - - - \sqrt, . . .) ϕ(x)=exp(-x2)(1,2x,2x22!2x33!,...)

利用高斯kernel可以把特征转换到无穷维空间，理论上可以将任何两类样本分开，这就是高斯kernel强大的地方，但是缺点是参数弄不好会导致模型过拟合，于是在参数选择过程中要小心。

多项式核由于是幂的形式，如果在x很大的情况下，transform之后的数值会非常大或者非常小，这会给模型造成不精确的问题，但是高斯核就避免了这个问题，它的值都是在0和1之间
多项式核的优势在于如果你知道模型项不会很高的情况，用这个可以更好的解释模型。实在是无法想象无穷维空间是怎么样的。

除了上面说到的这些kernel，还可以自定义一些kernel，如果你不喜欢上面提到的kernel的特征转换，那么可以自己定义，但是不是所有的函数都可以是kernel（因为不是所有函数可以转化成两个相同向量内积的形式），需要满足Mercer’s condition:

Kernel矩阵必须是对称的
kernel矩阵必须是半正定的

总结

有了核函数和上面的推导，最后的svm函数可以写成

g s v m (x) = w x + b = \sum s v α n y n z T n z n + b = \sum s v α n y n k (x n, x) + b gsvm(x)=wx+b=\sumsvαnynznTzn+b=\sumsvαnynk(xn,x)+b

b = y i - \sum S V α n y n z n z i = y i - \sum S V α n y n k (x n, x i) b=yi-\sumSVαnynznzi=yi-\sumSVαnynk(xn,xi)

有了核函数，可以将低维空间的特征投影到高维空间同时只消耗低维空间的计算量，而让模型更强大（可以区分任意样本）；有了支持向量，在计算w的时候只需要少许几个样本（Support Vector是稀疏的），同时也减少了计算量。于此同时，可以让模型获得更强大的能力，区分更复杂的数据，但是模型一复杂，就会出现很大的overfit问题，虽然large margin在一定程度上保证了泛化能力，但是在无穷维空间，什么事情都会发生。
上面的推导都是通过把样本映射到高维度，使得样本完全线性可分，然后用相关算法把样本分开。这种方法会有很大的过拟合的风险，想象下如果数据有很多噪声，本来可以在低维分开的，非得去高维空间。Soft margin SVM就是用来解决这个问题，它能够容忍模型有一定噪声的存在，从而减小了发生过拟合问题的风险。