无约束最优化问题求解方法的学习笔记
神经网络中的学习过程可以形式化为最小化损失函数问题, 该损失函数一般是由训练误差和正则项组成
损失函数的一阶偏导为
损失函数二阶偏导可以使用海塞矩阵 Hessian Matrix H\mathbf{H}H 表示, 其中每个权重向量 iii 的元素 jjj 的二阶偏导数为
一阶求解方法有 SGD Adam RMSProp 等,利用梯度(超平面)的信息求解,计算高效,收敛稍慢,需要超参数。
二阶求解方法有牛顿法,拟牛顿法,BFGS,L-BFGS 等,用二阶梯度(超曲面)的信息求解,计算复杂,收敛快,不需要超参数。
用损失函数的二阶偏导数寻找更好的训练方向. 记、
在w0w_0w0 点使用泰勒级数展开式二次逼近损失函数LLL$
另一阶导数g=0 , 有
参数www 迭代公式为
如果海塞矩阵非正定, 损失函数并不能保证在每一次迭代中都是减少的. 可以通过加上学习速率解决这个问题
优点: 比一阶导数更少迭代
缺点: 计算复杂度比一阶导数更高, 约O(n3), 因为对海塞矩阵及其逆的精确求值在计算量复杂度是十分巨大的.
Quasi-Newton method
拟牛顿法不直接计算海塞矩阵然后求其矩阵的逆, 而是在每次迭代的时候, 利用一阶偏导矩阵 Jacobian Matrix 或其他方法, 以逼近 Hessian Matrix 的逆, 复杂度约O(n2).
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) 更新
是一种拟牛顿法
由中值定理我们知道
所以有
同时,Hessian矩阵是对称矩阵。在这两个条件的基础上,我们希望Hn\mathbf{H}_nHn 相对于\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}
BFGS 每次迭代的复杂度O(n2)O(n^2)O(n2)$, 而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
优点: 使用一阶导数计算, 复杂度小于二阶导数
缺点: 变量没有归一化, 锯齿下降现象, 因为非线性函数局部的梯度方向并不一定就是朝着最优点
Stochastic Gradient Descent
每次迭代, 选取部分样本进行计算
相对于梯度下降,loss 函数更加波动,能帮助函数跳入另一个局部最优解。
An overview of gradient descent optimization algorithms
为解决 SGD 在沟壑(有一维梯度值特别大)的 Z 字形游走问题,引入动量,减少 Z 字震荡
NAG ref
NAG 是一种能给予梯度项「预测」功能的方法。我们通过计算θ−γvt−1\theta - \gamma v_{t-1}θ−γvt−1 给我们一个对下个参数θ\thetaθ 的估计,加速收敛。
NAG 的更新规则是
NAG 比 Momentum 收敛得更快。
使用了自适应技术来更新学习率:对变化[小|大]的参数进行更[大|小]的更新。epsilon 是一个用于抑制学习率产生变动率的常量。ref
Dean [3] 发现它改进 SGD 的鲁棒性,将其应用在大规模神经网络训练。
其中 Gt∈Rd×dG_t \in \mathbb{R}^{d \times d}Gt∈Rd×d 是对角矩阵,元素i,ii,ii,i 是 θi\theta_iθi 从t0t^{0}t0 到 tit^{i}ti 的平方和
代码表示
cache += dx ** 2
x += - learning_rate * dx / (np.sqrt(cache) + 1e-7)
Adagrad 有个缺点:随着迭代次数的增多,学习率项ηGt,ii+ϵ\frac{\eta}{\sqrt{G_{t,ii} + \epsilon}}√Gt,ii+ϵη 会急剧递减,可能会掉入局部最优点。Adadelta 和 RMSprop 尝试解决这个问题。
是 Adagrad 的扩展,减少 Adagrad 快速下降的学习率。把 Adagrad 的梯度平方和GtG_tGt 限制在时间窗口内
由 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)
Adaptive Moment Estimation, 除了像 Adadelta RMSprop 存储之前迭代的快速下降的梯度平方信息vtv_tvt ,它还存储之前迭代的快速下降的梯度信息mtm_tmt ,类似 momentum
其中,[ mtm_tmt | vtv_tvt ] 是第 [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)
如何选择?
αt=βαt−1
α=α0∗e−kt
a=a0/(1+kt)
由 Hinton 等人在 [4] 提出。做法是在 forward pass / backward prop 随机地把部分神经元置 0。
dropout 能使网络
参考 [0]
在小规模网络,可以这样初始化 W,但可能导致 non-homogeneous distribution of activations across the layers of a network
W = 0.01 * np.random.randn(D, H)
Bengio 在 2009 提出的 [9] ,用 unsupervised 方法 pre-training 网络,如 stacked-auto encoder,达到初始化网络的目的。
Glorot 等人在 2010 发表了 [5] 探讨了随机初始化参数来训练 SGD 效果不好的原因,并提出 Xavier Initialization 的参数初始化方法
W = np.random.randn(fan_in, fan_out) / np.sqrt(fan_in)
可用于 tanh 网络,但不适用于 ReLU
[7] 改进的 Xavier Initialization 方法,可用于 ReLU
W = np.random.randn(fan_in, fan_out) / np.sqrt(fan_in / 2)
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)}
优点
[8] 将 pre-train 时间减少 3 个数量级。
[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