coursera机器学习技法札记(1-4)——Support Vector Machine

1 Linear Support Vector Machine

1.1 Coursera Introduction

　　本门课程主要内容是围绕特征转换进行的，并包括三种主要的思想：
　　(1)怎样使用数字的特征并控制其复杂度：该角度启发了SVM模型。
　　(2)怎样构建并混合使用具有预测能力的特征：启发了adaboost模型。
　　(3)发现并利用潜在的特征：启发了Deep Learning模型。

1.2 Large Margin Separating Hyperplane

　　最大间隔的目标是，使得最靠近划分数据集的超平面的点到超平面的距离最大，同时保证超平面能正确划分所有点。即：

$$max(min_{1…n}distance(x_n,w))$$ $$s.t. every　y_n (w^T x_n+b)≥0$$

1.3 Standard Large-Margin Problem

　　首先计算$distance(x_n,w)$，套用几何公式，$x_n$到以$w$为法向量的超平面的距离是：

$$distance(x_n,w)=\frac{||w^T x_n-b||}{||w||}$$
同时，根据条件限制，我们有$y_n (w^T x_n+b)≥0$，故上式可写为：
$$distance(x_n,w)=\frac{1}{||w||} y_n (w^T x_n-b)$$
同时我们可以注意到，对$w$进行放缩(即每个分量同时乘以或除以一个常数)是对$distance(x_n,w)$没有影响的，所以我们对$w$进行缩放，令$min　y_n (w^T x_n-b)=1$，则整个问题变成了：
$$max\frac{1}{||w||}$$ $$s.t. 　min　y_n (w^T x_n+b)=1$$
鉴于约束条件难解，我们在不改变最优解的条件下放宽约束：
$$max\frac1{||w||}$$ $$s.t. 　∀ y_n (w^T x_n+b)≥1$$
这样做不改变最优解的原因是，当存在$w$使得$∀ y_n (w^T x_n+b)=c≥1$，我们可以通过不等号两边同时除以$c$，使得$w:=\frac{w}{c},b:=\frac{b}{c}$在满足约束的时候获得更大的$\frac{1}{||w||}$ ，因此最优解一定符合约束条件。
　　最后，我们将优化目标去绝对值，转换为对偶问题，并加上常数方便以后的运算：
$$max　\frac{1}{2} w^T w$$ $$s.t. 　∀ y_n (w^T x_n+b)≥1$$

1.4 Support Vector Machine

　　以上的优化目标可以用二次规划$QP(Q,p,A,c)$解决，二次规划的目标是：

$$max　w^T Qw+p^T w$$ $$s.t. 　Aw≥c$$
在此将b作为w_0加入 w后对照使用即可。

1.5 Reason behind Large-Margin Hyperplane

　　本节叙述了SVM能工作的理论基础。可以从优化目标内看出，SVM的目标是在限制$y_n (w^T x_n+b)≥1$的条件下对$w^Tw$取最小，而regularize是在$w^T w<c$的前提下使得$y_n (w^T x_n+b)$。
　　从VC维的角度来看，由于限制了最大边际至少大于1，因此使得一些能被PLA打散的数据不能被SVM打散，导致其VC维降低。

2 Dual Support Vector Machine

2.1 Motivation of Dual SVM

　　由于我们希望SVM能进行非线性划分，而通过多项式特征转换进行非线性划分会导致大量的VC维，因此我们希望找到一种方法使得其复杂度能与多项式特征个数无关。
　　本节后半部分介绍了用拉格朗日乘子来解带约束的优化问题，并解释了拉格朗日乘子的工作原理。

2.2 Largrange Dual SVM

　　我们希望将原问题转化为对偶问题：

