2020机器学习SVM-KKT条件(2)

2020-03-30 本文已影响0人 zidea

machine_learning.jpg

甜点

001.png

有时候只是单纯地看一些数据公式，比较难理解，如果我们通过绘制一些图形可以更好帮助理解这些公式，今天介绍的 SVM 就是一种很优雅的算法，同时也是相对于其他机器学习模型比较难懂，如果我们能够真正理解其背后算法其实一件值得我们乐道和骄傲的一件事。我在学习 SVM 也是一度困惑一度退缩，最后通过搜集各种资料和视频来对 SVM 有了点感觉。今天开始相比把这些感觉通过一系列分享分享给大家。

只有真正了解了拉格朗日乘子法和 KKT 条件才能真正理解 SVM 的算法，在开始KKT条件前，我们需要回归一下什么是拉格朗日乘子法，也就是求带有等式约束条件的极值问题，KKT条件就是求带不等式约束条件的极值问题

回归拉格朗日

在之前已经详细介绍过了拉格朗日，但是 KKT 还是说不是很清楚，所以重点说一说 KKT，不过还是要简单说一下拉格朗日乘子法。
$\begin{cases} \min f(x,y) \\ s.t. \, g(x,y) = 0 \end{cases}$
在拉格朗日乘子法就是解决有等式的约束条件下求最小值问题，这样问题可以通过拉格朗日法将等式约束条件和求极值函数写在一起如下，其中 $\lambda$ 不等于 0。

$\min f(\vec{x}) + \lambda g(\vec{x})\,(\lambda \neq 0)$

$\begin{cases} f(\vec{x}) = x_1^2 + x_2\\ g(x) = (x_1 - 3)^2 + (x_2 + 3)^2 -16 \\ \end{cases}$

$\begin{bmatrix} 2x_1\\ 1\\ \end{bmatrix} = \lambda \begin{bmatrix} 2(x_1 - 3)\\ 2(x_2 - 3) \end{bmatrix}$

$\begin{cases} 2x_1 = 2\lambda x_1 - 6 \lambda \\ 1 = 2 \lambda x_2 - 6 \lambda \end{cases}$

$\begin{cases} x_1 = \frac{6 \lambda }{2\lambda - 2} \\ x_2 =\frac{1+6 \lambda }{2\lambda} \\ \end{cases}$
然后可以将 $x_1$ 和 $x_2$ 带回去求 $\lambda$ 这里 $\lambda$ 的值可能不是一个值，我们根据不同情况求出函数的最小值。这里就不再赘述了，还是介绍今天重点

KKT 条件

$\begin{cases} \min f(x) \\ g(x) \le 0 \\ \end{cases}$

$\begin{cases} g(x) = 0 \\ g(x) < 0 \end{cases}$

$g(x) = 0$ 不再是我们之前说的拉格朗日乘子的等式约束，而是一个不等式约束，开始看起来觉得很难不过有了拉格朗日乘子的基础，KKT 也就显得不那么难。可以写成下面式子

$L = f(x) + \alpha g(x)$
接下来我们看一看上面式子需要满足什么样条件才成立
$\begin{aligned} \alpha \ge 0 \\ g(x) \le 0 \\ \begin{cases} g(x) = 0\\ g(x) < 0 & \alpha = 0 \end{cases} \rightarrow \alpha g(x) = 0 \end{aligned}$

我们一个一个地看一看这些约束条件
所以 $\alpha \ge 0$ 因为我们知道 $f(x)$ 与 $g(x)$ 梯度是相反的，所以 $\alpha \ge 0$ 的条件，而且 $g(x) \le 0$ 这是已知的约束条件

kkt.png

$f(x)$ 的最小值可能是落到 $g(x) \le 0$ 区域内，也可能落在区域外。如果 $f(x)$ 的最小值可能是落到 $g(x) \le 0$ 区域内(如上图左侧图)，那么带有条件约束的最小值就是 $f(x)$ 最小值，这是 $\alpha = 0$ 并且 $g(x) < 0$ 。如果 $f(x)$ 没有落在限制条件(如上图右侧图),也就是等价于带有 $g(x)=0$ 拉格朗日乘子法条件, $g(x) = 0$ ,这两两种情况就可以推导出 $\alpha g(x) = 0$ 的条件。

最后希望大家关注我们微信公众号

wechat.jpeg

2020机器学习SVM-KKT条件(2)

甜点

回归拉格朗日

KKT 条件

猜你喜欢

热点阅读