正规方程（Normal Equation）

作者: 爱吃鱼的夏侯莲子 | 来源:发表于2020-01-21 21:43 被阅读0次

针对某些线性回归问题，除了梯度下降算法，有一个更好的方法来求出最优解，就是正规方程（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)来解决。

转载自：
https://codeeper.com/2020/01/05/tech/machine_learning/normal_equation.html

网友评论

本文标题：正规方程（Normal Equation）

本文链接：https://www.haomeiwen.com/subject/kwfyzctx.html

延伸阅读

深度阅读

您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

正规方程（Normal Equation）

关于逆矩阵的一些问题

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读