$$min_{b,w}(max_{all　α_n≥0}L(b,w,α))≥max_{all　α_n≥0}(min_{b,w}L(b,w,α))$$
当满足KKT条件时不等号可以化为等号，推导过程如下：
$$max_{all　α_n≥0}(min_{b,w}\frac{1}{2} w^T w+∑_{n=1}^Mα_n (1-y_n (w^T x_n+b)))$$
对上式中最小化部分的$b$求导，并使结果等于0，得到结果：
$$∑_{n=1}^Mα_n y_n =0$$
对上式中最小化部分的w求导，并使结果等于0得到结果：
$$w=-∑_{n=1}^Mα_n y_n x_n$$
将这两者分别带入优化目标公式中可以得到对偶问题的优化目标公式：
$$max_{all　α_n≥0,∑α_n y_n =0,w=∑α_n y_n x_n }(-\frac{1}{2} ||∑_{n=1}^Mα_n y_n x_n ||^2+∑_{n=1}^Mα_n )$$
　　另外，KKT的条件是：
　　(1)满足原问题的约束；
　　(2)拉格朗日乘子不小于0(在上式中写为$α$)；
　　(3)对偶问题的各变量(即$w$和$b$)求导结果为0；
　　(4)拉格朗日项(即拉格朗日乘子乘以约束)均为0(要么拉格朗日乘子为0，要么约束项等于0)；
　　可以看出，在以上的推导、转换的过程中已经满足了KKT的全部条件，因此可以判定能转化为对偶问题。

2.3 Solving Dual SVM

　　我们可以将上节的最优化目标增加符号后转换为最小化优化问题，并利用二次规划解$α$。这里需要注意的是，由于在对应的二次优化问题中会出现一个极大密集矩阵$Q_{p,q}=y_p y_q x_p x_q$，因此建议使用对SVM特别优化的二次规划计算包。
　　当解得$α$后，我们可以通过

$$w=-∑_{n=1}^Mα_n y_n x_n$$
来解得$w$，并通过
$$α_n (1-y_n (w^T x_n+b))=0$$ $$b=y_n-w^T x_n$$
来解得$b$。以上公式由KKT条件得出。另外我们可以注意到一个有意思的现象是，当$α_n$不等于0时，$y_n (w^T x_n+b)=1$，说明该样本是支持向量。

2.4 Message behind Dual SVM

2.4.1 SVM与PLA的比较
　　可以发现，SVM与PLA在对$w$的求解上都是类似的，即$w$是样本点$xy$的线性组合。其区别在于，SVM采用了支持向量的样本点来求解$w$，而PLA用“犯错”的样本点来进行线性组合求解$w$。
2.4.2 原始SVM与对偶SVM的比较
　　原始SVM是通过拉伸$w$和$b$来找到合适的$w$和$b$，其与$w$的复杂度(特征向量的长度)有密切关系。而对偶问题通过找支持向量(判断$α_n$是否为0)来求解$w$。其中，原始问题由于与复杂度关系很大，因此适用于特征不多的情况下，而对偶问题由于表面上与特征数量无关，因此使用在数据量少而特征较多的情况下。
　　但需要注意的是，对偶问题并没有使得计算复杂度与特征数量完全独立，因为在求对偶问题的矩阵时，$Q_{p,q}=y_p y_q x_p x_q$很明显和特征数量有关系。
另外注意到的一点是，在边界上的点未必是支撑向量，因为它的$α_n$也同样可能是0.

3 Kernel Support Vector Machine

3.1 Kernel Trick

　　在SVM的对偶问题中，计算$Q_{p,q}=y_p y_q x_p x_q$时依旧会与特征数量相关，因此有一个trick可以简化多次特征的计算，在这里设$z$是$x$的多次特征转换之后的特征：

$$K(x,x')=z^T z'=1+∑_{i=1}^nx_i x_i'+∑_{i=1}^n∑_{j=1}^nx_i x_j x_i'x_j'=1+x^T x+(x^T x)^2$$
　　因此，只要有关$z^T z'$的特征计算，都可以通过计算$x^T x$来实现。这个函数叫核函数(kernel function)。同时，我们还可以通过该方法来计算$w^T z'$：
$$w^T z'=(∑_{n=1}^Mα_n y_n z_n 〗) z'=∑_{n=1}^Mα_n y_n z_n^T z'=∑_{n=1}^Mα_n y_n K(x_n^T x')$$
其中$M$是支持向量集。通过这种方法，我们能极大缩减高次特征转换所需要的计算资源。

3.2 Polynomial Kernel

　　对核函数的计算进行进一步简化，以二次核函数为例，我们设中间一次项系数为2，代表着我们对高次空间$z$中一次项的系数做了伸缩：

