线性回归 梯度下降

梯度下降算法

在开始之前，为了方便解释，首先规定几个符号所代表的意义：

$m$ 训练集中训练样本的数量
$X$ 输入变量 $Y$ 输出变量
$(x,y)$ 训练样本
$(x^i,y^i)$第i个训练样本（i表示一个索引）

监督学习算法的流程

提供训练集>学习算法得到$h$
（假设函数：用于描绘x与y的关系）>预测y 的值  

代价/损失函数（Cost function）

假设函数(Hypothesis function)——$h$ （用来表示某一个数据集可能存在的线性/非线性关系的函数。)

对于线性拟合，其假设函数为：
$$h_{\theta }(x)={\theta }_{1}x+{\theta }_0$$
这其中的$\theta$是假设函数当中的参数。
也可以简化为：
$$h_{\theta }(x)={\theta }_{1}x$$

代价函数，在统计学上称为均方根误差函数。当假设函数中的系数$\theta$取不同的值时，$\frac{1}{2m}$倍假设函数预测值$h_{\theta }(x^{(i)})$和真实值$y^{(i)}$的差的平方的和之间的函数关系表示为代价函数$J$。
$$J({\theta }_0,{\theta }_1)=\frac{1}{2m}\sum _{i=1}^m(h_{\theta }(x^{(i)})-y^{(i)}{)}^2$$

在这里取1/2的原因是便于消除求导之后产生的2倍,同时也可以进一步缩小$\theta$

代价函数在几何上表示为数据集空间内的各点到假设函数的距离的平方的平均值的一半。
要想使得数据能够被假设函数很好地拟合，那么代价函数要尽量地小。当代价函数取到它的最小值即$J({\theta }_1{)}_{min}$时，此时的填入假设函数的$\theta$对数据的拟合程度是最好的。
对于线性的代价函数，假设函数对数据集的拟合程度越高，对应的$({\theta }_0,{\theta }_1)$越接近代价函数图像等高线的中心。
梯度下降算法（Gradient Descent）

梯度

在微积分中，函数$f(x,y)$在$(x_0,y_0)$处是函数值增加最快的方向是梯度（Gradient）的方向，梯度的反方向是函数值减小最快的方向。

梯度的计算公式：
$$▿f{|}_{(x_0,y_0)}=(f_x(x_0,y_0),f_y(x_0,y_0))$$

概述

梯度下降算法是一种求解代价函数最小值的方法，它可以用在多维任意的假设函数当中。
简而言之，梯度下降算法求得$J({\theta }_1{)}_{min}$的主要思路是：

1. 给定${\theta }_0$和${\theta }_1$的初始值，通常令${\theta }_0=0$，${\theta }_1=0$。
2. 不断改变${\theta }_0$和${\theta }_1$的值使得$J({\theta }_0,{\theta }_1)$的值逐渐变小，直到找到$J({\theta }_0,{\theta }_1)$的最小值或者局部最小值。
   如果从一个初始值出发，寻找附近的最小值，重复该过程，得到上图，最后得到的值为局部最优解。

将梯度下降算法类比为爬山，从一个点开始，不断寻找“下山”的路线，最后找到一个“下山”的出口。——吴恩达

类似于标题图

当改变初始值时，会找到另一条“下山”的路径，找到第二个局部最优解（局部最小值）。
对于线性回归的代价函数而言，只存在一个局部最小值。（见代价函数的图像)

表示

梯度下降算法可以表示为：
Repeat untill convergence{
$${\theta }_j:={\theta }_j-\alpha \frac{\partial J({\theta }_0,{\theta }_1)}{\partial {\theta }_j},j=0andj=1$$
}
解释：

1. := 表示赋值运算符

2. α称为学习率，用来控制下降的步长（Padding），即更新的幅度：
   如果α太小，同步更新的速率会非常的慢
   而α过大，同步更新时可能会越过最小值点

3. $\frac{\partial J({\theta }_0,{\theta }_1)}{\partial {\theta }_j}$是代价函数的梯度：
   $$\frac{\partial J({\theta }_0,{\theta }_1)}{\partial {\theta }_0}=\frac{1}{m}\sum _{i=1}^m(h_{\theta }(x^{(i)})-y^{(i)})$$
   $$\frac{\partial J({\theta }_0,{\theta }_1)}{\partial {\theta }_1}=\frac{1}{m}\sum _{i=1}^m(h_{\theta }(x^{(i)})-y^{(i)})x^{(i)}$$

   △在代价函数中（以简化的代价函数为例），无论初始值在最小值点的左侧还是右侧，通过同步更新都能够使该点被“移动（Update)”到最小值，在最小值点，由于导数值为0，最终同步更新停止在了${\theta }_j={\theta }_j$，如前面所说，${\theta }_j$即为极小值点。

同步更新

同步更新（Simulaneous update）是实现梯度下降算法的最有效方式。
$$temp0:{\theta }_0:={\theta }_0-\alpha \frac{\partial J({\theta }_0,{\theta }_1)}{\partial {\theta }_0}$$
$$temp1:{\theta }_1:={\theta }_1-\alpha \frac{\partial J({\theta }_0,{\theta }_1)}{\partial {\theta }_1}$$
$${\theta }_0:=temp0$$
$${\theta }_1:=temp1$$
这个更新方程能够同时更新${\theta }_0$和${\theta }_1$：${\theta }_0$更新为${\theta }_0-J^{\prime }(\theta )$，对${\theta }_1$同理。
更新的方法是计算赋值号右边带入${\theta }_1$和${\theta }_2$的值进行计算，得到的两个值分别储存在temp0和temp1中，从上到下进行赋值。

对于简化的代价函数：
$${\theta }_1：={\theta }_1-\alpha J^{\prime }({\theta }_1)$$
$$\frac{dJ({\theta }_1,{\theta }_0)}{d{\theta }_j}=d(\frac{1}{2m}\Sigma (h_{\theta }(x_i)-y_i){)}^2)$$

将梯度代回代价函数中就得到了Batch梯度下降法的基本形式：
Repeat untill convergence{
$${\theta }_0:={\theta }_0-\alpha \frac{1}{m}\sum _{i=1}^m(h_{\theta }(x^{(i)})-y^{(i)})$$
$${\theta }_1:={\theta }_1-\alpha \frac{1}{m}\sum _{i=1}^m(h_{\theta }(x^{(i)})-y^{(i)})x^{(i)}$$
}

• 批量梯度下降 (Batch Gradient Descent,BGD)梯度下降的每一步中，都用到了所有的训练样本
• 随机梯度下降(Stochastic GradientDescent,SGD)用到一个样本，在每一次计算之后梯度下降的每一步中，便更新参数，而不需要首先将所有的训练集求和 小北量梯度下降
• (Mini-Batch Gradient Descent.MBGD）梯度下降的每一步中，用到了一定批量的训练样本