SVM 支持向量机(Support Vector Machine)(Part 2)

作者: pdnbplus | 发布时间: 2024/07/13 | 阅读量: 130

# SVM 支持向量机(Support Vector Machine)(Part 2) -- 潘登同学的Machine Learning笔记

简单回顾硬间隔SVM

算法流程

  • 1.原始目标： 求得一组 w 和 b 使得分隔 margin 最大
  • 2.转换目标： 通过拉格朗日函数构造目标函数，问题由求得 n 个 w 和 1 个 b 转换为求得 m 个α
    min⁡α≥012∑i=1,j=1mαiyixiTαjyjxj+∑i=1mαis.t∑i=1mαiyi=0(αi≥0)\min_{\alpha\geq0} \frac{1}{2}\sum_{i=1,j=1}^m\alpha_iy_ix_i^T\alpha_jy_jx_j + \sum_{i=1}^m\alpha_i\\ s.t \qquad \sum_{i=1}^{m}\alpha_iy_i = 0 \qquad(\alpha_i\geq0)
  • 3.利用 smo 算法求得 m 个α∗\alpha^*
  • 4.利用求得的 m 个α∗\alpha^*求得 w∗w^*和 b∗b^*
    w∗=∑i=1mαi∗yixibsupport=ysupport−(w∗)Txsupportb∗=1s∑support=1sbsupportw^* = \sum_{i=1}^m \alpha_i^*y_ix_i\\ b_{support} = y_{support} - (w^{*})^Tx_{support}\\ b^* = \frac{1}{s}\sum_{support=1}^{s}b_{support}\\

硬间隔面临的问题

有些时候，线性不可分是由噪声点决定的，可能这些数据本身就是分开的， 但是因为噪声， 某一类的个别数据混杂到了另一类中;

这里为什么要说个别数据呢？ 因为后面会说因为数据的特点线性不可分的情况;

软间隔SVM

回想硬间隔的条件

    1. 正负例完美分开（体现在约束条件>=1 上）
    1. 找到能使间隔最大的点（有约束条件的函数优化问题）

如果数据集线性不可分，意味着找不到一个合格的超平面 体现在优化问题上，任何的 w 和 b 都无法满足优化条件

解决方案

(这个解决方案与运筹学的那一套目标规划的套路差不多)

对于之前的问题，硬间隔不可分，体现在满足不了约束条件上，于是提出松弛变量ξi≥0\xi_i≥0（每 个数据点自己有一个ξi\xi_i）

我们将约束条件放松为：
yi(wTxi+b)≥1−ξiy_i(w^Tx_i+b) \geq 1 - \xi_i

注意:

  • 这样就肯定有好多的 w 和 b 满足条件了 但是这相当于没有约束条件了，只要ξi\xi_i 无穷大， 那么所有 w 和 b 都满足条件
  • ξi\xi_i代表异常点嵌入间隔面的深度，我们要在能选出符合约束条件的最好的 w 和 b 的同时，让嵌入间隔面的总深度越少越好

目标函数的优化

