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)中需要考虑如下边界情况：