无约束最优化问题求解

无约束最优化问题求解方法的学习笔记

神经网络中的学习过程可以形式化为最小化损失函数问题, 该损失函数一般是由训练误差和正则项组成

损失函数的一阶偏导为

损失函数二阶偏导可以使用海塞矩阵 Hessian Matrix H\mathbf{H}H 表示, 其中每个权重向量 iii 的元素 jjj 的二阶偏导数为

一阶求解方法有 SGD Adam RMSProp 等，利用梯度（超平面）的信息求解，计算高效，收敛稍慢，需要超参数。

二阶求解方法有牛顿法，拟牛顿法，BFGS，L-BFGS 等，用二阶梯度（超曲面）的信息求解，计算复杂，收敛快，不需要超参数。

牛顿法

用损失函数的二阶偏导数寻找更好的训练方向. 记、

在w0w_0w​0​​ 点使用泰勒级数展开式二次逼近损失函数LLL$

另一阶导数g=0 , 有

参数www 迭代公式为

如果海塞矩阵非正定, 损失函数并不能保证在每一次迭代中都是减少的. 可以通过加上学习速率解决这个问题

优点: 比一阶导数更少迭代

缺点: 计算复杂度比一阶导数更高, 约O(n3), 因为对海塞矩阵及其逆的精确求值在计算量复杂度是十分巨大的.

拟牛顿法

Quasi-Newton method

拟牛顿法不直接计算海塞矩阵然后求其矩阵的逆, 而是在每次迭代的时候, 利用一阶偏导矩阵 Jacobian Matrix 或其他方法, 以逼近 Hessian Matrix 的逆, 复杂度约O(n2).

1. 输入:

1. 对于n=0,1,...n = 0,1,...n=0,1,... 更新参数, 直到收敛:

a) 计算搜索方向和步长

\begin{aligned} \\ d &= \mathbf{H}^{-1} g_n\\ \alpha &\leftarrow \underset{\alpha \geq 0}{\min} L(w_n - \alpha d) \\ w_{n+1} &\leftarrow w_n - \alpha d \\ \end{aligned}

b) 计算并保存

c) 更新

BFGS

理解L-BFGS算法

是一种拟牛顿法

由中值定理我们知道

所以有

同时，Hessian矩阵是对称矩阵。在这两个条件的基础上，我们希望Hn\mathbf{H}_nH​n​​ 相对于\mathbf{H}_{n−1} 的变化并不大, 即

\begin{aligned}\\ \underset{\mathbf{H}^{-1}}{\min}\ &||\mathbf{H}^{-1}_n - \mathbf{H}^{-1}_{n-1}||\\ \text{s.t.} & \mathbf{H}^{-1}y_n=s_n\\ & \mathbf{H}^{-1} \text{is symmetric}\\ \end{aligned}

其中范式为 Weighted Frobenius Nrom, 这个式子的解, 即 BFGS 的QuasiUpdate\mathbf{QuasiUpdate}QuasiUpdate 定义为

其中

下面是完整算法

