PROSAGA-机器学习-机器学习十大算法-SGD梯度下降

<div style="width:595.0pt;margin-bottom:72.0pt;margin-top:72.0pt;margin-left:90.0pt;margin-right:90.0pt;">
 梯度下降（GD）是最小化风险函数、损失函数的一种常用方法，随机梯度下降和批量梯度下降是两种迭代求解思路，下面从公式和实现的角度对两者进行分析，如有哪个方面写的不对，希望网友纠正。
 
 下面的h(x)是要拟合的函数，J(theta)损失函数，theta是参数，要迭代求解的值，theta求解出来了那最终要拟合的函数h(theta)就出来了。其中m是训练集的记录条数，j是参数的个数。
 <img src="/user/files/H0WJPXXXE4gU1VFxkX9y3Dj1fEwwVEKrbJksKJoTt-g.png" width="90.0pt" height="100%">
 <img src="/user/files/wMTv5fMF-MTk-djC0f5yOhyOj2DwdYuecio8dssF6rA.png" width="187.5pt" height="100%">
 
 1、批量梯度下降的求解思路如下：
 （1）将J(theta)对theta求偏导，得到每个theta对应的的梯度
    <img src="/user/files/Zg_ll4Uat9V1CCeqlI4T5JULglmHMY4lkG5sUz5gTlM.png" width="187.5pt" height="100%">
 （2）由于是要最小化风险函数，所以按每个参数theta的梯度负方向，来更新每个theta
 <img src="/user/files/s3EH7_AT-B-Guy94PKQwIjYZUQO5d8vyWZJn2ONs7Sg.png" width="195.0pt" height="100%">
 （3）从上面公式可以注意到，它得到的是一个全局最优解，但是每迭代一步，都要用到训练集所有的数据，如果m很大，那么可想而知这种方法的迭代速度！！所以，这就引入了另外一种方法，随机梯度下降。
 
 2、随机梯度下降的求解思路如下：
 （1）上面的风险函数可以写成如下这种形式，损失函数对应的是训练集中每个样本的粒度，而上面批量梯度下降对应的是所有的训练样本：
 <img src="/user/files/9tq1SK1rJHekhQzqjUYlXTrmjxSHup6SyOUW3Dp5Cq4.png" width="330.0pt" height="100%">
 （2）每个样本的损失函数，对theta求偏导得到对应梯度，来更新theta
 <img src="/user/files/nRom2RVq07fEYqg51awkgkqOnjo03OHxkbQEmeD-G3Y.png" width="172.5pt" height="100%">
 （3）随机梯度下降是通过每个样本来迭代更新一次，如果样本量很大的情况（例如几十万），那么可能只用其中几万条或者几千条的样本，就已经将 theta迭代到最优解了，对比上面的批量梯度下降，迭代一次需要用到十几万训练样本，一次迭代不可能最优，如果迭代10次的话就需要遍历训练样本10 次。但是，SGD伴随的一个问题是噪音较BGD要多，使得SGD并不是每次迭代都向着整体最优化方向。
 
 
 
 一、梯度gradient
 <a href="http://zh.wikipedia.org/wiki/%E6%A2%AF%E5%BA%A6">http://zh.wikipedia.org/wiki/%E6%A2%AF%E5%BA%A6 </a>
 在标量场f中的一点处存在一个矢量G，该矢量方向为f在该点处变化率最大的方向，其模也等于这个最大变化率的数值，则矢量G称为标量场f的梯度。
 在<a href="http://baike.baidu.com/view/7823334.htm">向量微积分 </a>中，<a href="http://baike.baidu.com/view/550627.htm">标量场 </a>的梯度是一个<a href="http://baike.baidu.com/view/550639.htm">向量场 </a>。
 标量场中某一点上的梯度指向标量场增长最快的方向，梯度的长度是这个最大的变化率。
 更严格的说，从欧氏空间Rn到R的函数的梯度是在Rn某一点最佳的线性近似。在这个意义上，梯度是雅戈比矩阵的一个特殊情况。
 在单变量的<a href="http://baike.baidu.com/view/1120153.htm">实值函数 </a>的情况，梯度只是<a href="http://baike.baidu.com/view/30958.htm">导数 </a>，或者，对于一个<a href="http://baike.baidu.com/view/2169890.htm">线性函数 </a>，也就是线的<a href="http://baike.baidu.com/view/271319.htm">斜率 </a>。
 梯度一词有时用于<a href="http://baike.baidu.com/view/479644.htm" \t "_blank">斜度 </a>，也就是一个<a href="http://baike.baidu.com/view/324917.htm">曲面 </a>沿着给定方向的倾斜程度。
 一个标量函数<img src="/user/files/LA27K9W9FA6MC_rheEnWqtQ_xRpgNs8d6IAC4pp_2w4.png" width="9.75pt" height="100%">的梯度记为：<img src="/user/files/7XY-wTwb6SUe4YGvuxm8UByneuuJiulGdBvKP2jJ-ik.png" width="22.5pt" height="100%"> 或 <img src="/user/files/e0-1lWyiCXaH--EfnGndU9p99ppU1glP-XwO0bPsUE4.png" width="39.0pt" height="100%">， 其中<img src="/user/files/Vv7IQJRzhwjuUGmZTaonBxovDGUl3yXl469i7UEVtAo.png" width="12.0pt" height="100%">（<a href="http://zh.wikipedia.org/wiki/Nabla%E7%AC%A6%E5%8F%B7">nabla </a>）表示矢量<a href="http://zh.wikipedia.org/wiki/%E5%BE%AE%E5%88%86%E7%AE%97%E5%AD%90" \t "_blank">微分算子 </a>。
  
 二、梯度下降法
 <a href="http://zh.wikipedia.org/wiki/%E6%A2%AF%E5%BA%A6%E4%B8%8B%E9%99%8D%E6%B3%95">http://zh.wikipedia.org/wiki/%E6%A2%AF%E5%BA%A6%E4%B8%8B%E9%99%8D%E6%B3%95 </a>
 梯度下降法，基于这样的观察：
 如果实值函数 <img src="/user/files/GsZ9LU2xgAhTQnO-CZg3QGMBJb2qmqk2puh1qJhwMjk.png" width="31.5pt" height="100%"> 在点 <img src="/user/files/Ym_FkZ8RunOoKTG7czpBhzWq2jW9p-ZiJmiCGGrq38Q.png" width="8.25pt" height="100%"> 处<a href="http://zh.wikipedia.org/wiki/%E5%8F%AF%E5%BE%AE" \t "_blank">可微 </a>且有定义，那么函数 <img src="/user/files/GsZ9LU2xgAhTQnO-CZg3QGMBJb2qmqk2puh1qJhwMjk.png" width="31.5pt" height="100%">在 <img src="/user/files/Ym_FkZ8RunOoKTG7czpBhzWq2jW9p-ZiJmiCGGrq38Q.png" width="8.25pt" height="100%"> 点沿着<a href="http://zh.wikipedia.org/wiki/%E6%A2%AF%E5%BA%A6" \t "_blank">梯度 </a>相反的方向 <img src="/user/files/njkKxoqVdvJ2cw4C7gP3keGJmC6FuXbmNMSPosamr3w.png" width="53.25pt" height="100%"> 下降最快。因而，如果
 <img src="/user/files/w6JVYXWPoT2PsbFdZPSvGpPcrWIEg-AUj79D2Cm3fTo.png" width="106.5pt" height="100%">
 对于 <img src="/user/files/dIbcME7ZT349mhFtBzwvx_gTBe71WUk7tq2g3WUITWA.png" width="34.5pt" height="100%"> 为一个够小数值时成立，那么 <img src="/user/files/cNsDGcgyXQ4Np3qKgYIXa6IKfdTwLVkq79Qac7N9euM.png" width="81.75pt" height="100%">。
 <img src="/user/files/Ym_FkZ8RunOoKTG7czpBhzWq2jW9p-ZiJmiCGGrq38Q.png" width="8.25pt" height="100%"> 是向量。
 考虑到这一点，我们可以从函数 <img src="/user/files/OE4rA1AR_xNfQ3wjELzB9HFn63ZM-4hlT3vFk8Z_ZhQ.png" width="11.25pt" height="100%"> 的局部极小值的初始估计 <img src="/user/files/ddpQWQ3WkywvMFDq2vDe4UtYiTTrXYF_bUoEeXbUNbs.png" width="14.25pt" height="100%"> 出发，并考虑如下序列 <img src="/user/files/MtcZgQecHH00eGueN0fzhfy_yqU2IOS_eAn2ltaPAXY.png" width="80.25pt" height="100%"> 使得
 <img src="/user/files/PTwKplXAoKGgtgZ1cG824ykZvTzyupiNBHFC0FGXTfI.png" width="199.5pt" height="100%">
 因此可得到
 <img src="/user/files/j7jK9vz4PxSt9HashhqX7G0-WNkIXBIBYG1Ofy5OciU.png" width="198.0pt" height="100%">
 如果顺利的话序列 <img src="/user/files/YD-ySuj1iHbd8Dwja_EMJxPLY7tw6QQa9I-2k3Bqhi8.png" width="25.5pt" height="100%"> 收敛到期望的极值。注意每次迭代步长 <img src="/user/files/-iKKnucEECYMwDdDgWYfWozIE_q7GvGw-KXYZn457Ww.png" width="8.25pt" height="100%"> 可以改变。
  
 梯度下降法的缺点是：
 靠近极小值时速度减慢。
 直线搜索可能会产生一些问题。
 可能会'之字型'地下降。
  
 三、随机梯度下降法stochastic gradient descent，也叫增量梯度下降
 由于梯度下降法收敛速度慢，而随机梯度下降法会快很多
 –根据某个单独样例的误差增量计算权值更新，得到近似的梯度下降搜索（随机取一个样例）
 –可以看作为每个单独的训练样例定义不同的误差函数
 –在迭代所有训练样例时，这些权值更新的序列给出了对于原来误差函数的梯度下降的一个合理近似
 –通过使下降速率的值足够小，可以使随机梯度下降以任意程度接近于真实梯度下降
 •标准梯度下降和随机梯度下降之间的关键区别
 –
 标准梯度下降是在权值更新前对所有样例汇总误差，
 而随机梯度下降的权值是通过考查某个训练样例来更新的
 –在标准梯度下降中，权值更新的每一步对多个样例求和，需要更多的计算
 –标准梯度下降，由于使用真正的梯度，标准梯度下降对于每一次权值更新经常使用比随机梯度下降大的步长
 –如果标准误差曲面有多个局部极小值，随机梯度下降有时可能避免陷入这些局部极小值中
 
 
 一、误差准则函数与随机梯度下降：
 数学一点将就是，对于给定的一个点集（X，Y），找到一条曲线或者曲面，对其进行拟合之。同时称X中的变量为特征（Feature)，Y值为预测值。
 如图：
 <img src="/user/files/3ONyQKx7KbuVVVFo3onaKzEPlelKVz-T1Gam7NDGa60.png" width="243.75pt" height="100%">
 一个典型的机器学习的过程，首先给出一组输入数据X，我们的算法会通过一系列的过程得到一个估计的函数，这个函数有能力对没有见过的新数据给出一个新的估计Y，也被称为构建一个模型。
 我们用X1、X2...Xn 去描述feature里面的分量，用Y来描述我们的估计，得到一下模型：
 <img src="/user/files/c2o05tt_PDJo7pU2fWZyVmTR93IhQ0GrjkmKtuOBSpI.png" width="180.0pt" height="100%">
 我们需要一种机制去评价这个模型对数据的描述到底够不够准确，而采集的数据x、y通常来说是存在误差的（多数情况下误差服从高斯分布），于是，自然的，引入误差函数：
 <img src="/user/files/5kl8ERs8rCvQ8X5e5iJmDexLW2wpDR9qEUQFR24ZIYE.png" width="180.0pt" height="100%"> 
 关键的一点是如何调整theta值，使误差函数J最小化。J函数构成一个曲面或者曲线，我们的目的是找到该曲面的最低点：
 <img src="/user/files/p0im-cuWl5NDYEQEO1f7c5JTB4V5zDARQLibBcQiJRo.png" width="227.25pt" height="100%"> 
 假设随机站在该曲面的一点，要以最快的速度到达最低点，我们当然会沿着坡度最大的方向往下走（梯度的反方向）
 用数学描述就是一个求偏导数的过程：
 <img src="/user/files/cbaCHRiey0rFuYGMoJWlUZ5bOeWn8VIYXf9kv1UPfR4.png" width="323.25pt" height="100%"> 
 这样，参数theta的更新过程描述为以下：
 <img src="/user/files/ov1aI3lIJseIoPUD1Nah9EoTeHkK3uzdcCPziesfGYE.png" width="266.25pt" height="100%">   （α表示算法的学习速率） 
 二、算法实现与测试：
 通过一组数据拟合 y = theta1*x1 +theta2*x2
 [python]<a href="http://blog.csdn.net/zbc1090549839/article/details/38149561">view plain </a><a href="http://blog.csdn.net/zbc1090549839/article/details/38149561">copy </a><a href="http://blog.csdn.net/zbc1090549839/article/details/38149561">print </a><a href="http://blog.csdn.net/zbc1090549839/article/details/38149561">? </a><img src="/user/files/OV0QgkyVdMfNl7PKzvrQ8Xg-mKmWdW0h1ZA57hTqYvo.png" width="9.0pt" height="100%">
 #Python 3.3.5  
 # matrix_A  训练集  
 matrix_A = [[1,4], [2,5], [5,1], [4,2]]  
 Matrix_y = [19,26,19,20]  
 theta = [2,5]  
 #学习速率  
 leraing_rate = 0.005  
 loss = 50  
 iters = 1  
 Eps = 0.0001  
 while loss>Eps and iters <1000 :  
     loss = 0  
     for i in range(3) :  
         h = theta[0]*matrix_A[i][0] + theta[1]*matrix_A[i][1]   
         theta[0] = theta[0] + leraing_rate*(Matrix_y[i]-h)*matrix_A[i][0]  
         theta[1] = theta[1] + leraing_rate*(Matrix_y[i]-h)*matrix_A[i][1]  
     for i in range(3) :  
         Error = 0  
         Error = theta[0]*matrix_A[i][0] + theta[1]*matrix_A[i][1] - Matrix_y[i]  
         Error = Error*Error  
         loss = loss +Error  
     iters = iters +1  
 print ('theta=',theta)  
 print ('iters=',iters)  
 求解结果：
 >>>   
 theta= [2.9980959216157945, 4.001522800837675]  
 iters= 75  
 但如果对输入数据添加一些噪声
 matrix_A = [[1.05,4], [2.1,5], [5,1], [4,2]]  
 求解结果为：
 >>>   
 theta= [3.0095950685197725, 3.944718521027671]  
 iters= 1000  
 可见在有噪声的情况下，要及时调整模型误差精度、迭代次数上限，一期达到我们的需求。
</div>

机器学习十大算法-SGD梯度下降(机器学习十大算法)