支持向量机(SVM)

简介

• 是一种二分类模型，基本模型的定义是在特征空间上的间隔最大的线性分类器
• ==间隔最大有利于感知==
• 学习策略： 间隔最大化，可以形式化为一个求解凸二次规划问题，也等价于正则化的合页损失函数的最小化问题

线性可分支持向量机

• 通过间隔最大化或等价地求解相应的凸二次规划问题得到的分离超平面为

• $$
  w^{}x+b^{}=0
  $$

• 以及相应的分离决策函数

• $$
  f(x)=sign(w^{}x+b^{})
  $$

硬间隔

• 在超平面$wx+b$确定的情况下，$|wx+b|$能够表示点$x$与超平面的距离，$wx+b$的符号表示为预测为哪一类

函数间隔

• 定义函数间隔为

• $$\hat \gamma_i=y_i(wx_i+b)$$

• 定义最小值
  $$\hat \gamma_i = \min_{i=1,…,n}\hat \gamma_i$$

规范化

• 只有函数间隔还不够，因为只要成比例的改变w和b，例如改成2w和2b。
  • 这样超平面并没有改变，但是函数间隔却变成了原来的两倍，如果这样额话，那么只要改的很小，那么也会达到最小化的目的
• 所以我们要加上一点约束
  • 对向量w规范化，$||w||=1$
  • 这样使得间隔是确定的(???)，此时的函数间隔变成了几何间隔

几何间隔

• 点A与超平面(w,b)的距离由线段AB给出

• 总所周知，ax+by+c=0中(a,b)为直线的发现，所以w也为超平面的发现-

• 所以点到超平面的距离为

$$\gamma_i = \frac{w}{||w||}x_i+\frac{b}{||w||}$$

• 因此导出几何间隔

  • $$\gamma_i = y_i(\frac{w}{||w||}x_i+\frac{b}{||w||})$$

  • $$\gamma = \min_{i=1,..,n}\gamma_i$$

所以，容易知道函数间隔和几何间隔之间额关系

• $$\gamma_i = \frac{\hat \gamma_i}{||w||},,,,,,,,,,,,,,,,,,,,,,,,,,,,,,::\ \gamma_i = \frac{\hat \gamma_i}{||w||}$$

• 而因为||w||=1所以两者相等，但是当w和b成比例变化的时候，函数间隔会变，但是几何间隔不会变(因为超平面并没有变化)

最大间隔分离超平面

• 几何间隔的问题

$$max_{w,b};;;;\gamma \y_i(\frac{w}{||w||}x_i+\frac{b}{||w||})≥\gamma$$

• 用函数间隔和几何间隔的关系

• $$max_{w,b};;;;\frac{\hat \gamma}{||w||} \y_i(wx_i+b)≥\hat\gamma$$

  • 此时将w和b成比例改变，可以也把$\hat\gamma$也成比例改变，例如同时乘2。所以$\hat\gamma$的值并不影响优化问题，所以固定其为1

再把最小化和最大化的问题转化，所以有
$$min_{w,b};;;;\frac{1}{2}{||w||}^2 \y_i(wx_i+b)-1≥0$$
\ \最小化后变成这种形式可能只是习惯均方误差而已，不过也有是其他形式的变形

• 到此直接用SGD能简单的解决问题

对偶问题

拉格朗日乘子法

• 拉格朗日乘子法是一种寻找多元函数在其变量收到一个或多个条件的约束时的极值的方法。
  • 这种方法可以把n个变量与k个约束条件的问题转化成n+k个变量的方程组问题
  • 这个方法中引入了一个或一组新的未知数，即拉格朗日乘数，它们是约束方程作为梯度的线性组合中各向量的系数
  • 这种方法所得到的极点会包含原问题中所有的极值点，但并不保证每个极值点都是原问题的极值点

形式

• 如

$$要求f(x,y)在g(x,y)=c时的最大值是，我们引入\lambda,转化成\L(x,y,\lambda)=f(x,y)+\lambda(g(x,y)-c)$$

• 更一般的

$$L(x_1,x_2,…,x_n,\lambda_1,…,\lambda_k)=f(x_1,…,x_n)-\sum_{i=1}^k\lambda_ig_i(x_1,…,x_n)$$

驻点一定在切点处

