首页 > 代码库 > 梯度下降算法

梯度下降算法

先是几个英文:

linear regression线性回归    gradient descent梯度下降   normal equations正规方程组

notation符号:

m denote(指示) the number of training examples

x denote the input variables(also called features)

y denote the output variables(also called target variables)

(x,y) training example

第i行training example (x^(i),y^(i))

n denote features的数量

比如根据房子大小判断房子价钱这个例子,有m个例子就是说有m个(x,y)数据,如果x不止一个,就是说我们还要根据房子的位置啊,房间个数等特征来判断房子价钱,那么这个n就是这些特征的数量。x1是size,x2是beddrooms,那么n=2

 

开始算法:

现在有一个学习函数h,要使得h(x)能符合结果Y,h(x)可以用下面这样的式子来表示:

技术分享

θ在这儿称为参数,在这儿的意思是调整feature中每个分量的影响力,就是到底是房屋的面积更重要还是房屋的地段更重要。首先对θ赋值,这个值可以是随机的,也可以让θ是一个全零的向量。

又另技术分享(这个1/2就记一下吧,前面乘上的1/2是为了在求导的时候,这个系数就不见了。)

好的现在我们要让J(Θ)最小对吧。

gradient descent:就是想象你在下山,你要最最陡下降最快的那条路到达山底(J(Θ)最小值),所以这里要求个偏导。

技术分享

当单个特征值时,上式中j表示系数(权重)的编号,右边的值赋值给左边θj从而完成一次迭代。

技术分享

 

 单个特征的迭代如下:

技术分享

 

 

多个特征的迭代如下:

 技术分享

上式就是批梯度下降算法(batch gradient descent),当上式收敛时则退出迭代,何为收敛,即前后两次迭代的值不再发生变化了。一般情况下,会设置一个具体的参数,当前后两次迭代差值小于该参数时候结束迭代。注意以下几点:

(1) a 即learning rate,决定的下降步伐,如果太小,则找到函数最小值的速度就很慢,如果太大,则可能会出现overshoot the minimum的现象;这个参数一般都是手动设置的,简单的说就是你跨步子的大小,跨得太小就会花很长的时间来收敛。反之……
 
(2) 初始点不同,获得的最小值也不同,因此梯度下降求得的只是局部最小值;
 
(3) 越接近最小值时,下降速度越慢;
 
(4) 计算批梯度下降算法时候,计算每一个θ值都需要遍历计算所有样本,当数据量的时候这是比较费时的计算。
 
批梯度下降算法的步骤可以归纳为以下几步:
 
(1)先确定向下一步的步伐大小,我们称为Learning rate ;
 
(2)任意给定一个初始值:θ向量,一般为0向量
 
(3)确定一个向下的方向,并向下走预先规定的步伐,并更新θ向量
 
(4)当下降的高度小于某个定义的值,则停止下降;
 
 
这个batch gradient descent可不是个好东西,因为它每一步都要遍历所有的examples,如果样本数很大,几百万,上千万的时候,这数基本上就是没法算了。所以就有了下面这个随机梯度算法:
stochastic gradient descent 随机梯度下降算法
每次迭代只是考虑让该样本点的J(θ)趋向最小,而不管其他的样本点,这样算法会很快,但是收敛的过程会比较曲折,整体效果上,大多数时候它只能接近局部最优解,而无法真正达到局部最优解。所以适合用于较大训练集的case。
技术分享

 

这里整个算法才用了j个training examples

 

 

梯度下降算法