为什么支持向量机会有对偶算法？

马同学图解数学 · 公众号 · 数学 · 2020-12-08 10:10

正文

下面是机器学习的《监督式学习》课程中“支持向量机”单元的内容，感兴趣的同学可以点击最下方的阅读原文购买。

一句话答案就是，通过对偶算法（Dual Problem）来计算支持向量机（Support Vector Machines，缩写为 SVM ）的决策边界会比较简单。

1 原算法与对偶算法

对于支持向量机而言，对偶算法是借助拉格朗日对偶性从原算法（Primal Problem）推出的，两者完全等价，只是求解了不同的条件极值（下面是硬间隔支持向量机的原算法和对偶算法）：

从上面的对比可以看出，对偶算法主要有三点改进使得决策边界的求解不再困难：

对偶算法中没有 $\boldsymbol{w}$ 和 $b$ ，这样求解比较简单
对偶算法限制条件中的 $\displaystyle\sum_{i=1}^{n}\lambda_i y_i=0$ 很容易消去，在后面的例子中可以看到
更重要的是，原算法的限制条件为较为复杂的线性不等式 $y_i(\boldsymbol{w}\cdot\boldsymbol{x_i}+b)\ge 1$ ，而消去 $\displaystyle\sum_{i=1}^{n}\lambda_i y_i=0$ 的对偶算法，其限制条件只为简单的 $\lambda_i \geq 0$ ，这会极大地降低求解的难度

这么说可能不太直观，下面会用例子来进一步说明。

2 例子

假设数据集

D

为：

下面会通过原算法、对偶算法来分别计算硬间隔支持向量机的决策边界。

3 原算法求解

很多资料都没介绍原算法怎么计算，主要是因为原算法中的限制条件为较为复杂的线性不等式

y_i(\boldsymbol{w}\cdot\boldsymbol{x_i}+b)\ge 1

，要正儿八经地去计算涉及到二次规划中较为复杂的理论。本文也没有打算正面去计算，下面的计算过程会用到一些技巧。

（1）改写条件极值。原算法要求解的条件极值为：

$\begin{aligned} \min_{\boldsymbol{w},b}\quad &\frac{1}{2}||\boldsymbol{w}||^2\\ s.t.\quad &y_i(\boldsymbol{w}\cdot\boldsymbol{x_i}+b)\ge 1, i=1,2,3 \end{aligned}$ 根据该条件极值，首先写出拉格朗日函数：

$L=\frac{1}{2}||\boldsymbol{w}||^2+\sum_{i=1}\lambda_i[1-y_i(\boldsymbol{w}\cdot \boldsymbol{x}_i+b)]$ 然后根据拉格朗日乘数法以及 KKT 条件，从上述条件极值可以得到下面的方程组：

$\begin{cases} \displaystyle\frac{\partial L}{\partial \boldsymbol{w}}=0,\displaystyle\frac{\partial L}{\partial b}=0\\ \\ \lambda_i(1-y_i(\boldsymbol{w}\cdot \boldsymbol{x}_i+b))=0\\ \\ \lambda_i\ge 0,1-y_i(\boldsymbol{w}\cdot \boldsymbol{x}_i+b)\le 0 \end{cases}$

（2）下面来求解（1）中得到的方程组。改写 $L$ 可得：

$\begin{aligned} L &=\frac{1}{2}||\boldsymbol{w}||^2+\sum_{i=1}^{n}\lambda_i[1-y_i(\boldsymbol{w}\cdot \boldsymbol{x}_i+b)]\\ \\ &=\frac{1}{2}\boldsymbol{w}^{\text{T}}\boldsymbol{w}+\sum_{i=1}^{n}\lambda_i-\sum_{i=1}^{n}\lambda_iy_i(\boldsymbol{w}\cdot \boldsymbol{x}_i)+\sum_{i=1}^{n}\lambda_iy_i b \end{aligned}$ 因此： $\begin{aligned} \frac{\partial L}{\partial \boldsymbol{w}}&=\frac{1}{2}\cdot 2\boldsymbol{w}+0-\sum_{i=1}^n\lambda_iy_i\boldsymbol{x}_i+0\\\\ &=\boldsymbol{w}-\sum_{i=1}^n\lambda_iy_i\boldsymbol{x}_i \end{aligned}$

