2018-11-15

---

layout: post

title:  梯度下降算法小结

date:  2017-01-11 09:00:00 +0800

tags: Machine-Learning

categories: Machine-Learning

typora-root-url: ..\..

---

{% include lib/mathjax.html%}

### 基本概念

#### 梯度

在微积分里面，对多元函数的参数求偏导数，把求得的各个参数的偏导数以向量的形式写出来，就是梯度。比如函数$$f(x,y)$$, 分别对x,y求偏导数，求得的梯度向量就是$$(\frac{\partial f}{\partial x_0},\frac{\partial f}{\partial y_0})^T$$,简称$$grad f(x,y)$$或者$$▽f(x,y)$$。对于在点(x0,y0)的具体梯度向量就是$$(\frac{\partial f}{\partial x_0},\frac{\partial f}{\partial y_0})^T$$.或者▽f(x0,y0)。如果是3个参数的向量梯度，就是$$(∂f/∂x, ∂f/∂y，∂f/∂z)^T$$,以此类推。 

梯度向量，从几何意义上讲，就是函数变化增加最快的地方。具体来说，对于函数f(x,y),在点(x0,y0)，沿着梯度向量的方向就是$$(∂f/∂x0, ∂f/∂y0)^T$$的方向是f(x,y)增加最快的地方。或者说，沿着梯度向量的方向，更加容易找到函数的最大值。反过来说，沿着梯度向量相反的方向，也就是$$ -(∂f/∂x0, ∂f/∂y0)^T$$的方向，梯度减少最快，也就是更加容易找到函数的最小值。

#### 梯度下降

在机器学习算法中，在最小化损失函数时，可以通过梯度下降法来一步步的迭代求解，得到最小化的损失函数和模型参数值。


#### 梯度下降的相关概念

1. 步长（Learning rate）：步长决定了在梯度下降迭代的过程中，每一步沿梯度负方向前进的长度。用上面下山的例子，步长就是在当前这一步所在位置沿着最陡峭最易下山的位置走的那一步的长度。

2. 特征（feature）：指的是样本中输入部分，比如样本（x0,y0）,（x1,y1）,则样本特征为x，样本输出为y。

3. 假设函数（hypothesis function）：在监督学习中，为了拟合输入样本，而使用的假设函数，记为hθ(x)。比如对于样本（xi,yi）(i=1,2,...n),可以采用拟合函数如下： $$h_\theta(x) = \theta_0 + \theta_1 x$$。

4. 损失函数（loss function）：为了评估模型拟合的好坏，通常用损失函数来度量拟合的程度。损失函数极小化，意味着拟合程度最好，对应的模型参数即为最优参数。在线性回归中，损失函数通常为样本输出和假设函数的差取平方。比如对于样本（xi,yi）(i=1,2,...n),采用线性回归，损失函数为：

$$

J(\theta_0, \theta_1) = \sum\limits_{i=1}^{m}(h_\theta(x_i) - y_i)^2

$$

其中$$x_i$$表示样本特征$$x$$的第$$i$$个元素，$$y_i$$表示样本输出$$y$$的第$$i$$个元素，$$h_\theta(x_i)$$为假设函数。

### 梯度下降算法

**核心**:最小化目标函数J(θ)，其中θ是模型的参数，$$\theta \in \mathbb{R}^d$$。它的方法是，在每次迭代中，对每个变量，按照目标函数在该变量梯度的相反方向，更新对应的参数值。其中，学习率η决定了函数到达（局部）最小值的迭代次数。

梯度下降法的算法的两种表示方式：

+ 代数法

+ 矩阵法(向量法)

#### 算法过程

1. 确定当前位置的损失函数的梯度，对于$$θ_i$$,其梯度表达式如下：

$$

\frac{\partial}{\partial \theta_i}J(\theta_0,\theta_1,...,\theta_n)

$$

2. 用步长乘以损失函数的梯度，得到当前位置下降的距离，即$$\alpha \frac{\partial}{\partial \theta_i}J(\theta_0,\theta_1,...,\theta_n)$$对应于前面登山例子中的某一步。

3. 确定是否所有的θi,梯度下降的距离都小于ε，如果小于ε则算法终止，当前所有的$$θ_i(i=0,1,...n)$$即为最终结果。否则进入步骤4.

4. 更新所有的θ，对于$$θ_i$$，其更新表达式如下。$$\theta_i = \theta_i - \alpha\frac{\partial}{\partial\theta_i}J(\theta_0, \theta_1..., \theta_n)$$更新完毕后继续转入步骤1.

### 梯度下降的各种变体(BGD，SGD，MBGD)

**不同之处**：一次性使用多少数据来计算目标函数的梯度。

