针对某些线性回归问题，除了梯度下降算法，有一个更好的方法来求出最优解，就是正规方程（Normal Equation）

与梯度下降算法采用求导，然后迭代计算的方法不同，正规方程采用的矩阵的求解，方便快捷，但也有一些弊端。

房价的例子：

$x_0$ 尺寸$x_1$ 房间数$x_2$ 房屋年份$x_3$ 价格$y$
1 2104 5 45 460
1 1416 3 40 232
1 1534 3 30 315
1 852 2 36 178
… … … … …

和之前不同的是，这个在前面加了一列$x_0$，而这一列的值都是1。

下面用矩阵的形式来展现这个数据集：
$$ X=\left[ \begin{matrix} 1 & 2104 & 5 & 45 \\ 1 & 1416 & 3 & 40 \\ 1 & 1534 & 3 & 30 \\ 1 & 852 & 2 & 36 \end{matrix} \right], y=\left[ \begin{matrix} 460 \\ 232 \\ 315 \\ 178 \end{matrix} \right] $$

$X$为$m \times (n+1)$维矩阵，$y$为$m$维向量

正规方程的公式为：
$$ \theta=(X^TX)^{-1}X^Ty $$

$X^T$ 是矩阵 $X$ 的转置，$(X^TX)^{-1}$ 是矩阵 $X^TX$ 的逆矩阵

通过这个公式的到的$\theta$ 会最小化线性回归的代价函数 $J(\theta)$，和梯度下降算法不同的是，正规方程不需要采用特征值缩放。

何时采用正规方程，何时采用梯度下降

这是两种算法之间的差距

梯度下降 正规方程
学习率($\alpha$) 需要选择学习率($\alpha$) 不需要学习率($\alpha$)
迭代 需要迭代很多次 不需要迭代
复杂度 $O(kn^2)$ $O(n^3)$，因为需要计算$(X^TX)^{-1}$
多特征值 当特征值n非常大时，性能好 当特征值n非常大时，性能差

正规方程不需要选择学习率($\alpha$)，也不要迭代很多次，这点在计算的繁琐程度上是优于梯度下降的。
正规方程的劣势是在计算 $(X^TX)^{-1}$ 这个公式上面，$X$是一个$m \times (n+1)$的矩阵，那么$X^TX$则为$m$维的方阵，这个过程的复杂度相当于$O(n^2)$，在计算该矩阵的逆矩阵，就相当于$O(n^3)$的复杂度。当n很大时，正规方程的复杂度就比梯度下降大得多，也就更加耗时。

用此当n较大时，选择梯度下降性能会更好；当n较小时，选择正规方程会更好的计算$\theta$。

在实践中，当n超过10000时，可以考虑选择梯度下降算法。

关于逆矩阵的一些问题

在求解 $(X^TX)$ 的逆矩阵时，可能会遇到该矩阵不可逆，造成这种情况的原因是：

  • 在特征值中有冗余的特征，例如在预测房价中，有一列特征值是以平方英尺为单位计算的房子大小，又有一列是以平方米的单位来计算房子大小，这样两个特征值就是冗余的，两个只要取其中一个就好了；
  • 特征值过多，当特征值大于样本数时，即$m\leq n$。遇到这样的，删掉一个关联不大的特征值，或者使用正则化(regularization)来解决。