机器学习（三）- normal equation

normal equation

对于线性规划问题来说，除了使用梯度下降，我们还是可以使用normal equation（正规方程），非常简单的函数完成一步求解，不需要反复迭代：

接下来举个例子就一目了然了。

既然有如此简洁的方法，相比之下梯度下降算法一下就落于下风。
当然对于这两种方法，各有各的优势和适用场景。

Gradient Descent	Normal Equation
需要手动设置 α$\alpha$	不需要设置 α$\alpha$
需要反复迭代	不需要迭代
O(kn2)$O(k{n}^2)$	O(n3)$O(n^3)$ 需要计算 (XTX)−1$(X^{T}X{)}^{-1}$
当x$x$很大的时候，速度优于normal equation	当x$x$很大的时候，速度就会变得缓慢

Andrew Ng教授指出，一般当n大于10000才需要考虑摒弃正规方程，在此之前正规方程的用时是少于梯度下降的。
但是对于classification，比如逻辑回归或者更复杂的学习算法，正规方程并不适用，我们还是不得不选择使用梯度下降。

Noninvertibility

对于矩阵 XTX$X^{T}X$ 来说，如果它是奇异矩阵或者退化矩阵，那么它是不可逆的，这将导致无法求得(XTX)−1$(X^{T}X{)}^{-1}$。在这里对应了两种情况：
第一种就是对应了下图中的第一点，选取了冗余的特征然后导致矩阵存在线性相关的列，导致矩阵不满秩。
第二种对应下图中的第二点，对于矩阵 A$A$ 来说，它的row小于column，这样就说明我们选取了太多的特征，导致我们没有足够多的sample去fit这些特征，这就好比我们在求解线性方程时，我们的方程数比我们所要求的未知数还有少，导致我们有无穷多解，同理，sample数小于特征数，我们很难很好的fit这些特征。

对于以上的情况，我们可以先检查是否存在冗余的特征量，如果存在就删除冗余特征，然后再检查我们是否存在过多的特征，如果存在就删除一些或者使用正则化手段。

---

小广告

淘宝choker、耳饰小店 物理禁止
女程序员编码时和编码之余 都需要一些美美的choker、耳饰来装扮自己
男程序员更是需要常备一些来送给自己心仪的人
淘宝小店开店不易 希望有缘人多多支持 (O ^ ~ ^ O)
本号是本人 只是发则小广告 没有被盗 会持续更新深度学习相关博文和一些翻译
感谢大家 不要拉黑我 ⊙﹏⊙|||°