机器学习学习笔记--线性回归

Page content

Andrew NG's Machine Learning.

1. 一元线性回归

线性回归问题是监督学习中最基础的算法之一。在统计学中,线性回归是利用称为线性回归方程的最小而成函数对一个或多个自变量和因变量之间关系进行建模的一种回归方式。下面就由浅入深的来了解线性回归算法的建模方式。

1.1 模型表示

以之前的房屋交易问题为例,假设我们的回归问题的训练集(Traning Set)如下表所示:

Size in  $feet^2$ (x) Price($) in 1000's (y)
2104 460
1416 232
1534 315
852 178
... ...

定义如下几个标记来描述这个回归问题:

  • $m$ 代表训练集中实例的数量

  • $x$ 代表特征/输入变量

  • $y$ 代表目标变量/输出变量

  • $\left( x,y \right)$ 代表训练集中的实例

  • $\left(x^{(i)}, y^{(i)} \right)$ 代表第i个观察实例

  • $h$ 代表学习算法的解决方案或函数 也称为假设hypothesis

于是,监督学习算法的工作方式可以表示为如下图所示:

在上图中,我们将训练集(房屋价格表)传给学习算法,学习算法的工作就是,假设一个函数,通常用$h$(hypothesis)来表示,该函数的输入是房屋尺寸大小(设为$x$),$h$会跟根据$x$的值来得出$y$值,$y$值对应的是房屋的价格,

要解决房价预测的问题,我们该如何选择$h$?最简单的表达方式是:

\[ h_\theta \left(x \right) = \theta_{0} + \theta_{1}x \]

因为只含有一个特征/输入变量,因此这种问题被称为单变量线性回归问题

1.2 代价函数(Cost Function)

针对房价预测问题,我们选择了hypothesis函数为:

\[ h_\theta \left(x \right) = \theta_{0} + \theta_{1}x \]

于是,引出了一个问题,我们如何选择$\theta_0$和$\theta1$使得 $h\theta \left(x \right)$能够更加接近真实值$y$。我们选择的参数决定了我们得到的直线相对于我们的训练集的准确程度,模型所预测的值与训练集中是聚酯之间的差距就是建模误差(modeling error)。如下图所示,蓝线部分就是建模误差。

在线性回归问题中,我们的目标是选择出可以使得建模误差的平方和能够最小的模型参数,即使得代价函数:

\[ J\left( \theta_0, \theta_1 \right) = \frac{1}{2m}\sum\limits_{i=1}^m \left(h_{\theta}(x^{(i)})-y^{(i)} \right)^{2} \]

达到最小。针对课后习题中的样本集,我们来直观的感受一下,$J\left( \theta_0, \theta_1 \right)$在$\theta_0$和$\theta_1$变化的过程中,代价函数得到的值。

如果将生成的3D图映射成一维的等高线图,就能更直观的理解代价函数。

当然,我们不可能让计算机把这写点的值都算出来,从而找到一个特定的$\theta_0$和$\theta_1$,使得代价函数达到最小。我们所需要的是找到一种有效的算法,能够自动地找出这些使代价函数J取最小值时的参数$\theta_0$和$\theta_1$。

1.3 梯度下降

梯度下降是一个用来求函数最小值的算法,该算法的思路如下:

  1. 随机选取一组$\theta_0$和$\theta_1$

  2. 重复下面的运算,直到收敛

\[ \theta_{j} := \theta_{j} - \alpha \frac\partial{\partial\theta_{j}}J\left(\theta_0,\theta_1\right) \qquad \left(for\quad j = 0\quad and\quad j = 1\right) \]

其中,$\alpha$为学习率,它决定了我们沿着能让代价函数下降程度最大的方向向下的步长有多大。梯度下降法不能找到全局最小值,而只能找到局部最优解,下图能更直观的理解这句话。

