- 问题定义
- 向一般QP问题转化
- 转为对偶问题
- 回到 SVM 优化问题上
- SVM 中的 SMO 方法
- 松弛变量的加入 (hinge损失)
- 线性 SVM 总结
- 核函数的应用
- 非线性 SVM 总结
- SVM 的现代优化方法
整理一下之前有关 SVM 的笔记，并补充一些内容，包括原始问题定义、对偶问题推导、松弛变量的加入、核函数的应用等。
Cham’s Blog 首发原创
问题定义
直观先验：超平面在两类中间，且距离两边都尽量远 记号：给定 ${ x_i,y_i }, \ i=1,\dots,n$, $x_i \in \mathbb{R}^d,\ y_i \in {-1,+1}$ 模型，$h_{\mathrm{w},b}(x)=\mathrm{w}^{\top}x+b$
所有属于 $\bullet$ 的点满足 $h(x)>0$，所有属于 $\circ$ 的点满足 $h(x)<0$ 定义距离：（点到超平面距离，其中 $x_A$ 为任意一点，$x_B$ 为 $x_A$ 在超平面上的投影点） \(\begin{cases} x_B = x_A - d_{AB} \frac {\mathrm{w} } {\| \mathrm{w} \|} \\\ \mathrm{w}^Tx_B+b = 0 \end{cases}\)
联立上面公式可以得出点到超平面间隔 $\sigma_i$ 计算公式
\[d_{AB}=\frac {\mathrm{w}^T } {\| \mathrm{w} \|} x^A+\frac b {\| \mathrm{w} \|} \ \Longrightarrow \ \sigma_i\triangleq \frac {\mathrm{w}_i } {\| \mathrm{w} \|} x_i+\frac b {\| \mathrm{w} \|}\]则 SVM 的目的是从所有 $\sigma_i$ 中找出最小的间隔，并通过学习合适的 $\mathrm{w^{\ast} }$ 与 $b^{\ast}$ 使得最小的间隔尽量大。
\[\sigma \triangleq\min_{i=1,\dots,n}\sigma_i\qquad [\mathrm{w^{\ast} }, b^{\ast}]=\arg \max \sigma\]向一般QP问题转化
直观的优化问题
\[\begin{align*} \max_{\sigma,\mathrm{w},b}\ \sigma \qquad & s.t.\ y_i(\mathrm{w}^Tx_i+b)\ge \sigma,\ \|\mathrm{w}\|=1, \quad i=1,\dots,n \end{align*}\]简化约束条件，令 $\hat \sigma=\sigma|\mathrm{w}|$，继续转化
\[\begin{align} \max_{\hat\sigma,\mathrm{w},b}\ \hat\sigma/\|\mathrm{w}\| \qquad s.t.\ y_i(\mathrm{w}^{\top}x_i+b)\ge \hat \sigma \quad i=1,\dots,n \end{align}\]考虑 $\mathrm{w}^{\top}x+b=0$，所以 $\mathrm{w}^{\top}x/{\hat\sigma}+b/{\hat\sigma}=0$，更新 $\mathrm{w}\gets \mathrm{w}^{\top}/{\hat\sigma}$，$b\gets b/{\hat\sigma}$ 令 $\hat \sigma=1$，继续简化
\[\begin{align*} \max_{\mathrm{w},b}\ 1/\|\mathrm{w}\| \qquad s.t.\ y_i(\mathrm{w}^{\top}x_i+b)\ge 1 \quad i=1,\dots,n \end{align*}\]转化为凸优化问题
\[\begin{align*} \min_{\mathrm{w},b}\ \frac 12 \|\mathrm{w}\|^2 \qquad s.t.\ y_i(\mathrm{w}^{\top}x_i+b)\ge 1 \quad i=1,\dots,n \end{align*}\]转为对偶问题
下面结合一般的凸优化问题说明这类问题的解决思路
\[\begin{align*} \min &\ f(\mathrm{w})\\ &s.t. \ h_i(\mathrm{w})=0,\ i=1,\dots,l\\ & \qquad g_i(\mathrm{w})\le 0,\ i=1,\dots,k \end{align*}\]定义增广拉格朗日函数
\[\mathcal{L}(\mathrm{w},\alpha,\beta)=f(\mathrm{w} )+\Sigma\alpha_ig_i(\mathrm{w})+\Sigma\beta_ih_i(\mathrm{w})\]为了解决这一优化问题，定义
\[\Theta_p(\mathrm{w}) \triangleq \max_{\alpha,\beta,\alpha_i\ge 0}\mathcal{L}(\mathrm{w},\alpha,\beta)= \begin{cases} f(\mathrm{w}) \ & 若 \mathrm{w} 满足约束，在可行区域\\\ +\infty \ & 其它情况，\mathrm{w} 不在可行区域 \end{cases}\]$p^{\ast}$ 表示这个这个目标函数的最优值
\[p^\ast=\min_\mathrm{w}\max_{\beta,\alpha_i\ge 0}\mathcal{L}(\mathrm{w},\alpha,\beta)\]看一下我们的新目标函数，先求最大值，再求最小值。这样的话，我们首先就要面对带有需要求解的参数 $\mathrm{w}$ 和 $b$ 的方程，而 $\alpha_i$ 又是不等式约束，这个求解过程不好做。所以，我们需要使用拉格朗日函数对偶性，将最小和最大的位置交换一下，这样就变成了：
\[d^\ast=\max_{\beta,\alpha_i\ge 0}\min_\mathrm{w}\mathcal{L}(\mathrm{w},\alpha,\beta)\]可知 $d^{\ast}\le p^{\ast}$，即对偶问题最优值 $d^{\ast}$ 是原始问题最优值 $p^{\ast}$ 的一个下界，在满足 KKT 条件下，二者是等价的。Slater 定理和 KKT 条件，如果 $f$ 和 $g_i$ 是凸的， $h_i$ 是仿射，假设 $g_i$ 是严格可解的，即 $\exists \ \mathrm{w}$ 使得 $g_i(\mathrm{w})<0\quad \forall i$，则存在 $\mathrm{w}^{\ast}, \alpha^{\ast}, \beta^{\ast}$ 使得 $\mathrm{w}^{\ast}$ 是原问题的解，$\alpha^{\ast}, \beta^{\ast}$ 是对偶问题的解。此外 $p^{\ast} = d^{\ast}=\mathcal{L}(\mathrm{w}^{\ast}, \alpha^{\ast}, \beta^{\ast})$，且 $\mathrm{w}^{\ast}, \alpha^{\ast}, \beta^{\ast}$ 满足 KKT 条件：
\[\begin{cases} \frac {\partial} {\partial \mathrm{w}_i} \mathcal{L} （\mathrm{w^{\ast}, \alpha^{\ast},\beta^{\ast} }）=0, \ i=1,\dots,n \\\ h_i(\mathrm{w})=0,\ i=1,\dots,l \\\ g_i(\mathrm{w}^{\ast})\le0 \quad i=1,\dots,k\\\ \alpha^{\ast}g_i(\mathrm{w}^{\ast})=0,\quad i=1,\dots,k \\\ \alpha_i\ge0 \quad i=1,\dots,k \end{cases}\]满足上述几条约束，就可以用对偶问题替代原始问题，并且对偶问题的解是原问题最优值得最好下界。这里是假设 $\mathrm{w}$、等式以及不等式的约束个数不一样，SVM 中是一样的。
回到 SVM 优化问题上
对于问题
\[\begin{align*} \min_{\mathrm{w},b}\ \frac 12 \|\mathrm{w}\|^2 \qquad s.t.\ y_i(\mathrm{w}^{\top}x_i+b)\ge 1 \quad i=1,\dots,n \end{align*}\]其拉格朗日函数为
\[L(\mathrm{w},b,\alpha)=\frac 1 2 \|\mathrm{w}\|^2-\sum_{i=1}^n\alpha_i(y_i(\mathrm{w}^{\top}x_i+b)-1)\]对偶问题
\[\max_{\alpha_i\ge 0} \min_{\mathrm{w},b}L(\mathrm{w},b,\alpha)\]令 $L(\mathrm{w},b,\alpha)$ 对 $\mathrm{w}$ 和 $b$ 的偏导为 0，可得
\[\mathrm{w}=\sum_{i=1}^n\alpha_iy_ix_i\\ \sum_{i=1}^n\alpha_iy_i=0\]将以上两个等式带入拉格朗日目标函数，消去 $\mathrm{w}$ 和 $b$ ，得
\[\min_{\mathrm{w},b}L(\mathrm{w},b,\alpha)=\sum_{i=1}^n\alpha_i-\frac 1 2\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_j(x_i^{\top}x_j)\]求 $\min_{\mathrm{w},b}L(\mathrm{w},b,\alpha)$ 对 $\alpha$ 的极大，即是对偶问题，继续调整为极小问题
\[\begin{align} \min_{\alpha}&\ \frac 1 2\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_j(x_i^{\top}x_j) - \sum_{i=1}^n\alpha_i\\ &\text{s.t.}\ \sum_{i=1}^n\alpha_iy_i=0,\ \alpha_i\ge0,\quad i=1,\dots,n \end{align}\]现在我们的优化问题变成了如上的形式，其可以使用序列最小优化（SMO）算法优化。我们通过这个优化算法能得到 $\alpha^{\ast}$ ，再根据 $\alpha^{\ast}$，我们就可以求解出 $\mathrm{w}^{\ast}$ 和 $b^{\ast}$，进而求得我们最初的目的：找到超平面，即”决策平面”。$\mathrm{w}^{\ast}$ 和 $b^{\ast}$ 的计算公式为
\[\mathrm{w}^{\ast}=\sum_{i=1}^n\alpha_i^{\ast}y_ix_i\\ b^{\ast}=y_j-\sum_{i=1}^n\alpha_i^{\ast}y_ix_i^{\top}x_j\]前面的推导都是假设满足 KKT 条件下成立的，在 $\alpha^{\ast}$ 中至少存在一个 $\alpha^{\ast}_j>0$，因为若全为 0，则 $\mathrm{w}^{\ast}=0$，矛盾。对于任意训练样本 $(x_i,y_i)$ ，总有 $\alpha_i^{\ast}=0$ 或者 $y_j(\mathrm{w}^{\top}x_j+b)=1$ 。若 $\alpha_i^{\ast}=0$，则该样本不会在最后求解模型参数的式子中出现。若 $\alpha_i^{\ast}>0$，则必有 $y_j(\mathrm{w}^{\top}x_j+b)=1$，所对应的样本点位于最大间隔边界上，是一个支持向量。这显示出支持向量机的一个重要性质：训练完成后，大部分的训练样本都不需要保留，最终模型仅与支持向量有关。
SVM 中的 SMO 方法
SVM 中的对偶问题为
\[\begin{align} \min_{\alpha}&\ \frac 1 2\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_j(x_i^{\top}x_j) - \sum_{i=1}^n\alpha_i\\ &\text{s.t.}\ \sum_{i=1}^n\alpha_iy_i=0,\ \alpha_i\ge0,\quad i=1,\dots,n \end{align}\]其为二次规划问题，可以使用通用的二次规划算法求解。但问题规模正比于样本数，因此开销相当大，需要引入 SMO (序列最小化优化) 算法。初始化参数 $\alpha^{\ast}$ 后，SMO 算法重复下面两个步骤直至收敛：
- 选取一对需要更新的变量 $\alpha^{\ast}_i$ 和 $\alpha^{\ast}_j$
- 固定 $\alpha^{\ast}_i$ 和 $\alpha^{\ast}_j$ 以外的参数，求解对偶问题式来更新 $\alpha^{\ast}_i$ 和 $\alpha^{\ast}_j$
选取 $\alpha^{\ast}_i$ 和 $\alpha^{\ast}_j$ 策略：只要选取的 $\alpha^{\ast}_i$ 和 $\alpha^{\ast}_j$ 中有一个不满足 KKT 条件，那么更新后目标函数的值就会增大，而且违背 KKT 条件的程度越大，更新后目标函数的增幅就会越大。因此，SMO 算法先选取一个违背 KKT 条件程度最大的变量 $\alpha^{\ast}_i$，然后再选一个使目标函数增长最快的变量 $\alpha^{\ast}_j$，使选取的两变量对应的样本之间间隔最大，使得目标函数有更大的变化，从而更快搜索到全局最大值。SMO 算法在每次迭代中，仅优化两个选定的参数，其他参数是固定的。此时，可将对偶问题式的约束重写为：
\[\alpha^{\ast}_iy_i + \alpha^{\ast}_jy_j = c,\quad \alpha^{\ast}_i \geq 0, \alpha^{\ast}_j \geq 0\]其中，$c = -\sum_{k \neq i,j} \alpha_k^{\ast} y_k$ 看作是固定的常数。利用上式，我们可以把 $\alpha_j^{\ast}$ 从对偶问题中消去，这样就得到了一个单变量二次规划问题，只需考虑 $\alpha_i^{\ast} \geq 0$ 这个约束。这样的问题具有闭式解，所以我们连数值优化方法都不需要了，可以直接算出 $\alpha_i^{\ast}$ 和 $\alpha_j^{\ast}$。使用 SMO 算法计算出最优解之后，用 $\mathrm{w}^{\ast} = \sum_{i=1}^m \alpha_i^{\ast} y_i x_i$ 获得 $\mathrm{w}^{\ast}$，而位移项 $b^{\ast}$ 则可以通过支持向量导出，因为对于任一支持向量 $(x_s, y_s)$，都有函数间隔等于 1，所以有：
\[y_sf(x) = y_s(\sum_{i \in S} \alpha^{\ast}_i y_i x_i^{\top} x_s + b^{\ast})= 1\]这里的 $S$ 是所有支持向量的下标集。理论上，我们只要选取任意一个支持向量代入上式就可以把 $b^{\ast}$ 算出来了。但实际任务中往往采用一种更鲁棒的做法：用所有支持向量求解的平均值。
\[b^{\ast} = \frac{1}{|S|} \sum_{s \in S} (\frac{1}{y_s} - \sum_{i \in S}\alpha^{\ast}_i y_i x_i^{\top} x_s)\]松弛变量的加入 (hinge损失)
在很多实际问题，由于存在各种噪音，所以现实生活中的分类可能并不能直接通过一个超平面将其完全分隔开来，即使能完全分隔，但得到的超平面也不一定是最佳的，因此引入了“软间隔”的概念，即允许某些点不满足约束。方式为引入 hinge 损失， $\text{hinge}(x_i) = \max (0,1-y_i(\mathrm{w}^{\top}x_i+b))$ ，如果点正确分类且在间隔之外，则损失为0；如果点正确分类且在间隔之内，则损失为 $1-y_i(\mathrm{w}^{\top}x_i+b)\in(0,1)$；如果点错误分类，则损失为 $1-y_i(\mathrm{w}^{\top}x_i+b)\in(1,+\infty)$，如下图
参考：Support Vector Machines for Credit Scoring。
原优化问题在软间隔加入下改为
\[\begin{align} \min_{\mathrm{w},b}&\ \frac 12 \|\mathrm{w}\|^2 + C\sum_{i=1}^n\xi_i\\ &s.t.\ y_i(\mathrm{w}^{\top}x_i+b)\ge 1-\xi_i,\ \xi_i\ge 0, \quad i=1,\dots,n\\ \end{align}\]其中 $\xi_i$ 为“松弛变量”，每一个样本都有一个对应的松弛变量，表征该样本不满足约束的程度。 $C>0$ 称为惩罚参数， $C$ 值越大，对分类的惩罚越大。跟线性可分求解的思路一致，同样这里先用拉格朗日乘子法得到拉格朗日函数，再求其对偶问题。其对偶问题为
\[\begin{align} \min_{\alpha}&\ \frac 1 2\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_j(x_i^{\top}x_j) - \sum_{i=1}^n\alpha_i\\ &\text{s.t.}\ \sum_{i=1}^n\alpha_iy_i=0,\ 0\le\alpha_i\le C ,\quad i=1,\dots,n \end{align}\]线性 SVM 总结
输入：训练数据集 ${ x_i,y_i }, \ i=1,\dots,n$, $x_i \in \mathbb{R}^d,\ y_i \in {-1,+1}$
输出：分离超平面和分类决策函数
1）选择惩罚参数 $C>0$，构造并求解凸二次规划问题
\[\begin{align} \min_{\alpha}&\ \frac 1 2\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_j(x_i^{\top}x_j) - \sum_{i=1}^n\alpha_i\\ &\text{s.t.}\ \sum_{i=1}^n\alpha_iy_i=0,\ 0\le\alpha_i\le C ,\quad i=1,\dots,n \end{align}\]得到最优解 $\alpha^{\ast}=(\alpha_1^{\ast},\alpha_2^{\ast},…,\alpha_n^{\ast})^{\top}$
2）计算
\[\mathrm{w}^{\ast}=\sum_{i=1}^n\alpha_i^{\ast}y_ix_i\]选择 $\alpha^{\ast}$ 的一个分量 $\alpha_j^{\ast}$ 满足条件 $0<\alpha_j^{\ast}<C$，计算
\[b^{\ast}=y_j-\sum_{i=1}^n\alpha_i^{\ast}y_ix_i^{\top}x_j\]3）求分离超平面
\[(\mathrm{w}^{\ast})^{\top}x_i+b^{\ast}=0\]分类决策函数：
\[f(x)=sign\left((\mathrm{w}^{\ast})^{\top}x_i+b^{\ast} \right)\]核函数的应用
对于输入空间中的非线性分类问题，可以通过非线性变换将它转化为某个维特征空间中的线性分类问题，在高维特征空间中学习线性支持向量机。由于在线性支持向量机学习的对偶问题里，目标函数和分类决策函数都只涉及实例和实例之间的内积，所以不需要显式地指定非线性变换，而是用核函数替换当中的内积。核函数表示，通过一个非线性转换后的两个实例间的内积。具体地， $K(x_i,x_j)$ 是一个函数，或正定核，意味着存在一个从输入空间到特征空间的映射 $\phi(x)$ ，对任意输入空间中的 $x_i,x_j$，有
\[K(x_i,x_j)=\phi(x_i)^{\top}\phi(x_i)\]注意：核函数和映射没有关系。核函数只是用来计算映射到高维空间之后的内积的一种简便方法，或者说 trick，可以简化二次规划中间的内积计算。也即中间步骤有一步必须求得 $\phi(x_i)^{\top}\phi(x_i)$，而我们可以定义核函数，使得我们在不需要显式计算每一个 $\phi(x_i)$、甚至不需要知道 $\phi(\cdot)$ 长什么样的情况下，直接求出 $\phi(x_i)^{\top}\phi(x_i)$ 的值来。
在线性支持向量机学习的对偶问题中，用核函数 $K(x,x_i)$ 替代内积，其对偶问题为
\[\begin{align} \min_{\alpha}&\ \frac 1 2\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_jK(x_i,x_j) - \sum_{i=1}^n\alpha_i\\ &\text{s.t.}\ \sum_{i=1}^n\alpha_iy_i=0,\ 0\le\alpha_i\le C ,\quad i=1,\dots,n \end{align}\]求解得到的就是非线性支持向量机
\[f(x)=sign\left(\sum_{i=1}^n\alpha_i^{\ast}y_iK(x,x_i) + b^{\ast} \right)\]非线性 SVM 总结
输入：训练数据集 ${ x_i,y_i }, \ i=1,\dots,n$, $x_i \in \mathbb{R}^d,\ y_i \in {-1,+1}$
输出：分离超平面和分类决策函数
1）选择惩罚参数 $C>0$，构造并求解凸二次规划问题
\[\begin{align} \min_{\alpha}&\ \frac 1 2\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_jK(x_i,x_j) - \sum_{i=1}^n\alpha_i\\ &\text{s.t.}\ \sum_{i=1}^n\alpha_iy_i=0,\ 0\le\alpha_i\le C ,\quad i=1,\dots,n \end{align}\]得到最优解 $\alpha^{\ast}=(\alpha_1^{\ast},\alpha_2^{\ast},…,\alpha_n^{\ast})^{\top}$
2）计算
\[\mathrm{w}^{\ast}=\sum_{i=1}^n\alpha_i^{\ast}y_ix_i\]选择 $\alpha^{\ast}$ 的一个分量 $\alpha_j^{\ast}$ 满足条件 $0<\alpha_j^{\ast}<C$，计算
\[b^{\ast}=y_j-\sum_{i=1}^n\alpha_i^{\ast}y_iK(x_i,x_j)\]3）分类决策函数：
\[f(x)=sign\left(\sum_{i=1}^n\alpha_i^{\ast}y_iK(x,x_i) + b^{\ast} \right)\]以常用的 RBF 核为例
\[K(x_1,x_2)=\exp \left(-\frac {\|x-z\|^2} {2\sigma^2}\right)\]对应的 SVM 是高斯径向基函数分类器，在此情况下，分类决策函数为
\[f(x)=sign\left(\sum_{i=1}^n\alpha_i^{\ast}y_i\exp \left(-\frac {\|x-z\|^2} {2\sigma^2}\right) + b^{\ast} \right)\]SVM 的现代优化方法
用于找到 SVM 分类器的最近的算法包括次梯度下降和坐标下降。当处理大的稀疏数据集时，这两种技术已经被证明有着显著的优点—当存在许多训练实例时次梯度法是特别有效的，并且当特征空间的维度高时，坐标下降特别有效。
SVM的次梯度下降算法直接用表达式
\[f(\mathrm{}w,b)=\left[\frac 1 n \sum_{i=1}^n\max(0,1-y_i(\mathrm{w^{\top}x_i+b}))\right]+\lambda\|w\|^2\]注意 $f$ 是 $\mathrm{w}$ 与 $b$ 的凸函数。用传统的梯度下降（或 SGD）方法，其中不是在函数梯度的方向上前进，而是在从函数的次梯度中选出的向量的方向上前进。该方法的优点在于，对于某些实现，迭代次数不随着数据点的数量 $n$ 而增加或减少。
参考：