第9.7节 SVM优化问题
各位朋友大家好，欢迎来到月来客栈，我是掌柜空字符。
本期推送内容目录如下，如果本期内容对你有所帮助，欢迎点赞、转发支持掌柜！
9.7 SVM优化问题 9.7.1 构造硬间隔广义拉格朗日函数 9.7.2 硬间隔求解计算示例 9.7.3 构造软间隔广义拉格朗日函数 9.7.4 软间隔中的支持向量 9.7.5 小结 引用
9.7 SVM优化问题
经过前面几节内容的介绍，我们已经知道了支持向量机背后的原理。同时，为了求解SVM中的目标函数，笔者还在前面两节内容中陆续介绍了拉格朗日乘数法和对偶性问题。接下来，将开始正式介绍SVM的求解过程。同时，为了便于各位读者循序渐进地了解整个求解过程，下面笔者会依次介绍硬间隔和软间隔中目标函数的求解步骤。
9.7.1 构造硬间隔广义拉格朗日函数
由9.2节的内容可知，SVM硬间隔最终的优化目标为[1]
由此可以得到广义的拉格朗日函数为
其中为拉格朗日乘子，并且同时记为
进一步可得原始问题的对偶优化问题为
所以，为了求得对偶问题的解，需要按照式(9.79)中的顺序进行。
1. 关于参数和求的极小值
为了求解式(9.79)中的对偶优化问题，首先需要最小化式(9.77)，即分别对和求偏导数并令其为0，有
进一步有
到此便得到了权重的解析表达式，而它对于理解SVM中核函数的利用有着重要的作用。接着将式(9.80)~式(9.82)代入式(9.77)可得
化简得到式(9.83)的具体步骤为
将式(9.80)~式(9.82)代入式(9.84)可得
至此，便得到了参数的解析式。
2. 关于参数求的极大值
由式(9.83)可以得出如下优化问题
之所以式(9.81)会成为约束条件，是因为是通过式(9.80)和式(9.81)求解得到，并且是存在的前提。
进一步，假设为对偶优化问题的解，那么为了使对偶优化问题与原始优化问题同解需要满足以下KKT条件
根据式(9.87)可得
从式(9.92)可以看出，至少存在一个。因为如果所有的均为0，则由式(9.92)可知此时的也为0，而这显然不是原始优化问题的解[2]。
同时，由式(9.89)可知，若存在，则必有
根据式(9.93)可知，此时的样本点是一个支持向量，而这也显示出一个重要性质，即超平面仅仅与支持向量有关。
进一步，将式(9.92)代入式(9.93)并注意可得
综上所述，对于任意给定线性可分数据集，首先可以根据式(9.86)中的优化问题求解得到，然后利用式(9.92)和式(9.94)分别求解得到和，最后便可得到分离超平面。
9.7.2 硬间隔求解计算示例
为了使各位读者更加清楚SVM中硬间隔决策面的求解步骤，下面笔者将以一个实际的数据集进行计算示例。现有数据集一共包含7个样本点，其中和为负样本，和为正样本。黑色实线为决策面，黑色虚线为间隔边界，带圈的样本点为支持向量，如图9-12所示。
由给定数据集及式(9.86)可知，对偶问题为
注意：
此时由约束条件可知，将其代入目标函数并记为
对、、分别求偏导并令其为0，可得
不过根据式(9.97)中的3个等式联立求解后发现，同时满足这3个式子的解并不存在，也就是说最终的解只可能在约束条件的边界处产生 ，即不考虑一些约束条件。因此，在式(9.97)中需要考虑如下边界情况：
为你认可的知识付费，欢迎订阅本专栏阅读更多优质内容！
(1) 当时，根据式(9.97)中后两个等式可求得不满足式(9.95)中的约束条件。