SVM

1.motivation

对于一组带标签 $y\in R$ 的特征向量 $\mathbf{x}\in R^{n}$ ,如果他们是线性可分的，我们希望用一个超平面(n-1维的) $\mathbf{W^{T}\mathbf{x}+b}=0$ 将他们划分开

2.选取超平面原则

让离 $\mathbf{W^{T}\mathbf{x}+b}=0$ 这个超平面的最近的点的距离最大,形式化表述为
对于任意样本 $｛\mathbf{x_0},..\mathbf{x_i}..\mathbf{x_{m}}｝$ 和他的标签 $｛y_i｝$ 满足 $y_i(\mathbf{W^{T}\mathbf{x_i}+b})>0$ 优化目标为：

$\mathop{\max}\limits_{\mathbf{W},b}(\mathop{\min}\limits_i\frac{|\mathbf{W^{T}\mathbf{x_{i}}+b}|}{||\mathbf{W}||})$

其中min过程是遍历i得到，max是对b， $\mathbf{W}$ 改变而得到

理解：让最小距离最大可以忍受更大的噪声波动，使得模型的variance更小

一个比较形象的对于优化过程的描述是让这条线（超平面）一直变粗，一直能变到最粗与样本点相交为止

3.问题简化

3.1简化距离的计算和约束条件

如果只是想让超平面与两类样本距离最大的话，其实距离大于离超平面最近的点的距离的点（人话说：离的更远的点）是不必要的，他们是不会影响最后的结果的。而且对于距离d：
$\mathop{\min}\limits_i\frac{|\mathbf{W^{T}\mathbf{x_{i}}+b}|}{||\mathbf{W}||}$
我们总是可以通过伸缩变化（例如所有样本左乘一个满秩的矩阵）使得最小距离 $d=\frac{1}{\mathbf{||W||}}$ ,为了简化运算，W又跟i无关所以min函数可以消去，则问题又可以转化为：
对于任意样本 $｛\mathbf{x_0},..\mathbf{x_i}..\mathbf{x_{m}}｝$ 和他的标签 $｛y_i｝$ 满足 $y_i(\mathbf{W^{T}\mathbf{x_i}+b})\geq1$ (这里蕴含了最小距离为 $d=\frac{1}{\mathbf{||\mathbf{W}||}}$ )优化目标为：

$\mathop{\max}\limits_{\mathbf{W},b}\frac{1}{\mathbf{||W||}}$
又因为习惯求最小值和为了之后的简化
最终命题简化为
对于任意样本 $｛\mathbf{x_0},..\mathbf{x_i}..\mathbf{x_{m}}｝$ 和他的标签 $｛y_i｝$ 满足 $y_i(\mathbf{W^{T}\mathbf{x_i}+b})\geq1$ (这里蕴含了最小距离为 $d=\frac{1}{\mathbf{||\mathbf{W}||}}$ )优化目标为：

$\mathop{\min}\limits_{\mathbf{W},b}\frac{1}{2}||\mathbf{W}||^2$

注意到限制条件是一次不等式，目标是二次式，其实可以使用二次规划来解决。二次规划求解可以套QP二次规划的形式,python可以用scipy的包求解。

3.2脱掉约束和转化为对偶问题

因为现在有m个样本，约束条件其实有m个,求解的变量其实是n+1个（ $\mathbf{X_i}\in R^n$ 加上一个偏移量b），如果n比m大很多的话，求解会比较困难。

因为有比较确定的约束条件，可以考虑使用拉格朗日乘子法求其条件极值。则可以设拉格朗日函数为
$L(\mathbf{\alpha},\mathbf{W},b)=\frac{1}{2}||\mathbf{W}||^2+\sum_{i=0}^{m-1}\mathbf{\alpha_i}(1-y_i(\mathbf{W^T\mathbf{x_i}+b}))$
优化目标则变为
$\mathop{\min}\limits_{\mathbf{W},b}\mathop{\max}\limits_{\forall\alpha_i\geq0}(L(\mathbf{\alpha},\mathbf{W},b))$

这里便把约束条件给塞进优化目标里了，实现上来讲免去了对样本的搜索。

