12.gitchat训练营-SVM——直观理解拉格朗日乘子法

作者: 风吹柳_柳随风 | 来源:发表于2019-03-11 17:45 被阅读0次

12.gitchat训练营-SVM——直观理解拉格朗日乘子法
【TODO】支持向量机学习笔记
02 SVM - 拉格朗日乘子法
支持向量机SVM
拉格朗日乘子法
03 SVM - KKT条件
机器学习数学原理（7）——SVM支持向量机
SVM系列第六讲--拉格朗日乘子法
拉格朗日乘子法和 KKT 条件
SVM(1) 之拉格朗日乘子法和KKT条件

可视化函数及其约束条件

我们用二元函数——也就是自变量为2维的函数——来做个例子（为了看着更习惯一点，我们直接用 $x$ ， $y$ 作为自变量的两个维度）。

（被约束的）函数

我们之前有过可视化函数本身的经验。此处我们先要可视化一个二元函数 $f(x,y)$ 。
用一个大家熟悉的表达方式： $z = f(x,y)$ 。这就涉及到了3个变量 $x$ ， $y$ 和 $z$ 。
如果在三维直角坐标系中将 $f(x,y)$ 做出图来，比如下面几幅图，分别对应不同的 $f(x,y)$ ：

image

（函数的）约束条件

函数 $f(x,y)$ 的约束条件为： $g(x,y) = 0$ 。 $g(x,y) = 0$ 又可以写成： $y = h(x)$ 的形式——它所表达的是 $x$ 与 $y$ 两者之间的相互关系。

约束条件对函数的约束

        那么，一个二维图形对一个三维图形的约束从何体现呢？让我们这样做：
                1.在自己的头脑中建立一个三维直角坐标系，有 $x$ 轴、 $y$ 轴、 $z$ 轴，它们互相垂直。
                2. $f(x,y)$ 对应图形是三维坐标系里面的一个曲面——一个（可能是奇形怪状的）“体”的“外皮”。
                3.在 $z = 0$ 的平面上，把 $y=h(x)$ 的图形（一条曲线）画出来。
                4.将第 3 步做出的那条曲线沿着平行 z 轴的方向平移，它平移过的轨迹也形成了一个曲面，这个曲面和 $z = f(x,y)$ 形成的曲面会相交，交叠的部分是一条三维空间中的曲线。
                4.换个角度考虑，第 4 步形成的曲线，其实就是 $g(x,y) = 0$ 在 $z=0$ 平面上形成的曲线，在 $z=f(x,y)$ 形成的曲面上的投影。

拉格朗日乘子法

目标函数

        线性可分 SVM 的目标函数：
$min\frac{||w||^2}{2}$
$s.t.\;\; 1- y_i(w·x_i + b) \leqslant 0， i=1，2，…, m$
        其中的自变量为 $w$ 和 $b$ ，也是一个二元函数（ $x_i$ 和 $y_i$ 都是样本值，已知数值， $\frac{||w||^2}{2}$ 虽然只包含 $w$ ，但我们可以想象它也是一个二元函数，只不过变量 $b$ 的系数为 $0$ ）。
        所以，我们可以再抽象一步，将其概括为：
$min f(x,y)$
$s.t. g(x,y) \leqslant 0$
        这个约束条件其实可以写作：
$s.t.\;\; g(x,y) = 0 \;\;OR \;\;g(x,y) < 0$
        因为不等式约束条件难度稍大，我们先从等式约束条件开始。

等式约束条件

假设，我们的目标函数是：
$min f(x,y)$
$s.t. g(x,y) = 0$
现在我们在一张图中做出 $f(x,y)$ 和 $g(x,y)$ 的等高线（三维图形投影到二维平面后的结果），形如下图：

image
绿线是

g(x,y)

的等高线，因为约束条件是

g(x,y) = 0

，因此，只有一条

g(x,y)

的等高线——

g(x,y) = 0

对我们有意义，因此只画它即可。
蓝线是

f(x,y)

的等高线。图中两条蓝线具体对应的函数分别是

f(x,y) = d_1

和

f(x,y) = d_2

。

d_1

和

d_2

是两个常数，对应上图中两个蓝圈对应的

z

轴坐标。此处，

d_2 < d_1

。
图中红点映射到

f(x,y)

上，就是取得

f(x,y)

符合

g(x,y) = 0

的约束的极小值的点。
我们设红点的自变量值为

(x^*, y^*)

