Jarvis' Blog 成功的路上并不拥挤, 因为坚持的人不多

支持向量机 (Suppoert Vector Machine)

2019-05-15
Jarvis
Post

支持向量机 (support vector machine, SVM) 是一类有监督地对二元数据分类的广义线性分类器, 其决策边界是对学习样本求解的最大间隔超平面.

问题来源: 超平面 (hyperplane) 分类器的不唯一性.

超平面分类器的不唯一性

图 1: 超平面分类器的不唯一性

因此需要给定一个准则来选择一个最优的超平面.

1. 线性可分 SVM 问题构建

线性 SVM 的意思是使用一次函数作为 SVM 分类器, 可分的意思是当前的数据是可以使用分类器完全划分开的, 即可以使用一条直线(二维情况)把数据的两个类别完全分隔开1.

1.1 几何间距

令 $\gamma$ 表示空间一点 $ \xx $ 到超平面

的距离, $ \ww $ 为超平面的法向. 设 $ \xx $ 正投影到超平面的点为 $ \xx_0 $ , 则有

其中 $y$ 取值为 $1$ 或 $-1$, 表示 $ \xx $ 在超平面的上方/下方. 如下图所示.

几何距离

图 2: 几何距离

1.2 硬间隔最大化

因为 $ \xx_0 $ 落在超平面上, 所以代入公式 $\eqref{eq:hyperplane}$ 得到

解得

当超平面在小范围内改变时, 超平面附近点的分类可能会发生变化, 而离超平面远的点的分类不会发生变化. 因此我们要寻找一个尽可能在两类点”中间”的一个超平面(即既要把两类点分开, 还要离两类点尽可能的远), 如下图中红色的线. 这种准则称为最大化间隔 (maximum margin).

最大化间隔

图 3: 最大化间隔

注: 这里是间隔最大化, 因为数据点是线性可分的, 因此强制要求该超平面距离两类点尽可能地远..

由此我们可以得到一个最大化间隔的分类器:

其中 $\gamma_i$ 表示训练集中第 $i$ 个点到超平面的距离. 由于分子项 $y(\ww^T\xx + b)$ 可以在不改变超平面的前提下任意变大, 因此为了方便我们固定 $\gamma\vw=y(\ww^T\xx + b)=1$ . 从而这个问题就变为了

注: 对于直线 $y=ax+3$ , 其对应的 $\ww=(a, -1)^T, b=3$ . 我们同时把 $ \ww $ 和 $b $ 乘以同样的系数 $2$, 则 $\ww=(2a, -2)^T, b=6$ 直线方程变为 $2y=2ax+6$ 和原来的方程等价. 因此在表示同一个超平面的情况下 $ \ww $ 和 $b$ 可以成比例的缩放.

最后我们的分类器可以表示为:

其中目标函数增加 $1/2$ 和平方是为了优化的方便, 其最小值不会因此而改变. 注意到公式 $\eqref{eq:classifier}$ 中的不等式约束, 离目标超平面远的点的约束其实是不必要的, 因为他们会被离超平面更近点的约束所包含, 因此实际起作用的约束所对应的点是我们关心的, 这些点称为支持向量 (support vector), 如下图所示, 蓝色圈中的点为支持向量, 这三个点对应的不等式约束是实际起作用的.

支持向量

图 4: 支持向量

1.3 问题的求解

直接求解原问题是一个带不等式约束的凸二次规划问题(convex quadratic programming), 可以使用凸优化算法求解.

  • Python 上的凸优化包 CVXOPT

1.4 求解对偶问题

带不等式约束的优化问题可以转为对偶问题求解. 使用 Lagrange 乘子法, 优化问题 $\eqref{eq:classifier}$ 可以变为

其中 $\boldsymbol\alpha=(\alpha_1,\cdots,\alpha_n)^T$ 为 Lagrange 乘子向量.

定理: 最优化问题

是原始问题 $\eqref{eq:classifier}$ 的对偶问题. 这里可以用极小化代替目标函数的负数的极大化.

把原问题转化为对偶问题求解有两个好处:

  • 对偶问题一般来说更容易求解
  • 在对偶问题中仅包含了关于数据点 $i, j$ 的内积 $\xx_i^T\xx_j$ 的形式, 从而通过引入核方法(kernel method) 可以把 SVM 泛化为更加复杂的分类器.

