梯度上升算法与最小二乘法的区别

dupuleng 2021-08-21 原文

可参考：http://www.zhihu.com/question/20822481

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

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

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