支持向量机的对偶算法

支持向量机系列导航

对于一个线性分类问题，有数据 $Data = \{x_i,y_i\}_{i=1}^{N},x_i \in R^p,y_i\in \{+1,-1\}$ , 即有N个数据样本需要分类，每个样本 $x_i$ 为 $p$ 维向量， $y_i$ 取值为 $+1 \text{or}-1$

上一节将支持向量机模型转化为如下凸二次规划问题

\begin{equation}\begin{aligned}&\min _{b, w} \;\;\;\frac{1}{2} w^{T} w\\&\text { s.t. } \quad 1-y_{n}\left(\mathbf{w}^{T} \mathbf{x}_{n}+b\right) \leq 0 ,n=1,2,...,N\end{aligned}\end{equation}

通常，当 $N,p$ 比较小的时候，可以直接交给库函数来求解。但是当 $N$ 很大或者引入核方法后，可能会导数样本维度为巨大甚至为无穷大，此时可以通过拉格朗日乘子法引入其对偶问题来求解。

通过求解对偶问题得到原始问题的最优解，就是支持向量机的对偶算法。采用对偶算法，有优点：

对偶问题一般更容易求解
自然引入核函数，进而推广到非线性分类问题。

原优化问题的对偶问题

首先构造其拉格朗日函数，为此，对每一个不等式约束引入拉格朗日乘子 $a_i ≥ 0$ , I = 1,2,..,N, 拉格朗日函数如下：

\begin{equation}L(w, b, \alpha)=\frac{1}{2} w^{T} w+\sum_{i=1}^{N} \alpha_{i}\left(1-y_{i}\left(w^{T} x_{i}+b\right)\right), i = 1,2,...,N\end{equation}

这时，原优化问题就等价于如下无约束问题：

\begin{equation}\begin{aligned}&\min _{w, b} \max _{\alpha} L(w, b, \alpha) \\&\text { s.t. }\;\;\; \alpha_{i} \geq 0, \;\;i=1,2, \ldots, N\end{aligned}\end{equation}

原问题和以上无约束问题为什么等价？理解如下（逻辑理解，非数理证明）

上述无约束问题（P）的对偶问题（D）为如下极大极小问题：

\begin{equation}\begin{aligned} &\max _{\alpha}\min _{w, b} L(w, b, \alpha) \\&\text { s.t. }\;\;\; \alpha_{i} \geq 0, \;\;i=1,2, \ldots, N\end{aligned}\end{equation}

所以，为了得到对偶问题的解，需要先对 $L(w,b,\alpha)$ 对 $w,b$ 求极小，再求对 $\alpha$ 的极大。

求 $\min_{w,b}L(w,b,\alpha)$ 将拉格朗日函数 $L(w,b,\alpha)$ 分别对 $w,b$ 求偏导并令其为0。先对 $L(w,b,\alpha)$ 进行化解，如下：

\begin{align*}L(w, b, \alpha)&=\frac{1}{2} w^{T} w+\sum_{i=1}^{N} \alpha_{i}\left(1-y_{i}\left(w^{T} x_{i}+b\right)\right) \\ &=\frac 1 2 w^Tw + \sum_{i=1}^N\alpha _i - \sum_{i=1}^N\alpha _iy_iw^Tx_i - \sum_{i=1}^N\alpha _iy_i b\end{align*}

对 $w,b$ 求偏导如下：

\begin{align*} & \frac{\partial L(w,b,\alpha)}{\partial b} = -\sum_{i=1}^N\alpha_i y_i \\[5bp] &\frac{\partial L(w,b,\alpha)}{\partial w} = w-\sum_{i=1}^N \alpha_i y_i x_i \end{align*}

令偏导为0,则有

\begin{align} &\sum_{i=1}^N\alpha_i y_i=0 \\[5bp] &w=\sum_{i=1}^N \alpha_i y_i x_i \end{align}

将求得的w（式(4)）带入拉格朗日函数（式 $(2)$ ）,并利用式(5)，可得

