10.7 SVM优化问题#
经过前面几节内容的介绍，我们已经知道了支持向量机背后的原理。为了求解SVM中的目标函数，我们还在前面两节内容中陆续介绍了拉格朗日乘数法和对偶性问题。接下来，将开始正式介绍SVM的求解过程。同时，为了便于各位读者循序渐进地了解整个求解过程，下面我们会依次介绍硬间隔和软间隔中目标函数的求解步骤。
10.7.1 构造硬间隔广义拉格朗日函数#
由10.3节内容可知，SVM硬间隔最终的优化目标为[1]
$$ \begin{aligned} & \underset{w,b}{\mathop{\min }}\,\frac{1}{2}||w|{{|}^{2}}\\[2ex] \text{s}.\text{t}.\ &{{y}^{(i)}}({{w}^{T}}{{x}^{(i)}}+b)\ge 1,i=1,2,...m \end{aligned}\tag{10-64} $$由此可以得到广义的拉格朗日函数为
$$ \mathcal{L}(w,b,\alpha )=\frac{1}{2}||w|{{|}^{2}}-\sum\limits_{i=1}^{m}{{{\alpha }_{i}}}\left[ {{y}^{(i)}}({{w}^{T}}{{x}^{(i)}}+b)-1 \right]\tag{10-65} $$其中${{\alpha }_{i}}\ge 0$为拉格朗日乘子，并且同时记为
$$ {{g}_{i}}(w)=-{{y}^{(i)}}({{w}^{T}}{{x}^{(i)}}+b)+1\le 0\tag{10-66} $$进一步可得原始问题的对偶优化问题为
$$ {{d}^{*}}=\underset{\alpha ,{{\alpha }_{i}}\ge 0}{\mathop{\max }}\,\underset{w,b}{\mathop{\min }}\,\mathcal{L}(w,b,\alpha )\tag{10-67} $$所以，为了求得对偶问题的解，需要按照式(10-67)中的顺序进行。
1. 关于参数$w$和$b$求$\mathcal{L}$的极小值$W(\alpha )$
为了求解式(10-67)中的对偶优化问题，首先需要最小化式(10-65)，即分别对$w$和$b$求偏导数并令其为0，有
$$ \frac{\partial \mathcal{L}}{\partial w}=w-\sum\limits_{i=1}^{m}{{{\alpha }_{i}}}{{y}^{(i)}}{{x}^{(i)}}=0 \tag{10-68} $$$$ \frac{\partial \mathcal{L}}{\partial b}=-\sum\limits_{i=1}^{m}{{{\alpha }_{i}}}{{y}^{(i)}}=0\tag{10-69} $$进一步有
$$ w=\sum\limits_{i=1}^{m}{{{\alpha }_{i}}}{{y}^{(i)}}{{x}^{(i)}}\tag{10-70} $$到此便得到了权重$w$的解析表达式，而它对于理解SVM中核函数的原理有着重要的作用。接着将式(10-69)和式(10-70)代入式(10-65)可得
$$ W(\alpha )=\underset{w,b}{\mathop{\min }}\,\mathcal{L}(w,b,\alpha )=\sum\limits_{i=1}^{m}{{{\alpha }_{i}}}-\frac{1}{2}\sum\limits_{i,j=1}^{m}{{{y}^{(i)}}}{{y}^{(j)}}{{\alpha }_{i}}{{\alpha }_{j}}{{({{x}^{(i)}})}^{T}}{{x}^{(j)}}\tag{10-71} $$化简得到式(10-71)的具体步骤为
$$ \begin{aligned} \mathcal{L}(w,b,\alpha )&=\frac{1}{2}{{w}^{T}}w-\sum\limits_{i=1}^{m}{{{\alpha }_{i}}}\left[ {{y}^{(i)}}({{w}^{T}}{{x}^{(i)}}+b)-1 \right] \\[1ex] & =\frac{1}{2}{{w}^{T}}w-\sum\limits_{i=1}^{m}{{{\alpha }_{i}}}{{y}^{(i)}}{{w}^{T}}{{x}^{(i)}}-\sum\limits_{i=1}^{m}{{{\alpha }_{i}}}{{y}^{(i)}}b+\sum\limits_{i=1}^{m}{{{\alpha }_{i}}} \\[1ex] & =\frac{1}{2}{{w}^{T}}w-{{w}^{T}}\sum\limits_{i=1}^{m}{{{\alpha }_{i}}}{{y}^{(i)}}{{x}^{(i)}}-b\sum\limits_{i=1}^{m}{{{\alpha }_{i}}}{{y}^{(i)}}+\sum\limits_{i=1}^{m}{{{\alpha }_{i}}} \end{aligned}\tag{10-72} $$将式(10-69)和式(10-70)代入式(10-72)可得
$$ \begin{aligned} W(\alpha )&=\frac{1}{2}{{w}^{T}}w-{{w}^{T}}w+\sum\limits_{i=1}^{m}{{{\alpha }_{i}}} \\[1ex] & =\sum\limits_{i=1}^{m}{{{\alpha }_{i}}}-\frac{1}{2}{{w}^{T}}w \\[1ex] & =\sum\limits_{i=1}^{m}{{{\alpha }_{i}}}-\frac{1}{2}\sum\limits_{i,j=1}^{m}{{{\alpha }_{i}}}{{\alpha }_{j}}{{y}^{(i)}}{{y}^{(j)}}{{({{x}^{(i)}})}^{T}}{{x}^{(j)}} \end{aligned}\tag{10-73} $$至此，便得到了参数$w$的解析式。
2. 关于参数$\alpha$求$W(\alpha)$的极大值
由式(10-71)可以得出如下优化问题
$$ \begin{aligned} & \underset{\alpha }{\mathop{\max }}\,\ W(\alpha )=\underset{\alpha }{\mathop{\max }}\,\sum\limits_{i=1}^{m}{{{\alpha }_{i}}}-\frac{1}{2}\sum\limits_{i,j=1}^{m}{{{y}^{(i)}}}{{y}^{(j)}}{{\alpha }_{i}}{{\alpha }_{j}}{{({{x}^{(i)}})}^{T}}{{x}^{(j)}} \\[1ex] \text{s}.\text{t}.\ \ &{{\alpha }_{i}}\ge 0,i=1,...,m \\[2ex] & \sum\limits_{i=1}^{m}{{{\alpha }_{i}}}{{y}^{(i)}}=0 \end{aligned}\tag{10-74} $$之所以式(10-69)会成为约束条件，是因为$W(\alpha)$是通过式(10-68)和式(10-69)求解得到，并且是$W(\alpha)$存在的前提。
进一步，假设${{\alpha }^{*}}={{(\alpha _{1}^{*},\alpha _{2}^{*},...,\alpha _{m}^{*})}^{T}}$为对偶优化问题的解，那么为了使对偶优化问题与原始优化问题同解需要满足以下KKT条件
$$ \frac{\partial }{\partial w}\mathcal{L}({{w}^{*}},{{b}^{*}},{{\alpha }^{*}})={{w}^{*}}-\sum\limits_{i=1}^{m}{\alpha _{i}^{*}}{{y}^{(i)}}{{x}^{(i)}}=0\tag{10-75} $$$$ \frac{\partial }{\partial b}\mathcal{L}({{w}^{*}},{{b}^{*}},{{\alpha }^{*}})=-\sum\limits_{i=1}^{m}{\alpha _{i}^{*}}{{y}^{(i)}}=0\tag{10-76} $$$$ \alpha _{i}^{*}{{g}_{i}}({{w}^{*}})=\alpha _{i}^{*}\left[ {{y}^{(i)}}({{w}^{*}}\cdot {{x}^{(i)}}+{{b}^{*}})-1 \right]=0,\ \ \ i=1,2,...,,m\tag{10-77} $$$$ {{g}_{i}}({{w}^{*}})=-{{y}^{(i)}}({{w}^{*}}\cdot {{x}^{(i)}}+{{b}^{*}})+1\leq 0,\ \ i=1,2,...,m\tag{10-78} $$$$ \alpha _{i}^{*}\ge 0,\ \ i=1,2,...,m\tag{10-79} $$根据式(10-75)可得
$$ {{w}^{*}}=\sum\limits_{i=1}^{m}{\alpha _{i}^{*}}{{y}^{(i)}}{{x}^{(i)}}\tag{10-80} $$从式(10-80)可以看出，至少存在一个$\alpha _{j}^{*}>0$。因为如果所有的$\alpha _{i}^{*}$均为0，则由式(10-80)可知此时的${{w}^{*}}$也为0，而这显然不是原始优化问题的解[2]。
同时，由式(10-77)可知，若存在$\alpha _{j}^{*}>0$，则必有
$$ {{y}^{(j)}}({{w}^{*}}\cdot {{x}^{(j)}}+{{b}^{*}})=1\tag{10-81} $$根据式(10-81)可知，此时的样本点${{x}^{(j)}}$是一个支持向量，而这也显示出一个重要性质，即超平面仅仅与支持向量有关。
进一步，将式(10-80)代入式(10-81)并注意${{({{y}^{(j)}})}^{2}}=1$可得
$$ {{b}^{*}}={{y}^{(j)}}-\sum\limits_{i=1}^{m}{\alpha _{i}^{*}}{{y}^{(i)}}({{x}^{(i)}}\cdot {{x}^{(j)}})\tag{10-82} $$综上所述，对于任意给定线性可分数据集，首先可以根据式(10-74)中的优化问题求解得到${{\alpha }^{*}}$，然后利用式(10-80)和式(10-82)分别求解得到${{w}^{*}}$和${{b}^{*}}$，最后便可得到分离超平面。
10.7.2 硬间隔求解计算示例#
为了使各位读者更加清楚SVM中硬间隔决策面的求解步骤，下面我们将以一个实际的数据集进行计算示例。现有数据集一共包含4个样本点，其中${{x}^{(1)}}={{(1,3)}^{T}}$和${{x}^{(2)}}={{(3,0)}^{T}}$为负样本，${{x}^{(3)}}={{(3,5)}^{T}}$和${{x}^{(4)}}={{(2,7)}^{T}}$为正样本。黑色实线为决策面，黑色虚线为间隔边界，带圈的样本点为支持向量，如图10-13所示。
由给定数据集及式(10-74)可知，对偶问题为
$$ \begin{aligned} & \underset{\alpha }{\mathop{\max }}\,\sum\limits_{i=1}^{4}{{{\alpha }_{i}}}-\frac{1}{2}\sum\limits_{i,j=1}^{4}{{{y}^{(i)}}}{{y}^{(j)}}{{\alpha }_{i}}{{\alpha }_{j}}{{({{x}^{(i)}})}^{T}}{{x}^{(j)}} \\[1ex] & =({{\alpha }_{1}}+{{\alpha }_{2}}+{{\alpha }_{3}}+{{\alpha }_{4}})-\frac{1}{2}(10\alpha _{1}^{2}+9\alpha _{2}^{2}+34\alpha _{3}^{2}+53\alpha _{4}^{2}+6{{\alpha }_{1}}{{\alpha }_{2}} \\[1ex] & -36{{\alpha }_{1}}{{\alpha }_{3}}-46{{\alpha }_{1}}{{\alpha }_{4}}-18{{\alpha }_{2}}{{\alpha }_{3}}-12{{\alpha }_{2}}{{\alpha }_{4}}+82{{\alpha }_{3}}{{\alpha }_{4}}) \\[1ex] \text{s}.\text{t}.\ \ &{{\alpha }_{i}}\ge 0,\ i=1,2,3,4 \\[1ex] &-{{\alpha }_{1}}-{{\alpha }_{2}}+{{\alpha }_{3}}+{{\alpha }_{4}}=0 \\ \end{aligned}\tag{10-83} $$注意：$\left\langle x+y,x+y \right\rangle =\left\langle x,x \right\rangle +\left\langle x,y \right\rangle +\left\langle y,x \right\rangle +\left\langle y,y \right\rangle $
此时由约束条件可知${{\alpha }_{1}}={{\alpha }_{3}}+{{\alpha }_{4}}-{{\alpha }_{2}}$，将其代入目标函数并记为
$$ \varphi ({{\alpha }_{2}},{{\alpha }_{3}},{{\alpha }_{4}})=2{{\alpha }_{3}}+2{{\alpha }_{4}}-\frac{13}{2}\alpha _{2}^{2}-4\alpha _{3}^{2}-\frac{17}{2}\alpha _{4}^{2} -2{{\alpha }_{2}}{{\alpha }_{3}}-10{{\alpha }_{2}}{{\alpha }_{4}}-10{{\alpha }_{3}}{{\alpha }_{4}}\tag{10-84} $$对$\alpha_2$、$ \alpha_3$、$\alpha_4$分别求偏导并令其为0，可得
$$ \begin{cases} \frac{\partial \varphi }{\partial {{\alpha }_{2}}}=-13{{\alpha }_{2}}-2{{\alpha }_{3}}-10{{\alpha }_{4}}=0 \\[1ex] \frac{\partial \varphi }{\partial {{\alpha }_{3}}}=2-2{{\alpha }_{2}}-8{{\alpha }_{3}}-10{{\alpha }_{4}}=0 \\[1ex] \frac{\partial \varphi }{\partial {{\alpha }_{4}}}=2-10{{\alpha }_{2}}-10{{\alpha }_{3}}-17{{\alpha }_{4}}=0 \end{cases}\tag{10-85} $$不过根据式(10-85)中的3个等式联立求解后发现，同时满足这3个式子的解并不存在，也就是说最终的解只可能在约束条件的边界处产生，即不考虑一些约束条件。因此，在式(10-85)中需要考虑如下边界情况：
(1) 当$\alpha_2=0$时，根据式(10-85)中后两个等式可求得${{\alpha }_{4}}=-1/9<0$不满足式(10-83)中的约束条件。
(2) 当$\alpha_3=0$时，根据式(10-85)中第1个和第3个等式可求得$\alpha_2<0$，也不满足约束条件。
(3) 当$\alpha_4=0$时，根据式(10-85)中前两个等式求解后发现同样不满足约束条件。
(4) 最后，只有当$\alpha_2=0$和$\alpha_4=0$时，才能求得满足约束条件的解，即此时${{\alpha }_{1}}^{*}=0.25,{{\alpha }_{2}}^{*}=0,{{\alpha }_{3}}^{*}=0.25,{{\alpha }_{4}}^{*}=0$。对于其它情况，读者可以自行验算。
进一步，根据上述求得的结果通过式(10-80)便可求得决策面中的$w$为
$$ {{w}^{*}}=-\frac{1}{4}\cdot (1,3)+\frac{1}{4}\cdot (3,5)=(\frac{1}{2},\frac{1}{2})\tag{10-86} $$同时，根据式(10-82)并任取${{\alpha }_{1}}$和${{\alpha }_{3}}$中的一个作为${{\alpha }_{j}}$即可求得$b$为
$$ {{b}^{*}}=-1-(-\frac{1}{4}\cdot 10+\frac{1}{4}\cdot 18)=-3\tag{10-87} $$最后，可以得到决策面方程为
$$ \frac{1}{2}{{x}_{1}}+\frac{1}{2}{{x}_{2}}-3=0\tag{10-88} $$10.7.3 构造软间隔广义拉格朗日函数#
由10.4节的内容可知，SVM软间隔最终的优化目标为
$$ \begin{aligned} & \underset{w,b,\xi }{\mathop{\min }}\,\frac{1}{2}||w|{{|}^{2}}+C\sum\limits_{i=1}^{m}{{{\xi }_{i}}} \\[2ex] \text{s}.\text{t}.\ \ & {{y}^{(i)}}({{w}^{T}}{{x}^{(i)}}+b)\ge 1-{{\xi }_{i}},\ \ {{\xi }_{i}}\ge 0,\ i=1,2,...m \\ \end{aligned}\tag{10-89} $$由此可以得到广义的拉格朗日函数为[2]
$$ \mathcal{L}(w,b,\xi ,\alpha ,r)=\frac{1}{2}||w|{{|}^{2}}+C\sum\limits_{i=1}^{m}{{{\xi }_{i}}}-\sum\limits_{i=1}^{m}{{{\alpha }_{i}}}\left[ {{y}^{(i)}}({{w}^{T}}{{x}^{(i)}}+b)-1+{{\xi }_{i}} \right]-\sum\limits_{i=1}^{m}{{{r}_{i}}{{\xi }_{i}}}\tag{10-90} $$其中${{\alpha }_{i}}\ge 0$和${{r}_{i}}\ge 0$为拉格朗日乘子，并且同时记
$$ \begin{cases} {{g}_{i}}(w)=-{{y}^{(i)}}({{w}^{T}}{{x}^{(i)}}+b)+1-{{\xi }_{i}}\le 0 \\[2ex] {{h}_{i}}(\xi )=-{{\xi }_{i}}\le 0;\ \ i=1,2,...,m \\ \end{cases}\tag{10-91} $$进一步可以得到原始问题的对偶优化问题为
$$ {{d}^{*}}=\underset{\alpha ,r}{\mathop{\max }}\,\underset{w,b,\xi }{\mathop{\min }}\,\mathcal{L}(w,b,\xi ,\alpha ,r)\tag{10-92} $$所以，为了求得对偶问题的解，需要按照式(10-92)中的顺序进行。
1. 关于参数$w$、$b$、$\xi$ 求$\mathcal{L}$ 的极小值$W(\alpha,r)$
首先需要最小化式(10-90)，即分别对$w$、$b$、$\xi$ 求偏导数并令其为0，有
$$ \frac{\partial \mathcal{L}}{\partial w}=w-\sum\limits_{i=1}^{m}{{{\alpha }_{i}}}{{y}^{(i)}}{{x}^{(i)}}=0\tag{10-93} $$$$ \frac{\partial \mathcal{L}}{\partial b}=-\sum\limits_{i=1}^{m}{{{\alpha }_{i}}}{{y}^{(i)}}=0\tag{10-94} $$$$ \frac{\partial \mathcal{L}}{\partial {{\xi }_{i}}}=C-{{\alpha }_{i}}-{{r}_{i}}=0 \tag{10-95} $$进一步有
$$ w=\sum\limits_{i=1}^{m}{{{\alpha }_{i}}}{{y}^{(i)}}{{x}^{(i)}}\tag{10-96} $$$$ \sum\limits_{i=1}^{m}{{{\alpha }_{i}}}{{y}^{(i)}}=0\tag{10-97} $$$$ C-{{\alpha }_{i}}-{{r}_{i}}=0\tag{10-98} $$接着，将式(10-96)~式(10-98)代入式(10-90)，有
$$ \begin{aligned} W(\alpha ,r)&=\frac{1}{2}{{w}^{T}}w+C\sum\limits_{i=1}^{m}{{{\xi }_{i}}}-{{w}^{T}}w+\sum\limits_{i=1}^{m}{{{\alpha }_{i}}}-\sum\limits_{i=1}^{m}{{{\alpha }_{i}}}{{\xi }_{i}}-\sum\limits_{i=1}^{m}{{{r}_{i}}}{{\xi }_{i}} \\[1ex] & =\sum\limits_{i=1}^{m}{{{\alpha }_{i}}}-\frac{1}{2}{{w}^{T}}w+\sum\limits_{i=1}^{m}{{{\xi }_{i}}}\left( C-{{\alpha }_{i}}-{{r}_{i}} \right) \\[1ex] & =\sum\limits_{i=1}^{m}{{{\alpha }_{i}}}-\frac{1}{2}{{w}^{T}}w \end{aligned}\tag{10-99} $$此时可以发现，式(10-99)化简后$r$已经消去了。
2. 关于参数$\alpha$求$W(\alpha)$的极大值
由式(10-99)求$\alpha$ 的极大值可以得出如下优化问题
$$ \underset{\alpha }{\mathop{\max }} \ W(\alpha )=\underset{\alpha }{\mathop{\max }}\,\ \sum\limits_{i=1}^{m}{{{\alpha }_{i}}}-\frac{1}{2}{{w}^{T}}w\tag{10-100} $$$$ \text{s}.\text{t}.\;\;\;\;\;\sum\limits_{i=1}^{m}{{{\alpha }_{i}}}{{y}^{(i)}}=0\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\tag{10-101} $$$$ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;C-{{\alpha }_{i}}-{{r}_{i}}=0,\ \ i=1,2,...,m\tag{10-102} $$$$ \;\;\;\;\;\;\;\;\;{{\alpha }_{i}}\ge 0,\;\; i=1,2,...,m\tag{10-103} $$$$ \;\;\;\;\;\;\;\;\;{{r}_{i}}\ge 0,\;\;i=1,2,...,m\tag{10-104} $$接着，将式(10-104)代入式(10-102)便可得到化简后的约束条件
$$ 0\le {{\alpha }_{i}}\le C\tag{10-105} $$最后便可得到最终的对偶优化问题
$$ \begin{aligned} & \underset{\alpha }{\mathop{\max }}\sum_{i=1}^m\,{{\alpha }_{i}}-\frac{1}{2}\sum\limits_{i,j=1}^{m}{{{y}^{(i)}}{{y}^{(j)}}{{\alpha }_{i}}{{\alpha }_{j}}}{{({{x}^{(i)}})}^{T}}{{x}^{(j)}} \\[1ex] \text{s}.\text{t}.\ \ &0\le {{\alpha }_{i}}\le C,\ i=1,2,...,m \\[2ex] &\sum\limits_{i=1}^{m}{{{\alpha }_{i}}}{{y}^{(i)}}=0 \\ \end{aligned}\tag{10-106} $$从式(10-106)可以发现，SVM软间隔的对偶优化问题同硬间隔的对偶优化问题仅仅在约束问题上发生了变化。
现在假设${{\alpha }^{*}}={{(\alpha _{1}^{*},\alpha _{2}^{*},...,\alpha _{m}^{*})}^{T}}$为对偶优化问题(10-106)的解，那么为了使对偶优化问题与原始优化问题同解则需要满足以下KKT条件
$$ \frac{\partial }{\partial w}\mathcal{L}({{w}^{*}},{{b}^{*}},{{\xi }^{*}},{{\alpha }^{*}},{{r}^{*}})={{w}^{*}}-\sum\limits_{i=1}^{m}{\alpha _{i}^{*}}{{y}^{(i)}}{{x}^{(i)}}=0\tag{10-107} $$$$ \frac{\partial }{\partial b}\mathcal{L}({{w}^{*}},{{b}^{*}},{{\xi }^{*}},{{\alpha }^{*}},{{r}^{*}})=-\sum\limits_{i=1}^{m}{\alpha _{i}^{*}}{{y}^{(i)}}=0\tag{10-108} $$$$ \frac{\partial }{\partial \xi }\mathcal{L}({{w}^{*}},{{b}^{*}},{{\xi }^{*}},{{\alpha }^{*}},{{r}^{*}})=C-{{\alpha }^{*}_i}-{{r}^{*}_i}=0\tag{10-109} $$$$ \alpha _{i}^{*}{{g}_{i}}({{w}^{*}})=\alpha _{i}^{*}\left[ {{y}^{(i)}}({{w}^{*}}\cdot {{x}^{(i)}}+{{b}^{*}})-1+\xi _{i}^{*} \right]=0,\;\;\; i=1,2,...,,m\tag{10-110} $$$$ r_{i}^{*}{{h}_{i}}({{\xi }^{*}})=r_{i}^{*}\xi _{i}^{*}=0;\;\;\; i=1,2,...,m\tag{10-111} $$$$ {{g}_{i}}({{w}^{*}})=-{{y}^{(i)}}({{w}^{*}}\cdot {{x}^{(i)}}+{{b}^{*}})+1-{{\xi }_{i}}^{*}\le 0,\ ;\;\;i=1,2,...,m\tag{10-112} $$$$ {{h}_{i}}({{\xi }^{*}})=-{{\xi }_{i}}\le 0;\;\;\; i=1,2,...,m\tag{10-113} $$$$ \alpha _{i}^{*}\ge 0,\ \ r_{i}^{*}\ge 0;\;\;\; i=1,2,...,m\tag{10-114} $$因此，根据式(10-107)可得
$$ {{w}^{*}}=\sum\limits_{i=1}^{m}{\alpha _{i}^{*}}{{y}^{(i)}}{{x}^{(i)}}\ \ \ i=1,2,...,m\tag{10-115} $$从式(10-115)可以看出，至少存在一个$0<\alpha _{j}^{*}\le C$。因为如果所有的$\alpha_i$均为0，则由式(10-115)可知此时的${{w}^{*}}$同样为0，而这显然不是原始优化问题的解。进一步，若存在 $0 < \alpha _{j}^{*} < C$，则由式(10-109)可知，此时对应的 $r_{j}^{*} > 0$，再由式(10-111)可知，此时必有 $\xi^{\ast}_j=0$，所以最后由式(10-110)可知，此时必有
$$ {{y}^{(j)}}({{w}^{*}}\cdot {{x}^{(j)}}+{{b}^{*}})=1\tag{10-116} $$进一步，将式(10-115)代入式(10-116)可得
$$ {{b}^{*}}={{y}^{(j)}}-\sum\limits_{i=1}^{m}{\alpha _{i}^{*}}{{y}^{(i)}}({{x}^{(i)}}\cdot {{x}^{(j)}})\tag{10-117} $$综上所述，对于任意给定数据集，首先可以根据式(10-106)中的优化问题求解得到${{\alpha }^{*}}$，然后利用式(10-115)和式(10-117)分别求解得到${{w}^{*}}$和${{b}^{*}}$，最后即可得到分离超平面。
10.7.4 软间隔中的支持向量#
在本章伊始，以及10.7.1节和10.7.2节内容中，我们都提到了“支持向量”这个词，并且还介绍了位于间隔边界上的样本点就是支持向量。不过到底支持向量是什么呢？也就是说，能够影响决策面形成样本点就是支持向量。例如从图10-13可以看出，对于影响最后决策面形成的只有${{x}^{(1)}}$和${{x}^{(3)}}$这两个样本点。同时，从硬间隔的定义可以看出，在求解得到决策面后所有样本点的分布只存在两种情况。第1种是位于间隔边界上，而第2种则是在间隔边界以外，因此，在硬间隔中影响决策面形成的就只有位于间隔边界上的样本点，即支持向量。
但是从软间隔的定义可以看出，由于软间隔允许样本点被错误分类，并且其程度可通过惩罚系数$C$进行控制，因此可以得出在软间隔中，$C$ 可以影响决策面的位置，并且支持向量不仅只会位于间隔边界上，如图10-14所示。
从图10-14可以看出，在新加入一个样本点以后为了增强模型最终的泛化能力SVM并没有在样本点 $x^{(3)}$ 和 $x^{(5)}$ 之间建立一个超平面。软间隔目标函数在求解过程将${{x}^{(3)}}$和${{x}^{(5)}}$这两个样本点都划分到了间隔边界以内，并且样本点$x^{(5)}$还被错误地划分到了另外一个类别中（当然${{x}^{(3)}}$和${{x}^{(5)}}$本身也可能是异常样本），因此可以得出，在SVM软间隔的建模过程中，影响决策面位置的除了位于间隔边界上的样本还有位于间隔边界内的样本点，所以这些都被称为支持向量。
同时，由式(10-109)~式(10-112)可知，当$0 < \alpha_i < C$时，则$\xi_i=0$，此时支持向量${{x}^{(i)}}$将位于间隔边界上，即图10-14中的样本点$x^{(2)}$和$x^{(4)}$； 当$\alpha_i=C$，$0 < \xi_i < 1$时，此时支持向量$x^{(i)}$将位于间隔边界与决策面之间，即$x^{(3)}$和$x^{(5)}$； 当$\alpha_i=C$，$\xi_i=1$时，此时支持向量$x^{(i)}$将位于决策面上； 当$\alpha_i=C$，$\xi_i > 1$时，此时支持向量$x^{(i)}$将位于决策面的另一侧[2]。进一步，可以总结得到
$$ \begin{aligned} &{{\alpha }_{i}}=0 \Rightarrow {{y}^{(i)}}({{w}^{T}}{{x}^{(i)}}+b)\ge 1 \\[1ex] &{{\alpha }_{i}}=C\Rightarrow {{y}^{(i)}}({{w}^{T}}{{x}^{(i)}}+b)\le 1 \\[1ex] &0 < {{\alpha }_{i}} < C\Rightarrow {{y}^{(i)}}({{w}^{T}}{{x}^{(i)}}+b)=1 \end{aligned}\tag{10-118} $$10.7.5 小结#
在本节中，我们首先介绍了在求解SVM模型中如何构造硬间隔的广义的拉格朗日函数及其对应的对偶问题，接着通过求解对偶问题中$\mathcal{L}(w,b,\alpha)$的极小值得到了$w$的计算解析式，需要提醒的是，$w$的表达式也是理解SVM核函数的关键，然后以一个实际的示例介绍了SVM硬间隔的求解过程，最后，我们还介绍了如何构造软间隔中的拉格朗日函数及软间隔中的支持向量，而SVM软间隔的实际求解过程将在10.9节中进行介绍。