支持向量机（SVM）中的对偶问题

待我称王封你为后i 2022-01-14 07:19 432阅读 0赞

### 前言 ###

在SVM中有一个求极小值的问题转换过程，转换为一个对偶问题，但是我不太清楚这个问题为什么可以转换，而且还不太清楚为什么这么转换？不太明确转换后有什么优点，写个文章来了解这些内容。

### 原始问题转换 ###

min ⁡ 1 2 ∣ ∣ w ∣ ∣ 2 s . t . y i ( x i + b ) > = 1 i=1,2...,n \\min \\quad \\frac\{1\}\{2\} ||w||^2 \\\\ s.t. \\quad y\_i(x\_i+b) >=1 \\qquad \\text\{i=1,2...,n\} min21∣∣w∣∣2s.t.yi(xi\+b)>=1i=1,2...,n  
拉格朗日乘子之后的公式为：  
 F ( w , b , a ) = 1 2 ∣ ∣ w ∣ ∣ 2 + ∑ i = 1 n a i \[ 1 − y i ( w x i + b ) \] s . t . a i > = 0 F(w,b,a)= \\frac\{1\}\{2\} ||w||^2+\\sum\_\{i=1\}^\{n\}a\_\{i\}\[1-y\_i(wx\_i+b)\] \\\\ s.t. \\quad a\_i>=0 F(w,b,a)=21∣∣w∣∣2\+i=1∑nai\[1−yi(wxi\+b)\]s.t.ai>=0  
优化问题为：  
 min ⁡ F ( w , b , a ) = 1 2 ∣ ∣ w ∣ ∣ 2 + ∑ i = 1 n a i \[ 1 − y i ( w x i + b ) \] \\min \\quad F(w,b,a)= \\frac\{1\}\{2\} ||w||^2+\\sum\_\{i=1\}^\{n\}a\_\{i\}\[1-y\_i(wx\_i+b)\] minF(w,b,a)=21∣∣w∣∣2\+i=1∑nai\[1−yi(wxi\+b)\]

*  有一个疑惑，为什么是 1 − y i ( w x i + b ) < = 0 1-y\_i(wx\_i+b)<=0 1−yi(wxi\+b)<=0?  
    这样可以把 a i > 0 a\_i>0 ai>0作为约束条件，小于0 乘以-1就可以非常方便的转换过去。

我们假设有一个最优解 w ∗ w^\* w∗，则得到最小值 f ( w ∗ ) = 1 2 ∣ ∣ w ∗ ∣ ∣ 2 f(w^\*)= \\frac\{1\}\{2\} ||w^\*||^2 f(w∗)=21∣∣w∗∣∣2，则会发现一些：  
 min ⁡ F ( w ∗ , b , a ) < = f ( w ∗ ) \\min \\quad F(w^\*,b,a)<= f(w^\*) minF(w∗,b,a)<=f(w∗)  
最优解 w ∗ w^\* w∗，使得 1 − y i ( w x ∗ + b ) < = 0 1-y\_i(wx^\*+b)<=0 1−yi(wx∗\+b)<=0，则 ∑ i = 1 n a i \[ 1 − y i ( w ∗ x i + b ) \] < = 0 \\sum\_\{i=1\}^\{n\}a\_\{i\}\[1-y\_i(w^\*x\_i+b)\]<=0 ∑i=1nai\[1−yi(w∗xi\+b)\]<=0，这里 a i > = 0 a\_i>=0 ai>=0，所以上述公式必然成立，但一般我们会把问题假设为如下所示：  
 max ⁡ a i > 0 F ( w , b , a ) = 1 2 ∣ ∣ w ∣ ∣ 2 + ∑ i = 1 n a i \[ 1 − y i ( w x i + b ) \] \\max\_\{a\_i>0\} \\quad F(w,b,a)= \\frac\{1\}\{2\} ||w||^2+\\sum\_\{i=1\}^\{n\}a\_\{i\}\[1-y\_i(wx\_i+b)\] ai>0maxF(w,b,a)=21∣∣w∣∣2\+i=1∑nai\[1−yi(wxi\+b)\]

因为有这种考虑：

*  满足约束条件 1 − y i ( w x i + b ) < = 0 1-y\_i(wx\_i+b)<=0 1−yi(wxi\+b)<=0，要想使得 max ⁡ a i > 0 F ( w , b , a ) = 1 2 ∣ ∣ w ∣ ∣ 2 \\max \\limits\_\{a\_i>0\} \\quad F(w,b,a)= \\frac\{1\}\{2\} ||w||^2 ai>0maxF(w,b,a)=21∣∣w∣∣2，则 ∑ i = 1 n a i \[ 1 − y i ( w x i + b ) \] = 0 \\sum\_\{i=1\}^\{n\}a\_\{i\}\[1-y\_i(wx\_i+b)\]=0 ∑i=1nai\[1−yi(wxi\+b)\]=0，这也是KKT条件之一。
 *  不满足约束条件， 1 − y i ( w x i + b ) > 0 1-y\_i(wx\_i+b)>0 1−yi(wxi\+b)>0，则 max ⁡ a i > 0 F ( w , b , a ) \\max \\limits\_\{a\_i>0\} \\quad F(w,b,a) ai>0maxF(w,b,a)可以是无穷大，也就无解了

