Parameter updates

Vanilla update

一般都选择一部分$(x_1,x_2,x_3,...,x_n)$作为参数进行小批量梯度下降
$$
x_t = x_{t-1} - \alpha \cdot g_t
$$
假定$x$是参数矢量，$dx$是梯度。更新形式为:

# Vanilla update
x += - learning_rate * dx

MBGD或者SGD可以速度很快的达到极值，但是也存在问题

比如遇到了local-minama或者saddle point，对于saddle point是更需要解决的问题，因为对于高维参数来说很少存在使所有维度都处于局部最小

Momentum update

MBGD with momentum

这里我更喜欢李宏毅老师的讲解，stanford的物理意义解释我不是很明白，通过引入momentum的概念，它模拟的是物体运动时的惯性，即更新的时候在一定程度上保留之前更新的方向，同时利用当前batch的梯度微调最终的更新方向。这样一来，可以在一定程度上增加稳定性，从而学习地更快，并且还有一定摆脱局部最优的能力，也就一定程度上解决了saddle point的问题
$$
v_t = \beta \cdot v_{t-1} + \alpha \cdot g_t \\
x_t = x_{t-1} - v_t
$$

# Momentum update
# mu always= [0.5, 0.9, 0.95, 0.99]
v = mu * v + learning_rate * dx # integrate velocity
x -= v # integrate position

其中，动量超参数$mu$满足$0≤mu<1$,当其为0时Momentum update等价于MBGD

Nesterov Momentum

加入动量后，在梯度下降中即使当前的梯度为0，由于动量的存在，更新梯度依然会存在并继续更新w。而Nesterov算法认为继续当前点w的梯度是不太有意义的，有意义的是，假设下一个点w（仅靠动量滚到下一个点的w）的梯度方向才是决定当前梯度的重要因素。
$$
g_t=\nabla f(w_t- \frac{\alpha \cdot m_{t-1}}{ \sqrt{V_{t-1}}}) \\
v_t = \beta \cdot v_{t-1} + \alpha \cdot g_t \\
x_t = x_{t-1} - v_t
$$

x_ahead = x + mu * v
# evaluate dx_ahead (the gradient at x_ahead instead of at x)
v = mu * v + learning_rate * dx_ahead
x -= v

借用cs231n的图片来形象表示一下两种动量算法的不同

AdaGrad

通过一个简单的双参数梯度优化来解释

可以看到，同一位置上，目标函数在竖直方向比在水平方向的斜率的绝对值更大。因此，给定学习率，梯度下降迭代自变量时会使自变量在竖直方向比在水平方向移动幅度更大。那么，我们需要一个较小的学习率从而避免自变量在竖直方向上越过目标函数最优解。然而，这会造成自变量在水平方向上朝最优解移动变慢。

由此引入了二阶动量，可以自适应地调整步长

$$
V_t = \sum_{\tau=1}^{t} g_\tau^2
$$

# Assume the gradient dx and parameter vector x
cache += dx**2
x += - learning_rate * dx / (np.sqrt(cache) + eps)

通过此在学习率上进行调整，相当于由于一次性移动dx太大而加的惩罚，增加对震荡的阻力，但是由于梯度平方累计, 导致后期学习率极小，由此引入了其他算法

AdaDelta/RMSProp

两种算法都改变二阶动量计算方法的策略：不累积全部历史梯度，而只关注过去一段时间窗口的下降梯度，这些梯度按元素平方做指数加权移动平均
$$
V_t = \beta_2 * V_{t-1} + (1-\beta_2) g_t^2
$$

# RMSProp
cache = decay_rate * cache + (1 - decay_rate) * dx**2
x += - learning_rate * dx / (np.sqrt(cache) + eps)

这就避免了二阶动量持续累积、导致训练过程提前结束的问题了。

AdaDelta算法跟RMSProp算法的不同之处在于是否有学习率这一概念

Adam

Adam算法在RMSProp算法基础上对小批量随机梯度也做了指数加权移动平均
$$
m_t = \beta_1 \cdot m_{t-1} + (1-\beta_1)\cdot g_t \\
V_t = \beta_2 \cdot V_{t-1} + (1-\beta_2) \cdot g_t^2 \\
w_{t+1} = w_t - {\alpha \over \sqrt{\hat V_t}+\epsilon}\hat m_t
$$

由于初始时的累计梯度很小,需要做偏差校正

$$
\hat m_t={m_t\over 1-\beta_1^t} \\
\hat V_t={V_t\over 1-\beta_2^t}
$$

# t is your iteration counter going from 1 to infinity
m = beta1*m + (1-beta1)*dx
mt = m / (1-beta1**t)
v = beta2*v + (1-beta2)*(dx**2)
vt = v / (1-beta2**t)
x += - learning_rate * mt / (np.sqrt(vt) + eps)

当然普遍来说，使用Adam可以很方便的解决大部分问题

Summary

对于牛顿法和拟牛顿法我没有赘述，我觉得使用矩阵进行求解的算法复杂度非常高$O(n^3)$，但是相关方法在cs231n都有介绍，有需要可以去了解