\begin{equation*}\begin{aligned}L(w, b, \alpha) &=\frac{1}{2} \sum_{i-1}^{N} \sum_{j=1}^{N} \alpha_{i} \alpha_{j} y_{i} y_{j}\left(x_{i} \cdot x_{j}\right)-\sum_{i=1}^{N} \alpha_{i} y_{i}\left(\left(\sum_{j=1}^{N} \alpha_{j} y_{j} x_{j}\right) \cdot x_{i}+b\right)+\sum_{i=1}^{N} \alpha_{i} \\&=-\frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_{i} \alpha_{j} y_{i} y_{j}\left(x_{i} \cdot x_{j}\right)+\sum_{i=1}^{N} \alpha_{i}\end{aligned}\end{equation*}

即

\begin{equation*}L\left(w, b, \lambda_{i}\right)=-\frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \lambda_{i} \lambda_{j} y_{i} y_{j} x_{i}^{T} x_{j}+\sum_{i=1}^{N} \alpha_{i}\end{equation*}

求 $\min_{w,b}L(w,b,\alpha)$ 对 $\alpha$ 的极大，即对偶问题

\begin{equation}\begin{split} \max_{\alpha}& \;\;\;\sum_{i=1}^{N} \alpha_{i}-\frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_{i} \alpha_{j} y_{i} y_{j} x_{i}^{T} x_{j} \\ \text { s.t. }&\;\;\; \sum_{i=1}^{N} \alpha_{i} y_{i}=0 \\ &\;\;\; \alpha_{i} \geq 0, i=1,2, \ldots, N \end{split}\end{equation}

将上式子的目标函数由求极大转换为求极小，就得到下面与之等价的对偶最优化问题

\begin{equation}\begin{split} \min_{\alpha}& \;\;\;\frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_{i} \alpha_{j} y_{i} y_{j} x_{i}^{T} x_{j} -\sum_{i=1}^{N} \alpha_{i}\\ \text { s.t. }&\;\;\; \sum_{i=1}^{N} \alpha_{i} y_{i}=0 \\ &\;\;\; \alpha_{i} \geq 0, i=1,2, \ldots, N \end{split}\end{equation}

考虑原始最优化问题 (1) (3) 和对偶优化问题（8)。原始优化问题与对偶问题为强对偶关系。所以存在 $w^*,b^*,\alpha^*$ , 使得 $w^*,b^*$ 是原问题的解， $\alpha^*$ 为对偶问题的解。这意味着求解原始问题(1)(3)可以转换为求解对偶问题(8)。此外因为是强对偶关系，所以满足KKT条件（强对偶与KKT条件为充要关系）。

假设对偶问题最优化问题对 $\alpha$ 的解为 $\alpha ^*$ ，那么可以由 $\alpha ^*$ 根据KKT条件求得原始最优化问题对 $w,b$ 的解 $w^*, b^*$ 如下，其中 $x_k$ 为任意一边界上的数据点。

\begin{align*}\hat{w}&=\sum_{i=1}^{N} \lambda_{i} y_{i} x_{i} \\ b^* &= y_{k}-\sum_{i=1}^{N} \lambda_{i} y_{i} x_{i}^{T} x_{k} \end{align*}

证明 KKT条件如下：

综上，分离超平面可写为：

\begin{equation*} \sum_{i=1}^{N} \alpha_{i}^{*} y_{i}\left(x \cdot x_{i}\right)+b^{*}=0 \end{equation*}

分类决策函数可以写为：

\begin{equation*}f(x)=\operatorname{sign}\left(\sum_{i=1}^{N} \alpha_{i}^{*} y_{i}\left(x \cdot x_{i}\right)+b^{*}\right)\end{equation*}

分类决策函数只依赖于输入 $x$ 和训练样本输入的内积

注可以发现， $w^*,b^*$ 均为输入数据的线性组合。

总结

对于给定的线性可分训练数据集，可以首先求其对偶问题的解 $\alpha^*$ ，再求得原始问题的解 $w^*, b^*$ 。从而得到分离超平面及分类决策函数。这种算法称为线性可分支持向量机的对偶学习算法。

具体来看，SVM原始优化问题为凸二次规划问题，由拉格朗日对偶性将原始问题转为对偶问题，因为SVM原始优化问题为凸二次规划，所以原始问题与对偶问题满足强对偶关系，所以求得对偶问题的解即为原始问题的解。因为满足强对偶关系，进而满足kkt条件，所以求解对偶问题的时候，可以用 $\alpha$ 求出 $w,b$ 。