随机梯度下降 python为什么比梯度下降快

来源：蜘蛛抓取(WebSpider) 时间：2017-04-18 11:06 标签： 随机梯度下降算法
当前位置浏览文章
各位小伙伴们大家周末好,这几天在看《统计学习方法》这本书，发现梯度下降法在感知机等机器学习算法中有很重要的应用，所以就特别查了些资料。今天让我们来一起聊一聊在机器学习中使用非常广泛的优化算法,也是众多的机器学习算法中很常用的优化方法之一:梯度下降算法.在现在几乎众多的机器学习库或者深度学习库中都会包括梯度下降算法的不同变种的实现,但是,他们对于我们这些初学者来说并不友好,就像是一个优化的黑盒,很难以将他们的优缺点进行实际的解释.所以,在构思了一段时间以后,我想把我自己对于梯度下降的一些算法的不同变种一些理解介绍给大家,并且和大家一起进行交流.对于机器学习,很多方面我们都在想用什么方式去用数学方法进行描述,要想学好机器学习,首先就得去理解其中的一些数学意义,虽然说不一定能够轻松自如的推导其中的公式,不过最起码也得认识这些式子.不然很多的论文可就看不懂了,所以我想将来有时间可以写一个系列去描述机器学习的这个部分,尽量的覆盖但是不局限于算法之类.1:回归和梯度下降回归在数学上来说是给定一个点集，能够用一条曲线去拟合之，如果这个曲线是一条直线，那就被称为线性回归，如果曲线是一条二次曲线，就被称为二次回归，回归还有很多的变种，如locally weighted回归，logistic回归，等等.而梯度下降法（gradient descent）则是求解无约束最优化问题的一种常用方法，有实现简单的优点。梯度下降法是迭代算法，每一步需要求解目标函数的梯度向量。现在我想引用斯坦福的机器学习公开课的房屋价值预估的系统来去解释下回归的问题,一个房屋价值的来自于很多的地方,比如房子的大小,房子的面积,房子的地理位置,房子的朝向等等,这样的影响房屋价值的变量会被我们成为特征值,(关于特征值可以看看我以前的一篇文章).在这里为了模型的简单,我们就假设我们的房屋现在只受房子面积这一个变量的影响.现在我们假设得到一组房屋销售数据
现在我们根据x轴为房屋的面积,y轴是房屋的售价做出一个图:
这个时候我们输入了一个在以前的数据没有的面积,我们应该怎么办呢?这时候我么可能就会想,如果我们可以用一条曲线去尽量拟合这些数据,假设如果有新的数据输入进来,我们可以将这个曲线上的值对应的点返回.如过我们可以用一条曲线去拟合,就可以得到以下这个样子绿色的点就是我们想要预测的那个点.而逐渐拟合的这个过程我们就可以称为回归问题.
现在我们介绍下梯度下降方法,假设我们现在给定一个应用场景,场景如下:1:给定许多组数据(Xi,Yi),Xi为输入,Yi为输出,现在我们设定一个线性函数y=h(x)去拟合这些数据既然对于现行场景:既然是线性函数,我们不妨可以设h(x)= w0*x0 + w1*x1;刺水我们遇到的问题可能是如何去确定W0,W1这两个参数,既可以表现为w=(w0,w1)这两个向量.既然是拟合,这个拟合的效果可以用平方损失合数来表现为E(w)=∑[h(x)- y]^2 / 2来衡量。其中w是权重二维向量,x是输入二维向量,x和y都可以认为是训练集的数据,可以表现为已知.至于为什么在平方损失函数中除以2,只是为了在以后的求导过程中可以消除系数,这里可以省略.因此这个问题就可以变换为求E(x)最小值求无约束最优化的问题2:对于感知机场景感知机（perceptron）为二类分类的线性分类模型。输入为实例的特征向量，输出为实例的类别，取+1和-1二值。现在我们假设输入空间为x,输出空间为y={+1,-1},由输入空间到输出空间的函数可以如下:f(x)= sign(w · x + b)w∈Rn其中w叫做权值或者权值向量,b叫做偏振。w · x表示向量w和x的点积感知机sign(w · x + b)的损失函数为L(w,b)= -∑yi(w · xi+ b)x∈M,M为误分类点集合。因此该问题变成了求L(w,b)最小值的无约束最优化问题二:梯度下降方法梯度下降理解好其实可以是高数求导的方法,对E这个公式针对每个维数（w0，w1）求偏导后的向量▽E(w)=（?E/?w0,?E/?w1）.对于第一种应用场景,对E这个公式针对的每个维数(w0,w1),求偏导数后的向量可以为▽E(w)=（?E/?w0,?E/?w1）.梯度则可以理解为最陡峭的上升方向,对应的梯度下降的训练法则可以为:w=w-η▽E(w)这里的η代表学习速率，决定梯度下降搜索中的步长。上式的w是向量，即可用将该式写成分量形式为:wi=wi-η*?E/?wi.现在的公式计算可以转化为计算?E/?wi：推导的过程比较简单,&统计学习方法&这本书也写得比较详细,在这里我也只引入了结论,其实说白了就是对目标函数的求导.?E/?wi=∑（h(x)-y）*(xi)这里的∑是对样本空间，即训练集进行一次遍历，耗费时间较大，可以使用梯度下降的随机近似.对于感知机场景:感知机的学习算法是误分类驱动的,具体的可以采用随机梯度下降的方法:▽wL(w,b)=
-∑yixi▽bL(w,b)=
-∑yi随机选取一个误分类点（xi,yi),对w,b进行更新：w
w - η *(-yixi)b
b - η *(-yi)式中η(0 & η &= 1)是步长，在统计学习中又称为学习率（learning rate）在遇到随机近似的情况下,我们会想的,既然是随机近似，则顾名思义，肯定是用近似方法来改善梯度下降时候的时间复杂度问题。正如上所说，在?E/?wi=∑（h(x)-y）*(xi)的时候∑耗费了大量的时间，特别是在训练集庞大的时候。所以肯定有人会猜想，如果把求和去掉如何，即变为?E/?wi=（h(x)-y）*(xi)。幸运的是，猜想成立了。只是要注意一下标准的梯度下降和随机梯度下降的区别：1.标准下降时在权值更新前汇总所有样例得到的标准梯度，随机下降则是通过考察每次训练实例来更新。2.对于步长η的取值，标准梯度下降的η比随机梯度下降的大。因为标准梯度下降的是使用准确的梯度，理直气壮地走，随机梯度下降使用的是近似的梯度，就得小心翼翼地走，怕一不小心误入歧途南辕北辙了。3.当E（w）有多个局部极小值时，随机梯度反而更可能避免进入局部极小值中。好了,写完了有感觉到自己其实对于梯度下降的算法的理解还是远远不够的,仍然需要努力,也希望大家可以和我一起交流,共同进步!batch&gradient&descent（批量梯度下降）&和&stochastic&gradient&descent（随机梯度下降）
批量梯度下降是一种对参数的update进行累积，然后批量更新的一种方式。用于在已知整个训练集时的一种训练方式，但对于大规模数据并不合适。
随机梯度下降是一种对参数随着样本训练，一个一个的及时update的方式。常用于大规模训练集，当往往容易收敛到局部最优解。
详细参见：Andrew Ng 的Machine Learning的课件（见参考1）
可能存在的改进
1）样本可靠度，特征完备性的验证
例如可能存在一些outlier，这种outlier可能是测量误差，也有可能是未考虑样本特征，例如有一件衣服色彩评分1分，料子1分，确可以卖到10000万元，原来是上面有一个姚明的签名，这个特征没有考虑，所以出现了训练的误差，识别样本中outlier产生的原因。
2）批量梯度下降方法的改进
并行执行批量梯度下降
3）随机梯度下降方法的改进
找到一个合适的训练路径（学习顺序），去最大可能的找到全局最优解
4）假设合理性的检验
&H（X)是否合理的检验
5）维度放大
维度放大和过拟合问题，维度过大对训练集拟合会改善，对测试集的适用性会变差，如果找到合理的方法？
下面是我做的一个实验
假定有这样一个对衣服估价的训练样本，代码中matrix表示，第一列表示色彩的评分，第二列表示对料子质地的评分，例如第一个样本1,4表示这件衣服色彩打1分，料子打4分。我们需要训练的是theta，其表示在衣服的估价中，色彩和料子的权重，这个权重是未知量，是需要训练的，训练的依据是这四个样本的真实价格已知，分别为19元，...20元。
通过批量梯度下降和随机梯度下降的方法均可得到theta_C={3,4}T
批量梯度下降法：
随机梯度下降法
【2】/rocketfan/archive//1966325.html
【3】//batch-gradient-descent/
【4】http://ygc.name//machine-learning-ex2-linear-regression/
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。

我要回帖

更多关于 随机梯度下降算法 的文章

 

随机推荐