梯度下降法或最速下降法是求解无约束最优化问题的一种最常用的方法，梯度下降法是迭代算法，每一步需要求解目标函数的梯度向量。
1、梯度
首先，我们来看看什么是梯度。
在向量微积分中，标量场的梯度是一个向量场。标量场中某一点上的梯度指向标量场增长最快的方向，梯度的长度是这个最大的变化率。也就是说我们按照某一点的梯度走，那么我们可以最快的速度得到其最值。
2、回归与梯度下降
回归在数学上来说是给定一个点集，能够用一条曲线去拟合之，如果这个曲线是一条直线，那就被称为线性回归，如果曲线是一条二次曲线，就被称为二次回归，回归还有很多的变种，如locally weighted回归，logistic回归，等等，这个将在后面去讲。
用一个很简单的例子来说明回归，这个例子来自很多的地方，也在很多的open source的软件中看到，比如说weka。大概就是，做一个房屋价值的评估系统，一个房屋的价值来自很多地方，比如说面积、房间的数量（几室几厅）、地 段、朝向等等，这些影响房屋价值的变量被称为特征(feature)，feature在机器学习中是一个很重要的概念，有很多的论文专门探讨这个东西。在 此处，为了简单，假设我们的房屋就是一个变量影响的，就是房屋的面积。
假设有一个房屋销售的数据如下：
面积(m^2) 销售价钱（万元）
123 250
150 320
87 160
102 220
… …
这个表类似于帝都5环左右的房屋价钱，我们可以做出一个图，x轴是房屋的面积。y轴是房屋的售价，如下：
如果来了一个新的面积，假设在销售价钱的记录中没有的，我们怎么办呢？
我们可以用一条曲线去尽量准的拟合这些数据，然后如果有新的输入过来，我们可以在将曲线上这个点对应的值返回。如果用一条直线去拟合，可能是下面的样子：
绿色的点就是我们想要预测的点。
首先给出一些概念和常用的符号，在不同的机器学习书籍中可能有一定的差别。
房屋销售记录表 - 训练集(training set)或者训练数据(training data), 是我们流程中的输入数据，一般称为x
房屋销售价钱 - 输出数据，一般称为y
拟合的函数（或者称为假设或者模型），一般写做 y = h(x)
训练数据的条目数(#training set), 一条训练数据是由一对输入数据和输出数据组成的
输入数据的维度(特征的个数，#features)，n
下面是一个典型的机器学习的过程，首先给出一个输入数据，我们的算法会通过一系列的过程得到一个估计的函数，这个函数有能力对没有见过的新数据给出一个新的估计，也被称为构建一个模型。就如同上面的线性回归函数。
我们用X1，X2..Xn 去描述feature里面的分量，比如x1=房间的面积，x2=房间的朝向，等等，我们可以做出一个估计函数：
θ在这儿称为参数，在这儿的意思是调整feature中每个分量的影响力，就是到底是房屋的面积更重要还是房屋的地段更重要。为了如果我们令X0 = 1，就可以用向量的方式来表示了：
我们程序也需要一个机制去评估我们θ是否比较好，所以说需要对我们做出的h函数进行评估，一般这个函数称为损失函数（loss function）或者错误函数(error function)，描述h函数不好的程度，在下面，我们称这个函数为J函数
在这儿我们可以做出下面的一个错误函数：
这个错误估计函数是去对x(i)的估计值与真实值y(i)差的平方和作为错误估计函数，前面乘上的1/2是为了在求导的时候，这个系数就不见了。
如何调整θ以使得J(θ)取得最小值有很多方法，其中有最小二乘法(min square)，是一种完全是数学描述的方法，在stanford机器学习开放课最后的部分会推导最小二乘法的公式的来源，这个来很多的机器学习和数学书 上都可以找到，这里就不提最小二乘法，而谈谈梯度下降法。
梯度下降法是按下面的流程进行的：
1）首先对θ赋值，这个值可以是随机的，也可以让θ是一个全零的向量。
2）改变θ的值，使得J(θ)按梯度下降的方向进行减少。
为了更清楚，给出下面的图：
这是一个表示参数θ与误差函数J(θ)的关系图，红色的部分是表示J(θ)有着比较高的取值，我们需要的是，能够让J(θ)的值尽量的低。也就是深蓝色的部分。θ0，θ1表示θ向量的两个维度。
在上面提到梯度下降法的第一步是给θ给一个初值，假设随机给的初值是在图上的十字点。
然后我们将θ按照梯度下降的方向进行调整，就会使得J(θ)往更低的方向进行变化，如图所示，算法的结束将是在θ下降到无法继续下降为止。
当然，可能梯度下降的最终点并非是全局最小点，可能是一个局部最小点，可能是下面的情况：
上面这张图就是描述的一个局部最小点，这是我们重新选择了一个初始点得到的，看来我们这个算法将会在很大的程度上被初始点的选择影响而陷入局部最小点
下面我将用一个例子描述一下梯度减少的过程，对于我们的函数J(θ)求偏导J：（求导的过程如果不明白，可以温习一下微积分）
下面是更新的过程，也就是θi会向着梯度最小的方向进行减少。θi表示更新之前的值，-后面的部分表示按梯度方向减少的量，α表示步长，也就是每次按照梯度减少的方向变化多少。
一个很重要的地方值得注意的是，梯度是有方向的，对于一个向量θ，每一维分量θi都可以求出一个梯度的方向，我们就可以找到一个整体的方向，在变化的时候，我们就朝着下降最多的方向进行变化就可以达到一个最小点，不管它是局部的还是全局的。
用更简单的数学语言进行描述步骤2）是这样的：
倒三角形表示梯度，按这种方式来表示，θi就不见了，看看用好向量和矩阵，真的会大大的简化数学的描述啊。
3、梯度下降法的一般步骤
上面通过一个例子形象的给出了梯度下降法的一个应用，接下来，根据李航老师的《统计学习方法》一书，我们给出如下的梯度下降法的步骤：
4、梯度下降法的类型
全量梯度下降(Batch gradient descent)
全量梯度下降法每次使用全量的训练集样本来更新模型参数，即：
其代码如下：
for i in range(epochs):
params_grad = evaluate_gradient(loss_function,data,params)
params = params - learning_rate * params_grad
epochs 是用户输入的最大迭代次数。通过上诉代码可以看出，每次使用全部训练集样本计算损失函数loss_function的梯度params_grad，然后使用学习速率learning_rate朝着梯度相反方向去更新模型的每个参数params。
全量梯度下降每次学习都使用整个训练集，因此其优点在于每次更新都会朝着正确的方向进行，最后能够保证收敛于极值点(凸函数收敛于全局极值点，非凸函数可能会收敛于局部极值点)，但是其缺点在于每次学习时间过长，并且如果训练集很大以至于需要消耗大量的内存，并且全量梯度下降不能进行在线模型参数更新。
随机梯度下降(Stochastic gradient descent)
随机梯度下降算法每次从训练集中随机选择一个样本来进行学习，即：
批量梯度下降算法每次都会使用全部训练样本，因此这些计算是冗余的，因为每次都使用完全相同的样本集。而随机梯度下降算法每次只随机选择一个样本来更新模型参数，因此每次的学习是非常快速的，并且可以进行在线更新。
代码如下：
for i in range(epochs):
np.random.shuffle(data)
for example in data:
params_grad = evaluate_gradient(loss_function,example,params)
params = params - learning_rate * params_grad
随机梯度下降最大的缺点在于每次更新可能并不会按照正确的方向进行，因此可以带来优化波动(扰动)，如下图：
不过从另一个方面来看，随机梯度下降所带来的波动有个好处就是，对于类似盆地区域（即很多局部极小值点）那么这个波动的特点可能会使得优化的方向从当前的局部极小值点跳到另一个更好的局部极小值点，这样便可能对于非凸函数，最终收敛于一个较好的局部极值点，甚至全局极值点。
由于波动，因此会使得迭代次数（学习次数）增多，即收敛速度变慢。不过最终其会和全量梯度下降算法一样，具有相同的收敛性，即凸函数收敛于全局极值点，非凸损失函数收敛于局部极值点。
小批量梯度下降(Mini-batch gradient descent)
Mini-batch梯度下降综合了batch梯度下降与stochastic梯度下降，在每次更新速度与更新次数中间取得一个平衡，其每次更新从训练集中随机选择m,m<n个样本进行学习，即：
其代码如下：
for i in range(epochs):
np.random.shuffle(data)
for batch in get_batches(data, batch_size=50):
params_grad = evaluate_gradient(loss_function,batch,params)
params = params - learning_rate * params_grad
相对于随机梯度下降，Mini-batch梯度下降降低了收敛波动性，即降低了参数更新的方差，使得更新更加稳定。相对于全量梯度下降，其提高了每次学习的速度。并且其不用担心内存瓶颈从而可以利用矩阵运算进行高效计算。一般而言每次更新随机选择[50,256]个样本进行学习，但是也要根据具体问题而选择，实践中可以进行多次试验，选择一个更新速度与更次次数都较适合的样本数。
5、梯度下降法的挑战
虽然梯度下降算法效果很好，并且广泛使用，但同时其也存在一些挑战与问题需要解决：
1）选择一个合理的学习速率很难。如果学习速率过小，则会导致收敛速度很慢。如果学习速率过大，那么其会阻碍收敛，即在极值点附近会振荡。
2）学习速率调整(又称学习速率调度，Learning rate schedules)[11]试图在每次更新过程中，改变学习速率，如退火。一般使用某种事先设定的策略或者在每次迭代中衰减一个较小的阈值。无论哪种调整方法，都需要事先进行固定设置，这边便无法自适应每次学习的数据集特点。
3）模型所有的参数每次更新都是使用相同的学习速率。如果数据特征是稀疏的或者每个特征有着不同的取值统计特征与空间，那么便不能在每次更新中每个参数使用相同的学习速率，那些很少出现的特征应该使用一个相对较大的学习速率。
4）对于非凸目标函数，容易陷入那些次优的局部极值点中，如在神经网路中。那么如何避免呢。Dauphin指出更严重的问题不是局部极值点，而是鞍点(These saddle points are usually surrounded by a plateau of the same error, which makes it notoriously hard for SGD to escape, as the gradient is close to zero in all dimensions.)。
6、梯度下降优化算法
待更新
