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

2019-03-11 本文已影响0人风吹柳_柳随风

可视化函数及其约束条件

我们用二元函数——也就是自变量为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$ 。