如上图所示,梯度下降可以理解为,我们站在一座山头,需要尽快的下山,那么我们要做的就是,环顾四周,找到最佳的下山方向,然后迈出一步,接下来重复上面的动作,直到下山。这么一来,我们站在哪个山头将影响着我们下山的最终位置,即我们选择的起始值不同,将影响最终找到的局部最小值。

接下来,我们换一种思路来理解对梯度下降,如下图所示:

对于$\theta_1$来说,\(J\left(\theta_1\right)\)是一个二次函数,对$J\left(\theta_1\right)$求导代表求曲线的切线,找到切线方向就是下降最快的方向,图中从红色点开始,一步一步的更新$\theta_1$,最终达到$J\left(\theta_1\right)$的局部最小值。

在梯度下降法中,当我们越接近局部最低点时,梯度下降法会自动采取更小的幅度,这是因为局部最低点的倒数会自动变得越来越小。

接下来,我没来推导一下代价函数的求导。

\[ \begin{eqnarray} \theta_0 & = & \theta_0 - \alpha\frac\partial{\partial\theta_0}\frac{1}{2m}\sum\limits_{i=1}^m \left(h_{\theta}(x^{(i)})-y^{(i)} \right)^{2} \\ & = & \theta_0 - \alpha\frac{1}{m}\sum\limits_{i=1}^m\left(h_{\theta}(x^{(i)})-y^{(i)}\right) \end{eqnarray} \]

\[ \begin{eqnarray} \theta_1 & = & \theta_1 - \alpha\frac\partial{\partial\theta_1}\frac{1}{2m}\sum\limits_{i=1}^m \left(h_{\theta}(x^{(i)})-y^{(i)} \right)^{2} \\ & = & \theta_1 - \alpha\frac{1}{m}\sum\limits_{i=1}^m\left(\left(h_{\theta}(x^{(i)})-y^{(i)}\right)x^{(i)} \right) \end{eqnarray} \]

每次计算$\theta_0$和$theta_1$时,我们都需要对所有样本进行求和运算,因此这个算法也被叫做批量梯度下降算法。在下一节中,我们会应用线性代数的知识来简化这个运算。

2 线性代数基础

2.1 矩阵向量

矩阵维数即行数x列数,如$mn$矩阵代表该矩阵有$m$行,$n$列。如下,为一个23的矩阵:

\[ \left[\begin{matrix} 1 & 2 & 5 \\ 3 & 10 & 20 \end{matrix} \right] \]

矩阵元素即矩阵项$A_{ij}$为第$i$行,第$j$列元素,如$A_{12} = 2$,一般矩阵的元素是从1开始,而不是从0开始。

2.2 矩阵加、减运算

矩阵加法和减法要求两个矩阵的行数和列数必须相同。两个矩阵相加等于矩阵中各个对应位置的矩阵项相加得到的矩阵。即

\[ A \pm B= \left[A_{ij} \pm B_{ij}\right] \]

矩阵加、减运算满足交换律和结合律,如下:

\[ A+B= B+A\\ A+B+C = A+(B+C) \]

2.3 矩阵标量乘法

数$\lambda$乘以矩阵$A$,等于数$\lambda$乘以矩阵$A$的每一个元素,记为$\lambda A$或者$A\lambda$。特别的,$-A$成为$A$矩阵的负矩阵。

标量乘法满足分配律和结合律。

\[ \lambda \mu A = \lambda (\mu A) \\ \lambda (A+B) = \lambda A + \lambda B \]

2.4 矩阵向量乘法

设存在

\[A = ( a _{ij} ) _{m*s} \\ B=(b _{ij}) _{s*n}\]

,则$A$和$B$的乘积$C=AB$是这样一个矩阵:

  1. 行数与左矩阵即$A$相同,列数与右矩阵即$B$相同,即$C=(C_{ij})_{m*n}$
  2. $C$的第$i$行第$j$列元素等于$A$的第$i$行元素和$B$的第$j$列元素对应相乘,然后再取乘积之和。

