【作者主页】Francek Chen
【专栏介绍】$\lceil$Python机器学习$\rfloor$ 机器学习是一门人工智能的分支学科，通过算法和模型让计算机从数据中学习，进行模型训练和优化，做出预测、分类和决策支持。Python成为机器学习的首选语言，依赖于强大的开源库如Scikit-learn、TensorFlow和PyTorch。本专栏介绍机器学习的相关算法以及基于Python的算法实现。
【GitCode】专栏资源保存在我的GitCode仓库：https://gitcode.com/Morse_Chen/Python_machine_learning。

---

  本文我们介绍非参数化模型。与参数化模型不同，非参数化模型对数据分布不做先验的假设，从而能够更灵活地适配到不同的数据分布上。但另一方面，灵活性也使其对数据更为敏感，容易出现过拟合现象。本文主要介绍一个经典的非参数化模型：支持向量机（support vector machine，SVM），以及其求解算法——序列最小优化（sequential minimal optimization，SMO）算法，并利用其完成平面点集的二分类任务。

  由于非参数化模型与数据集大小有关，我们假设数据集 $\mathcal{D}=\{({\mathbf{x}}_1,y_1),({\mathbf{x}}_2,y_2),\cdots ,({\mathbf{x}}_m,y_m)\}$，其中 ${\mathbf{x}}_i\in {\mathbb{R}}^n$ 是输入向量， y i ∈ { − 1 , 1 } y_i\in \{-1,1\} yi​∈{−1,1} 是输入数据的分类。为了下面理论推导方便，这里我们用-1代替0作为类别标签。线性的SVM假设数据集中的点是线性可分的。需要注意，该假设与SVM是非参数化模型并不矛盾，因为SVM仍然需要与数据集大小相匹配的参数量来求解分隔平面，具体的求解流程我们会在下文详细说明。与之相反，逻辑斯谛回归作为参数化模型，其参数$\mathbf{\theta }$的维度只和输入向量的维度$n$有关。

  通常来说，即使数据集$\mathcal{D}$是线性可分的，可以将其分开的超平面也有无数种选择。如图1所示，任意一条绿色或红色的直线都可以将平面上的橙色点和蓝色点分开。然而，如果我们考虑到现实场景中可能的噪声和扰动，这些分隔线就会产生区别。假如下图中的数据点实际所处的位置可能在它们旁边标出的虚线圆圈内的任意一处，那么图中的两条红色虚线就有可能给出错误的分类结果。因此，为了使分隔直线对数据点的扰动或噪声的鲁棒性更强，我们希望从这无数个可以分隔两个点集的超平面中，挑选出与任意一点间隔（margin）的最小值最大的平面。

图1 用直线分隔带噪声的点集