$$K_2 (x,x' )=1+2x^T x+(x^T x)^2=(1+x^T x)^2$$
可以看到，我们再一次简化了计算。将该方法扩展至高次，并添加系数以控制伸缩程度：
$$K_2 (x,x' )=(δ+γx^T x)^Q$$
　　这样，计算资源再一次得到了缩减，并且可以通过系数来控制伸缩程度。这种放缩的方法本质上对应着距离定义的变化。

3.3 Gaussian Kernel

　　我们可以利用高斯函数作为核函数，即：

$$K(x,x' )=exp(-γ||x-x'||^2)$$
由于高斯函数可以通过泰勒展开成为无限高次的多项式组合，因此高斯核代表了无限高次的特征转化。
　　但需要注意的是，$γ$过高时依旧会发生过拟合的现象。

3.4 Comparison of Kernels

　　本节对几个kernel做了对比。
　　(1)线性SVM的好处是用原始问题求解速度快，并且不用担心过拟合问题，缺点是不能解决非线性数据分类。
　　(2)多次核的好处是可以解决非线性分类问题，但参数多难以选择，并且在次数高的时候得到的核的值要么很大，要么逼近0，因此在低阶的时候可以考虑使用多次核。同时，当次数很低，例如是2或是3的时候，或许直接构造出多次特征空间然后用线性SVM的原始问题求解可能会更快。
　　(3)高斯核的好处在于非常强大，并且参数少。缺点在于计算复杂，容易过拟合。
　　另外，可以将核函数看成是两个向量的相似度，但是由于核的出处是内积，因此如果要构造新的核，需要在一定程度上满足内积的特点：
　　(1)对称性，所定义的核必须满足两个向量交换位置值不变。
　　(2)所有样本两两之间相互使用核函数进行计算所得到的矩阵是半正定的。

4 Soft-Margin Support Vector Machine

4.1 Motivation and Primal Problem

　　我们在原优化目标的基础上加入容忍错误的条目并使错误更轻成为优化目标之一：

$$min_{w,b,ε}\frac{1}{2} w^T w+C∑_{n=1}^Nε$$ $$s.t.∀y_n w^T x_n+b≤1-ε_n$$ $$∀ε_n≥0$$
其中，$C$代表了margin的大小与容忍样本错误度的相对比例，$C$越大，代表我们希望错误程度越低，即SVM更严格，margin越低，反之亦然。$ε_n$代表了第$n$个节点偏离超平面的程度。

4.2 Dual Problem

　　我们按照原来的hard-SVM的方法同样来推导soft-SVM。首先通过拉格朗日乘子将问题转化为min-max问题，然后利用KKT条件转化为max-min问题，在这里注意到的是，设条件$∀y_n w^T x_n+b≤1-ε_n$的拉格朗日乘子为$α_n$，$∀ε_n≥0$的拉格朗日乘子为$β_n$，则先对$ε_n$求导，我们可以得到$β_n=C-α_n$，代入式子后发现和原来hard-SVM的形式相同，因此soft-SVM的对偶形式为：

$$max_α(-\frac{1}{2} ||∑_{n=1}^Mα_n y_n x_n ||^2+∑_{n=1}^Mα_n )$$ $$C≥α_n≥0$$ $$∑α_n y_n =0$$
其中仅第二行的条件有所区别，原因是新加入条件$β_n=C-α_n≥0$。

4.3 Message behind Soft-Margin SVM

　　注意到在最后求解$b$的时候Soft-SVM会与hard-SVM有所区别，通过KKT条件我们可以知道：

$$α_n (1-ε_n-y_n (w^T x_n+b))=0$$ $$(C-α_n ) ε_n=0$$
可以看到，我们必须令$0<α_n<C$才能使得$ε_n=0$并且通过
$$1-y_n (w^T x_n+b)=0$$
解出$b$，这部分的样本叫free-support vector。当$α_n=C$时，$ε_n>0$，代表这部分样本到超平面的距离小于最小边界，或者分类错误了。当$α_n=0$时$ε_n=0$，因此代表这些样本非常安全，离边界很远。

4.4 Model Selection

　　选择最好模型参数的方法是利用验证集，同时，SVM还有一个非常有意思的理论可以在某种程度上减少我们验证的次数。
　　在交叉测试的留一法中，如果被选中作为测试点的样本是非支持向量，则该点的测试结果一定是正确，同时如果把它放进训练集再换另一个非支持向量出来测试，结果同样是正确。而如果把支持向量作为测试样本，结果未必正确。因此，SVM的误差上限是支持向量数量除以样本总量。
　　需要注意的是，由于仅仅是误差上限，因此常常用来排除“错误答案”。