梯度递降法(1)（gradient descent）

作者: 十年磨剑_莫回首 | 来源:发表于2020-03-20 05:58 被阅读0次

神经网络优化2
全梯度下降算法从零实现，基于Numpy
机器学习系列（十六）——随机梯度下降Stochastic Gra
3.线性神经网络 - 随机梯度下降法
机器学习_梯度下降算法
sklearn学习笔记——稳健回归分析
吴恩达深度学习笔记（8）-重点-梯度下降法（Gradient D
（史上最详细）批量梯度下降算法、随机梯度下降算法、小批量梯度下降
机器学习笔记（六）—— 梯度下降
快速理解梯度下降法

Gradient descent for unconstrained problems

梯度下降法常常用于寻找一个多元函数的最大值，最小值问题。

梯度下降比较关心的两个问题是：

1. 如何实现 $f(x^{t+1} )<f(x^{t})$ ，在每一次更新 $x^{t+1}=M(x^{t})$ ，其中M： $R^{n}\rightarrow R^{n}$

2. 收敛速度的控制，这主要涉及到每次更新的stepsize的选择。

一更新公式的由来

对于一个可微函数 $f$ : $R^{n}\rightarrow R$ ，构造这样一组有序数列{ ${x: x\in R^{n}}$ }，使得

$f(x^{t+1})<f(x^{t})$ ，t=0,1,2,...

引入向量 $d\in R^{n}$ ,那么我们有

$df(x;d)$ = $\lim_{\tau\to0}\frac{f(x+\tau d)-f(x)}{\tau}$ = $▽ f(x)^{T}d$ <0，其中 $▽ {f}$ 为在 $x$ 处的梯度, $df$ 为梯度 $▽ f$ 沿着向量d的方向导数值。

由 $\lim_{\tau\to0}\frac{f(x+\tau d)-f(x)}{\tau}$ <0，可以知道当 $\tau$ 为正数的时候，那么沿着向量d方向的增量，可以满足 $f(x+\tau d)<f(x)$ , 如此就可以构造出这样一个符合 $f(x^{t+1})<f(x^t)$ 的一组有序数列{ $x^t$ }。

我们乘这样的一个方向向量 $d$ 梯度方向向量。

于是乎，在每一次 $x^t$ 的更新中，我们可以寻找这样的梯度向量 $d^t$ ，来使得每一次更新都可以实现

$f(x^{t+1})<f(x^t)$ ，公式中的 $\tau$ 其实就是我们需要定义的迭代步长 ${\eta }^t$ 。

那么迭代更新公式也基本已经明了：

$x^{t+1}=x^t+{\eta }^t d^t$ ，其中 ${\eta }^t>0$ , $d^t 是梯度方向$

$在梯度下降中非常经典的一个例子是 \quadx^{t+1}=x^t-{\eta }^t ▽f(x^t)$

$这里，梯度方向：d^t=-▽f(x^t) \quad这里引入最速递降的原理：$

$arg\quad min_{d:||d||_2\leq 1}\quad df(x;d)=arg\quad min_{d:||d||_2\leq1} ▽f(x)^{T}d=-||▽f(x)||_2$

$对于二次型最小问题（quadratic \quad minimization \quad problem）\quad其目标函数：$

$f(x^*)=minimize_x \quad \frac{1}{2}(x-x^*)^TQ(x-x^*)$

$其中，对于一个n*n的方阵Q，其满足\succ 0，并且 ▽f(x)=Q(x-x^*)$ $\text{[math]}$ $对于二次型这个概念，大家如果有不清楚的可以去查找资料。$

固定步长(constant stepsize)

$在可以产生这样的序列{x^t}以后,初始化的点为x^0$

$下面考察使用定步长的{\eta }^t 的更新迭代的收敛情况。$

$已知，对于一个向量x，左乘一个矩阵A,$

$那么其实就是对向量x做了旋转和拉伸变换，$

$而矩阵A的特征值{\lambda }反映了旋转拉伸变化的大小，所以，$