矩阵乘法运算必须要满足左矩阵的列数和右矩阵的行数相等。

单位矩阵:$n$阶单位矩阵表示一个$n*n$的矩阵,其主对角线元素均为1,其他元素为0。如2阶单位矩阵:

\[ E_2 = \left[\begin{matrix} 1 & 0\\0 & 1 \end{matrix}\right] \]

对于单位矩阵,满足矩阵乘法交换律$EA=AE$,非单位矩阵不满足乘法交换律。矩阵乘法满足以下定律,即:

  • 结合律:$A×B×C=A×(B×C)$
  • 分配律:$A×(B \pm C) = A×B \pm A×C$ (左分配律) $(B \pm C)×A = B×A \pm C×A$ (右分配律)

  • $(\lambda A)B = \lambda (AB) = A (\lambda B)$

2.5 矩阵转置

将矩阵$A$的行换成同序号的列所得到的新矩阵称为矩阵$A$的转置矩阵,记作$A{‘}$或$A{T}$,即:

\[ A _{ij} = \left(A^{T}\right)_{ji} \]

矩阵转置满足一下性质,假设运算都是可行的。

  • $(A ^{T}) ^{T} = A$
  • $(A+B) ^{T} = A^{T} + B^{T}$
  • $(AB) ^T = B ^TA ^T$
  • $(\lambda A)^T = \lambda A^T$, $\lambda$是常数

2.6 逆矩阵

对于矩阵$A$,如果存在一个矩阵$B$,满足$AB = BA =E$, 则称$B$是$A$的逆矩阵,记为$A^{-1}$。逆矩阵满足如下性质:

  • $ (A ^{-1}) ^{-1} = A $
  • $ (I ^{-1}) ^{-1} = I $
  • $(M ^{T}) ^{-1} = (M ^{-1}) ^{T}$
  • $(AB) ^{-1} = B ^{-1}A ^{-1}$

求逆矩阵的方法有如下两种,这里不展开介绍,可以参考如下链接矩阵求逆

  • 伴随矩阵法
  • 矩阵初等变换法

3. 多元线性回归

3.1 模型建立

以上我们讨论了一元线性回归问题,但真实情况是,房价的决定因素并不只有房屋面积,还有房屋楼层,主卧面积等等,于是就构成了一个多线线性回归问题。训练集如下:

Size Number of BedRooms Number of floors Age of home(years) Price
2104 5 1 45 460
1416 3 2 40 232
1534 3 2 40 315
... ... ... ... ...

这样一来,我们引入一系列新的定义:

  • $n$代表特征的数量

  • ${x^{\left( i \right)}}$代表第 $i$ 个训练实例,是特征矩阵中的第$i$行,是一个向量vector

  • ${x}_{j}^{\left( i \right)}$代表特征矩阵中第 $i$ 行的第 $j$ 个特征,也就是第 $i$ 个训练实例的第 $j$ 个特征。

  • 支持多变量的假设函数$h​$表示为:$h_{\theta}\left( x \right)={\theta_{0}}+{\theta_{1}}{x_{1}}+{\theta_{2}}{x_{2}}+...+{\theta_{n}}{x_{n}}​$,为了使该公式简化,我们假定$x_{0} = 1​$,从而得到$h_{\theta} \left( x \right)={\theta_{0}}{x_{0}}+{\theta_{1}}{x_{1}}+{\theta_{2}}{x_{2}}+...+{\theta_{n}}{x_{n}}​$,用矩阵表示,即$h_{\theta} \left( x \right)={\theta^{T}}X​$

3.2 多元梯度下降

