手推支持向量机02-硬间隔SVM-模型求解（引出对偶问题）

古城微笑少年丶 2023-02-28 04:02 29阅读 0赞

**目录**

1.写在前面

2.硬间隔SVM之模型求解

--------------------

# 1.写在前面 #

我们上一篇讲到了硬间隔SVM的最大间隔分类器模型的数学表示，其中样本点表示：![\\\{(x\_\{i\},y\_\{i\})\\\}\_\{i=1\}^\{N\},x\_\{i\}\\euro R^\{\\Phi \},y\_\{i\}\\euro \\\{-1,1\\\}][x_i_y_i_i_1_N_x_i_euro R_Phi _y_i_euro _-1_1] ，我们最后得到的是这样一个关于w，b的最小化问题（实际上是一个凸优化问题）以及约束st（有N个约束，是线性约束，是一个QP凸二次规划问题）。

![20200721220008660.png][]

# 2.硬间隔SVM之模型求解 #

在理想状态下（纬度低，样本N个数小），QP问题可以直接利用套件求解，实际情况下，我们通常称**上面问题是原问题（primal problem），我们会找到它的对偶问题（dual problem）**。既然是一个优化问题，我们最直接想法就是把它写做**拉格朗日乘子**。

![20200721221023857.png][]

那么这个最小化问题就可以直接转化为下面函数，这两个解是等价的。下图中最下面的优化问题，对w，b没有任何限制，我们**怎么判断这个无约束的优化函数和我们最开始的带约束的优化函数是等价的呢**？

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1N1eWViaXViaXU_size_16_color_FFFFFF_t_70][]

我们用一个蓝色的大圈表示（w,b）的一个集合，△是上图中的部分，右侧我们让△≤0，左侧让△>0。我们这样可以把这个（w,b）集合划分成两个部分。

我们分别讨论两个情况：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1N1eWViaXViaXU_size_16_color_FFFFFF_t_70 1][]

通过**先对λ求max，在对w，b求min，实际上把△>0所对应的（w,b）丢弃了**。这个优化问题妙就妙在最优解（w,b）一定出自△≤0这个区域的。这个地方并没有真正的证明，我们只是从式子上面去理解。

我们再看一下它的对偶问题，它的对偶问题就是maxmin函数。max针对的是λ，min针对的是w和b。我们把**上面两个函数（一个带约束，一个不带约束）称为原问题，下面的称为对偶问题。**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1N1eWViaXViaXU_size_16_color_FFFFFF_t_70 2][]

首先，我们看一下 ![minmax\\mathcal\{L\}][minmax_mathcal_L] 和 ![maxmin\\mathcal\{L\}][maxmin_mathcal_L] ，我们从直观上理解，我们对一个函数![minmax\\mathcal\{L\}][minmax_mathcal_L]先求最大值max，再求最小值min，它一定大于等于后面的![maxmin\\mathcal\{L\}][maxmin_mathcal_L]。![minmax\\mathcal\{L\}][minmax_mathcal_L] （凤尾）≥ ![maxmin\\mathcal\{L\}][maxmin_mathcal_L]（鸡头），这个就是我们说的“**宁为鸡头（鸡），不为凤尾（凤）**”，无论怎样鸡是肯定小于凤的，一个上界最小，一个下界最大。![minmax\\mathcal\{L\}][minmax_mathcal_L] （凤尾）> ![maxmin\\mathcal\{L\}][maxmin_mathcal_L]（鸡头）这个关系我们称为“**弱对偶关系**”，我们不仅要弱队伍关系，我们还想要“**强对偶关系**”![minmax\\mathcal\{L\}][minmax_mathcal_L] （凤尾）= ![maxmin\\mathcal\{L\}][maxmin_mathcal_L]（鸡头）。

我们知道我们要优化的函数是凸二次优化问题，目标函数是二次的，约束是线性的。这些条件会天然满足强对偶关系，也就是![minmax\\mathcal\{L\}][minmax_mathcal_L] （凤尾）= ![maxmin\\mathcal\{L\}][maxmin_mathcal_L]（鸡头）是成立的。也就是**原函数和对偶函数实际上是等价的**，证明这个地方也不再赘述。那么我们直接**求它的对偶函数（先对w,b求最小值，再对λ求最大值）**即可，可以先固定λ，针对w，b求min，这个是无约束的情况。

![20200721232436535.png][]

中间过程去掉，直接写结论：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1N1eWViaXViaXU_size_16_color_FFFFFF_t_70 3][]

最终我们的函数可以写成（红框内w带进去就是最小值）：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1N1eWViaXViaXU_size_16_color_FFFFFF_t_70 4][]

总结：**我们先把带约束问题，转化为无约束问题，通过强对偶关系将minmax转为maxmin，对w,b求min，最终我们求出来最小值，然后关于λ求最大值**，λ也是一个向量，![\\lambda = \\begin\{pmatrix\} \\lambda1\\\\ \\lambda2\\\\ .\\\\ \\lambda n\\\\ \\end\{pmatrix\}][lambda _ _begin_pmatrix_ _lambda1_ _lambda2_ ._ _lambda n_ _end_pmatrix]。

[x_i_y_i_i_1_N_x_i_euro R_Phi _y_i_euro _-1_1]: https://private.codecogs.com/gif.latex?%5C%7B%28x_%7Bi%7D%2Cy_%7Bi%7D%29%5C%7D_%7Bi%3D1%7D%5E%7BN%7D%2Cx_%7Bi%7D%5Ceuro%20R%5E%7B%5CPhi%20%7D%2Cy_%7Bi%7D%5Ceuro%20%5C%7B-1%2C1%5C%7D
[20200721220008660.png]: /images/20230209/9677939ef5ee43a1942dd18b99fce214.png
[20200721221023857.png]: /images/20230209/52bc854e904d4ddcbc4ca90f6d5320f0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1N1eWViaXViaXU_size_16_color_FFFFFF_t_70]: /images/20230209/b01ab065eb8c4fd38fdb3820133b6870.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1N1eWViaXViaXU_size_16_color_FFFFFF_t_70 1]: /images/20230209/e487ceaab01b441790395f53d01bdf7d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1N1eWViaXViaXU_size_16_color_FFFFFF_t_70 2]: /images/20230209/16dbe0ea8dd3494db9378ff8ba32fcf5.png
[minmax_mathcal_L]: https://private.codecogs.com/gif.latex?minmax%5Cmathcal%7BL%7D
[maxmin_mathcal_L]: https://private.codecogs.com/gif.latex?maxmin%5Cmathcal%7BL%7D
[20200721232436535.png]: /images/20230209/6af7ac0db66d4b199decabbf9636f5e0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1N1eWViaXViaXU_size_16_color_FFFFFF_t_70 3]: /images/20230209/a22fc2cba01d45a882a49c60b167e16b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1N1eWViaXViaXU_size_16_color_FFFFFF_t_70 4]: /images/20230209/7f8838535c2449e5bf6918eeb3d77904.png
[lambda _ _begin_pmatrix_ _lambda1_ _lambda2_ ._ _lambda n_ _end_pmatrix]: https://private.codecogs.com/gif.latex?%5Clambda%20%3D%20%5Cbegin%7Bpmatrix%7D%20%5Clambda1%5C%5C%20%5Clambda2%5C%5C%20.%5C%5C%20%5Clambda%20n%5C%5C%20%5Cend%7Bpmatrix%7D