SVM

支持向量机(SVM)

• 间隔

  在支持向量机中, 我们用间隔刻画划分 超平面与样本之间的距离。

  引理1：$\bf{R}^d$空间中某点$p$到超平面$w^Tx+b=0$的距离为

$$\frac{1}{||w||}|w^Tp+b|$$

​ 定义1：间隔表示距离划分超平面最近的样本到划分超平面距离的两倍, 即

$$\gamma=2\min_i\frac{1}{||w||}|w^Tp+b|$$

​ 定理1：线性支持向量机的目标是找到一组合适的参数 $(w,b)$, 使得

$$\max_{w,b}\min_i\frac{2}{||w||}|w^Tp+b|$$ $$s.t.\ \ \ \ \ \ \ \ \ \ \ y_i(w^Tx_i+b)\gt0,\ \ \ \ \ i=1,2,....m$$

​

​ 即线性支持向量机希望在特征空间找到一个划分超平面, 将属于不同标记的样本分开, 并且该划分超平面距离 各样本最远

• 线性支持向量机基本型

  引理2： 若 $(w^,b^) $是定理3优化问题的解, 那么对任意r > 0, $(rw^,rb^) $仍是该优化问题的解

  由于对$(w,b)$的放缩不影响解, 为了简化优化问题, 我们约束$(w,b)$使得

  $$\min_i|w^Tx_i+b|=1$$

  因此，定理1等价于

  $$\min_{w,b}\frac{1}{2}w^Tw$$ $$s.t.\ \ \ \ \ \ \ \ \ \min_iy_i(w^Tx_i+b)=1$$

• 对偶问题

  引理3：对偶问题是主问题的下界，即

  $$\max_{\alpha,\beta}\min_uL(u,\alpha,\beta)\le\min_u\max_{\alpha,\beta}L(u,\alpha,\beta)$$

• 线性支持向量机对偶型

  线性支持向量机的拉格朗日函数为

  $$L(w,b,\alpha)=\frac{1}{2}w^Tw+\sum^m_{i=1}\alpha_i(1-y_i(w^Tx_i+b))$$

  描述的优化问题是：

  $$\min_{w,b}\max_{\alpha}\frac{1}{2}w^Tw+\sum^m_{i=1}\alpha_i(1-y_i(w^Tx_i+b))$$ $$s.t. \ \ \ \ \ \ \ \ \ \alpha_i\ge0,\ \ i=1,2,...,m$$

  其对偶问题为

  $$\max_{\alpha}\min_{w,b}\frac{1}{2}w^Tw+\sum^m_{i=1}\alpha_i(1-y_i(w^Tx_i+b))........*$$ $$s.t. \ \ \ \ \ \ \ \ \ \alpha_i\ge0,\ \ i=1,2,...,m$$

  定理2： (线性支持向量机对偶型)线性支持向量机的 对偶问题等价于找到一组合适的参数 $\alpha$, 使得

  $$\min_\alpha\frac{1}{2}\sum^m_{i=1}\sum^m_{j=1}\alpha_i\alpha_jy_iy_jx_i^Tx_j-\sum^m_{i=1}\alpha_i$$ $$s.t.\ \ \ \ \ \ \ \ \sum^m_{i=1}\alpha_iy_i=0\\ \qquad\qquad\qquad\qquad \alpha_i\ge0,\ \ \ i=1,2,...,m$$

  证明： 因为公式$*$内层对$(w,b)$的优化属于无约束优化问题, 我们可以通过令偏导等于零的方法得到$(w,b)$的最优值

  $$\frac{\partial L}{\partial w}=0\Rightarrow w=\sum^m_{i=1}\alpha_iy_ix_i\\ \frac{\partial L}{\partial b}=0\Rightarrow\sum^m_{i=1}\alpha_iy_i=0$$

  将其代入公式$*$可得

• 核函数

  • 非线性可分问题

    既然在原始的特征空间$\bf{R}^{d}$不是线性可分的, 支持向量机希望通过一个映射 $\phi: \bf{R}^d →\bf{R}^{\tilde{d}}$, 使得数据在新的空间是线性可分的。a

    令$\phi(x)$代表将样本$x$映射到$\bf{R}^{\tilde{d}}$中的特征向量, 参数$w$的维数也要相应变为$\tilde{d}$维。则支持向量机的基本型和对偶型相应变为

    $$\min_{w,b}\frac{1}{2}w^Tw\\ \qquad \qquad s.t.\qquad\qquad y_i(w^T\phi(x_i)+b)\ge1,\qquad i=1,2,...,m$$ $$\min_\alpha\frac{1}{2}\sum^m_{i=1}\sum^m_{j=1}\alpha_i\alpha_jy_iy_j\phi(x_i)^T\phi(x_i)-\sum^m_{i=1}\alpha_i\\ s.t.\qquad\qquad\sum^m_{i=1}\alpha_iy_i=0,\\ \qquad\qquad\qquad\qquad\qquad\alpha_i\ge0,\qquad i=1,2,...m$$

  • 核技巧

    在支持向量机的对偶型中, 被映射到高维的特征向量总是以成对内积的形式存在, 即$\phi(x_i)^T\phi(x_j)$。如果先计算特征在$\bf{R}^{\tilde{d}}$空间的映射, 再计算内积，会非常的复杂。

    核技巧旨在将特征映射和内积这两步运算压缩为一步, 构造一个核函数 $\kappa(x_i,x_j)$, 使得

    $$\kappa(x_i,x_j)=\phi(x_i)^T\phi(x_j)$$

    几种常用核函数：

    | 名称 | 形式 | 优点 | 缺点 |
    | ———— | ——————————————————— | ———————————————————————- | —————————————————- |
    | 线性核 | $x_i^Tx_j$ | 有高效实现，不易过拟合 | 无法解决非线性可分问题 |
    | 多项式核 | $(\beta x_i^Tx_i+\theta)^n$ | 比线性核更一般，$n$直接描述了被映射空间的复杂度 | 参数多，当$n$很大时会导致计算不稳定 |
    | RBF核 | $\exp(-\frac{||x_i-x_j||}{2\alpha^2})$ | 只有一个参数，没有计算不稳定问题 | 计算慢，过拟合风险大 |