机器学习方法(七)：支持向量机(support vector machines, SVM)

2019-08-14

× 文章目录

1. 一、线性可分SVM——硬间隔
2. 二、线性SVM——软间隔
3. 三、非线性SVM——核技巧
1. 3.1. 3.1 非线性支持向量机
4. Summary
5. Reference

一、线性可分SVM——硬间隔

1.1 超平面与间隔

给定训练集$D={(x_1,y_1 ),(x_2,y_2 ),…,(x_m,y_m )} ,y_i∈{-1,+1}$，分类学习的最基本的任务就是在样本空间中寻找一个划分超平面，将不同类别的样本划分开来，但是这样的超平面有很多，选择哪个最好呢？直观上来看，越接近两类样本分隔界的样本，越容易产生分类错误，而位于两类样本“正中间”的划分超平面受影响最小，泛化能力更强。

在样本空间中，划分的超平面可通过如下线性方程表示：

$w_1 x_1+w_2 x_2+w_3 x_3+⋯+w_d x_d+b=0$

即：

$\left[\begin{array}{lllll} w_{1} & w_{2} & w_{3} & \ldots & w_{d} \end{array}\right] \cdot\left[\begin{array}{l} x_{1} \\ x_{2} \\ x_{3} \\ \ldots \\ x_{d} \end{array}\right]+b=0$

转换向量表示即为：

$\boldsymbol{w}^{T} \boldsymbol{x}+b=0$

其中$\mathbf{w}=\left(\mathrm{w}_{1} ; \mathrm{w}_{2} ; \ldots ; \mathrm{w}_{\mathrm{d}}\right)$为法向量,决定了超平面的方向;$b$为位移项，决定了超平面与原点之间的距离。则样本空间中任一点x到超平面(w,b)的距离可表示为：

$\begin{equation} r=\frac{\left|\boldsymbol{w}^{T} x+b\right|}{|| \boldsymbol{w}||} \tag{1.1} \end{equation}$

如果我们的决策面方程可以对样本正确分类，即对$\left(x_{i}, y_{i}\right) \in D$，若$y_{i}=+1$，则有$\boldsymbol{w}^{T} \boldsymbol{x}_{i}+b>0$；

若$y_{i}=-1$，则有$\boldsymbol{w}^{T} \boldsymbol{x}_{i}+b<0$；令：

