梯度下降法¶

学习目标¶

掌握梯度下降算法的原理
掌握梯度下降法优化损失函数的原理

1. 梯度下降(Gradient Descent)¶

1.1 什么是梯度下降¶

梯度下降法的基本思想可以类比为一个下山的过程。

假设这样一个场景：

一个人 被困在山上，需要从山上下来 (i.e. 找到山的最低点，也就是山谷)。但此时山上的浓雾很大，导致可视度很低。

因此，下山的路径就无法确定，他必须利用自己周围的信息去找到下山的路径。这个时候，他就可以利用梯度下降算法来帮助自己下山。

具体来说就是，以他当前的所处的位置为基准，寻找这个位置最陡峭的地方，然后朝着山的高度下降的地方走，（同理，如果我们的目标是上山，也就是爬到山顶，那么此时应该是朝着最陡峭的方向往上走）。然后每走一段距离，都反复采用同一个方法，最后就能成功的抵达山谷。

梯度下降的基本过程就和下山的场景很类似。

首先，我们有一个 可微分的函数 。这个函数就代表着一座山。

我们的目标就是找到 这个函数的最小值 ，也就是山底。

根据之前的场景假设，最快的下山的方式就是找到当前位置最陡峭的方向，然后沿着此方向向下走，对应到函数中，就是 找到给定点的梯度 ，然后朝着梯度相反的方向，就能让函数值下降的最快！因为梯度的方向就是函数值变化最快的方向。所以，我们重复利用这个方法，反复求取梯度，最后就能到达局部的最小值，这就类似于我们下山的过程。而求取梯度就确定了最陡峭的方向，也就是场景中测量方向的手段。

1.2 梯度的概念¶

梯度是微积分中一个很重要的概念

在单变量的函数中，梯度其实就是函数的微分，代表着函数在某个给定点的切线的斜率；
在多变量函数中，梯度是一个向量，向量有方向，梯度的方向就指出了函数在给定点的上升最快的方向；
在微积分里面，对多元函数的参数求∂偏导数，把求得的各个参数的偏导数以向量的形式写出来，就是梯度。

这也就说明了为什么我们需要千方百计的求取梯度！我们需要到达山底，就需要在每一步观测到此时最陡峭的地方，梯度就恰巧告诉了我们这个方向。梯度的方向是函数在给定点上升最快的方向，那么梯度的反方向就是函数在给定点下降最快的方向，这正是我们所需要的。所以我们只要沿着梯度的反方向一直走，就能走到局部的最低点！

1.3 梯度下降举例¶

单变量函数的梯度下降

我们假设有一个单变量的函数 :\(J(\theta) = \theta^2\)

函数的微分：\(J^\prime(\theta) = 2\theta\)

初始化，起点为：\(\theta^0 = 1\)

学习率：\(\alpha = 0.4\)

我们开始进行梯度下降的迭代计算过程:

\[ \large \begin{eqnarray} \theta^0 &=& 1 \tag{1} \\ \theta^1 &=& \theta^0-\alpha * J^\prime(\theta^0) \tag{2} \\ &=& 1 - 0.4 * 2 \\ &=& 0.2 \\ \theta^2 &=&\theta^1-\alpha*J^\prime(\theta^1) \tag{3} \\ &=& 0.04 \\ \theta^3 &=& 0.008 \tag{4}\\ \theta^4 &=& 0.0016 \tag{5} \end{eqnarray} \]

如图，经过四次的运算，也就是走了四步，基本就抵达了函数的最低点，也就是山底

多变量函数的梯度下降

我们假设有一个目标函数：\(J(\theta) = \theta_{1}^{2} + \theta_{2}^{2}\)

现在要通过梯度下降法计算这个函数的最小值。我们通过观察就能发现最小值其实就是 (0，0)点。但是接下来，我们会从梯度下降算法开始一步步计算到这个最小值! 我们假设初始的起点为： \(\theta^{0} = (1, 3)\)

初始的学习率为：\(\alpha = 0.1\)

函数的梯度为：\(\Delta J(\theta) =< 2\theta_{1} ,2\theta_{2}>\)

进行多次迭代：

\[ \begin{eqnarray} \Theta^0 &=& (1, 3) \\ \Theta^1 &=& \Theta^0-\alpha\Delta J(\Theta)\\ &=&(1,3)-0.1(2,6)\\ &=&(0.8, 2.4)\\ \Theta^2 &=& (0.8, 2.4)-0.1(1.6, 4.8)\\ &=&(0.64, 1.92)\\ \Theta^3 &=& (0.512, 1.536)\\ \Theta^4 &=& (0.4096, 1.2288)\\ \vdots\\ \Theta^{10} &=& (0.10737418240000003, 0.32212254720000005)\\ \vdots\\ \Theta^{50} &=& (1.1417981541647683e^{-5}, 3.425394462494306e^{-5})\\ \vdots\\ \Theta^{100} &=& (1.6296287810675902e^{-10}, 4.888886343202771e^{-10})\\ \end{eqnarray} \]

我们发现，已经基本靠近函数的最小值点

1.4 梯度下降（Gradient Descent）公式¶

\[ \Large \theta_{i+1} = \theta_{i} - \alpha\frac{\partial}{\partial\theta_{i}}J(\theta) \]

1) \(\alpha\)是什么含义？