• f(x,y)有n个变量，g(x,y)=c是限制条件画出来的曲线，图上越小的圈的值越小
• $f(x,y)=d$是n个变量的所有集合组成使得f的值为d画出的曲线
• 易证在切线处有驻点
• ==切线处，梯度方向相同，用向量的形式就是在且向上平行==
  • 拉格朗日乘子法的必要条件是$\nabla f=\lambda\nabla g$，就是两个梯度平行

引入变量表示梯度向量

• 引入变量$\lambda$

$$\nabla f(x,y)=-\lambda\nabla(g(x,y)-c)\ 即\nabla [f(x,y)+\lambda(g(x,y)-c)]=0$$
所以，一旦求出$\lambda$的值，将其套入下列公式，容易求出在无约束条件下的极值和对应的极值点
$$F(x,y,\lambda)=f(x,y)+\lambda(g(x,y)-c)$$
$F(x,y,\lambda)达到极值的时候与f(x,y)相等，因为达到极值时，g(x,y)-c总\为0(在切点处)，这也是为什么要减c的原因$

证明

$$设f(x,y)，和g(x,y)=c\ 两个函数在A处的全微分为\ df=\frac{\vartheta f}{\vartheta x}dx+\frac{\vartheta f}{\vartheta y}dy=0\ dg=\frac{\vartheta g}{\vartheta x}dx+\frac{\vartheta g}{\vartheta y}dy=0\ 由于前提就是要平行，所以有\ \frac{\frac{\vartheta f}{\vartheta x}}{\frac{\vartheta g}{\vartheta x}}=\frac{\frac{\vartheta f}{\vartheta y}}{\frac{\vartheta g}{\vartheta y}}=-\lambda\ 即\ \frac{\vartheta f}{\vartheta x}+\lambda\frac{\vartheta g}{\vartheta x}=0\ \frac{\vartheta f}{\vartheta y}+\lambda\frac{\vartheta g}{\vartheta y}=0\ 将上两式分别乘dx,dy再相加并积分，就得到新函数\ L(x,y,\lambda)=f(x,y)+\lambda g(x,y)\ 其实就是一个变量用对于隐函数存在定理再带入即可$$

对于不等式约束时

• ==暂时把-c和g(x,y)划分到一起==

• 形式为
  $$min;;;f(x)\ g(x)≤0$$

KKT条件

• 现在g(x,y)有边界解和内部解

  • 如果解本来就在g的内部，那么g的调价就没什么用了，我们的$\lambda=0$即可
  • 如果解不在外部，那么我们就要在边界上找点了，那么就和等式条件一样了有$g(x)=0$
  • 所以不管是什么上面的点都有$\lambda g(x)=0$，称为互补松弛性

• $\nabla f=-\lambda \nabla g$

  • 我们知道等式条件是要梯度平行的，但是这里我们不仅需要平行还需要相反，所以有$\lambda>0$。就是说梯度f应该指向f最陡峭的地方，即指向g的内部，但是梯度g却是指向g的外部的。因此有$\lambda≥0$。
  • 原因：==$\nabla g$始终指向约束控制的可行区域==，所以如果解在区域外的话那需要调整梯度的方向才不会造成影响，调整的方法就是$-\lambda$
  • 对偶可行性。按照上面的图就是，g(x)标的是≤，所以方向应该向里面指，但是梯度是从小的地方向大的地方指的，所以对于≤来说，切点的梯度方向是相反的。==特殊的，如果要求的是max f(x)，g(x)≥0，则λ≤0==

• 所以上面的那个形式要对应的KKT条件为
  $$g(x)≤0\ \lambda ≥0\ \lambda g(x)=0\ \nabla f+\lambda \nabla g = 0$$
  所对应的广义拉格朗日函数还是
  $$L(x,\lambda)=f(x)+\lambda g(x)$$

引入拉格朗日乘子

$$L(w,b,a)=\frac{1}{2}||w||^2+\sum_{i=1}^Na_i(1-y_i(wx_i+b))$$

• 问题会变成

$$
\min {w,b}\max _{a>=0}L(w,b,a)=\frac{1}{2}||w||^2+\sum{i=1}^Na_i(1-y_i(wx_i+b))
$$

• 为什么会有max(a)呢

  • max的存在代替了原来的约束条件
    • 假设，各个参数范围是符合要求的话，那么会正常的返回值，但是假如有不符合条件的，那么会通过对a的调整取到+∞
    • 所以这个max的作用就是来判断对错的

• ==因为到了这一步之后还是无法求解，(因为我们对无穷大求最小并没有解决问题)所以我们引入对偶问题==