$我们知道|\lambda _{min}(A)|\cdot ||x||_2\leq ||Ax||_2\leq |\lambda _{max}(A)|\cdot ||x||_2$

$根据梯度下降更新公式，我们可以有如下推导：$

$x^{t+1}-x^*=x^t-x^*-{\eta }^t▽f(x^t)=(I-{\eta }^tQ)(x^t-x^*)\\\implies ||x^{t+1}-x^*||_2\leq ||I-{\eta }^t||x^t-x^*||_2$

$这里需要||\cdot ||_2 代表求向量l_2范数，可以理解为向量的模长，$

$那么，我们可以发现：$

$||I-{\eta }^tQ||=max(|1-{\eta }^t\lambda _{max}(Q)|,|1-{\eta }^t\lambda _{min}(Q)|) \\({\eta }^t= \frac{2}{\lambda _{max}(Q)+\lambda_{min}(Q)}) \\||I-{\eta }^tQ||=1- \frac{2\lambda_{min}(Q)}{\lambda _{max}(Q)+\lambda_{min}(Q)}= \frac{\lambda_{max}(Q)-\lambda_{min}(Q)}{\lambda_{max}(Q)+\lambda_{min}(Q)}= \frac{K-1}{K+1} \\\\ 其中，K称之为条件数(condition \quad number)$

$这里需要注意步长{\eta }^t的取法，{\eta }^t:=min\quad max (|I-{\eta }^tQ|)$

收敛性

$x^{t+1}-x^*=x^t-x^*-{\eta}^t▽f(x^t)\leq ( \frac{K-1}{K+1})(x^t-x^*)\\\implies x^{t}-x^*\leq( \frac{K-1}{K+1})^{t}(x^0-x^*)$

非固定步长

固定步长的缺点是我们需要知道矩阵Q的谱，简单地即矩阵Q的特征值情况，但是在实际生活中，往往计算Q的谱，是一个比较昂贵的操作，尤其是在Q比较复杂的情况下，有的时候Q是满秩，有的时候Q是不满秩。

因此有必要使用其他的方法来选择每一次的迭代步长。对于非固定步长，常用的方法是exact line search 和 backtracking research，来选取每一次迭代更新的步长。

下面先介绍 exact line search 方法

Exact line search

该方法的主要策略是每一次都去寻找这样的一个步长 ${\eta}^t$ ,使得:

${\eta}^t:=argmin_{\eta\geq0} \quad f(x^t-{\eta}^t▽f(x^t))$

这里不加证明地给出步长的更新公式：

$令g^t=▽f(x^t)=Q(x^t-x^*)\\{\eta}^t=\frac{{g^t}^Tg^t}{{g^t}^TQg^t}$

下面推导收敛性：