\begin{aligned} \\ & \mathbf{BFGSMultiply}(\mathbf{H}^{-1}_0, \{s_k\}, \{y_k\}, d): \\ & \hspace{1em} r \leftarrow d \\ & \hspace{1em} \mbox{// Compute right product} \\ & \hspace{1em} \mbox{for i=n,...,1}: \\ & \hspace{1em} \hspace{1em} \alpha_i \leftarrow \rho_{i} s^T_i r \\ & \hspace{1em} \hspace{1em} r \leftarrow r - \alpha_i y_i \\ & \hspace{1em} \mbox{// Compute center} \\ & \hspace{1em} r \leftarrow \mathbf{H}^{-1}_0 r \\ & \hspace{1em} \mbox{// Compute left product} \\ & \hspace{1em} \mbox{for i=1,\ldots,n}: \\ & \hspace{1em} \hspace{1em} \beta \leftarrow \rho_{i} y^T_i r \\ & \hspace{1em} \hspace{1em} r \leftarrow r + (\alpha_{n-i+1}-\beta)s_i \\ & \hspace{1em} \mbox{return r} \\ \end{aligned}

L-BFGS

BFGS 每次迭代的复杂度O(n2)O(n^2)O(n​2​​)$, 而L-BFGS, limited-mem BFGS, 是 O(nm),m=5 40O(nm), m=5 ~ 40O(nm),m=5 40

在 full batch 非常有效，但是在 mini batch 收敛较慢。

共轭梯度法

Conjugate gradient, 可认为是梯度下降法和牛顿法的中间物, 希望能加速梯度下降的收敛速度, 同时避免使用海塞矩阵进行求值、储存和求逆获得必要的优化信息. 每次迭代, 沿着共轭方向 (conjugate directions) 执行搜索的, 所以通常该算法要比沿着梯度下降方向优化收敛得更迅速. 共轭梯度法的训练方向是与海塞矩阵共轭的.

TODO

梯度下降

优点: 使用一阶导数计算, 复杂度小于二阶导数

缺点: 变量没有归一化, 锯齿下降现象, 因为非线性函数局部的梯度方向并不一定就是朝着最优点

SGD

Stochastic Gradient Descent

每次迭代, 选取部分样本进行计算

相对于梯度下降，loss 函数更加波动，能帮助函数跳入另一个局部最优解。

Momentum

An overview of gradient descent optimization algorithms

为解决 SGD 在沟壑（有一维梯度值特别大）的 Z 字形游走问题，引入动量，减少 Z 字震荡

Nesterov Momentum

NAG ref

NAG 是一种能给予梯度项「预测」功能的方法。我们通过计算θ−γvt−1\theta - \gamma v_{t-1}θ−γv​t−1​​ 给我们一个对下个参数θ\thetaθ 的估计，加速收敛。

NAG 的更新规则是

NAG 比 Momentum 收敛得更快。

AdaGrad

使用了自适应技术来更新学习率：对变化[小|大]的参数进行更[大|小]的更新。epsilon 是一个用于抑制学习率产生变动率的常量。ref

Dean [3] 发现它改进 SGD 的鲁棒性，将其应用在大规模神经网络训练。

其中 Gt∈Rd×dG_t \in \mathbb{R}^{d \times d}G​t​​∈R​d×d​​ 是对角矩阵，元素i,ii,ii,i 是 θi\theta_iθ​i​​ 从t0t^{0}t​0​​ 到 tit^{i}t​i​​ 的平方和

代码表示

cache += dx ** 2
x += - learning_rate * dx / (np.sqrt(cache) + 1e-7)

Adagrad 有个缺点：随着迭代次数的增多，学习率项ηGt,ii+ϵ\frac{\eta}{\sqrt{G_{t,ii} + \epsilon}}​√​G​t,ii​​+ϵ​​​​​η​​ 会急剧递减，可能会掉入局部最优点。Adadelta 和 RMSprop 尝试解决这个问题。

Adadelta

是 Adagrad 的扩展，减少 Adagrad 快速下降的学习率。把 Adagrad 的梯度平方和GtG_tG​t​​ 限制在时间窗口内

RMSprop

由 Hinton 在 coursera 提出 [2]。类似 Adadelta，解决 Adagrad 快速降低的学习率

Hinton 建议 γ=0.9,η=0.001

代码

cache = decay_rate * cache + (1 - decay_rate) * dx**2
x += - learning_rate * dx / (np.sqrt(cache) + 1e-7)

Adam

Adaptive Moment Estimation, 除了像 Adadelta RMSprop 存储之前迭代的快速下降的梯度平方信息vtv_tv​t​​ ，它还存储之前迭代的快速下降的梯度信息mtm_tm​t​​ ，类似 momentum

其中，[ mtm_tm​t​​ | vtv_tv​t​​ ] 是第 [1|2] 个时刻的梯度估计 [the mean | uncenter variance]，也是 Adam 名字的由来

m = beta1 * m + (1 - beta1) * dx
v = beta2 * v + (1 - beta2) * dx**2
a
# bias correlation, only relavant in first few iter when m,v close to 0
m /= 1 - beta1**t
v /= 1 - beta2**t

x += - learning_rate * m / (np.sqrt(v) + 1e-7)

SGD 技巧

• shuffling training data
• curriculumn learning Bengio09 循序渐进学习
• batch normalization
• early stopping
• gradient noise Neelakantan

总结

opt-update-rule

如何选择？

• 如果数据稀疏，或者训练深度神经网络，用 adative learning-rate methods，不需要手动调整学习率，超参数默认值 (0.9) 很容易达到较好的效果
• Adam 可能是较好的选择，Kingma 指出 Adam 的 bias-correction 的特性帮助 Adam 稍微优于 RMSProp Adadelta
• 有趣的是，很多最新的论文，都直接使用了（不带动量项的）Vanilla SGD 法，配合一个简单的学习率（退火）列表。这些 SGD 最终都能帮助他们找到一个最小值，但会花费远多于上述方法的时间。

Learning Rate Decay

step decay

αt=βαt−1

exp decay

α=α0∗e−kt

1/t decay

a=a0/(1+kt)

Dropout

由 Hinton 等人在 [4] 提出。做法是在 forward pass / backward prop 随机地把部分神经元置 0。

dropout 能使网络

• redundant representation
• ensemble of models
• 提升成绩

Weight Init

参考 [0]

在小规模网络，可以这样初始化 W，但可能导致 non-homogeneous distribution of activations across the layers of a network

W = 0.01 * np.random.randn(D, H)

Pre-train

Bengio 在 2009 提出的 [9] ，用 unsupervised 方法 pre-training 网络，如 stacked-auto encoder，达到初始化网络的目的。

Xavier Initialization

Glorot 等人在 2010 发表了 [5] 探讨了随机初始化参数来训练 SGD 效果不好的原因，并提出 Xavier Initialization 的参数初始化方法

W = np.random.randn(fan_in, fan_out) / np.sqrt(fan_in)

可用于 tanh 网络，但不适用于 ReLU

He et al., 2015

[7] 改进的 Xavier Initialization 方法，可用于 ReLU

W = np.random.randn(fan_in, fan_out) / np.sqrt(fan_in / 2)

Batch Normalization

Ioffe et al. 2015 [6] 等人提出，对每个 mini batch，归一化每个样本，作为网络的输入

\hat x^{(k)} = \frac{x^{(k)} - E[x^{(k)}]}{\sqrt{Var[x^{(k)}]}} \\ y^{(k)} = \gamma^{(k)} \hat x^{(k)} + \beta^{(k)}

优点

• 改善梯度流
• 允许更高的学习率
• 降低对 weight init 的依赖
• 有 regulization 的作用，可以减少 dropout

Data-dependent Initialization

[8] 将 pre-train 时间减少 3 个数量级。

Reference

[0] CS231n Winter 2016: Lecture 5: Neural Networks Part 2 VIDEO PDF

[1] CS231n Winter 2016 Lecture 6 Neural Networks Part 3 VIDEO PDF

[2] T. Tieleman and G. E. Hinton. Lecture 6.5-rmsprop: Divide the gradient by a running average of its recent magnitude. Coursera. 2012. PDF

[3] Dean, Jeffrey, et al. “Large scale distributed deep networks.” Advances in neural information processing systems. 2012. PDF

[4] Srivastava N, Hinton G E, Krizhevsky A, et al. Dropout: a simple way to prevent neural networks from overfitting[J]. Journal of machine learning research, 2014, 15(1): 1929-1958. PDF

[5] Glorot X, Bengio Y. Understanding the difficulty of training deep feedforward neural networks[C]//Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics. 2010: 249-256. PDF

[6] Ioffe S, Szegedy C. Batch normalization: Accelerating deep network training by reducing internal covariate shift[C]//International Conference on Machine Learning. 2015: 448-456. PDF

[7] He K, Zhang X, Ren S, et al. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification[C]//Proceedings of the IEEE international conference on computer vision. 2015: 1026-1034. PDF

[8] Krähenbühl P, Doersch C, Donahue J, et al. Data-dependent initializations of convolutional neural networks[J]. arXiv preprint arXiv:1511.06856, 2015. PDF

[9] Erhan D, Manzagol P A, Bengio Y, et al. The difficulty of training deep architectures and the effect of unsupervised pre-training[C]//Artificial Intelligence and Statistics. 2009: 153-160. PDF