【机器学习】（2）：梯度下降算法

    上一章中我们简单介绍了机器学习的大概情况，今天我们开始循序渐进地学习机器学习中相关的算法。在接触经典算法之前，我们先来了解下“梯度下降”算法。
一、算法背景
    作为一个算法演示的背景，我们还是采用上一章中提到的房屋价格和房屋大小的关系问题，不同大小的房屋对应不同的房价，我们要通过分析已有的数据样本，来预 测一个新样本的房价。这里其实是监督式学习中回归问题的简单应用，如果所有的特性因变量都是一次的关系，那么就称之为一个线性回归问题。下面就是我们解决 问题的基本思路：

    首先从训练集中使用学习算法，得到一个关于问题的假设（实质是H(X)=Y的映射），然后选取一个新的房屋，由其大小预测其价格。解决这个问题还需要规定一些符号便于后面的说明，如：
1. M：样本集，表示所有的训练集；
2. X：输入变量，也叫做feature，这个例子里就是房屋大小；
3. Y：输出变量，也叫做targeted variable，这个例子里就是房屋价格；
4. (X,Y)：表示一个训练样本实例；
5. 第i个样本实例：；

二、梯度下降
    对于上面房屋价格和房屋大小的这个例子，如果我们仅仅考虑线性关系，那么Y应当都是X的线性关系。作为演示的例子，我们不妨设房屋大小、房间数量是房屋价 格的两个线性因变量，那么我们的假设H(X)其实可以写作关于X的函数，为了方便，我们将后面所用到的公式和结果一并写在下面：

（1）式中表示的是当考虑房屋大小和房间数量两个因变量时的线性函数，其中X0的值为1，X1表示房屋大小，X2表示房间数量；
（2）式中的J函数，就是我们的目标函数，即如果存在一个函数可以最好的拟合现有的训练数据集M，那么所有样本在该函数上的方差一定最小，前面乘以1/2是为了后面运算化简的方便，不必细究；
（3）式就是我们所说的梯度下降算法的更新公式，将现有训练集的所有样本考虑在内，那么变量成为了两个系数，因此我们不断变化系数以寻求使得H函数达到最小值的值，这里的是一个常变量，表示的是每次下降的步长，如果该值过小，导致算法收敛时间太长，如果该值过大，则有可能会越过最小值点；
（4）式是仅仅考虑只有一个样本的时候得到的关于梯度下降的公式；
（5）式是考虑有m个样本的时候的梯度下降公式；
（6）式是随机梯度下降公式；
    注意！梯度下降的思想其实很简单，如果将所有的样本值绘成等高线图，那么好比一个人站在其中一点，每当要迈步的时候都要考虑哪个方向迈一步可以最快下山。这里其选择的最快下山方向其实是该点的偏导数。具体如图：


    同理，我们也可以看等高线图：

    从上面的（5）式中我们可以看出，每次更新一次系数的时候，都需要遍历所有的样本集合进行运算，因此称为“批梯度算法”，但是如果遇到非常大的样本集合， 这样无疑是十分低效的。因此我们又有了“随机梯度算法”，其思想就是每次只使用一个样本来更新所有的参数值，但是需要更新m*n次（m是样本大小，n是因 变量个数），伪代码就是：
Repeat {
    For j = 1 to m {
        (6)式  (for all i)
    }
}
    随机梯度算法的收敛速度要比批梯度要快，但是最后收敛的未必有批梯度那么准确，也许会围绕最小值点来回摆动。由于梯度算法的核心是减去了偏导数，因此梯度算法一定会有收敛值，而且对于线性问题来说，所得的局部最小值往往就是全局最小值。