梯度下降法与牛顿法

梯度下降和牛顿法的推导均与泰勒公式有关，所以先介绍泰勒展开公式：

基本形式：

上面这个迭代形式将应用到下面的梯度下降和牛顿法中。

梯度下降法应用一阶泰勒展开，假设 L (θ)代表损失函数，目标：最小化损失函数，θ是需要更新的模型参数。下面公式中alpha是步长(学习率)，可以直接赋值一个小的数，也可以通过line search。

牛顿法应用二阶泰勒展开，目标：最小化损失函数

g定义为雅克比矩阵，矩阵中各元素对应一阶偏导数

Hessian矩阵中各元素对应二阶偏导数。Hessian矩阵的逆同比于梯度下降法的学习率参数alpha，Hessian的逆在迭代中不断减小，起到逐渐缩小步长的效果。

1梯度下降法： 通过梯度方向和步长，直接求解目标函数最小值时的参数。

越接近最优值时，步长应该不断减小，否则会在最优值附近来回震荡。

2牛顿法：

优点：通过求解目标函数的一阶导数为0时的参数，进而求出目标函数最小值时的参数。收敛速度很快。海森矩阵的逆在迭代过程中不断减小，可以起到逐步减小步长的效果。

缺点：海森矩阵的逆计算复杂，代价比较大，因此有了拟牛顿法。

解决牛顿法计算比较复杂的问题，使用正定矩阵近似Hessian矩阵的逆，简化了运算的复杂度。

常用的拟牛顿算法：DFP算法和BFGS算法

梯度下降是通过迭代搜索一个函数极小值的优化算法。使用梯度下降，寻找一个函数的局部极小值的过程起始于一个随机点，并向该函数在当前点梯度（或近似梯度）的反方向移动。梯度下降算法是一种非常经典的求极小值的算法。

比如逻辑回归可以用梯度下降进行优化，因为这两个算法的损失函数都是严格意义上的凸函数，即存在全局唯一极小值，较小的学习率和足够的迭代次数，一定可以达到最小值附近，满足精度要求是完全没有问题的。并且随着特征数目的增多，梯度下降的效率将远高于去解析标准方程的逆矩阵。

常用的梯度下降法有3种不同的形式：

（1）批量梯度下降法，简称BGD，使用所有样本，比较耗时。

（2）随机梯度下降法，简称SGD，随机选择一个样本，简单高效。

（3）小批量梯度下降法，简称MBGD，使用少量的样本，这是一个折中的办法。

机梯度下降法优点：

1、更容易跳出局部最优解。

2、具有更快的运行速度。

clear all;

close all;

clc;

V=double(imread('lenajpg'));

imshow(mat2gray(V));

[i u]=size(V); %计算V的规格

r=100; %设置分解矩阵的秩

W=rand(i,r); %初始化WH，为非负数

H=rand(r,u);

maviter=100; %最大迭代次数

for iter=1:maviter

W=W((V/(WH))H'); %注意这里的三个公式和文中的是对应的

W=W/(ones(i,1)sum(W));

H=H(W'(V/(WH)));

end

img_V=WH;

figure;

imshow(mat2gray(img_V));

梯度下降法实现简单，当目标函数是凸函数时，梯度下降法的解是全局解。一般情况下，其解不保证是全局最优解，梯度下降法的速度也未必是最快的。梯度下降法的优化思想是用当前位置负梯度方向作为搜索方向，因为该方向为当前位置的最快下降方向，所以也被称为是”最速下降法”。最速下降法越接近目标值，步长越小，前进越慢。

最速下降法越接近目标值，步长越小，前进越慢。

[if !vml]

[endif]梯度下降法的搜索迭代示意图如图所示

梯度下降法在接近最优解的区域收敛速度明显变慢，利用梯度下降法求解需要很多次的迭代。实际上收敛速度并不快。 其主要原因是每次迭代后下一次的搜索方向总是和前一次相互垂直，产生锯齿现象，使得收敛速度较为缓慢。

最速下降法的一种简单形式是：

[if !vml]

[endif]

在机器学习中，基于基本的梯度下降法发展了两种梯度下降方法，分别为随机梯度下降法和批量梯度下降法。

1 ）批量梯度下降法（Batch Gradient Descent，BGD）,是梯度下降的batch版本

[if !vml]

[endif][if !vml]

[endif]

2 ）随机梯度下降（Stochastic Gradient Descent , SGD）。

对于训练数据集，我们首先将其分成n个batch，每个batch包含m个样本。我们每次更新都利用一个batch的数据，而非整个训练集。即：

[if !vml]

[endif]

随机梯度下降是通过每个样本来迭代更新一次，如果样本量很大的情况（例如几十万），那么可能只用其中几万条或者几千条的样本，就已经将theta迭代到最优解了，对比上面的批量梯度下降，迭代一次需要用到十几万训练样本，一次迭代不可能最优，如果迭代10次的话就需要遍历训练样本10次。但是，SGD伴随的一个问题是噪音较BGD要多，使得SGD并不是每次迭代都向着整体最优化方向。

优点：

当训练数据太多时，利用整个数据集更新往往时间上不显示。batch的方法可以减少机器的压力，并且可以更快地收敛。

当训练集有很多冗余时（类似的样本出现多次），batch方法收敛更快。以一个极端情况为例，若训练集前一半和后一半梯度相同。那么如果前一半作为一个batch，后一半作为另一个batch，那么在一次遍历训练集时，batch的方法向最优解前进两个step，而整体的方法只前进一个step。

随机梯度下降每次迭代只使用一个样本，迭代一次计算量为n2，当样本个数m很大的时候，随机梯度下降迭代一次的速度要远高于批量梯度下降方法。两者的关系可以这样理解：随机梯度下降方法以损失很小的一部分精确度和增加一定数量的迭代次数为代价，换取了总体的优化效率的提升。增加的迭代次数远远小于样本的数量。

对批量梯度下降法和随机梯度下降法的总结：

批量梯度下降 ---最小化所有训练样本的损失函数，使得最终求解的是全局的最优解，即求解的参数是使得风险函数最小，但是对于大规模样本问题效率低下。

随机梯度下降 ---最小化每条样本的损失函数，虽然不是每次迭代得到的损失函数都向着全局最优方向， 但是大的整体的方向是向全局最优解的，最终的结果往往是在全局最优解附近，适用于大规模训练样本情况。

梯度下降是迭代法的一种，可以用于求解最小二乘问题（线性和非线性都可以）。

在求解机器学习算法的模型参数，即无约束优化问题时，梯度下降（Gradient Descent）是最常采用的方法之一，另一种常用的方法是最小二乘法。在求解损失函数的最小值时，可以通过梯度下降法来一步步的迭代求解，得到最小化的损失函数和模型参数值。

反过来，如果需要求解损失函数的最大值，这时就需要用梯度上升法来迭代了。在机器学习中，基于基本的梯度下降法发展了两种梯度下降方法，分别为随机梯度下降法和批量梯度下降法。

缺点：

（1）靠近极小值时收敛速度减慢。

（2）直线搜索时可能会产生一些问题。

（3）可能会“之字形”地下降。

以上就是关于梯度下降法与牛顿法全部的内容，包括:梯度下降法与牛顿法、梯度下降法是什么、哪位朋友有matlab非负矩阵分解的随机梯度下降算法程序等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！