机器学习

梯度下降

一、符号约定

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

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

二、梯度下降

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

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

三、公式推导

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

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

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

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

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

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

五、实现

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

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