(把上面这个观点表示在目标函数中)

  • 构建目标函数
    min⁡w12∥w∥22+C∑i=1mξis.tdi=yi(wTxi+b)≥1−ξiξi≥0\min_{w} \frac{1}{2}\lVert w \rVert_2^2 + C\sum_{i=1}^{m}\xi_i\\ s.t \qquad d_i = y_i(w^Tx_i+b) \geq 1 - \xi_i \\ \xi_i \geq 0

  • 构建拉格朗日函数
    L(w,b,ξ,α,μ)=12∥w∥22+C∑i=1mξi−∑i=1mαi[yi(wTxi+b)−1+ξi]−∑i=1mμiξi(αi≥0,μi≥0)L(w,b,\xi,\alpha,\mu)=\frac{1}{2}\lVert w \rVert_2^2 + C\sum_{i=1}^{m}\xi_i - \sum_{i=1}^m\alpha_i[y_i(w^Tx_i+b) - 1 + \xi_i] - \sum_{i=1}^m\mu_i\xi_i\\ (\alpha_i\geq0,\mu_i\geq0)

  • 优化原始问题
    min⁡w,b,ξmax⁡αi≥0,μi≥0L(w,b,ξ,α,μ)\min_{w,b,\xi}\max_{\alpha_i\geq0,\mu_i\geq0}L(w,b,\xi,\alpha,\mu)

  • 等价于优化原始问题的对偶问题
    max⁡αi≥0,μi≥0min⁡w,b,ξL(w,b,ξ,α,μ)\max_{\alpha_i\geq0,\mu_i\geq0}\min_{w,b,\xi}L(w,b,\xi,\alpha,\mu)

  • 第一步求极小，对w,b,ξw,b,\xi分别求偏导
    ∂L∂w=0⇒w=∑i=1mαiyixi∂L∂b=0⇒∑i=1mαiyi=0∂L∂ξ=0⇒C−α−μ=0\frac{\partial{L}}{\partial{w}} = 0 \Rightarrow w = \sum_{i=1}^m\alpha_iy_ix_i \\ \frac{\partial{L}}{\partial{b}} = 0 \Rightarrow \sum_{i=1}^m\alpha_iy_i = 0\\ \frac{\partial{L}}{\partial{\xi}} = 0 \Rightarrow C-\alpha-\mu=0\\

  • 带回拉格朗日函数
    L(w,b,ξ,α,μ)=12∥w∥22+C∑i=1mξi−∑i=1mαi[yi(wTxi+b)−1+ξi]−∑i=1mμiξi=12∥w∥22−∑i=1mαi[yi(wTxi+b)−1+ξi]+∑i=1mαiξi=12∥w∥22−∑i=1mαi[yi(wTxi+b)−1](这不就变回硬间隔了嘛)=∑i=1mαi−12∑i=1,j=1mαiyixiTαjyjxj\begin{aligned} L(w,b,\xi,\alpha,\mu)&=\frac{1}{2}\lVert w \rVert_2^2 + C\sum_{i=1}^{m}\xi_i - \sum_{i=1}^m\alpha_i[y_i(w^Tx_i+b) - 1 + \xi_i] - \sum_{i=1}^m\mu_i\xi_i\\ &=\frac{1}{2}\lVert w \rVert_2^2 - \sum_{i=1}^m\alpha_i[y_i(w^Tx_i+b) - 1 + \xi_i] + \sum_{i=1}^m\alpha_i\xi_i\\ &=\frac{1}{2}\lVert w \rVert_2^2 - \sum_{i=1}^m\alpha_i[y_i(w^Tx_i+b) - 1](这不就变回硬间隔了嘛)\\ &= \sum_{i=1}^m\alpha_i-\frac{1}{2}\sum_{i=1,j=1}^m\alpha_iy_ix_i^T\alpha_jy_jx_j \\ \end{aligned}

  • 第二步求极大
    max⁡α∑i=1mαi−12∑i=1,j=1mαiyixiTαjyjxjs.t.∑i=1mαiyi=0C−α−μ=0(∗)αi≥0(i=1,2,…,m)μi≥0(i=1,2,…,m)\max_{\alpha}\sum_{i=1}^m\alpha_i-\frac{1}{2}\sum_{i=1,j=1}^m\alpha_iy_ix_i^T\alpha_jy_jx_j \\ s.t. \qquad \sum_{i=1}^{m}\alpha_iy_i = 0\\ C-\alpha-\mu=0 (*)\\ \alpha_i\geq0(i=1,2,\ldots,m)\\ \mu_i\geq0(i=1,2,\ldots,m)\\

