行业新闻

机器学习中的优化方法_1

前几天听了林宙辰老师的一个报告，讲的是机器学习中的优化方法【1】，做个笔记。推荐机器学习的人去听听。林老师的主页：

https://zhouchenlin.github.io/

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

“Machine learning=Representation+Optimization+Evaluation”

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

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

1.分类回归问题

$\\min_{x\\in \\mathbb{R}^n}\\frac{1}{n}\\sum_{i=1}^nf_i(x)+\\lambda R(x) \\\\ \ ag{1}$

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

2.AdaBoost

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

$\\min_{\\beta,\\gamma}\\sum_{i=1}^nloss\\left(y_i,\\sum_{j=1}^M\\beta_jf_j(x_i;\\gamma_j)\\right) \\\\$

3.生成对抗网络

$\\min_G\\max_D V(D,G)=\\mathbb{E}_{x\\sim p_{data}(x)}[\\log D(x)]+\\mathbb{E}_{z\\sim p_{z}(z)}[\\log (1-D(G(z))]$

4.AutoML

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

$\\begin{split}\\min_{\\lambda}& l_{validation}(w,\\lambda) \\\\ s.t. & \\lambda \\in \\mathcal{C}_1 \\\\ & w\\in \\arg\\min_{w\\in \\mathcal{C}_2}l_{train}(w,\\lambda) \\end{split}\\\\$

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

零阶：只涉及到 $f(x_k)$ ，适用于函数形式不知道，求不了导数；梯度不存在或者很难计算的情况，比如强化学习。
一阶：需要用到函数值 $f(x_k)$ 和梯度值 $\ abla f(x_k)$ ,更一般情况下，可以将函数的proximal 算子也纳入到一阶中。
二阶：需要用到函数值 $f(x_k)$ 和梯度值 $\ abla f(x_k)$ 以及Hessian信息 $\ abla^2 f(x_k)$ 。

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

1.基本模块：

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

梯度下降： $x_{k+1}=x_k - \\alpha_k \ abla f(x_k)$ ，前向运算，也叫forward operator。
临近算子： $x_{k+1}=\\mbox{prox}_{\\alpha f}(x_k)$ ，后向运算，也叫backward operator。
对偶：当原问题不好解，或者计算量比较大，可以考虑对偶问题。
randomization：当问题（1）的 $n$ 较大或者变量维度较大，可以考虑随机梯度或者坐标下降。

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

考虑无约束问题：

$\\min_x f(x) \\\\$

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

梯度下降 $x_{k+1}=x_k - \\alpha_k \ abla f(x_k) \\\\$
共轭梯度

$\\begin{split}\\alpha_k=& \\arg\\min_{\\alpha >0}f(x_k + \\alpha d_k) \\\\ x_{k+1}=& x_k + \\alpha_k d_k\\\\ d_{k+1}=& -\ abla f(x_k) + \\beta_k d_k \\\\ \\end{split}\\\\$

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

拟牛顿

$\\begin{split}d_{k+1}=& -H_k \ abla f(x_k) \\\\ \\alpha_k=& \\arg\\min_{\\alpha >0}f(x_k + \\alpha d_k) \\\\ x_{k+1}=& x_k + \\alpha_k d_k\\\\ \\end{split}\\\\$

$H_k$ 是 $x_k$ 处Hessian矩阵逆的近似，需要满足 $H_{k+1}\ abla g_k=\ abla x_k$ ,主要有两类近似：秩1和秩2近似。

L-BFGS

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

临近梯度算法

考虑可分问题：

$\\min_x f(x) + g(x) \\\\ \ ag{2}$ 其中 $f$ 光滑， $g$ 为非光滑。临近梯度算法对光滑的那部分做二次近似，每一步求解如下问题：

$\\begin{split}x^{k+1}&=\\arg\\min_x f(x^k)+ <\ abla f(x^k),x-x^k>+\\frac{1}{2\\alpha^k}\\|x-x^k\\|^2 + g(x) \\\\ &=\\mbox{prox}_{\\alpha^k g}(x^k - \\alpha^k \ abla f(x^k)) \\end{split}\\\\$

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

考虑一般问题：

$\\min_{x\\in \\mathcal{X}}f(x) \\\\$ 其中 $\\mathcal{X}$ 是一个约束集合。

投影梯度方法

$x_{k+1}=\\pi_{\\mathcal{X}}(x_k - \\alpha_k \ abla f(x_k)) \\\\$

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

罚方法

$\\min_x f(x)+ \\lambda P(x) \\\\$

通过罚参数将约束集放到目标函数上，其中 $P$ 要满足一些条件：连续非负，以及 $P(x)=0$ 当且仅当 $x\\in \\mathcal{X}$ 。该方法依赖于罚参数。

条件梯度

$\\begin{split}s^{k}&=\\arg\\min_{x\\in\\mathcal{X}}<\ abla f(x^k),x> \\\\ x^{k+1}&=x^k + \\eta_k (s^k - x^k) \\\\ \\end{split}\\\\$

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

ADMM

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

$\\min_x f(x) + g(z) \\\\ \\mbox{s.t.}Ax +Bz=b \\\\$

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

$\\mathcal{L}_{\\alpha}(x,z;y)=f(x) +g(z)+ (y)^T(Ax+Bz-b) + \\frac{\\alpha}{2}\\|Ax+Bz-b\\|^2 \\\\$

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

$\\left\\{ \\begin{split}x^{k+1}&=\\arg\\min_x\\mathcal{L}_{\\alpha_k}(x,z^k;y^k) \\\\ z^{k+1}&=\\arg\\min_z \\mathcal{L}_{\\alpha_k}(x^{k+1},z;y^{k})\\\\ y^{k+1}&=y^{k}+ \\alpha_k (Ax^{k+1}+Bz^{k+1}-b) \\end{split}\\right.\\\\$