[机器学习笔记#3] 简明Lagrange multiplier(拉格朗日乘数)讲义
Cirno2016/08/06软件综合 IP:美国

[机器学习笔记#1]从 Logistic Regression 讲讲分类器和机器学习
[机器学习笔记#2] 一步步用 softmax Regression 实现手写字符识别
[资源分享]机器学习资料和常用工具汇总

(这次的笔记是为了以后的内容做准备,提前介绍一些基础数学知识,以便日后引用)

在机器学习中经常会遇到一类受限优化问题,要求某目标函数在限制条件下的最优值点。

最基本的一类问题可简述为:

问题1:给定目标函数 \(f(x)\)(假设convex),求当x取值满足\(g(x)=0\)的条件下,x的最优值使得\(f(x)\)的值最小/最大。

例如:
$$ x=\underset {x}{argmax} \ \ f(x) $$ $$ s.t. \quad g(x)=0 $$ 由于这里我们预先假设\(f(x)\)是一个凸函数(convex function),当不存在限制条件时,其最大值当取在使得\(\nabla f(x)=0\)处。而存在限制条件时,表示x在定义域中的位置必须落在曲面\(g(x)=0\)上,可想象为x在该曲面表面滑动,直到找到使得\(f(x)\)最大的位置时停止。

我们可以非常自然的得到一个结论:满足此条件的位置\(x_A\)上,必然有\(\nabla f(x)=\lambda \nabla g(x)\),其中\(\lambda\)是非零实变量,被称为拉格朗日乘数(Lagrange multiplier)。如下图所示(图片出自PRML P. 708)。
Screenshot from 2016-08-05 19:03:03.png 因为如果在此处\(\nabla f(x)\)和\( \nabla g(x)\)不共线,\(\nabla f(x)\)将在该点有一个切向分量,x可沿该分量方向运动,到达一个使 \(f(x)\) 更大的点(参考gradient ascend),最终会稳定在一个使得 \(\nabla f(x)\) 和\( \nabla g(x)\) 共线的位置。
Screenshot from 2016-08-05 19:03:03_2.png
所以可知求解问题1中的受限优化问题,等同于求解:
$$ x,\lambda=\underset {x,\lambda}{argmax} \ \ L(x,\lambda) $$ $$ L(x,\lambda)=f(x)+\lambda g(x),\ \ \lambda \neq 0 $$ $$ s.t.\ \ \nabla_x L(x,\lambda)=0, \ \ \nabla_{\lambda}L(x,\lambda)=0 $$
其中\(L(x,\lambda)\)被称为拉格朗日方程。

以下借用PRML中的一个例子,令: $$ \textbf{x}=(x_1,x_2), \ \ f( \textbf{x})=1-x_1^2-x_2^2, \ \ g(\textbf{x})=x_1+x_2-1=0 $$
即如下图示:
Screenshot from 2016-08-05 19:56:05.png 所以: $$L(\textbf{x},\lambda)=1-x_1^2-x_2^2+\lambda(x_1+x_2-1) $$ 求导得:
$$ -2x_1+\lambda=0 $$ $$ -2x_2+\lambda=0 $$ $$ x_1+x_2-1=0 $$ 解得 \(x_1=x_2=0.5\)


问题2:给定目标函数 \(f(x)\)(假设convex),求当x取值满足\(g(x)\geq0\)的条件下,x的最优值使得\(f(x)\)的值最小/最大。

例如:
$$ x=\underset {x}{argmax} \ \ f(x) $$ $$ s.t. \quad g(x)\geq0 $$ 问题1中的等式变成了不等式,x的可能取值空间从曲面 \(g(x)=0\) ,变成了 \(g(x)\geq0\)所表示的内部空间j及表面,如下图:
Screenshot from 2016-08-05 20:05:56.png
所以分两种情况考虑:

  1. x 取在 \(g(x)>0\)的腔体内,此时问题跟无限制条件时无区别,所以是求解\( \nabla f(x)=0\),等同于将拉格朗日方程中的\(\lambda\)设为0的情况;
  2. x 取在 \(g(x)=0\)的曲面上,此时优化\(f(x)\)跟问题1无区别,使用拉格朗日方程求解。

整合起来就是求:
$$ x,\lambda=\underset {x,\lambda}{argmax} \ \ L(x,\lambda) $$ $$ L(x,\lambda)=f(x)+\lambda g(x) $$ 其中: $$ g(x) \geq0
$$ $$ \lambda \geq0 $$ $$ \lambda g(x)=0 $$ 上述条件被称为 Karush-Kuhn-Tucker 条件,简称 KKT 条件。注意这里是针对 maximization的情况,如果是 minimization, 则拉格朗日方程变为 \(L(x,\lambda)=f(x)-\lambda g(x)\) (原因自己想,提示:当最优解在曲线表面时,即情况2,\( \nabla f(x)\) 应该朝着哪个方向?)。

KKT条件在SVM 的数学模型中有重要体现。

[修改于 7年9个月前 - 2016/08/06 14:49:59]

来自:计算机科学 / 软件综合
0
已屏蔽 原因:{{ notice.reason }}已屏蔽
{{notice.noticeContent}}
~~空空如也

想参与大家的讨论?现在就 登录 或者 注册

所属专业
所属分类
上级专业
同级专业
Cirno
专家 进士 老干部 学者 机友 笔友
文章
34
回复
359
学术分
2
2012/09/03注册,10天10时前活动

Machine Learning, computer vision enthusiast

Google

主体类型:个人
所属领域:无
认证方式:手机号
IP归属地:未同步
文件下载
加载中...
{{errorInfo}}
{{downloadWarning}}
你在 {{downloadTime}} 下载过当前文件。
文件名称:{{resource.defaultFile.name}}
下载次数:{{resource.hits}}
上传用户:{{uploader.username}}
所需积分:{{costScores}},{{holdScores}}下载当前附件免费{{description}}
积分不足,去充值
文件已丢失

当前账号的附件下载数量限制如下:
时段 个数
{{f.startingTime}}点 - {{f.endTime}}点 {{f.fileCount}}
视频暂不能访问,请登录试试
仅供内部学术交流或培训使用,请先保存到本地。本内容不代表科创观点,未经原作者同意,请勿转载。
音频暂不能访问,请登录试试
支持的图片格式:jpg, jpeg, png
插入公式
评论控制
加载中...
文号:{{pid}}
投诉或举报
加载中...
{{tip}}
请选择违规类型:
{{reason.type}}

空空如也

加载中...
详情
详情
推送到专栏从专栏移除
设为匿名取消匿名
查看作者
回复
只看作者
加入收藏取消收藏
收藏
取消收藏
折叠回复
置顶取消置顶
评学术分
鼓励
设为精选取消精选
管理提醒
编辑
通过审核
评论控制
退修或删除
历史版本
违规记录
投诉或举报
加入黑名单移除黑名单
查看IP
{{format('YYYY/MM/DD HH:mm:ss', toc)}}