梯度下降

引子

好啦，今天开始机器学习的第一个算法——梯度下降。

有关梯度下降这个东西，其实在数学课程里反复提到好多次，但很多人仍然很懵逼，不明白这货到底有什么实用价值？

我们当时举的例子是如何下山对吧？怎么着？真被困在山顶上时，还要掏出一堆草稿纸验算一下最优路径？脑子进水了吧？

理论终究是理论，如果不把它变成实实在在的东西，那它就是垃圾。

幸运的是，今天我们真的可以把它实实在在的捏在手里了，就像是捏着钞票一样的真实，因为我们可以把梯度下降法写成程序！酷吧？

如何下山

我们再简单的看一下这张图：

还是假设你在山顶上，这时准备下山了。

假设你所在的起始位置是(0,0)点，然后下一步怎么走？

你茫然四顾，把整个山脉都瞅了一圈（遍历），找到一个绝佳位置（梯度），迈出了一小步（学习率），然后停下来（更新参数），再次茫然四顾，把整个山脉又瞅了一圈，再次找到一个绝佳位置，又迈出了一小步，如此循环下去。。。。

按照这个方法，最终你顺利的到达山底，这就是梯度下降法。

这个下山法，需注意这么几个问题：

1）每往下走一步，都要环顾一圈。

为啥一定要环顾一圈呢？

因为你每走一步，都要找到全局中最好的那个位置，这样才能保证每一步都是最好的。

那怎么找到最好的位置呢？就是沿着梯度的方向迈出一个梯度的距离。

2）迈出的步子。

那我们该迈多大的步子呢？

太大了容易扯着蛋，太小了走的太慢。这是个变数，需要自己来把握。这里增加一个学习率的参数，可以帮你来调整步子大小。

好啦，下山的例子就介绍到这，下面就看真正的梯度下降啦~~

寻找拟合方程

吴恩达教授的课程中举了房屋价格的例子，我们来看一下。

从这个表格中，我们可以得到什么信息呢？

可以看出，房屋的价格（y），是跟着房屋的面积、卧室的数量等特征（x）走的。

假如这些数据，都可以正好落在某个线性方程上，那它一定是长成酱紫的：

其中θ是未知的参数，x1和x2分别代表房屋面积和卧室数量两个特征。

这个线性方程我们可以做一下调整：

我们把y用字母h替换一下，别问为什么，这是有历史原因的（吴恩达教授原话），当然啦，特征值可以是多个：

这样我们就得到了h(θ)这样一条拟合线性方程。

但是呢，现实中不可能有这么一条线，正好可以拟合所有样本数据点的，只能是最大限度的拟合而已，如图：

那么下面我们的任务就是找到这个h(θ)了。

如果我们真的找到了，那么就等于你找到了房屋定价的秘密，你可以利用这条线性方程h(θ)来预测房屋价格啦，实在太酷了！

如何找到h(θ)？

实际上就是问：如何计算出所有的θ参数？

降低误差

如何计算h(θ)？在此之前你先回答这个问题：

h(θ)如何最大限度的拟合所有的样本点？

要想达到这个目的，就需要将这条直线的误差降到最小才行。

那么如何量化这个误差呢？

这就需要用到我们之前学过的方差的概念，不记得的回去翻一下。

我们用大写的J表示这个误差，就是：

其中，

m表示m个样本；

x和y顶头上的括号i表示第几个样本数据；

前面的1/2是为了方便计算加上去的，因为求导的话会出现2，正好可以约掉，看后面就知道了。

下山—梯度下降

经过上面的讨论，我们得到了两个有价值的信息，分别是：

一、拟合方程。

二、误差函数。

然后我们就结合下山的例子，开始做梯度下降。

我们分这么几个步骤来走：

1）设定初始位置。

我们把θ设置为0，作为起始位置，也就是：

2）迈出第一步。

大家还记得如何迈出第一步吗？对了，需要环顾周围，找到一个全局最佳点。

那么这个全局最佳点在哪里呢？当然就是沿梯度方向，下降一个梯度了：

这里的α叫学习率，或者通俗点叫做步长，也就是迈出的步子大小。

:=这个符号表示赋值的意思。开始我们不是已经给θ赋值为0了么，现在迈出了一步，也就是减掉了一个梯度，因此需要重新赋值。

我们把这个导数求一下：

于是我们把这个结果代入上式，就是：

这样我们就得到了迭代赋值公式，第一步就迈出去了。

大家需要注意的是，哪怕是迈第一步，都需要环顾四周，也就是把所有的样本数据都遍历一遍，这样才能计算出误差函数的导数，也就是梯度值，然后再走下一步，如此迭代。

可能有同学会有疑问：这样做，是不是遍历次数太多了啊？效率也很低下。

确实是酱紫的，如果样本数据太大，几千万甚至好几个亿的数据量，很容易就把计算机算挂了，咱们后面再介绍一些优化的方案，这里先暂时不用管。

3）误差的阈值。

当θ迭代过一次之后，h(θ)也就跟着更新了。我们用新h(θ)和旧的h(θ)分别代入误差函数，计算出误差值，然后二者相减取绝对值，看看这个数字有多大？

如果肥肠小，譬如0.0001这样的数字，这说明两次迭代相差的不大，有了收敛的迹象，这就是我们想要的结果；如果相差很大，那就需要继续迭代。

4）重复迭代，直到结果收敛为止。

迭代的结果一定会是收敛的吗？

这个不一定，也可能是发散的。

那如何让结果收敛呢？

这取决于你取的学习率，也就是步长，所以我们需要调参。

程序实现

好了同学们，经过一系列的努力，我们终于可以用程序实现一个梯度下降算法了，是不是很鸡冻呀？

为了让这个例子让大家都能看懂，我把特征只设为2个好啦。代码的注释很详细，相信大家都可以看懂~~

不用迭代？

运行的结果：

梯度下降是一种迭代法，通过迭代更新参数，逐渐收敛得出最终的结果。

那么，如果不用迭代，能否一步到位就得到最优解呢？

这就相当于你下山，你对着地图看了一会，直接找出了全局最优路径，用笔标注好，直接大踏步照着走就行了，而并不是走一步看一步，这就是最小二乘法，我们下次课再详细讲解。

小结

今天我们用代码模拟了一下梯度下降法，其实它的全名叫“批量梯度下降法”，也就是每走一步，都要遍历一遍所有的数据，其性能肯定是比较低下的，但是它确实能保证你下到最低点。

有种办法可以提升它的效率，就是少用一些样本，而不是全部都用，这就需要我们对数据做一些预处理的工作了，也就是数据清洗，只提炼出有用的数据供我们迭代使用，这叫做“迷你批量梯度下降法”。

还有一种极端的办法，就是只用一个样本来反复迭代，这样就等于你逮着一个方向，闷头往下应走，能走到最低点吗？

有可能到，也有可能到不了，这种方法也有个名字，叫随机梯度下降法，也就是随机抽一个样本的意思。