优化理论 Optimization

3. 优化理论 Optimization

3.1 优化理论 Optimization

一个线性分类器的loss可以表示为 \[ L(W) = \frac{1}{N}\sum_{i=1}^N L_i(x_i, y_i,W) + \lambda R(W) \] 优化理论（optimization）就是求使\(L\)最小时\(W\)的值，即求 \[ w^*=\arg \min_w L(w) \]

3.2 梯度下降法 Gradient Descent

通过迭代的方式，沿函数梯度的负方向下降以寻找函数最小值的方法为梯度下降法（gradient descent）： \[ x_{t+1} = x_t - \alpha \nabla f(x_t) \] 代码思路如下：

1
2
3
4
5
# Vanilla gradient descent
w = initialize_weights()
for t in range(num_steps):
    dw = compute_gradient(loss_fn, data, w)
    w -= lenrning_rate * dw

其中hyperparameters有initailize_weights()、num_steps和learning_rate

在计算梯度时，通常使用\(\nabla_WL\)的解析式计算，并用数值计算的方式检验

3.3 随机梯度下降法 Stochastic Gradient Descent (SGD)

loss的梯度计算表达式为 \[ \nabla_WL(W) = \frac{1}{N}\sum_{i=1}^N \nabla _W L_i(x_i, y_i,W) + \lambda \nabla_WR(W) \] 当\(N\)的数值很大时，计算梯度的开销会很大

为了避免巨大的开销，我们可以从概率的角度考虑loss function

对于一个数据集： \[ \{(x_i, y_i)\}_{i=1}^N \] 式中\(x_i\)是图像，\(y_i\)是该图像对应的正确标签，我们将\(L\)视作关于\(x\)、\(y\)的joint probability distribution

那么loss就可以看做该分布的期望，即 \[ L(W) = \mathbb E(L) +\lambda R(W) \] \[ \nabla _W L(W) = \nabla_W\mathbb E(L) + \lambda \nabla_WR(W) \]

为了方便计算\(\mathbb E(L)\)，可以采用蒙特卡洛方法进行采样估计： \[ L(W) \approx \frac1n \sum_{i=1}^n L_i(x_i, y_i, W) + \lambda R(W) \] \[ \nabla_WL(W) \approx \frac1n \sum _{i=1}^n \nabla_WL_i(x_i, y_i, W) + \lambda \nabla _WR(W) \]

所以我们会从整个数据集中采样出minibatch来估计梯度，称为随机梯度下降法（stochastic gradient descent），minibatch的大小通常为32、64或128

代码思路如下：

1
2
3
4
5
6
# Stochastic gradient descent
w = initialize_weights()
for t in range(num_steps):
    minibatch = sample_data(data, batch_size)
    dw = compute_gradient(loss_fn, minibatch, w)
    w -= learning_rate * dw

其中hyperparameters有initialize_weights()，num_steps、learning_rate、batch_size和sample_data()

3.4 SGD + Momentum (SGDM)

当loss function有局部最小值（local minimum）或鞍点（saddle point）时，SGD方法会立即停止，我们引入”速度向量“来模拟一个小球沿斜坡下滚的过程： \[ v_{t+1} = \rho v_t + \nabla f(x_t) \] \[ x_{t+1} = x_t - \alpha v_{t+1} \]

速度向量的实质就是梯度的累计，函数将沿累计的梯度方向下降

代码思路如下：

1
2
3
4
5
6
# Stochastic gradient descent with momentum
v = 0
for t in range(num_steps):
    dw = compute_gradient(w)
    v = rho * v + dw
    w -= learning_rate * v

同时由于速度向量的引入，我们引入了一个新的hyperparameter rho模拟摩擦系数以保证小球最终会停止，通常rho的值为0.9或0.99

3.5 Nesterov Momentum

在累计梯度时，我们选择不累计当前的梯度，而是假设小球以当前的速度运动一小段距离后，累计运动后小球处的梯度，这种方法被称为Nesterov momentum： \[ v_{t+1} = \rho v_t - \alpha \nabla f(x_t + \rho v_t) \] \[ x_{t+1} = x_t + v_{t+1} \]

通常为了计算方便，我们令\(\tilde x = x_t + \rho v_t\)，于是有： \[ v_{t+1} = \rho v_t - \alpha \nabla f(\tilde x_t) \] \[ \tilde x_{t+1} = \tilde x_t + v_{t+1} +\rho ( v_{t+1} - v_t) \]

代码思路如下：

1
2
3
4
5
6
7
# Nesterov momentum
v = 0
for t in range(num_steps):
    dw = compute_gradient(w)
    old_v = v
    v = rho * v - learning_rate * dw
    w -= rho * old_v - (1 + rho) * v

3.6 AdaGrad

在梯度下降法中，由于learning rate是固定的，梯度大小不同的方向下降的速度是相同的

但是我们希望在梯度较大的方向减缓下降速度以防震荡，梯度较小的方向加快下降速度，于是我们用AdaGrad使learning rate自适应大小： \[ S_{t+1} = S_t + \nabla_W^2 \] \[ x_{t+1} = x_t - \alpha \frac{\nabla_W}{\sqrt{S_{t+1}+\varepsilon}} \]

式中平方和除法均指矩阵按元素操作，\(\varepsilon\)是一个极小的数字以增强数值稳定性，防止出现分母为0的情况

代码思路如下：

