机器学习（三）—— 梯度下降法

线性模型与线性回归

线性模型(linear model)试图学得一个通过属性的线性组合来进行预测的函数，根据预测值是的连续和离散可分为线性回归（Linar Regression）和Logistic回归

线性模型形式简单、易于建模，是最基础的机器学习模型，但却蕴涵着机器学习中一些重要的基本思
想.许多功能更为强大的非线性模型(nonlinear model)可在线性模型的基础上通过引入层级结构或高维映射而得.此外，由于 $\boldsymbol\theta$ 直观表达了各属性在预测中的重要性，因此线性模型有很好的可解释性(comprehensibility)

线性回归基本概念详解

给定由 $m$ 个属性描述的数据集 $D = \{ {(\boldsymbol x_1 ,y_1) , (\boldsymbol x_2, y_2)，...， (\boldsymbol x_m ， y_m)} \}$ ，其中， $\boldsymbol x_i = (x_{i1}; x_{i2}; ... ;x_{in})$ ，该数据集可用一个 $m \times n$ 矩阵 $\boldsymbol X$ 表示，即

$\boldsymbol X = \begin{pmatrix} x_{11} & x_{12} & \cdots & x_{1n}\\ x_{21} & x_{22} & \cdots & x_{2n}\\ \vdots & \vdots & \ddots & \vdots\\ x_{m1} & x_{m2} & \cdots & x_{mn}\\ \end{pmatrix}$

线性回归试图习得

$f(\boldsymbol X) =\boldsymbol \theta \boldsymbol X = \theta_0 +\theta_1 \boldsymbol x_1 + ... + \theta_m \boldsymbol x_m$ ，使得 $f(\boldsymbol X) \simeq \boldsymbol y$ （ $\simeq$ 表示近似等于）

其中， $\theta_0, \theta_1\cdots\theta_m$ 为待确定的参数，也就是我们要确定的一个 $m + 1$ 维向量 $\boldsymbol\theta$

我们发现， $\boldsymbol \theta$ 是 $n+1$ 维列向量，而 $X$ 是 $m \times n$ 的，为了对应上，我们增广 $\boldsymbol X$ ，令

$\boldsymbol X = \begin{pmatrix} x_{11} & x_{12} & \cdots & x_{1n} & 1\\ x_{21} & x_{22} & \cdots & x_{2n} & 1\\ \vdots & \vdots & \ddots & \vdots & \vdots\\ x_{m1} & x_{m2} & \cdots & x_{mn} & 1\\ \end{pmatrix}$

这样一来，矩阵 $\boldsymbol X$ 就是一个 $m \times (n + 1)$ 维矩阵，而 $\boldsymbol \theta$ 是 $n+1$ 维列向量，相乘即可拟合 $\boldsymbol y$

该模型的均方误差函数为

$J(\theta_1, \theta_2\cdots\theta_i) = \frac{1}{2m} \sum_\limits{i=1}^{m} (f(x_i) - y_i)^2$

设向量(或者矩阵) $\boldsymbol x = \{x_1, x_2,\cdots, x_n\}$ ，则 $\boldsymbol x$ 模(行列式）的平方 $|x|^2 = \sum\limits_1^n x_i^2$ ，也可以写为

$\boldsymbol x^T \boldsymbol x$

于是误差函数也可以写为向量形式，即

$J(\boldsymbol \theta) = |(\boldsymbol y - \boldsymbol \theta^T \boldsymbol X)|^2=(\boldsymbol y - \boldsymbol \theta^T \boldsymbol X)^T(\boldsymbol y - \boldsymbol \theta^T \boldsymbol X)$

梯度下降法原理

想要模型尽可能地更优，就要尽可能地使得均方误差更小，我们的误差函数是一个凸函数，对于凸函数我们可以采用梯度下降法求出最值的数值解

梯度下降法（英语：Gradient descent）是一个一阶数值优化算法（我们熟悉的二分法也是此类算法的一种）要使用梯度下降法找到一个函数的局部极小值，必须向函数上当前点对应梯度（或者是近似梯度）的反方向的规定步长距离点进行迭代搜索。(如果相反地向梯度正方向迭代进行搜索，则会接近函数的局部极大值点；这个过程则被称为梯度上升法)

直观理解，假设你迷失在山上的浓雾之中，你能感觉到的只有你脚下路面的坡度。快速到达山脚的一个策略就是沿着最陡的方向下坡。这就是梯度下降的做法

以最简单的一元函数 $y = f(x)$ 为例，我们需要有一个初始估计值 $x_0$ (一般设为 $0$ ，或者是一个随机值), 以及每一步的步长（也称作学习率） $\alpha$ ，每一次”下山“即为一次迭代，通过不断迭代的方式动态更新 $x$ 的取值，直至收敛，写成递推式即

$x_{n + 1} = x_n - \alpha_n \nabla f(x)$

用图像直观表示，即

梯度下降法图解

梯度下降法的基本步骤如下：

确定定参数的初始值，计算损失函数的偏导数
将参数代入偏导数计算出梯度。若梯度为 0（若收敛），结束
用步长乘以梯度，并对参数进行更新
重复 2-3

回到我们的代价函数

$J(\boldsymbol \theta) = |(\boldsymbol y - \boldsymbol \theta \boldsymbol X)|^2=(\boldsymbol y - \boldsymbol \theta \boldsymbol X)^T(\boldsymbol y - \boldsymbol \theta \boldsymbol X)$

对其求偏导(此处即为求梯度，因为是对向量求导)

$\frac{\partial J(\boldsymbol\theta)}{\partial\boldsymbol\theta} = 2\boldsymbol X^T( \boldsymbol X \boldsymbol \theta - \boldsymbol y)$

故更新参数的操作为（此处等号代表赋值）,由于学习率 $\alpha$ 是我们人为设定的，所以这个2不要也罢

$\theta_i = \theta_i - \alpha \frac{\partial J(\theta)}{\theta_i} = \theta_i - \alpha \boldsymbol X^T( \boldsymbol X \boldsymbol \theta - \boldsymbol y)$

梯度下降优缺点分析

我们再看下这个图

梯度下降法图解

理想的梯度下降就应该如此，如同一个小球，很快就滑落到谷底，

如果是多元函数，如

[图片上传失败...(image-e01a90-1611658317073)].png)