• 对偶后的问题变成了一个极大极小问题
  $$
  \max a \min _{w,b}L(w,b,a)=\frac{1}{2}||w||^2+\sum{i=1}^Na_i(1-y_i(wx_i+b))
  $$

  • 先对w,b求导得到极小，再对a得到极大
  • 其实就是把最大和最小换了一个顺序

分别对w，b偏导为0得
$$w=\sum a_iy_ix_i\ 0=\sum a_iy_i$$
带入原问题
$$\min_a \frac{1}{2}\sum\sum a_ia_jy_iy_j(x_i\cdot x_j)-\sum a_i\ \sum a_iy_i=0\ a_i≥0$$

求解

• 得到$a^*$

• 根据$a^$算$w^,b^*$

$$
w^=\sum a_i^*y_ix_i\
b^=y-\sum a_i^*y_i(x_i\cdot x_j)
$$

• $w^,b^$只依赖于数据中对应的$a_i^>0$的样本点，而其他样本点对这两个值没有影响。我们将数据集中对应的$a_i^>0$的点称为支持向量

  • 这个用坐标下降算法来优化

• 搞了半天最后的答案可能只和两个点有关系QAQ，不过毕竟这个还是只能解决线性可分的问题的，解决的都是硬间隔

软间隔

• 毕竟很多问题还是线性不可分的，所以上述的很多约束并不能成立

所以，我们考虑引入松弛变量$\xi_i\geq0$

• 约束条件变为$y_i(w\cdot x_i+b)\geq1-\xi_i$

对于每一个松弛变量我们支付一个$\xi_i$的代价

• $\frac{1}{2}||w||^2+C\sum \xi_i$
  • 这个的C是惩罚参数

原问题就变成
$$\min_{w,b,\xi}\frac{1}{2}||w||^2+C\sum \xi_i\ y_i(w\cdot x_i+b)\geq1-\xi_i\ \xi_i\geq0$$
然后用类似硬间隔的解决方法就行了

• 通过拉格朗日乘子法

$$=\min_{w,b,\xi}\frac{1}{2}||w||^2+C\sum \xi_i+\sum_{i=1}^ma_i(1-\xi_i-y_i(w^Tx_i+b))\sum_{i=1}^m \mu_i\xi_i$$

• 偏导

$$w=\sum a_iy_ix_i\ \sum a_iy_i=0\ C=a_i+\mu_i$$

• 问题对偶为

$$\max_a \sum a_i\frac{1}{2}\sum\sum a_ia_jy_iy_jx^T_ix_j\ \sum a_iy_i=0\ 0\leq a_i\leq C$$

软间隔的另一种解释：合页损失函数(hinge-loss)

• 另一种解释，最小化下面的函数
  $$min \sum [1-y_i(w\cdot x_i+b)]_++\lambda||w||^2$$
  • 下标“+”是取正值函数即max(x,0)，前面那一项是经验损失
  • 优化这个问题和优化软间隔问题等价(经验损失那一项就等价于软间隔$\xi_i>=0$)
  • 这个东西直接SGD就行了

核技巧

• 非线性的东西往往不好求解，如上图左边的，直接用hinge-loss可能不会得到好的结果，而我们现在的策略就是把==把非线性问题转化为线性的问题==

• 设原空间$x=(x^{(1)},x^{(2)})^T$,新空间$z=(z^{(1)},z^{(2)})$

  • 从原空间到新空间的仿射变换为$z=\phi(x)=((x^{(1)})^2,(x^{(2)})^2)$
  • 然后就能把左边的图变成右边的图

• 这种方法被称为核化，用这种方法把非线性分类转化为线性的分类

核函数

• 设$X$是输入空间，又设$H$为特征空间(希尔伯特空间)
  • 如存在$\phi(x)$为输入空间到特征空间的映射使得$K(x,y)=\phi(x)\cdot\phi(y)$（这个是两个向量的内积）
  • 经常把输入空间映射到高维空间，这样可能能更高的划分

核技巧在SVM中的应用

• 我们在对偶问题中涉及输入实例之间的内积，我们可以把内积用核函数代替

$$W(a)=\frac{1}{2}\sum\sum a_ia_jy_iy_jK(x_i,x_j)-\sum a_i$$

• 同样其他的有内积的地方也能用核函数来替换

$$f(x)=\sum a_iy_iK(x_i,x)+b\ a_i>0—->b=y_i-w^Tx_i$$

正定核

