首页 > 代码库 > 第二集 监督学习的应用 梯度下降

第二集 监督学习的应用 梯度下降

一:线性回归:

例:上一节课的房屋大小与价格数据集

 

技术分享

本例中:m:数据个数,x:房屋大小,y:价格

通用符号:

m = 训练样本数

x = 输入变量(特征)

y = 输出变量(目标变量)

(x,y) – 一个样本

技术分享 –第i个训练样本 =技术分享

对假设进行线性表示  h(x)=θ01*x

在线性回归的问题上大部分都会有多个输入特征,比如这个例子的输入特征可能也有房间大小,卧室数目两个特征,那么就用x1=房间大小,x2=卧室数目。则方程式就变成了:

h(x)=θ01*x12*x2

                                                                                             

 为了将公式简洁化,假设x0=0,则当有n种特征时,公式为:技术分享    n为特征数目,θ为参数

 选择θ的目的,是使h(x)与y的平方差尽量小。又由于有m个训练样本,需要计算每个样本的平方差,最后为了简化结果乘以1/2,即(最小二乘法):技术分享(这里的上标 i 表示第几个样本)(最小二乘法的原理需要看一下,http://blog.csdn.net/lotus___/article/details/20546259)

最小二乘法的思想, 使得预测数据尽量接近训练集给出的答案,剩下的问题是求该函数的最小值时 θ值。)

但是各个xn前面的参数是无法确定的,因此可以采用梯度下降的方法来确定Θn的值。根据最小二乘法,得到误差函数J(Θ),目标是计算出各个θ,使得J(θ)最小。

我们要做的就是求:min(J(θ))

 

min(J(θ))方法:梯度下降和正规方程组

二  梯度下降

梯度下降是一种搜索算法,基本思想:先给出参数向量一个初始值;不断改变,使得 J(θ)不断缩小。

下面就是计算梯度下降的方法:
1. 随机初始化θ
2. 迭代,如果新的θ能够获得使得J(θ)更小
3. 如果J(θ)能够继续减小,那么回到2,继续执行

梯度下降

如图所示,水平坐标轴表示θ0和θ1,垂直坐标表示J(θ)

技术分享

 

 

 一开始选择0向量作为初始值,假设该三维图为一个三维地表,0向量的点位于一座“山”上。梯度下降的方法是,你环视一周,寻找下降最快的路径,即为梯度的方向,每次下降一小步,再环视四周,继续下降,以此类推。结果到达一个局部最小值,如下图:

技术分享

当然,若初始点不同,则结果可能为另一个完全不同的局部最小值,如下:

技术分享

表明梯度下降的结果依赖于参数初始值。

梯度下降算法的数学表示:

技术分享(这些图片θ的下标有的是j,有的是i,这都是各个作者写的方式不同,但是意思都是一样的,就是第几个参数,上标表示第几个样本,下标表示第几个参数)

技术分享为赋值运算符,即表示程序中的的赋值语句。

每一次将技术分享减去技术分享技术分享求偏导的结果,即沿最陡峭的“山坡”下降

技术分享(这里的下标j也是表示第几个参数)

技术分享:学习速度,步长,手动给出的参数。即决定你下山时每一步迈多大。设的过小,收敛时间长,设的过大,可能会超过最小值

 

(1)      批梯度下降算法:

上述为处理一个训练样本的公式,将其派生成包含m个训练样本的算法,循环下式直至收敛:

 

技术分享(这里θ的下标表示第i个参数)

复杂度分析:

对于每个技术分享的每次迭代,即上式所示,时间为O(m),每一个样本都对θ的值进行了更新

每次迭代(走一步)需要计算n个特征的梯度值,复杂度为O(mn)

一般来说,这种二次函数的技术分享的三维图形为一个碗状,有一个唯一的全局最小值。其等高线为一个套一个的椭圆形,运用梯度下降会快速收敛到圆心。

 

技术分享

梯度下降性质:接近收敛时,每次的步子会越来越小。其原因是每次减去技术分享乘以梯度,但是梯度会越来越小,所以步子会越来越小。

 

检测是否收敛的方法:

1)       检测两次迭代技术分享的改变量,若不再变化,则判定收敛

2)       更常用的方法:检验技术分享,若不再变化,判定收敛

 

批梯度下降算法的优点是能找到局部最优解,但是若训练样本m很大的话,其每次迭代都要计算所有样本的偏导数的和,当训练集合数据量大时效率比较低,需要的时间比较长,于是采用下述另一种梯度下降方法。

 (2)      随机梯度下降算法(增量梯度下降算法):

技术分享

 

每次计算技术分享不需要再遍历所有数据,而是只需计算样本i即可。

批梯度下降中,走一步为考虑m个样本;随机梯度下降中,走一步只考虑1个样本,也就是一个样本更新一个参数,等n个样本把n个参数一对一都更新了一次后,再换一组样本对参数更新,比如说更新个10次(样本的位置可以换一下,比如第一次样本1对参数θ1进行了更新,下次让 样本1对θ2更新

每次迭代复杂度为O(n)。当m个样本用完时,继续循环到第1个样本。

增量梯度下降算法可以减少大训练集收敛的时间(比批量梯度下降快很多),但可能会不精确收敛于最小值而是接近最小值。

上述使用了迭代的方法求最小值,实际上对于这类特定的最小二乘回归问题,或者普通最小二乘问题,存在其他方法给出最小值,接下来这种方法可以给出参数向量的解析表达式,如此一来就不需要迭代求解了。

 

3、 正规方程组

给定一个函数J,J是一个关于参数数组的函数,定义J的梯度关于的导数,它自己也是一个向量。向量大小为n+1维(从0到n),如下:

技术分享

所以,梯度下降算法可写成:技术分享

J:关于参数数组的函数;

 

下三角:梯度

 

更普遍的讲,对于一个函数f,f的功能是将一个m*n的矩阵映射到实数空间上,即:技术分享

 

假设输入为m*n大小的矩阵A,定义f关于矩阵A的导数为:

 

技术分享

 

导数本身也是个矩阵,包含了f关于A的每个元素的偏导数。

 

 

 

如果A是一个方阵,即n*n的矩阵,则将A的迹定义为A的对角元素之和,即:

 

技术分享

 

 

 

trA即为tr(A)的简化。迹是一个实数。

 

 

 

一些关于迹运算符和导数的定理:

 

1)       trAB = trBA

 

2)       trABC = trCAB = trBCA

 

3)       技术分享

 

4)       技术分享

 

5)       技术分享 tra = a

 

6)       技术分享

 

  

 

有了上述性质,可以开始推导了:

 

定义矩阵X,称为设计矩阵,包含了训练集中所有输入的矩阵,第i行为第i组输入数据,即:

 

技术分享

 

则由于技术分享,所以可得:

 

技术分享

 

又因为对于向量z,有技术分享,则有:

 

技术分享

 

由上述最后一个性质可得:技术分享

 

通过上述6个性质,推导:

 

技术分享

 

倒数第三行中,运用最后一个性质

 

 

 

技术分享置为0,则有:技术分享

 

称为正规方程组

 

可得:技术分享(推导过程知识:迹与矩阵求导)

 

 

 

 

 

 

 

 

 

 

 

 

第二集 监督学习的应用 梯度下降