基本形式

给定d个特征描述的示例$x=(x_1, x_2, \cdots, x_d)$，其中$x_i$是$x$在第$i$个特征上的取值，线性模型是试图学得一个通过属性的线性组合来进行预测的函数，即

$\begin{align*} f(x) &= w_1x_1 + w_2x_2 + \cdots + w_dx_d + b \\ &= (w_1, w_2, \cdots , w_d) \begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_d \end{pmatrix} + b \\ &= w x + b \end{align*}$

在线性模型中$w$直观表达了个属性在预测中的重要性，因此线性模型有很好的可解释性。

线性回归

给定数据集$D = {(x_1,y_1),(x_2,y_2), \cdots, (x_m,y_m)}$，其中$x_1$为d个特征描述的d维向量。线性回归试图学得

$f(x_i) = w x_i + b, 使得f(x_i)尽可能接近y_i$

那么如何衡量尽可能接近呢？均方误差是回归任务重最常用的性能度量，因此我们可试图让均方误差最小化，即

$\begin{align*} (w^*, b^*) &= argmin_{(w,b)} \sum_{i = 1}^{m} (f(x_i) - y_i)^2 \\ &= argmin_{(w,b)} \sum_{i = 1}^{m} (wx_i + b - y_i)^2 \end{align*}$

$(w^*,b^*)$表示$w$和$b$的解。基于均方误差最小化来进行模型求解的方法称为“最小二乘法”，在线性回归中，最小二乘法就是试图找到一条直线，使所有样本到直线上的欧式距离之和最小。

单特征求解

对于只有一个特征的线性回归模型的最小二乘法的解方法为：

令

$E_{(w,b)} = \sum_{i=1}^{m}(wx_i + b - y_i)^2$

分别对w和b求偏导

$\begin{align*} \frac{\partial E_(w,b)}{\partial w} &= 2\sum_{i=1}^{m}x_i(wx_i + b - y_i) \\ &= 2[w\sum_{i=1}^{m}x_i^2 - \sum_{i=1}^{m}(y_i - b)x_i] \tag{1} \end{align*}$ $\begin{align*} \frac{\partial E_{(w,b)}}{\partial b} &= 2\sum_{i=1}^{m}(wx_i + b - y_i) \\ &= 2[mb - \sum_{i=1}^{m}(y-wx_i)] \tag{2} \end{align*}$

令偏导数为0 可解得$w$和$b$为

$w = \frac{\sum_{i=1}^{m}y_i(x_i - \overline x)}{\sum_{i=1}^{m}x_i^2 - \frac{1}{m}(\sum_{i=1}^{m}x_i)^2} \tag{3}$ $b = \frac{1}{m} \sum_{i=1}^{m}(y_i - wx_i) \tag{4}$

式(4)可由式(2)等于0直接得出，式(3)可有式(2)和式(4)联立推出。其中$\overline x = \frac{1}{m} \sum_{i=1}^{m}x_i$为$x$的均值。

多元线性回归

上面对只有一个特征描述的数据集如何使用最小二乘法求解线性回归问题进行了说明，然而实际的问题更一般的情况是有多个特征标记的数据。这种称为多元线性回归。

为了便于讨论多元线性回归中$w$和$x$都为向量的情况，我们将$b$吸收进入$w$，即令$\hat w = (w;b)$，$\hat w$是一个$(d+1) \times 1$的矩阵。把数据集$D={(xi, y_i)}{i=1}^{m}$(注意$x_i$为向量，$y_i$为标量)表示为一个$m \times (d + 1)$大小的矩阵$X$，其中每行对应一个示例，每行的前d个元素对应一个示例的d个特征取值，最后一个元素恒置为1。并且把所有示例的最后结果表示为一个$m \times 1$的矩阵$Y$

即：

$\hat w = (w_1, w_2, \cdots, w_d, b)^T$ $X = \begin{pmatrix} x_{11} & x_{12} & \cdots & x_{1d} & 1 \\ x_{21} & x_{22} & \cdots & x_{2d} & 1 \\ \vdots & \vdots & & \vdots & \vdots \\ x_{m1} & m_{m2} & \cdots & x_{md} & 1 \end{pmatrix}$ $Y = (y_1, y_2, \cdots, y_m)^T$