注意:(∗)(*)中的α,μ\alpha,\mu都是向量而C是常数, 所以其实是C boardcast成向量再减去α,μ\alpha,\mu其实可以写成m条约束:
C−αi−μi=0(i=1,2,…,m)C-\alpha_i-\mu_i=0 (i=1,2,\ldots,m)

  • 将后3条约束改写,目标改写
    min⁡α12∑i=1,j=1mαiyixiTαjyjxj−∑i=1mαis.t.∑i=1mαiyi=00≤αi≤C(i=1,2,…,m)\min_{\alpha}\frac{1}{2}\sum_{i=1,j=1}^m\alpha_iy_ix_i^T\alpha_jy_jx_j - \sum_{i=1}^m\alpha_i\\ s.t. \qquad \sum_{i=1}^{m}\alpha_iy_i = 0\\ 0\leq\alpha_i\leq C(i=1,2,\ldots,m)\\

  • 而上面的问题还是一个非线性规划, 我们用SMO算法求解

求出了αi\alpha_i便可以得到w,b(与硬间隔一样)
w∗=∑i=1mαi∗yixibsupport=ysupport−(w∗)Txsupportb∗=1s∑support=1sbsupportw^* = \sum_{i=1}^m \alpha_i^*y_ix_i\\ b_{support} = y_{support} - (w^{*})^Tx_{support}\\ b^* = \frac{1}{s}\sum_{support=1}^{s}b_{support}\\

分析软间隔问题的支持向量

简单回顾硬间隔的支持向量

  • αi≠0\alpha_i\neq0的那个样本i就是支持向量

对于软间隔

  • αi=0\alpha_i=0为正确分类的点

解释：αi=0\alpha_i=0, 根据C−α−μ=0C-\alpha-\mu=0, 那么μi=C\mu_i =C, 根据拉格朗日函数的特点, 那么ξi\xi_i就为0, (因为这样才不会影响拉格朗日函数与原函数一样的特性)；

  • 0<αi<C0<\alpha_i<C该点为软边界上的点(支撑向量)

解释：0<αi<C0<\alpha_i<C, 根据C−α−μ=0C-\alpha-\mu=0, 那么μi≠0\mu_i\neq0, 根据拉格朗日函数的特点, 那么ξi\xi_i就为0, 且yi(wTxi+b)−1−ξi=0y_i(w^Tx_i+b) - 1-\xi_i=0，那这个不就是支撑向量的定义嘛(函数距离为1)；

  • αi=C\alpha_i=C该点嵌入了软边界内

解释：αi=C\alpha_i=C, 根据C−α−μ=0C-\alpha-\mu=0, 那么μi=0\mu_i=0, 根据拉格朗日函数的特点, 那么ξi\xi_i就一定不为0, 且yi(wTxi+b)−1−ξi=0y_i(w^Tx_i+b) - 1-\xi_i=0，当ξi\xi_i为零时函数距离为1, 现在ξi\xi_i不为0了, 就说明在边界内了；

  • 此时如果ξ<1\xi<1 ，该点被正确分类
  • 此时如果ξ=1\xi=1 ，该点刚好落在超平面上
  • 此时如果ξ>1\xi>1 ，该点该点被错误分类

总结软间隔最大化算法

  • 1.设定惩罚系数 C，构造优化问题
    min⁡α12∑i=1,j=1mαiyixiTαjyjxj−∑i=1mαis.t.∑i=1mαiyi=00≤αi≤C(i=1,2,…,m)\min_{\alpha}\frac{1}{2}\sum_{i=1,j=1}^m\alpha_iy_ix_i^T\alpha_jy_jx_j - \sum_{i=1}^m\alpha_i\\ s.t. \qquad \sum_{i=1}^{m}\alpha_iy_i = 0\\ 0\leq\alpha_i\leq C(i=1,2,\ldots,m)\\
  • 2.用 SMO 算法求出m 个α∗\alpha^*
  • 3.利用求得的 m 个α∗\alpha^*求得 w∗w^*和 b∗b^*
    w∗=∑i=1mαi∗yixibsupport=ysupport−(w∗)Txsupportb∗=1s∑support=1sbsupportw^* = \sum_{i=1}^m \alpha_i^*y_ix_i\\ b_{support} = y_{support} - (w^{*})^Tx_{support}\\ b^* = \frac{1}{s}\sum_{support=1}^{s}b_{support}\\

