最优化方法一：梯度下降法

        本文将从一个下山的场景开始，先提出梯度下降算法的基本思想，进而从数学上解释梯度下降算法的原理，最后实现一个简单的梯度下降算法的实例！

1 梯度下降

1.1 梯度下降的场景假设

1.2 梯度下降

       首先，我们有一个可微分的函数。这个函数就代表着一座山。我们的目标就是找到这个函数的最小值，也就是山底。根据之前的场景假设，最快的下山的方式就是找到当前位置最陡峭的方向，然后沿着此方向向下走，对应到函数中，就是找到给定点的梯度 ，然后朝着梯度相反的方向，就能让函数值下降的最快！因为梯度的方向就是函数之变化最快的方向(在后面会详细解释)
所以，我们重复利用这个方法，反复求取梯度，最后就能到达局部的最小值，这就类似于我们下山的过程。而求取梯度就确定了最陡峭的方向，也就是场景中测量方向的手段。那么为什么梯度的方向就是最陡峭的方向呢？接下来，我们从微分开始讲起。

1.2.1 微分：

看待微分的意义，可以有不同的角度，最常用的两种是：

• 函数图像中，某点的切线的斜率

• 函数的变化率
  几个微分的例子：

         

上面的例子都是单变量的微分，当一个函数有多个变量的时候，就有了多变量的微分，即分别对每个变量进行求微分：

       

1.2.2 梯度

        梯度实际上就是多变量微分的一般化。例如：

      

       我们可以看到，梯度就是分别对每个变量进行微分，然后用逗号分割开，梯度是用<>包括起来，说明梯度其实一个向量。

梯度是微积分中一个很重要的概念，之前提到过梯度的意义

• 在单变量的函数中，梯度其实就是函数的微分，代表着函数在某个给定点的切线的斜率
• 在多变量函数中，梯度是一个向量，向量有方向，梯度的方向就指出了函数在给定点的上升最快的方向

        这也就说明了为什么我们需要千方百计的求取梯度！我们需要到达山底，就需要在每一步观测到此时最陡峭的地方，梯度就恰巧告诉了我们这个方向。梯度的方向是函数在给定点上升最快的方向，那么梯度的反方向就是函数在给定点下降最快的方向，这正是我们所需要的。所以我们只要沿着梯度的方向一直走，就能走到局部的最低点！

1.3 梯度下降算法的数学解释

        下面开始从数学上解释梯度下降算法的计算过程和思想。

              

        此公式的意义是：J是关于Θ的一个函数，我们当前所处的位置为Θ0点，要从这个点走到J的最小值点，也就是山底。首先我们先确定前进的方向，也就是梯度的反向，然后走一段距离的步长，也就是α，走完这个段步长，就到达了Θ1这个点！

             

下面就这个公式的几个常见的疑问：

1.3.1 α是什么含义

       α在梯度下降算法中被称作为学习率或者步长，意味着我们可以通过α来控制每一步走的距离，以保证不要步子跨的太大，不要走太快，错过了最低点。同时也要保证不要走的太慢，导致太阳下山了，还没有走到山下。所以α的选择在梯度下降法中往往是很重要的！α不能太大也不能太小，太小的话，可能导致迟迟走不到最低点，太大的话，会导致错过最低点！

1.3.2 为什么要梯度要乘以一个负号？

        梯度前加一个负号，就意味着朝着梯度相反的方向前进！我们在前文提到，梯度的方向实际就是函数在此点上升最快的方向！而我们需要朝着下降最快的方向走，自然就是负的梯度的方向，所以此处需要加上负号。

1.4 梯度下降算法的实例

我们已经基本了解了梯度下降算法的计算过程，那么我们就来看几个梯度下降算法的小实例，首先从单变量的函数开始。

1.4.1 单变量函数的梯度下降

       我们假设有一个单变量的函数：

            

       函数的微分：；   初始化，起点为；  学习率为，。

       根据梯度下降的计算公式

         

        开始进行梯度下降的迭代计算，经过四次的运算，也就是走了四步，基本就抵达了函数的最低点，也就是山底。

                                        