• 已知映射函数$\phi$，可以通过内积来求核函数，但是我们能不构造$\phi$而直接判断一个给定的函数是不是核函数吗？

• 此地涉及大量的数学证明，不做讲述

常用的核函数

多项式核函数

$$K(x,z) = (x\cdot z+1)^p$$

• 对应的SVM是一个p次多项式分类器

高斯核函数

$$K(x,z)=exp(-\frac{||x-z||^2}{2\delta^2})$$

• 对应的SVM是高斯径向基函数分类器

字符串核函数

• 这个是基于离散集合的核函数

• 自行了解

SMO(序列最小优化方法)

• SMO算法要解决如下的凸二次规划的对偶问题
  $$\min_a \frac{1}{2}\sum\sum a_ia_jy_iy_jK(x_i,x_j)-\sum a_i\ \sum a_iy_i=0\ 0\leq a_i\leq C$$
• SMO算法是一个启发式算法
  • 思路：
    • 如果所有变量都满足此优化问题的KKT条件，那么答案就找到了
    • 否则，选择两个变量，固定其他变量，针对两个变量构建一个二次规划问题，这二次规划关于这两个变量的解应该更接近与原始问题的解，因而会使原始二次规划问题的函数目标值更小
      • 重要的是，子问题可以通过解析方法求解
      • 子问题有两个变量，一个是违反KKT条件最严重的那个，另一个由约束条件自动确定
      • 如此，SMO算法不断分解为子问题并对子问题求解，进而达到求解原问题的目的
    • 注意子问题的两个变量只有一个是自由变量，如果a1,a2为两个变量，其他的固定，由约束条件可知，假如a2为自由变量，那么a1可以有其他变量求出来
    • SMO算法包括两个部分：求解两个变量二次规划的解析方法，选择变量的启发式方法

两个变量的二次规划的求解方法

我们选择变量a1,a2，其他变量固定
$$\min_{a_1,a_2};;;W(a_1,a_2)=\frac{1}{2}K_{11}a_1^2+\frac{1} {2}K_{22}a_2^2+y_1y_2K_{12}a_1a_2-\(a_1+a_2)+y_1a_1\sum_{i=3}^Ny_ia_iK_{i1}+y_2a_2\sum_{i=3}^Ny_ia_iK_{i2}\ a_1y_1+a_2y_2=-\sum_{i=3}^Ny_ia_i=\zeta\ 0\leq a_i \leq C$$

• $\zeta$是常数，显然上面列举的是不含a1,a2的常数项

然后，只是两个变量的优化问题我们就可以在二维的平面上来操作了

• 因为y是1或-1，所以，两个a在平行于对角线的斜线上

• 根据上面的条件有

  • L,H为a范围的上下边界

  • $$L=max(0,a_2^{old}-a_1^{old}),H=min(C,C+a_2^{old}a_1^{old})\ L=max(0,a_2^{old}+a_1^{old}-C),H=min(C,a_2^{old}+a_1^{old})$$

我们首先求沿着约束方向未经剪辑即未经过不等式约束时$a_2$的最优解$a^{new,unc}$，然后再求出$a_2^{new}$

设
$$g(x)=\sum_{i=1}^Na_iy_iK(x_i,x)+b\ E_i=g(x_i)-y_i=(\sum a_jy_jK(x_j,x_i)+b)-y_i$$

• g(x)就是当前学习出的值，Ei就是误差值

然后有
$$a_2^{new,unc}=a_2^{old}+\frac{y_2(E_1-E_2)}{\eta}\ \eta=K_{11}+K_{22}-2K_{12}=||\phi(x_1)-\phi(x_2)||\ a_2^{new}= \begin{cases} H & a_2^{new,unc}>H\ a_2^{new,unc} & L\le a_2^{new,unc}\le H\ L & a_2^{new,unc}<L \end{cases}$$

证明

$$v_i=\sum_{j=3}^N a_jy_jK(x_i,x_j)=g(x_i)-\sum_{j=1}^2a_jy_jK(x_i,x_j)-b\ 所以W(a_1,a_2)=\frac{1}{2}K_{11}a_1^2+\frac{1}{2}K_{22}a_2^2+y_1,y_2,K_{12}a_1a_2-(a_1+a_2)+y_1v_1a_1+y_2v_2a_2$$

