可视化函数及其约束条件
我们用二元函数——也就是自变量为2维的函数——来做个例子(为了看着更习惯一点,我们直接用,作为自变量的两个维度)。
(被约束的)函数
我们之前有过可视化函数本身的经验。此处我们先要可视化一个二元函数。
用一个大家熟悉的表达方式:。这就涉及到了3个变量,和。
如果在三维直角坐标系中将做出图来,比如下面几幅图,分别对应不同的 :
(函数的)约束条件
函数的约束条件为:。又可以写成:的形式——它所表达的是与两者之间的相互关系。
约束条件对函数的约束
那么,一个二维图形对一个三维图形的约束从何体现呢?让我们这样做:
1.在自己的头脑中建立一个三维直角坐标系,有轴、轴、轴, 它们互相垂直。
2.对应图形是三维坐标系里面的一个曲面——一个(可能是奇形怪状的)“体”的“外皮”。
3.在的平面上,把的图形(一条曲线)画出来。
4.将第 3 步做出的那条曲线沿着平行 z 轴的方向平移,它平移过的轨迹也形成了一个曲面,这个曲面和形成的曲面会相交,交叠的部分是一条三维空间中的曲线。
4.换个角度考虑,第 4 步形成的曲线,其实就是在平面上形成的曲线,在形成的曲面上的投影。
拉格朗日乘子法
目标函数
线性可分 SVM 的目标函数:
其中的自变量为和,也是一个二元函数(和都是样本值,已知数值,虽然只包含,但我们可以想象它也是一个二元函数,只不过变量的系数为)。
所以,我们可以再抽象一步,将其概括为:
这个约束条件其实可以写作:
因为不等式约束条件难度稍大,我们先从等式约束条件开始。
等式约束条件
假设,我们的目标函数是:
现在我们在一张图中做出和的等高线(三维图形投影到二维平面后的结果),形如下图:
绿线是 的等高线,因为约束条件是 ,因此,只有一条 的等高线—— 对我们有意义,因此只画它即可。
蓝线是 的等高线。图中两条蓝线具体对应的函数分别是 和 。 和 是两个常数,对应上图中两个蓝圈对应的 轴坐标。此处, 。
图中红点映射到 上,就是取得 符合 的约束的极小值的点。
我们设红点的自变量值为 。此处我们需要用到一个概念——函数的梯度:表示该函数在某点处的方向导数,方向导数是某个多维函数上的点沿每个维度分别求导后,再组合而成的向量。记作:
我们知道,一个函数的梯度与它的等高线垂直。因此,在红点处, 的梯度与 在 处的切线垂直, 的梯度与 在 处的切线垂直。又因为 对应的蓝线与 对应的绿线在 处是相切的。
在 点处 与 的梯度,要么方向相同,要么方向相反。
所以,一定存在 , 使得:
这时我们将 称为拉格朗日乘子!
拉格朗日乘子和拉格朗日函数
定义拉格朗日函数:—— 其中是拉格朗日乘子。拉格朗日函数把原本的目标函数和其限制条件整合成了一个函数。
拉格朗日函数对,求偏导:
我们令拉格朗日函数对,求偏导的结果为,则有:
我们刚才已经知道了,符合约束的极小值的点满足:,用导函数表示就是:。也就是说我们要求的极小值点正好满足拉格朗日函数对求导后,令其结果为 0 形成的导函数。
既然如此,我们当然也就是可以直接引入一个新的变量:—— 拉格朗日乘子,和目标函数、约束条件一起,先构造出拉格朗日函数。
然后再令,之后通过最优化,求取的值。
另外,而令拉格朗日函数对求偏导的结果为:,就得到了约束条件:。
拉格朗日函数也可以通过求导变化成约束条件本身。于是,原本有约束的优化问题,就可以转化为对拉格朗日函数的无约束优化问题了。
不等式约束条件
当条件是:时, 我们可以它拆分成:,两种情况来看。这两种情况下可以先各取一个极小值,再比较一下,哪个更小就用哪个。
拆分后的严格不等式约束条件:。而对于情况,因为是一个区间,而不再是对应到三维坐标中的某个固定的曲面。这种情况下,如果的极小值就在这个区间里,然后直接对求无约束的极小值就好了。
对应到拉格朗日函数就是:令,直接通过令的梯度为求的极小值。求出极小值之后,再判断是否符合约束条件。
拆分后的等式约束条件:
只有当梯度方向和区域所在方向相同,也就是和点处函数梯度方向相反,那么的约束条件极小值才会出现在的曲线上。
所以,在这种情况下,存在常数,使得,进一步导出:
KKT 约束条件
我们将上面拆分开的严格不等式和等式两种情况再整合起来:
1.如果严格不等式成立时得到函数的极小值,则有,这样才能将拉格朗日函数直接转换为原始函数。则有。
2.如果等式成立时得到函数的约束条件极小值,则必然存在,且同时, 因此也有。
于是,对于不等式约束条件,最终的约束条件变成了:
这样由1变3的约束条件,叫做KKT 约束条件。
目标函数转化为拉格朗日函数
当然,KKT 条件不是单独成立的,它是拉格朗日乘子法的一部分!
当我们在约束条件下求解函数最优化问题,且约束条件为不等式时(问题描述如下):
我们针对目标函数生成拉格朗日函数为:
同时有 KKT 条件:
假设最优化结果对应点为,则当目标函数为:
时,若存在,使得,则。
而当目标函数为:
时,若存在,使得,则。
网友评论