非线性支持向量机

深刻理解软间隔不是非线性支持向量机

如前所述, 软间隔只是用于解决线性不可分的一个补丁, 随着两个类别之间的数据互相嵌入的越来越多, 或者数据的构造本来就不是线性可分的, 软间隔也不好使;

观察下图:

非线性SVM

这样的才叫分线性的数据, 显然非线性数据是线性不可分的, 叫软间隔来也不好使;

解决非线性的办法

前面其实说过Polynomial多项式升维

可以将 2 元特征(x1,x2)(x_1,x_2)映射为 5 元特征(x1,x2,x1x2,x12,x22)(x_1,x_2,x_1x_2,x_1^2,x_2^2) 这样在五元空间中有些二元空间里线性不可分的问题就变得线性可分了

SVM 的升维

  • 对于线性 SVM 来说，最优化问题为：
    min⁡α12∑i=1,j=1mαiyixiTαjyjxj−∑i=1mαis.t.∑i=1mαiyi=00≤αi≤C(i=1,2,…,m)\min_{\alpha}\frac{1}{2}\sum_{i=1,j=1}^m\alpha_iy_ix_i^T\alpha_jy_jx_j - \sum_{i=1}^m\alpha_i\\ s.t. \qquad \sum_{i=1}^{m}\alpha_iy_i = 0\\ 0\leq\alpha_i\leq C(i=1,2,\ldots,m)\\

  • 如果使用ϕ(x)\phi(x)对训练集升维，最优化问题就变成了：
    min⁡α12∑i=1,j=1mαiyiϕ(xi)Tαjyjϕ(xj)−∑i=1mαis.t.∑i=1mαiyi=00≤αi≤C(i=1,2,…,m)\min_{\alpha}\frac{1}{2}\sum_{i=1,j=1}^m\alpha_iy_i\phi(x_i)^T\alpha_jy_j\phi(x_j) - \sum_{i=1}^m\alpha_i\\ s.t. \qquad \sum_{i=1}^{m}\alpha_iy_i = 0\\ 0\leq\alpha_i\leq C(i=1,2,\ldots,m)\\

升维后的结果就像上图一样了

维度爆炸

看似这种升维方式已经完美解决了线性不可分问题，但是带来了一个新问题:假设就使用多项式回归的方式进行升维:2维数据→5维；3维数据→9维数据；那如果是10维数据→……

而且就算升到那么高的维度, 目标函数中的ϕ(xi)Tϕ(xj)\phi(x_i)^T\phi(x_j)还要做向量内积, 计算量就超级大, 就引起了维度灾难了;

引入核函数

但是有一个重要的观察, 就算我们进行升维, 最后要算的还是ϕ(xi)Tϕ(xj)\phi(x_i)^T\phi(x_j), 所以数学家们找到了一些叫核函数的东西， 能跳过ϕ(x)\phi(x)这一步, 直接得出升维后的内积;

  • 核函数
    K:X×X↦R∀x,z∈X,则称k(x,z)为核函数\mathcal{K}: \mathbb{X} \times \mathbb{X} \mapsto \mathbb{R}\\ \forall x,z \in \mathbb{X}, 则称k(x,z)为核函数

  • 正定核
    K:X×X↦R∀x,z∈X,有k(x,z)如果∃ϕ:X↦R,ϕ∈Hs.t.k(x,z)=<ϕ(x),ϕ(z)>\mathcal{K}: \mathbb{X} \times \mathbb{X} \mapsto \mathbb{R}\\ \forall x,z \in \mathbb{X}, 有k(x,z)\\ 如果\exist \phi: \mathbb{X} \mapsto \mathbb{R},\phi\in\mathcal{H}\\ s.t. k(x,z) = <\phi(x), \phi(z)>\\