为什么里面套了一个max？因为

$\sum_{i=0}^{m-1}\mathbf{\alpha_i}(1-y_i(\mathbf{W^T\mathbf{x_i}+b}))\leq0$

使得 $L(\mathbf{\alpha},\mathbf{W},b)$ 比起我们的理想值，总是偏小，所以需要max过程让他接近理想值。

3.2.1 乘子为什么大于等于0

这种凸优化问题可以表示为:
$\left \{ \begin{array}{c} \mathop{min}f(\mathbf{x})\\ \mathop{h}(\mathbf{x})\leq0 \end{array} \right.$
为什么这里设置了 $\alpha_i\geq0$ ?，L是一个凸函数，约束条件是线性的，不等式的约束函数的梯度和凸函数的梯度相反，而拉格朗日乘子法要求 $f^{'}(x)+\lambda h^{'}(x)=0$ (向量共线等价条件),所以拉格朗日乘子必大于等于0，这里是直觉性的说明，详细可看KKT条件推导。然而抛开优化理论的内容，光看拉格朗日函数也能推出 $\alpha_i\geq0$ 。还是因为
$\sum_{i=0}^{m-1}\mathbf{\alpha_i}(1-y_i(\mathbf{W^T\mathbf{x_i}+b}))\leq0$
如果 $\alpha_i<0$ ,那在max过程中 $L(\mathbf{\alpha},\mathbf{W},b)$ 会变无限大，使得整个优化过程无效。

3.2.2 对偶问题转化

转化为对偶问题就是把min跟max互换，即原问题对偶形式为：
$\mathop{\max}\limits_{\mathbf{\forall\alpha_i}\geq0}\mathop{\min}\limits_{\mathbf{W},b}(L(\mathbf{\alpha},\mathbf{W},b))$
理论上，一个函数的最大值中最小的应该是比其最小值中最大的要大，即：
$\mathop{\min}\limits_{\mathbf{W},b}\mathop{\max}\limits_{\forall\alpha_i\geq0}(L(\mathbf{\alpha},\mathbf{W},b))\geq\mathop{\max}\limits_{{\forall\alpha_i}\geq0}\mathop{\min}\limits_{\mathbf{W},b}(L(\mathbf{\alpha},\mathbf{W},b))$
这样差距称之为对偶差距，或者说成为两个问题有弱对偶性，但是因为SVM的场景是
1.凸优化问题 2.总能找到平面分开两类样本（有解） 3.线性约束条件
所以对偶差距被消除，弱对偶性变为强对偶性。

一个几何上直观的example:

SVM学习笔记
那么转化成对偶的好处在哪呢？

注意对于内部
$\frac{1}{2}||\mathbf{W}||^2+\sum_{i=0}^{m-1}\mathbf{\alpha_i}(1-y_i(\mathbf{W^T\mathbf{x_i}+b}))$
因为对偶问题的min过程中 $\alpha_i$ 是固定的,内部只有 $\mathbf{W},b$ 是变量且两者没有被约束，可以考虑直接求偏导,得偏导为0，联立方程组：
$\left \{ \begin{array}{c} \frac{\partial{L}}{\partial{b}}=-\sum_{i=0}^{m-1}\alpha_iy_i=0\\ \frac{\partial{L}}{\partial{\mathbf{W}}}=\mathbf{W}-\sum_{i=0}^{m-1}\alpha_iy_i\mathbf{x_i}=0 \end{array} \right.$
解得：
$\left \{ \begin{array}{c} \sum_{i=0}^{m-1}\alpha_iy_i=0\\ \mathbf{W}=\sum_{i=0}^{m-1}\alpha_iy_i\mathbf{x_i} \end{array} \right.$
这样以来 $\mathbf{W}$ 被 $\mathbf{\alpha}$ 所表示了，b则是因为系数为0消掉了，现在目标函数只跟 $\mathbf{\alpha}$ （因为样本是固定的）有关，将上述结果带回 $L$ ，优化目标则是：
$\mathop{\max}\limits_{\forall\alpha_i\geq0,\sum_{i=0}^{m-1}\alpha_iy_i=0}(-\frac{1}{2}||\sum_{i=0}^{m-1}\alpha_iy_i\mathbf{x_i}||^2+\sum_{i=0}^{m-1}\alpha_i)$
现在优化问题求解难度主要取决于样本数量 $m$ 了（虽然在对 $\mathbf{x}_i$ 取模时还是会涉及到维度，但并不是像在一开始是在 $R^n$ 下对 $\mathbf{W}$ 进行搜索了）。

3.2.3 如何求解

对于SVM，KKT条件可以具体为：
$1.y_i(\mathbf{W^T}\mathbf{x_i}+b)\geq1$ （primal feasible）
$2.\alpha_i\geq0$ （dual feasible）
$3.\sum_{i=0}^{m-1}y_i\alpha_i=0$ (dual-inner optimal)
$4.\alpha_i(1-yi(\mathbf{W}^T\mathbf{x}_i+b))=0$ (primal-inner optimal)

$\mathbf{W}$ 可以通过偏导结果直接求出
而b在偏导结果反代时被消掉了?那该怎么求呢？第4个条件表明在max过程中要不是 $\alpha_i=0$ ，要不就是距离d等于 $\frac{1}{||\mathbf{W}||}$ 。当情况是后者时，便可以得出
$b=y_i-\mathbf{W}^T\mathbf{x}_i$
这表示其实只有在这分割边界的样本点在求解中是有效的,这些点就命名为Support Vector

最关键的 $\mathbf{\alpha}$ 可以通过SMO或者再次通过二次规划的手段求得

3.3 kernel trick

将优化目标内部展开可得：
$\mathop{\max}\limits_{\forall\alpha_i\geq0,\sum_{i=0}^{m}\alpha_iy_i=0}(-\frac{1}{2}\sum_{i=0}^{m-1}\sum_{j=0}^{m-1}\alpha_i\alpha_jy_iy_j\mathbf{x}_i^T\mathbf{x}_j+\sum_{i=0}^{m-1}\alpha_i)$
可以看到内部涉及到样本之间内积的计算。引入kernel trick有两种解释

解释1

在原始的坐标系下，我们的样本不一定总是线性可分的，则需要把它映射到高维空间,在高维度下，从其他的角度可能就会得到一个平面能隔开样本。
然而高维度下对于内积计算话费是巨大的,便可以通过核技巧，让他在低维下计算高维的内积。所以我们并不需要知道具体是怎么升维的，只要用常见的核函数往里套，看效果就行。任何函数 $f(x_i,y_j)$ （x,y可以是向量），其对应值矩阵 $P_{ij}$ 是半正定的对称矩阵，则函数的值一定是某个高维希尔伯特空间的内积（源自西瓜书）

解释2

核函数是用来描述样本相似度的，越大样本之间越相似，只不过在原始问题中这个核函数恰好就是内积而已。简单的直接点乘效果不好，那就试试其他的核函数。用内积描述距离的话,边界就是线性的，而其他的就是曲线（这个比较观点general，上课老师教的也是这个）

常见kernel:
Linear:
$\kappa(\mathbf{x},\mathbf{y})=\mathbf{x}^T\mathbf{y}$
Polynomial:
$\kappa(\mathbf{x},\mathbf{y})=(\gamma\mathbf{x}^T\mathbf{y}+\zeta)^P$
对于其中的参数, $\gamma$ 代表在次数固定的情况下，决策边界之间的间隙的大小（或者说超平面的厚度，都不严谨）（距离=1/相似度）。一般来说大 $\gamma$ 会增加variance，决策边界间隙会减小，会增加SV的数量，因为对应的高维空间会很复杂，决策边界也会很复杂，样本在边界上概率会增大。*(应该跟具体优化过程有关)
SVM学习笔记
而 $\zeta$ 表示bias，最简单的线性场景就可以理解。
太高的P并不一定会带来甚至在训练集上的好表现，因为目标要不就是太小要不就是太大，容易优化失败，而且也很容易造成对于SV的过拟合，例如决策边界的划分区域只包含SV。而且二维投影上决策边界视觉上可能会不能划分样本，因为高维空间的复杂性。
SVM学习笔记
Gaussian:
$\kappa(\mathbf{x},\mathbf{y})=e^{-\frac{||\mathbf{x}-\mathbf{y}||^2}{2\sigma^2}}$
这个最常用，因为首先函数有界，不会突然跑很大，然后参数少。其对应的映射函数可以用 $e^x$ 的泰勒展开来得到,注意内积就是逐项相乘再求和的形式（例如对于一维样本x，一个简单的核函数 $\kappa(x,x')=e^{-(x-x')^2}$ ,其对应映射 $\phi(x)=e^{-x^2}(1,...\sqrt{\frac{2^i}{i!}}x^i,....)$ ，相当于是映射到了无穷维）。
当 $\sigma$ 特别大时，相似度增大，决策边界间隙会减小，会有更平滑的边界，因为其方差小，variance也会小。
当σ变小，除了上面反之显然的东西，SV还会变多，因为单个样本会对优化目标造成很大的影响，也应该跟优化过程有关，因为每两个样本核函数结果都会差距很远，总有样本会有更大的影响（as σ decreases），则被选为SV概率会越大。（优化过程中，这些影响大的样本，会影响其对应α的取值），还有一个intuitive是当σ很小，相当于正态分布的图像变的很尖，每个样本只会对跟他相近的边界很敏感（这种参数作用，都可用primal问题来理解，因为几何意义比较明确）。这里图片取的是σ的倒数
SVM学习笔记

之后把所有的涉及内积计算换成kernel的计算就好。如：
对于优化目标
$\mathop{\max}\limits_{\forall\alpha_i\geq0,\sum_{i=0}^{m}\alpha_iy_i=0}(-\frac{1}{2}\sum_{i=0}^{m-1}\sum_{j=0}^{m-1}\alpha_i\alpha_jy_iy_j\kappa(\mathbf{x}_i,\mathbf{x}_j)+\sum_{i=0}^{m-1}\alpha_i)$
（在优化过程中， $y_iy_j\kappa(\mathbf{x}_i,\mathbf{x}_j)$ 会一直重复计算，最好在优化之前拿个矩阵存下来）
对于b的计算：
$b=\mathbf{y_{\mathbf{s}}}-\sum_{i=0}^{m-1}\alpha_iy_i\kappa(\mathbf{s},\mathbf{x_i})$
对于预测来说：
$y=sign(\sum_{i}\alpha_iy_i\kappa(\mathbf{s_i},\mathbf{x})+b)$

3.4 soft-margin

就算我们避免使用比较复杂的kernel，SVM可能还是会过拟合，因为hard-margin SVM坚持要把所有的样本准确的分开，就算对于一些noise。所以可以做一点折中，容忍少量的样本不能被分开，允许其在margin之中。

推导

对于primal优化目标可以修改为（again，因为几何意义明确）
$\mathop{\min}\limits_{\mathbf{W},b,\xi}\frac{1}{2}\mathbf{W}\mathbf{W^T}+C\sum_{i=0}^{m-1}\xi_i$
约束条件为
$y_i(\mathbf{W}^T\phi(\mathbf{x_i})+b)\geq1-\xi_i$
$\xi_i\geq0$
约束条件相较之前相当于是放宽了对每个点到超平面的距离限制，对于每个样本 $\mathbf{x}_i$ 设置一个容忍度 $\xi_i$ ,允许一些点在间隔为 $\frac{2}{||\mathbf{W}||}$ 的margin内部（margin仍然是按照 $(\mathbf{W}^T\phi(\mathbf{x_i})+b=1)$ 来设置的，因为predict只是用的W，跟 $\xi$ 无关），这里其实相当于是正则化处理，其中 $C$ 相当于是正则化的权重。

接着，仿造hard-margin的构造拉格朗日函数，脱掉约束。
$L(\mathbf{W},b,\mathbf{\xi},\mathbf{\alpha},\mathbf{\beta})=\frac{1}{2}\mathbf{W}\mathbf{W^T}+C\sum_{i=0}^{m-1}\xi_i+\sum_{i=0}^{m-1}\alpha_i(1-\xi_i-y_i(\mathbf{W}^T\phi(\mathbf{x_i})+b))-\sum_{i=0}^{m-1}\beta_i\xi_i$

则问题现在变为：
$\mathop{\min}\limits_{\mathbf{W},b,\mathbf{\xi}}\mathop{\max}\limits_{\mathbf{\alpha},\mathbf{\mathbf{\beta}}}L(\mathbf{W},b,\mathbf{\xi},\mathbf{\alpha},\mathbf{\beta})$
其中
$\alpha_i\geq0$
$\beta_i\geq0$
再将其转化为对偶问题：
$\mathop{\max}\limits_{\mathbf{\alpha},\mathbf{\mathbf{\beta}}}\mathop{\min}\limits_{\mathbf{W},b,\mathbf{\xi}}L(\mathbf{W},b,\mathbf{\xi},\mathbf{\alpha},\mathbf{\beta})$
C是我们预先设的常量，学名叫Slackness Varible，again先看min内部， $\mathbf{W}$ 和b的偏导结果和hard-margin SVM相同，这里只需要对 $\mathbf{\xi}$ 求偏导（向量形式不好写，这里用分量）：
$\frac{\partial{L}}{\partial{\xi_i}}=C-\alpha_i-\beta_i=0$
得：
$\beta_i=C-\alpha_i$
将其带入约束条件 $\beta_i\geq0$ ，综合可得： $0\leq\alpha_i\leq C$

于是最终soft-margin的优化目标则为：
$\mathop{\max}\limits_{\forall \alpha_I, 0\leq\alpha_i\leq C,\sum_{i=0}^{m}\alpha_iy_i=0}(-\frac{1}{2}\sum_{i=0}^{m-1}\sum_{j=0}^{m-1}\alpha_i\alpha_jy_iy_j\kappa(\mathbf{x}_i,\mathbf{x}_j)+\sum_{i=0}^{m-1}\alpha_i)$
只用对每个 $\alpha_i$ 加一个上界便可。

但是其实注意到除了原始的约束条件，由于加入了 $\mathbf{\xi}$ ，KKT条件中的prime inner optimal（拉格朗日乘子项为0）也变为了如下两个(引入kernel后， $\mathbf{W}^T\mathbf{x}_i$ 都替换为 $\phi(\mathbf{x}_i)$ )：
$\alpha_i(1-\xi_i-y_i(\phi(\mathbf{x}_i)+b))=0$
$\xi_i(C-\alpha_i)=0$
当 $\alpha_i\ne0$ 时，b的求解式子就变成了：
$b=\mathbf{y_{\mathbf{s}}}-\xi_i-\sum_{i=0}^{m-1}\alpha_iy_i\kappa(\mathbf{s},\mathbf{x_i})$
然而注意到 $0\leq \alpha_i\leq C$ ，所以对于上面条件的 $\xi_i(C-\alpha_i)=0$ ,大多数情况下 $(C-\alpha_i)$ 总是大于0的。也就是说 $\xi_i$ 大概率为0，则b的计算式大部分情况下与hard-margin SVM相同。如果考虑所有 $\xi_i\ne0$ 会大大加大b的计算难度（这里是用等式得出来一个确定的b，如果考虑的话，会是一堆不等式限制b的范围，最终又会落到关于参数b对模型的优化），所以在实际中一般不考虑这种特殊情况，就算出现也可以调C来避免。

参数影响

现在来看C对SVM的影响：
C越大，代表variance越大，两种理解：一是对于初始soft-margin的优化目标，正则项的权重越大，对超平面的的约束就越大就越不允许d点在margin中出现。二是看最后对偶化简后的这个优化目标，C越大， $\alpha_i$ 都取值范围就越大，越有可能找到满足条件的 $\alpha$ 。
反之如果越小，没有合适的 $\alpha$ 就要放弃一些sample。如下图所示：
SVM学习笔记
进一步，可以根据 $\alpha$ 和C的大小关系，将样本点分成三类，
1） $\alpha==0$ ,在决策边界内的点
2） $0<\alpha<C$ 在决策边界上的点，也就是support vector
3） $\alpha==C$ ,在soft margin内的点，也就是我们允许犯错的点。

主要参考：
[1] 机器学习技法林轩田

SVM学习笔记

SVM