2020 机器学习之SVM(1)

作者: zidea | 来源:发表于2020-01-08 21:01 被阅读0次

2020 机器学习之SVM(1)
2020 机器学习之SVM(3)
2020 机器学习之SVM(2)
2020 机器学习之SVM(F)
总结一点面试问题－－算法工程师（机器学习）
机器学习之SVM
7.machine_learning_SVM
2020机器学习SVM SMO
2020机器学习SVM(3)
机器学习SVM，小白也能看得懂 , 从理论到实践！！！

machine_learning.jpg

统计学习SVM

今天我们就开始最难懂的 SVM，首先在开始介绍 SVM 之前先介绍一下拉格朗日。在线性回归中，已经知道如何来解决一个问题，首先我们找到损失函数，然后通过让损失函数最小来不断优化参数。在 SVM 中优化问题变成了有约束条件的优化。SVM 是一个难懂算法，要想真正掌握 SVM 并非一件易事。我们需要了解凸优化问题、拉格朗日乘子和对偶问题。
还有人说 SVM 核心是** Hinge Loss 函数和核函数**。有专门的厚厚的书专门用来介绍 SVM，感兴趣可以自己买来读一读。

我们先从优化问题讲起，只有了解不等式约束条件的优化问题，也就是拉格朗日算法我们才能真正理解 SVM 算法。

通常我们的问题是没有约束条件的优化，例如
$\begin{aligned} min f(x) & x \in \mathbb{R} & or & x \in \mathbb{R}^n \end{aligned}$
我们可以引入等式 h(x) 约束条件来约束 f(x) 的优化问题，也就是在保证 h(x) 等于 0 条件下来优化 f(x)。
$\begin{cases} \min f(x) = 0 \\ s.t. & h(x) = 0 \end{cases}$

当然我们约束条件可能不止一个约束条件可能是 i 个约束条件。
$\begin{cases} \min f(x) = 0 \\ s.t. & h_i(x) = 0 \end{cases}$

还可能有非等式的约束条件，例如我们添加小于等于 0 约束条件 g(x)，可能你会问可以是大于等于 0 的约束条件不? 当然可以不过我们将大于等于 0 的约束条件转化为小于等于 0 的约束条件。
$\begin{cases} \min f(x) = 0 \\ s.t. & h_i(x) = 0 & g(x) \le 0 \end{cases}$

$\begin{cases} \min f(x) = 0 \\ s.t. & h_i(x) = 0 & i = 1,2, \dots , n\\ s.t. & g(x)_j \le 0 & j = 1,2, \dots m \end{cases}$

今天我们介绍过程也是从简单无条件约束优化到不等式优化来逐步递进给大家分享如何理解 SVM。

无约束条件的优化问题

我们先将问题简化为无约束条件下求极值的优化问题，
$\min_x f(x) = x^2 (x \in \mathbb{R})$
$\begin{aligned} f(x) = x^2 \\ \nabla_x f(x) = 0 \\ \nabla_x f(x) = 0 \Rightarrow 2x = 0 \Rightarrow x = 0 \end{aligned}$
<img src="images/001.png" width="60%"/>
上面推导我们在一个最简单方式求导过程，在导数为 0 位置也就是函数极值位置。多维空间,我们对每一个特征相对函数进行求导
$\nabla_{x_j}f(x_j) = 0$

等式约束条件优化问题

有关优化问题，我们先将约束条件从不等式简化为等式，将求极值问题转化为在等式约束条件下求极值问题。
$\begin{cases} \min_x f(x) = x_1 + x_2 \\ s.t. & h(x) = x_1^2 + x_2^2 -2 = 0 \end{cases}$

就是在 $x_1^2 + x_2^2 -2 = 0$ 约束条件下求 $f(x) = x_1 + x_2$ 函数的极值。

002.png