与一元线性回归类似,在多元线性回归中,我们同样用最小二乘法构建了一个代价函数,也就是所有建模误差的平方和,即: \( J\left( {\theta_{0}},{\theta_{1}}...{\theta_{n}} \right)=\frac{1}{2m}\sum\limits_{i=1}^{m}{{{\left( h_{\theta} \left({x}^{\left( i \right)} \right)-{y}^{\left( i \right)} \right)}^{2}}} \) 其中,$h_{\theta}\left( x \right)=\theta^{T}X={\theta_{0}}+{\theta_{1}}{x_{1}}+{\theta_{2}}{x_{2}}+...+{\theta_{n}}{x_{n}}$

用python来计算代价函数代码如下:

def computeCostMulti(X, y, theta):
    """
     Compute cost for linear regression with multiple variables
       J = computeCost(X, y, theta) computes the cost of using theta as the
       parameter for linear regression to fit the data points in X and y
    """
    m = y.size
    temp = np.dot(X , theta)
    return np.sum(np.power(temp -y, 2)) / (2 * m)

这样一来,我们的目标和一元线性回归问题一样,即找出是的代价函数最小的一系列参数。多元线性回归问题的批量梯度下降算法如下:

\[ \theta_j := \theta_j - \alpha \frac\partial{\partial\theta_j} J(\theta_0, \theta_1 ... \theta_n) \\ \]

对上式进行求导运算可得:

\[ \theta_j := \theta_j - \alpha \frac{1}{m}\sum\limits_{i=1}^{m} \left( \left(h_{\theta} \left({x}^{\left( i \right)} \right)-{y}^{\left( i \right)} \right) · {x}_j ^{\left( i \right)} \right) \]

那么多元梯度下降的算法就是同步更新$\theta_j$,直到收敛。下面我们来用矩阵运算来简化这个运算,一步得到同步更新后的$\theta_j$值。

首先,我们在特征矩阵$X$的左边添加一行,如下:

\[ X = \left[\begin{matrix} 1 & x_1^1 & x_1^2 & x_1^3 & x_1^4 \\ 1 & x_2^1 & x_2^2 & x_2^3 & x_2^4 \\ 1 & x_3^1 & x_3^2 & x_3^3 & x_3^4 \\ ... & ...& ...& ...&... \end{matrix}\right] \]

记 $\theta = \left[\begin{matrix} \theta_0 & \theta_1 & \theta_2 & \theta_3 & \theta_4 \end{matrix}\right]$,

\[ Y = \left[\begin{matrix}y^1 \\ y^2 \\ y^3 \\ y^4 \end{matrix}\right] \]

于是$h_{\theta} \left({x}^{\left( i \right)} \right) - y {^\left(i\right)}$可以记为$X·\theta ^T - Y$,然后,$(X·\theta ^T - Y)^T · X$即可得到矩阵$\theta $ 。这里用Python实现如下:

def gradientDescentMulti(X, y, theta, alpha, num_iters):
    """
     Performs gradient descent to learn theta
       theta = gradientDescent(x, y, theta, alpha, num_iters) updates theta by
       taking num_iters gradient steps with learning rate alpha
    """
    # Initialize some useful values
    J_history = []
    m = y.size  # number of training examples

    for i in range(num_iters):
        temp = np.dot(X, theta)
        theta = theta - alpha / m * (np.dot(temp - y, X))
        # Save the cost J in every iteration
        J_history.append(computeCostMulti(X, y, theta))
    
    return theta, J_history

3.3 特征缩放

在多元线性回归问题中,如果我们能保证这些特征都具有相似的尺度,这将使得梯度下降算法更快的收敛。

还是以房价问题为例,假设我们使用两个特征,房屋的尺寸和房间的数量,尺寸的值为02000平方英尺,而房间的数量为05,以两个参数分别为横纵坐标,绘制代价函数等高线图。如下左图所示:

这样的等高线图表现为更长更扁,在梯度下降的时候,需要更多次的迭代才能使结果收敛;而上右图为特征缩放之后的等高线图,这种情况下可以用更少的迭代使得结果收敛。特征缩放有几种方法如下:

  1. 调节比例(Rescaling)

