机器学习, 神经网络

梯度下降

一、符号约定

在介绍内容前,我们先约定一些常用符号:

  • :训练样本的数量
  • :每个样本中变量的个数
  • 或者:变量或者特征
  • 或者:因变量或者目标变量
  • :训练集
  • :第个训练样本

二、梯度下降

梯度下降法(英语:Gradient descent)是一个一阶最优化算法,通常也称为最速下降法。 要使用梯度下降法找到一个函数的局部极小值,必须向函数上当前点对应梯度(或者是近似梯度)的反方向的规定步长距离点进行迭代搜索。

这个算法通常用于预测,算法的核心思想是首先寻找一个能够表示当前估计的预测公式的“成本”(即与真实情况的差别)的函数,之后使用梯度下降法寻找能够得到它的最小值(当然,在比较复杂的情况下我们只能找到局部最小值)的参数。这里需要尤为注意的一点是我们的目标是寻找能够使成本函数最小化的参数,而不是得到最小化的成本函数,因为单纯的成本函数是没有意义的。

三、公式推导

现在假设有一个预测函数,我们一般使用最小二乘法来定义成本函数如下:
,这里的1/2是为了之后的运算简便加入的。

那么我们怎么求能使上述公式最小化的参数呢?

基本思想很简单,我们先随机给赋一个值,然后求在这个值下成本函数对的导数,根据微积分的知识,我们可以知道导数是一个函数下降最快的方向,所以我们只要对参数做如下处理即可:

对于线性回归函数,我们可以进行如下化简:

上述公式也就是梯度下降的核心公式,它有几种不同的计算方法,这里介绍两种常用的:

  • 批量梯度下降法(Batch Gradient Descent):对每个参数,每次遍历整个训练集计算其更新值。这种方法速度会比较慢,甚至对于较大的、内存无法容纳的数据集,该方法都无法被使用。同时,梯度下降法不能以「在线」的形式更新我们的模型,也就是不能再运行中加入新的样本进行运算。
  • 随机梯度下降(Stochastic Gradient Descent):每次使用一个样本来更新所有的参数,速度较快。

四、梯度下降的向量公式

但是实际采用上面两种方法,会让很多的时间浪费在I/O而不是计算上,在机器学习中有一种更为常用的方法来避免显式的循环,即使用向量。下面我们来推导一下这个公式的向量形式。

首先预测函数写成向量形式:
(输入变量为m×n的矩阵,参数向量为n维行向量。可知h(x)是一个m维的列向量)

这时,可以表示为:
,可以使用表示导数,其中的第i行第j列的元素表示使用第i个样本计算出的成本函数对第j个参数的导数。

利用矩阵的迹运算,我们可以求出
令上式等于0可得(因为是实数,所以也可以写成)。这样可以直接得出更新之后的的值。
值得注意的是,梯度下降的向量实现在线性回归、样本量不大的情况下是个好方法,但却并不具有可行性,因为这个公式一次将所有的数据投入运算,而在实际中我们的样本可能非常大,无法一次投入运算,并且我们并不是每次都有好运气遇到一个可以使用线性回归解决的问题。所以我们一般采用的还是前面所述的两种方法,不过我们一般用向量计来取代批量梯度下降中的迭代过程。

五、代码实现

这里的代码实现参考了斯坦福机器学习笔记,使用线性回归函数来作为例子。

import numpy as np

def h(theta, X):
    """预测函数

    Args:
        theta: 相关系数矩阵
        X: 特征向量

    Returns:
        预测结果
    """
    return X.T * theta

def j(theta, X, y):
    """代价函数

    Args:
        theta: 相关系数矩阵
        X: 样本集矩阵
        y: 标签集矩阵

    Returns:
        预测误差(代价)
    """
    m = X.shape[0]
    hx = h(theta, X)
    return 1/2 * (hx - y).T * (hx - y)

def gd(rate, maxLoop, epsilon, X, y):
    """批量梯度下降法

    Args:
        rate: 学习率
        maxLoop: 最大迭代次数
        epsilon: 收敛精度
        X: 样本矩阵
        y: 标签矩阵

    Returns:
        (theta, errors)
    """
    m,n = X.shape
    # 初始化theta
    theta = np.zeros((n,1))
    count = 0
    converged = False
    error = float('inf')
    while count<=maxLoop and not converged :
        count += 1
        deriv = X.T * X * theta - y.T * X
        theta = theta - rate * deriv
        error = j(theta, X, y)
        # 如果已经收敛
        if(error < epsilon):
            converged = True
    return theta