为什么要 max ⁡ a i \\max \\limits\_\{a\_i\} aimax，而不是 min ⁡ a i \\min \\limits\_\{a\_i\} aimin？我觉得如果是求最小值，则有：

*  满足约束条件 1 − y i ( w x i + b ) < = 0 1-y\_i(wx\_i+b)<=0 1−yi(wxi\+b)<=0，要想使得 min ⁡ a i > 0 F ( w , b , a ) → − ∞ \\min \\limits\_\{a\_i>0\} \\quad F(w,b,a) \\to -\\infty ai>0minF(w,b,a)→−∞，则 a i → + ∞ a\_i \\to +\\infty ai→\+∞，无解
 *  不满足约束条件， 1 − y i ( w x i + b ) > 0 1-y\_i(wx\_i+b)>0 1−yi(wxi\+b)>0，则 min ⁡ a i > 0 F ( w , b , a ) = 1 2 ∣ ∣ w ∣ ∣ 2 \\min \\limits\_\{a\_i>0\} \\quad F(w,b,a)= \\frac\{1\}\{2\} ||w||^2 ai>0minF(w,b,a)=21∣∣w∣∣2，则 a i = 0 a\_i =0 ai=0

可以看出 min ⁡ a i \\min \\limits\_\{a\_i\} aimin是求解不了目标的，这只是我个人的理解，感兴趣的朋友可以自己去了解一下背后的数学知识。不过从另一个角度来分析：逼近。可能会有一些结果，从上面的一个公式来继续分析：  
 min ⁡ F ( w ∗ , b , a ) < = f ( w ∗ ) \\min \\quad F(w^\*,b,a)<= f(w^\*) minF(w∗,b,a)<=f(w∗)  
该公式说明存在满足约束条件的 w ∗ w^\* w∗，那这样 F ( w ∗ , b , a ) F(w^\*,b,a) F(w∗,b,a)只能去逼近这个 f ( w ∗ ) f(w^\*) f(w∗)，所以是求 F ( w ∗ , b , a ) F(w^\*,b,a) F(w∗,b,a)的最大值，也就是：  
 min ⁡ w i max ⁡ a i > 0 F ( w , b , a ) \\min\_\{w\_i\} \\max\_\{a\_i>0\} \\quad F(w,b,a) wiminai>0maxF(w,b,a)

先分析 max ⁡ a i > 0 F ( w , b , a ) \\max\_\{a\_i>0\} \\quad F(w,b,a) maxai>0F(w,b,a)，得到的结果是逼近 1 2 ∣ ∣ w ∣ ∣ 2 \\frac\{1\}\{2\} ||w||^2 21∣∣w∣∣2，然后再通过 min ⁡ w i 1 2 ∣ ∣ w ∣ ∣ 2 \\min\_\{w\_i\}\\frac\{1\}\{2\} ||w||^2 minwi21∣∣w∣∣2从而达到目的。我们最终的公式为：  
 min ⁡ w i max ⁡ a i > 0 F ( w , b , a ) = 1 2 ∣ ∣ w ∣ ∣ 2 + ∑ i = 1 n a i \[ 1 − y i ( w x i + b ) \] \\min\_\{w\_i\} \\max\_\{a\_i>0\} \\quad F(w,b,a)= \\frac\{1\}\{2\} ||w||^2+\\sum\_\{i=1\}^\{n\}a\_\{i\}\[1-y\_i(wx\_i+b)\] wiminai>0maxF(w,b,a)=21∣∣w∣∣2\+i=1∑nai\[1−yi(wxi\+b)\]  
 max ⁡ \\max max可以使得我们得到最接近 1 2 ∣ ∣ w ∣ ∣ 2 \\frac\{1\}\{2\} ||w||^2 21∣∣w∣∣2的 F ( w , b , a ) F(w,b,a) F(w,b,a)，然后再求 min ⁡ 1 2 ∣ ∣ w ∣ ∣ 2 \\min \\frac\{1\}\{2\} ||w||^2 min21∣∣w∣∣2，很多博客里称 min ⁡ x max ⁡ a i > 0 F ( w , b , a ) \\quad \\min \\limits\_x \\max \\limits\_\{a\_i>0\} F(w,b,a) xminai>0maxF(w,b,a)为原始问题，接下来就是求解该原始问题的对偶问题。

### 对偶问题 ###

于是我们可以转换问题为 m i n − m a x min-max min−max问题：  
 min ⁡ w max ⁡ a i > 0 1 2 ∣ ∣ w ∣ ∣ 2 + ∑ i = 1 n a i \[ 1 − y i ( w x i + b ) \] \\min\_\{w\} \\max\_\{a\_i>0\} \\quad \\frac\{1\}\{2\} ||w||^2+\\sum\_\{i=1\}^\{n\}a\_\{i\}\[1-y\_i(wx\_i+b)\] wminai>0max21∣∣w∣∣2\+i=1∑nai\[1−yi(wxi\+b)\]

