学习笔记 吴恩达 斯坦福大学公开课 ：机器学习课程-2 监督学习应用：梯度下降

NOTATION:

     m= #training examples训练样本个数
     x= “input”variable/features 输入变量/特征
     y=“output”variable/“target”variable输出变量/目标变量
     (x,y)-training example
     Ith training example=（x^(i)^,y^(i)^）第i个训练样本

线性回归特质：只有一个局部最小值

至此，我们的目标变为如何求解θ，θ决定了我们得到的函数h相对于我们的训练集的准确程度，我们要使得这个误差最小。（这也就是最小化问题）

用代价函数来说明误差，表示为：（我们要使J(θ)取得最小值）。

针对最小化问题，我们采用LMS（最小均方算法），即使得上述表达式取得最小值，这里介绍两种解决方法：梯度下降算法和正规方程组。

1梯度下降算法

用这张图来解释梯度下降算法，想象你正处于图中某一点，想要到达最低点，你的做法就是从这个点开始出发，环顾周围，选择下降幅度最大的方向，迈出一小步，到达一个新的点，以此循环，来达到最低点。这就是梯度下降算法。

当然如果你开始所处不同的位置，就有可能到达的最低点不同，（如下图），这就叫做局部最优。

我们可以看出，如果我们的步长太小，就会要迈很多步才能接近最小值，如果步长过大，就会有可能越过最小值。（实际上不会出现这种情况，下面会作解释）

这里我们以两个参数为例：θ0 ,θ1介绍梯度下降算法。

算法思路:首先将参数初始化，再不断调整参数大小，通过调整使得代价函数可以取得最小值。（或许只是局部最小，这取决于你的设置的参数初始值，不同的初始值可能会获得不同的最小值）

具体做法如下：
1、首先将它们都初始化为0。实际上，它们到底是什么其实并不重要，但通常的选择是将它们初始化为0。
2、不断调整参数大小。（下式中的α在这个例子中代表步长）


说明两点问题：

（1）在梯度下降算法中，我们需要同时更新θ0,θ1 。

（2）如果你的参数已经处于局部最低点，那么梯度下降法更新其实什么都没做（求导为0），它不会改变参数的值，这也正是你想要的，因为它使你的解始终保持在局部最优点，这也解释了为什么即使学习速率 α 保持不变时，梯度下降也可以收敛到局部最低点。

同时，通过分析上式，我们可以知道，梯度下降一步后，新的导数会变小一点点。随着梯度下降法的运行，你移动的幅度会自动变得越来越小，直到最终移动幅度非常小，你会发现已经收敛到局部极小值。

在梯度下降法中，当我们接近局部最低点时，梯度下降法会自动采取更小的幅度。这是因为当我们接近局部最低点时（很显然在局部最低时导数等于零 ），导数值会自动变得越来越小，所以梯度下降将自动采取较小的幅度，这就是梯度下降的做法，所以实际上没有必要再另外减小α。

实际上，用于线性回归的代价函数总是呈现一个弓形的样子，即就是凸函数（如下图）。所以，这个函数没有任何局部最优解，只有一个全局最优解。



在这个式子中，我们可以看出在梯度下降的每一步中我们都用到了所有的训​​练样本，实际上，这样的梯度下降算法叫做“批量梯度下降”。当m特别大时，这种算法很不适用。

这种情况，我们就需要采用另外一种算法 ——”随机梯度下降（增量梯度下降）”

随机梯度算法如下：
在这个式子中，我们可以看出在梯度下降的每一步中我们都用到了所有的训​​练样本，实际上，这样的梯度下降算法叫做“批量梯度下降”。当m特别大时，这种算法很不适用。

这种情况，我们就需要采用另外一种算法 ——”随机梯度下降（增量梯度下降）”

随机梯度算法如下：

正则方程组

首先先介绍一些线性代数中的知识点：
（1）矩阵求导：定义表示m×n的矩阵，那么对该矩阵进行求导可以用下式表示，可以看出求导后的矩阵仍然为 m×n。（A∈）

（2）矩阵的迹（trace）：. 对于一个n阶的方阵（n×n）,它的迹(tr)为对角线元素之和。

矩阵的迹的相关定理：
a. 对于一个实数，它的迹即为它本身 : tr a = a
b. 如果AB是一个方阵，那么 tr AB = tr BA
c. 由此可推导出 trABC = trCAB = trBCA(将末尾循环前移)
d. 假设A 和 B为方阵，a为实数，那么又可以推导出以下的特性：
trA = trAT
tr(A + B) = trA + trB
tr aA = atrA
e. 对迹进行求导，具有以下特性：

定义一个设计矩阵X：

定义目标集合为：



此时，代价函数J（θ）又可以写为：

对J(θ)进行求导可得：（得到红框这一结果，需要用到上面提到的几个定理，此处没有做具体解析）

最后，要使得miniminzes J(θ)，即：

至此，我们通过正规方程组的方法求解了参数θ。

附：

机器学习-随机梯度下降（Stochastic gradient descent）和 批量梯度下降（Batch gradient descent ）

梯度下降（GD）是最小化风险函数、损失函数的一种常用方法，随机梯度下降和批量梯度下降是两种迭代求解思路，下面从公式和实现的角度对两者进行分析，如有哪个方面写的不对，希望网友纠正。

下面的h(x)是要拟合的函数，J(theta)损失函数，theta是参数，要迭代求解的值，theta求解出来了那最终要拟合的函数h(theta)就出来了。其中m是训练集的记录条数，i是参数的个数。

1、批量梯度下降的求解思路如下：

（1）将J(theta)对theta求偏导，得到每个theta对应的的梯度

（2）由于是要最小化风险函数，所以按每个参数theta的梯度负方向，来更新每个theta

（3）从上面公式可以注意到，它得到的是一个全局最优解，但是每迭代一步，都要用到训练集所有的数据，如果m很大，那么可想而知这种方法的迭代速度！！所以，这就引入了另外一种方法，随机梯度下降。

2、随机梯度下降的求解思路如下：

（1）上面的风险函数可以写成如下这种形式，损失函数对应的是训练集中每个样本的粒度，而上面批量梯度下降对应的是所有的训练样本：

（2）每个样本的损失函数，对theta求偏导得到对应梯度，来更新theta

（3）随机梯度下降是通过每个样本来迭代更新一次，如果样本量很大的情况（例如几十万），那么可能只用其中几万条或者几千条的样本，就已经将theta迭代到最优解了，对比上面的批量梯度下降，迭代一次需要用到十几万训练样本，一次迭代不可能最优，如果迭代10次的话就需要遍历训练样本10次。但是，SGD伴随的一个问题是噪音较BGD要多，使得SGD并不是每次迭代都向着整体最优化方向。

3、对于上面的linear regression问题，与批量梯度下降对比，随机梯度下降求解的会是最优解吗？
（1）批量梯度下降—最小化所有训练样本的损失函数，使得最终求解的是全局的最优解，即求解的参数是使得风险函数最小。

（2）随机梯度下降—最小化每条样本的损失函数，虽然不是每次迭代得到的损失函数都向着全局最优方向， 但是大的整体的方向是向全局最优解的，最终的结果往往是在全局最优解附近。

4、梯度下降用来求最优解，哪些问题可以求得全局最优？哪些问题可能局部最优解？
对于上面的linear regression问题，最优化问题对theta的分布是unimodal，即从图形上面看只有一个peak，所以梯度下降最终求得的是全局最优解。然而对于multimodal的问题，因为存在多个peak值，很有可能梯度下降的最终结果是局部最优。