这几天在看《统计学习方法》这本书，发现 梯度下降法 在 感知机 等机器学习算法中有很重要的应用，所以就特别查了些资料。
一.介绍
梯度下降法（gradient descent）是求解无约束最优化问题的一种常用方法，有实现简单的优点。梯度下降法是迭代算法，每一步需要求解目标函数的梯度向量。
二.应用场景
1.给定许多组数据（xi, yi），xi （向量）为输入，yi为输出。设计一个线性函数y=h（x）去拟合这些数据。
2.感知机：感知机（perceptron）为二类分类的线性分类模型。 输入为实例的特征向量，输出为实例的类别， 取+1 和 -1 二值。
下面分别对这两种应用场景进行分析。
1.对于第一种场景:
既然是线性函数，在此不妨设为 h(x) = w0*x0 + w1*x1。
此时我们遇到的问题就是如何确定w0和w1这两个参数，即w=（w0，w1）这个向量。
既然是拟合，则拟合效果可以用平方损失函数：E(w)=∑ [ h(x)- y ] ^2 / 2 来衡量。
其中w是权重二维向量，x是输入二维向量，x和y都是训练集的数据，即已知。
至于后面除于2只是为了之后的推导过程中对E求导时候可以消除系数，暂时可以不管。
因此该问题变成了求E(w)最小值的无约束最优化问题
2.对于第二种场景:
假设输入空间(特征向量)为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）
1. 对于第一种场景
对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)
这里的∑是对样本空间，即训练集进行一次遍历，耗费时间较大，可以使用梯度下降的随机近似：
2. 对于第二种场景
感知机学习算法是误分类驱动的，具体采用随机梯度下降方法
▽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）有多个局部极小值时，随机梯度反而更可能避免进入局部极小值中。
四.代码及实例：
1. 对于第一种场景（批量梯度下降）：
第一步：对（x[0,0]，x1[0,1]），(x[1,0],x[1,1]).........(x[n,0],x[n,1])进行梯度计算之后得出W0、W1,
第二步：对函数进行损失衡量（误差达到标准就退出，不达到标准就进行第三步）
第三步：对（x[0,0]，x1[0,1]），(x[1,0],x[1,1]).........(x[n,0],x[n,1])进行梯度计算之后得出W0、W1,
第四步：对函数进行损失衡量（误差达到标准就退出，不达到标准就进行第五步）
。。。。。知道达到误差标准就退出
1 #include "stdio.h" 2 3 int main(void) 4 { 5 float matrix[4][2]={{1,4},{2,5},{5,1},{4,2}}; 6 float result[4]={19,26,19,20}; 7 float theta[2]={2,5}; //initialized theta {2,5}, we use the algorithm to get {3,4} to fit the model 8 float learning_rate = 0.01; 9 float loss = 1000.0; //set a loss big enough 10 11 for(int i = 0;i<100&&loss>0.0001;++i) 12 { 13 float error_sum = 0.0; 14 for(int j = 0;j<4;++j) 15 { 16 float h = 0.0; 17 for(int k=0;k<2;++k) 18 { 19 h += matrix[j][k]*theta[k]; 20 } 21 error_sum = result[j]-h; 22 for(int k=0;k<2;++k) 23 { 24 theta[k] += learning_rate*(error_sum)*matrix[j][k]; 25 } 26 } 27 printf("*************************************\n"); 28 printf("theta now: %f,%f\n",theta[0],theta[1]); 29 loss = 0.0; 30 for(int j = 0;j<4;++j) 31 { 32 float sum=0.0; 33 for(int k = 0;k<2;++k) 34 { 35 36 37 sum += matrix[j][k]*theta[k]; 38 } 39 loss += (sum-result[j])*(sum-result[j]); 40 } 41 printf("loss now: %f\n",loss); 42 } 43 return 0; 44 }
2. 对于第一种场景（随机梯度下降）：
第一步：对(x[0,0])进行梯度计算之后得出初始W0、W1,
第二步：对函数进行损失衡量（误差达到标准就退出，不达到标准就进行第三步）
第三步：对(x[1,0],x[1,1])进行梯度计算之后得出新的W0、W1,
第四步：对函数进行损失衡量（误差达到标准就退出，不达到标准就进行第五步）
。。。。。
第n步：对(x[n,0],x[n,1])进行梯度计算之后得出新的W0、W1,
第n+1步：对函数进行损失衡量（误差达到标准就退出，不达到标准就进行第n+2步）
。。。知道达到误差标准就退出
1 /* 2 * 随机梯度下降实验： 3 * 训练集输入为矩阵： 4 * 1,4 5 * 2,5 6 * 5,1 7 * 4,2 8 * 输出结果为： 9 * 19 10 * 26 11 * 19 12 * 20 13 * 目标函数:y=w0*x0+w1*x1; 14 * 15 * */ 16 #include<stdio.h> 17 #include <stdlib.h> 18 int main() 19 { 20 double matrix[4][2] = { { 1,4 },{ 2,5 },{ 5,1 },{ 4,2 } }; 21 double result[4] = { 19,26,19,20 }; 22 double w[2] = { 0,0 };//初始为零向量 23 double loss = 10.0; 24 const double n = 0.01; //步长 25 for (int i = 0; i<100 && loss>0.001; i++) 26 { 27 double error_sum = 0; 28 int m = i % 4; 29 double h = 0; 30 for (int k = 0; k < 2; k++) 31 { 32 h += matrix[m][k] * w[k]; 33 } 34 error_sum = h - result[m]; 35 for (int k = 0; k < 2; k++) 36 { 37 w[k] -= n * (error_sum)* matrix[m][k];//这里是关键 38 } 39 40 printf("%lf,%lf\n", w[0], w[1]); 41 double loss = 0; 42 for (int j = 0; j<4; j++) 43 { 44 double sum = 0; 45 for (int k = 0; k<2; k++) 46 { 47 sum += matrix[j][k] * w[k]; 48 } 49 loss += (sum - result[j]) * (sum - result[j]); 50 } 51 printf("%lf\n", loss); 52 } 53 54 system("pause"); 55 return 0; 56 }
3. 对于第二种场景
1 /* 2 * 基于感知机的随机梯度下降实验： 《统计学习方法》- p29-例2.1 3 * 训练集输入为矩阵： 4 * 3,3 5 * 4,3 6 * 1,1 7 * 输出结果为（表示实例的分类）： 8 * 1 9 * 1 10 * -1 11 * 需要参数为 w： 12 * ？ 13 * ？ 14 * 15 * 目标函数:y = w0 * x0 + w1 * x1 + b; 16 * 17 * */ 18 #include<stdio.h> 19 #include <stdlib.h> 20 int main() 21 { 22 double x[3][2]={{3,3},{4,3},{1,1}}; 23 double y[4]={1, 1, -1}; 24 double w[2]={0,0};//初始为零向量 25 double b = 0; 26 int j; 27 const double n = 1; //步长 28 29 while(1) 30 { 31 for(j=0;j<3;j++) 32 { 33 if(y[j] * (w[0] * x[j][0] + w[1] * x[j][1] + b) <= 0) 34 break; 35 } 36 if(j < 3) 37 { 38 for(int k=0;k<2;k++) 39 w[k] += n * y[j] * x[j][k];//这里是关键 40 b += n * y[j]; 41 } 42 else 43 break; 44 printf("%d :%lf,%lf %lf\n", j, w[0], w[1], b); 45 46 } 47 48 system("pause"); 49 return 0; 50 }
转载：http://www.cnblogs.com/iamccme/archive/2013/05/14/3078418.html
参考：http://blog.csdn.net/pennyliang/article/details/6998517
原文：http://www.cnblogs.com/wjy-lulu/p/6498696.html