则称k(x,z)为正定核函数， 其中H\mathcal{H}为希尔伯特空间(就是那个说汽车旅馆的那个数学家， 集合论就是他创建的)

  • 希尔伯特空间

完备的，可能是无限维的，被赋予内积的线性空间

完备的: 对极限运算封闭, 对{kn}有lim⁡x→∞kn=K∈H\{k_n\} 有 \lim_{x \to \infty}k_n = K \in \mathcal{H}

无限维的: 就是字面意思， 可以指函数的次数的无穷次方

被赋予内积: 满足内积空间的三个性质

  • 对称性--<a,b>=<b,a><a,b>=<b,a>
  • 正定性--<a,a>≥0<a,a>\geq0
  • 线性--<r1a1+r2a2,b>=r1<a1,b>+r2<a2,b><r_1a_1+r_2a_2, b> = r_1<a_1, b> + r_2<a_2, b>

线性空间： 对加法数乘封闭--经典8条(在这里还是推荐严质彬老师的矩阵分析)

我们SVM用的核函数都是正定核, 如果不加说明, 也默认核函数就是指正定核;

  • 正定核的性质

    • 对称性
      k(x,z)=k(z,x)k(x,z) = k(z,x)
    • 正定性

    (任取n个元素x1,x2,…,xnx_1, x_2, \ldots, x_n)对应的Gram martix(格莱姆矩阵)是半正定的, 其中矩阵中的元素aij=k(xi,xj)a_{ij} = k(x_i, x_j)

  • 想说明一个矩阵是半正定的

    • 特征值大于等于0
    • ∀α∈Rn,αTAα≥0\forall \alpha \in \mathbb{R}^n, \alpha^T A \alpha \geq 0

常用核函数

  • 线性核函数
    K(x,z)=x⋅zK(x,z) = x\cdot z
  • 多项式核函数
    K(x,z)=(γx⋅z+r)dK(x,z) = (\gamma x\cdot z + r)^d
  • 高斯核函数(常用)
    K(x,z)=eγ∣∣x−z∣∣2K(x,z) = e^{\gamma ||x-z||^2}
  • sigmoid核函数
    K(x,z)=tanh⁡(γx⋅z+r)K(x,z) = \tanh (\gamma x\cdot z + r)

举个栗子

著名的异或问题:

  • I类： (0,0) (1,1)
  • II类：(0,1) (1,0)

异或画图

在这个二分类问题中, 找不到一个超平面使得能把两类分开

  • 采用高斯核
    K(x,z)=eγ∣∣x−z∣∣2K(x,z) = e^{\gamma ||x-z||^2}

K((0,0),(1,1))=0K((0,1),(1,0))=1K((0,0), (1,1)) = 0\\ K((0,1), (1,0)) = 1

这样两个线性不可分的点就可以通过高斯核函数变成线性可分了;

  • 自己手动升维

设z=(x−y)2z = (x-y)^2则能用一个平面将他们分开;

升为后异或问题

非线性总结

  • 1.选择某个核函数及其对应的超参数
  • 2.选择惩罚系数 C
  • 3.构造最优化问题
    min⁡α12∑i=1,j=1mαiαjyiyjK(xi,xj)−∑i=1mαis.t.∑i=1mαiyi=00≤αi≤C(i=1,2,…,m)\min_{\alpha}\frac{1}{2}\sum_{i=1,j=1}^m\alpha_i\alpha_jy_iy_jK(x_i, x_j) - \sum_{i=1}^m\alpha_i\\ s.t. \qquad \sum_{i=1}^{m}\alpha_iy_i = 0\\ 0\leq\alpha_i\leq C(i=1,2,\ldots,m)\\
  • 4.利用 SMO 算法求解出一组α\alpha
  • 5.利用求得的 m 个α∗\alpha^*求得 w∗w^*和 b∗b^*

