支持向量机SVM(2)——拉格朗日乘数法

这里我们主要探讨有条件约束情况下的目标函数优化（求极值）
这类问题也称为条件极值。
本文参考了西瓜书以及B站的讲解视频…

1.拉格朗日函数

首先我们看到一个二元函数的例子：

求函数$z=f(x,y)$z=f(x,y)在条件$\phi(x,y)=0$ϕ(x,y)=0限制下的极值？
消元法：
设函数$f(x,y)$f(x,y)，$\phi(x,y)$ϕ(x,y)在$(x_0,y_0)$(x0​,y0​)附近具有连续偏导数，且$\phi^{'}_x(x,y)$ϕx′​(x,y)，$\phi^{'}_y(x,y)$ϕy′​(x,y)不同时为0，将y视为由方程$\phi(x,y)$ϕ(x,y)确定的x的函数$y=\psi(x)$y=ψ(x)，于是二元函数的条件极值问题就化为了一元函数$z=f(x,\psi(x))$z=f(x,ψ(x))的无条件极值问题。
因此在极值点处必须满足一元函数极值存在的必要条件（即导数等于0）：
$\frac{d_z}{d_x}=0$dx​dz​​=0
进一步z对x求导得：
$\frac{d_z}{d_x}=f^{'}_x(x,y)+f^{'}_y(x,y)\frac{d_y}{d_x} \qquad(1)$dx​dz​​=fx′​(x,y)+fy′​(x,y)dx​dy​​(1)
又由$\phi(x,y)=0$ϕ(x,y)=0得（这里使用了隐函数的微分法）：
$\frac{d_y}{d_x}=-\frac{\phi^{'}_x(x,y)}{\phi^{'}_y(x,y)} \qquad (2)$dx​dy​​=−ϕy′​(x,y)ϕx′​(x,y)​(2)
将(2)式代入(1)中，可得：
$\frac{d_z}{d_x}=f^{'}_x(x,y)-\frac{\phi^{'}_x(x,y)}{\phi^{'}_y(x,y)}f^{'}_y(x,y)$dx​dz​​=fx′​(x,y)−ϕy′​(x,y)ϕx′​(x,y)​fy′​(x,y)
根据极值存在必要条件的等式$\frac{d_z}{d_x}=0$dx​dz​​=0以及题目中的约束可得极值点的坐标必须满足以下方程：
$\begin{cases}f^{'}_x(x,y)-\frac{\phi^{'}_x(x,y)}{\phi^{'}_y(x,y)}f^{'}_y(x,y)=0 \qquad(3)\\\phi(x,y)=0\qquad\qquad\qquad\qquad\quad(4)\end{cases}$⎩⎨⎧​fx′​(x,y)−ϕy′​(x,y)ϕx′​(x,y)​fy′​(x,y)=0(3)ϕ(x,y)=0(4)​

我们将方程(3)(4)联立求解即可得到我们的极值点。

拉格朗日函数的做法：
令$F(x,y)=f(x,y)+\lambda\phi(x,y)$F(x,y)=f(x,y)+λϕ(x,y)（这里的F(x,y)就是我们的拉格朗日函数，$\lambda$λ称为拉格朗日乘数）
对上式求偏导，得：
$\begin{cases} F^{'}_x(x,y)=f^{'}_x(x,y)+\lambda\phi^{'}_x(x,y)\\ F^{'}_y(x,y)=f^{'}_y(x,y)+\lambda\phi^{'}_y(x,y) \end{cases}${Fx′​(x,y)=fx′​(x,y)+λϕx′​(x,y)Fy′​(x,y)=fy′​(x,y)+λϕy′​(x,y)​
令
$F^{'}_x(x,y)=0，F^{'}_y(x,y)=0$Fx′​(x,y)=0，Fy′​(x,y)=0
此时我们得到无条件极值的极值点要满足的必要条件：
$\begin{cases} f^{'}_x(x,y)+\lambda\phi^{'}_x(x,y)=0\\ f^{'}_y(x,y)+\lambda\phi^{'}_y(x,y)=0 \end{cases}${fx′​(x,y)+λϕx′​(x,y)=0fy′​(x,y)+λϕy′​(x,y)=0​
上式中消去$\lambda$λ我们可以得到与消元法最后相同的结果，这也证明了为什么要这样构造拉格朗日函数。

推广到n元函数在m个附加条件下的极値问题，拉格朗日函数的一般形式：
$F(x_1,x_2,...,x_n)=f(x_1,x_2,...,x_n)+\sum_{i=1}^m\lambda_i\phi_i(x_1,x_2,...,x_n)$F(x1​,x2​,...,xn​)=f(x1​,x2​,...,xn​)+i=1∑m​λi​ϕi​(x1​,x2​,...,xn​)
然后对其求偏导解方程就可以得到极值点了。

（了解完拉格朗日函数之后，我们回到SVM的所要解决的问题，即在给定条件下求最小值，这里的条件主要分为了等式约束条件和不等式两种。）

2.等式约束条件

这和我们上面的例子是差不多的，假设我们的目标函数是$f(x)$f(x)，约束条件$h_i(x)=0$hi​(x)=0，即：
$\qquad\qquad\qquad\qquad\qquad minf(x)$minf(x)
$\qquad\qquad \qquad s.t. \quad h_i(x)=0，i=1,2,3...$s.t.hi​(x)=0，i=1,2,3...
这里的x表示的是向量$(x_1,x_2,...,x_n)$(x1​,x2​,...,xn​)。
解决这类问题主要有以下几个步骤：
1.构造拉格朗日函数：
$\qquad\qquad\qquad\qquad F(x)=f(x)+\sum_{i=1}^m\lambda_ih_i(x)$F(x)=f(x)+∑i=1m​λi​hi​(x)
2.对变量求偏导
3.联合等式约束条件和偏导等于0进行求解得到极值点（最优解），再将极值点代入我们的目标函数，得到最小值。

3.不等式约束条件

现在我们来看看SVM所需要优化的问题(也成为原问题)：
$\begin{cases}min_{(w,b)}\frac{1}{2}w^Tw\\ s.t. \quad y_i(w^Tx_i+b)\geq1\iff1- y_i(w^Tx_i+b)\leq0\end{cases}${min(w,b)​21​wTws.t.yi​(wTxi​+b)≥1⟺1−yi​(wTxi​+b)≤0​
(注：min的下标(w,b)表示是找到一个w和b,来最小化目标函数，并且i=1,2,…N)

(1)首先构造拉格朗日函数：
$\qquad\qquad\qquad L(w,b,\lambda)=\frac{1}{2}w^Tw+\sum_{i=1}^N\lambda_i(1-y_i(w^Tx_i+b))$L(w,b,λ)=21​wTw+∑i=1N​λi​(1−yi​(wTxi​+b))
(2)接下来我们可以把原问题转为如下形式：
$\begin{cases}min_{(w,b)}\;max_{\lambda}L(w,b,\lambda)\\ s.t. \quad \lambda_i\geq0\end{cases}${min(w,b)​maxλ​L(w,b,λ)s.t.λi​≥0​
原问题中w,b是要满足条件$1- y_i(w^Tx_i+b)\leq0$1−yi​(wTxi​+b)≤0的，那么这么转换后和原问题是否等价，并且我们的优化目标是否也和原优化目标等价？
接下来可以粗略证明一下：
首先我们求解一下$max_{\lambda}L(w,b,\lambda)$maxλ​L(w,b,λ)到底等于多少？

我们构造的拉格朗日函数中$1- y_i(w^Tx_i+b)$1−yi​(wTxi​+b)这一项无非两种情况大于0或小于等于0.
1)如果$1- y_i(w^Tx_i+b)>0$1−yi​(wTxi​+b)>0,当$\lambda\to\infty$λ→∞时，$\sum_{i=1}^N\lambda_i(1-y_i(w^Tx_i+b))$∑i=1N​λi​(1−yi​(wTxi​+b))也趋于$\infty$∞，所以$max_{\lambda}L(w,b,\lambda)=\infty$maxλ​L(w,b,λ)=∞

2)如果$1- y_i(w^Tx_i+b)\leq0$1−yi​(wTxi​+b)≤0,当$\lambda=0$λ=0时，$\sum_{i=1}^N\lambda_i(1-y_i(w^Tx_i+b))$∑i=1N​λi​(1−yi​(wTxi​+b))取得最小值为0，所以$max_{\lambda}L(w,b,\lambda)=\frac{1}{2}w^Tw$maxλ​L(w,b,λ)=21​wTw。

最后，$min_{(w,b)}\;max_{\lambda}L(w,b,\lambda)=min_{(w,b)}\,(\infty,\frac{1}{2}w^Tw)=min_{(w,b)}\frac{1}{2}w^Tw$min(w,b)​maxλ​L(w,b,λ)=min(w,b)​(∞,21​wTw)=min(w,b)​21​wTw.
可以看到我们的优化目标是等价的，并且在求min的时候我们自动忽略掉等于$\infty$∞的那部分（也就是忽舍弃w，b满足$1- y_i(w^Tx_i+b)>0$1−yi​(wTxi​+b)>0），所以我们$\lambda，b$λ，b也就自动满足原问题中的条件，所以现在我们的问题是和原问题等价的，这也是构造拉格朗日函数的巧妙之处。

这么做的好处就是我们把原问题体重带约束转换为了对w，b无约束的问题，这就很方便我们后面求最优解了。

(3)利用对偶关系将我们上面得到的新问题再次转换为如下形式：
$\begin{cases}max_{\lambda}\;min_{(w,b)}L(w,b,\lambda)\\ s.t. \quad \lambda_i\geq0\end{cases}${maxλ​min(w,b)​L(w,b,λ)s.t.λi​≥0​
因为凸二次规划问题是具有强对偶关系的，所以只可以直接这么转换的（凸二次规划问题就是目标函数是二次，条件是线性的这种情况）。
这么转换的原因是此时w，b无约束，$\lambda_i$λi​有约束（要满足$\lambda_i\geq0$λi​≥0）,而无约束的情况是很好求极值的，所以我们希望先求min这部分。

接下来我们来求解$min_{(w,b)}L(w,b,\lambda)$min(w,b)​L(w,b,λ):
因为此时w,b是无约束的，所以我们就可以通过直接对w，b求偏导的方式来求极值。(求导的过程就不写出来了，直接放结果)
$\begin{cases}\frac{\delta L(w,b,\lambda)}{\delta b}=0\iff\sum_{i=1}^N\lambda_iy_i=0\\\frac{\delta L(w,b,\lambda)}{\delta w}=0\iff w=\sum_{i=1}^N\lambda_iy_ix_i\end{cases}${δbδL(w,b,λ)​=0⟺∑i=1N​λi​yi​=0δwδL(w,b,λ)​=0⟺w=∑i=1N​λi​yi​xi​​
此时我们求得的w就是最优解，虽然还没求得b，但是将求得的结果代入L(w,b,$\lambda$λ)$也会把b消掉，代入后的结果就得到了最小值，即：
$min_{(w,b)}L(w,b,\lambda)=-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\lambda_i\lambda_jy_iy_jx^T_ix_j+\sum_{i=1}^N\lambda_i$min(w,b)​L(w,b,λ)=−21​i=1∑N​j=1∑N​λi​λj​yi​yj​xiT​xj​+i=1∑N​λi​

(4)将上面求得的最小值代入优化问题中，(3)中的问题就变成如下形式：
$\begin{cases}max_{\lambda}\;(-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\lambda_i\lambda_jy_iy_jx^T_ix_j+\sum_{i=1}^N\lambda_i)\\ s.t. \quad \lambda_i\geq0\\\qquad\sum_{i=1}^N\lambda_iy_i=0\end{cases}$⎩⎪⎨⎪⎧​maxλ​(−21​∑i=1N​∑j=1N​λi​λj​yi​yj​xiT​xj​+∑i=1N​λi​)s.t.λi​≥0∑i=1N​λi​yi​=0​

前面我们已经求得了w的最优解，现在我们的任务是通过上面的优化问题来求b的最优解，我们先引入一个KKT条件。

(5)KKT条件：
$\begin{cases}\lambda_i(1- y_i(w^Tx_i+b))=0\\ \lambda_i\geq0\\1- y_i(w^Tx_i+b)\leq0\end{cases}$⎩⎪⎨⎪⎧​λi​(1−yi​(wTxi​+b))=0λi​≥01−yi​(wTxi​+b)≤0​
放一个定理：原问题和对偶问题满足“强对偶关系”的充要条件就是他们满足KKT条件。
而前面我们已经说过了凸二次规划问题具有强对偶关系，所以我们(4)中的问题是满足KKT条件的。

现在我们要用这个条件来求b：
对于任意支持向量$(x_k,y_k)$(xk​,yk​)，都有$1- y_k(w^Tx_k+b)=0$1−yk​(wTxk​+b)=0。(因为支持向量就是到超平面距离最短的那些点，也就是下图中虚线上的点)

将w代入求得求得$b=\frac{1}{y_k}-\sum_{i=1}^N\lambda_iy_ix^T_ix_k$b=yk​1​−∑i=1N​λi​yi​xiT​xk​

但是现实中会采用一种更鲁棒的做法：使用所有支持向量来取平均值。
$b=\frac{1}{|S|}\sum_{k\in S}(\frac{1}{y_k}-\sum_{i=1}^N\lambda_iy_ix^T_ix_k)$b=∣S∣1​∑k∈S​(yk​1​−∑i=1N​λi​yi​xiT​xk​) (S是所有支持向量的下标集合，|S|即集合的大小)

最后我们的超平面模型$f(x)=w^Tx+b$f(x)=wTx+b就变成以下形式：
$f(x)=\sum_{i=1}^N\lambda_iy_ix^T_ix+\frac{1}{|S|}\sum_{k\in S}(\frac{1}{y_k}-\sum_{i=1}^N\lambda_iy_ix^T_ix_k)$f(x)=i=1∑N​λi​yi​xiT​x+∣S∣1​k∈S∑​(yk​1​−i=1∑N​λi​yi​xiT​xk​)