梯度下降（Gradient Descent）是一种在图嵌入中广泛使用的基本优化算法。其主要目标是通过迭代调整图嵌入模型的参数，使得预定义的损失或成本函数的值最小。

梯度下降有不同的变体，每个变体都针对大规模图嵌入任务中的特定挑战进行了优化。主要的变体包括随机梯度下降（SGD, Stochastic Gradient Descent）和小批量梯度下降（MBGD, Mini-Batch Gradient Descent）。这些变体在每次迭代中只使用从单个数据点或小批量数据点计算的梯度来更新模型的参数。

基本形式

考虑一个现实场景：一个人站在山顶，希望尽快下山。一条最佳的下山路径自然是存在的，但想要精确地一下子找出这条路径却很不容易。更常见的做法是走一步看一步：每走一步到达一个新位置时，计算该位置最陡的下降方向（即梯度下降方向），然后朝着那个方向移动至下一位置。重复这个过程，直到到达山脚。

梯度下降就是一种不断沿着梯度下降方向寻找函数最小值的技术。相反地，梯度上升（Gradient Ascent）技术就是要沿着梯度上升方向找到最大值。

给定一个函数 $J(\theta )$，梯度下降的基本形式是：

其中，$\nabla J$ 是函数在位置 $\theta$ 处的梯度，$\eta$ 是学习率（Learning Rate）。由于梯度实际上是最陡的上升方向，所以在 $\eta \nabla J$ 前加一个减号就得到最陡的下降方向。

学习率决定了沿梯度下降方向朝目标前进的每一步的步长。在下山的例子中，可以将学习率视为每一步所行的距离。

在模型训练的过程中，学习率通常保持恒定。然而，有些模型的优化也可能包括学习率，例如使学习率随着训练的进行而逐渐减小或按照预定义的其他计划进行调整。这些调整旨在增强收敛性和优化效率。

示例：单变量函数

对于函数 $J={\theta }^2+10$，它的梯度（在这种情况下，与导数相同）是 $\nabla J=J\prime (\theta )=2\theta$。

如果从 ${\theta }_0=1$ 的位置开始，并设置 $\eta =0.2$，以下是根据梯度下降原则的位置移动：

• ${\theta }_1={\theta }_0-\eta \times 2{\theta }_0=1-0.2\times 2\times 1=0.6$
• ${\theta }_2={\theta }_1-\eta \times 2{\theta }_1=0.6-0.2\times 2\times 0.6=0.36$
• ${\theta }_3={\theta }_2-\eta \times 2{\theta }_2=0.36-0.2\times 2\times 0.36=0.216$
• ...
• ${\theta }_{18}=0.00010156$
• ...

随着步数的增加，会逐渐收敛到 $\theta =0$ 的位置，最终达到函数的最小值。

示例：多变量函数

对于函数 $J(\Theta )={\theta }_1^2+{\theta }_2^2$，其梯度是 $\nabla J=(2{\theta }_1\mathrm{, }2{\theta }_2)$。

如果起始位置是 ${\Theta }_0=(-1\mathrm{, }-2)$，并设置 $\eta =0.1$，以下是根据梯度下降原则的位置移动：

• ${\Theta }_1=(-1-0.1\times 2\times -1\mathrm{, }-2-0.1\times 2\times -2)=(-0.8\mathrm{, }-1.6)$
• ${\Theta }_2=(-0.64\mathrm{, }-1.28)$
• ${\Theta }_3=(-0.512\mathrm{, }-1.024)$
• ...
• ${\Theta }_{20}=(-0.011529215\mathrm{, }-0.002305843)$
• ...

随着步数的增加，会逐渐收敛到 $\Theta =(0\mathrm{, }0)$ 的位置，最终达到函数的最小值。

在图嵌入中的应用

在图嵌入的神经网络模型训练过程中，通常会使用一个损失或成本函数 $J(\Theta )$ 来评估模型的输出与预期结果之间的差异，然后应用梯度下降技术来最小化这个损失函数。这就涉及到在梯度 $\nabla J$ 的反方向上迭代调整模型的参数，直到收敛，从而优化模型。

为了在计算效率和准确性之间取得平衡，在实际中采用了几种梯度下降的变体，主要包括：

1. 随机梯度下降 (SGD)
2. 小批量梯度下降 (MBGD)

示例

考虑使用 $m$ 个样本来训练一个神经网络模型的场景。每个样本包括输入值和对应的期望输出。我们使用 $x^{(i)}$ 和 $y^{(i)}$（$i=1\mathrm{, }2\mathrm{, }\mathrm{...}\mathrm{, }m$）分别表示第 $i$ 个输入值和期望的输出。

模型的假设函数（hypothesis）$h(\Theta )$ 定义如下：

在这里，$\Theta$ 代表模型的参数 ${\theta }_0$ ~ ${\theta }_n$，$x^{(i)}$ 是第 $i$ 个输入向量，包含 $n$ 个特征。模型通过函数 $h(\Theta )$ 对输入的特征进行加权组合来计算输出。

