梯度下降法,随机梯度下降法SGD,Mini-batch SGD
- 梯度下降法
- 凸函数(convex)和非凸函数
- 梯度更新方向选择
- 步长的选择
- 随机梯度下降SGD(Stochastic Gradient Descent)
- 梯度下降法：
- SGD:
- Mini-batch SGD
梯度下降法
- 从一个随机点开始
- 决定下降方向（重要）
- 确定步长（重要）
- 太小： 迭代太多次，消耗过多资源
- 太大： 容易越界，不稳定
- 不断更新，直到符合停止标准
- e.g. 变化足够小
∣ f ( w 0 ) − f ( w 6 ) ∣ < e = 1 0 − 3 |f(w0) - f(w6)| < e = 10^{-3} ∣f(w0)−f(w6)∣<e=10−3
- e.g. 变化足够小
凸函数(convex)和非凸函数
凸函数：最小二乘，岭回归，逻辑回归…
非凸函数：会在第一个最小的拐点停止，但是实际上还有更低点。
梯度更新方向选择
更新规则：
w i + 1 = w i − α i d f d w ( w i ) w_{i+1} = w_i - α_i\frac{df}{dw}(w_i) wi+1=wi−αidwdf(wi)
-dw : 斜率的负数，决定更新的方向
如果 -dw > 0 则往左走
如果 -dw < 0 则往右走
α ： 步长
公式推导：
Loss :
f ( x ) = ∣ ∣ w x − y ∣ ∣ 2 2 f(x) = ||wx - y||^2_2 f(x)=∣∣wx−y∣∣22
求导：
d f d w ( w ) = 2 ∣ ∣ w x − y ∣ ∣ 2 \frac{df}{dw}(w) = 2||wx-y||_2 dwdf(w)=2∣∣wx−y∣∣2
梯度更新：
w i + 1 = w i − α ∣ ∣ w x − y ∣ ∣ w_{i+1} = w_i - α||wx -y|| wi+1=wi−α∣∣wx−y∣∣
2 包含在α里
步长的选择
α i = α n i α_i = \frac{α}{n\sqrt{i}} αi=niα
α : 常量
n : 训练集数量
i : iteration 迭代次数
随着迭代次数增加，步长越来越小。
随机梯度下降SGD(Stochastic Gradient Descent)
梯度下降法：
w i + 1 = w i − α i ∑ j = 1 n ( w i T x ( j ) − y ( j ) ) x ( j ) w_{i+1} = w_i - α_i\sum^n_{j=1}(w^T_ix^{(j)} - y^{(j)})x^{(j)} wi+1=wi−αij=1∑n(wiTx(j)−y(j))x(j)
空间复杂度： O(nk)
SGD:
随机样本计算梯度，如果全部样本都计算梯度，计算量过大
w i + 1 = w i − α i ( w i T x ( j ) − y ( j ) ) x ( j ) w_{i+1} = w_i - α_i(w^T_ix^{(j)} - y^{(j)})x^{(j)} wi+1=wi−αi(wiTx(j)−y(j))x(j)
空间复杂度： O(k) 【取消了sum】
w i + 1 = w i + α i ▼ f j ( w i ) w_{i+1} = w_i + α_i▼f_j(w_i) wi+1=wi+αi▼fj(wi)
j 表示随机抽取的样本
- 优点：
- 每次更快，计算量更少
- 缺点：
- 需要迭代更多次
batch_SGD_57">Mini-batch SGD
w i + 1 = w i − α i ∑ j ∈ B n ( w i T x ( j ) − y ( j ) ) x ( j ) w_{i+1} = w_i - α_i\sum^n_{j∈B}(w^T_ix^{(j)} - y^{(j)})x^{(j)} wi+1=wi−αij∈B∑n(wiTx(j)−y(j))x(j)
只计算最小batch的梯度更新
- 优点
- 比SGD更大的计算量
- 比GD更小的计算量
- 缺点
- 多了一个参数 batch size