$\begin{equation} \left\{\begin{array}{ll} \boldsymbol{w}^{T} \boldsymbol{x}_{i}+b \geq+1, & y_{i}=+1 \\ \boldsymbol{w}^{T} \boldsymbol{x}_{i}+b \leq-1, & y_{i}=-1 \end{array}\right. \tag{1} \end{equation}$

1.2 间隔最大化

距离超平面最近的这几个训练样本点使式(1)的等号成立的样本被称为“支持向量”，对于这些支持向量样本点，有：

$d=\frac{\left|\boldsymbol{w}^{T} x+b\right|}{|| \boldsymbol{w}||}=\frac{1}{|| \boldsymbol{w}||}, \text { if } x_{i} \text { is a support vector }$

两个异类支持向量到平面的距离和为：

$r=\frac{2}{|| w||}$

找到最大间隔的超平面，即找到参数w和b,使得r最大，即：

$\begin{equation} \max _{w, b} \frac{2}{|| w||}\\ \tag{1.2} \begin{array}{ll} \text { s. t. } & y_{i}\left(\boldsymbol{w}^{T} x+b\right) \geq 1 & i=1,2, \ldots, m \text { . } \end{array} \end{equation}$

这等价于最小化$|\mathbf{w}|^{2}$,上式可写成：

$\begin{equation} \min _{w, b} \frac{1}{2}|| w||^2 \\ \tag{1.3} \end{equation} \begin{array}{ll} \text { s. t. } & y_{i}\left(\boldsymbol{w}^{T} x+b\right) \geq 1 \quad i=1,2, \ldots, m \text { . } \end{array}$

1.3 对偶问题

上述式(1.3)本身是一个含有不等式的凸二次规划的问题。

凸二次规划的问题：凸优化问题的一个特殊形式，当目标函数是二次型函数且约束函数g是仿射函数时，就变成一个凸二次规划问题，凸二次规划问题的一般形式为：
$\min _{x} \frac{1}{2} x^{T} Q x+c^{T} x \\ \begin{aligned} &\text {s.t.} \quad W x \leq b \end{aligned}$

对式(1.3)使用拉格朗日乘子法可得到其“对偶问题”，对每条约束添加拉格朗日乘子$\alpha_i≥0$，则该问题的拉格朗日目标函数：

$\begin{equation} L(\boldsymbol{w}, b, \boldsymbol{\alpha})=\frac{1}{2}|| \boldsymbol{w}||^{2}+\sum_{i=1}^{m} \alpha_{i}\left(1-y_{i}\left(\boldsymbol{w}^{T} x+b\right)\right) \tag{1.4} \end{equation}$

拉格朗日乘子法：假设需要求极值的目标函数为$f(x,y) $，约束条件为$\varphi(x,y)=M$。设$g(x,y)=M-φ(x,y) $，定义一个新函数$F(x,y,λ)=f(x,y)+λg(x,y) $，则用偏导数方法列出方程：
$\left\{\begin{array}{l} \frac{\partial F(x, y, \lambda)}{\partial x}=0 \\ \frac{\partial F(x, y, \lambda)}{\partial y}=0 \\ \frac{\partial F(x, y, \lambda)}{\partial \lambda}=0 \end{array}\right.$
求出$x,y,λ$的值，代入即可得到目标函数的极值。

其中$\alpha_i$为拉格朗日乘子，且 $\alpha_i≥0$。现在我们令

$\theta(\boldsymbol{w})=\max _{\alpha_i≥0}⁡L(\boldsymbol{w},b,\boldsymbol{\alpha})$

当样本点不满足约束条件时，即在可行解区域外：$y_{i}\left(\boldsymbol{w}^{T} x+b\right)<1$，此时，将$\alpha_i$设置为无穷大；当满本点满足约束条件时，即在可行解区域内：$y_{i}\left(\boldsymbol{w}^{T} x+b\right)≥1$

$\theta(\boldsymbol{w})=\left\{\begin{array}{lr} \frac{1}{2}|| \boldsymbol{w}||^{2}, \ w和b满足(3)式约束条件 \\ +\, \infty , \ w和b不满足(3)式约束条件 \end{array}\right.$

于是原约束问题就等价于:

$\begin{equation} \min _{\boldsymbol{w}, b} \theta(\boldsymbol{w})=\min _{\boldsymbol{w}, b} \max _{\alpha_{i} \geq 0} L(\boldsymbol{w}, b, \boldsymbol{\alpha})=p^{*} \tag{1.5} \end{equation}$

其与式$(1.3)$所述问题是完全等价的。

这个求解过程不好做，使用拉格朗日函数对偶性，将最小和最大的位置交换，即：

$\begin{equation} \max _{a_{i} \geq 0} \min _{\mathbf{w}, \mathrm{b}} L(\boldsymbol{w}, b, \boldsymbol{\alpha})=d^{*} \tag{1.6} \end{equation}$

要使得${p^\ast =d^\ast}$，需要满足$KKT$条件，即要求：

$\left\{\begin{array}{l} a_{i} \geq 0 \\ y_{i} f\left(x_{i}\right)-1 \geq 0 \\ a_{i}\left(y_{i} f\left(x_{i}\right)-1\right)=0 \end{array}\right.$

为得到具体形式，第一步先求$\min _{\mathbf{w}, \mathrm{b}} L(\boldsymbol{w}, b, \boldsymbol{\alpha})$，令$L(\boldsymbol{w}, b, \boldsymbol{\alpha})$对$\boldsymbol{w}$和b的偏导为0，可得：

$\begin{aligned} \nabla_{\boldsymbol{w}} L(\boldsymbol{w}, b, \alpha)&=\boldsymbol{w} -\sum_{i=1}^{n} \alpha_{i} y_{i} x_{i}=0 \Longrightarrow \boldsymbol{w}=\sum_{i=1}^{n} \alpha_{i} y_{i} x_{i} \\ \nabla_{b} L(\boldsymbol{w}, b, \alpha)&=-\sum_{i=1}^{n} \alpha_{i} y_{i} \Longrightarrow 0 \Longrightarrow \sum_{i=1}^{n} \alpha_{i} y_{i}=0 \end{aligned}$

将这两个式子带入拉格朗日目标函数$L(\boldsymbol{w}, b, \alpha)$，消去$\boldsymbol{w}$和b,得：

$\begin{aligned} L(\boldsymbol{w}, b, \boldsymbol{\alpha})&=\frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_{i} \alpha_{i} y_{i} y_{j}\left(x_{i} \cdot x_{j}\right)-\sum_{i=1}^{N} a_{i} y_{i}\left(\left(\sum_{j=1}^{N} \alpha_{j} y_{j} x_{j}\right) \cdot x_{i}+b\right)+\sum_{i=1}^{N} \alpha_{i} \\ &=-\frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_{i} \alpha_{i} y_{i} y_{j}\left(x_{i} \cdot x_{j}\right)+\sum_{i=1}^{N} \alpha_{i} \end{aligned}$

即：

$\begin{equation} \min _{\boldsymbol{w}, b} L(\boldsymbol{w}, b, \boldsymbol{\alpha})=-\frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_{i} \alpha_{i} y_{i} y_{j}\left(\boldsymbol{x}_{i} \cdot \boldsymbol{x}_{j}\right)+\sum_{i=1}^{N} \alpha_{i} \tag{1.7} \end{equation}$

第二步继续求$\min _{\boldsymbol{w}, b} L(\boldsymbol{w}, b, \boldsymbol{\alpha})$对$\alpha$的极大：

$\max _{\alpha}\left(-\frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_{i} \alpha_{i} y_{i} y_{j}\left(x_{i} \cdot x_{j}\right)+\sum_{i=1}^{N} \alpha_{i}\right) \\ \text { s.t. } \sum_{i=1}^{N} \alpha_{i} y_{i}=0 \quad a_{i} \geq 0, i=1,2, \ldots, N$

等价于式$(1.7)$取负数后求极小值：

$\min _{\alpha} \left(\frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_{i} \alpha_{i} y_{i} y_{j}\left(x_{i} \cdot x_{j}\right)-\sum_{i=1}^{N} \alpha_{i} \right) \\ \text { s.t. } \sum_{i=1}^{N} \alpha_{i} y_{i}=0 \quad a_{i} \geq 0, i=1,2, \ldots, N$

对于上式，使用序列最小优化（SMO）算法求解$\alpha^\ast$，进而求得w和b,进而求出超平面。

SMO算法基本思想：在每一步优化当中，挑选出诸多参数$(a_k(k=1,2,…,N))$中的两个参数$(a_i,a_j)$作为“真正参数”，其余的参数都视为常数，从而问题就变成了类似二次方程求最大值的问题。

根据前面的推导，有：

$\boldsymbol{w}=\sum_{i=1}^{n} \alpha_{i} y_{i} x_{i} \quad \sum_{i=1}^{n} \alpha_{i} y_{i}=0$

在$\alpha^\ast$中，至少存在一个$a_j^\ast>0$，对此$j$有

$y_{j}\left(\boldsymbol{w}^{*} \cdot x_{j}+b^{*}\right)-1=0$

可得：

$\begin{aligned} b^* &= \frac{1}{y_j} - \boldsymbol{w}^{*} \cdot x_{j} \\ &= y_j - \boldsymbol{w}^{*} \cdot x_{j} \\ &= y_j - \sum_{i=1}^{N} a_{i}^{*} y_{i}\left(\boldsymbol{x}_{i} \cdot \boldsymbol{x}_{\boldsymbol{j}}\right) \end{aligned}$

即：

$\boldsymbol{w}^{*}=\sum_{i=1}^{N} a_{i}^{*} y_{i} \boldsymbol{x}_{i} \quad b^{*}=y_{j}-\sum_{i=1}^{N} a_{i}^{*} y_{i}\left(\boldsymbol{x}_{i} \cdot \boldsymbol{x}_{\boldsymbol{j}}\right)$

分析$KKT$条件里的互补条件，对于任意样本$(x_i,y_i)$，总会有$\alpha_i=0$或者$y_{i} f(x_{i})-1=0$。则有若$\alpha_i=0$，此样本点不是支持向量对模型没有任何作用；若$\alpha_i>0$，此样本位于最大间隔边界上，是一个支持向量，如下图所示：

二、线性SVM——软间隔

在前面的讨论中，我们一直假定训练数据是严格线性可分的，即存在一个超平面能完全将两类数据分开。但是现实任务这个假设往往不成立，例如下图所示的数据。

2.1 软间隔最大化

解决该问题的一个办法是允许SVM在少量样本上出错，为此引入“软间隔(soft margin)”的概念。即允许少量样本不满足约束

$\begin{equation} y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right) \geqslant 1 \tag{2.1} \end{equation}$

为了在最大化间隔的同时，使得不满足约束的样本尽可能少，我们需要在优化的目标函数(3)里面新增一个对这些点的惩罚项。

$\begin{equation} \min _{\boldsymbol{w}, b} \frac{1}{2}\|\boldsymbol{w}\|^{2}+C \sum_{i=1}^{m} \ell_{0 / 1}\left(y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right)-1\right) \tag{2.2} \end{equation}$

其中$C>0$是个常数，$\ell_{0 / 1}$是“0/1损失函数”

$\ell_{0 / 1}(z)=\left\{\begin{array}{ll}1, & \text { if } z<0 \\0, & \text { otherwise }\end{array}\right.$

即若样本点满足约束条件损失就是$1$，否则损失就是$0$。当$C$为无穷大时，式$(2.2)$迫使所有样本均满足约束$(2.1)$，式$(2.2)$等价于$(1.4)$；当$C$取有限值时，式$(2.2)$允许一些样本不满足约束。

但是$\ell_{0 / 1}$非凸、非连续，因此常常使用其他损失函数来代替$\ell_{0 / 1}$。

$\begin{aligned} &hinge损失：\ell_{hinge}(z)=max(0,1-z);\\ &z指数损失：\ell_{exp}(z)=exp(-z);\\ &对数损失：\ell_{log}(z)=log(1+exp(-z)) \end{aligned}$

最常用的是$hinge$损失，即若样本点满足约束条件损失就是$0$，否则损失就是$1-z$，则优化目标$(2.2)$变成

$\begin{equation} \min _{\boldsymbol{w}, b} \frac{1}{2}\|\boldsymbol{w}\|^{2}+C \sum_{i=1}^{m} \max \left(0,1-y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right)\right) \tag{2.3} \end{equation}$

其中$C$称为惩罚参数，$C$越小时对误分类惩罚越小，越大时对误分类惩罚越大，当$C$取正无穷时就变成了硬间隔优化。实际应用时我们要合理选取$C$，$C$越小越容易欠拟合，越大越容易过拟合。

引入“松弛变量”$\xi_i≥0$，式$(2.3)$可写为：

$\begin{equation} \min _{\boldsymbol{w}, b, \xi_{i}} \frac{1}{2}\|\boldsymbol{w}\|^{2}+C \sum_{i=1}^{m} \xi_{i} \\ \begin{array}{c}\text { s.t. } y_{i}\left(X_{i}^{T} W+b\right) \geq 1-\xi_{i} \\\xi_{i} \geq 0, i=1,2, \ldots n .\end{array} \tag{2.4} \end{equation}$

这就是常用的“软间隔支持向量机”。

2.2 对偶问题

式$(2.4)$表示的软间隔支持向量机依然是一个凸二次规划问题，和硬间隔支持向量机类似，我们可以通过拉格朗日乘子法将其转换为对偶问题进行求解：

$\begin{equation} \begin{aligned} L(\boldsymbol{w}, b, \boldsymbol{\alpha}, \boldsymbol{\xi}, \boldsymbol{\mu})=& \frac{1}{2}\|\boldsymbol{w}\|^{2}+C \sum_{i=1}^{m} \xi_{i} + \sum_{i=1}^{m} \alpha_{i}\left(1-\xi_{i}-y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right)\right)-\sum_{i=1}^{m} \mu_{i} \xi_{i} \end{aligned} \tag{2.5} \end{equation}$

类似1.3节，为了求得对偶问题的解，我们需要先求得$L(\boldsymbol{w}, b, \boldsymbol{\alpha}, \boldsymbol{\xi}, \boldsymbol{\mu})$对$\boldsymbol{w}、 b、 \boldsymbol{\xi}$的极小再求对$\boldsymbol{\alpha}、 \boldsymbol{\mu}$的极大。

第一步先求$\min _{\boldsymbol{w}, b, \xi} L(\boldsymbol{w}, b, \boldsymbol{\alpha}, \boldsymbol{\xi}, \boldsymbol{\mu})$，令$L(\boldsymbol{w}, b, \boldsymbol{\alpha}, \boldsymbol{\xi}, \boldsymbol{\mu})$对$\boldsymbol{w}$,b,$\xi_i$的偏导为0，可得：

$\begin{align} \boldsymbol{w} &=\sum_{i=1}^{m} \alpha_{i} y_{i} \boldsymbol{x}_{i} \tag{2.6} \\ 0 &=\sum_{i=1}^{m} \alpha_{i} y_{i} \tag{2.7} \\ C &=\alpha_{i}+\mu_{i} \tag{2.8} \end{align}$

将上面三个式子代入式$(2.5)$并进行类似式$(1.7)$的推导即得：

$\begin{equation} \min _{\boldsymbol{w}, b, \xi} L(\boldsymbol{w}, b, \boldsymbol{\alpha}, \boldsymbol{\xi}, \boldsymbol{\mu}) = -\frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_{i} \alpha_{j} y_{i} y_{j} \boldsymbol{x}_{i}^{\mathrm{T}} \boldsymbol{x}_{j} + \sum_{i=1}^{m} \alpha_{i} \tag{2.9} \end{equation}$

第二步先求$\min _{\boldsymbol{w}, b, \xi} L(\boldsymbol{w}, b, \boldsymbol{\alpha}, \boldsymbol{\xi}, \boldsymbol{\mu})$对$\alpha$的极大，等价于式子$(2.9)$取负数后求极小值：

$\begin{equation} \min_\alpha \left( \frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_{i} \alpha_{j} y_{i} y_{j} \boldsymbol{x}_{i}^{\mathrm{T}} \boldsymbol{x}_{j} - \sum_{i=1}^{m} \alpha_{i} \right) \tag{2.10} \end{equation}\\ \text { s.t. } \sum_{i=1}^{m} \alpha_{i} y_{i}=0 \\ 0 \leqslant \alpha_{i} \leqslant C, \ i=1,2, \ldots, m$

至此，我们得到了原始最优化问题$(2.4)$和对偶最优化问题$(2.10)$。

类似1.3节，假设我们现在通过通用的二次规划求解方法或者SMO算法求得了$(2.10)$的最优解$\alpha^\ast$，则根据式$(2.6)$可求得最优$\boldsymbol{w^\ast}$：

$\boldsymbol{w} =\sum_{i=1}^{m} \alpha_{i} y_{i} \boldsymbol{x}_{i}$

对于软间隔支持向量机，$KKT$条件要求：

$\begin{equation} \left\{\begin{array}{l} \alpha_{i} \geqslant 0, \quad \mu_{i} \geqslant 0 \\ y_{i} f\left(\boldsymbol{x}_{i}\right)-1+\xi_{i} \geqslant 0 \\ \alpha_{i}\left(y_{i} f\left(\boldsymbol{x}_{i}\right)-1+\xi_{i}\right)=0 \\ \xi_{i} \geqslant 0, \mu_{i} \xi_{i}=0 \end{array}\right. \tag{2.11} \end{equation}$

对任意训练样本 $\left(\boldsymbol{x}_{i}, y_{i}\right),$ 总有 $\alpha_{i}=0$ 或 $y_{i} f\left(\boldsymbol{x}_{i}\right)=1-\xi_{i}$：

若 $\alpha_{i}=0$，则该样本不会对 $f(\boldsymbol{x})$ 有任何影响；
若 $\alpha_{i}>0$，则有 $y_{i} f\left(\boldsymbol{x}_{i}\right)=1-\xi_{i}$ ，即该样本是支持向量；

由式 (2.8) 可知：

若 $\alpha_{i} < C$，则有 $\mu_{i}>0$ ，进而有 $\xi_{i}=0$ 即该样本恰在最大间隔边界上；
若 $\alpha_{i}=C$，则有 $\mu_{i}=0$，此时若 $\xi_{i} \leqslant 1$ 则该样本落在最大间隔内部，若 $\xi_{i}>1$ 则该样本被错误分类；

如下图所示：

由此可看出, 软间隔支持向量机的最终模型仅与支持向量有关, 即通过采用$hinge$损失函数仍保持了稀疏性。

2.3 惩罚参数C

$\begin{equation} \min _{\boldsymbol{w}, b, \xi_{i}} \frac{1}{2}\|\boldsymbol{w}\|^{2}+C \sum_{i=1}^{m} \xi_{i} \\ \begin{array}{c} \end{array} \tag{2.4} \end{equation}$

对于一般化的问题，上式可以简化为：

$\min _{f} \Omega(f)+C \sum_{i=1}^{m} \ell\left(f\left(\boldsymbol{x}_{i}\right), y_{i}\right)$

其中$\Omega(f)$可以理解为“结构风险(structural risk)”，用来描述所求模型$f$的某些性质；第二项$\sum_{i=1}^{m} \ell\left(f\left(\boldsymbol{x}_{i}\right) , y_{i}\right)$称为“经验风险(empirical risk)”，用来描述模型与训练数据的契合程度(即误差)。而参数$C$就是用于对二者的折中,即我们一方面要求模型要满足某种性质（例如希望获得复杂度较小的模型）另一方面又想使模型与训练数据很契合（减小误差）。

从正则化角度来讲，$\Omega(f)$称为正则化项，$C$称为惩罚参数，越大即对误分类的惩罚越大(要求模型对训练模型更契合)，这可能会存在过拟合；越小即相对更加看重正则化项，此时可能存在欠拟合。

三、非线性SVM——核技巧

前面介绍的都是线性问题，然而在现实任务中，原始样本空间内也许不存在一个能正确划分两类样本的超平面(例如异或问题)，此时就需要用到核技巧(kernel trick)将线性支持向量机推广到非线性支持向量机。

设 $\mathcal{X}$ 是输入空间，又设 $\mathcal{H}$ 是特征空间（希尔伯特空间），如果存在一个 $\mathcal{X}$ 到 $\mathcal{H}$ 的映射 $\phi(x): \mathcal{X} \rightarrow \mathcal{H}$ 使得对所有 $x_i, x_j \in \mathcal{X},$ 函数 $K(x_i, x_j)$ 满足条件 $K(x_i, x_j)=\phi(x_i)^T \cdot \phi(x_j)$ 则称 $K(x_i, x_j)$ 为核函数, $\phi(x)$ 为映射函数, 式中 $\phi(x_i) \cdot \phi(x_j)$ 为 $\phi(x_i)$ 和 $\phi(x_j)$ 的内积。

给核函数$K(x_i,x_j)$定的情况下，可以利用解线性问题的方法求解非线性问题的支持向量。常用的核函数：

多项式核函数(polynomial kernel function) $K(x, z)=(x \cdot z+1)^{p}$
高斯核函数(guassian kernel function)

$K(x, z)=\exp \left(-\frac{\|x-z\|^{2}}{2 \sigma^{2}}\right)$

3.1 非线性支持向量机

利用核技巧可以很简单地把线性支持向量机扩展到非线性支持向量机，只需将线性支持向量机中的內积换成核函数即可。

选取合适的核函数$K(x_i,x_j)$和参数$C$，构造最优化问题：

$\min _{\alpha} \ \frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_{i} \alpha_{j} y_{i} y_{j} K(x_i,x_j) - \sum_{i=1}^{m} \alpha_{i} \\ \begin{array}{ll} \text { s.t. } & \sum_{i=1}^{m} \alpha_{i} y_{i}=0 \\ & \alpha_{i} \geqslant 0, \quad i=1,2, \ldots, m \end{array}$

再利用现成的二次规划问题求解算法或者SMO算法求得最优解$\alpha^*$。

选择一个$\alpha^*$满足

$0<{\alpha}_{j}^*<C$

的分量${\alpha}_{j}^*$ , 计算：

$b^*=y_{j}-\sum_{i \in S V} \alpha^*_{i} y_{i} K\left(x_{j}, x_{i}\right)$

构造决策函数：

$f(x)=\operatorname{sign}\left(\sum_{i \in S V} \alpha^*_{i} y_{i} K\left(x_{j}, x_{i}\right)+b^*\right)$