1.5 构造分类器

最后可以根据对偶问题的解 $\boldsymbol\alpha^*$ 计算原始问题的解:

选择 $\boldsymbol\alpha^* $ 的一个满足 $\alpha_i^*>0$ 的分量计算 (注意这里要选择严格正的分量): 得到分类器:

1.6 支持向量

根据对偶问题的解 $\boldsymbol\alpha^* $ , 我们把分量 $\alpha_i^* $ 对应的样本点 $ \xx_i $ 称为支持向量. 根据 KKT 互补条件 可知 那么对于 $\alpha_i^*>0$ 的样本点, 必然有 $y_i(\ww^T\xx_i+b)=1$, 从而得到 $\ww^T\xx_i+b=\pm1$ , 那么点 $ \xx_i $ 一定在间隔边界上. 这与我们在前面给出的支持向量的定义是吻合的.

2. 线性不可分 SVM 与软间隔最大化

2.1 软间隔最大化

线性可分 SVM 对于线性不可分的数据是不适用的, 因为上述不等式约束对于部分数据点无法满足. 此时需要修改原来的不等式约束(硬间隔最大化)为间隔最大化2.

原来硬间隔最大化可以满足 $y_i\ww^T\xx_i+b\geq1$ , 线性不可分问题的数据点不一定可以满足该公式, 因此引入松弛变量 $\xi_i>0$ 加到函数间隔上即可使其满足:

对于每个松弛变量我们发现取到正无穷大也会满足约束, 但这样就相当于没有了约束, 因此我们同时要求松弛变量尽可能小, 需要在代价函数增加一项作为惩罚: 其中 $C>0$ 为超参数, $C$ 越大, 对误分类的数据点惩罚越大.

那么线性不可分 SVM 的目标函数变为如下的凸二次规划 注意, 这里的问题关于 $(\ww, b, \xi)$ 的解是存在的, 其中 $ \ww $ 的解唯一, 但 $b$ 的解可能不唯一, 而是存在于一个区间.

2.2 求解对偶问题

使用 Language 乘子法, 带松弛变量的优化问题 $ \eqref{eq:cla2} $ 可以变为

其中 $\boldsymbol\alpha=(\alpha_1,\cdots,\alpha_n)^T,~\boldsymbol\beta=(\beta_1,\cdots,\beta_n)^T$ 均为 Lagrange 乘子向量.

定理: 最优化问题

是原始问题 $ \eqref{eq:cla2} $ 的对偶问题.

上面的定理可以消去 $\boldsymbol\beta$ 而简化为

2.3 构造分类器

线性不可分 SVM 最终构造分类器的公式与可分 SVM 的相同, 求出 $\ww^*$ 和 $b^*$ 即可, 计算 $b^*$ 的时候选择的 $\boldsymbol\alpha^* $ 的分量应当满足 $0<\alpha_i^*<C$ , 类似的这里不能取等号.

2.4 支持向量

在线性不可分的情况下, 把对偶问题 $ \eqref{eq:cla2_dual} $ 的解 $\boldsymbol\alpha^*=(\alpha_1^*,\alpha_2^*,\cdots,\alpha_n^*)^T$ 中对应于 $\alpha_i^*>0$ 的数据点 $ \xx_i $ 称为(软间隔的)支持向量. 如下图所示.

软间隔支持向量机分类超平面, 存在误分的数据点

图 5: 软间隔支持向量机分类超平面, 存在误分的数据点

软间隔的支持向量可能落在 (1) 间隔边界上 (2) 间隔边界到分离超平面之间 (3) 分离超平面误分的一侧:

  • 若 $\alpha_i^*=0$, 则 $\xi_i=0$, 数据点为间隔边界两侧的点
  • 若 $0<\alpha_i^* < C$ , 则 $\xi_i=0$, 数据点落在间隔边界上, 是支持向量
  • 若 $\alpha_i^*=C$ 且 $0<\xi_i<1$ , 则数据点落在间隔边界到分离超平面之间
  • 若 $\alpha_i^*=C$ 且 $\xi_i=1$ , 则数据点落在分离超平面上
  • 若 $\alpha_i^*=C$ 且 $\xi_i>1$ , 则数据点落在分离超平面误分的一侧