SVM算法的历史渊源

对于SVM来说， 判别函数y=(wTx+b)y=(w^Tx+b), 由于w=∑i=1mαiyixiw=\sum_{i=1}^m \alpha_iy_ix_i
∴y=(∑i=1mαiyi(xix)+b)\therefore y=(\sum_{i=1}^m \alpha_iy_i(x_ix)+b)
由于αiyi\alpha_iy_i是确定的；所以得到一个结论：

每次计算判别函数时，需要求得判别点与所有训练集的内积；

所以SVM不怕样本维度多， 只怕样本数量大(预测时)

至于为什么要将拉格朗日函数的求解转化为求解对偶函数:
min⁡w,bmax⁡α⇒max⁡αmin⁡w,b\min_{w,b}\max_{\alpha} \Rightarrow \max_{\alpha}\min_{w,b}

是因为之前数据量不大， 原本求解w个参数的就转换成了求α\alpha个参数了(α<w,也就是m<n\alpha<w, 也就是m<n);

但是现在数据量大了(n<mn<m), SVM已经不擅长了…\ldots

SMO算法

SMO算法思想

将原始求解N个参数二次规划问题分解成很多个子二次规划问题分别求解。

每个子问题只需求解2个参数, 方法类似于坐标上升(固定其他变量， 研究某个变量)， 每次启发式选择两个变量进行优化， 不断循环， 直到达到函数最优值；

  • 问题1： 为什么要视为调整2个参数, 而不是像坐标上升一样只调一个

由约束条件:
∑i=1mαiyi=0\sum_{i=1}^{m}\alpha_iy_i = 0

yiy_i已知, 若把m−1个αm-1个\alpha固定, 那αk\alpha_k就固定， 就无法优化；

所以只固定m−2个αm-2个\alpha， 将α1,α2\alpha_1,\alpha_2设置为变量， 固定其他参数；

SMO求解过程

  • 简化目标函数， 将不含α1,α2\alpha_1,\alpha_2的项设置为常数ConstantConstant
    min⁡α12∑i=1,j=1mαiαjyiyjK(xi,xj)−∑i=1mαi⇒min⁡α12K11α12+12K22α22+y1y2K12α1α2−(α1+α2)+y1α1∑j=3mαjyjK1j+y2α2∑j=3mαjyjK2j+Constant\min_{\alpha}\frac{1}{2}\sum_{i=1,j=1}^m\alpha_i\alpha_jy_iy_jK(x_i, x_j) - \sum_{i=1}^m\alpha_i\\ \Rightarrow \min_{\alpha}\frac{1}{2} K_{11}\alpha_1^2 + \frac{1}{2} K_{22}\alpha_2^2 + y_1y_2K_{12}\alpha_1\alpha_2 - (\alpha_1+\alpha_2) + y_1\alpha_1\sum_{j=3}^m\alpha_jy_jK_{1j} + y_2\alpha_2\sum_{j=3}^m\alpha_jy_jK_{2j} + Constant\\

注意： Kij表示的是核函数K(xi,xj)K_{ij}表示的是核函数K(x_i,x_j)

  • 对约束条件
    α1y1+α2y2=−∑i=3mαiyi=常数\alpha_1y_1 + \alpha_2y_2 = -\sum_{i=3}^m \alpha_iy_i = 常数

  • 求解

通过约束, 用α2来表示α1用\alpha_2 来表示 \alpha_1, 带回目标中求极小(带回去求解就是一个很简单的一元函数求极小, 直接跳过了);

称此时求得的α2\alpha_2为
α2unclipped=αold+y2(E1−E2)η\alpha_2^{unclipped} = \alpha^{old} + \frac{y_2(E_1-E_2)}{\eta}

