1 详解梯度下降算法
1.1梯度下降的相关概念复习
在详细了解梯度下降的算法之前，我们先复习相关的一些概念。
假如步子太大就会错过最佳点，步子太小又会计算的很慢
- 步长(Learning rate)：
- **步长决定了在梯度下降迭代的过程中，每一步沿梯度负方向前进的长度。**用前面下山的例子，步长就是在当前这一步所在位置沿着最陡峭最易下山的位置走的那一步的长度。
特征(feature)：
- 指的是样本中输入部分，比如2个单特征的样本
- (x{(0)},y{(0)}),(x{(1)},y{(1)})(x(0),y(0)),(x(1),y(1))
- 则第一个样本特征为x(0)，第一个样本输出为y(0)。
- 假设函数(hypothesis function)：
- *在监督学习中，为了拟合输入样本，而使用的假设函数，记为
。比如对于单个特征的m个样本
- (x{(i)},y{(i)})(i=1,2,…m)(x(i),y(i))(i=1,2,…m),可以采用拟合函数如下： h_\theta (x)=\theta _0+\theta _1x*hθ(x)=θ0+θ1x
- 损失函数(loss function)：
- 为了评估模型拟合的好坏，**通常用损失函数来度量拟合的程度。**损失函数极小化，意味着拟合程度最好，对应的模型参数即为最优参数。
在线性回归中，损失函数通常为样本输出和假设函数的差取平方。比如对于m个样本(x_i,y_i)(i=1,2,…m)(x**i,y**i)(i=1,2,…m) 采用线性回归，损失函数为：
其中xi表示第i个样本特征，yi表示第i个样本对应的输出，hθ(xi)为假设函数。
1.2 梯度下降法的推导流程
1) 先决条件： 确认优化模型的假设函数和损失函数。
比如对于线性回归，假设函数表示为 h_\theta (x_1,x_2,…,x_n)=\theta _0+\theta _1x_1x_1+…+\theta _nx_nh**θ(x1,x2,…,x**n)=θ0+θ1x1+…+θnx**n, 其中
为模型参数，x_i (i = 0,1,2… n)x**i(i=0,1,2…n)为每个样本的n个特征值。这个表示可以简化，我们增加一个特征x0=1 ，这样
同样是线性回归，对应于上面的假设函数，损失函数为：
2) 算法相关参数初始化,
主要是初始化
,算法终止距离ε以及步长α。在没有任何先验知识的时候，我喜欢将所有的θ 初始化为0， 将步长初始化为1。在调优的时候再 优化。
3) 算法过程：
3.1) 确定当前位置的损失函数的梯度，对于
,其梯度表达式如下：
3.2) 用步长乘以损失函数的梯度，得到当前位置下降的距离，即
对应于前面登山例子中的某一步。
3.3) 确定是否所有的
，梯度下降的距离都小于ε，如果小于ε则算法终止，当前所有的\theta _i(i=0,1,…n)θ**i(i=0,1,…n)即为最终结果。否则进入步骤4.
4)更新所有的θ ，对于
，其更新表达式如下。更新完毕后继续转入步骤1.
下面用线性回归的例子来具体描述梯度下降。假设我们的样本是:
损失函数如前面先决条件所述：
则在算法过程步骤1中对于
的偏导数计算如下：
由于样本中没有xi上式中令所有的xj0为1.
步骤4中
的更新表达式如下：
从这个例子可以看出当前点的梯度方向是由所有的样本决定的，加1/m是为了好理解。由于步长也为常数，他们的乘积也为常数，所以这里α*1/m可以用一个常数表示。
在下面一节中，咱们会详细讲到梯度下降法的变种，他们主要的区别就是对样本的采用方法不同。这里我们采用的是用所有样本。
2 梯度下降法大家族
首先，我们来看一下，常见的梯度下降算法有：
- 全梯度下降算法(Full gradient descent),
- 随机梯度下降算法(Stochastic gradient desce
- 小批量梯度下降算法(Mini-batch gradient descent),
- 随机平均梯度下降算法(Stochastic average gradient descent)
它们都是为了正确地调节权重向量，通过为每个权重计算一个梯度，从而更新权值，使目标函数尽可能最小化。其差别在于样本的使用方式不同。
2.1 全梯度下降算法(FG)
批量梯度下降法，是梯度下降法最常用的形式，具体做法也就是在更新参数时使用所有的样本来进行更新。
计算训练集所有样本误差，对其求和再取平均值作为目标函数。
权重向量沿其梯度相反的方向移动，从而使当前目标函数减少得最多。
其是在整个训练数据集上计算损失函数关于参数θ 的梯度：
由于我们有m个样本，这里求梯度的时候就用了所有m个样本的梯度数据。
注意：
- 因为在执行每次更新时，我们需要在整个数据集上计算所有的梯度，所以批梯度下降法的速度会很慢，同时，批梯度下降法无法处理超出内存容量限制的数据集。
- 批梯度下降法同样也不能在线更新模型，即在运行的过程中，不能增加新的样本。
2.2 随机梯度下降算法(SG)
由于FG每迭代更新一次权重都需要计算所有样本误差，而实际问题中经常有上亿的训练样本，故效率偏低，且容易陷入局部最优解，因此提出了随机梯度下降算法。
其每轮计算的目标函数不再是全体样本误差，而仅是单个样本误差，即每次只代入计算一个样本目标函数的梯度来更新权重，再取下一个样本重复此过程，直到损失函数值停止下降或损失函数值小于某个可以容忍的阈值。
此过程简单，高效，通常可以较好地避免更新迭代收敛到局部最优解。其迭代形式为
但是由于，SG每次只使用一个样本迭代，若遇上噪声则容易陷入局部最优解。
2.3 小批量梯度下降算法
小批量梯度下降(mini-batch)算法是FG和SG的折中方案,在一定程度上兼顾了以上两种方法的优点。
每次从训练样本集上随机抽取一个小样本集，在抽出来的小样本集上采用FG迭代更新权重。
被抽出的小样本集所含样本点的个数称为batch_size，通常设置为2的幂次方，更有利于GPU加速处理。
特别的，若batch_size=1，则变成了SG；若batch_size=n，则变成了FG.其迭代形式为
上式中，也就是我们从m个样本中，选择x个样本进行迭代(1<x<m),
2.4 随机平均梯度下降算法(SAG)
在SG方法中，虽然避开了运算成本大的问题，但对于大数据训练而言，SG效果常不尽如人意，因为每一轮梯度更新都完与上一轮的数据和梯度无关。
随机平均梯度算法克服了这个问题，在内存中为每一个样本都维护一个旧的梯度，随机选择第i个样本来更新此样本的梯度，其他样本的梯度保持不变，然后求得所有梯度的平均值，进而更新了参数。
如此，每一轮更新仅需计算一个样本的梯度，计算成本等同于SG，但收敛速度快得多。
其迭代形式为：
- 我们知道sgd是当前权重减去步长乘以梯度，得到新的权重。sag中的a，就是平均的意思，具体说，就是在第k步迭代的时候，我考虑的这一步和前面n-1个梯度的平均值，当前权重减去步长乘以最近n个梯度的平均值。
- n是自己设置的，当n=1的时候，就是普通的sgd。
- 这个想法非常的简单，在随机中又增加了确定性，类似于mini-batch sgd的作用，但不同的是，sag又没有去计算更多的样本，只是利用了之前计算出来的梯度，所以每次迭代的计算成本远小于mini-batch sgd，和sgd相当。效果而言，sag相对于sgd，收敛速度快了很多。这一点下面的论文中有具体的描述和证明。
3 小结
- 全梯度下降算法(FG)【知道】
- 在进行计算的时候,计算所有样本的误差平均值,作为我的目标函数
- 随机梯度下降算法(SG)【知道】
- 每次只选择一个样本进行考核
- 小批量梯度下降算法(mini-batch)【知道】
- 选择一部分样本进行考核
- 随机平均梯度下降算法(SAG)【知道】
- 会给每个样本都维持一个平均值,后期计算的时候,参考这个平均值
