机器学习中的优化方法小结

2020 年 7 月 26 日 极市平台

加入极市专业CV交流群，与 10000+来自港科大、北大、清华、中科院、CMU、腾讯、百度等名校名企视觉开发者互动交流！

同时提供每月大咖直播分享、真实项目需求对接、干货资讯汇总，行业技术交流。关注 极市平台 公众号，回复 加群，立刻申请入群~

来源｜福大命大@知乎， https://zhuanlan.zhihu.com/p/158215009

前几天听了林宙辰老师的一个报告，讲的是机器学习中的优化方法[1]，做个笔记。推荐机器学习的人去听听。林老师的主页：https://zhouchenlin.github.io/zhouchenlin.github.io

机器学习是离不开优化方法的，Pedro Domingos这样概括机器学习和优化方法的关系：

“Machine learning=Representation+Optimization+Evaluation”

后面三项对应于三步：建立模型，求解模型，验证模型。

一、机器学习中的优化问题

首先介绍一下机器学习中常见的优化问题：

1.分类回归问题

很多的分类回归问题都可以写成问题（1）的一个特例，比如SVM，正则的logistic回归，多层感知器，线性回归，岭回归，Lasso问题等。

2.AdaBoost

通常数据的分类面可能是很复杂的，我们可以通过多个简单的线性分类器组合而成。

3.生成对抗网络

4.AutoML

自动超参数的选取，这是一个双层优化问题。

二、算法的阶数

根据所需要的信息，算法大概分为三种：零阶、一阶、二阶。

1、零阶：只涉及到，适用于函数形式不知道，求不了导数；梯度不存在或者很难计算的情况，比如强化学习。

2、一阶：需要用到函数值和梯度值 ,更一般情况下，可以将函数的proximal 算子也纳入到一阶中。

3、二阶：需要用到函数值和梯度值以及Hessian信息。

机器学习中，一阶用的是最广泛的。当然也不排除有零阶和二阶的，这适用于那些具有特殊结构的问题。

三、机器学习中的优化算法

1.基本模块：

通常的优化算法主要有以下几个模块，将这些模块以不同的方式组合一下就得到了不同的优化方法。

1、梯度下降：，前向运算，也叫forward operator。

2、临近算子：，后向运算，也叫backward operator。

3、对偶：当原问题不好解，或者计算量比较大，可以考虑对偶问题。

4、randomization：当问题（1）的较大或者变量维度较大，可以考虑随机梯度或者坐标下降。

上面的四个模块在不同的拼接下就形成了很多现有的优化算法。

2.机器学习中的无约束优化算法

考虑无约束问题：

假设函数是光滑的（如果不光滑，我们可以用次梯度，光滑化等）

梯度下降
共轭梯度

当目标函数是二次的时候，选出来的方向是共轭方向。

拟牛顿

是处Hessian矩阵逆的近似，需要满足 ,主要有两类近似：秩1和秩2近似。

L-BFGS

上面说到的逆牛顿需要存储一个大的矩阵 ,考虑到他是秩1或秩2近似，因此我们可以通过存储一些向量来代替。

临近梯度算法

考虑可分问题：

其中光滑，为非光滑。临近梯度算法对光滑的那部分做二次近似，每一步求解如下问题：

该算法需要假设对于g的proximal operator是容易计算的。

3.机器学习中的约束优化方法

考虑一般问题：

其中是一个约束集合。

投影梯度方法

首先走一个梯度步，然后投影回去。

罚方法

通过罚参数将约束集放到目标函数上，其中要满足一些条件：连续非负，以及当且仅当。该方法依赖于罚参数。

条件梯度

其中需要是一个紧集（欧氏空间下等价于有界闭集）。方向的求解相当于对函数做泰勒一次展开。这个算法适用于稀疏低秩问题，这时候可能是一个低秩范数球，这时候关于的求解有很高效的算法。

ADMM

当约束是线性约束并且可分的时，可以采用ADMM，考虑问题：

对应的增广拉格朗日函数为：

ADMM算法交替的去更新增广拉格朗日函数中的三个变量：

如果对于还是不好求，我们可以对后面的二次项做线性化，得到线性化的ADMM。

坐标下降方法

如果问题中的变量可以分为多块，比如：

这种情况下可以采取块坐标下降方法：本质上是交替极小的一个扩展。

4.大数据的处理

考虑如下形式的问题：

随机梯度

找到一个近似的方向近似梯度，只要满足即可。有很多的变种，adam，adagrad，adadelta，ada...

四、加速算法

通常情况下的加速策略都是利用内插和外推。

1.确定

Heavy ball

后面那一项称为Momentum。

Nesterov

加速临近梯度

将Nesterov加速应用到了非光滑的可分问题（2）上：

2.随机

考虑问题：

我们可以用梯度方法： , 如果n太大，每一步的计算量太大。

接着我们采用最初的随机梯度方法：，也就是一次选一个去走。

这两个方法似乎都是一种极端，所以中间存在一种tradeoff。思考如何做到在降低variance的情况下计算量不要增长的太快。

SVRG

这个方法的思想就是，每隔一段时间算一次完整梯度，用这个信息去矫正每一步的随机梯度方向。

Katyusha

这个方法是Nesterov加速和variance reduction的结合。（这个名字取得真是让人摸不着头脑，包括下面的Catalyst，还有一个方法SARAH）

Catalyst

注意到第三步，你可以使用任何一个可以计算的方法去求解第三步中的问题

SPIDER

这个相对于SVRG方差更小。

五、展望

大规模优化的展望主要有这几点：

随机化
分布式
异步
learning based
Quantum

最后林老师推荐了机器学习的人应该学习的优化书籍，最后一本是林老师自己的。

参考文献

[1] https://www.bilibili.com/video/BV1uZ4y1u7Ri?t=3131

推荐阅读

添加极市小助手微信 （ID : cv-mart） ，备注： 研究方向-姓名-学校/公司-城市 （如：目标检测-小极-北大-深圳），即可申请加入 极市技术交流群 ，更有 每月大咖直播分享、真实项目需求对接、求职内推、算法竞赛、 干货资讯汇总、行业技术交流 ，一起来让思想之光照的更远吧~