其中,
η=K11+K22−2K12Ei=f(xi)−yif(xi)=∑i=1mαiyiK(xix)+b(判别函数)\eta = K_{11} + K_{22} - 2K_{12}\\ E_i = f(x_i) - y_i \\ f(x_i)=\sum_{i=1}^m \alpha_iy_iK(x_ix)+b(判别函数)\\

  • 对原始解进行剪切

上述求出的解未考虑到约束条件
0≤αi≤Cα1y1+α2y2=常数0\leq \alpha_i \leq C\\ \alpha_1y_1 + \alpha_2y_2 = 常数

其实后一个约束条件上面已经考虑到了, 现在只是做一个一般性的讨论；

  • 当y1≠y1⇒α1−α2=k(常数)y_1\neq y_1 \Rightarrow \alpha_1 - \alpha_2 = k(常数)
  • 当y1=y1⇒α1+α2=k(常数)y_1 = y_1 \Rightarrow \alpha_1 + \alpha_2 = k(常数)

在二维平面上直观地表达两个约束条件：

SMO图示

对α2\alpha_2进行剪切，有
L≤α2≤HL\leq\alpha_2\leq H

其中，
{y1≠y1，L=max⁡(0,α2−α1),H=min(C,C+α2−α1)y1=y1，L=max⁡(0,α2+α1−C),H=min(C,α2+α1)\begin{cases} y_1\neq y_1， L=\max(0, \alpha_2-\alpha_1), H=min(C, C+\alpha_2-\alpha_1)\\ y_1 = y_1，L=\max(0, \alpha_2+\alpha_1-C), H=min(C,\alpha_2+\alpha_1)\\ \end{cases}

  • 经过剪切
    α2={H,α2unclipped>Hα2unclipped,L≤α2unclipped≤HL,α2unclipped<L\alpha_2 = \begin{cases} H, \alpha_2^{unclipped}>H\\ \alpha_2^{unclipped}, L\leq\alpha_2^{unclipped}\leq H\\ L, \alpha_2^{unclipped}<L \\ \end{cases}

再带回约束α1y1+α2y2=常数,求出α1\alpha_1y_1 + \alpha_2y_2 = 常数,求出\alpha_1;

启发式选择变量

  • 第一个变量的选择

首先遍历整个样本集， 选择违反KKT条件的α1\alpha_1

KKT条件:
{αi=0,yi(wTxi+b)≥1αi=C,yi(wTxi+b)≤10<αi<C,yi(wTxi+b)=1\begin{cases} \alpha_i = 0, y_i(w^Tx_i + b) \geq 1 \\ \alpha_i = C, y_i(w^Tx_i + b) \leq 1 \\ 0 < \alpha_i < C, y_i(w^Tx_i + b) = 1 \\ \end{cases}

  • 第二个变量的选择

由于α2unclipped=αold+y2(E1−E2)η\alpha_2^{unclipped} = \alpha^{old} + \frac{y_2(E_1-E_2)}{\eta}
后面的项相当于步长，我们希望算法尽快收敛，所以后面的步长越大越好；

前面选出的α1对应E1\alpha_1对应E_1
{当E1>0时，选择最小的Ei当作E2当E1<0时，选择最大的Ei当作E2\begin{cases} 当E_1>0时， 选择最小的E_i当作E_2\\ 当E_1<0时， 选择最大的E_i当作E_2\\ \end{cases}

每完成对两个变量的优化后, 要对b的值进行更新， 因为b值关系到f(xi)f(x_i)的计算

  • b的计算

    • 0<α1<C0<\alpha_1<C

    由y1(wTx1+b)=1可求得b1y_1(w^Tx_1 + b) = 1 可求得b_1

    • 0<α2<C0<\alpha_2<C

    由y2(wTx2+b)=1可求得b2y_2(w^Tx_2 + b) = 1 可求得b_2

    • 若0<α1，α2<C0<\alpha_1，\alpha_2<C

    则b1=b2b_1 = b_2

    • 若不满足0<α1，α2<C0<\alpha_1，\alpha_2<C

    则取b=b1+b22b = \frac{b_1 + b_2}{2}

SVM概率化输出

标准的 SVM 的无阈值输出为
f(x)=h(x)+bf(x) = h(x) + b
其中,
h(x)=∑i=1myiαiK(xi,x)h(x) = \sum_{i=1}^{m}y_i\alpha_iK(xi, x)

Platt(发明SMO的那个) 利用 sigmoid-fitting 方法，将标准 SVM 的输出结果进行后处理，转换成后验概率。
P(y=1∣f)=11+eAf+BP(y=1|f) = \frac{1}{1+e^{Af+B}}
其中，A、B为待拟合的参数，f为样本x的无阈值输出；

sigmoid-fitting 方法的优点在于保持 SVM 稀疏性的同时，可以良好的估计后验概率。

拟合 sigmoid 模型

用极大似然估计来估计公式中的参数 A,B

  • 定义训练集为(yi.ti),ti(y_i.t_i), t_i为目标概率输出值

定义为ti=yi+12(yi所属的类别：{−1,1})t_i = \frac{y_i+1}{2}(y_i所属的类别：\{-1,1\})

  • 极小化训练集上的负对数似然函数
    min⁡−∑i=1mtilog⁡Pi+(1−ti)log⁡(1−Pi)其中,Pi=11+eAfi+B\min - \sum_{i=1}^{m}t_i\log P_i + (1-t_i)\log(1-P_i)\\ 其中, P_i = \frac{1}{1+e^{Af_i + B}}

  • 梯度下降求解

(代码实现的时候， 将SVC中超参probability设置为True， 预测时predict_proba， 可以概率化输出)

Loss 损失求解SVM

还记得之前说过SVM有两种求解方法, 一种是前面的找支撑向量, 另一种是直接Loss函数梯度下降求解；

  • 合页损失(hinge loss)

合页损失

如图：0-1 损失是二分类问题的真正损失函数，合页损失与 logistic 损失是对 0-1 的损失函 数的近似。

SVM的loss函数就是用hinge loss
L(y−(wTx+b))=[1−y(wTx+b)]+[Z]+={Z,Z>00,Z<0L(y-(w^Tx+b)) = [1-y(w^Tx+b)]_+\\ [Z]_+ = \begin{cases} Z, Z > 0\\ 0, Z < 0 \\ \end{cases}

即数据如果被分类正确, 损失为0； 如果被分类错误, 损失为Z；

  • SVM的损失函数(要加正则项)
    min⁡w,b∑i=1m[1−y(wTx+b)]++λ∣∣w∣∣2\min_{w,b}\sum_{i=1}^m[1-y(w^Tx+b)]_+ + \lambda||w||^2

可以直接梯度下降求解w,b因为没有约束了；

SVM多分类

SVM多分类与Logistics回归差不多，就是OVO与OVR， 忘了回去看

总结

优缺点

优点：

  • 特征维度大于样本数时很有效
  • 仅仅使用一部分支撑向量来做超平面， 无需依赖所有数据
  • 有大量的核函数可用， 灵活处理非线性分类
  • 样本量小的时候， 分类准确率高，泛化能力强

缺点：

  • 维度远远大于样本， 表现一般
  • 样本量大不好处理
  • 对缺失值敏感

对于LR和SVM, 如何选择

(吴恩达：)

  • 特征量大， 与样本量差不多， 选择LR或linear Kerenl的SVM
  • 特征量小， 样本不多， 选SVM+Gaussian Kernel(高斯核)
  • 特征量小， 样本很多， 需要手工添加一些feature变成第一条

SVM支持向量机就是这样了, 继续下一章吧！pd的Machine Learning