NLP2.2:梯度下降法的收敛性证明

1411-李同学

发表文章数:148

热门标签

, ,
首页 » 算法 » 正文

1、复习凸函数

  • 凸函数有全局最优解
  • 神经网络是非凸函数,有大量的局部最优解,需要好的初始化(pre-training)

2、如何解决一个非凸函数:Set cover problem

NLP2.2:梯度下降法的收敛性证明
NLP2.2:梯度下降法的收敛性证明

2.1 Approach 1: Exhaustive Search——穷举法

  • 1、遍历每一个集合:看它们是否有等于U
  • 2、一次选择两个集合:共有16种不同的方法,看它们的并集是否满足U
  • 3、一次选择三个集合…

考虑了所有的可能的组合,可以得到全局最优解
NLP2.2:梯度下降法的收敛性证明

2.2 Approach 2: Greedy search:贪心算法

每次都考虑局部最优解

  • 1、考虑所有的集合s1,s2,s3,s4,s5,s6,看他的并集是否等于U
  • 2、每次删除掉一个集合,如果删除后,还是满足于U,就可以删掉
  • 3、可以多次尝试,得到不同的局部最优解,筛选出最好的局部最优解

NLP2.2:梯度下降法的收敛性证明
相比于穷举法,时间上高效很多

2.3 Approach 3:Optimization

重点:需要设计变量

  • 对于每个子集和,都有选择和不选择两个决策
  • x=1时,选择si
  • x=0时,没有选择si

如何设计objective function

constraint1:对于任意出现在U中的元素e,必须保证至少选择了一个出现e的所有子集合。
constraint2:xi等于0/1

NLP2.2:梯度下降法的收敛性证明

上述objective function是不是凸函数

  • 保证定义域是凸集
  • 目标也需要convex

对于定义域{0,1},不满足是凸集
所以objective function不是凸函数

Approximation and Relation:问题的松弛化

  • 目标函数是线性的
  • 条件也是线性的
    所以是个linear programming
  • 定义域是整形的
    所以是Integer Linear programming

NLP2.2:梯度下降法的收敛性证明

设定阈值,对结果进行筛选

NLP2.2:梯度下降法的收敛性证明

2.4 Summary

1、

  • Smooth vs Non-smooth
  • Convex or Non-convex
  • Constrained or Non-constrained
  • Continuous or Discrete

2、convex:全局最优解
3、判断convex?

  • 定义域
  • 一阶导数
  • 二阶导数大于等于0
  • preserved operation:例如两个凸函数的相加

4、优化目标的种类

  • least square problem
  • quadratic programming
  • linear programming

5、非凸函数的处理:
Adam,Adagrad,SGD, RMSprof

3、梯度下降法

NLP2.2:梯度下降法的收敛性证明

3.1 梯度下降法的复杂度

收敛性分析

NLP2.2:梯度下降法的收敛性证明
L-Lipschitz: 平滑的函数

NLP2.2:梯度下降法的收敛性证明
NLP2.2:梯度下降法的收敛性证明
NLP2.2:梯度下降法的收敛性证明
NLP2.2:梯度下降法的收敛性证明
NLP2.2:梯度下降法的收敛性证明
NLP2.2:梯度下降法的收敛性证明
NLP2.2:梯度下降法的收敛性证明

未经允许不得转载:作者:1411-李同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《NLP2.2:梯度下降法的收敛性证明》 发布于2021-02-13

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

Vieu3.3主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录