。此处我们需要用到一个概念——函数的梯度：表示该函数在某点处的方向导数，方向导数是某个多维函数上的点沿每个维度分别求导后，再组合而成的向量。记作：

\nabla_{x,y} g = (\frac{\partial{g}}{\partial{x}}, \frac{\partial{g}}{\partial{y}})

我们知道，一个函数的梯度与它的等高线垂直。因此，在红点处，

f(x^*,y^*)

的梯度与

f(x,y) = d_2

在

(x^*，y^*)

处的切线垂直，

g(x^*,y^*)

的梯度与

g(x,y) = 0

在

(x^*，y^*)

处的切线垂直。又因为

f(x,y) = d_2

对应的蓝线与

g(x,y) = 0

对应的绿线在

g(x^*,y^*)

处是相切的。
在

(x^*，y^*)

点处

f(x,y)

与

g(x,y)

的梯度，要么方向相同，要么方向相反。
所以，一定存在

\lambda \ne 0

，使得：

\nabla_{x,y}f(x^*,y^*) + \lambda \nabla_{x,y}g(x^*,y^*) = 0

这时我们将

\lambda

称为拉格朗日乘子！

拉格朗日乘子和拉格朗日函数

        定义拉格朗日函数： $L(x,y,\lambda) = f(x,y) + \lambda g(x,y)$ —— 其中 $\lambda$ 是拉格朗日乘子。拉格朗日函数把原本的目标函数和其限制条件整合成了一个函数。
        拉格朗日函数对 $x$ ， $y$ 求偏导：
$L'_{x,y}(x,y,\lambda) =f'_{x,y}(x,y) + \lambda g'_{x,y}(x,y)$
        我们令拉格朗日函数对 $x$ ， $y$ 求偏导的结果为 $0$ ，则有：
$f'_{x,y}(x,y) + \lambda g'_{x,y}(x,y) = 0$
        我们刚才已经知道了， $f(x,y)$ 符合 $g(x,y) = 0$ 约束的极小值的点 $(x^*,y^*)$ 满足： $\nabla_{x,y}f(x^*,y^*) + \lambda \nabla_{x,y}g(x^*,y^*) = 0$ ，用导函数表示就是： $f'_{x,y}(x^*,y^*) + \lambda g'_{x,y}(x^*,y^*) = 0$ 。也就是说我们要求的极小值点正好满足拉格朗日函数对 $x、y$ 求导后，令其结果为 0 形成的导函数。
        既然如此，我们当然也就是可以直接引入一个新的变量： $\lambda$ —— 拉格朗日乘子，和目标函数、约束条件一起，先构造出拉格朗日函数 $L(x,y, \lambda)$ 。
        然后再令 $L'_{x,y}(x,y,\lambda) = 0$ ，之后通过最优化 $L'_{x,y}(x,y,\lambda) = 0$ ，求取 $(x^*,y^*)$ 的值。
        另外，而令拉格朗日函数对 $\lambda$ 求偏导的结果为 $0$ ： $L'_\lambda(x,y,\lambda) = 0$ ，就得到了约束条件： $g(x, y) = 0$ 。
        拉格朗日函数也可以通过求导变化成约束条件本身。于是，原本有约束的优化问题，就可以转化为对拉格朗日函数的无约束优化问题了。

不等式约束条件

        当条件是： $g(x,y) \leqslant 0$ 时, 我们可以它拆分成： $g(x,y) = 0 \;\; OR \;\;g(x,y) < 0$ ，两种情况来看。这两种情况下可以先各取一个极小值，再比较一下，哪个更小就用哪个。
        拆分后的严格不等式约束条件： $g(x,y) < 0$ 。而对于 $g(x,y) < 0$ 情况，因为 $< 0$ 是一个区间，而不再是对应到三维坐标中的某个固定的曲面。这种情况下，如果 $f(x,y)$ 的极小值就在这个区间里，然后直接对 $f(x,y)$ 求无约束的极小值就好了。
        对应到拉格朗日函数就是：令 $\lambda = 0$ ，直接通过令 $f(x,y)$ 的梯度为 $0$ 求 $f(x,y)$ 的极小值。求出极小值 $f(x^*,y^*)$ 之后，再判断 $(x^*,y^*)$ 是否符合约束条件。
        拆分后的等式约束条件： $g(x,y) = 0$
        只有当 $f(x,y)$ 梯度方向和 $g(x,y) <0$ 区域所在方向相同，也就是和 $(x^*,y^*)$ 点处 $g(\cdot)$ 函数梯度方向相反，那么 $f(x,y)$ 的约束条件极小值才会出现在 $g(x,y)=0$ 的曲线上。
        所以，在这种情况下，存在常数 $\lambda > 0$ ，使得 $f'_{x,y}(x^*,y^*) = - \lambda g'_{x,y}(x^*,y^*)$ ，进一步导出：