#### 批量梯度下降（Batch gradient descent） 

代码实现：

```python

for i in range(nb_epochs):

    params_grad = evaluate_gradient(loss_function, data, params)

    params = params - learning_rate * params_grad

```

#### 随机梯度下降（Stochastic gradient descent）

代码实现：

```python

for i in range(nb_epochs):

    np.random.shuffle(data)

    for example in data:

        params_grad = evaluate_gradient(loss_function, example, params)

        params = params - learning_rate * params_grad

```

#### 小批量梯度下降（Mini-batch gradient descent）

代码实现：

```python

for i in range(nb_epochs):

    np.random.shuffle(data)

    for batch in get_batches(data, batch_size=50):

        params_grad = evaluate_gradient(loss_function, batch, params)

        params = params - learning_rate * params_grad

```

### 梯度下降的算法调优

在使用梯度下降时，需要进行调优。哪些地方需要调优呢？

1. 算法的步长选择

  步长太大，会导致迭代过快，甚至有可能错过最优解。步长太小，迭代速度太慢，很长时间算法都不能结束。

2. 算法参数的初始值选择

  初始值不同，获得的最小值也有可能不同，因此梯度下降求得的只是局部最小值；当然如果损失函数是凸函数则一定是最优解。由于有局部最优解的风险，需要多次用不同初始值运行算法，关键损失函数的最小值，选择损失函数最小化的初值。

3. 归一化

  由于样本不同特征的取值范围不一样，可能导致迭代很慢，为了减少特征取值的影响，可以对特征数据归一化，也就是对于每个特征x，求出它的期望$\overline{x}$和标准差std(x)，然后转化为： 

$$

\frac{x - \overline{x}}{std(x)} 

$$

这样特征的新期望为0，新方差为1，迭代次数可以大大加快。

### 梯度下降法和其他无约束优化算法的比较

#### 无约束优化算法

+ 最小二乘法

+ 梯度下降

    - 批量梯度下降 

    - 随机梯度下降 

    - 小批量梯度下降 

+ 牛顿法

+ 拟牛顿法

#### 无约束优化算法的比较

+ 梯度下降法和最小二乘法相比，梯度下降法需要选择步长，而最小二乘法不需要。梯度下降法是迭代求解，最小二乘法是计算解析解。如果样本量不算很大，且存在解析解，最小二乘法比起梯度下降法要有优势，计算速度很快。但是如果样本量很大，用最小二乘法由于需要求一个超级大的逆矩阵，这时就很难或者很慢才能求解解析解了，使用迭代的梯度下降法比较有优势。

+ 梯度下降法和牛顿法/拟牛顿法相比，两者都是迭代求解，不过梯度下降法是梯度求解，而牛顿法/拟牛顿法是用二阶的海森矩阵的逆矩阵或伪逆矩阵求解。相对而言，使用牛顿法/拟牛顿法收敛更快。但是每次迭代的时间比梯度下降法长。

### 面临的挑战

由于 Vanilla 小批量梯度下降法并不能保证良好地收敛，这给我们留下了如下待解决的挑战：

+ 选择适当的学习率是一个难题。

太小的学习率会导致较慢的收敛速度，而太大的学习率则会阻碍收敛，并会引起罚函数在最小值处震荡，甚至有可能导致结果发散； 

+ 我们可以设置一个关于学习率地列表，通过如退火的方法，在学习过程中调整学习率——按照一个预先定义的列表、或是当每次迭代中目标函数的变化小于一定阈值时来降低学习率。但这些列表或阈值，需要根据数据集地特性，被提前定义。

+ 此外，我们对所有的参数都采用了相同的学习率。但如果我们的数据比较稀疏，同时特征有着不同的出现频率，那么我们不希望以相同的学习率来更新这些变量，我们希望对较少出现的特征有更大的学习率。

+ 在对神经网络最优化非凸的罚函数时，另一个通常面临的挑战，是如何避免目标函数被困在无数的局部最小值中，以导致的未完全优化的情况。Dauphin 及其他人认为，这个困难并不来自于局部最小值，而是来自于「鞍点」，也就是在一个方向上斜率是正的、在一个方向上斜率是负的点。这些鞍点通常由一些函数值相同的面环绕，它们在各个方向的梯度值都为 0，所以 SGD 很难从这些鞍点中脱开。

应对上述问题，学者们提出了一些改进算法，它们被广泛应用于深度学习。下一篇文章介绍[梯度下降的优化算法]()。

### Reference

+ http://ruder.io/optimizing-gradient-descent/

+ https://www.jiqizhixin.com/articles/2016-11-21-4

+ http://www.cnblogs.com/pinard/p/5970503.html