讨论函数\(z = f(x, y)\)在一点\(p(x, y)\)沿某一方向的变化率问题. 已知 \[ \Delta z = f(x + \Delta x, y + \Delta y) - f(x, y) \] 令向量\(l\)为从\(p\)点引出的任意球向量, 其模为\(\rho = \sqrt{(\Delta x)^2 + (\Delta y)^2}\), 则变化率为 \[ \frac{\Delta z}{\rho} = \frac{f(x + \Delta x, y + \Delta y) - f(x, y)}{\sqrt{(\Delta x)^2 + (\Delta y)^2}} \]

取极限后

\[ \frac{\partial f}{\partial l} =\lim_{\rho \rightarrow 0} \frac{f(x + \Delta x, y + \Delta y) - f(x, y)}{\sqrt{(\Delta x)^2 + (\Delta y)^2}} \] 是否存在?

如果函数\(f(x, y)\)在\(p(x, y)\)可微, 那么在\(p\)沿任意方向\(l\)的方向导数为:

\[ \begin{aligned} \frac{\partial f}{\partial l} =& \lim_{\rho \rightarrow 0} \frac{f(x + \Delta x, y + \Delta y) - f(x, y)}{\sqrt{(\Delta x)^2 + (\Delta y)^2}} \\ =& \lim_{\rho \rightarrow 0} \frac{\frac{\partial f}{\partial x} \Delta x + \frac{\partial f}{\partial y} \Delta y + o(\rho)}{\sqrt{(\Delta x)^2 + (\Delta y)^2}} \\ =& \frac{\partial f}{\partial x} cos\ \phi + \frac{\partial f}{\partial y} sin\ \phi \end{aligned} \] 其中\(\phi\)为\(x\)与\(l\)的夹角.

\[ \begin{aligned} \frac{\partial f}{\partial l} =& \lim_{\rho \rightarrow 0} \frac{f(x + \Delta x, y + \Delta y) - f(x, y)}{\sqrt{(\Delta x)^2 + (\Delta y)^2}} \\ =& \lim_{\rho \rightarrow 0} \frac{\frac{\partial f}{\partial x} \Delta x + \frac{\partial f}{\partial y} \Delta y + o(\rho)}{\sqrt{(\Delta x)^2 + (\Delta y)^2}} \\ =& \frac{\partial f}{\partial x} cos\ \phi + \frac{\partial f}{\partial y} sin\ \phi \\ =& [\frac{\partial f}{\partial x}, \frac{\partial f}{\partial y}]^T \cdot \underbrace{[cos\ \phi, sin\ \phi]}_{l方向的单位向量} \\ =& |\frac{\partial f}{\partial x}, \frac{\partial f}{\partial y}| \times cos\ \theta \\ \leq & |\frac{\partial f}{\partial x}, \frac{\partial f}{\partial y}|, \end{aligned} \]

其中\(\theta\) 表示两向量的夹角.

我们这样定义\(f(x, y)\)在点\(p\)的梯度:

\[ \nabla\ f(x, y) = [\frac{\partial f}{\partial x}, \frac{\partial f}{\partial y}]. \]

其是一个向量,模为方向导数的最大值,方向与取得最大值的方向向量\(l\)一致.

如果多变量函数 \(F(\mathbf{x})\) 在点 \(\mathbf{a}\)(看作前文的\(p(x, y)\)) 的邻域内可微分,那么从点 \(\mathbf{a}\) 沿着 \(F\) 在该点的负梯度方向移动会使 \(F(\mathbf{x})\) 下降最快. 换句话说,如果

\[ \mathbf{a}_{n+1} = \mathbf{a}_n - \gamma \nabla F(\mathbf{a}_n) \]

其中 \(\gamma \in \mathbb{R}_+\) 是足够小的步长或学习率, 那么 \(F(\mathbf{a}_n) \geq F(\mathbf{a}_{n+1})\). 换言之, 我们从 \(\mathbf{a}\) 中减去 \(\gamma \nabla F(\mathbf{a})\), 因为我们希望朝着梯度的反方向移动, 朝着局部最小值的方向. 基于这一观察, 为了优化求解 \(F\) 的局部最小值, 我们从 \(\mathbf{x}_0\) 开始, 考虑序列 \(\mathbf{x}_0, \mathbf{x}_1, \mathbf{x}_2, \ldots\) 满足

\[ \mathbf{x}_{n+1} = \mathbf{x}_n - \gamma_n \nabla F(\mathbf{x}_n), \quad n \geq 0. \]

我们可以得到一个单调递减的序列

\[ F(\mathbf{x}_0) \geq F(\mathbf{x}_1) \geq F(\mathbf{x}_2) \geq \ldots, \]

