【Method】SVM（四）支持向量机的对偶算法

原理

线性可分支持向量机

理解支持向量机学习的对偶算法是理解支持向量机的关键。
为了求解线性可分支持向量机的最优化问题，我们通过求解对偶问题（dual problem）得到原始问题（primal problem）的最优解，这就是线性可分支持向量机的对偶算法（dual algorithm）。这样做的优点，一是对偶问题往往更容易求解；二是自然引入核函数，进而推广到非线性分类问题。
首先构建拉格朗日函数(Lagrange function)。为此，对每一个不等式约束引进拉格朗日乘子(Lagrange multiplier) $\alpha_i \geq 0, i=1,2,...,N$，定义拉格朗日函数：
\[L(w,b,\alpha)=\frac{1}{2} \|w\|^2 - \sum_{i=1}^N \alpha_i (y_i (w \bullet x_i + b) -1)\]
其中，$\alpha=(\alpha_1,\alpha_2,...,\alpha_N)^T$为拉格朗日乘子向量。

根据支持向量机的优化目标$\min_{w,b} \frac{1}{2} \|w\|^2$得到原始问题为：
\[\min_{w,b} \max_{\alpha:\alpha_i \geq 0} L(w,b,\alpha)\]
根据拉格朗日对偶性，原始问题的对偶问题是极大极小问题：
\[\max_\alpha \min_{w,b} L(w,b,\alpha)\]
所以，为了得到对偶问题的解，需要先求$L(w,b,\alpha)对$w,b$的极小，再求对$\alpha$$的极大

(1) 求$\min_{w,b} L(w,b,\alpha)$

将拉格朗日函数$L(w,b,\alpha)$分别对$w,b$求偏导数并令其等于0.
\[\nabla_w L(w,b,\alpha) =w-\sum_{i=1}^N \alpha_i y_i x_i = 0\] \[\nabla_b L(w,b,\alpha) = \sum_{i=1}^N \alpha_i y_i = 0\]
得，
\[w=\sum_{i=1}^N \alpha_i y_i x_i\] \[\sum_{i=1}^N \alpha_i y_i = 0\]
将上述式子代入拉格朗日函数$L(w,b,\alpha)$，得，
\[\begin{eqnarray} L(w,b,\alpha) &=& \frac{1}{2} w^Tw - \sum_{i=1}^N \alpha_i (y_i (w \bullet x_i + b) -1) \\ &=& \frac{1}{2} w^Tw - \sum_{i=1}^N \alpha_i y_i (w \bullet x_i + b) + \sum_{i=1}^N \alpha_i \\ &=& \frac{1}{2} w^Tw - \sum_{i=1}^N \alpha_i y_i x_i w + \sum_{i=1}^N \alpha_i \\ &=& \frac{1}{2} w^Tw - w^Tw + \sum_{i=1}^N \alpha_i \\ &=& -\frac{1}{2} w^Tw + \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 \bullet x_j) + \sum_{i=1}^N \alpha_i \end{eqnarray}\]
即，
\[min_{w,b} L(w,b,\alpha) = -\frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (x_i \bullet x_j) + \sum_{i=1}^N \alpha_i\]
(2)求$min_{w,b} L(w,b,\alpha)$对$\alpha$的极大，即是对偶问题
\[\begin{align} &max_\alpha -\frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (x_i \bullet x_j) + \sum_{i=1}^N \alpha_i \\ &s.t. \sum_{i=1}^N \alpha_i y_i = 0 \\ &\alpha_i \geq 0, i=1,2,...,N \end{align}\]
上式即为对偶最优化问题。

设$\alpha^* = (\alpha_1^*, \alpha_2^*,...,\alpha_l^*)^T是对偶最优化问题的解，则存在下标j，使得$\alpha_j^* >0$，并可按下式求得原始最优化问题的解$w^, b^$$
\[w^*=\sum_{i=1}^N \alpha_i^* y_i x_i\] \[b^* = y_i - \sum_{i=1}^N \alpha_i^* y_i (x_i \bullet x_j)\]
由此定理可知，分离超平面可以写成
\[\sum_{i=1}^N \alpha_i^* y_i (x \bullet x_i) + b^* = 0\]
分类决策函数可以写成
\[f(x) = sign(\sum_{i=1}^N \alpha_i^* y_i (x \bullet x_i) + b^*)\]
这就是说，分类决策函数只依赖于输入x和训练样本输入的内积。上式称为线性可分支持向量机的对偶形式。
线性可分支持向量机学习算法

输入：线性可分训练集$T={(x_1,y_1),(x_2,y_2),...,(x_N,y_N)}$，其中$x_i \in X = R^n, y_i \in Y={+1,-1}, i=1,2,...,N$；

输出：分离超平面和分类决策函数

（1）构造并求解约束最优化问题
\[\begin{align} &max_\alpha \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (x_i \bullet x_j) - \sum_{i=1}^N \alpha_i \\ &s.t. \sum_{i=1}^N \alpha_i y_i = 0 \\ &\alpha_i \geq 0, i=1,2,...,N \end{align}\]
求得最优解$\alpha^* = (\alpha_1^*, \alpha_2^*,...,\alpha_l^*)^T$.

（2）计算
\[w^*=\sum_{i=1}^N \alpha_i^* y_i x_i\]
并选择$\alpha^*$的一个正分量$\alpha_j^*>0$，计算
\[b^* = y_i - \sum_{i=1}^N \alpha_i^* y_i (x_i \bullet x_j)\]
（3）求得分离超平面
\[w^* \bullet x + b^* = 0\]
分类决策函数：
\[f(x)=sign(w^* \bullet x + b^*)\]
在线性可分支持向量机中，$w^*$和$b^*$只依赖于训练数据中对应于$\alpha_i^*>0$的样本点$(x_i,y_i)$，而其他样本点对$w^*$和$b^*$没有影响。我们将训练数据中对应于$\alpha_i^*>0$的实例点$x_i \in R^n$称为支持向量。

