[机器学习笔记#3] 简明Lagrange multiplier(拉格朗日乘数)讲义

[机器学习笔记#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 的数学模型中有重要体现。

[修改于 3 年前 - 2016-08-06 14:49:59]

来自 机器学习

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

插入资源
全部
图片
视频
音频
附件
全部
未使用
已使用
正在上传
空空如也~
上传中..{{f.progress}}%
处理中..
上传失败,点击重试
{{f.name}}
空空如也~
(视频){{r.oname}}
{{selectedResourcesId.indexOf(r.rid) + 1}}
ID:{{user.uid}}
{{user.username}}
{{user.info.certsName}}
{{user.description}}
{{format("YYYY/MM/DD", user.toc)}}注册,{{fromNow(user.tlv)}}活动
{{submitted?"":"投诉"}}
请选择违规类型:
{{reason.description}}
支持的图片格式:jpg, jpeg, png