1.4.2 多变量函数的梯度下降

       我们假设有一个目标函数

           

       现在要通过梯度下降法计算这个函数的最小值。我们通过观察就能发现最小值其实就是 (0，0)点。接下来，我们会从梯度下降算法开始一步步计算到这个最小值！
       假设初始的起点为：； 初始的学习率为：；  函数的梯度为：

       进行多次迭代，已经基本靠近函数的最小值点：

      

         

2 批量梯度下降法 BGD(Batch gradient descent)

2.1 简介

        梯度下降就是上面的推导，要留意，在梯度下降中，对于θ的更新，所有的样本都有贡献，也就是参与调整θ。其计算得到的是一个标准梯度。因而理论上来说一次更新的幅度是比较大的。如果样本不多的情况下，当然是这样收敛的速度会更快。

例如一个线性回归问题，使用均方误差代价函数作为代价函数：

         

      此公示中

• m是数据集中点的个数
• ½是一个常量，这样是为了在求梯度的时候，二次方乘下来就和这里的½抵消了，自然就没有多余的常数系数，方便后续的计算，同时对结果不会有影响
• y 是数据集中每个点的真实y坐标的值

• h 是我们的预测函数，根据每一个输入x，根据Θ 计算得到预测的y值，即

           

       我们可以根据代价函数看到，代价函数中的变量有两个，所以是一个多变量的梯度下降问题，求解出代价函数的梯度，也就是分别对两个变量进行微分：

       

      从上面公式可以注意到，它得到的是一个全局最优解，但是每迭代一步，都要用到训练集所有的数据，如果m很大，那么可想而知这种方法的迭代速度会相当的慢。所以，这就引入了另外一种方法——随机梯度下降。

　　对于批量梯度下降法，样本个数m，x为n维向量，一次迭代需要把m个样本全部带入计算，迭代一次计算量为m*n^2。

2.2 Python实现

     x1和x2是样本值，y是预测目标，我们需要以一条直线来拟合上面的数据，待拟合的函数如下：

       ——1式

    我们的目的就是要求出θ1和θ2的值，让h(θ)尽量逼近目标值y。

    样本值取自于y=3*x1+4*x2

   我们首先确定损失函数：

 

      ——2式

    其中，J(θ)是损失函数，m代表每次取多少样本进行训练，如果采用SGD进行训练，那每次随机取一组样本，m=1；如果是批处理，则m等于每次抽取作为训练样本的数量θ是参数，对应（1式）的θ1和θ2。求出了θ1和θ2，h(x)的表达式就出来了：

        ——3式

    我们的目标是让损失函数J(θ)的值最小，根据梯度下降法，首先要用J(θ)对θ求偏导：

        ——4式

    由于是要最小化损失函数（2式），所以参数θ按其负梯度方向来更新：

       ——5式

    α是学习效率，即训练步长。

#-*- coding: utf-8 -*-
import random
#This is a sample to simulate a function y = theta1*x1 + theta2*x2
input_x = [[1,4], [2,5], [5,1], [4,2]]#输入
y = [19,26,19,20]   #输出
theta = [1,1]       #θ参数初始化
loss = 10           #loss先定义一个数，为了进入循环迭代
step_size = 0.001   #步长
eps =0.0001         #精度要求
max_iters = 10000   #最大迭代次数
error =0            #损失值
iter_count = 0      #当前迭代次数
while( loss > eps and iter_count < max_iters):
    loss = 0
    #这里更新权重的时候所有的样本点都用上了
    for i in range (4):   #4为样本数量
        pred_y = theta[0]*input_x[i][0]+theta[1]*input_x[i][1]
        theta[0] = theta[0] - step_size * (pred_y - y[i]) * input_x[i][0]
        theta[1] = theta[1] - step_size * (pred_y - y[i]) * input_x[i][1]
    for i in range (4):
        pred_y = theta[0]*input_x[i][0]+theta[1]*input_x[i][1]
        error = 0.5*(pred_y - y[i])**2
        loss = loss + error
    iter_count += 1
    print ('iters_count', iter_count)

print ('theta: ',theta )
print ('final loss: ', loss)
print ('iters: ', iter_count)

3 随机梯度下降 SGD（Stochastic gradientdescent）

