支持向量机

硬间隔支持向量机

支持向量机最简单的情况是线性可分支持向量机，或硬间隔支持向量机
- 构建它的条件是训练数据线性可分
- 函数间隔与几何间隔
  - 函数间隔：$label(w^Tx+b)\ or\ y_i(w^Tx+b)$
  - 几何间隔：$r=\frac{label(w^Tx+b)}{||w||_2}$，当数据被正确分类时，几何间隔就是点到超平面的距离
- 学习策略是 最大间隔法。可以表示为凸二次规划问题，其原始最优化问题为
  $$ \min_{w, b} \frac{1}{2}|w|^{2} \quad \\
  s.t. \quad y_{i}\left(w \cdot x_{i}+b\right)-1 \geqslant 0, \quad i=1,2, \cdots, N $$
  - 应用拉格朗日对偶性，求解对偶问题得到原始问题的最优解
    - 二次规划问题的对偶问题是
      $$\min L(w,b,\alpha) = \frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_{i} \alpha_{j} y_{i} y_{j}\left(x_{i} \cdot x_{j}\right)-\sum_{i=1}^{N} \alpha_{i} \quad \\ s.t. \quad \sum_{i=1}^{N} \alpha_{i} y_{i}=0 \\ \alpha_{i} \geqslant 0, \quad i=1,2, \cdots, N$$
      其中$\alpha = { \alpha_1, \alpha_2, …, \alpha_N }^T$是拉格朗日乘子向量
    - 求解出对偶问题的最优值 $a^{*} = { \alpha_1^{*}, \alpha_2^{*}, …, \alpha_N^{*} }^T$
    - 对偶问题的解 $\alpha^{*}$ 中满足 $\alpha_{i}^{*}>0$ 的实例点 $x_i$ 称为支持向量。支持向量可在间隔边界上，也可在间隔边界与分离超平面之间，或者在分离超平面误分一侧。
  - 进而求得最优化问题的解为 $w^{*}$ ， $b^{*}$ ，
    - $w^*=\sum\limits_{i=1}^{N} \alpha_{i}^{*} y_{i} x_{i}$
    - 选择 $a^{*}$ 的一个正分量 $ a^{*}_j>0 $ ,
    - 计算 $ b^{*}=y_j - \sum\limits_{i=1}^{N} \alpha_{i}^{*} y_{i} (x_{i}x_{j})$
  - 得到线性可分支持向量机，分离超平面是
    - $w^{*} \cdot x+b^{*}=0$
  - 得到分类决策函数是
    - $f(x)=\operatorname{sign}\left(w^{*} \cdot x+b^{*}\right)$
- 线性可分支持向量机的最优解存在且唯一。位于间隔边界上的实例点为支持向量。最优分离超平面由支持向量完全决定。

软间隔支持向量机

引入松弛变量 $\xi_{\mathrm{i}}$ ，使近似线性可分的训练数据“可分”
原始最优化问题是
$$\min _{w, b, \xi} \frac{1}{2}|w|^{2}+C \sum_{i=1}^{N} \xi_{i} \quad \\ s.t. \quad y_{i}\left(w \cdot x_{i}+b\right) \geqslant 1-\xi_{i}, \quad i=1,2, \cdots, N\\\xi_{i} \geqslant 0, \quad i=1,2, \cdots, N$$
$C>0$ 被称为惩罚参数
线性可分支持向量机的解 $w^{*}$ 唯一但 $b^{*}$ 不唯一。对偶问题是
$$\min _{\alpha} \frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_{i} \alpha_{j} y_{i} y_{j}\left(x_{i} \cdot x_{j}\right)-\sum_{i=1}^{N} \alpha_{i} \quad \\ s.t. \quad \sum_{i=1}^{N} \alpha_{i} y_{i}=0 \quad 0 \leqslant \alpha_{i} \leqslant C, \quad i=1,2, \cdots, N$$
线性支持向量机学习等价于最小化二阶范数正则化的合页函数
$$\sum_{i=1}^{N}\left[1-y_{i}\left(w \cdot x_{i}+b\right)\right]_{+}+\lambda|w|^{2}$$

非线性支持向量机

对于输入空间中的非线性分类问题，可以通过非线性变换将它转化为某个高维特征空间中的线性分类问题，在高维特征空间中学习线性支持向量机。
核函数表示通过一个非线性转换后的两个实例间的内积
- 核函数$K(x,z)$
  - 存在一个从输入空间x到特征空间的映射$\mathcal{X} \rightarrow \mathcal{H}$，对任意$\mathcal{X}$，有$K(x, z)=\phi(x) \cdot \phi(z)$
- 对称函数$K(x,z)$为正定核的充要条件：
  - 对任意$\mathrm{x}_{\mathrm{i}} \in \mathcal{X}, \quad \mathrm{i}=1,2, \ldots, \mathrm{m}, \forall m \in \mathbf{N}$，对称函数$K(x,z)$对应的Gram矩阵是半正定的
- 在线性支持向量机学习的对偶问题中，用核函数$K(x,z)$替代内积，求解得到的就是非线性支持向量机
  $$f(x)=\operatorname{sign}\left(\sum_{i=1}^{N} \alpha_{i}^{*} y_{i} K\left(x, x_{i}\right)+b^{*}\right)$$

SMO算法

不断地将原二次规划问题分解为只有两个变量的二次规划子问题，并对子问题进行解析求解，直到所有变量满足KKT条件为止