机器学习是一个目标函数优化问题,给定目标函数f,约束条件会有一般包括以下三类:
- 仅含等式约束
- 仅含不等式约束
- 等式和不等式约束混合型
当然还有一类没有任何约束条件的最优化问题
关于最优化问题,大都令人比较头疼,首先大多教材讲解通篇都是公式,各种符号表达,各种梯度,叫人看的云里雾里。
有没有结合几何图形阐述以上问题的?很庆幸,还真有这么好的讲解材料,图文并茂,逻辑推导严谨,更容易叫我们理解拉格朗日乘数法
、KKT条件
为什么就能求出极值。
1 仅含等式约束
假定目标函数是连续可导函数,问题定义如下:
然后,
通过以上方法求解此类问题,但是为什么它能求出极值呢?
这是本篇文章写作目的,解释为什么这种方法就能求出极值。
2 找找 sense
大家时间都有限,只列出最核心的逻辑,找找sense, 如有兴趣可回去下载PPT仔细体会。
此解释中对此类问题的定义:
为了更好的阐述,给定一个具体例子,锁定:
所以,f(x)的一系列取值包括0,1,100,10000等任意实数:
但是,约束条件h(x)
注定会约束f(x)
不会等于100,不会等于10000...
一个可行点:
3 梯度下降
我们想要寻找一个移动x
的规则,使得移动后f(x delta_x)
变小,当然必须满足约束h(x delta_x)=0
使得f(x
)减小最快的方向就是它的梯度反方向,即
因此,要想f(x delta_x) 变小,通过图形可以看出,只要保持和梯度反方向夹角小于90,也就是保持大概一个方向,f(x delta_x)
就会变小,转化为公式就是:
如下所示的一个delta_x
就是一个会使得f(x)减小的方向,但是这种移动将会破坏等式约束: h(x)=0
,关于准确的移动方向下面第四小节会讲到
4 约束面的法向
约束面的外法向:
约束面的内法向:
绿圈表示法向的正交
方向
x沿着绿圈内的方向移动,将会使得f(x)减小,同时满足等式约束h(x) = 0
5 提出猜想
我们不妨大胆假设,如果满足下面的条件:
根据第四小节讲述,delta_x
必须正交于h(x)
,所以:
所以:
至此,我们就找到f(x)
偏导数等于0的点,就是下图所示的两个关键点(它们也是f(x)与h(x)的临界点)。且必须满足以下条件,也就是两个向量必须是平行的:
6 完全解码拉格朗日乘数法
至此,已经完全解码拉格朗日乘数法,拉格朗日巧妙的构造出下面这个式子:
还有取得极值的的三个条件,都是对以上五个小节中涉及到的条件的编码
关于第三个条件,稍加说明。
对于含有多个变量,比如本例子就含有2个变量x1
, x2
,就是一个多元优化问题,需要求二阶导,二阶导的矩阵就被称为海塞矩阵
(Hessian Matrix)
与求解一元问题一样,仅凭一阶导数等于是无法判断极值的,需要求二阶导,并且二阶导大于0才是极小值,小于0是极大值,等于0依然无法判断是否在此点去的极值。