机器学习笔记E2.1--梯度下降与正则化

前面的笔记简单介绍了线性回归的相关内容，针对正规方程法求解参数 $\theta$ 时的两个问题，这里将介绍 梯度下降法（Gradient Descent）和 正则化（regularization） 的相关知识。

梯度下降法
- 梯度下降思想
- 批量梯度下降
- 特征缩放
  - Standardization
  - Min-Max Scaling
- 随机梯度下降（Stochastic Gradient Descent）——未完成
- 批量梯度下降与随机梯度下降的比较——未完成
- 梯度下降法与正规方程法的比较
正则化
- Lasso回归和岭回归

梯度下降法

梯度下降算法是一种通过迭代计算来不断逼近目标函数的局部最优解的优化算法。当目标函数是凸函数（MSE就是一个凸函数）时，局部最优解就是全局最优解，在机器学习中目标函数就是损失函数。

梯度下降思想

梯度下降的思想很简单，假设你一觉醒来发现自己身处某一座山的山顶，你想要下山，采用梯度下降的思想，你首先确定了你要去的方向，找到这个方向上的最佳下山方向，向下走了一小段。然后你休息一下，顺便找到了接下来最佳的下山方向...一直重复执行这个操作，直到你顺利到达山脚。但是可能一开始你并不知道你在山顶的那个地方，可能是左边的红圈，也可能是右边的红圈。很显然，他们到达的山脚是不同的，所以这些“山脚”其实就是一个个 局部最优解（local minimum） ，你选择的方向不同，就会得到不同的局部最优解。而你并不能确定到底哪个才是我们需要的 全局最优解（global minimum） 。

Andrew Ng梯度下降法图解

而对于凸函数，例如线性回归的均方误差损失函数，无论选取如何的初始点，你到达的“山脚”都会到最低的那个地方。即最终都会收敛到相同的最小值。

线性回归的均方误差损失函数MSE

在实际的计算中，“梯度”就是下山的方向，是函数在当前点的偏导数组成的向量。沿着梯度方向函数数值增长最快，沿着梯度相反方向函数下降最快。

批量梯度下降（batch gradient descent）

单变量线性回归的梯度下降算法的公式为：

批量梯度下降

其中， $a$ 是学习率（learning rate），它决定了我们“下山”步子的大小；

$:=$ 为赋值符号，将 $\theta_j$ 减去梯度的结果再赋值给 $\theta_j$ ；

$\frac{\partial}{\partial\theta_j}J(\theta_0,\theta_1)$ 是 $J(\theta)$ 在点 $(\theta_0,\theta_1)$ 处的偏导数， $\frac{\partial}{\partial\theta_j}J(\theta_0,\theta_1)=\frac{1}{m}\sum_{i=1}^m(h_\theta(x^{(i)})-y^i)x_j^{(i)}$ ；

$repeat$ $until$ $convergence$ 的意思是“重复直到收敛”。

具体步骤为：

随机初始化 $\theta_0$ 和 $\theta_1$ ，即给一个随机的点 $(\theta_0,\theta_1)$ 开始下降
同时减小 $\theta_0 ,\theta_1$ ，到达一个新的点。
循环执行第二步直至收敛。

梯度下降直观理解

注意更新 $\theta$ 值应该同时更新，为什么要同时更新呢？

!@! $!#%@$ ^#%&dsdagag

同时更新可以使上式向量化，也可以采取下面的方式：

同时更新

梯度下降算法中还有一个较为重要的地方就是选择学习率

只要学习率足够小， $J(\theta)$ 就会必然减小。但如果学习率 $a$ 太小，梯度下降的收敛过程可能会很慢，梯度下降的迭代次数会增多。就会让算法失去意义。
而学习率 $a$ 过大，会使梯度下降的过程不断震荡，导致无法收敛。

具体情况如下：

𝛼的大小对梯度下降过程的影响

看到这里，机智的你可能会想到，学习率大的时候下降快，小的时候下降稳，那这样，我是不是可以先选个大的学习率来让函数快速下降，然后改用小的学习率逼近收敛？实际上是不需要的，适当大的固定的学习率也可以保证收敛，因为越接近最优值时梯度越小，梯度与学习率的乘积也会越小，对x的更新也就越小。也就是说，越接近最优值，梯度下降的增量就会自动变得越小。

梯度增量与学习率

以上的梯度下降算法，有时也称为 批量梯度下降 ，指的是在每个单独的梯度下降中，我们都要计算微分求导项，这个项需要对所有m个训练样本求和。所以在梯度下降的每一步中，我们都用到了所有的训练样本，即“批量”的来历。

特征缩放

在基本了解了梯度下降之后，我们来考虑一个更加实际的问题，现在我要对一个房屋的售价进行预测，给定数据集如下，简化每个样本均只有面积和卧室数量两个特征。

房屋面积（英尺）	卧室数量（间）	售价（美元）
2104	3	399900
1600	3	329900
2400	3	369000
1416	2	232000
...	...	...

可以看到，房屋面积和卧室数量这两个特征在数值上差异巨大，反映在 等高线图 上就是一个细长细长的椭圆（不了解等高线图的话就想象把上面那个MSE的三维图压扁，同一条闭合的椭圆上代表的数值相等）。这样的图形，在使用梯度下降法时，会让梯度下降的过程变得不仅曲折，而且非常耗时。

等高线图

解决办法就是将各个特征量化到统一的区间，即对特征进行 特征缩放 。常见的特征缩放方式有两种：

Standardization

Standardization又称为Z-score normalization，量化后的特征服从 标准正态分布 ：

$z=\frac{x_i-\mu}{\delta}$
其中， $\mu$ ， $\delta$ 分别对应特征 $x_i$ 的均值和标准差，量化后的特征将分布在[-1,1]区间。

Min-Max Scaling

MIn-Max Scaling 又称为 normalization ，特征量化的公式为：

$z=\frac{x_i-min(x_i)}{max(x_i)-min(x_i)}$
量化后的特征将分布在 [0,1] 区间。

nomalization的翻译有两种，一种是归一化，一种是标准化。
而在Andrew Ng的课程中将 $z=\frac{x_i-\mu}{s}$ 的形式又称 Mean nomalization 均值归一化 。其中 $\mu$ 为平均值， $s$ 是该特征的范围（max-min）也可以是标准差。
核心思想都是一样的。

大多数机器学习算法中会选择 Standardization 来进行特征缩放，**Min-Max Scaling ** 也并非不用，在数字图像处理中，像素强度通常会被量化到 [0,1] ，在一般的神经网络算法中，也会要求特征被量化到 [0,1] 区间。

回归到我们的梯度下降上，在进行了特征缩放以后，之前“细长的”等高线图就会变得“偏圆”。

缩放了特征的代价函数

特征缩放前后比较

随机梯度下降（Stochastic Gradient Descent）

@@#￥……TFGHFGsdfsf%……%##@￥@

批量梯度下降与随机梯度下降的比较