由于$a_1y_1=\xi-a_2y_2,y_i^2=1$
$$所以a_1(\xi-y_2a_2)y_1$$
代入
$$W(a_2)=\frac{1}{2}(\xi-a_2y_2)^2+\frac{1}{2}K_{22}a_2^2+y_2K_{12}(\xi-a_2y_2)a_2-(\xi-a_2y_2)y_1\ -a_2+v_1(\xi-a_2y_2)+y_2x_2a_2$$
求导
$$\frac{\vartheta W}{\vartheta a_2}=K_{11}a_2+K_{22}a_2-2K_{12}a_2-K_{11}\xi y_2+K_{12}\xi y_2+y_1y_2-1-v_1y_2+y_2v_2$$
令其为零
$$(K_{11}+K_{22}-2K_{12})a_2=…=y_2(y_2-y_1+\xi K_{11}-\xi K_{12}+(g(x_1)-\sum_{j=1}^2y_ja_jK_{1j}-b))\-(g(x_2)-\sum_{j=1}^2y_ja_jK_{2j}-b)$$
因为$\xi=a_1^{old}y_1+a_2^{old}y_2$
$$(K_{11}+K_{22}-2K_{12})a_2^{new,unc}=…=(K_{11}+K_{22}-2K_{12})a_2^{old}+y_2(E_1-E_2)$$
将$\eta=K_{11}+K_{22}-K_{12}$
$$a_2^{new,unc}=a_2^{old}+\frac{y_2(E_1-E_2)}{\eta}$$

再由约束得到$a_2^{new}$，在得到$a_1^{new}$

变量的选择方法

• 如果只按照上面的方法的话，在寻找变量a会用掉很多的时间，所以我们考虑选择的优化

第一个变量的选择

• SMO称选择第一个变量的过程为外层循环

  • 外层循环在训练中选取违反KKT条件最严重的样本点，并将其作为第一个变量

  • $$\begin{cases} a_i=0 \iff y_Ig(x_i)\geq1\ 0<a_i<C\iff y_ig(x_i)=1\ a_i=C\iff y_ig(x_i)\leq1 \end{cases}\ 其中g(x_i)如上$$

  • 该校验是在误差$\varepsilon$范围中进行的

    • 在校验的过程中，外层循环首先遍历所有满足条件$0<a_i<C$的样本点，即在间隔边界的支持向量点，校验他们是否满足KKT条件，如果这些样本点都满足KKT条件，那么遍历整个训练集，校验他们是否满足KKT条件

第二个变量

• SMO称选择第二个变量的过程为内层循环
  • 假设已经找到了变量$a _ 1$，我们希望$a_2$选择的是能是$a_2$变化足够大的
  • 所以$a_2^{new}$是依赖于$|E_1-E_2|$
    • 为了加快计算，我们最简单的选择方法是使得$|E_1-E_2|$最大
    • 因为$a_1$确定，$E_1$也确定，那么直接把所有的$E_i$存在一个列表(有序列表)中节省时间
• 在特殊的情况下，如果内层循环通过以上方法不能使目标函数有足够的下降，那么用以下启发式规则继续选择$a_2$
  • 遍历间隔边界上的支持向量点，一次将其对应的变量作为$a_2$试用，直到目标函数有足够的下降
  • 若找不到合适的$a_2$，那么遍历整个数据集
  • 若上两个都不行，则放弃这个$a_1$，用其他的$a_1$

计算阈值b和差值$E_i$

$$b_1^{new}=y_1-\sum_{i=3}^Na_iy_iK_{i1}-a_1^{new}y_1K_{11}-a_2^{new}y_2K_{21}\ E_1 = \sum_{i=3}^{N}a_iy_iK_{i1}+a_1^{old}y_1K_{11}+a_2^{old}y_2K_{21}+b^{old}-y_1$$

将之前的式子整理
$$b_1^{new}=-E_1-y_1K_{11}(a_1^{new}-a_1^{old})-y_2K_{21}(a_2^{new}-a_2^{old})+b^{old}\ b_2^{new}=-E_2-y_1K_{12}(a_1^{new}-a_1^{old})-y_2K_{21}(a_2^{new}-a_2^{old})+b^{old}$$

• 如果$a_1^{new},a_2^{new}$同时满足(0,C)的条件，那么$b^{new}=b_1^{new}=b_2^{new}$
• 如果两个值就在0和C上，那么两个b之间的数都是符合KKT条件的阈值，这是就取中点

$$E_i^{new}=\sum_Sy_ja_jK(x_i,x_j)+b^{new}-y_i$$

S是所有支持向量$x_j$的集合（不过打的时候直接用整个数据集）