支持向量机
线性可分支持向量机
训练数据 \[ T = \{(x_1, y_1), (x_2, y_2), \ldots, (x_N, y_N)\} \]
\[ x_i \in \mathcal{X} = \mathbb{R}^n, \quad y_i \in \mathcal{Y} = \{+1, -1\}, \quad i = 1, 2, \ldots, N \]
分离超平面
\[ w^* \cdot x + b^* = 0 \]
分类决策函数
\[ f(x) = \operatorname{sign}(w^* \cdot x + b^*) \]
函数间隔
\[ \begin{align*} \hat{\gamma}_i &= y_i (w \cdot x_i + b) \\\\ \hat{\gamma} &= \min_{i = 1, 2, \ldots, N} \hat{\gamma}_i \end{align*} \]
规范化函数间隔得到几何间隔
\[ \begin{align*} \gamma_i &= y_i \times \left(\frac{w \cdot x_i + b}{\lVert w \rVert}\right) \\\\ \gamma &= \min_{i=1, \ldots, N} \gamma_i \end{align*} \]
\(\lVert w \rVert\) is \(L_2\) 范数，也就是：
\[ \lVert w \rVert _{2} = \sqrt{w_1^2 + w_2^2 + \cdots + w_n^2} \]
可以得到几何间隔和函数间隔之间的关系：
\[ \gamma_i = \frac{\hat{\gamma}_i}{\lVert w \rVert} \]
间隔最大化
原始问题如下：
\[ \begin{align*} &\max_{w, b} \quad \gamma \\\\ &s.t. \quad y_i\left(\frac{w}{\lVert w \rVert} \cdot x_i + \frac{b}{\lVert w \rVert}\right) \geq \gamma, \quad i = 1, 2, \ldots ,N \end{align*} \]
我们可以将原始问题转换为一个凸二次规划问题。
\[ \begin{align*} &\min_{w, b} \quad \frac{1}{2} \lVert w \rVert ^2 \\\\ &s.t. \quad y_i(w \cdot x_i + b) - 1 \geq 0, \quad i = 1, 2, \ldots, N \end{align*} \]
支持向量满足如下关系：
\[ y_i(w \cdot x_i + b) - 1 = 0 \]
间隔的定义如下：
\[ d = \frac{2}{\lVert w \rVert} \]
学习的对偶算法
如何解上述的凸二次规划问题？应用拉格朗日对偶性得到原始问题的对偶问题：
\[ L(w, b, \alpha) = \frac{1}{2} \lVert w \rVert ^2 - \sum_{i = 1}^{N} \alpha_i y_i (w \cdot x_i + b) + \sum_{i = 1}^{N} \alpha_i \]
在求极大极小问题，先求极小问题 \(\min_{w, b} L(w, b, \alpha)\)
分别对 \(w\)，\(b\) 求偏导，并令偏导为 \(0\) 得：
\[ \begin{align*} \nabla_{w} L(w, b, \alpha) &= w - \sum_{i = 1}^{N} \alpha_i y_i x_i = 0 \\\\ \nabla_b L(w, b, \alpha) &= -\sum_{i = 1}^{N} \alpha_i y_i = 0 \end{align*} \]
也就是
\[ \begin{align*} &w = \sum_{i = 1}^{N} \alpha_i y_i x_i \\\\ &\sum_{i = 1}^{N} \alpha_i y_i = 0 \end{align*} \]
回代，得到
\[ \min_{w, b} 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 \]
再求极大问题
\[ \max_{\alpha} \quad -\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 \]
去掉负号，也就是
\[ \begin{align*} \min_{\alpha} \quad &\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 \\\\ \operatorname{s.t.} \quad &\sum_{i = 1}^{N} \alpha_i y_i = 0 \\ &\alpha_i \geq 0, \quad i = 1, 2, \cdots, N \end{align*} \]
学习算法
输入：\(T\)
输出：分离超平面和分类决策函数
- 构造并求解约束最优化问题。
\[ \begin{align*} \min_{\alpha} \quad &\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 \\\\ \operatorname{s.t.} \quad &\sum_{i = 1}^{N} \alpha_i y_i = 0 \\ &\alpha_i \geq 0, \quad i = 1, 2, \cdots, N \\\\ &\alpha^* = (\alpha_1^{\ast}, \alpha_2^{\ast}, \ldots, \alpha_N^{\ast}) \end{align*} \]
- 计算
\[ \begin{align*} w^{\ast} &= \sum_{i=1}^{N} \alpha_i^{\ast} y_i x_i \\\\ \forall y_j > 0, \quad b^\ast &= y_j - \sum_{i=1}^{N}\alpha_i^\ast y_i(x_i \cdot x_j) \end{align*} \]
线性支持向量机
引进一个松弛变量 \(\xi_i \geq 0\)，
\[ y_i (w \cdot x_i + b) \geq 1 - \xi_i \]
相应的原始最优化问题变为：
\[ \begin{align*} \min_{w, b, \xi} \quad &\frac{1}{2} \lVert w \rVert^2 + C \sum_{i = 1}^{N} \xi_i \\\\ s.t. \quad &y_i(w \cdot x_i + b) \geq 1 - \xi_i \\\\ &i = 1, 2, \ldots, N, \quad \xi_i \geq 0 \end{align*} \]
这里 \(C \geq 0\) 称为惩罚变量，值越大，对误分类的惩罚越大。
求解原始问题的拉格朗日对偶问题得到
\[ \begin{align*} \min_{\alpha} \quad &\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 \\\\ \operatorname{s.t.} \quad &\sum_{i = 1}^{N} \alpha_i y_i = 0 \\ &C \geq \alpha_i \geq 0, \quad i = 1, 2, \cdots, N \end{align*} \]
学习算法
输入：\(T\)
输出：分离超平面和分类决策函数
- 选择惩罚参数，构造并求解： \[ \begin{align*} \min_{\alpha} \quad &\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 \\\\ \operatorname{s.t.} \quad &\sum_{i = 1}^{N} \alpha_i y_i = 0 \\ &C \geq \alpha_i \geq 0, \quad i = 1, 2, \cdots, N \end{align*} \]
得到最优解 \(\alpha^* = (\alpha_1^{\ast}, \alpha_2^{\ast}, \ldots, \alpha_N^{\ast})\)。
- 计算
\[ \begin{align*} w^{\ast} &= \sum_{i=1}^{N} \alpha_i^{\ast} y_i x_i \\\\ \forall C > \alpha_j^{\ast} > 0, \quad b^\ast &= y_j - \sum_{i=1}^{N}\alpha_i^\ast y_i(x_i \cdot x_j) \end{align*} \]
荷叶损失函数
这是对线性支持向量机学习的一种解释，就是最小化以下目标函数：
\[ \min_{w, b} \quad \sum_{i = 1}^{N} [1 - y_i(w \cdot x_i + b)]_+ + \lambda \lVert w \rVert^2 \]
非线性支持向量机
正定核函数
\(K :\mathcal{X} \times \mathcal{X} \to \mathbb{R}\) 是对称函数，\(K(x, z)\) 是正定核函数 \(\Leftrightarrow\) 对于任意 \(x_i \in \mathcal{X}, \quad i = 1, 2, 3, \dots, m\)，\(K(x, z)\) 对应的格拉姆矩阵是半正定的。
\(Gram\) 矩阵
\[ K = [K(x_i, x_j)]_{m \times m} \]
如何判别这个矩阵是半正定的，可以采用特征值判别法，如果一个矩阵的所有特征值都 \(\geq 0\)，则这个矩阵是半正定的。
学习算法
输入：\(T\)
输出：分离超平面和分类决策函数
- 选择惩罚参数，构造并求解： \[ \begin{align*} \min_{\alpha} \quad &\frac{1}{2} \sum_{i = 1}^{N} \sum_{j = 1}^{N} \alpha_i \alpha_j y_i y_j K\left(x_i \cdot x_j\right) - \sum_{i = 1}^{N} \alpha_i \\\\ \operatorname{s.t.} \quad &\sum_{i = 1}^{N} \alpha_i y_i = 0 \\ &C \geq \alpha_i \geq 0, \quad i = 1, 2, \cdots, N \end{align*} \]
得到最优解 \(\alpha^* = (\alpha_1^{\ast}, \alpha_2^{\ast}, \ldots, \alpha_N^{\ast})\)。
- 计算
\[ \begin{align*} w^{\ast} &= \sum_{i=1}^{N} \alpha_i^{\ast} y_i x_i \\\\ \forall C > \alpha_j^{\ast} > 0, \quad b^\ast &= y_j - \sum_{i=1}^{N}\alpha_i^\ast y_i K(x_i \cdot x_j) \end{align*} \]
序列最小最优化算法
两个变量二次规划的求解方式
\[ \begin{align} &\min_{\alpha} \frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N}\alpha_i \alpha_j y_i y_j K(x_i \cdot x_j) - \sum_{i=1}^{N} \alpha_i \\\\ &s.t. \quad \sum_{i = 1}^{N} \alpha_i y_i = 0, \quad C \geq \alpha_i \geq 0, \quad i = 1, 2, \ldots, N \end{align} \]
我们选择 \(\alpha_1，\alpha_2\)，规定其他 \(\alpha_i (i = 3, 4, \dots, N)\)。
学习算法
下面只给出应试过程
我们的目标是，求解下述最小化问题：
\[ \begin{align} &\min_{\alpha_1, \alpha_2} W(\alpha_1, \alpha_2) = \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_{i=3}^{N}y_i\alpha_iK_{i1} + y_2\alpha_2\sum_{i=3}^{N}y_i\alpha_iK_{i2} \tag{1} \\\\ &s.t. \quad \alpha_1y_1 + \alpha_2y_2 = \sum_{i=3}^{N}y_i\alpha_i = \zeta, \quad 0 \leq \alpha_i \leq C, \quad i = 1, 2 \tag{2} \end{align} \]
\(K_{ij} = K(x_i, x_j),i,j = 1,2, \dots, N\)，\(\zeta\) 是一个常数。同时需要注意的是，公式 \((1)\) 缺少了常数项
\[ \text{const} = \sum_{i=3}^N \alpha_i - \frac{1}{2} \sum_{i=3}^N \sum_{j=3}^N \alpha_i \alpha_j y_i y_j K(x_i, x_j) \]
但这个常数项不会影响优化 \(\alpha_1\) 和 \(\alpha_2\) 的结果，故可以省略。
我们考虑 \(\alpha_2\) 的最优化问题。
如果 $ y_1 y_2 $
\[ L = \max(0, \alpha_2^{old} - alpha_1^{old}), \quad H = \min(C, C + \alpha_2^{old} - alpha_1^{old}) \tag{3} \]
否则
\[ L = \max(0, \alpha_2^{old} + alpha_1^{old} - C), \quad H = \min(C, \alpha_2^{old} + alpha_1^{old}) \tag{4} \]
为了叙述简单，记
\[ g(x) = \sum_{i=1}^{N}\alpha_i y_i K(x_i, x) + b \]
令
\[ E_i = g(x_i) - y_i = \sum_{j=1}^{N}\alpha_j y_j K(x_j, x_i) + b - y_i, \quad i = 1, 2 \]
接下来我们更新 \(\alpha_2\)
\[ \alpha_2^{new,unc} = \alpha_2^{old} + \frac{y_2(E_1 - E_2)}{\eta}, \quad \eta = K_{11} + K_{22} - 2K_{12} \]
\[ \alpha_2^{new} = \begin{cases} H, &\alpha_2^{new,unc} > H \\\\ \alpha_2^{new,unc}, &L \leq \alpha_2^{new,unc} \leq H \\\\ L, &\alpha_2^{new,unc} < L \end{cases} \]
N然后再更新 \(\alpha_1\)
\[ \alpha_1^{new} = \alpha_1^{old} + y_1 y_2(\alpha_2^{old} - \alpha_2^{new}) \]
如何选择 \(\alpha_1\) 和 \(\alpha_2\)
- 在所有节点中选择具有最大 \(E_i\) 值的节点作为 \(\alpha_1\)。
- 选择使得 \(|E_1 - E_2|\) 最大的节点作为 \(\alpha_2\)。
求解阈值 b 和 E 的计算方法
\[ b_1^{new} = -E_1 - y_1 K_{11} (\alpha_1^{new} - \alpha_1^{old}) - y_2 K_{21} (\alpha_2^{new} - \alpha_2^{old}) + b^{old} \]
\[ b_2^{new} = -E_2 - y_1 K_{12} (\alpha_1^{new} - \alpha_1^{old}) - y_2 K_{22} (\alpha_2^{new} - \alpha_2^{old}) + b^{old} \]
\[ b^{new} = \frac{b_1^{new} + b_2^{new}}{2} \]
此外
更新 \(E\)：
\[ E_i^{new} = \sum_{\mathcal{S}}y_j \alpha_j K(x_i, x_j) + b^{new} - y_i \]
其中 \(\mathcal{S}\) 包含所有支持向量 \(x_i\)。样本 \(x_i\) 是支持向量 \(\Leftrightarrow\) \(0 < \alpha_i^* < C\)。