$假设f(x^*)=0,然后，我么可以推导出：\\f(x^{t+1})= \frac{1}{2}(x^t-{\eta}^tg^t-x^*)^TQ(x^t-{\eta}^tg^t-x^*\\= \frac{1}{2}(x^t-x^*)^TQ(x^t-x^*)-{\eta}^t||g^t||_2^2+ \frac{{{\eta}^t}^2}{2}{g^t}^TQg^t\\= \frac{1}{2}(x^t-x^*)^TQ(x^t-x^*)- \frac{||g^t||_2^4}{2{g^t}^TQg^t}\\=(1- \frac{||g^t||_2^4}{({g^t}^TQg^t)({g^t}^TQ^{-1}g^t)})f(x^t)\\其中，f(x^t)= \frac{1}{2}(x^t-x^*)^TQ(x^t-x^*)= \frac{1}{2}{g^t}^TQ^{-1}g^t \\从 Kantorovich 不等式可以知道：\\\frac{||g^t||_2^4}{({g^t}^TQg^t)({g^t}^TQ^{-1}g^t)}\geq \frac{4\lambda_{max}(Q)\lambda_{min}(Q)}{(\lambda_{min}(Q)+\lambda_{max}(Q))^2} \\这样，我们进一步可以获得：\\f(x^{t+1}) \leq (1- \frac{4 \lambda_{min}(Q)\lambda_{max}(Q)}{(\lambda_{min}(Q)+\lambda_{max}(Q))^2})f(x^t)\\=( \frac{\lambda_{max}(Q)-\lambda_{min}(Q)}{\lambda_{max}(Q)-\lambda_{min}(Q)})^2f(x^t)$

这里如果再把 $f(x^*)=0$ 带进去，就是一个收敛式子。

这个方法由于计算量也比较大，所以在日常的研究中，使用的频率不是特别高，大家了解一下就好。

下面在说backtracking search之前，先说一下convex和smooth性质的二阶可微函数 $f(x)$

如果 $f(x)$ 是 $\mu-convex \quad and\quad L-smooth$ ,

$如果一个函数是\mu-convex 的，那么根据泰勒展开有：\\f(y)= f(x)+▽f(x)^T(y-x)+ \frac{1}{2}(y-x)^T▽^2f(x)(y-x)+\cdots\\=f(x)+▽f(x)^T(y-x)+ \frac{1}{2}(y-x)^T▽^2f(x)(y-x)+ \frac{1}{2}(y-x)^TuI(y-x)- \frac{1}{2}(y-x)^TuI(y-x)+\cdots\\=f(x)+▽f(x)^T(y-x)+ \frac{1}{2}(y-x)^T(▽^2f(x)-uI)(y-x)+ \frac{1}{2}(y-x)^TuI(y-x)+\cdots\\\geq f(x)+▽f(x)^T(y-x)+ \frac{1}{2}(y-x)^TuI(y-x)\\=f(x)+▽f(x)^T(y-x)+ \frac{\mu}{2}||y-x||_2^2, \forall x,y$

证明主要涉及到正定矩阵的一个性质：对于一个正定矩阵A，其满足 $x^TAx \geq0 恒成立$

这里的 $A=▽^2f(x)-uI \succeq 0$

同样地，可以证明：

$f(y) \leq f(x)+▽f(x)^T(y-x)+ \frac{L}{2}||y-x||_2^2,\forall x,y$

那么根据定义就有： $0\preceq \mu I\preceq▽^2f(x)\preceq LI, \forall x$

神经网络优化2
梯度下降梯度下降法批梯度下降法（Batch Gradient Descent，BGD）是最常用的梯度下降形式，...
全梯度下降算法从零实现，基于Numpy
批量梯度下降法BGD Github 批量梯度下降法（Batch Gradient Descent，简称BGD）是梯...
机器学习系列（十六）——随机梯度下降Stochastic Gra
随机梯度下降法Stochastic Gradient Descent 在之前的梯度下降法解决线性回归问题中，梯度向...
3.线性神经网络 - 随机梯度下降法
随机梯度下降法:stochastic gradient descent 大纲 1. look --- 大数据情况...
机器学习_梯度下降算法
梯度下降法(Gradient descent)或最速下降法(steepest descent)是求解无约束最优化问...
sklearn学习笔记——稳健回归分析
1、零碎的概念学习 Stochastic Gradient Descent 随机梯度下降法 Perceptron ...
吴恩达深度学习笔记（8）-重点-梯度下降法（Gradient D
梯度下降法（Gradient Descent）（重点）梯度下降法可以做什么？在你测试集上，通过最小化代价函数（...
（史上最详细）批量梯度下降算法、随机梯度下降算法、小批量梯度下降
伪代码：批量梯度下降法（Batch Gradient Descent）:Repeat until converg...
机器学习笔记（六）—— 梯度下降
梯度下降批量梯度下降（Batch Gradient Descent，BGD）批量梯度下降法是最原始的形式，它是...
快速理解梯度下降法
1. 梯度下降法的抽象理解梯度下降法（Gradient descent）是深度学习中的最基础的工具之一，它是一种...