后三条结论可以根据公式 $\eqref{eq:soft}$ 得出.

2.5 合页损失函数 (hinge loss)

线性 SVM 由以下几部分组成:

  1. 模型: 分离超平面 $\ww^{*T}\xx+b^*=0$
  2. 决策函数: $f(\xx)=\text{sign}(\ww^{*T}\xx+b^*)$
  3. 学习策略: 软间隔最大化
  4. 求解算法: 凸二次规划

根据最初对线性 SVM 的期望, 其损失函数也可以按如下方式构造: 其中第一项为经验损失, $L[x]=[1-x]_+=\text{Relu}(1-x)$ 称为合页损失函数(hinge loss), 当样本点的分类 $y_i(\ww^T\xx_i+b)>1$ 时, 损失为0, 反之损失线性递增. 目标函数的第二项为正则化项. 可以证明优化问题 $\eqref{eq:hinge}$ 与优化问题 $\eqref{eq:cla2}$ 等价. 合页损失函数的图像如下图所示.

合页损失函数与感知机损失, 0-1损失对比

图 6: 合页损失函数与感知机损失, 0-1损失对比

3. SVM 的核方法

核方法可以把普通的线性 SVM 推广到非线性. 核方法的直观来自于数据点升维. 如下图中二维的点.

非线性分类器

图 7: 非线性分类器

线性分类器无法得到圆形的分类边界, 但是如果通过某个函数 $\Phi(\cdot)$ 把点映射到三维空间(比如映射成锥形, 中间点的值较小, 周围点的值较大), 那么就可以找到一个三维空间中的二维平面把两类点分开. 如此我们只需要把第1节和第2节中所有的 $ \xx $ 替换为 $ \Phi(\xx) $ , 其他保持不变即可得到非线性 SVM 对应的推导.

3.1 核函数

可以发现在求解对偶问题时, $ \Phi(\xx_i)\cdot\Phi(\xx_j) $ 总是以内积的形式出现, 因此我们可以把这样的形式定义为一个关于 $ \xx_i $ 和 $ \xx_j $ 的二元函数 $K(\cdot,\cdot)$

这样我们仍然可以得到相同的决策函数而简化了计算方式以及 $\Phi(\cdot)$ 函数的构造.

核函数的种类 $\def\kk{K(x_1,x_2)}$:

  • $\kk = (x_1\cdot x_2)$ 是核函数
  • $f(\cdot)$ 是定义在 $R^n$ 上的实值函数, 则 $\kk = f(x_1)f(x_2)$ 是核函数
  • 核函数的和与积都是核函数
  • 若 $K_1(x_1, x_2)$ 是 $R^m\times R^m$ 上的核函数, $\theta(x)$ 是从 $R^n$ 到 $R^m$ 上的映射, 则 $K_2(x_1, x_2) = K_1(\theta(x_1), \theta(x_2))$ 是 $R^n$ 到 $R^n$ 上的核函数. 特别的, 若矩阵 $B$ 半正定, 则 $\kk = x_1^TBx_2$ 是 $R^n$ 到 $R^n$ 上的核函数.

常用的核函数:

  • 多项式核函数 $\kk = (x_1\cdot x_2)^d$ 和 $\kk = (x_1\cdot x_2 + 1)^d$
  • Gauss 径向基函数 $\kk = \exp\left(\frac{-\lVert x_1-x_2\rVert^2}{\sigma^2}\right)$

3.2 C - 支持向量分类机

使用步骤:

  1. 选择核函数 $K(\cdot,\cdot)$ 和惩罚参数 $C\geq0$

  2. 求解优化问题:

    的解为 $\boldsymbol\alpha^*=(\alpha_1^*,\cdots,\alpha^*_n)$ .

  3. 计算 $b^*$ , 选择位于区间 $(0, C)$ 的 $\alpha^*$ 的分量 $\alpha^*_j$ , 据此计算

  4. 构造决策函数

  5. 获得支持向量* : 支持向量为 $\{(\xx_j, y_j)\lvert \alpha^*_j=0\}$ .

4. Appendix*

5. Reference

  1. 支持向量机——理论、算法与拓展
    邓乃扬, 田英杰
    No Link. In 2009, 科学出版社 

  2. 统计学习方法
    李航
    No Link. In 2012, 清华大学出版社 


Comments

Content