据此可得： $\frac{\partial L}{\partial \boldsymbol{w}}=0\Longrightarrow \boldsymbol{w}=\sum_{i=1}^n\lambda_iy_i\boldsymbol{x}_i$ 又： $\frac{\partial L}{\partial b}=0+0+0+\sum_{i=1}^{n}\lambda_iy_i$ 所以可得： $\frac{\partial L}{\partial b}=0\Longrightarrow \sum_{i=1}^{n}\lambda_iy_i=0$ 综合下即有： $\begin{cases} \displaystyle\frac{\partial L}{\partial\boldsymbol{w}}=0\implies \displaystyle\boldsymbol{w}=\sum_{i=1}^{3}\lambda_iy_i\boldsymbol{x}_i\\ \displaystyle\frac{\partial L}{\partial b}=0\implies \displaystyle\sum_{i=1}^{n}\lambda_i y_i=0 \end{cases}$ 代入数据可得： $\begin{cases} w_1=3\lambda_1+4\lambda_2-\lambda_3\\ w_2=3\lambda_1+3\lambda_2-\lambda_3\\ \lambda_1+\lambda_2-\lambda_3=0 \end{cases}$ 下面需要分情况讨论。

（3）如果 $\lambda_i=0$ ，那么意味着 $w_1=w_2=0$ ，又因为决策边界为 $\boldsymbol{w}\cdot\boldsymbol{x}+b=0$ ，所以推出 $b=0$ ，那么此时有： $1-y_i(\boldsymbol{w}\cdot \boldsymbol{x}_i+b)=1\nleq 0$ 即不满足方程组的条件，所以 $\lambda_i=0$ 不是解。

（4）根据（3）， $\lambda_i$ 不能全为 0，所以：

$\lambda_1+\lambda_2-\lambda_3=0\implies \lambda_3 >0$ 进而可以推出： $\begin{aligned} \left.\begin{aligned} \lambda_i(1-y_i(\boldsymbol{w}\cdot \boldsymbol{x}_i+b))=0\\ \lambda_3 >0\\ w_1=3\lambda_1+4\lambda_2-\lambda_3\\ w_2=3\lambda_1+3\lambda_2-\lambda_3 \end{aligned}\right\} &\implies1-y_3(\boldsymbol{w}\cdot \boldsymbol{x}_3+b)=0\\ &\implies 6\lambda_1+7\lambda_2-2\lambda_3+b=-1 \end{aligned}$ （5）因为 $\lambda_3\ne 0$ ，所以 $\lambda_1$ 和 $\lambda_2$ 中至少还有一个不为 0 ，假设 $\lambda_1 >0$ ， $\lambda_2=0$ ，那么有 : $\left.\begin{aligned} \lambda_1+\lambda_2-\lambda_3=0\\ \lambda_1 >0, \lambda_2=0, \lambda_3 > 0\\ \end{aligned}\right\}\implies \lambda_1=\lambda_3 > 0$ 进而可以推出： $\begin{aligned} \left.\begin{aligned} \lambda_i(1-y_i(\boldsymbol{w}\cdot \boldsymbol{x}_i+b))=0\\ \lambda_1 >0\\ w_1=3\lambda_1+4\lambda_2-\lambda_3\\ w_2=3\lambda_1+3\lambda_2-\lambda_3 \end{aligned}\right\} &\implies1-y_1(\boldsymbol{w}\cdot \boldsymbol{x}_1+b)=0\\ &\implies 18\lambda_1-21\lambda_2-6\lambda_3+b=1 \end{aligned}$ 因为有 $\lambda_1=\lambda_3$ 、 $\lambda_2=0$ ，所以：