对偶问题就是将min与max位置互换，为什么可以互换？确实是可以互换的，但是不太清楚原理，先直接放定理：若原始问题和对偶问题都有最优值，则对偶问题最优值 d ∗ d^∗ d∗小于或等于原始问题最优值 p ∗ p^∗ p∗。公式表示就是如下：  
 d ∗ = min ⁡ w max ⁡ a , b F ( w , a , b ) < = max ⁡ a , b min ⁡ w F ( w , a , b ) = p ∗ d^\*=\\min\_\{w\}\\max\_\{a,b\}F(w,a,b) <= \\max\_\{a,b\}\\min\_\{w\}F(w,a,b) =p^\* d∗=wmina,bmaxF(w,a,b)<=a,bmaxwminF(w,a,b)=p∗  
其实我是非常想学习这个对偶问题的转换，其相关知识涉及最优化理论、运筹学等数学知识，需要时间去研读。不过就这个问题继续转换，就是得到原问题的对偶问题，这中间的转换主要是：

*   min ⁡ w F ( w , b , a i ) \\min\_\{w\}F(w,b,a\_i) minwF(w,b,ai) 对w、b求偏导，偏导等于零，求极值，得到：  
     w = ∑ i a i y i x i ∑ i a y = 0 w=\\sum\_\{i\}a\_iy\_ix\_i \\\\ \\sum\_\{i\}ay=0 w=i∑aiyixii∑ay=0
 *  将w、b结果代入到原公式中得到：  
     m a x a i > 0 − 1 2 ∑ i ∑ j a i a j y i y j ( x i ∗ x j ) + ∑ i a i s . t . ∑ i a i y i = 0 a i > = 0 max\_\{a\_i>0\} -\\frac\{1\}\{2\}\\sum\_\{i\} \\sum\_\{j\}a\_\{i\}a\_\{j\}y\_\{i\}y\_\{j\}(x\_i \* x\_j) + \\sum\_\{i\}a\_i \\\\ s.t. \\sum\_i a\_iy\_i =0 \\\\ a\_i>=0 maxai>0−21i∑j∑aiajyiyj(xi∗xj)\+i∑ais.t.i∑aiyi=0ai>=0  
    在对这个函数求解，求解方法有SMO方法，也可以通过求极值方法，假设我们得到了 a a a的值，然后再通过

w = ∑ i a i y i x i w=\\sum\_\{i\}a\_iy\_ix\_i w=i∑aiyixi  
求解b 稍微复杂些，根据 y = w x + b y=wx+b y=wx\+b求的：  
 b = y j − ∑ i a i y i ( x i ∗ x j ) b = y\_j-\\sum\_\{i\}a\_iy\_i(x\_i\*x\_j) b=yj−i∑aiyi(xi∗xj)  
这里 y j y\_j yj是支持向量的点，并不是所有样本数据集，是 a j > 0 a\_j>0 aj>0的点，而且也不是只有一个，应该有多个，最后求解平均值作为b的值。

### 转换为对偶问题的优点 ###

*  对偶问题往往更易于求解  
    为什么这么讲呢？原本的函数是 m i n w m a x a , b min\_\{w\} max\_\{a,b\} minwmaxa,b变为了 m a x a , b m i n w max\_\{a,b\}min\_\{w\} maxa,bminw，这样 a , b a,b a,b的值可以用 w w w来替换，这样对求解方程方便。原问题的优化是一个二次规划问题，求解较麻烦，用拉格朗日乘子法转换后可以用smo等算法更简单地优化。
 *  自然引入核函数，推广到非线性分类问题的求解  
    由于转换后的假设函数主要由内积运算构成，可以使用核函数简化特征映射到高维空间后的内积运算，高效地求解非线性问题。

### 总结 ###

对偶问题还是比较难理解，本文没有去分析其原理，而且本文是基于一个min问题来看到对偶问题，如果是一个max问题，它的对偶问题如何，其实也是一样的，思想是换成了求上限，对上限求min，逼近真实值，大家可以看下参考博客的知乎，Cyber的回答，这篇文章会继续完善。

### 参考博客 ###

[深入理解SVM之对偶问题][SVM]  
[如何通俗地讲解对偶问题？尤其是拉格朗日对偶lagrangian duality？][lagrangian duality]  
[KKT 条件][KKT]  
[【分类战车SVM】第四话：拉格朗日对偶问题（原来这么简单，你也可以轻松学会）][SVM 1]  
[一文理解拉格朗日对偶和KKT条件][KKT 1]

[SVM]: https://juejin.im/post/5acda05c518825556534db9a
[lagrangian duality]: https://www.zhihu.com/question/58584814
[KKT]: https://zhuanlan.zhihu.com/p/38163970
[SVM 1]: https://cloud.tencent.com/developer/article/1076967
[KKT 1]: https://www.jianshu.com/p/52aeaa540d25