设系统参数为
ω
\omega
ω。对于样本
i
i
i，其代价函数为
Q
i
(
ω
)
Q_i(\omega)
Qi(ω)。在n个样本组成的训练集上，其整体代价函数为：
Q
(
ω
)
=
∑
i
=
1
n
Q
i
(
ω
)
Q(\omega)=\sum_{i=1}^nQ_i(\omega)
Q(ω)=i=1∑nQi(ω)
要求
ω
\omega
ω使得上式最小，由于没有闭式解，需要通过近似迭代逐步逼近。
基础一阶优化
GD
GD(Gradient Descent)以
η
\eta
η为学习率，在每次迭代中用一阶泰勒展开近似：
ω
t
+
1
=
ω
t
−
η
∇
Q
(
ω
)
\omega_{t+1}=\omega_t - \eta\nabla Q(\omega)
ωt+1=ωt−η∇Q(ω)
将求和与梯度互换。GD方法的增量来源于对所有样本同时求梯度之和：
ω
t
+
1
=
ω
t
−
η
∑
i
=
1
n
∇
Q
i
(
ω
)
\omega_{t+1}=\omega_t - \eta\sum_{i=1}^n\nabla Q_i(\omega)
ωt+1=ωt−ηi=1∑n∇Qi(ω)
这些方法都以GD为基础，但收敛速度更快，换句话说
ϵ
t
\epsilon_t
ϵt更小。 关于收敛速度的意义，请参看这篇博客。
ASGD
ASGD(Average Stochastic Gradient Descent)选择一个迭代的时间点(代数)
t
0
t_0
t0，在这个时间点之前，和SGD一样：
ω
ˉ
t
=
ω
t
\bar{\omega}_t = \omega_t
ωˉt=ωt
在这个时间点之后，使用
t
0
t_0
t0到当前时刻
t
t
t的平均值：
ω
ˉ
t
=
1
t
−
t
0
+
1
∑
τ
=
t
0
t
ω
τ
\bar{\omega}_t = \frac{1}{t-t_0+1}\sum_{\tau=t_0}^t\omega_\tau
ωˉt=t−t0+11τ=t0∑tωτ
AdaGrad
AdaGrad1(Adaptive Gradient)方法对参数的每一维进行归一化，使用的分母是之前步骤中该维度的平方和：
ω
t
+
1
d
=
ω
t
d
−
η
1
∑
τ
=
1
t
−
1
[
∇
Q
(
ω
t
)
d
]
2
∇
Q
(
ω
t
)
\omega_{t+1}^d=\omega_t^d-\eta\frac{1}{\sqrt{\sum_{\tau=1}^{t-1} \left[ \nabla Q(\omega_t)^d\right]^2}}\nabla Q(\omega_t)
ωt+1d=ωtd−η∑τ=1t−1[∇Q(ωt)d]21∇Q(ωt) 相当于为每一维参数设定了不同的学习率：压制常常变化的参数，突出稀缺的更新。能够更有效地利用少量有意义样本。
AdaDelta
AdaDelta2(Adaptive Delta)和AdaGrad一样为每一维参数设定不同学习率，但是不用再设定基础学习率
η
\eta
η。
首先维护一个期望D，描述之前迭代中的参数变化情况，同样是个D维向量：
D
t
=
γ
D
t
−
1
+
(
1
−
γ
)
Δ
ω
t
2
D_t=\gamma D_{t-1}+(1-\gamma)\Delta\omega^2_t
Dt=γDt−1+(1−γ)Δωt2
另一个期望G，描述之前迭代中的梯度的平方：
G
t
=
γ
G
t
−
1
+
(
1
−
γ
)
∇
Q
(
ω
)
t
2
G_t=\gamma G_{t-1} + (1-\gamma)\nabla Q(\omega)_t^2
Gt=γGt−1+(1−γ)∇Q(ω)t2
使用D和G的比值作为权重，分别归一化每一维参数：
ω
t
+
1
d
=
ω
t
d
−
D
t
d
G
t
+
1
d
∇
Q
(
ω
)
\omega_{t+1}^d=\omega_t^d-\frac{D_t^d}{G_{t+1}^d}\nabla Q(\omega)
ωt+1d=ωtd−Gt+1dDtd∇Q(ω)
减号后的归一化参数决定了：单位梯度变化对应多少参数变化。
Adam
Adam3(Adaptive Moment Estimation)的思路和AdaGrad相似，都使用梯度平方根归一化学习率。
注意：为书写简便，后续的矩阵相乘相除都逐元素进行，更新也对参数每一维单独进行。
维护一个一阶momentum，等价于梯度：
m
t
=
α
⋅
m
t
−
1
+
(
1
−
α
)
⋅
∇
Q
(
ω
)
m_t=\alpha\cdot m_{t-1} + (1-\alpha)\cdot \nabla Q(\omega)
mt=α⋅mt−1+(1−α)⋅∇Q(ω)
另一个二阶momentum，等价于梯度平方：
v
t
=
β
⋅
v
t
−
1
+
(
1
−
β
)
⋅
∇
Q
(
ω
)
2
v_t=\beta\cdot v_{t-1}+(1-\beta)\cdot \nabla Q(\omega)^2
vt=β⋅vt−1+(1−β)⋅∇Q(ω)2
由于
m
,
v
m,v
m,v都初始化为0，使用t次幂让其在头几次迭代中更大一些：
m
^
t
=
m
t
1
−
α
t
,
v
^
t
=
v
t
1
−
β
t
\hat m_t=\frac{m_t}{1-\alpha^t}, \hat v_t=\frac{v_t}{1-\beta^t}
m^t=1−αtmt,v^t=1−βtvt
使用梯度平方
v
v
v归一化学习率，更新幅度为梯度
m
m
m:
ω
t
+
1
=
ω
t
−
η
1
v
^
t
m
^
t
\omega_{t+1}=\omega_t-\eta\frac{1}{\sqrt{\hat v_t}}\hat m_t
ωt+1=ωt−ηv^t1m^t
Rprop
RProp4(Resilient Propagation)比较本次梯度
∇
Q
(
ω
)
t
+
1
d
\nabla Q(\omega)_{t+1}^d
∇Q(ω)t+1d和上次梯度
∇
Q
(
ω
)
t
d
\nabla Q(\omega)_t^d
∇Q(ω)td符号变化来为参数d的变化加权。
如果两次梯度符号相反，则抑制参数变化(
η
−
<
1
\eta^-<1
η−<1)：
ω
t
+
1
d
=
ω
t
d
−
η
−
⋅
∇
Q
(
ω
)
\omega_{t+1}^d=\omega_t^d-\eta^-\cdot \nabla Q(\omega)
ωt+1d=ωtd−η−⋅∇Q(ω)
如果两次符号相同，则增强参数变化(
η
+
>
1
\eta^+>1
η+>1)：
ω
t
+
1
d
=
ω
t
d
−
η
+
⋅
∇
Q
(
ω
)
\omega_{t+1}^d=\omega_t^d-\eta^+\cdot \nabla Q(\omega)
ωt+1d=ωtd−η+⋅∇Q(ω)
RMSprop
RMSprop5(Root Mean Square Propagation)类似于简化版的AdaDelta，但是是独立发展而来的。
维护期望G，描述之前迭代中的梯度的平方：
G
t
=
γ
G
t
−
1
+
(
1
−
γ
)
∇
Q
(
ω
)
t
2
G_t=\gamma G_{t-1} + (1-\gamma)\nabla Q(\omega)_t^2
Gt=γGt−1+(1−γ)∇Q(ω)t2
用G修正学习率：
ω
t
+
1
d
=
ω
t
d
−
η
G
t
+
1
d
∇
Q
(
ω
)
\omega_{t+1}^d=\omega_t^d-\frac{\eta}{G_{t+1}^d}\nabla Q(\omega)
ωt+1d=ωtd−Gt+1dη∇Q(ω)
Duchi, J., Hazan, E., & Singer, Y. (2011). Adaptive Subgradient Methods for Online Learning and Stochastic Optimization. Journal of Machine Learning Research, 12, 2121–2159. ↩︎
Zeiler, M. D. (2012). ADADELTA: An Adaptive Learning Rate Method. Retrieved from http://arxiv.org/abs/1212.5701 ↩︎
Kingma, D. P., & Ba, J. L. (2015). Adam: a Method for Stochastic Optimization. International Conference on Learning Representations, 1–13. ↩︎
Martin Riedmiller und Heinrich Braun: Rprop - A Fast Adaptive Learning Algorithm. Proceedings of the International Symposium on Computer and Information Science VII, 1992 ↩︎