3.1 简介

       每次迭代使用一组样本。针对BGD算法训练速度过慢的缺点，提出了SGD算法，普通的BGD算法是每次迭代把所有样本都过一遍，每训练一组样本就把梯度更新一次。而SGD算法是从样本中随机抽出一组，训练后按梯度更新一次，然后再抽取一组，再更新一次，在样本量及其大的情况下，可能不用训练完所有的样本就可以获得一个损失值在可接受范围之内的模型了。

        最小化每条样本的损失函数，虽然不是每次迭代得到的损失函数都向着全局最优方向， 但是大的整体的方向是向全局最优解的，最终的结果往往是在全局最优解附近，适用于大规模训练样本情况。

3.2 Python实现

# -*- coding:utf-8 -*-
# @author:sxy

import random
#This is a sample to simulate a function y = theta1*x1 + theta2*x2
input_x = [[1,4], [2,5], [5,1], [4,2]]#输入
y = [19,26,19,20]   #输出
theta = [1,1]       #θ参数初始化
loss = 10           #loss先定义一个数，为了进入循环迭代
step_size = 0.001   #步长
eps =0.0001         #精度要求
max_iters = 10000   #最大迭代次数
error =0            #损失值
iter_count = 0      #当前迭代次数
while( loss > eps and iter_count < max_iters):
    loss = 0
    #每一次选取随机的一个点进行权重的更新
    i = random.randint(0,3)
    pred_y = theta[0]*input_x[i][0]+theta[1]*input_x[i][1]
    theta[0] = theta[0] - step_size * (pred_y - y[i]) * input_x[i][0]
    theta[1] = theta[1] - step_size * (pred_y - y[i]) * input_x[i][1]
    for i in range (4):
        pred_y = theta[0]*input_x[i][0]+theta[1]*input_x[i][1]
        error = 0.5*(pred_y - y[i])**2
        loss = loss + error
    iter_count += 1
    print('iters_count', iter_count)

print('theta: ', theta)
print('final loss: ', loss)
print('iters: ', iter_count)

4 小批量梯度下降 MBGD（Mini-batch gradient descent）

4.1 简介

        SGD相对来说要快很多，但是也有存在问题，由于单个样本的训练可能会带来很多噪声，使得SGD并不是每次迭代都向着整体最优化方向，因此在刚开始训练时可能收敛得很快，但是训练一段时间后就会变得很慢。在此基础上又提出了小批量梯度下降法，它是每次从样本中随机抽取一小批进行训练，而不是一组。

4.2 Python实现

# -*- coding:utf-8 -*-
# @author:sxy
import random

# This is a sample to simulate a function y = theta1*x1 + theta2*x2
input_x = [[1, 4], [2, 5], [5, 1], [4, 2]]
y = [19, 26, 19, 20]
theta = [1, 1]
loss = 10
step_size = 0.001
eps = 0.0001
max_iters = 10000
error = 0
iter_count = 0
while (loss > eps and iter_count < max_iters):
    loss = 0

    i = random.randint(0, 3)  # 注意这里，我这里批量每次选取的是2个样本点做更新，另一个点是随机点+1的相邻点
    j = (i + 1) % 4
    pred_y = theta[0] * input_x[i][0] + theta[1] * input_x[i][1]
    theta[0] = theta[0] - step_size * (pred_y - y[i]) * input_x[i][0]
    theta[1] = theta[1] - step_size * (pred_y - y[i]) * input_x[i][1]

    pred_y = theta[0] * input_x[j][0] + theta[1] * input_x[j][1]
    theta[0] = theta[0] - step_size * (pred_y - y[j]) * input_x[j][0]
    theta[1] = theta[1] - step_size * (pred_y - y[j]) * input_x[j][1]
    for i in range(4):
        pred_y = theta[0] * input_x[i][0] + theta[1] * input_x[i][1]
        error = 0.5 * (pred_y - y[i]) ** 2
        loss = loss + error
    iter_count += 1
    print('iters_count', iter_count)

print('theta: ', theta)
print('final loss: ', loss)
print('iters: ', iter_count)

 

参考：https://blog.csdn.net/u014696921/article/details/54410193

https://www.cnblogs.com/louyihang-loves-baiyan/p/5136447.html

http://www.cnblogs.com/maybe2030/p/4751804.html