也能通过梯度下降法到达最小值，如图所示

多元函数梯度下降

可事实上我们的代价函数并非都如此简单，图形都像一个漂亮的“碗”，它可能像高原，像洞等等不规则的地形，则梯度下降可能会导致比较大的时间复杂度

学习率 $\alpha$ 的选取问题

学习率 $\alpha$ 是一个比较关键的参数，如果过小，会导致较大的时间复杂度，效率低下，如图所示

6238042-26ab515295e610dd.gif

如果过大，可能会导致越过极值点，从而无法收敛，如图所示~~(反复横跳！)~~

640 (1).gif

选择合适的学习率是一门手艺活，我们通常的操作是绘制 $f(x)$ 与迭代次数的图像，如

640 (2).png

如果过大或者过小，一般采用调整学习率数量级的方式进行调整

特征缩放法

线性回归的成本函数虽然是碗状的，可以使用梯度下降，但是如果如果不同特征的尺寸差别巨大，那么这个“碗”将会变成一个非常细长的碗，导致难以收敛，效率低下

细长的碗

于是我们有必要对数据进行一定的预处理，使得它们尽可能地位于同一个数量级，实际操作中，我们一般将其尽可能接近0，或者处于 $[-1, 1]$ 之间，这样的处理技巧我们称为特征缩放法

参考Python代码与详细注释

import numpy as np
import matplotlib.pyplot as plt


class gradientDecent(object):
    def __init__(self, X, y, trainingTimes=1000, alpha=0.000001):
        """
        初始化类
        """
        self.y = y
        self.trainingTimes = trainingTimes
        self.alpha = alpha
        self.shape = X.shape  # shape函数返回一个储存维数的矩阵
        self.m = self.shape[0]
        self.nPlus = self.shape[1] + 1  # shape[0],shape[1]表示行数和列数，我们增广了一列1，所以要加1
        self.ones = np.ones((self.m, 1))
        self.X = np.concatenate((X, self.ones), axis=1)  # 使用concatenate将数据集与1进行增广
        self.theta = np.random.randn(self.nPlus, 1) #注意维数为n + 1
        self.lossList = [] #用列表存储loss

    def getRes(self):
        """
        计算残差，res = (X theta - y),残差在后面的计算经常用到
        """
        return np.matmul(self.X, self.theta) - self.y

    def calGradient(self):
        """
        计算梯度，梯度计算公式为 X^T * (X*theta-Y).
        """
        res = self.getRes()
        return np.matmul(self.X.T, res)

    def updatingTheta(self):
        """
        对theta进行迭代
        """
        for i in range(self.trainingTimes):
            a = self.calGradient()
            self.theta -= self.alpha * a
            self.loss()
        return self.theta

    def loss(self):
        """
        loss函数计算公式：J(theta) =(X*theta-Y)^T * (X*theta-Y)
        """
        # loss = np.matmul((self.getRes()).T, self.getRes())
        # self.lossList.append(loss)
        res = np.matmul(self.X, self.theta) - self.y
        loss = np.matmul(res.T, res)
        self.lossList.append(int(loss))
        return loss

def createData():
    """
    对一个线性函数进行扰动产生散点图进行拟合
    """
    X = 10 * np.random.rand(1000, 1)
    theta = np.array([[5]])
    y = np.matmul(X, theta) + 2
    salt = np.random.randn(1000, 1) #salt表示扰动，randn能让产生的随机数呈正态分布
    y = y.reshape((-1, 1)) + salt #reshape用于特征缩放
    return X, y


def main():
    X, y = createData()
    print(X, y)
    plt.scatter(X, y)
    gra = gradientDecent(X, y)
    thetaFinal = gra.updatingTheta()
    yPre = np.matmul(gra.X, thetaFinal)
    plt.plot(X, yPre, color='r')
    plt.show()
    plt.close()
    
    x = [i for i in range(1000)]
    plt.plot(x, gra.lossList)
    plt.show()
    plt.close()
if __name__ == '__main__':
    main()

机器学习（三）—— 梯度下降法