SVM——（四）目标函数求解

在之前的两篇文章中[1][2]分别用两种方法介绍了如何求得目标优化函数，这篇文章就来介绍如何用拉格朗日对偶(Lagrange duality)问题以及SMO算法求解这一目标函数，最终得到参数。

本文主要分为如下部分：
1.构造广义拉格朗日函数L(w,b,α)
2.关于参数w,b,求L的极小值W(α)
3.使用SMO算法求W(α)的极大值
4.求解参数w,b
其中2,3,4也是求解对偶问题的一般步骤。

1.构造广义拉格朗日函数L(w,b,α)

由上文可知SVM最终的优化目标为：

min ω, b 12 | | ω | | 2 s. t. y i (ω T x i + b) \geq 1, i = 1, 2, . . ., m (1.1)

由此我们可以得到广义的拉格朗日函数为：
GeneralizedLagrangian

L (w, b, α) = 12 | | w | | 2 - \sum i = 1 m α i [y (i) (w T x (i) + b) - 1] s . t . g i (w) = - y (i) (w T x (i) + b) + 1 \leq 0 (1.2)

注：此处有两个参数w,b,一个拉格朗日乘子向量α，且αi≥0，因为只有这样才能满足12||w||2=maxL；(详见此处)

由对偶性：

d * = max α, α i \geq 0 min w, b L (w, b, α) = min w, b max α, α i \geq 0 L (ω, α, β) = p * (1.3)

可知，对偶问题d∗与原始问题p∗同解，但上述过程需满足KKT条件：

⎧ ⎩ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ α i \geq 0; g i (w, b) \leq 0; α i g i (w, b) = 0 (1.4)

于是，对于任意训练样本(x(i),y(i))，总有αi=0或者αigi(w,b)=0。若αi=0，由下面(2.1)可知，超平面为0x+b=0，这就意味着与决策面与该样本点无关；若αi>0，则必有y(i)(wTx(i)+b)=1，也就是说该样本点是一个支持向量。这显示出一个重要性质：超平面仅仅与支持向量有关。

2.关于参数w,b,求L的极小值W(α)

这一步同拉格朗日乘数法求极值一样，分别对w,b求偏导，并令其为0：

\partial L \partial w w \partial L \partial b = w - \sum i = 1 m α i y (i) x (i) = 0 = \sum i = 1 m α i y (i) x (i) = \sum i = 1 m α i y (i) = 0 (2.1) (2.2)

常用范数求导法则
将(2.1),(2.2)代入(1.2)可知：

W (α) = min w, b L (w, b, α) = \sum i = 1 m α i - 12 \sum i, j = 1 m y (i) y (j) α i α j (x (i)) T x (j) (2.3)

详细步骤：

L W (α) 其 中 ： w T w = 12 w T w - \sum i = 1 m α i [y (i) (w T x (i) + b) - 1] = 12 w T w - \sum i = 1 m α i y (i) w T x (i) - \sum i = 1 m α i y (i) b + \sum i = 1 m α i = 12 w T w - w T \sum i = 1 m α i y (i) x (i) - b \sum i = 1 m α i y (i) + \sum i = 1 m α i 代 入 (2.1)(2.2) 得 = 12 w T w - w T w + \sum i = 1 m α i = \sum i = 1 m α i - 12 w T w = \sum i = 1 m α i - 12 \sum i, j = 1 m α i α j y (i) y (j) (x (i)) T x (j) = \sum i = 1 m α i y (i) x (i) \cdot \sum j = 1 m α j y (j) x (j) = \sum i, j = 1 m α i α j y (i) y (j) (x (i)) T x (j) = \sum i = 1 m \sum j = 1 m α i α j y (i) y (j) (x (i)) T x (j)

3.使用SMO算法求W(α)的极大值

由(2.3)我们可以得出如下优化问题：

max α s . t . W (α) = \sum i = 1 m α i - 12 \sum i, j = 1 m y (i) y (j) α i α j (x (i)) T x (j) α i \geq 0, i = 1, . . ., m \sum i = 1 m α i y (i) = 0 (3.1)

之所以(2.2)也会成为约束条件，是因为W(α)就是通过(2.2)求解的出来的，是W(α)存在的前提。

现在我们的优化问题变成了如上的形式。对于这个问题，我们有更高效的优化算法，即序列最小优化（SMO）算法。我们通过这个优化算法能得到α，再根据α，我们就可以求解出w和b，进而求得我们最初的目的：找到超平面，即”决策平面”。

至于具体求解步骤，不急咱们先放着，到后面再来解决。

总结一句话：我们为啥使出吃奶的劲儿进行推导？因为我们要将最初的原始问题，转换到可以使用SMO算法求解的问题，这是一种最流行的求解方法。为啥用这种求解方法？因为它牛逼啊！

4. 求解w,b

经过3.2求解出α之后，代入(18)即可求解出w;而b的求解公式为：

b = - 12 (max i : y (i) = - 1 w T x (i) + min i : y (i) = + 1 w T x (i))

例如：

SVM——（四）目标函数求解

如图，红色为正样本(y=+1),紫色为负样本(y=−1),直线为x1+x2−b=0,则有：

max i : y (i) = - 1 w T x (i) = max (1 * 2 + 1 * 3, 1 * 1 + 1 * 2) = 5 min i : y (i) = + 1 w T x (i) = min (1 * 5 + 1 * 4, 1 * 6 + 1 * 3) = 9 b = - 12 (5 + 9) = - 7

SVM——（七）SMO（序列最小最优算法）
SVM——（六）软间隔目标函数求解
 SVM——（五）线性不可分之核函数
 SVM——（四）目标函数求解
 SVM——（三）对偶性和KKT条件（Lagrange duality and KKT condition）
SVM——（二）线性可分之目标函数推导方法2
SVM——（一）线性可分之目标函数推导方法1

参考：

Python3《机器学习实战》学习笔记（八）：支持向量机原理篇之手撕线性SVM
《机器学习》周志华

SVM——（四）目标函数求解

相关推荐