这种方法是将数据缩放到[0,1]或者之间,缩放到什么范围取决于数据的性质。对于这种方法,其公式如下:

\[ x^{'} = \frac {x - x_{min}} {x_{max} - x_{min}} \qquad或\qquad x^{'} = \frac {x - x_{mean}} {x_{max} - x_{min}} \]

  1. 标准化

特征标准化使每个特征有零均值(zero-mean)和单位方差(unit-variance)。这个方法在机器学习中被广泛的使用,例如:SVM、逻辑回归和神经网络。这个方法的公式如下:

\[ x^{'} =\frac {x - \bar x}{\sigma} \]

除了特征缩放外,学习率对梯度下降也有一定的影响。

梯度下降算法收敛所需要的迭代次数根据模型的不同而不同,从算法上来看,每次迭代下降的值受到学习率的影响,如果学习率太小,则达到收敛所需要的迭代次数就非常高;如果学习率太大,每次迭代可能不会减小代价函数,可能会越过局部最低点,导致无法收敛。

特征缩放用python代码实现如下:

import numpy as np 

def featureNormalize(X):
    """
       returns a normalized version of X where
       the mean value of each feature is 0 and the standard deviation
       is 1. This is often a good preprocessing step to do when
       working with learning algorithms.
    """
    mu = np.mean(X, axis=0)
    sigma = np.std(X, axis=0)
    X_norm = (X - mu) / sigma

    return X_norm, mu, sigma

3.4 特征和多项式回归

还是以预测房价为例,现在数据集中提供两个特征,分别为$frontage$临街宽度和$depth$纵向深度,这样一来我们构建的$h _\theta(x)$函数如下图所示:

但是,这种假设函数特征上存在冗余情况,我们完全可以将临街宽度和纵向深度合成一个特征,即房屋面积。因此对此种数据集来说,我们要预先对特征数据进行合并。

\[ Area \ x = frontage * depth \\ h _\theta(x) = \theta _0 + \theta _1x \]

这样一来,降低了梯度下降算法中的计算量,同时使得模型更加合理。

还有一种情况,线性回归可能并不适用于所有数据,有时我们可能需要用曲线来适应我们的数据集。比如一个二次函数或者一个三次函数。如下图所示:

这种情况下,我们可以构建一个新的特征,从而将模型转化为线性回归模型。如:

\[ x _1 = x \\ x _2 = x ^ 2 \\ x _3 = x ^ 3 \\ h _\theta (x) = \theta _0 + \theta _1x _1 + \theta _2 x _2 + \theta _3 x_3 \]

再比如,如上图中虚线所示,才是符合数据集的模型,这样一来我们可以假设$h _\theta(x)$ 如下:

\[ x _1 = x \\ x _2 = x ^ 2 \\ x _3 = \sqrt x \\ h _\theta (x) = \theta _0 + \theta _1x _1 + \theta _2 x _2 + \theta _3 x_3 \]

Important: 如果使用多项式回归,在进行建模前,特征缩放显得非常重要,且必不可少

因此,在拿到数据集的时候,我们需要先观察数据集适合哪种模型,然后通过合并特征以及在已有特征的基础上新建多项式特征使得模型更加合理,然后在进行建模运算。

3.5 正规方程

在前面的小节中,我们都是用梯度下降算法来求代价函数$J(\theta)$的局部最小值,但是对于某些线性回归问题,正规方程可能是更好的解决方法,我们先来推到一下正规方程如何求代价函数的最小值。

\[ J(\theta) =\frac{1}{2m}\sum\limits_{i=1}^{m}{{{\left( h_{\theta} \left({x}^{\left( i \right)} \right)-{y}^{\left( i \right)} \right)}^{2}}} = (H _\theta(X) - Y)^T(H _\theta(X) - Y) \]

其中,参数矩阵为$\theta=(\theta _0 \ \theta _1 \ \theta _2 \ ... \theta _m) ^T$ , $h _\theta(X) = X \theta$, $Y = (y _1\ y _2 \ ...\ y _n)^T$。当$\frac {d}{d _\theta }J(\theta) = 0$时,此时代价函数达到最小值,满足此条件的$\theta$即为所求。

在代价函数求导之前,我们先复习一下矩阵求导的基础知识。

  • 矩阵的迹

\[ tr A = \sum\limits_{i=1}^{n} A _{ii} \]

  • 矩阵的迹简单运算

\[ \begin{eqnarray} a &=& tr \ a \qquad a \in \mathbb{R} \\ tr AB &=& tr BA \\ tr ABC &=& trCBA \end{eqnarray} \]

  • 迹求导运算

\[ \begin{eqnarray} \nabla _A tr AB &=& \nabla _A tr BA = B^T \\ \nabla _{A^T}a &=& (\nabla _A a)^T \\ \nabla _A tr ABA^TC &=& CAB + C^TAB^T \end{eqnarray} \]

接下来,开始推导。

\[ \begin{eqnarray} \nabla _\theta J(\theta) &=& \nabla _\theta(X\theta -Y)^T(X\theta -Y) \\ &=& \nabla _\theta(\theta^TX^T - Y^T)(X\theta -Y) \\ &=& \nabla _\theta(\theta^TX^TX\theta - Y^TX\theta - \theta^TX^TY - Y^TY) \tag{1}\\ &=& \nabla _\theta(\theta^TX^TX\theta - 2\theta^TX^TY) \\ &=& \nabla _\theta tr (\theta^TX^TX\theta - 2\theta^TX^TY) \\ &=& \nabla _\theta tr (\theta\theta^TX^TX) - 2 Y^TX \tag{2} \\ &=& \nabla _\theta tr (\theta I \theta^TX^TX) - 2 Y^TX \\ &=& 2X^T X\theta - 2 Y^TX \\ \end{eqnarray} \]

其中公式$(1)$处,$\theta ^T X ^T Y$是标量,因为$\theta ^ T$是$1 * m$矩阵,$X ^ T$是$m * n$矩阵,$Y$是$n * 1$矩阵,该式结果为$1 * 1$矩阵,即标量。

公式$(2)$处,$\theta\theta ^T X ^T X = \theta I \theta ^T X ^ TX$符合迹求导公式$\nabla _A tr ABA ^T C = CAB + C ^T AB ^T$。

最后我们令$2X ^T X \theta - 2 Y ^T X = 0$, 即得$\theta = (X ^T X) ^ {-1} Y ^T X$,推导完毕。

梯度下降和正规方程求$\theta$的优劣势对比如下:

梯度下降 正规方程
需要选择学习率 不需要选择学习率
需要大量迭代 不需要迭代
复杂率$O(kn^2)$ 复杂率$O(n^3),需要计算逆矩阵$
大量数据集时也能表现很好 大量数据集时运行很慢

在计算正规方程时,$X ^T X$ 不一定可逆,主要原因如下:

  • 冗余特征,其中两个特征密切相关(即他们是线性相关的)。
  • 特征太多(如m<=n), 在这种情况下,删除一些特征或者使用特征化。

因此,在进行正规方程计算时,需要删除一些冗余特征或者当特征太多时,删除一些特征。这点非常重要。

正规方程的python实现如下:

import numpy as np  
def normalEqn(X, y):
    """ Computes the closed-form solution to linear regression
       normalEqn(X,y) computes the closed-form solution to linear
       regression using the normal equations.
    """
    temp =  np.linalg.inv(np.dot(X.T, X))
    temp1 = np.dot(temp, X.T)
    theta = np.dot(temp1, y.T)
    return theta

附赠:

课后习题python代码答案版:coursera-ML-python

参考

矩阵求导术(上)

正规方程求解特征参数的推导过程