• 为了保证你在浏览本网站时有着更好的体验,建议使用类似Chrome、Firefox之类的浏览器~~
    • 如果你喜欢本站的内容何不Ctrl+D收藏一下呢,与大家一起分享各种编程知识~
    • 本网站研究机器学习、计算机视觉、模式识别~当然不局限于此,生命在于折腾,何不年轻时多折腾一下

机器学习导论(附录)–拉格朗日乘子法

ml admin 3年前 (2016-11-22) 1681次浏览 0个评论 扫描二维码

在 LDA 线性判别分析中使用到拉格朗日乘子法,本着从理论到实践搞清楚机器学习原理,深入研究下每个方法的本质,虽然百度会有一大堆介绍,自己也尝试在此基础上使用白话的方式来阐述

最优化问题分类

最优化问题有如下几类:

(i) 无约束优化问题,可以写为:

min f(x);

(ii) 有等式约束的优化问题,可以写为:

min f(x),

s.t. h_i(x) = 0; i =1, …, n

(iii) 有不等式约束的优化问题,可以写为:

min f(x),

s.t. g_i(x) <= 0; i =1, …, n

h_j(x) = 0; j =1, …, m

对于第(i)类的优化问题,常常使用的方法就是 Fermat 定理,即使用求取 f(x)的导数,然后令其为零,可以求得候选最优值,再在这些候选值中验证;如果是凸函数,可以保证是最优解。

对于第(ii)类的优化问题,常常使用的方法就是拉格朗日乘子法(Lagrange Multiplier) ,即把等式约束 h_i(x)用一个系数与 f(x)写为一个式子,称为拉格朗日函数,而系数称为拉格朗日乘子。通过拉格朗日函数对各个变量求导,令其为零,可以求得候选值集合,然后验证求得最优值。

对应的函数可以表示为

F(x,y)=f(x,y)+lambda*h_i(x,y)

分别对变量 x 和 lambda 求导,得到最优化问题的求解

数学解释

359cdc26e15205e66204bce2b33e4535_r上述圆形虚线圈表示等高线,等高线的概念(可以想象一个山从山顶往下俯视就会得到不同山高度的等高线,类似上图一圈一圈)

g(x,y)相当于之前给定的方程中的 h_i(x,y)也是优化问题中的约束条件,g(x,y)与等高线存在相交和相切的时候。相交的点符合最优化问的解,但是相交点并不是我们需要的点,为什么?如果二者相交,证明还存在相应的等高线使得达到最大值或者最小值,当前的点并不是最优的。

efc7e83116906f8ffebba8b0ab58dcd2_b上图红色约束条件与等高线相交,必然还存在其他等高线符合约束条件且达到最优。

所以不言而喻二者在相交的时候就会达到最优值,此时二者在该点的法向量相同方向或者相反,因此

对 F(x,y)=f(x,y)+lambda*h_i(x,y)求解 x 偏是函数在无约束条件下的充分条件


Deeplearn, 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明机器学习导论(附录)–拉格朗日乘子法
喜欢 (0)
admin
关于作者:
互联网行业码农一枚/业余铲屎官/数码影音爱好者/二次元

您必须 登录 才能发表评论!