$\begin{cases} 6\lambda_1+7\lambda_2-2\lambda_3+b=-1\implies 4\lambda_1+b=-1\\ 18\lambda_1-21\lambda_2-6\lambda_3+b=1\implies 12\lambda_1+b=1 \end{cases}$ 解上述线性方程组可得 $\lambda_1=\frac{1}{4},b=-2$ ，所以最终可得： $\hat{\boldsymbol{w}}=\begin{pmatrix}w_1\\w_2\end{pmatrix}=\begin{pmatrix}\frac{1}{2}\\\frac{1}{2}\end{pmatrix},\quad \hat{b}=-2$ 进而得到决策边界为： $h(\boldsymbol{x})=\operatorname{sign}(\hat{\boldsymbol{w}}\cdot\boldsymbol{x}+\hat{b})=\operatorname{sign}(\frac{1}{2}x_1+\frac{1}{2}x_2-2)$ 可以图示如下：

（6）如果假设 $\lambda_2 >0$ ，或所有的 $\lambda_i >0$ ，是无法求解的，这里就不再赘述。

4 对偶算法求解

对偶算法的限制条件比较简单，所以下面的解法虽然看上去过程也较多，但只要按部就班就可以解出。

（1）消去条件中的 $\displaystyle\sum_{i=1}^{n}\lambda_i y_i=0$ 。根据数据集 $D$ ，我们要求解的对偶算法的条件极值如下： $\begin{aligned} \min_{\lambda}\quad &\frac{1}{2}\sum_{i=1}^{3}\sum_{j=1}^{3} \lambda_i\lambda_jy_iy_j\boldsymbol{x}_i^{\text{T}}\boldsymbol{x}_j-\sum_{i=1}^{3}\lambda_i \\ &=\frac{1}{2}\left(18 \lambda_{1}^{2}+25 \lambda_{2}^{2}+2 \lambda_{3}^{2}+42 \lambda_{1} \lambda_{2}-12 \lambda_{1} \lambda_{3}-14 \lambda_{2} \lambda_{3}\right)-\lambda_{1}-\lambda_{2}-\lambda_{3} \\ \text { s.t. } \quad & \lambda_{1}+\lambda_{2}-\lambda_{3}=0\\ & \lambda_{i} \geq 0, \quad i=1,2,3 \end{aligned}$ 由第一个条件可得 $\lambda_3=\lambda_1+\lambda_2$ ，将其代入要求最小值的目标函数，就得到了新的函数，记作： $s\left(\lambda_{1}, \lambda_{2}\right)=4 \lambda_{1}^{2}+\frac{13}{2} \lambda_{2}^{2}+10 \lambda_{1} \lambda_{2}-2 \lambda_{1}-2 \lambda_{2}$ 这个函数融合了第一个条件，所以要优化的条件极值可以改写为： $\begin{aligned} \min_{\lambda}\quad &s\left(\lambda_{1}, \lambda_{2}\right)=4 \lambda_{1}^{2}+\frac{13}{2} \lambda_{2}^{2}+10 \lambda_{1} \lambda_{2}-2 \lambda_{1}-2 \lambda_{2}\\ \text { s.t. } \quad & \lambda_{i} \geq 0, \quad i=1,2,3 \end{aligned}$ 实际上这就消去了条件中的 $\displaystyle\sum_{i=1}^{n}\lambda_i y_i=0$ 。

（2）通过数据集找到支持向量。根据拉格朗日乘数法以及 KKT 条件，从修改后的条件极值可以得到下面的方程组： $\begin{cases} \displaystyle\frac{\partial s}{\partial \lambda_1}=8\lambda_1+10\lambda_2-2=0\\ \displaystyle\frac{\partial s}{\partial \lambda_2}=10\lambda_1+13\lambda_2-2=0\\ \lambda_i\ge 0 \end{cases}$ 根据前两个方程可以算出： $\begin{cases} \displaystyle\frac{\partial s}{\partial \lambda_1}=8\lambda_1+10\lambda_2-2=0\\ \displaystyle\frac{\partial s}{\partial \lambda_2}=10\lambda_1+13\lambda_2-2=0 \end{cases}\implies\lambda_1=\frac{3}{2},\lambda_2=-1$ 因为： $\lambda_2=-1\ngeq 0$ 所以最小值没有办法在 $(\frac{3}{2},-1)$

为什么支持向量机会有对偶算法？

正文

请到「今天看啥」查看全文