这张图是我精心绘制的，图中红色线表示 $x_1 + x_2 = 0$ 函数，我们这里以间隔 1 进行绘制，大家可以理解为函数f(x) 的等高线。蓝色圆表示等式约束条件。
其中 $x_1 + x_2 = 0$ 这条线穿过圆心的斜率为 -1 的直线。在任何一点都可以有一条平行直线，我们这里将这些间隔为 1 来选取直线理解为 f(x) 的等高线。

然后绘制出h(x)的图像，表示一个以 $\sqrt{2}$ 半径,圆心在(0,0)的圆，这样我更直观地观察他们之间关系。这里约束条件就是要求我们 $x_1$ 和 $x_2$ 都要落在这个圆上,因为在圆上的任意一点都满足h(x)的约束条件，然后我们在这个圆上找到合适点，也就是 x1 + x2 值是最小，这一点也就是最优解，现在我们也就是把一个优化问题变成几何问题，这些平行的线我们通常叫做等高线。

什么样的点是极值点呢?下面内容会有些难度，假设点 $X_F$ 附近移动 $\delta_x$ ( $\delta_x$ 这里是一个非常小的数)距离,后满足下面条件, 首先 $X_F$ 移动一个距离，其中 $\um$ 是一个常数有点类似梯度下降中学习率，其中 $\delta_x$ 是一个趋近无穷小的单位，移动一个距离后点还落在约束条件(圆）上。
$\begin{cases} \delta_x: h(X_F + \mu \delta_x) = 0\\ f(X_F + \mu \delta_x) < f(X_F) \end{cases}$

并且移动后在函数值 $f(X_F + \mu \zeta_x)$ 要小于 $f(X_F)$ 值，也就是我们沿着梯度下降的方向进行移动。这是我们期望移动方向。

有了移动距离，那么移动方向是要满足 $f(X_F + \mu \delta_x) < f(X_F)$ 因为我们希望每一次移动后都会变小，也就是沿梯度下降进行移动这样来找最小值。

$\begin{aligned} f(x) = x_1 + x_2 \\ \frac{\partial f(x_1,x_2)}{\partial x_1} = 1 \\ \frac{\partial f(x_1,x_2)}{\partial x_2} = 1 \\ \nabla_{x_1,x_2} f(x_1,x_2) = \begin{bmatrix} 1 \\ 1 \end{bmatrix} \end{aligned}$

因为f(x)中有两个变量，梯度也就是二维向量来表示分别在x1 和 x2 两个方向的梯度，我们知道梯度为零处函数出现极值，这里偏导向量 $[1,1]^T$ 表梯度方向，因为损失函数通常是 $\theta - \eta \frac{\partial J(\theta)}{\partial \theta}$ 所以我们更新是其负梯度。
图(svm_2)

$\begin{cases} \vec{a} \cdot \vec{b} > 0 \\ \vec{a} \cdot \vec{b} = 0 \\ \vec{a} \cdot \vec{b} < 0 \end{cases}$

$\begin{cases} \frac{\partial h(x_1,x_2)}{\partial x_1} = 2 x_1 \\ \frac{\partial h(x_1,x_2)}{\partial x_2} = 2 x_2 \\ \end{cases} \Rightarrow \begin{bmatrix} 2 x_1 \\ 2 x_2 \end{bmatrix}$

那么在(1,-1)点的梯度为(2,-2),而在(-1,-1)点的梯度为(-2,-2),然后我们来看f(x)和h(x)两者之间的梯度关系。
$$\begin{cases}
\delta_x \perp \nabla_x h(X_F) \
h(X_F + \delta_x) = 0 \
\delta_x \cdot (-\nabla_x f(X_f)) = 0

\end{cases} $通过上面不等式图我们$ -\nabla_x f(X_F) = \mu \nabla_x h(X_F)$$

$\begin{cases} min_x f(x) \\ s.t. & h(x) = 0 \end{cases} \Rightarrow L(x,\mu) = f(x) + \mu h(x)$
这里 $\mu$ 就是拉格朗日乘子，我们

$\frac{\partial L}{\partial x} = \nabla_x f(x) + \mu \nabla_x h(x)$

先说说 SVM 这个模型，早在深度学习出现之前 SVM 曾经盛行一时。SVM 良好的表现和其背后算法被多数工程人员所接受。让数学理论里实际应用不再那么遥远。我们可以真真切切体会到数据给我们带来福利。

之前我们讲了等式约束条件下如何求取一个函数的最优解。今天我们来说一说在不等式约束条件下求函数的最优解的方法

不等式约束条件

$\begin{cases} min_x f(x) \\ s.t. & g(x) \le 0 \end{cases}$
这里我们还是通过一个实际的例子来讲解有关在不等式条件下如何解函数的最优解，下面 f(x)
$\begin{cases} f(x) = x_1^2 + x_2^2 \\ g(x) = x_1^2 + x_2^2 - 1 \le 0 \end{cases}$

003.png

f(x) 是用一个一圆一圆的等高线来表示方程 f(x) 也就是上图中的绿色的线，从上图来看，很清楚我们限制条件就是 g(x) ，图中用浅黄色表示圆形面积为约束条件

1 情况 f(x) 函数最优点落在限制条件 g(x) 面积(浅黄色区域)内

<img src="images/003.png" width="80%"/>
就可以按照非限制条件来正常处理，也就是f(x)全局最优解就是f(x)的最优解。
$\nabla_x f(x) = 0$
$\Rightarrow \begin{matrix} 2x_1 \\ 2x_2 \end{matrix} = 0$

如果计算出全局最优解不满足限制条件，这就是第二种情况，也就是f(x)的全局最有点没有落在限制条件内

004.png

2 情况 f(x) 函数函数最优点没有落在限制条件g(x)区域内

$\begin{cases} f(x) = (x_1 - 1.5)^2 + (x_2 - 1.5)^2 \\ g(x) \le 0 \end{cases}$

$L(x,\lambda) = f(x) + \lambda g(x)$
$\begin{cases} 1. \nabla_x \perp (x^*,\lambda^*) \\ 2. \lambda^* \ge 0 \\ 3. \lambda^* g(x^*) = 0 \begin{cases} \lambda =0 \Rightarrow L(x,\lambda) = f(x) \\ g(x) = 0 \Rightarrow \lambda > 0 \end{cases} \\ 4. g(x^*) \le 0 \end{cases}$

f(x)负梯度与 g(x) 法向方向平行，也就是方向相同他们之间可能就差系数 $\lambda$
如果 $\lambda$ 这时候约束条件可以等价于 g(x)=0 ，也就是 KKT 条件

满足第一个条件

$\nabla_x \perp (X^*,\lambda^*) = 0$

$\frac{L(x,\lambda)}{\partial x} \begin{aligned} = \nabla_x f(x) + \lambda \nabla_x g(x) \\ \Rightarrow -\nabla_x f(x) = \lambda \nabla_x g(x) \end{aligned}$

满足第二个条件

$\lambda \ge 0$

满足第三个条件

$\lambda^* \cdot g(x) = 0$

举一个例子

005.png

我们用上面学过的知识来解决这个不等式约束条件。
$\begin{cases} \min_{x} x^2 \\ s.t. & x \ge b & (b - x \le 0) \end{cases}$
$\begin{cases} L(x, \lambda) = \underbrace{x^2}_{f(x)} + \lambda \underbrace{(b - x)}_{g(x)}\\ \lambda \ge 0 \end{cases}$
这样我们用拉格朗日乘子来表示上面不等式约束条件问题，计算最优解过程就是对 lambda 和 x 进行求取偏导。

$\frac{\partial L}{\partial x} = 2x - \lambda = 0 \Rightarrow x^{*} = \frac{\lambda}{2}$

$\frac{\partial L}{\partial \lambda} = b - x = 0 \Rightarrow x = b \Rightarrow \frac{\lambda}{2} = b \Rightarrow \lambda^{*} = 2b$

如果 lambda 等于 0 那么 f(x) 全局最优解就是 0,因为 lambda 等于就等于 g(x) 等于 0
如果 lambda 不等于 0 就变成 g(x) = 0 的等式约束条件，那么 x = b 才能够满足约束条件，此时 lambda = 2b
$\lambda^{*} = \max(0,2b)$
由此可见 lambda 是取值是 2b 和 0 的最大值，当 b 为负数时候 lambda 就取 0 反之取 2b
有两种情况如果全局最优解在约束条件内也就是 $\lambda = 0$ ,最优解不在约束条件内外，那么 $\lambda$ 就是一个不等于 0 的数时候就可以计算 $\lambda = 2b$
$x^{*} = \begin{cases} 0 \\ b \end{cases}$

$\begin{cases} min_{x} f(x) \\ s.t. & h_i(x) = 0 & i= 1,2,\dots l \\ s.t. & g_j(x) \le 0 & j= 1,2,\dots m \\ \end{cases}$

$L(x,\mu, \lambda) = f(x) + \sum_{i=1}^l \mu_i h_i(x) +\sum_{j=1}^m \lambda_j g_j(x)$

wechat.jpeg

2020 机器学习之SVM(1)
统计学习SVM 今天我们就开始最难懂的 SVM，首先在开始介绍 SVM 之前先介绍一下拉格朗日。在线性回归中，已经...
2020 机器学习之SVM(3)
上一次我们已经将目标函数和约束条件基本都用数学形式表示出来，今天我们先看一看什么是对偶问题。然后开始通过一些列推导...
2020 机器学习之SVM(2)
之前我们已经学习如何在等式约束条件，随后又加入了不等式约束条件下最函数最优解，也就是 KKT 条件。有了这些基础今...
2020 机器学习之SVM(F)
我们发现 i 和 j 都是从 1 取到 N 的，对偶形式 i j 也就是 alpha1 需要和从 alpha1 到...
总结一点面试问题－－算法工程师（机器学习）
BAT机器学习面试系列 1.请简要介绍下SVM。 SVM，全称是support vector machine，中文...
机器学习之SVM
SVM 概述 SVM(支持向量机)，是一种分类算法，用一个超平面将数据分成两份。N维的数据需要(N-1)维的超平面...
7.machine_learning_SVM
1 机器学习支持向量机补充阅读资料：攀登传统机器学习的珠峰-SVM (上)[https://zhuanlan....
2020机器学习SVM SMO
甜点坚持是苦的，坚持也是甜点，过程是苦的，回味是甜，这就是为什么苦的东西慢慢体味会有一丝甜味的原因。假设今天能...
2020机器学习SVM(3)
甜点生活中有太多束缚我们无法打破，吃的太多无法消化；睡得太少感觉困倦。这一切都是创造时预先设定，有了约束也就是有...
机器学习SVM，小白也能看得懂 , 从理论到实践！！！
Blog - 机器学习-SVM 机器学习-SVM-小白也能看得懂演讲•公开课科技bilibili哔哩哔哩 http...

2020 机器学习之SVM(1)

统计学习SVM

无约束条件的优化问题

等式约束条件优化问题

不等式约束条件

1 情况 f(x) 函数最优点落在限制条件 g(x) 面积(浅黄色区域)内

2 情况 f(x) 函数函数最优点没有落在限制条件g(x)区域内

满足第一个条件

满足第二个条件

满足第三个条件

举一个例子

相关文章

2020 机器学习之SVM(1)

2020 机器学习之SVM(3)

2020 机器学习之SVM(2)

2020 机器学习之SVM(F)

总结一点面试问题－－算法工程师（机器学习）

机器学习之SVM

7.machine_learning_SVM

2020机器学习SVM SMO

2020机器学习SVM(3)

机器学习SVM，小白也能看得懂 , 从理论到实践！！！

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

机器学习与计算机视觉

深度学习