线性支持向量机

原始最优化问题的拉格朗日函数是
\[L(w,b,\xi,\alpha,\mu) \equiv \frac{1}{2} \|w\|^2 + C \sum_{i=1}^N \xi_i - \sum_{i=1}^N \alpha_i(y_i(w \bullet x_i +b)-1 + \xi_i) - \sum_{i=1}^N \mu_i \xi_i\]
对偶问题是拉格朗日函数的极大极小问题。首先求$L(w,b,\xi,\alpha,\mu)$对$w,b,\xi$的极小，由
\[\nabla_w L(w,b,\xi,\alpha,\mu) = w - \sum_{i=1}^N \alpha_i y_i x_i = 0\] \[\nabla_b L(w,b,\xi,\alpha,\mu) = - \sum_{i=1}^N \alpha_i y_i = 0\] \[\nabla_{\xi_i} L(w,b,\xi,\alpha,\mu) = C - \alpha_i - \mu_i = 0\]
得，
\[w = \sum_{i=1}^N \alpha_i y_i x_i\] \[\sum_{i=1}^N \alpha_i y_i = 0\] \[C-\alpha_i-\mu_i=0\]
将上述式子代入拉格朗日函数得到,
\[min_{w,b,\xi} L(w,b,\xi,\alpha,\mu) = -\frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (x_i \bullet x_j) + \sum_{i=1}^N \alpha_i\]
再对$min_{w,b,\xi} L(w,b,\xi,\alpha,\mu)$求$\alpha$的极大，即得对偶问题：
\[\max_\alpha -\frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (x_i \bullet x_j) + \sum_{i=1}^N \alpha_i\] \[\begin{eqnarray} s.t. \sum_{i=1}^N \alpha_i y_i &=& 0 \\ C - \alpha_i - \mu_i &=& 0 \\ \alpha_i &\geq& 0 \\ \mu_i &\geq& 0, i=1,2,...,N \end{eqnarray}\]
即，
\[\max_\alpha -\frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (x_i \bullet x_j) + \sum_{i=1}^N \alpha_i\] \[s.t. \sum_{i=1}^N \alpha_i y_i = 0\] \[C \geq \alpha \geq 0, i=1,2,...,N\]
设$\alpha^* = (\alpha_1^*, \alpha_2^*,...,\alpha_l^*)^T是对偶最优化问题的解，则存在下标j，使得$0 < \alpha_j^* < C$，并可按下式求得原始最优化问题的解$w^, b^$$
\[w^*=\sum_{i=1}^N \alpha_i^* y_i x_i\] \[b^* = y_i - \sum_{i=1}^N \alpha_i^* y_i (x_i \bullet x_j)\]
由此分离超平面可以写成
\[\sum_{i=1}^N \alpha_i^* y_i (x \bullet x_i) + b^* = 0\]
分类决策函数可以写成
\[f(x) = sign(\sum_{i=1}^N \alpha_i^* y_i (x \bullet x_i) + b^*)\]
软间隔的支持向量$x_i$或者在间隔边界上，或者在间隔边界与分离超平面之间，或者在分离超平面误分一侧。若$\alpha_i^* <C$，则$\xi_i=0$，支持向量$x_i$恰好落在间隔边界上；若$\alpha_i^*=C, 0<\xi_i<1$，则分类正确，$x_i$在间隔边界与分离超平面之间；若$\alpha_i^*=C, \xi_i=1$，则$x_i$在分离超平面上；若$\alpha_i^*=C, \xi_i>1$，则$x_i$在分离超平面误分一侧。

非线性支持向量机与核技巧

我们注意到在线性支持向量机的对偶问题中，无论是目标函数还是决策函数（分离超平面）都只涉及输入实例和实例之间的内积。在对偶问题的目标函数中的内积$x_i \bullet x_j$可以用核函数$K(x,z)=\phi(x) \bullet \phi(z)$来代替。此时对偶问题的目标函数成为
\[W(\alpha)=\frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j K(x_i,x_j) - \sum_{i=1}^N \alpha_i\]
同样，分类决策函数中内积也可以用核函数代替，而分类决策函数式成为
\[f(x)=sign(\sum_{i=1}^{N_s} \alpha_i^* y_i \phi(x_i) \bullet \phi(x) + b^*) = sign(\sum_{i=1}^{N_s} \alpha_i^* y_i K(x_i, x) + b^*)\]
这等价于经过映射函数$\phi$将原来的输入空间变换到一个新的特征空间，将输入空间中的内积$x_i \bullet x_j$变化为特征空间的内积$\phi(x_i) \bullet \phi(x_j)$，在新的特征空间里从训练样本中学习线性支持向量机。当映射函数是非线性函数时，学习到的含有核函数的支持向量机是非线性分类模型。

也就是说，在核函数$K(x,z)$给定的条件下，可以利用解线性分类问题的方法求解非线性分类问题的支持向量机，学习是隐式地在特征空间进行的，不需要显示地定义特征空间和映射函数，这样的技巧称为核技巧，它是巧妙地利用线性分类学习方法与核函数解决非线性问题的技术。在实际应用中，往往依赖领域知识直接选择核函数，核函数选择的有效性需要通过实验验证。
$x^*$和$\alpha^*,\beta^*$分别是原始问题和对偶问题的解的充分必要条件是$x^*,\alpha^*, \beta^*$满足Karush-Kuhn-Tucker（KKT）条件。