一、支持向量机的数学描述

  我们首先来考虑如何计算样本点与平面的间隔。如图2所示，设决策边界给出的超平面方程为 ${\mathbf{w}}^{\mathrm{T}}\mathbf{x}+b=0$，其中 $\mathbf{w}\in {\mathbb{R}}^n$ 和 $b\in \mathbb{R}$ 为支持向量机的参数，$\mathbf{w}$方向就是该平面的法线方向。设样本${\mathbf{x}}_i$到平面的距离是${\gamma }_i$，那么从${\mathbf{x}}_i$出发，沿着法线方向经过长度${\gamma }_i$，应当正好到达平面上。因此，${\gamma }_i$满足$${\mathbf{w}}^{\mathrm{T}}\left({\mathbf{x}}_i-{\gamma }_i\frac{\mathbf{w}}{\Vert \mathbf{w}\Vert }\right)+b=0$$或$${\mathbf{w}}^{\mathrm{T}}\left({\mathbf{x}}_i+{\gamma }_i\frac{\mathbf{w}}{\Vert \mathbf{w}\Vert }\right)+b=0$$ 出现两个不同的方程是因为我们还没有确定是在法线的方向还是法线的反方向。如果${\mathbf{x}}_i$在法线方向，那么有 ${\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b>0$，反之则是 ${\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b<0$。因此，不妨规定使 ${\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b>0$ 的样本点的类别标签 $y_i=1$，使 ${\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b<0$ 的样本点的类别标签 $y_i=-1$。对于分类问题，标签的具体值我们可以任意替换，只要最终能对应回原始类别即可。另外，我们设使 ${\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b=0$ 的点的类别标签 $y_i=0$，因为这些点正好处于该超平面上，从而 $y_i=0$ 表示超平面无法对其进行分类。这样，我们就可以把上面两个方程统一起来，写成$${\mathbf{w}}^{\mathrm{T}}\left({\mathbf{x}}_i-{\gamma }_i{y}_i\frac{\mathbf{w}}{\Vert \mathbf{w}\Vert }\right)+b=0$$或者等价变形为$${\gamma }_i=\frac{y_i({\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b)}{\Vert \mathbf{w}\Vert }=y_i\left(\frac{{\mathbf{w}}^{\mathrm{T}}}{\Vert \mathbf{w}\Vert }\mathbf{x}+\frac{b}{\Vert \mathbf{w}\Vert }\right)$$

图2 二维空间下的分类决策边界和几何间隔

  对上式来说，当$\mathbf{w}$和$b$的大小同时变为$\lambda$倍时，式中的分母$\Vert \mathbf{w}\Vert$也变为$\lambda$倍，这时划分超平面完全不变。因此，我们不妨设 ${\hat{\gamma }}_i=y_i({\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b)$，称为函数间隔（functional margin），而将几何间隔（geometric margin）${\gamma }_i={\hat{\gamma }}_i/\Vert \mathbf{w}\Vert$ 看作函数间隔对$\mathbf{w}$的长度归一化的结果。

  我们希望所有样本到平面的几何间隔${\gamma }_i$的最小值最大。设 $\gamma ={\min }_i{\gamma }_i$，$\hat{\gamma }={\min }_i{\hat{\gamma }}_i$，那么 $\gamma =\hat{\gamma }/\Vert \mathbf{w}\Vert$。于是，支持向量机的优化目标可以写为
$$\begin{array}{rl}& \underset{\hat{\gamma },\mathbf{w},b}{\max }\frac{\hat{\gamma }}{\Vert \mathbf{w}\Vert }\\ & \text{s.t.}{y}_i({\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b)\ge \hat{\gamma },i=1,\cdots ,m\end{array}$$ 上面已经提到，函数间隔$\hat{\gamma }$关于$\mathbf{w}$和$b$的大小并不影响实际的几何间隔$\gamma$，因为其变化总会被$\Vert \mathbf{w}\Vert$所抵消。因此，不妨令 $\hat{\gamma }=1$。这样上面的优化目标就变为
$$\begin{array}{rl}& \underset{\mathbf{w},b}{\max }\frac{1}{\Vert \mathbf{w}\Vert }\\ & \text{s.t.}{y}_i({\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b)\ge 1,i=1,\cdots ,m\end{array}$$ 然而，优化目标$\begin{array}{r}\frac{1}{\Vert \mathbf{w}\Vert }\end{array}$是非凸的，其求解较为困难。考虑到函数$\begin{array}{r}\frac{1}{t}\end{array}$关于$t$单调递减，最大化$\begin{array}{r}\frac{1}{t}\end{array}$与最小化$t$的任意一个单调递增函数都等价。为了求解方便，我们选择凸的单调递增函数，进一步将优化目标等价地写为
$$\begin{array}{rl}& \underset{\mathbf{w},b}{\min }\frac{1}{2}\Vert \mathbf{w}{\Vert }^2\\ & \text{s.t.}{y}_i({\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b)\ge 1,i=1,\cdots ,m\end{array}$$ 由于 $\Vert \mathbf{w}\Vert \ge 0$，其二次函数在定义域内是单调递增的，并且为凸函数。其中，系数选择$\begin{array}{r}\frac{1}{2}\end{array}$是为了后续求导简洁，与MSE中的作用类似。

  至此，我们讨论了数据线性可分的情况。如果数据线性不可分，我们可以适当放低上面的约束要求，引入松弛变量${\xi }_i$，将约束问题改写为
$$\begin{array}{rl}& \underset{\mathbf{w},b,{\xi }_i}{\min }\frac{1}{2}\Vert \mathbf{w}{\Vert }^2+C\sum _{i=1}^m{\xi }_i\\ & \text{s.t.}{y}_i({\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b)\ge 1-{\xi }_i\\ & {\xi }_i\ge 0,i=1,\cdots ,m\end{array}$$

  可以看出，松弛变量允许某个样本点的类别与超平面给出的分类不同。但是，对这些分类错误的样本点，我们也需要进行惩罚。因此，我们在优化的目标函数上加入${\xi }_i$值本身作为惩罚项，其中$C$是惩罚系数。

  对于带约束的凸优化问题，数学上有一套成熟的解决方式，将其转化为更容易的对偶问题求解。我们将较为繁琐的数学推导放在本文的拓展阅读中，感兴趣的可以自行学习，这里我们直接给出结论。求解上面的优化问题等价于求解下面的二次规划：
$$\begin{array}{rl}& \underset{\mathbf{\alpha }}{\max }W(\mathbf{\alpha })=\underset{\mathbf{\alpha }}{\max }\left(\sum _{i=1}^m{\alpha }_i-\frac{1}{2}\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i{\alpha }_j{y}_i{y}_j{\mathbf{x}}_i^{\mathrm{T}}{\mathbf{x}}_j\right)\\ & \text{s.t.}0\le {\alpha }_i\le C,i=1,\cdots ,m\\ & \sum _{i=1}^m{\alpha }_i{y}_i=0\end{array}$$ 其中，$\mathbf{\alpha }$是待求解的参数。这时可以看出，SVM问题的参数量是与数据集的规模$m$相当的。当数据集规模增大时，其参数量也相应变多，表现出非参数化模型的特性。

  当解出最优的${\mathbf{\alpha }}^{\ast }$后，SVM的参数${\mathbf{w}}^{\ast }$和$b^{\ast }$可以由下式计算得到
$$\begin{gathered} {\mathbf{w}}^{\ast }=\sum _{i=1}^m{\alpha }_i^{\ast }{y}_i{\mathbf{x}}_i \\ {b}^{\ast }=-\frac{1}{2}(\underset{i,y_i=-1}{\max }{\mathbf{w}}^{\ast \mathrm{T}}{\mathbf{x}}_i+\underset{i,y_i=1}{\min }{\mathbf{w}}^{\ast \mathrm{T}}{\mathbf{x}}_i) \end{gathered}$$ 并且，这组最优参数$({\mathbf{w}}^{\ast },b^{\ast },{\mathbf{\alpha }}^{\ast })$满足 ${\alpha }_i^{\ast }(1-y_i({\mathbf{w}}^{\ast \mathrm{T}}{\mathbf{x}}_i+b^{\ast }))=0$。因此对于数据集中的任意一个样本${\mathbf{x}}_i$来说，要么其对应的参数 ${\alpha }_i^{\ast }=0$，要么其与支持向量机对应的超平面 ${\mathbf{w}}^{\ast \mathrm{T}}\mathbf{x}+b^{\ast }=0$ 的函数间隔 $y_i({\mathbf{w}}^{\ast \mathrm{T}}{\mathbf{x}}_i+b)=1=\hat{\gamma }$，从而${\mathbf{x}}_i$是所有样本中与该超平面间隔最小的。我们称这些与超平面间隔最小的向量${\mathbf{x}}_i$称为支持向量（supporting vector）。引入松弛变量后，对于那些类别与SVM的超平面相反的向量，由于其 ${\alpha }_i^{\ast }\ne 0$，会影响SVM的参数，因此这些向量也属于支持向量。

  设支持向量的集合为 S = { x i ∣ ( x i , y i ) ∈ D , y i ( w ∗ T x i + b ∗ ) = 1 } \mathcal S=\{\boldsymbol x_i|(\boldsymbol x_i,y_i)\in \mathcal D,y_i(\boldsymbol w^{*\mathrm T}\boldsymbol x_i+b^*)=1\} S={xi​∣(xi​,yi​)∈D,yi​(w∗Txi​+b∗)=1}，那么上面所有关于${\alpha }_i^{\ast }$的求和只需要在集合$\mathcal{S}$中进行，因为其余非支持向量对应的${\alpha }_i^{\ast }$都为零，对求和没有贡献。进一步，当我们需要用支持向量机预测某个新样本$\mathbf{x}$的类别时，需要计算 ${\mathbf{w}}^{\ast \mathrm{T}}\mathbf{x}+b^{\ast }$ 的正负性，即计算$${\mathbf{w}}^{\ast \mathrm{T}}\mathbf{x}+b^{\ast }={\left(\sum _{i=1}^m{\alpha }_i^{\ast }{y}_i{\mathbf{x}}_i\right)}^{\mathrm{T}}\mathbf{x}+b^{\ast }=\sum _{i=1,{\mathbf{x}}_i\in \mathcal{S}}^m{\alpha }_i^{\ast }{y}_i{\mathbf{x}}_i^{\mathrm{T}}\mathbf{x}+b^{\ast }$$

  这样，用SVM进行预测的时间复杂度从$O(m)$变为了$O(|\mathcal{S}|)$。通常情况下支持向量只占数据集的很小一部分，因此，利用支持向量的特性，SVM模型建立完成后，再进行预测的时间复杂度就大大减小了。这一优势在线性SVM中并不明显，因为我们可以直接计算出${\mathbf{w}}^{\ast }$的值，但是对于后面会介绍的带有非线性核函数的SVM来说，其优化是相当可观的。

  现在，我们只需要从上面的二次规划问题中解出${\mathbf{\alpha }}^{\ast }$。然而，传统的求解二次规划问题的算法时间开销都非常大。因此，我们通常使用专门针对SVM的问题形式所设计的序列最小优化（SMO）算法来求解SVM的优化问题。

二、序列最小优化

  序列最小优化的核心思想是，同时优化所有的参数${\alpha }_i$较为困难，因此每次可以选择部分参数来优化。由于优化问题中有等式约束 $\sum _{i=1}^m={\alpha }_i{y}_i=0$，我们每次选取两个不同的参数${\alpha }_i$和${\alpha }_j$，而固定其他的参数，只优化这两个参数从而保证等式约束一直成立。完成后，再选取另两个参数，固定其他个 $m-2$ 参数，进行优化。如此反复迭代，直到目标函数的值收敛位置。无论目标是需要被最大化还是最小化，SMO算法都可以工作。下面，我们以固定${\alpha }_1$和${\alpha }_2$为例，演示SMO算法的流程。

  固定${\alpha }_1$与${\alpha }_2$后，优化问题的目标为
$$\begin{array}{rl}\underset{{\alpha }_1,{\alpha }_2}{\max }{W}_{1,2}({\alpha }_1,{\alpha }_2)=& \underset{{\alpha }_1,{\alpha }_2}{\max }({\alpha }_1+{\alpha }_2-\frac{1}{2}\Vert {\alpha }_1{y}_1{\mathbf{x}}_1+{\alpha }_2{y}_2{\mathbf{x}}_2{\Vert }^2\\ & -({\alpha }_1{y}_1{\mathbf{x}}_1+{\alpha }_2{y}_2{\mathbf{x}}_2{)}^{\mathrm{T}}\left(\sum _{i=3}^m{\alpha }_i{y}_i{\mathbf{x}}_i\right)+A_0)\\ \text{s.t.}0\le {\alpha }_1,{\alpha }_2\le & C\\ {\alpha }_1{y}_1+{\alpha }_2{y}_2& =-\sum _{i=3}^m{\alpha }_1{y}_i\end{array}$$ 其中，$A_0$是与${\alpha }_1$和${\alpha }_2$无关的常数。注意到上式中样本向量不会单独出现，而都以两个样本做内积的形式出现。回忆线性回归中的核技巧，我们将样本向量之间的内积记为矩阵 $\mathbf{K}=\mathbf{X}{\mathbf{X}}^{\mathrm{T}}$，其中$\mathbf{X}$的行向量${\mathbf{x}}_i$是数据集中的样本，根据矩阵乘法的规则和向量内积的对称性可知 $K_{ij}=K_{ji}={\mathbf{x}}_i^{\mathrm{T}}{\mathbf{x}}_j$。注意， y i ∈ { − 1 , 1 } ⇒ y i 2 = 1 y_i\in \{-1,1\}\Rightarrow y_i^2=1 yi​∈{−1,1}⇒yi2​=1，目标函数$W_{1,2}({\alpha }_1,{\alpha }_2)$可以用$\mathbf{K}$改写为
$$\begin{array}{rl}{W}_{1,2}({\alpha }_1,{\alpha }_2)=& {\alpha }_1+{\alpha }_2-\frac{1}{2}(K_{11}{\alpha }_1^2+K_{22}{\alpha }_2^2)-y_1{y}_2{K}_{12}{\alpha }_1{\alpha }_2\\ & -y_1{\alpha }_1\sum _{i=3}^m{\alpha }_i{y}_i{K}_{1i}-y_2{\alpha }_2\sum _{i=3}^m{\alpha }_i{y}_i{K}_{2i}+A_0\end{array}$$

  上述第二个约束条件表明，${\alpha }_1$与${\alpha }_2$不是独立的，我们可以将${\alpha }_2$用${\alpha }_1$表示。记 $\zeta =-\sum _{i=3}^m{\alpha }_i{y}_i$，则有
$$\begin{array}{rlrl}& & & {\alpha }_1{y}_1+{\alpha }_2{y}_2=\zeta \\ \Rightarrow & & & {\alpha }_2=-{\alpha }_1\frac{y_1}{y_2}+\frac{\zeta }{y_2}\\ \Rightarrow & & & {\alpha }_2=(-y_1{\alpha }_1+\zeta )y_2\end{array}$$

  将上式代入优化目标，消去${\alpha }_2$，可得
$$\begin{array}{rl}{W}_{1,2}({\alpha }_1,{\alpha }_2)& =W_1({\alpha }_1)\\ & =(1-y_1{y}_2){\alpha }_1-\frac{1}{2}{K}_{11}{\alpha }_1^2-\frac{1}{2}{K}_{22}(\zeta -y_1{\alpha }_1)-y_1{K}_{12}(\zeta -y_1{\alpha }_1){\alpha }_1\\ & -y_1{\alpha }_1\sum _{i=3}^m{y}_i{\alpha }_i{K}_{1i}+y_1{\alpha }_1\sum _{i=3}^m{y}_i{\alpha }_i{K}_{2i}+A_1\\ & =-\frac{1}{2}(K_{11}+K_{22}-2K_{12}){\alpha }_1^2+\left[y_1-y_2+(K_{22}-K_{12})\zeta +\sum _{i=3}^m{y}_i{\alpha }_i(K_{2i}-K_{1i})\right]y_1{\alpha }_1+A_1\\ & =p{\alpha }_1^2+q{\alpha }_1+A_1\end{array}$$ 其中，$p$、$q$和$A_1$是与${\alpha }_1$无关的常数，且$$p=-\frac{1}{2}(K_{11}+K_{22}-2K_{12})=-\frac{1}{2}({\mathbf{x}}_1^{\mathrm{T}}{\mathbf{x}}_1+{\mathbf{x}}_2^{\mathrm{T}}{\mathbf{x}}_2-2{\mathbf{x}}_1^{\mathrm{T}}{\mathbf{x}}_2)=-\frac{1}{2}\Vert {\mathbf{x}}_1-{\mathbf{x}}_2{\Vert }^2\le 0$$

  如果数据集中没有相同的样本，那么严格有 $p<0$。因此，该优化问题本质上是寻找参数${\alpha }_1$的二次函数的最大值点，非常容易计算。注意参数${\alpha }_1$的取值范围是$[0,C]$，使其二次函数取最大值${\alpha }_1$的有3种情况：
$$\arg \underset{{\alpha }_1}{\max }W({\alpha }_1)=\{\begin{array}{rlrl}& 0,& & -\frac{q}{2p}<0\\ & -\frac{q}{2p},& & 0\le -\frac{q}{2p}\le C\\ & C,& & -\frac{q}{2p}>C\end{array}$$ 其对应的大致图像如图3所示。

图3 SMO最优解示意图

  解出${\alpha }_1$的最优值${\alpha }_1^{\prime }$后，就得到${\alpha }_2$的最优值 ${\alpha }_2^{\prime }=-y_1{y}_2{\alpha }_1^{\prime }+\zeta y_2$。我们还需要保证${\alpha }_2^{\prime }$也在$[0,C]$范围内，因此在计算${\alpha }_2^{\prime }$之前，再用 $0\le -y_1{y}_2{\alpha }_1^{\prime }+\zeta y_2\le C$ 这一条件对${\alpha }_1^{\prime }$进行裁剪。

  为了代码实现方便，我们进一步化简$\begin{array}{r}-\frac{q}{2p}\end{array}$。设 $g(\mathbf{x})=\sum _{i=1}^m{y}_i{\alpha }_i{\mathbf{x}}_i^{\mathrm{T}}\mathbf{x}+b$，则$$g({\mathbf{x}}_1)=\sum _{i=1}^m{y}_i{\alpha }_i{K}_{1i}+b,g({\mathbf{x}}_2)=\sum _{i=1}^m{y}_i{\alpha }_i{K}_{2i}+b$$

  将$g({\mathbf{x}}_1)$、$g({\mathbf{x}}_2)$与 $\zeta =y_1{\alpha }_1+y_2{\alpha }_2$ 代入$q$的表达式，得到
$$\begin{array}{rl}q& =\left[y_1-y_2+(K_{22}-K_{12})\zeta +\sum _{i=3}^m{y}_i{\alpha }_i(K_{2i}-K_{1i})\right]y_1\\ & =[y_1-y_2+(K_{22}-K_{12})(y_1{\alpha }_1+y_2{\alpha }_2)\\ & +(g({\mathbf{x}}_2)-y_1{\alpha }_1{K}_{12}-y_2{\alpha }_2{K}_{22}-b)-(g({\mathbf{x}}_1)-y_1{\alpha }_1{K}_{11}-y_2{\alpha }_2{K}_{12}-b)]y_1\\ & =(K_{11}+K_{22}-2K_{12}){\alpha }_1+[g({\mathbf{x}}_2)-y_2-g({\mathbf{x}}_1)+y_1]y_1\end{array}$$ 于是可得$$\arg \underset{{\alpha }_1}{\max }{W}_1({\alpha }_1)=-\frac{q}{2p}={\alpha }_1+\frac{[g({\mathbf{x}}_2)-y_2]-[g({\mathbf{x}}_1)-y_1]}{K_{11}+K_{22}-2K_{12}}{y}_1$$ 这一形式更加简洁和对称。

  在计算出${\alpha }_1^{\prime }$和${\alpha }_2^{\prime }$之后，阈值$b$同样需要更新，以保证通过对偶问题推导出的SVM优化问题成立。下面我们粗略解释其原因，感兴趣的话也可以参考本文的拓展阅读，详细了解为何要进行这样的保证。简单来说，样本对应的系数$\alpha$反映了样本的分类性质。$\alpha =0$ 说明样本被正确分类，$\alpha =C$ 说明样本被错误分类，这两种情况下$\alpha$都取边界值，样本不是支持向量。反之，$\alpha \in (0,C)$ 时，其对应的样本必定是支持向量。这也反映出，SVM的分类边界完全是由支持向量所决定的。回到SMO中，当 $0<{\alpha }_1^{\prime }<C$ 时，其对应的样本${\mathbf{x}}_1$必定是支持向量，因此我们需要保证更新过参数的SVM一定会将${\mathbf{x}}_1$分类为$y_1$。设新的阈值为$b_1$，将$({\mathbf{x}}_1,y_1)$代入SVM的分类表达式可得：
$$\begin{array}{rlrl}& & y_1& =y_1{\alpha }_1^{\prime }{K}_{11}+y_2{\alpha }_2^{\prime }{K}_{12}+\sum _{i=3}^m{y}_i{\alpha }_i{K}_{1i}+b_1\\ & & & =y_1({\alpha }_1^{\prime }-{\alpha }_1)K_{11}+y_2({\alpha }_2^{\prime }-{\alpha }_2)K_{12}-b+b_1+g({\mathbf{x}}_1)\\ \Rightarrow & & b_1& =b-g({\mathbf{x}}_1)+y_1-y_1({\alpha }_1^{\prime }-{\alpha }_1)K_{11}-y_2({\alpha }_2^{\prime }-{\alpha }_2)K_{12}\end{array}$$ 同理，当 $0<{\alpha }_2^{\prime }<C$ 时，下面的阈值$b_2$可以保证SVM将${\mathbf{x}}_2$分类为$y_2$：$$b_2=b-g({\mathbf{x}}_2)+y_2-y_2({\alpha }_2^{\prime }-{\alpha }_2)K_{22}-y_1({\alpha }_1^{\prime }-{\alpha }_1)K_{12}$$

  而如果${\alpha }_1^{\prime }$和${\alpha }_2^{\prime }$都在$(0,C)$范围内，说明两个样本都是支持向量，此时上面两种方法算出的$b_1$和$b_2$是相等的。与此相对，如果${\alpha }_1^{\prime }$和${\alpha }_2^{\prime }$都取边界值$0$或者$C$，说明两个样本都不是支持向量，对$b$的条件也就可以放宽，$b_1$与$b_2$之间的任何值都满足对偶问题成立的条件。此时我们通常取 $b=(b_1+b_2)/2$ 为两种极端情况的平均值。

  最后，我们将更新后的${\alpha }_1^{\prime }$和${\alpha }_2^{\prime }$代回原目标函数，得到 $W(\mathbf{\alpha })=W({\alpha }_1^{\prime },{\alpha }_2^{\prime },{\alpha }_3,\cdots ,{\alpha }_m)$。接下来，我们再随机选取一对参数，例如${\alpha }_3$和${\alpha }_4$，固定其他参数，用相同的方式求解新的目标函数$W_{3,4}({\alpha }_3,{\alpha }_4)$。注意此时参数${\alpha }_1$和${\alpha }_2$的值已经更新为刚刚解出的最优值${\alpha }_1^{\prime }$和${\alpha }_2^{\prime }$。这样反复迭代下去，直到更新参数时，$W(\mathbf{\alpha })$的变化量小于某个预设的精度常数$\delta$，或迭代次数达到预设的最大轮数为止。由于计算$W(\mathbf{\alpha })$的时间复杂度较高，实践中通常采用后者。

三、动手实现SMO求解SVM

  下面，我们按照上节讲述的步骤来动手实现SMO算法求解SVM。我们先考虑最简单的线性可分的情况，本节的数据集linear.csv包含了一些平面上的点及其分类。数据文件的每一行有3个数，依次是点的横坐标$x_1$、纵坐标$x_2$和类别 y ∈ { − 1 , 1 } y\in\{-1,1\} y∈{−1,1}。由于数据集非常简单，明显线性可分，SVM应当能达到100%的正确率，因此我们不再划分训练集和测试集，只以此为例讲解代码实现。

import numpy as np
import matplotlib.pyplot as plt
from matplotlib.colors import ListedColormap
from tqdm import tqdm, trangedata = np.loadtxt('linear.csv', delimiter=',')
print('数据集大小：', len(data))
x = data[:, :2]
y = data[:, 2]# 数据集可视化
plt.figure()
plt.scatter(x[y == -1, 0], x[y == -1, 1], color='red', label='y=-1')
plt.scatter(x[y == 1, 0], x[y == 1, 1], color='blue', marker='x', label='y=1')
plt.xlabel(r'$x_1$')
plt.ylabel(r'$x_2$')
plt.legend()
plt.show()

  下面我们来实现SVM的主要部分SMO算法，具体的讲解放在代码注释中。

def SMO(x, y, ker, C, max_iter):'''SMO算法x，y：样本的值和类别ker：核函数，与线性回归中核函数的含义相同C：惩罚系数max_iter：最大迭代次数'''# 初始化参数m = x.shape[0]alpha = np.zeros(m)# 预先计算所有向量的两两内积，减少重复计算K = np.zeros((m, m))for i in range(m):for j in range(m):K[i, j] = ker(x[i], x[j])for l in trange(max_iter):# 开始迭代for i in range(m):# 有m个参数，每一轮迭代中依次更新# 固定参数alpha_i与另一个随机参数alpha_j，并且保证i与j不相等j = np.random.choice([l for l in range(m) if l != i])# 用-b/2a更新alpha_i的值eta = K[j, j] + K[i, i] - 2 * K[i, j] # 分母e_i = np.sum(y * alpha * K[:, i]) - y[i] # 分子e_j = np.sum(y * alpha * K[:, j]) - y[j]alpha_i = alpha[i] + y[i] * (e_j - e_i) / (eta + 1e-5) # 防止除以0zeta = alpha[i] * y[i] + alpha[j] * y[j]# 将alpha_i和对应的alpha_j保持在[0,C]区间# 0 <= (zeta - y_j * alpha_j) / y_i <= Cif y[i] == y[j]:lower = max(0, zeta / y[i] - C)upper = min(C, zeta / y[i])else:lower = max(0, zeta / y[i])upper = min(C, zeta / y[i] + C)alpha_i = np.clip(alpha_i, lower, upper)alpha_j = (zeta - y[i] * alpha_i) / y[j]# 更新参数alpha[i], alpha[j] = alpha_i, alpha_jreturn alpha

  利用SMO算法解出$\mathbf{\alpha }$后，我们可以得到SVM的参数$\mathbf{w}$和$b$。我们把该算法应用在导入的线性数据集上，绘制出SVM给出的分隔直线，并标记出支持向量。

# 设置超参数
C = 1e8 # 由于数据集完全线性可分，我们不引入松弛变量
max_iter = 1000
np.random.seed(0)alpha = SMO(x, y, ker=np.inner, C=C, max_iter=max_iter)

# 用alpha计算w，b和支持向量
sup_idx = alpha > 1e-5 # 支持向量的系数不为零
print('支持向量个数：', np.sum(sup_idx))
w = np.sum((alpha[sup_idx] * y[sup_idx]).reshape(-1, 1) * x[sup_idx], axis=0)
wx = x @ w.reshape(-1, 1)
b = -0.5 * (np.max(wx[y == -1]) + np.min(wx[y == 1]))
print('参数：', w, b)# 绘图
X = np.linspace(np.min(x[:, 0]), np.max(x[:, 0]), 100)
Y = -(w[0] * X + b) / (w[1] + 1e-5)
plt.figure()
plt.scatter(x[y == -1, 0], x[y == -1, 1], color='red', label='y=-1')
plt.scatter(x[y == 1, 0], x[y == 1, 1], marker='x', color='blue', label='y=1')
plt.plot(X, Y, color='black')
# 用圆圈标记出支持向量
plt.scatter(x[sup_idx, 0], x[sup_idx, 1], marker='o', color='none', edgecolor='purple', s=150, label='support vectors')
plt.xlabel(r'$x_1$')
plt.ylabel(r'$x_2$')
plt.legend()
plt.show()

思考：对于同一个数据集，逻辑斯谛回归和支持向量机给出的分隔平面一样吗？用本节的linear.csv数据集验证你的想法。

from sklearn.linear_model import LogisticRegression# 创建并拟合模型
log_reg = LogisticRegression(max_iter=10000)
log_reg.fit(x, y)# 提取模型参数
w_log_reg = log_reg.coef_[0]
b_log_reg = log_reg.intercept_# 计算决策边界
Y_log_reg = -(w_log_reg[0] * X + b_log_reg) / (w_log_reg[1] + 1e-5)# 可视化
plt.figure()
plt.scatter(x[y == -1, 0], x[y == -1, 1], color='red', label='y=-1')
plt.scatter(x[y == 1, 0], x[y == 1, 1], marker='x', color='blue', label='y=1')
plt.plot(X, Y_log_reg, color='green', label='Logistic Regression')
plt.xlabel(r'$x_1$')
plt.ylabel(r'$x_2$')
plt.legend()
plt.show()

四、核函数

  对于略微有些线性不可分的数据，我们采用松弛变量的方法，仍然可以导出SVM的分隔超平面。然而，当数据的分布更加偏离线性时，可能完全无法用线性的超平面进行有效分类，松弛变量也就失效了。为了更清晰地展示非线性的情况，我们读入双螺旋数据集spiral.csv并绘制数据分布。该数据集包含了在平面上呈螺旋分布的两组点，同类的点处在同一条旋臂上。

data = np.loadtxt('spiral.csv', delimiter=',')
print('数据集大小：', len(data))
x = data[:, :2]
y = data[:, 2]# 数据集可视化
plt.figure()
plt.scatter(x[y == -1, 0], x[y == -1, 1], color='red', label='y=-1')
plt.scatter(x[y == 1, 0], x[y == 1, 1], marker='x', color='blue', label='y=1')
plt.xlabel(r'$x_1$')
plt.ylabel(r'$x_2$')
plt.legend()
plt.axis('square')
plt.show()

  显然，平面上任意一条直线都无法为上图的双螺旋数据集给出分类。因此，我们需要引入非线性的特征映射。将在神经网络与多层感知机一文中提到，非线性函数可以使数据升维，将在低维中线性不可分的数据映射到高维空间，使其变得线性可分。设映射函数为 $\varphi (\mathbf{x}):{\mathbb{R}}^n\to {\mathbb{R}}^N$。将线性SVM中的${\mathbf{x}}_i$全部替换为$\varphi ({\mathbf{x}}_i)$，并进行相同的数学推导，可以得到对偶问题的优化目标函数为$$W(\mathbf{\alpha })=\sum _{i=1}^m{\alpha }_i-\frac{1}{2}\sum _{i=1}^m\sum _{j=1}^m{y}_i{y}_j{\alpha }_i{\alpha }_j\varphi ({\mathbf{x}}_i{)}^{\mathrm{T}}\varphi ({\mathbf{x}}_j)$$

  为了简化上式，我们利用核技巧，定义核函数 $K(\mathbf{x},\mathbf{y})=\varphi (\mathbf{x}{)}^{\mathrm{T}}\varphi (\mathbf{y})$。【机器学习的基本思想】模型优化与评估 中我们曾介绍过，引入核函数后，计算特征映射的时间复杂度被大大降低了。与不带有特征映射时类似，现在SVM对新样本$\mathbf{x}$的预测为$$\hat{y}={\mathbf{w}}^{\ast \mathrm{T}}\varphi (\mathbf{x})+b^{\ast }$$

  虽然我们不知道$\varphi (\mathbf{x})$，无法按照原来的方法由${\mathbf{\alpha }}^{\ast }$计算 ${\mathbf{w}}^{\ast }=\sum {\alpha }_i^{\ast }{y}_i\varphi ({\mathbf{x}}_i)$。但是，我们可以直接利用核函数计算${\mathbf{w}}^{\ast \mathrm{T}}\varphi (\mathbf{x})$：$${\mathbf{w}}^{\ast \mathrm{T}}\varphi (\mathbf{x})=\sum _{i=1,{\mathbf{x}}_i\in \mathcal{S}}^m{\alpha }_i^{\ast }{y}_i\varphi ({\mathbf{x}}_i{)}^{\mathrm{T}}\varphi (\mathbf{x})=\sum _{i=1,{\mathbf{x}}_i\in \mathcal{S}}^m{\alpha }_i^{\ast }{y}_{i}K({\mathbf{x}}_i,\mathbf{x})$$ 从而$b^{\ast }$也可以按原方法计算得出：$$b^{\ast }=-\frac{1}{2}(\underset{i,y_i=-1}{\max }{\mathbf{w}}^{\ast \mathrm{T}}\varphi ({\mathbf{x}}_i)+\underset{i,y_i=1}{\max }{\mathbf{w}}^{\ast \mathrm{T}}\varphi ({\mathbf{x}}_i))$$

  实践中，$b^{\ast }$仍然由SMO算法求解时同步迭代计算。这时，SVM在计算时只需要用到支持向量的优点就很明显了。在数据集上建立好SVM模型后，我们可以只保留支持向量，而将剩余的数据都舍弃，减小存储模型的空间占用。

  现在，我们的任务就变成寻找合适的核函数，来让原本线性不可分的数据线性可分。通常来说，核函数应当衡量向量之间的相似度。常用的核函数有：

• 内积核：$K(\mathbf{x},\mathbf{y})={\mathbf{x}}^{\mathrm{T}}\mathbf{y}$，该函数即为线性SVM所用的核函数。

• 简单多项式核：$K(\mathbf{x},\mathbf{y})=({\mathbf{x}}^{\mathrm{T}}\mathbf{y}{)}^d$。

• 高斯核：$K(\mathbf{x},\mathbf{y})={\text{e}}^{-\frac{\Vert \mathbf{x}-\mathbf{y}{\Vert }^2}{2{\sigma }^2}}$，又称径向基函数（radial basis function，RBF）核。

• 余弦相似度核：$K(\mathbf{x},\mathbf{y})=\frac{{\mathbf{x}}^{\mathrm{T}}\mathbf{y}}{\Vert \mathbf{x}\Vert \cdot \Vert \mathbf{y}\Vert }$，该函数计算的是向量$\mathbf{x}$与$\mathbf{y}$之间夹角的余弦值。

• Sigmoid核：$K(\mathbf{x},\mathbf{y})=\tanh (\beta {\mathbf{x}}^{\mathrm{T}}\mathbf{y}+c)$，可以证明，带有sigmoid核的SVM等价于两层的多层感知机。

  下面，我们尝试用不同的非线性核函数对螺旋数据集进行分类，并观察分类效果。首先，我们实现上文介绍的几个核函数。

# 简单多项式核
def simple_poly_kernel(d):def k(x, y): return np.inner(x, y) ** dreturn k# RBF核
def rbf_kernel(sigma):def k(x, y):return np.exp(-np.inner(x - y, x - y) / (2.0 * sigma ** 2))return k# 余弦相似度核
def cos_kernel(x, y):return np.inner(x, y) / np.linalg.norm(x, 2) / np.linalg.norm(y, 2)# sigmoid核
def sigmoid_kernel(beta, c):def k(x, y):return np.tanh(beta * np.inner(x, y) + c)return k

  然后，我们依次用这4种核函数计算SVM在双螺旋数据集上的分类结果。其中，简单多项式核取 $d=3$；RBF核取标准差 $\sigma =0.1$；sigmoid核取 $\beta =1$、$c=-1$。为了更清晰地展示结果，我们在 $[-1.5,1.5]\times [-1.5,1.5]$ 的平面上网格状均匀选点，用构建好的SVM判断这些点的类别，并将其所在小网格涂成对应的颜色。

kernels = [simple_poly_kernel(3), rbf_kernel(0.1), cos_kernel, sigmoid_kernel(1, -1)
]
ker_names = ['Poly(3)', 'RBF(0.1)', 'Cos', 'Sigmoid(1,-1)']
C = 1e8
max_iter = 500# 绘图准备，构造网格
plt.figure()
fig, axs = plt.subplots(2, 2, figsize=(10, 10))
axs = axs.flatten()
cmap = ListedColormap(['coral', 'royalblue'])# 开始求解 SVM
for i in range(len(kernels)):print('核函数：', ker_names[i])alpha = SMO(x, y, kernels[i], C=C, max_iter=max_iter)sup_idx = alpha > 1e-5 # 支持向量的系数不为零sup_x = x[sup_idx] # 支持向量sup_y = y[sup_idx]sup_alpha = alpha[sup_idx]# 用支持向量计算 w^T*xdef wx(x_new):s = 0for xi, yi, ai in zip(sup_x, sup_y, sup_alpha):s += yi * ai * kernels[i](xi, x_new)return s# 计算b*neg = [wx(xi) for xi in sup_x[sup_y == -1]]pos = [wx(xi) for xi in sup_x[sup_y == 1]]b = -0.5 * (np.max(neg) + np.min(pos))# 构造网格并用 SVM 预测分类G = np.linspace(-1.5, 1.5, 100)G = np.meshgrid(G, G)X = np.array([G[0].flatten(), G[1].flatten()]).T # 转换为每行一个向量的形式Y = np.array([wx(xi) + b for xi in X])Y[Y < 0] = -1Y[Y >= 0] = 1Y = Y.reshape(G[0].shape)axs[i].contourf(G[0], G[1], Y, cmap=cmap, alpha=0.5)# 绘制原数据集的点axs[i].scatter(x[y == -1, 0], x[y == -1, 1], color='red', label='y=-1')axs[i].scatter(x[y == 1, 0], x[y == 1, 1], marker='x', color='blue', label='y=1')axs[i].set_title(ker_names[i])axs[i].set_xlabel(r'$x_1$')axs[i].set_ylabel(r'$x_2$')axs[i].legend()plt.show()

  从实验结果图我们可以看出，不同的核函数对SVM模型的分类效果是截然不同的。对于双螺旋数据的二分类任务，高斯核函数（RBF）带给SVM的性能要明显好于其他核函数。根据高斯核函数的公式，我们可以看到高斯核本质是在衡量样本和样本之间基于欧几里得距离的相似度，这样使得欧几里得距离近的样本更好的聚在一起，在高维空间中达到线性可分。此外，松弛变量带来的对错分类样本的容忍度$C$也会极大影响分类结果，可以调整$C$的值，观察不同核函数决策边界的变化。

五、Sklearn中的SVM工具

  机器学习工具库sklearn提供了封装好的SVM工具，且支持多种内置核函数。我们以RBF核函数为例，复现上面在双螺旋数据集上的分类结果。在sklearn.SVM中，SVC表示用SVM完成分类任务，SVR表示用SVM完成回归任务，这里我们选用SVC。此外，它的参数和我们上面的公式在表达上有细微的区别。对于RBF核函数，其参数为 $\gamma =1/(2{\sigma }^2)$。上一节我们设置 $\sigma =0.1$，因此这里对应的参数为 $\gamma =50$。我们同样在平面上采样，绘制出该SVM给出的分类边界。可以看出，其结果与我们自己实现的SVM基本一致。

  使用scikit-learn库中svm模块的SVC类可以建立支持向量机模型，其语法格式和参数说明如下。

sklearn.svm.SVC(C=1.0, kernel=’rbf’, degree=3, gamma=’auto’, coef0=0.0, shrinking=True, probability=False, tol=0.001, cache_size=200, class_weight=None, verbose=False, max_iter=-1, decision_function_shape=’ovr’, random_state=None)

参数名称	说明
C	接收int或float，默认为1.0。惩罚参数C，用于控制分类器的复杂度。较大的C值会使分类器更复杂并且可能导致过拟合，而较小的C值会使分类器更简单但可能导致欠拟合。
kernel	接收str。表示核函数，可选参数为linear、poly、rbf、sigmoid、precomputed。默认为rbf。
degree	接收int。表示多项式核函数poly的维度。默认为3。
gamma	接收str。表示rbf、poly、sigmoid核函数的参数，若是auto，则自动设置参数。默认为auto。
coef0	接收int或float。表示核函数的常数项，对poly和sigmoid有效，默认为0.0。
shrinking	接收bool。是否启用收缩启发式。收缩启发式可以加速训练过程，尤其是在数据量较大的情况下。默认=True。
probability	接收bool。是否启用概率估计。启用后，会增加训练时间，但可以使用predict_proba方法来获取预测概率。默认=False。
tol	接收float。表示停止训练的误差大小。默认为0.001。
cache_size	接收float。指定缓存大小（以MB为单位），用于加速计算。默认=200。
class_weight	接收dict or {‘balanced’}。类别权重。可以为不同的类别设置不同的权重，‘balanced’ 会根据类的频率自动调整权重。默认=None。
verbose	接收bool。是否输出详细的训练过程信息。默认=False。
max_iter	接受int。表示最大迭代次数，-1表示无限制。默认为-1。
decision_function_shape	接收{‘ovo’, ‘ovr’}。决策函数的形状：‘ovo’：一对一策略；‘ovr’：一对多策略。默认=‘ovr’。
break_ties	接收bool。是否在决策函数值相等的情况下打破平局。在decision_function_shape='ovr’且probability=True时有效。默认=False。
random_state	接收int, RandomState instance or None。控制随机数生成的种子，确保结果的可复现性。默认=None。

# 从sklearn.svm中导入SVM分类器
from sklearn.svm import SVC# 定义SVM模型，包括定义使用的核函数与参数信息
model = SVC(kernel='rbf', gamma=50, tol=1e-6)
model.fit(x, y)# 绘制结果
fig = plt.figure(figsize=(6,6))
G = np.linspace(-1.5, 1.5, 100)
G = np.meshgrid(G, G)
X = np.array([G[0].flatten(), G[1].flatten()]).T # 转换为每行一个向量的形式
Y = model.predict(X)
Y = Y.reshape(G[0].shape)
plt.contourf(G[0], G[1], Y, cmap=cmap, alpha=0.5)
# 绘制原数据集的点
plt.scatter(x[y == -1, 0], x[y == -1, 1], color='red', label='y=-1')
plt.scatter(x[y == 1, 0], x[y == 1, 1], marker='x', color='blue', label='y=1')
plt.xlabel(r'$x_1$')
plt.ylabel(r'$x_2$')
plt.legend()
plt.show()

思考：试基于本节代码，标记出双螺旋数据集spiral.csv上使用RBF核函数的SVM模型的支持向量，并讨论这些数据点成为支持向量的原因。

# 访问支持向量的索引
support_vector_indices = model.support_# 获取支持向量
support_vectors = x[support_vector_indices]# 绘制结果
fig = plt.figure(figsize=(6,6))
G = np.linspace(-1.5, 1.5, 100)
G = np.meshgrid(G, G)
X = np.array([G[0].flatten(), G[1].flatten()]).T # 转换为每行一个向量的形式
Y = model.predict(X)
Y = Y.reshape(G[0].shape)
plt.contourf(G[0], G[1], Y, cmap=cmap, alpha=0.5)# 绘制支持向量
plt.scatter(support_vectors[:,0], support_vectors[:,1], marker='o', color='none', edgecolor='purple', s=150, label='Support Vectors')# 绘制原数据集的点
plt.scatter(x[y == -1, 0], x[y == -1, 1], color='red', label='y=-1')
plt.scatter(x[y == 1, 0], x[y == 1, 1], marker='x', color='blue', label='y=1')
plt.xlabel(r'$x_1$')
plt.ylabel(r'$x_2$')
plt.legend()
plt.show()

  双螺旋数据是一个常用的非线性数据集，通常需要使用RBF（径向基函数）核函数来处理。在这样的数据集中，数据点在空间中具有复杂的分布，支持向量通常分布在各个类别的交界处，帮助模型准确地捕捉非线性的决策边界。成为支持向量的原因如下：

• 离决策边界较近：支持向量通常距离决策边界较近。这些点直接影响决策边界的定位，因为它们位于距离边界的“支持”区域。
• 非线性特征：在RBF核函数的帮助下，SVM能够在高维特征空间中处理非线性问题。支持向量在高维空间中体现为离决策边界非常近的点，这些点在原始空间中可能处于复杂的非线性区域。
• 边界的确定：支持向量是确定分类决策边界的关键点。如果移除这些点，决策边界可能会发生变化，因此它们在模型训练中起着关键作用。

六、拓展：SVM对偶问题的推导

  对一般形式的带约束的凸优化问题
$$\begin{array}{rl}\underset{w}{\min }& f(w)\\ \text{s.t.}& g_i(w)\le 0,i=1,\cdots ,k\\ & h_j(w)=0,j=1,\cdots ,l\end{array}$$ 定义其拉格朗日函数（Lagrangian function）为$$\mathcal{L}(w,\mathbf{\alpha },\mathbf{\beta })=f(w)+\sum _{i=1}^k{\alpha }_i{g}_i(w)+\sum _{i=1}^l{\beta }_i{h}_i(w),{\alpha }_i\ge 0$$ 其中$\mathbf{\alpha }$与$\mathbf{\beta }$称为拉格朗日乘子。拉格朗日函数$\mathcal{L}$的值不仅与原问题的参数$w$有关，还与乘子$\mathbf{\alpha }$和$\mathbf{\beta }$有关，因此，可以利用乘子的值来表达原问题的约束条件。记原问题为$${\theta }_{\mathcal{P}}(w)=\underset{\mathbf{\alpha },\mathbf{\beta };{\alpha }_i\ge 0}{\max }\mathcal{L}(w,\mathbf{\alpha },\mathbf{\beta })$$ 并且定义参数$w$使得原问题的约束条件被违反，即 $g_i(w)>0$ 或 $h_i(w)\ne 0$ 时，原问题 ${\theta }_{\mathcal{P}}=+\infty$。反过来说，如果原问题的约束条件都被满足，那么 $h_i(w)=0$，从而拉格朗日函数的第3项全部为零。并且由 $g_i(w)\le 0$ 且 ${\alpha }_i\ge 0$，知 ${\alpha }_i{g}_i(w)\le 0$。如果要让$\mathcal{L}$最大，那么所有拉格朗日乘子${\alpha }_i$都应当使 ${\alpha }_i{g}_i(w)=0$，否则$\mathcal{L}$的值会减小。因此，当约束条件满足时，拉格朗日函数的最大值恰好就等于原问题的目标函数$f(w)$，从而原问题可以写为
$${\theta }_{\mathcal{P}}=\{\begin{array}{rlrl}& f(w),& & w满足约束条件\\ & +\infty ,& & 其他情况\end{array}$$ 于是，最开始带约束的优化问题等价于对原问题的无约束优化：$$\underset{w}{\min }{\theta }_{\mathcal{P}}(w)=\underset{w}{\min }\underset{\mathbf{\alpha },\mathbf{\beta };{\alpha }_i\ge 0}{\max }\mathcal{L}(w,\mathbf{\alpha },\mathbf{\beta })$$ 记该问题的最优值为 $p^{\ast }=\underset{w}{\min }{\theta }_{\mathcal{P}}(w)$。

  至此，我们只是通过拉格朗日函数对原问题进行了等价变形，并没有降低问题求解的难度。为了真正解决该优化问题，我们考虑另一个稍微有些区别的函数${\theta }_{\mathcal{D}}$，定义为$${\theta }_{\mathcal{D}}(\mathbf{\alpha },\mathbf{\beta })=\underset{w}{\min }\mathcal{L}(w,\mathbf{\alpha },\mathbf{\beta })$$

  将上面优化问题中计算$\min$和$\max$的顺序交换，定义其对偶问题为$$\underset{\mathbf{\alpha },\mathbf{\beta };{\alpha }_i\ge 0}{\max }{\theta }_{\mathcal{D}}(\mathbf{\alpha },\mathbf{\beta })=\underset{\mathbf{\alpha },\mathbf{\beta };{\alpha }_i\ge 0}{\max }\underset{w}{\min }\mathcal{L}(w,\mathbf{\alpha },\mathbf{\beta })$$ 记其最优值为 $d^{\ast }=\underset{\mathbf{\alpha },\mathbf{\beta };{\alpha }_i\ge 0}{\max }{\theta }_{\mathcal{D}}(\mathbf{\alpha },\mathbf{\beta })$。可以证明，先取$\min$后取$\max$的对偶问题最优值$d^{\ast }$要小于等于先取$\max$后取$\min$的原问题最优值$p^{\ast }$。然而，在满足某些特殊条件的情况下，两者的最优值是相等的，即 $d^{\ast }=p^{\ast }$。对于一个凸优化问题，如果其约束条件可以被严格满足，即存在$w$使得 $g_i(w)<0$ 且 $h_i(w)=0$，那么必然存在$w^{\ast }$、${\mathbf{\alpha }}^{\ast }$和${\mathbf{\beta }}^{\ast }$，满足：

• $w^{\ast }$是原问题$\underset{w}{\min }{\theta }_{\mathcal{P}}(w)$的解；
• ${\mathbf{\alpha }}^{\ast }$和${\mathbf{\beta }}^{\ast }$是对偶问题 $\underset{\mathbf{\alpha },\mathbf{\beta };{\alpha }_i\ge 0}{\max }{\theta }_{\mathcal{D}}(\mathbf{\alpha },\mathbf{\beta })$ 的解；
• 最优值 $d^{\ast }=p^{\ast }=\mathcal{L}(w^{\ast },{\mathbf{\alpha }}^{\ast },{\mathbf{\beta }}^{\ast })$，

以及卡鲁什-库恩-塔克条件（Karush-Kuhn-Tucker conditions），简称KKT条件：

• 稳定性：${\nabla }_w\mathcal{L}(w^{\ast },{\mathbf{\alpha }}^{\ast },{\mathbf{\beta }}^{\ast })=0$；
• 原问题满足性：$g_i(w^{\ast })\le 0$，$h_i(w^{\ast })=0$；
• 对偶问题满足性：${\alpha }_i^{\ast }\ge 0$；
• 互补松弛性：${\alpha }_i^{\ast }{g}_i(w^{\ast })=0$。

  反过来，如果某一组$(w,\mathbf{\alpha },\mathbf{\beta })$满足KKT条件，那么它们也是原问题和对偶问题的解。KKT条件中的前3个条件较好理解，都是优化问题本身的约束；最后一个互补松弛性我们在推导 ${\theta }_{\mathcal{P}}=f(w)$ 时也提到过，否则 ${\alpha }_i^{\ast }{g}_i(w^{\ast })<0$ 会使目标拉格朗日函数的值减小，与${\alpha }_i^{\ast }$和$w^{\ast }$是最优解矛盾。

  根据上面的讨论，如果一个凸优化问题满足KKT条件，且其对偶问题比原问题更容易解决，那么我们可以通过求对偶问题的解来得到原问题的解。对线性版本的支持向量机的优化问题
$$\begin{array}{rl}& \underset{\mathbf{w},b}{\min }\frac{1}{2}\Vert \mathbf{w}{\Vert }^2\\ & \text{s.t.}{y}_i({\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b)\ge 1,i=1,\cdots ,m\end{array}$$ 来说，$\mathbf{w}$和$b$都是问题的参数。我们将约束条件重写为 $g_i(\mathbf{w},b)=-y_i({\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b)+1\le 0$，得到其拉格朗日函数为$$\mathcal{L}(\mathbf{w},b,\mathbf{\alpha })=\frac{1}{2}\Vert \mathbf{w}{\Vert }^2-\sum _{i=1}^m{\alpha }_i(y_i({\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b)-1)$$

  为了求其最小值$\underset{\mathbf{w},b}{\min }\mathcal{L}$，令其对$\mathbf{w}$和$b$的梯度等于0，得
$$\begin{array}{rlrl}& & 0& ={\nabla }_{\mathbf{w}}\mathcal{L}(\mathbf{w},b,\mathbf{\alpha })=\mathbf{w}-\sum _{i=1}^m{\alpha }_i{y}_i{\mathbf{x}}_i\\ \Rightarrow & & \mathbf{w}& =\sum _{i=1}^m{\alpha }_i{y}_i{\mathbf{x}}_i\\ & & 0& ={\nabla }_b\mathcal{L}(\mathbf{w},b,\mathbf{\alpha })=\sum _{i=1}^m{\alpha }_i{y}_i\end{array}$$

  我们把$\mathbf{w}$与$b$代入拉格朗日函数的表达式，得到对偶函数${\theta }_{\mathcal{D}}(\mathbf{\alpha })$的表达式为
$$\begin{array}{rl}{\theta }_{\mathcal{D}}(\mathbf{\alpha })& =\underset{\mathbf{w},b}{\min }\mathcal{L}(\mathbf{w},b,\mathbf{\alpha })\\ & =\frac{1}{2}{\Vert \sum _{i=1}^m{\alpha }_i{y}_i{\mathbf{x}}_i\Vert }^2-\sum _{i=1}^m\left({\alpha }_i{y}_i\sum _{j=1}^m{\alpha }_j{y}_j{\mathbf{x}}_j^{\mathrm{T}}{\mathbf{x}}_i\right)-{\left(\sum _{i=1}^m{\alpha }_i{y}_i\right)}^2+\sum _{i=1}^m{\alpha }_i\\ & =\sum _{i=1}^m{\alpha }_i-\frac{1}{2}\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i{\alpha }_j{y}_i{y}_j{\mathbf{x}}_i^{\mathrm{T}}{\mathbf{x}}_j\end{array}$$ 于是，对偶优化问题的形式为
$$\begin{array}{rl}& \underset{\mathbf{\alpha }}{\max }{\theta }_{\mathcal{D}}(\mathbf{\alpha })\\ & \text{s.t.}{\alpha }_i\ge 0,i=1,\cdots ,m\\ & \sum _{i=1}^m{\alpha }_i{y}_i=0\end{array}$$

  而引入松弛变量${\xi }_i$后，我们用类似的方式也可以求出其对偶问题。具体的推导过程与上面基本一致，我们在此略去，感兴趣的可以自行尝试推导。最后的结果为
$$\begin{array}{rl}& \underset{\mathbf{\alpha }}{\max }{\theta }_{\mathcal{D}}(\mathbf{\alpha })\\ & \text{s.t.}0\le {\alpha }_i\le C,i=1,\cdots ,m\\ & \sum _{i=1}^m{\alpha }_i{y}_i=0\end{array}$$ 其中，${\theta }_{\mathcal{D}}(\mathbf{\alpha })$的形式与不带松弛变量的版本相同。该对偶问题是关于$\mathbf{\alpha }$的二次规划问题，相比于原问题来说求解难度大大降低了。可以验证，这一问题的形式满足KKT条件，从而我们可以通过求解对偶问题得到原问题的解。并且根据KKT条件中的互补松弛性，最优的$(\mathbf{w},b,{\mathbf{\alpha }}^{\ast })$满足 ${\alpha }_i^{\ast }(1-y_i({\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b^{\ast }))=0$。

思考：试通过参数量与数据集大小的关系、参数更新方式等视角，分析和体会SVM模型的原问题对应参数化模型，而对偶问题对应非参数化模型。

（1）原问题：

  原问题是指SVM的原始优化问题，它直接处理数据点和模型参数。SVM的原问题涉及一个带有约束的优化问题，即在满足所有数据点到分隔超平面距离至少为某个固定值（即间隔）的条件下，最大化这个间隔。
  在数学上，原问题可以表示为关于支持向量和模型参数（例如，权重向量和偏置项）的问题。如果数据集很大，那么相应的参数也会很多，因此，从这个角度看，原问题似乎是一个参数化模型。然而，由于解仅由一小部分称为支持向量的数据点决定，所以实际上并不需要存储整个数据集。

（2）对偶问题：

  通过引入拉格朗日乘子将原问题的约束优化转换为无约束优化问题，我们得到了所谓的对偶问题。在这个过程中，数据点以拉格朗日乘子的形式出现，并且最终决策函数仅依赖于数据点之间的内积，而不是数据点的显式表示。这意味着在对偶形式下，我们不需要直接处理原始数据点，而是关注数据点之间的关系。
  从参数更新方式来看，对偶问题通常只涉及拉格朗日乘子（alpha），而与原始问题中的参数（如权重和偏置）无关。这使得对偶问题看起来更像一个非参数化模型，因为它没有直接使用原始参数空间的大小作为其复杂性的度量。此外，对偶问题通常具有更少的变量（拉格朗日乘子的数量等于数据点的数量），这使得求解过程更加高效，尤其是在处理大规模数据集时。

附：以上文中的数据集及相关资源下载地址：
链接：https://pan.quark.cn/s/1ce6354d6788
提取码：gHSD