模型训练的目标是找到尽可能使得输出接近期望值的 ${\theta }_{\mathrm{j}}$ 的最佳参数组合。在训练开始时，随机初始化所有参数 ${\theta }_{\mathrm{j}}$。

在模型训练的每轮迭代中，计算出所有样本的输出后，使用均方误差（MSE）作为损失/成本函数 $J(\Theta )$ 来衡量每个输出与其对应的期望值之间的平均误差：

在标准的均方误差（MSE）公式中，分母是 $\frac{1}{m}$。然而，其作为机器学习的损失函数时，通常使用 $\frac{1}{2m}$ 作为分母，目的是抵消掉对损失函数的平方项求导后产生的常数系数，从而简化后续计算。这种修改不会影响最终的结果。

随后，利用梯度下降更新参数 ${\theta }_j$。对 ${\theta }_j$ 求偏导数如下：

因此，${\theta }_j$ 更新为：

从 $i=1$ 到 $m$ 的求和表示在每次迭代中使用所有 $m$ 个样本来更新参数，这种方法被称为批量梯度下降（Batch Gradient Descent，BGD），是梯度下降优化的原始和最直接形式。在 BGD 中，每次迭代使用整个样本数据集来计算损失函数的梯度。

尽管 BGD 可以确保精确收敛到损失函数的最小值，但对于大型数据集来说计算则过于密集。因此梯度下降的变体，如 SGD 和 MBGD，就被开发出来以平衡效率和收敛速度。它们在每次迭代中只使用训练数据的子集，使得优化过程更快，同时仍能够找到最优的参数。

随机梯度下降法

随机梯度下降（SGD）每次迭代只随机选择一个样本进行梯度计算。

在使用 SGD 时，上述的损失函数应表示为：

对于 ${\theta }_j$ 求偏导数为：

更新 ${\theta }_j$ 为：

SGD 的计算复杂性大大降低了，因为它只使用一个样本，不需要求和以及求平均。虽然提高了计算速度，但代价是牺牲一定程度的准确性。

小批量梯度下降法

BGD 和 SGD 代表两个极端——一个使用所有样本，另一个只使用一个样本。小批量梯度下降法（MBGD）则随机选择大小为 $x\in (1\mathrm{, }m)$ 的样本量进行计算，以求在二者之间取得平衡。

数学基础

导数

单变量函数 $f(x)$ 的导数（Derivative）通常表示为 $f\prime (x)$ 或 $\frac{df}{dx}$，它表示在给定位置上 $x$ 略微变化时 $f(x)$ 的变化。

从图上看，$f\prime (x)$ 对应函数曲线的切线（Tangent Line）的斜率。点 $x$ 处的导数是：

例如，$f(x)=x^2+10$，在点 $x=-7$ 处：

切线是指一条刚好触碰到函数曲线上某一点的直线，切线的方向与该点的方向相同。

偏导数

多变量函数的偏导数（Partial Derivative）衡量在保持其他所有变量不变的情况下，某一个变量变化时函数如何变化。对于一个函数 $f(x,y)$，在特定点 $(x,y)$ 处，它相对于 $x$ 的偏导数表示为 $\frac{\partial f}{\partial x}$ 或 $f_x^{\prime }$：

例如，$f(x,y)=x^2+y^2$，在点 $x=-4$，$y=-6$ 处：

$L1$ 表示在保持 $x$ 不变、沿 Y 轴移动时函数的变化；$L2$ 表示在保持 $y$ 不变、沿 X 轴移动时函数的变化

方向导数

函数的偏导数表示沿着坐标轴方向轻微移动时输出的变化情况。当沿着与任何坐标轴都不平行的方向移动时，就有了方向导数（Directional Derivative）的概念。

方向导数在数学上表示为向量 $\nabla f$（它由函数的所有偏导数组成）与表示变化方向的单位向量 $\overrightarrow{w}$ 的点积：

其中 $|\overrightarrow{w}|=1$，$\theta$ 是两个向量之间的夹角，并且

梯度

梯度（Gradient）是使函数的输出具有最陡上升的方向，这等同于找到最大的方向导数，而这发生在向量 $\nabla f$ 和 $\overrightarrow{w}$ 之间的角度 $\theta$ 为 $0$ 时，因为 $\cos 0=1$，即 $\overrightarrow{w}$ 与 $\nabla f$ 的方向一致。因此，$\nabla f$ 就是函数的梯度。

很显然，负梯度就是函数最陡下降的方向。

链式法则

链式法则（Chain Rule）描述如何计算复合函数的导数。在最简单的形式中，复合函数 $f(g(x))$ 的导数可以通过将 $f$ 关于 $g$ 的导数与 $g$ 关于 $x$ 的导数相乘来计算：

例如，$s(x)={(2x+1)}^2$ 由 $s(u)=u^2$ 和 $u(x)=2x+1$ 组成，那么：

在多变量复合函数中，可以通过对每个变量应用链式法则来获得偏导数。

例如，$s(x,y)=(2x+\mathrm{y})(y-3)$ 由 $s(f,g)=fg$ 以及 $f(x,y)=2x+\mathrm{y}$ 和 $g(x,y)=y-3$ 组成，那么：