机器学习中的优化方法【1】——做个笔记

前几天听了林周臣老师的报告，关于机器学习中的优化方法[1]，并做了笔记。推荐机器学习的人去听。林老师主页：

机器学习离不开优化方法。Pedro 总结了机器学习与优化方法的关系：

“=++”

最后三项对应三个步骤：构建模型、求解模型和验证模型。

1.机器学习中的优化问题

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

1.分类和回归问题

\min_{x\in \{R}^n}\frac{1}{n}\sum_{i=1}^nf_i(x)+\ R(x) \\ \tag{1}

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

2.

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

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

3. 生成对抗网络

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

4.

自动超参数选择，这是一个两层优化问题。

\begin{split} \min_{\}& l_{}(w,\) \\ st & \ \in \{C}_1 \\ & w\in \arg\min_{w\in \{C}_2 } l_{train}(w,\) \end{split} \\

二、算法的顺序

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

在机器学习中，一阶是最广泛使用的。当然也有零阶和二阶之分，适合那些特殊结构的问题。

3.机器学习中的优化算法

一、基础模块：

通常的优化算法主要有以下几个模块。以不同的方式组合这些模块会导致不同的优化方法。

以上四个模块形成了许多现有的不同拼接下的优化算法。

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

考虑无约束问题：

\min_x f(x) \\

假设函数 f 是平滑的（如果不是，我们可以使用次梯度、平滑等）

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

当目标函数是二次的时，选择的方向 d_k 是共轭方向。

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

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

上面提到的逆牛顿需要存储一个大矩阵H_k，考虑到它是秩1或秩2的近似直线搜索方法,无约束优化方法,约束优化方法，所以我们可以存储一些向量来代替。

考虑可分离问题：

\min_x f(x) + g(x) \\ \tag{2} 其中 f 是平滑的，g 是非平滑的。相邻梯度算法对平滑部分进行二次逼近，每一步解决如下问题：

+\frac{1}{2\alpha^k}\|xx^k\|^2 + g(x) \\ &= \mbox{prox}_{\alpha^kg}(x^k - \alpha ^k \nabla f(x^k)) \end{split} \\">\begin{split} x^{k+1} &= \arg\min_x f(x^k)+ +\frac{1 }{2\alpha^k}\|xx^k\|^2 + g(x) \\ &= \mbox{prox}_{\alpha^kg}(x^k - \alpha^k \nabla f (x^k)) \end{拆分} \\

该算法需要假设 g 易于计算。

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

考虑一般问题：

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

x_{k+1} = \pi_{\{X}}(x_k - \ \nabla f(x_k)) \\

首先采取渐变步骤，然后再投影。

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

约束集通过惩罚参数放置在目标函数上，其中 P 必须满足一些条件：连续非负，并且 P(x)=0 iff x\in \{X} 。此方法依赖于惩罚参数。

\\ x^{k+1} &= x^k + \eta_k (s^k - x^k) \\ \end{split} \\">\begin{split} s^{k} &= \ arg\min_{x\in\{X}} \\ x^{k+1} &= x^k + \eta_k (s^k - x^k) \\ \end{split} \\

其中 \{X} 必须是紧集（相当于欧几里得空间中的有界闭集）。方向 s^k 的解等价于函数 f 的泰勒展开。该算法适用于稀疏的低秩问题。此时直线搜索方法,无约束优化方法,约束优化方法，\{X} 可能是一个低秩范数球。这时候有一个非常高效的算法来求解s^k。

当约束为线性且可分时，可以使用 ADMM，考虑以下问题：

\min_x f(x) + g(z) \\ \mbox{st} Ax + Bz = b \\

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

\{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\{L}_{\}(x,z^k;y^k) \\ z^{k+1} &= \arg\min_z \{L}_{\}(x^{k+1},z;y^{k})\\ y^{k+1} &= y^{k} + \ ( Ax^{k+1}+Bz^{k+1}-b) \end{split}\right.\\

如果仍然难以求出 x,z，我们可以将后面的二次项线性化，得到线性化的 ADMM。

如果问题中的变量可以分为多个部分，例如：

\min_{x\in \{X}} f(x_1,x_2,\cdots,x_n) \\

在这种情况下，可以采用块坐标下降法：本质上是交替最小值的扩展。

x_i^{k+1} = \arg\min_{x_i\in \{X}_i}f(x_{1}^{k+1},\cdots,x_{i-1}^{k+1} ,x,x_{i+1}^k,\cdots,x_n^k)\\

4. 大数据处理

考虑以下形式的问题：

\min_x \left\{f(x):=\sum_{i=1}^n f_i(x) \right\}\\

只要满足 \{E}(v_k) = \nabla f(x)，就可以在 v_k 方向找到一个近似梯度。有很多变种，adam,,,ada...

四、加速算法

通常的加速策略是使用插值和外推。

1.好的

x_{k+1} = x_k - \eta \nabla f(x_k) + \beta (x_k - x_{k-1}) \\ 调用后一项。

\begin{split} y_k = & x_k + \(x_k - x_{k-1}) \\ x_{k+1} = &y_k - \eta \nabla f(y_k) \end{split}\\

加速度应用于非光滑可分问题（2）：

\begin{split} y_k = & x_k + \(x_k - x_{k-1}) \\ x_{k+1} = & \mbox{prox}_{\eta g}(y_k - \eta \nabla f (y_k)) \end{拆分}\\

2.随机

认为邻接：

\min_x \left\{f(x):=\frac{1}{n}\sum_{i=1}^n f_i(x) \right\}\\

我们可以使用梯度法： x^{k+1} = x^k - \alpha \nabla f(x^k) ，如果n太大，每一步的计算量太大，

然后我们使用最原始的随机梯度法： x^{k+1} = x^k - \alpha \nabla f_{i_k}(x^k) ，即一次选择一个去。

这两种方法似乎都是极端的，因此介于两者之间。考虑如何在减少计算量的同时保持计算量增长过快。这里有几种从这个角度入手的方法。

这种方法的思想是每隔一段时间计算一次完整的梯度，并利用这个信息来修正每一步的随机梯度方向。

该方法是加速度和 .

请注意，在第 3 步中，您可以使用任何可计算的方法来解决第 3 步中的问题

这比 SVRG 的方差小。

五、展望

大规模优化的前景主要包括这几点

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

我的专栏

参考

【1】/video/?t=3131