1
2
3
4
5
6
# AdaGrad
grad_squared = 0
for t in range(num_steps):
    dw = compute_gradient(w)
    grad_squared += dw * dw
    w -= learning_rate * dw / (grad_sqruared.sqrt() + 1e-7)

3.7 RMSProp

在AdaGrad中，若迭代的次数过多，可能会出现梯度平方累积过大的情况，导致learning rate过小而不能产生有效迭代

RMSProp效仿SGD+Momentum引入摩擦系数\(\rho\)保证小球最终停止的想法，引入“摩擦“以防止梯度平方的累积过大： \[ S_{t+1} = \rho S_t + (1-\rho)\nabla_W^2 \] \[ x_{t+1} = x_t - \alpha \frac{\nabla_W}{\sqrt{S_{t+1}+\varepsilon}} \]

式中平方和除法均指矩阵按元素操作，\(\varepsilon\)是一个极小的数字以增强数值稳定性，防止出现分母为0的情况

代码思路如下：

1
2
3
4
5
6
# RMSProp
grad_squared = 0
for t in range(num_steps):
    dw = compute_gradient(w)
    grad_squared = decay_rate * grad_squared + (1 - decay_rate) * dw * dw
    w -= learning_rate * dw / (grad_squared.sqrt() + 1e-7)

decay_rate为新的hyperparameter

3.8 Adam

将RMSProp和momentum的思想结合起来，我们就得到了Adam： \[ v_{t+1} = \rho_1 v_t + (1 - \rho_1)\nabla _W \] \[ S_{t+1} = \rho_2 S_t + (1-\rho_2)\nabla_W^2 \]

\[ x_{t+1} = x_t - \alpha \frac{v_{t+1}}{\sqrt{S_{t+1}+\varepsilon}} \]

式中平方和除法均指矩阵按元素操作，\(\varepsilon\)是一个极小的数字以增强数值稳定性，防止出现分母为0的情况

代码思路如下：

1
2
3
4
5
6
7
8
# Adam
moment1 = 0
moment2 = 0
for t in range(num_steps):
    dw = compute_gradient(w)
    moment1 = beta1 * moment1 + (1 - beta1) * dw
    moment2 = beta2 * moment2 + (1 - beta2) * dw * dw
    w -= learning_rate * moment1 / (moment2.sqrt() + 1e-7)

beta1和beta2为新的hyperparameters

但是在第一次迭代时，由于\(\rho_2\)通常趋近于1，\(S_1\)和\(S_2\)通常会趋近于0，导致第一次迭代的跨度会非常大，容易产生不好的结果，所以我们在Adam中会加入bias correction来修正： \[ v_{t+1} = \frac{\rho_1 v_t + (1 - \rho_1)\nabla _W}{\sqrt{1-\rho_1^{t+1}}} \] \[ S_{t+1} = \frac{\rho_2 S_t + (1-\rho_2)\nabla_W^2}{\sqrt{1-\rho_2^{t+1}}} \]

\[ x_{t+1} = x_t - \alpha \frac{v_{t+1}}{\sqrt{S_{t+1}+\varepsilon}} \]

修正后的代码思路如下：

1
2
3
4
5
6
7
8
9
10
# Adam with bias correction
moment1 = 0
moment2 = 0
for t in range(num_steps):
    dw = compute_gradient(w)
    moment1 = beta1 * moment1 + (1 - beta1) * dw
    moment2 = beta2 * moment2 + (1 - beta2) * dw * dw
    moment1_unbias = moment1 / (1 - beta1 ** t)
    moment2_unbias = moment2 / (1 - beta2 ** t)
    w -= learning_rate * moment1 / (moment2.sqrt() + 1e-7)

beta1通常取0.9，beta2通常取0.999，learning_rate通常取1e-3、5e-4、1e-4

3.9 二阶优化 Second-Order Optimization

以上我们提到的优化方式均为一阶优化，它们通过梯度来线性拟合函数并迭代以得到函数最小值

那么，我们可以考虑通过梯度和黑塞矩阵来二次拟合函数，不妨设二次拟合的迭代式为 \[ x_{t+1} = x_t+d \] 我们希望\(x_{t+1}\)尽可能小，即求 \[ d = \arg \min_d f(x_t+d) \] \(f(x)\)在\(x_t\)处的二阶泰勒展开式为 \[ f(x) = f(x_t) + (x - x_t)^{\mathsf{T}}\nabla f(x_t) + \frac12(x-x_t)^{\mathsf{T}}\mathbf{H}f(x_t)(x-x_t) \] 代入\(x_{t+1}\)的值得 \[ f(x_{t+1}) = f(x_t+d)=f(x_t)+d^{\mathsf{T}}\nabla f(x_t)+\frac12d^{\mathsf{T}}\mathbf{H}f(x_t)d \] 当\(d=-[\mathbf{H}f(x_t)]^{-1}\nabla f(x_t)\)时取最小值

则二阶优化的迭代式为： \[ x_{t+1} = x_t-\left[\mathbf{H}f(x_t)\right]^{-1}\nabla f(x_t) \] 然而由于黑塞矩阵元素数量过多且矩阵求逆复杂度过高，实践中很少使用二阶优化

优化理论 Optimization
http://hmnkapa.github.io/2024/07/20/优化理论/
作者
呼姆奴库
发布于
2024年7月20日
许可协议