当前位置：首页 > news >正文

手搓人工智能-最优化算法（1）最速梯度下降法，及推导过程

news 文章来源：https://blog.csdn.net/weixin_73858308/article/details/144075302 2025/1/13 10:22:58

“Men pass away, but their deeds abide.”

人终有一死，但是他们的业绩将永存。

——奥古斯坦-路易·柯西

前言

简单函数求极值

复杂函数梯度法求极值

泰勒展开

梯度，Nabla算子

Cauchy-Schwarz不等式

梯度下降算法

算法流程

梯度下降法优缺点

前言

在学习和训练过程中，需要根据训练样本来确定一组与分类器模型相关的参数。学习过程往往要首先定义某个准则函数，用以描述参数的“合适性”，然后寻找一组“合适性”最大的参数作为学习的结果，也就是将学习问题转化成针对某个准则函数的优化问题

简单函数求极值

对于简单函数，根据数学分析的知识可知：

$m$ 维矢量 $x'$ 是 $f(x)$ 的极值点的必要条件是：

$\frac{\partial f }{\partial x_i'}=0,\forall i \in [1,m]$

将所有的偏导数写成矢量形式：

$\frac{\partial f(x)}{\partial x}=\begin{bmatrix} \frac{\partial f}{\partial x_1}\\ \vdots \\ \frac{\partial f}{\partial x_m} \end{bmatrix}=\begin{bmatrix} 0\\ \vdots \\ 0 \end{bmatrix}=\vec 0$

函数 $f(x)$ 的极值点可以通过求解该矢量方程得到

但是，上述方程的解可能是极大值点，也可能是极小值点，也可能不是极值点，具体情况还需二阶导数来判断。

如果希望求 $f(x)$ 的极大值或极小值点，可以通过比较所有的极大值或极小值得到。

复杂函数梯度法求极值

对于简单的纯凸函数或纯凹函数，由于只存在唯一的极值点，极值点即为最大值或最小值点，因此可以直接求解矢量方程 $\frac{\partial f(x)}{\partial x}=\vec 0$ 得到 $f(x)$ 的优化解。

对于复杂函数来说，直接求解矢量方程得到优化函数的极值点往往非常困难。在这种情况下，可以考虑采用迭代的方法从某个初始值开始，逐渐逼近极值点，即——梯度法

泰勒展开

如果给定了点 $x_0$ 具有所有的前 $n$ 阶导数的函数 $f(x)$ ，我们称多项式：

为函数 $f(x)$ 在点 $x_0$ 处的 $n$ 阶泰勒展开式

泰勒公式是高等数学中的一个非常重要的内容，它将一些复杂的函数逼近近似地表示为简单的多项式函数，泰勒公式这种化繁为简的功能，使得它成为分析和研究许多数学问题的有力工具

考虑到多元函数 $f(x)$ 在点 $x$ 附近的一阶泰勒展开式：

$f(x+\Delta x)=f(x)+\sum_{i=1}^m \frac{\partial f}{\partial x_i}\Delta x_i+r(x,\Delta x)$

其中：

$\Delta x$ 为矢量增量

$\Delta x_i$ 为其第 $i$ 维元素

$r(x,\Delta x)$ 为展开式的余项

梯度，Nabla算子

接下来引入梯度的概念

设二元函数 $z=f(x,y)$ 在平面区域 $D$ 上具有一阶连续偏导数，则对于每一个点 $p(x,y)$ 都可以定出一个向量：

$\{\frac{\partial f}{\partial x},\frac{\partial f}{\partial y}\}=f_x(x,y)\vec i+f_y(x,y)\vec j$

称作函数 $z=f(x,y)$ 在点 $p(x,y)$ 的梯度，记作 $\triangledown f(x,y)$

其中：

$\triangledown =\frac{\partial}{\partial x}\vec i+\frac{\partial }{\partial y}\vec j$

称为（二维的）向量微分算子或Nabla算子

设 $e = \{cos\alpha ,cos\beta \}$ 是方向 $l$ 上的单位向量，则：

$\frac{\partial f}{\partial l}=\frac{\partial f}{\partial x}cos\alpha+\frac{\partial f}{\partial y}cos\beta=\triangledown f(x,y)e$

$=|\triangledown f(x,y)|\cdot|e|\cdot cos[\triangledown f(x,y),e]$

当 $l$ 与梯度方向一致时，有：

$cos[\triangledown f(x,y),e]=1$

此时方向导数 $\frac{\partial f}{\partial l}$ 有最大值，值为梯度的模：

$|\triangledown f(x,y)|=\sqrt{(\frac{\partial f}{\partial x})^2+(\frac{\partial f}{\partial y})^2}$

我们将其推广到无穷维的情况：

设 $n$ 维函数 $f(x)$ 在空间区域 $G$ 内具有一阶连续偏导数，点 $P(x)\in G$ ，称向量：

$\{\frac{\partial f}{\partial x_1},\frac{\partial f}{\partial x_2},\cdots,\frac{\partial f}{\partial x_n}\}$

为函数在点 $P$ 处的导数，记为 $\triangledown f(x)$

稍微集中一下注意力：

注意到一阶展开式中求和项 $\sum_{i=1}^m \frac{\partial f}{\partial x_i} \Delta x_i$ ，改写为：

$\frac{\partial f}{\partial x_1}\Delta x_1 +\frac{\partial f}{\partial x_2}\Delta x_2+\cdots+\frac{\partial f}{\partial x_m}\Delta x_m$

不难发现，该求和式实际上为 $f(x)$ 关于 $x$ 的梯度矢量与矢量增量 $\Delta x$ 之间的内积。

同时，令 $\Delta x\rightarrow 0$ ，有 $r(x,\Delta x)\rightarrow 0$ ，于是有：

$f(x+\Delta x)\approx f(x)+[\triangledown f(x)]^T\Delta x =f(x)+(\frac{\partial f}{\partial x})^T\Delta x$

如果要求取 $f(x)$ 的极小值 $x'$ ，可以从某个初始点 $x_0$ 开始搜索，每次增加一个增量 $\Delta x$ ，虽然不能保证 $x_0+\Delta x$ 直接达到极小值点，但如果能够保证每次迭代过程中函数值逐渐减小：

$f(x+\Delta x)<f(x)$

那么经过一定的迭代次数之后，函数值能够逐渐逼近极小值 $x'$ ，这是一个逐渐下降的过程，因此称为梯度下降法。

更进一步，如果希望下降过程越快越好，用尽可能少的迭代次数逼近极小值，达到对极小值更高精度的逼近，这种方法称为最速下降法

Cauchy-Schwarz不等式

要使函数值下降的最快，就是要寻找一个矢量增量 $\Delta x$ 使得 $[\triangledown f(x)]^T\Delta x$ 最小。

我们引入Cauchy-Schwarz不等式：

其向量形式（欧式空间）：

$x\cdot y=|x|\cdot|y|\cdot cos(x,y)\leq |x|\cdot|y|$

这里不做严谨的证明，且该结论对于大部分人来说非常显然

由于上面我们只展开到一阶近似，当 $||\Delta x||$ 过大时，余项 $r(x,\Delta x)$ 便不能忽略，近似的精度会很差。因此不能直接寻找矢量增量，而是应该寻找使得函数值下降的最快的方向，也就是在约束 $||\Delta x|| =1$ 的条件下，寻找使得 $[\triangledown f(x)]^T\Delta x$ 最小的矢量增量。找到最速下降的方向后，在确定该方向上合适的矢量长度

根据柯西不等式：

$||[\triangledown f(x)]^T\Delta x||\leq ||\triangledown f(x)||\cdot||\Delta x||$

$(\triangledown f(x))^T\Delta x \geq -||\triangledown f(x)||\cdot||\Delta x|| = -||\triangledown f(x)||$

令

$\Delta x=-\frac{\triangledown f(x)}{||\triangledown f(x)||}$

有：

$[\triangledown f(x)]^T\Delta x=[\triangledown f(x)]^T[-\frac{\triangledown f(x)}{||\triangledown f(x)||}]$

$=-\frac{[\triangledown f(x)^T]\triangledown f(x)}{||\triangledown f(x)||}$

$=-\frac{||\triangledown f(x)||^2}{||\triangledown f(x)||}$

$=-||\triangledown f(x)||$

可以得到，当 $\Delta x$ 为负的梯度方向时，不等式等号成立， $[\triangledown f(x)]^T\Delta x$ 取得最小值，函数值下降速度最快。

所以，最速下降法按照以下方式进行迭代：

$x=x+\Delta x=x-\eta \triangledown f(x)$

其中 $\eta$ 一般被称为“学习率” ，用于控制矢量的长度。如果是要寻找极大值，则 $\Delta x$ 应当沿梯度正方向。

梯度下降算法

因为代码求梯度非常困难~~，博主手搓不出来，~~这里只给算法流程

算法流程

初始化： $x_0,\eta,\theta,i=0$
循环，直到 $||\eta\triangledown f(x)|_{x=x_i}||<\theta$
计算当前点的梯度矢量： $\triangledown f(x)|_{x=x_i}$
更新优化解： $x_{i+1}=x_i-\eta\triangledown f(x)|_{x=x_i}$
$i=i+1$
输出优化解