找出一个二维数组中的鞍点的流程图_如何在黎曼流形上避开鞍点？本文带你了解优化背后的数学知识...

机器之心原创

作者&＃xff1a;Joshua Chou
编辑&＃xff1a;Joni Zhong翻译&＃xff1a;魔王

在一篇名为《Escaping from saddle points on Riemannian manifolds》的论文中&＃xff0c;来自华盛顿大学、加州大学伯克利分校的研究人员深入探索了优化问题的细节&＃xff0c;这对理解机器学习底层的数学知识非常重要。本文是对该论文的解读。

引言
「优化」通常是指将函数最大化或最小化&＃xff0c;而函数的集合通常表示遵循约束条件的可选择范围。我们可以通过对比集合内不同的函数选择来确定哪个函数是「最优」的。
学习是模型迭代地学习最小化某个误差函数或者最大化某个奖励函数的过程。拿用于分类任务的简单线性回归为例&＃xff0c;误差函数是模型输出和数据真值输出之间的均方差&＃xff0c;学习过程即找出线性函数 y &＃61; a^Tx &＃43; b 的系数 a_i 和 b_i&＃xff0c;以最小化 y(模型输出)和 y*(真值输出)间的误差。例如&＃xff0c;学习(即优化)通常使用梯度下降算法通过反向传播来迭代进行。在每一次迭代中&＃xff0c;系数 a_i 和 b_i 都是(所有可能 a_i 和 b_i 值集合中的)一个选择&＃xff0c;算法将学习到能够最小化误差函数的下一组系数。因此&＃xff0c;模型的学习过程归根结底还是优化问题。
论文《Escaping from saddle points on Riemannian manifolds》深入探索了优化问题的细节&＃xff0c;这对理解机器学习的底层数学知识非常重要。
在经典的最小化任务中&＃xff0c;基于梯度的优化方法是寻找局部极小值的最常用方法。「陷入鞍点」问题就出现在基于梯度的优化方法中。优化问题旨在寻找能使目标函数达到局部极小值的驻点&＃xff0c;而鞍点是不能达到局部极小值的驻点。因此&＃xff0c;了解如何识别并避开鞍点至关重要。这篇论文介绍了一种新方法&＃xff0c;能够针对满足流形约束的目标函数识别并避开鞍点。设置
该论文考虑在平滑流形 M 上最小化非凸平滑函数&＃xff1a;