$f'_{x,y}(x^*,y^*) + \lambda g'_{x,y}(x^*,y^*) = 0,\;\; \lambda > 0$

KKT 约束条件

        我们将上面拆分开的严格不等式和等式两种情况再整合起来:
                1.如果严格不等式成立时得到 $f(\cdot)$ 函数的极小值，则有 $\lambda=0$ ，这样才能将拉格朗日函数直接转换为原始函数。则有 $\lambda g(x,y) = 0$ 。
                2.如果等式成立时得到 $f(\cdot)$ 函数的约束条件极小值，则必然存在 $\lambda > 0$ ，且同时 $g(x,y) = 0$ , 因此也有 $\lambda g(x,y) = 0$ 。
        于是，对于不等式约束条件 $g(x,y) \leqslant 0$ ，最终的约束条件变成了：
$g(x,y) \leqslant 0$
$\lambda \geqslant 0$
$\lambda g(x,y) = 0$
这样由1变3的约束条件，叫做KKT 约束条件。

目标函数转化为拉格朗日函数

        当然，KKT 条件不是单独成立的，它是拉格朗日乘子法的一部分！
        当我们在约束条件下求解函数最优化问题，且约束条件为不等式时（问题描述如下）：
$Optimize\;\; f(x,y)$
$s.t. \;\; g(x,y) \leqslant 0$
        我们针对目标函数生成拉格朗日函数为：
$L(x,y,\lambda) = f(x,y) + \lambda g(x,y)$
        同时有 KKT 条件： $g(x,y) \leqslant 0$
$\lambda \geqslant 0$
$\lambda g(x,y) = 0$
        假设最优化结果对应点为 $(x^*, y^*)$ ，则当目标函数为：
$min f(x,y)$
$s.t. \;\; g(x,y) \leqslant 0$
时，若存在 $\lambda \ne 0$ ，使得 $f'_{x,y}(x^*,y^*) + \lambda g'_{x,y}(x^*,y^*) = 0$ ，则 $\lambda > 0$ 。
        而当目标函数为：
$max f(x,y)$
$s.t. \;\; g(x,y) \leqslant 0$
时，若存在 $\lambda \ne 0$ ，使得 $f'_{x,y}(x^*,y^*) + \lambda g'_{x,y}(x^*,y^*) = 0$ ，则 $\lambda < 0$ 。

12.gitchat训练营-SVM——直观理解拉格朗日乘子法
可视化函数及其约束条件我们用二元函数——也就是自变量为2维的函数——来做个例子（为了看着更习惯一点，我们直接用，...
【TODO】支持向量机学习笔记
？？拉格朗日乘子法？？Soft Margin的优化 SVM基本思想 SVM用来解决线性不可分问题。基本思想是，把原...
02 SVM - 拉格朗日乘子法
01 SVM - 概述自变量无约束的求极值方法 - 梯度下降法 10 回归算法 - 梯度下降在线性回归中的应用1...
支持向量机SVM
支持向量机SVM（Support Vector Machine）【关键词】支持向量，最大几何间隔，拉格朗日乘子法...
拉格朗日乘子法
拉格朗日乘子法如何理解？ - 知乎
03 SVM - KKT条件
02 SVM - 拉格朗日乘子法回顾上章，原始问题与对偶问题的关系：结论：1、对偶问题小于等于原始问题。2、当...
机器学习数学原理（7）——SVM支持向量机
机器学习数学原理（7）——SVM支持向量机这篇博文笔者将默认读者已经了解了最优间隔分类器以及泛化拉格朗日乘子法，...
SVM系列第六讲--拉格朗日乘子法
在前面的几讲中，我们终于引出了支撑向量的概念，同时得到了求解最大间隔分类器的目标规划式，接下来，我们就要对该式进行...
拉格朗日乘子法和 KKT 条件
这篇博文中直观上讲解了拉格朗日乘子法和 KKT 条件，对偶问题等内容。首先从无约束的优化问题讲起，...
SVM(1) 之拉格朗日乘子法和KKT条件
其实我之前看过这个地方，但是当时感触不深(或者说根本没看懂,也可能是忘了)，所以重新推导一下。《西瓜书》、《统计...