线性可分支持向量机
定义
对于一个数据集 $D$, 如果能找到一个超平面 $H: w^Tx + b = 0$, 将数据分为两类. 即对任意 $(x_i, y_i) \in D$, 若 $y_i = 1$, 则 $w^Tx_i + b \geq 0$; 若 $y_i = -1$, 则 $w^Tx_i + b < 0$. 则称 $D$ 是 线性可分的 , 超平面 $H$ 是 $D$ 的一个 分离超平面.
最优超平面不仅要能够将数据分开, 还要使得两类数据点到超平面的距离尽可能远.
考虑到 $w,b$ 任意缩放都不影响超平面的位置, 我们可以规定 $w^Tx + b = 1$ 为最近的正类数据点满足的方程. 此时距离为 $1/{\|w\|}$, 要最大化这个量, 即化归成凸二次规划问题:
$$ \begin{aligned} & \min_{w, b} \frac{1}{2} \|w\|^2 \\ & \text{s.t.} \quad y_i(w \cdot x_i + b) \geq 1, \quad i = 1, 2, \cdots, n \end{aligned} $$只要 $D$ 是线性可分的, 上述问题一定有解且唯一. 对应的分类决策函数
$$ f(x) = \text{sign}(w^Tx + b) $$称为 线性可分支持向量机.
引入 Lagrange 乘子 $\alpha_i \geq 0$:
$$ L(w, b, \alpha) = \frac{1}{2} \|w\|^2 - \sum_{i=1}^n \alpha_i(y_i(w \cdot x_i + b) - 1) $$对 $w, b$ 求偏导为 $0$, 得到
$$ \begin{aligned} & w = \sum_{i=1}^n \alpha_i y_i x_i \\ & 0 = \sum_{i=1}^n \alpha_i y_i \end{aligned} $$代入 $L(w, b, \alpha)$, 得到对偶问题:
线性可分对偶问题
$$ \begin{aligned} & \max_{\alpha} \sum_{i=1}^n \alpha_i - \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j y_i y_j x_i \cdot x_j \\ & \text{s.t.} \quad \alpha_i \geq 0, \quad \sum_{i=1}^n \alpha_i y_i = 0 \end{aligned} $$由 KKT 条件, 最优解一定满足
$$ \begin{aligned} \alpha_i(y_i(w \cdot x_i + b) - 1) &= 0 \\ y_i(w \cdot x_i + b) - 1 &\geq 0 \\ \alpha_i &\geq 0 \\ \end{aligned} $$由于 $\alpha_i$ 不全为 $0$, 存在 $j$ 使得 $y_j(w \cdot x_j + b) = 1$, 由此
$$ b = y_j - w \cdot x_j = y_j - \sum_{i=1}^n \alpha_i y_i x_i \cdot x_j $$乘上 $\alpha_jy_j$ 做累和, 有
$$ 0=\sum_{j=1}^n \alpha_jy_jb = \sum_{j=1}^n \alpha_j - \| w \|^2 $$上式中 $\alpha_i=0$ 的 $i$ 也成立, 因为都是 $0$ 不影响结果. 注意到 $w = \sum_{i=1}^n \alpha_i y_i x_i$ 也只收到 $\alpha_i > 0$ 的影响, 而这些项的点都落在间隔边界
$$ H_1: w \cdot x + b = 1, \quad H_2: w \cdot x + b = -1 $$上, 称这些点 $x_i$ 为 支持向量.
支持向量机的留一误差
$$ \hat{R}_{\text{loo}} = \frac{1}{n} \sum_{i=1}^n I(f_{D-\{x_i\}}(x_i) \neq y_i) $$则 $\hat{R}_{\text{loo}} \le N_{SV}/n$, 其中 $N_{SV}$ 为支持向量的个数.
线性支持向量机
要求 $D$ 线性可分有点苛刻. 容忍一些误差, 引入松弛变量 $\xi_i \geq 0$, 使得约束条件变为
$$ y_i(w \cdot x_i + b) \geq 1 - \xi_i $$对于被错误分类的点, $\xi_i$ 可以大于 $1$. 把 $\xi_i \ne 0$ 的点视为特异点, 那么希望特异点尽可能少, 于是优化目标变为
$$ \begin{aligned} & \min_{w, b, \xi} \frac{1}{2} \|w\|^2 + C \sum_{i=1}^n I(\xi_i \ne 0) \\ & \text{s.t.} \quad y_i(w \cdot x_i + b) \geq 1 - \xi_i, \quad \xi_i \geq 0 \end{aligned} $$直接用 $\xi_i$ 代替 $I(\xi_i \ne 0)$, 问题变为
$$ \begin{aligned} & \min_{w, b, \xi} \frac{1}{2} \|w\|^2 + C \sum_{i=1}^n \xi_i \\ & \text{s.t.} \quad y_i(w \cdot x_i + b) \geq 1 - \xi_i, \quad \xi_i \geq 0 \end{aligned} $$既然要 $\xi_i$ 尽可能小, 不妨取 $\xi_i = 1 - y_i(w \cdot x_i + b)$, 引入合页损失函数 $h(z) = \max(0, 1-z)$, 即
$$\xi_i = h(y_i(w \cdot x_i + b))$$则提出一个 $C$ 后, 优化目标变为
$$ \min_{w, b} \frac{1}{2C} \|w\|^2 + \sum_{i=1}^n h(y_i(w \cdot x_i + b)) $$做了这么多, 只是相当于把 0-1 损失函数换成了合页损失函数.
回到原问题, 引入 Lagrange 乘子 $\alpha_i, \beta_i \geq 0$, 得到
$$ L(w, b, \xi, \alpha, \beta) = \frac{1}{2} \|w\|^2 + C \sum_{i=1}^n \xi_i - \sum_{i=1}^n \alpha_i(y_i(w \cdot x_i + b) - 1 + \xi_i) - \sum_{i=1}^n \beta_i \xi_i $$对 $w, b, \xi$ 偏导为 $0$, 得到
$$ \begin{aligned} & w = \sum_{i=1}^n \alpha_i y_i x_i \\ & 0 = \sum_{i=1}^n \alpha_i y_i \\ & \beta_i = C - \alpha_i \end{aligned} $$代入 $L(w, b, \xi, \alpha, \beta)$, 得到对偶问题
线性支持向量机对偶问题
$$ \begin{aligned} & \max_{\alpha} \sum_{i=1}^n \alpha_i - \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j y_i y_j x_i \cdot x_j \\ & \text{s.t.} \quad 0 \leq \alpha_i \leq C, \quad \sum_{i=1}^n \alpha_i y_i = 0 \end{aligned} $$与线性可分支持向量机类似, 只是多了一个 $\alpha_i \leq C$ 的约束. 现在考虑 KKT 条件, 有
$$ \begin{aligned} \alpha_i(y_i(w \cdot x_i + b) - 1 + \xi_i) &= 0 \\ y_i(w \cdot x_i + b) - 1 + \xi_i &\geq 0 \\ \beta_i \xi_i &= 0 \\ \alpha_i &\geq 0 \\ \beta_i &\geq 0 \\ \alpha_i + \beta_i&=C \end{aligned} $$则 $\alpha_i > 0$ 的点 $x_i$ 为支持向量, 满足 $y_i(w \cdot x_i + b) = 1 - \xi_i$. 这点与线性可分支持向量机的支持向量不同. 但进一步如果 $\alpha_i \lt C$ , 则 $\beta_i \gt 0$, 则 $\xi_i=0$, 从而 $y_i(w \cdot x_i + b) = 1$, 这样就一致了.
进一步, 把 $y_i(w \cdot x_i + b) = 1$ 两边乘 $y_i$, 类似有
$$ b = y_j - \sum_{i=1}^n \alpha_i y_i x_i \cdot x_j $$因而最优分类超平面为
$$ \sum_{i=1}^n \alpha_i y_i x_i \cdot x + b = 0 $$和决策函数
$$ f(x) = \text{sign}\left(\sum_{i=1}^n \alpha_i y_i x_i \cdot x + b\right) $$超平面法向量可以被唯一确定, 但是偏置不唯一.
SMO 算法
SMO 算法是一种启发式算法, 用于求解支持向量机的对偶问题. SMO 算法的基本思想是: 每次选择两个变量, 固定其他变量, 优化这两个变量. 这样不断迭代, 直到收敛.
设当前迭代的两个变量为 $\alpha_i, \alpha_j$, 则
$$ \alpha_1 y_1 + \alpha_2 y_2 = -\sum_{i=3}^n \alpha_i y_i $$同乘 $y_1$, 有
$$ \alpha_1 + \alpha_2 y_1y_2= -\sum_{i=3}^n \alpha_i y_1y_i $$记右边为 $\gamma$, $s=y_1y_2 \in \{-1, 1\}$, 则
$$ \alpha_1 + s\alpha_2 = \gamma $$记$K_{ij} = x_i \cdot x_j$, $v_i = \sum_{j=3}^{N} \alpha_j y_j K_{ij}$, 则对偶问题转化为
$$ \begin{aligned} & \max_{\alpha_1, \alpha_2} \alpha_1 + \alpha_2 - \frac{1}{2} K_{11}\alpha_1^2 - \frac{1}{2} K_{22}\alpha_2^2 - sK_{12}\alpha_1\alpha_2 - y_1v_1\alpha_1 - y_2v_2\alpha_2 \\ & \text{s.t.} \quad 0 \leq \alpha_i \leq C, \quad \alpha_1 + s\alpha_2 = \gamma \end{aligned} $$再由 $\alpha_1 = \gamma - s\alpha_2$, 代入目标函数, 并对 $\alpha_2$ 求导为 $0$, 得到
$$ \alpha_2 = \frac{s(K_{11}-K_{12})\gamma + y_2(v_1 - v_2) - s + 1}{K_{11} + K_{22} - 2K_{12}} $$代入 $v$ 的定义, 随后化简得
$$ \alpha_2 = \alpha_2^* + y_2 \frac{(y_2 - f(x_2))- (y_1-f(x_1))}{K_{11} + K_{22} - 2K_{12}} $$别忘了约束 $0 \le \alpha_1, \alpha_2 \le C$, 以及 $\alpha_1 + s\alpha_2 = \gamma$, 对 $\alpha_2$ 进行裁剪为 $\alpha_2^{\text{clip}}$. 相应地,
$$ \alpha_1 = \alpha_1^* + s(\alpha_2^* - \alpha_2^{\text{clip}}) $$最后, 更新 $b$. 假设在 $\alpha_1, \alpha_2$ 中, $0 \lt \alpha_i \lt C$, 则
$$ b = y_i - \sum_{j=1}^n \alpha_j y_j K_{ij} $$关于选取 $\alpha_1, \alpha_2$, 一般有两个原则:
- 选择违反 KKT 条件最严重的两个变量.
- 选择两个变量使得目标函数有最大变化.
核方法和非线性支持向量机
对于非线性问题, 可以通过核方法将数据映射到高维空间, 从而在高维空间中找到一个线性超平面.
假设有一个映射 $\phi: \mathcal{X} \mapsto \mathcal{Z}$, 则在 $\mathcal{Z}$ 的线性支持向量机变为:
$$ \begin{aligned} & \min_{w, b, \xi} \frac{1}{2} \|w\|^2 + C \sum_{i=1}^n \xi_i \\ & \text{s.t.} \quad y_i(w \cdot \phi(x_i) + b) \geq 1 - \xi_i, \quad \xi_i \geq 0 \end{aligned} $$对应的对偶问题为
$$ \begin{aligned} & \max_{\alpha} \sum_{i=1}^n \alpha_i - \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j y_i y_j \phi(x_i) \cdot \phi(x_j) \\ & \text{s.t.} \quad 0 \leq \alpha_i \leq C, \quad \sum_{i=1}^n \alpha_i y_i = 0 \end{aligned} $$相应的分类决策函数为
$$ f(x) = \text{sign}\left(\sum_{i=1}^n \alpha_i y_i \phi(x_i) \cdot \phi(x) + b\right) $$然而, 直接计算 $\phi(x_i) \cdot \phi(x_j)$ 的复杂度很高. 为此, 引入核函数
定义
设 $\mathcal{X}$ 是输入空间, $\mathcal{Z}$ 是特征空间, 如果存在一个从 $\mathcal{X}$ 到 $\mathcal{Z}$ 的映射 $\phi$, 使得对任意 $x, x' \in \mathcal{X}$, 都有
$$ K(x, x') = \phi(x) \cdot \phi(x') $$则称 $K$ 为 核函数.
注意, 这里我们不再需要显式地计算 $\phi(x_i)$, 因为结果只与 $K(x_i, x_j)$ 有关.
非线性支持向量机对偶问题
$$ \begin{aligned} & \max_{\alpha} \sum_{i=1}^n \alpha_i - \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j y_i y_j K(x_i, x_j) \\ & \text{s.t.} \quad 0 \leq \alpha_i \leq C, \quad \sum_{i=1}^n \alpha_i y_i = 0 \end{aligned} $$此时, 分类决策函数为
$$ f(x) = \text{sign}\left(\sum_{i=1}^n \alpha_i y_i K(x_i, x) + b\right) $$定义
$\mathcal{X}$ 上的函数 $K: \mathcal{X} \times \mathcal{X} \mapsto \mathbb{R}$ 称为 正定对称核函数, 如果对任意 $x_1, x_2, \cdots, x_n \in \mathcal{X}$, 核矩阵 (Gram 矩阵) $[K_{ij}]_{m \times m}$ 是半正定的.
常见的核函数有:
- 线性核函数: $K(x, x') = x \cdot x'$, 对应线性支持向量机.
- 多项式核函数: $K(x, x') = (x \cdot x' + 1)^d, c \gt 0$
- 高斯核函数: $K(x, x') = \exp\left(-\frac{\|x-x'\|^2}{2\sigma^2}\right), \sigma \gt 0$