则

$X\hat w = \begin{pmatrix} x_{11} & x_{12} & \cdots & x_{1d} & 1 \\ x_{21} & x_{22} & \cdots & x_{2d} & 1 \\ \vdots & \vdots & & \vdots & \vdots \\ x_{m1} & m_{m2} & \cdots & x_{md} & 1 \end{pmatrix} \begin{pmatrix} w_1 \\ w_2 \\ \vdots \\ w_d \\ b \end{pmatrix} = Y$

则我们的目标是

$argmin_{\hat w}(Y - X\hat w)^T(Y-X\hat w)$

$Y-X \hat w$为一个$m \times 1$的矩阵。

同理为了求出$\hat w$，可以对$\hat w$求导并令其等于0，注意这里是标量对向量求导，具体标量如何对向量求导的可以看我的另一篇博客。

令$E_{\hat w} = (Y - X\hat w)^T(Y - X\hat w)$，对$\hat w$求导得到：

$\begin{align*} dE &= d(Y - X\hat w)^T·(Y - X\hat w) + (Y - X \hat w)^T d(Y - X\hat w) \\ &= [d(Y - X\hat w)]^T(Y - X\hat w) + (Y - X \hat w)^TdY - (Y - X\hat w)^Td(X\hat w) \\ &= [(dY)^T - d(X\hat w)]^T(Y - X\hat w) - (Y - X\hat w)^T(dX · \hat w + Xd\hat w) \\ &= -(dX · \hat w + Xd\hat w)^T(Y - X\hat w) - (Y - X\hat w)^T(Xd\hat w) \\ &= -(Xd\hat w)^T(Y - X\hat w) - (Y - X\hat w)^T Xd\hat w \\ \\ dE = tr(E) &= tr[-(Xd\hat w)^T(Y - X\hat w)] - tr[(Y - X\hat w)^T Xd\hat w] \\ &= tr[-(Y - X\hat w)^T Xd\hat w] - tr[(Y - X\hat w)^T Xd\hat w] \\ &= tr[-2(Y - X\hat w)^T Xd\hat w] \\ &= tr[2(X\hat w - Y)X d\hat w] \\ \\ 则\frac{\partial E}{\partial \hat w} &= 2(X\hat w - Y)X \tag{5} \end{align*}$

(其中$dX$、$dY = 0$)

令式(5)等于0可得：

$\hat w^* = (X^TX)^{-1} X^T Y$

最后得到的线性回归模型为：

$f(x) = x (X^T X)^{-1} X^T Y$

这里求解模型的方法其实就是标准方程法。

对于线性规划问题，另外的一种解法就是梯度下降。

一个小问题：若$X^TX$不可逆

如果出现了$X^TX$不可逆的情况，可能是一下问题导致的：

1、选用的特征有冗余的特征，即一个特征可以同其他几个特征线性表示

2、用于训练的数据的数量小于选用的特征数量

如果仍然还是不可逆，那么可以对矩阵求伪逆，事实上在编程时大多数矩阵操作运算的库都提供了求矩阵伪逆的函数。

或者直接使用求解线性方程的方法，求出多个$\hat w$，他们都能使均方误差最小化，选择哪一个作为最后的输出将由学习算法的归纳偏好决定，常见的做法是引入正则化。

对比一下梯度下降法和标准方程法

梯度下降法	标准方程法
需要选定学习率$\alpha$，可能需要多次运行训练程序才能确定最后的$\alpha$	不需要确定学习率
需要多次迭代才能找到最优解	不需要迭代
梯度下降法在有很多特征时也能很好的运行，即使对于百万级的特征数也可以使用梯度下降法	在特征数量过多时，存储矩阵需要的内存需要很大，并且计算矩阵的逆矩阵会很慢。`求解矩阵的逆的时间复杂度大致为`$O(n^3)$，其中n为方阵的阶数。

综上所述，当n比较小时，可以考虑使用标准方程法，当n很大时，使用梯度下降法会比较好