机器学习（三）——最小均方算法（LMS algorithm）

原文：http://cs229.stanford.edu/notes/cs229-notes1.pdf

我们要选择θ，以便最小化J(θ)。要做到这一点，让我们使用一个搜索算法，它以θ的“初始猜测”开头，而反复变化θ使J(θ)越来越小，直到我们收敛到一个值θ,使得J(θ)最小化。具体来说，让我们考虑梯度下降算法，由一些初始化的θ开始，然后反复执行更新：

(对j=0，…，n.的所有值同时执行此更新)在这里，α被称为学习速率。这是一个反复朝J的下降幅度最大的方向迈出一步的非常自然的算法。

为了实现这一算法，我们必须计算出右手边的偏导数项是什么。首先，如果我们只有一个训练例子(x，y)，这样我们就可以忽略J的定义中的和，我们有：

（此处用到了一些微积分的知识，我们在前面定义了J(θ)=12∑mi=1(hθ(x(i))−y(i))2J(θ)=12∑i=1m(hθ(x(i))−y(i))2 ，此处把 J(θ)J(θ) 代入公式后进行复合函数求导。前面也提到了 h(x)=∑ni=0θixih(x)=∑i=0nθixi ，整体对 θjθj 求导只剩下 xjxj 。如果此处推导看不懂，建议回头去看看上面对数学符号的约定以及复习一下微积分相关内容。）

对于一个训练样本，提供了更新规则：

这个规则叫做 LMS 更新规则（LMS是 “least mean squares”，即最小均方的缩写），也被称为 Widrow-Hoff 学习规则。它有几个属性看起来是十分自然和直观的。例如，每次更新的大小与 误差（error） 项 (y(i)−hθ(x(i)))(y(i)−hθ(x(i)))是成比例的；另外，当训练样本的预测值与真实值 y(i)y(i) 非常接近的情况下，对参数进行更新的幅度就会很小；相比之下，如果我们的预测 hθ(x)hθ(x) 有一个非常大的误差（比如距离 y(i)y(i)非常的远），参数的变化就会变得大得多。

当只有一个训练样本时，我们导出了LMS规则。由两种方法可以针对超过一个样本的训练集对这种方法进行修改。

第一种方法是用以下算法替换它：

读者能够很容易地证明，在上面这个更新规则中求和项的值就是 ∂J(θ)/∂θj∂J(θ)/∂θj（根据对 JJ 的原始定义）。所以这个更新规则实际上就是对原始的成本函数 JJ 进行简单的梯度下降。此方法在每一个更新步骤中检查整个训练集中的所有训练样本，也叫做批量梯度下降法（batch gradient descent）。这里要注意，因为梯度下降法容易被局部最小值影响，而这里我们要解决的这个线性回归的优化问题只有一个全局的最优解，没有其它的局部最优解；因此，梯度下降法应该总是收敛到全局最小值（假设学习速率 αα 没有设置的过大）。可以证明出，这里的 JJ 是一个凸的二次函数。下面是一个样例，表明对一个二次函数使用了梯度下降法来找到最小值。

上图所示的椭圆就是一个二次函数的轮廓图。图中显示了梯度下降的轨迹，初始点位置在(48,30)。图中的画的 xx（用直线相连）标记了梯度下降法所经过的 θθ 的可用值。

对我们之前的房屋数据集进行批量梯度下降来拟合 θθ ，即把房屋价格当作关于房屋面积的一个函数来进行预测，我们得到的结果是 θ0=71.27,θ1=0.1345θ0=71.27,θ1=0.1345 。如果把 hθ(x)hθ(x) 关于 xx （面积）的函数绘制出来，同时标上训练数据的点，我们会得到下面的图像：

如果添加上卧室数量作为输入特征，那么得到的结果就是 θ0=89.60,θ1=0.1392,θ2=−8.738θ0=89.60,θ1=0.1392,θ2=−8.738​.

上面的结果就是使用批量梯度下降法来获得的。此外还有另外一种方法能够替代批量梯度下降法，这种方法效果也不错。如下所示：

在这个算法里，我们对整个训练集进行了循环遍历，每次遇到一个训练样本，只针对那个单一的训练样本的误差的梯度来对参数进行更新。这个算法叫做随机梯度下降法（stochastic gradient descent），或者叫增量梯度下降法（incremental gradient descent）。

批量梯度下降法要在运行第一个步骤之前先对整个训练集进行扫描遍历，当训练集的规模 m 变得很大的时候，因此引起的性能开销就很不划算了；随机梯度下降法就没有这个问题，而是可以立即开始，它对处理到的每个样本都进行单独运算。通常情况下，随机梯度下降法查找到足够 “接近（close）“ 最低值的参数 θθ 的速度要比批量梯度下降法更快一些。（注意，也有可能会一直无法 ”收敛（converge）“ 到最小值，这时候 θθ 会一直在 J(θ)J(θ) 的最小值附近震荡；不过在通常情况下，在最小值附近的这些值也足够接近真实最小值了，足以满足咱们的精度要求，所以也可以被使用。当然更常见的情况是我们事先对数据集已经有了描述，并且有了一个确定的学习率 αα ，然后进行随机梯度下降，同时逐渐让学习速率 αα 随着算法的执行而逐渐趋于0，这样也能保证我们最后得到的参数会收敛到最小值，而不是在最小值范围进行震荡。）由于以上种种原因，通常更推荐使用的都是随机梯度下降法，而不是批量梯度下降法，尤其是在训练用的数据集规模很大的时候。