其中 M 是一个 d 维平滑流形&＃xff0c;f 是二次可微函数&＃xff0c;Hessian 符合 ρ-Lipschitz。为此类问题寻找全局最小值是一项挑战&＃xff0c;而这篇论文利用一阶优化方法找出近似的二阶驻点(达到局部极小值)。在抵达驻点时&＃xff0c;作者引入一种方法来识别该驻点是鞍点还是局部极小值。此外&＃xff0c;作者提出一种方法来避开鞍点&＃xff0c;并尝试将目标函数收敛至局部极小值。
随着越来越多的应用被建模为大规模优化问题&＃xff0c;较简单的一阶方法变得越来越重要。因此&＃xff0c;该论文使用一阶方法处理非凸问题&＃xff0c;并查看其效果。具体而言&＃xff0c;作者对黎曼流形上的非凸问题执行优化。背景知识
在深入了解该论文之前&＃xff0c;我们先要理解一些底层数学概念。理想情况下&＃xff0c;这篇论文要求读者对高斯几何有基础了解&＃xff0c;即三维欧几里德空间中曲线和表面的几何。此外&＃xff0c;微分几何的知识也很重要。不过&＃xff0c;我会尝试解释这篇论文中某些术语的意义。
每个平滑的 d 维流形 M 都局部微分同胚于 R^n。M 中每个点周围都有一个平坦的(小型)邻域。因此&＃xff0c;它遵循 R^n 上的欧几里德度量。从视觉上来看&＃xff0c;这意味着 M 中的每个点周围都有一个曲率为零的小型邻域和欧几里德度量。
接下来&＃xff0c;我们需要了解可微流形 M 在 M 内的点 x 处的切空间 TxM。切空间是一个维度与 M 相同的向量空间。读者需要了解这个概念&＃xff1a;在标准 R^n 中&＃xff0c;点 x ∈ R^n 处的切向量 v 可解释为&＃xff1a;对围绕 x 局部定义的实值函数执行的一阶线性可微运算。而这一点可以泛化至流形设置中。
现在我们来看黎曼流形。黎曼流形具备黎曼度量。黎曼度量为我们提供了每个切空间上的标量积&＃xff0c;可用于衡量流形上曲线的角度和长度。它定义了距离函数&＃xff0c;并自然而然地将流形转换为度量空间。
假设读者了解曲率这一概念&＃xff0c;我们来看黎曼曲率张量(Riemann curvature tensor)和黎曼流形的截面曲率。我们可以把黎曼曲率张量理解为流形的曲率&＃xff0c;这与我们对曲率的直观理解是一致的。
曲率
读者可以在标准来源中找到截面曲率的定义&＃xff0c;其思路是向平面分配曲率。切空间中平面 p 的截面曲率与初始方向在 P 中的测地线(geodesic)所掠过表面的高斯曲率成正比。直观上&＃xff0c;这是一个穿过给定平面的二维切片&＃xff0c;你需要度量其二维曲率。符号
该论文关注平滑的 d 维黎曼流形 (M,g)&＃xff0c;该流形使用黎曼度量 g。点 x ∈ M 的切空间是 TxM。邻域被定义为&＃xff1a;Bx(r) &＃61; { v ∈ TxM, ||v|| ≤ r }&＃xff0c;即以 0 为中心、半径 r 位于切空间 TxM 内的球。在任意点 x ∈ M&＃xff0c;度量 g 自然地推导出切空间 <· , · > : TxM x TxM → R 上的内积。黎曼曲率张量用 R(x)[u, v] 来表示&＃xff0c;其中 x ∈ M&＃xff0c;u, v ∈ TxM。截面曲率是 K(x)[u, v]&＃xff0c;x ∈ M, u, v ∈ TxM&＃xff0c;其定义如下&＃xff1a;

该论文用 d(x, y) 表示 M 中两个点之间的距离(根据黎曼度量得出)。测地线 γ : R → M 是一条等速曲线&＃xff0c;其长度等于 d(x, y)&＃xff0c;即测地线是连接 x 和 y 的最短路径。
指数映射 Exp_x (v) 将 v ∈ TxM 映射到 y ∈ M&＃xff0c;则存在测地线 γ&＃xff0c;使 γ(0) &＃61; x&＃xff0c;γ(1) &＃61; y&＃xff0c;(d/dt)γ(0) &＃61; v。这个概念很难理解&＃xff0c;读者可以按照下面的方法理解指数映射。
将指数映射看作沿着切向量 v 的方向将点 x 推动一小段距离。如果我们可以将该点沿着测地线 γ 推动 1 个距离单位&＃xff0c;那么我们将到达点 y。
另一个理解方式是投影。假设点 p1 的坐标为 (x_1, y_1, z_1)&＃xff0c;z_1 &＃61; 0&＃xff0c;即 p1 在 x-y 平面上。向 p1 添加向量 p2 (x_2, y_2, z_2)&＃xff0c;其中 z_2 不等于 0&＃xff0c;即 p3 &＃61; p1&＃43;p2。现在&＃xff0c;使用投影定理&＃xff0c;将 p3 投影回 x-y 平面得到 p4。根据投影定理&＃xff0c;p4 与 p1 间的距离最短。测地线即球面或其他曲面或流形上两点之间的最短路线。指数映射类似于该示例中的投影算子。主要算法
在黎曼流形上执行优化的主要算法如下所示&＃xff1a;

算法 1 看起来很吓人&＃xff0c;但是作者给出的总结对于理解该算法机制很有用。算法 1 按照以下步骤运行&＃xff1a;