并希望序列 \((\mathbf{x}_n)\) 收敛到所需的局部最小值. 其中步长 \(\gamma\) 的值允许在每次迭代时改变.

在对函数 \(F\) 的一些假设（例如\(F\) 是凸的）以及特定的 \(\gamma\) 选择下, 可以保证函数 \(F\) 收敛到局部最小值. 当函数 \(F\) 是凸的时, 所有局部最小值也是全局最小值,因此在这种情况下,梯度下降可以收敛到全局解.

在许多监督学习问题中,存在一个输出变量 \(y\) 和一个与其相关的输入变量 \(x\) 向量,它们之间存在某种概率分布关系.目标是找到一些函数 \(\hat{F}(x)\),它能够最好地从输入变量的值中近似输出变量.这通过引入某个损失函数 \(L(y, \hat{F}(x))\) 并在期望中将其最小化来形式化：

\[ \hat{F} = \underset{F}{\arg \min} \mathbb{E}_{x,y}[L(y, F(x))] \]

梯度提升方法假设 \(y\) 为实数值.它寻求以一系列来自某个类 \(H\)（称为基本（或弱）学习器）的函数 \(h_m(x)\) 的加权和形式来逼近 \(\hat{F}(x)\)：

\[ {\displaystyle {\hat {F}}(x)=\sum _{m=1}^{M}\gamma _{m}h_{m}(x)+{\mbox{const}}}. \]

通常,我们会得到一个已知样本值 \(x\) 和相应值 \(y\) 的训练集 \(\{(x_{1},y_{1}),\dots ,(x_{n},y_{n})\}\).根据经验风险最小化原则,该方法试图找到一个近似函数 \(\hat{F}(x)\) ,使其在训练集上损失函数的平均值最小化,即最小化经验风险.它通过从一个由常数函数 \(F_{0}(x)\) 组成的模型开始,并以贪婪的方式逐步扩展该模型来实现：

\[ F_{0}(x) = \underset{\gamma}{\arg \min} \sum_{i=1}^{n} L(y_{i}, \gamma) \]

\[ F_{m}(x) = F_{m-1}(x) + \left(\underset{h_{m}\in \mathcal{H}}{\operatorname{arg\,min}} \left[ \sum_{i=1}^{n} L(y_{i}, F_{m-1}(x_{i}) + h_{m}(x_{i})) \right] \right)(x) \]

对于 \(m \geq 1\),其中 \(h_{m} \in \mathcal{H}\) 是基本学习器函数.

不幸的是,对于一般的损失函数 \(L\),在每一步选择最佳函数 \(h_{m}\) 是一个计算上不可行的优化问题.因此,我们将我们的方法限制在问题的简化版本上.

这个想法是对这个最小化问题应用一个最陡降步（函数梯度下降）.

最陡降背后的基本思想是通过迭代 \(F_{m-1}(x)\) 来找到损失函数的局部最小值.事实上,损失函数的局部最大下降方向是负梯度.

因此,移动一个小量 \(\gamma\) 以使线性近似仍然有效：

\[ F_{m}(x) = F_{m-1}(x) - \gamma \sum_{i=1}^{n} \nabla_{F_{m-1}} L(y_{i}, F_{m-1}(x_{i})) \]

其中 \(\gamma > 0\).对于小的 \(\gamma\),这意味着 \(L(y_{i}, F_{m}(x_{i})) \leq L(y_{i}, F_{m-1}(x_{i}))\).

输入：训练集 \(\{(x_i, y_i)\}_{i=1}^{n}\),可微损失函数 \(L(y, F(x))\),迭代次数 \(M\).

算法：

1. 用常数值初始化模型： \[ F_0(x) = \underset{\gamma}{\arg\min} \sum_{i=1}^n L(y_i, \gamma). \]

2. 对于 \(m = 1\) 到 \(M\)：

• 计算所谓的伪残差： \[ r_{im} = -\left[\frac{\partial L(y_i, F(x_i))}{\partial F(x_i)}\right]_{F(x)=F_{m-1}(x)} \quad \text{对于} \, i=1,\ldots,n. \]

• 将基学习器（或弱学习器,例如树）调整到伪残差,即使用训练集 \(\{(x_i, r_{im})\}_{i=1}^n\) 进行训练.

• 通过解决以下一维优化问题计算乘子 \(\gamma_m\)： \[ \gamma_m = \underset{\gamma}{\operatorname{arg\,min}} \sum_{i=1}^n L\left(y_i, F_{m-1}(x_i) + \gamma h_m(x_i)\right). \]

  • 更新模型： \[ F_m(x) = F_{m-1}(x) + \gamma_m h_m(x). \]

输出：\(F_M(x)\).