\(\alpha\)在梯度下降算法中被称作为 学习率 或者步长，意味着我们可以通过α来控制每一步走的距离，控制参数不要走太快，错过了使损失函数取最小值的点。同时也要保证不要走的太慢，导致太阳下山了，还没有走到山下。所以α的选择在梯度下降法中往往是很重要的！α不能太大也不能太小，太小的话，可能导致迟迟走不到最低点，太大的话，会导致错过最低点！

2) 为什么梯度要乘以一个负号？

梯度前加一个负号，就意味着朝着梯度相反的方向前进！我们在前文提到，梯度的方向实际就是函数在此点上升最快的方向！而我们需要朝着下降最快的方向走，自然就是负的梯度的方向，所以此处需要加上负号

我们通过两个图更好理解梯度下降的过程

ååéçæ¢¯åº¦ä¸é

å¤åéçæ¢¯åº¦ä¸é

所以有了梯度下降这样一个优化算法，回归就有了"自动学习"的能力

优化动态图演示¶

2. 梯度下降优化原理¶

2.1梯度下降的相关概念复习¶

在详细了解梯度下降的算法之前，我们先复习相关的一些概念。

步长(Learning rate)：

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

特征(feature)：

指的是样本中输入部分，比如2个单特征的样本\((x^{(0)},y^{(0)}),(x^{(1)},y^{(1)})\),则第一个样本特征为\(x^{(0)}\)，第一个样本输出为\(y^{(0)}\)。

假设函数(hypothesis function)：

在监督学习中，为了拟合输入样本，而使用的假设函数，记为\(h_\theta (x)\)。 比如对于单个特征的m个样本\((x^{(i)},y^{(i)})(i=1,2,...m)\),可以采用拟合函数如下： \(h_\theta (x)=\theta _0+\theta _1x\)。

损失函数(loss function)：

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

\[ \large J(\theta_0, \theta_1) = \sum_{i=1}^{m}(h_{\theta}(x_{i})-y_{i})^2 \]

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

2.2 梯度下降法的推导流程¶

1) 先决条件：确认优化模型的假设函数和损失函数。

比如对于线性回归，假设函数表示为 \(h_\theta (x_1,x_2,...,x_n)=\theta _0+\theta _1x_1+...+\theta _nx_n\), 其中\(\theta _i (i = 0,1,2... n)\)为模型参数，\(x_i (i = 0,1,2... n)\)为每个样本的n个特征值。这个表示可以简化，我们增加一个特征\(x_0=1\) ，这样

\[ \large h_\theta(x_{0}, x_{1}, \cdots, x_{n}) = \sum_{i=0}^{n}\theta_ix_i \]

同样是线性回归，对应于上面的假设函数，损失函数为：

\[ \large J(\theta_0,\theta_1,\cdots,\theta_n) = \frac{1}{2m}\sum_{j=0}^{m}(h_{\theta}(x_0^{(j)},x_1^{(j)},\cdots,x_n^{(j)})-y_j)^2 \]

2) 算法相关参数初始化,

主要是初始化\(\theta _0,\theta _1...,\theta _n\),算法终止距离ε以及步长\(\alpha\) 。在没有任何先验知识的时候，可以将所有的\(\theta\) 初始化为0，将步长初始化为1。在调优的时候再优化。

3) 算法过程：

3.1) 确定当前位置的损失函数的梯度，对于\(\theta _i\),其梯度表达式如下：

\[ \large \frac{\partial}{\partial\theta_i}J(\theta_0,\theta_1,\cdots,\theta_n) \]

3.2) 用步长乘以损失函数的梯度，得到当前位置下降的距离，即

\[ \large \alpha\frac{\partial}{\partial\theta_i}J(\theta_0,\theta_1,\cdots,\theta_n) \]

对应于前面登山例子中的某一步。

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

4)更新所有的\(\theta\) ，对于\(\theta _i\)，其更新表达式如下。更新完毕后继续转入步骤1。

\[ \large \theta_{i+1} = \theta_i - \alpha\frac{1}{m}\sum_{j=0}^{m}(h_{\theta}(x_0^{(j)},x_1^{(j)},\cdots,x_n^{(j)})-y_j)x_i^{(j)} \]

下面用线性回归的例子来具体描述梯度下降。假设我们的样本是:

\[ \large (x_1^{(0)},x_2^{(0)},\cdots,x_n^{(0)},y_0), (x_1^{(1)},x_2^{(1)},\cdots,x_n^{(1)},y_1), (x_1^{(m)},x_2^{(m)},\cdots,x_n^{(m)},y_m) \]

损失函数如前面先决条件所述：

\[ \large J(\theta_0,\theta_1,\cdots,\theta_n) = \frac{1}{2m}\sum_{j=0}^{m}(h_{\theta}(x_1^{(j)},x_2^{(j)},\cdots,x_n^{(j)})-y_j)^2 \]

则在算法过程步骤1中对于\(\theta _i\) 的偏导数计算如下：

\[ \large \frac{\partial}{\partial\theta_i}J(\theta_0,\theta_1,\cdots,\theta_n) = \frac{1}{m}\sum_{j=0}^{m}(h_{\theta}(x_1^{(j)},x_2^{(j)},\cdots,x_n^{(j)})-y_j)x_i^{(j)} \]

由于样本中没有\(x_0\)上式中令所有的\(x_0^j\)为1.

步骤4中\(\theta _i\)的更新表达式如下：