机器学习中最小二乘与梯度下降发的区别

http://www.zhihu.com/question/20822481

知乎用户，非文, 非理

Spirit_Dongdong、Wildog、mt Practices 等人赞同

同意 @张子权的说法, 稍微再补充一下. 看问题估计, 题主可能是在学 machine learning 的东西, 所以才会有此问题. 但正如其他人指出的, 其实两种方法并不太具有可比性. 不过我当时在学的时候也有类似的问题. 当时我的问题是, 最小二乘法的矩阵解法和梯度下降法的区别在哪里? 我估摸着题主可能是想问这个问题, 所以稍微回答一下. 如果我理解错了, 直接忽视下文即可.

其实, 在计算量方面, 两者有很大的不同, 因而在面对给定的问题时, 可以有选择性的根据问题的性质选择两种方法中的一个.
具体来说, 最小二乘法的矩阵公式是 $(A^{T}A)^{-1}A^{T}b$ , 这里的 A 是一个矩阵, b 是一个向量. 如果有离散数据点, $(x_{1}, y_{1}), ..., (x_{n}, y_{n})$ , 而想要拟合的方程又大致形如 $a_{0} + a_{1}x^{1} + a_{2}x^{2}+...+a_{m}x^{m}$ , 那么, A 就是一个 $n imes{}(m+1)$ 的矩阵, 第 i 行的数据点分别是 $[x_i^0, x_i^1, ...,x_i^m]$ , 而 b 则是一个向量, 其值为 $[y_1, ..., y_n]^T$ . 而又已知, 计算一个矩阵的逆是相当耗费时间的, 而且求逆也会存在数值不稳定的情况 (比如对希尔伯特矩阵求逆就几乎是不可能的). 因而这样的计算方法有时不值得提倡.
相比之下, 梯度下降法虽然有一些弊端, 迭代的次数可能也比较高, 但是相对来说计算量并不是特别大. 而且, 在最小二乘法这个问题上, 收敛性有保证. 故在大数据量的时候, 反而是梯度下降法 (其实应该是其他一些更好的迭代方法) 更加值得被使用.

当然, 其实梯度下降法还有别的其他用处, 比如其他找极值问题. 另外, 牛顿法也是一种不错的方法, 迭代收敛速度快于梯度下降法, 只是计算代价也比较高. 题主有兴趣可以查阅相关资料

编辑于 2013-11-16 1 条评论感谢分享收藏 • 没有帮助 • 举报

张子权，Ph.D candidate in mathematical finance

王木木子、冲月、杨炎其等人赞同

相同
1.本质相同：两种方法都是在给定已知数据（independent & dependent variables）的前提下对dependent variables算出出一个一般性的估值函数。然后对给定新数据的dependent variables进行估算。
2.目标相同：都是在已知数据的框架内，使得估算值与实际值的总平方差尽量更小（事实上未必一定要使用平方），估算值与实际值的总平方差的公式为：
$Delta =frac{1}{2} sum_{i=1}^{m}{(f_{eta }(ar{x_{i}} )-y_{i})^{2} }$ 其中 $ar{x_{i} }$ 为第i组数据的independent variable， $y_{i}$ 为第i组数据的dependent variable， $eta$ 为系数向量。

不同
1.实现方法和结果不同：最小二乘法是直接对 $Delta$ 求导找出全局最小，是非迭代法。而梯度下降法是一种迭代法，先给定一个 $eta$ ，然后向 $Delta$ 下降最快的方向调整 $eta$ ，在若干次迭代之后找到局部最小。梯度下降法的缺点是到最小点的时候收敛速度变慢，并且对初始点的选择极为敏感，其改进大多是在这两方面下功夫。

编辑于 2013-03-21 1 条评论

知乎用户，近期实在无所事事

Spirit_Dongdong、知乎用户、王小小赞同

最小二乘法源自线性回归，属于数理统计。在回归中样本量（n）会远大于变量数量（m），最小二乘法目的在于解决n个方程解m个未知数的问题。求极值的过程不是最小二乘法的重点，其重点在于平衡了n个样本得出m个方程进而去解m个未知参数。再说其中的极值，线性回归这一前提决定了其天生就只有一个极值点，即全局最小。

梯度上升（下降）法是一个单纯的求极值方法，用以应对各种古怪的极值求解，属于优化算法。具体的@张子权已经说清楚了。

发布于 2013-03-21 添加评论

江磊，计算数学在读骑车

tidy honey、Ansel Ting、知乎用户等人赞同

最速下降法是一种最优化求极值的方法。与此相关的还有共轭梯度法，牛顿法，拟牛顿法(为解决海森矩阵求逆代价过大的问题)等。
当然很多线性方程组也可以看做一个优化问题，因为只需要优化所谓残差即可，Ax-b。
最小二乘法本质上是一个优化问题，或者说本质上是一个解线性方程组问题，如上面所提到的，当然这个方程组很有可能是超定的，简单说即方程个数远大于未知量个数，这样的方程在线性代数意义下是无解的，但我们可以在一个更广阔的空间中去求解它，比如说将残差（Ax-b）极小化，就是最小二乘。
至于之前答案提到的数值稳定性，收敛性又是另一些问题了。不知道是否说清楚了，欢迎讨论。

编辑于 2013-07-10 添加评论

知乎用户，A follower in the Church of Emacs

杨炎其、方琨、mt Practices 等人赞同

最小二乘法的目标：求误差的最小平方和，对应有两种：线性和非线性。线性最小二乘的解是closed-form即 $x=(A^T A)^{-1}A^Tb$ ，而非线性最小二乘没有closed-form，通常用迭代法求解。

迭代法，即在每一步update未知量逐渐逼近解，可以用于各种各样的问题（包括最小二乘），比如求的不是误差的最小平方和而是最小立方和。