算法 1 依赖流形的指数映射&＃xff0c;对于易于计算指数映射的情况很有用(而多种常见流形的指数映射是容易计算的)。作者用可视化的方式进行了展示&＃xff1a;

图 1&＃xff1a;鞍点位于球面上的函数 f。
函数 f 的定义是&＃xff1a;f(x) &＃61; (x_1)^2 − (x_2)^2 &＃43; 4(x_3)^2&＃xff0c;如图 1 所示。该算法在 x_0 处进行初始化&＃xff0c;x_0 是鞍点。在其切空间中向 x_0 添加噪声&＃xff0c;然后计算指数映射&＃xff0c;将点 x_0 映射回流形上的点 x_1。然后算法运行黎曼梯度下降&＃xff0c;并在 x* 处停止&＃xff0c;x* 即局部极小值。主定理背后的概念
该算法背后的思路很简单&＃xff0c;但底层证明较为复杂。我尝试简要直观地解释结果并提供一些见解。详细证明及相关文献参见原论文。假设
该论文作出了多项假设&＃xff0c;前两个假设关于 f&＃xff0c;最后一个假设关于 M&＃xff1a;

简要来讲&＃xff0c;利普希茨连续是连续性的定量版本。给出 x 和 y 之间的距离 d(x,y)&＃xff0c;则利普希茨函数对 f(x) 和 f(y) 之间的距离设置定量上限。如果 C 是 f 的利普希茨值&＃xff0c;则该距离至多为 C×d(x, y)。假设 1 和假设 2 是梯度和 Hessian 的标准利普希茨条件&＃xff0c;即常数 β 和 ρ 分别描述梯度和 Hessian 在「最糟糕情况下」的分离情况。这些假设主要是为了确保梯度和 Hessian 可微分。
类似地&＃xff0c;假设 3 对 M 的截面曲率设置了上限。直观来看&＃xff0c;该假设旨在确保指数映射不会无限增大。例如&＃xff0c;对于点 x∈M&＃xff0c;其切空间 TxM 和 x 周围的曲率是极大的。TxM 中点的指数映射 Exp_x (v) 可能得到点 y∈M&＃xff0c;y 距离 x 非常远。这样算法就没用了&＃xff0c;因为该算法仅希望稍微离开鞍点到达另一个点&＃xff0c;以便避开鞍点&＃xff0c;向另一个驻点前进。主定理
主定理如下所示。本质上&＃xff0c;该定理确保目标函数(向驻点收敛)的下降速率。证明策略是&＃xff0c;经过特定次数的迭代后&＃xff0c;当逼近鞍点时&＃xff0c;该函数的值大概率会下降。

上图看起来比较复杂&＃xff0c;我们可以从中得到以下信息&＃xff1a;

1. 大 O 符号和步长规则都与 β 相关&＃xff0c;就此我们可以得出&＃xff1a;梯度的利普希茨常数 β 越大&＃xff0c;算法收敛时间就越长。
2. ρ 与参数 ϵ 直接相关&＃xff0c;扰动后的黎曼梯度下降(perturbed Riemannian gradient descent)算法将以 1/(2 ϵ^2) 的速率避开鞍点。
3. 流形的维度是影响 ϵ 的另一个参数。我们可以看到 d 以对数的方式影响收敛速率。

该论文的证明策略是&＃xff0c;经过特定次数的迭代后&＃xff0c;当逼近鞍点时&＃xff0c;该函数的值大概率会下降。作者进一步证明&＃xff0c;完成扰动和执行算法的 T 步后&＃xff0c;如果迭代仍然远离鞍点&＃xff0c;则函数会下降。结论
该论文研究了受限优化问题&＃xff0c;即对满足多个流形约束条件和一些关于 f(x) 假设的函数 f(x) 执行最小化。该研究证明&＃xff0c;只要函数和流形具备恰当的平滑度&＃xff0c;则扰动黎曼梯度下降算法能够避开鞍点。