2020/02/20 16:12

Joshua Chou作者Joni Zhong编辑魔王翻译

如何在黎曼流形上避开鞍点？本文带你了解优化背后的数学知识

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

引言

「优化」通常是指将函数最大化或最小化，而函数的集合通常表示遵循约束条件的可选择范围。我们可以通过对比集合内不同的函数选择来确定哪个函数是「最优」的。

学习是模型迭代地学习最小化某个误差函数或者最大化某个奖励函数的过程。拿用于分类任务的简单线性回归为例，误差函数是模型输出和数据真值输出之间的均方差，学习过程即找出线性函数 y = a^Tx + b 的系数 a_i 和 b_i，以最小化 y（模型输出）和 y*（真值输出）间的误差。例如，学习（即优化）通常使用梯度下降算法通过反向传播来迭代进行。在每一次迭代中，系数 a_i 和 b_i 都是（所有可能 a_i 和 b_i 值集合中的）一个选择，算法将学习到能够最小化误差函数的下一组系数。因此，模型的学习过程归根结底还是优化问题。

论文《Escaping from saddle points on Riemannian manifolds》深入探索了优化问题的细节，这对理解机器学习的底层数学知识非常重要。

在经典的最小化任务中，基于梯度的优化方法是寻找局部极小值的最常用方法。「陷入鞍点」问题就出现在基于梯度的优化方法中。优化问题旨在寻找能使目标函数达到局部极小值的驻点，而鞍点是不能达到局部极小值的驻点。因此，了解如何识别并避开鞍点至关重要。这篇论文介绍了一种新方法，能够针对满足流形约束的目标函数识别并避开鞍点。

设置

该论文考虑在平滑流形 M 上最小化非凸平滑函数：

其中 M 是一个 d 维平滑流形，f 是二次可微函数，Hessian 符合 ρ-Lipschitz。为此类问题寻找全局最小值是一项挑战，而这篇论文利用一阶优化方法找出近似的二阶驻点（达到局部极小值）。在抵达驻点时，作者引入一种方法来识别该驻点是鞍点还是局部极小值。此外，作者提出一种方法来避开鞍点，并尝试将目标函数收敛至局部极小值。

随着越来越多的应用被建模为大规模优化问题，较简单的一阶方法变得越来越重要。因此，该论文使用一阶方法处理非凸问题，并查看其效果。具体而言，作者对黎曼流形上的非凸问题执行优化。

背景知识

在深入了解该论文之前，我们先要理解一些底层数学概念。理想情况下，这篇论文要求读者对高斯几何有基础了解，即三维欧几里德空间中曲线和表面的几何。此外，微分几何的知识也很重要。不过，我会尝试解释这篇论文中某些术语的意义。

每个平滑的 d 维流形 M 都局部微分同胚于 R^n。M 中每个点周围都有一个平坦的（小型）邻域。因此，它遵循 R^n 上的欧几里德度量。从视觉上来看，这意味着 M 中的每个点周围都有一个曲率为零的小型邻域和欧几里德度量。

接下来，我们需要了解可微流形 M 在 M 内的点 x 处的切空间 TxM。切空间是一个维度与 M 相同的向量空间。读者需要了解这个概念：在标准 R^n 中，点 x ∈ R^n 处的切向量 v 可解释为：对围绕 x 局部定义的实值函数执行的一阶线性可微运算。而这一点可以泛化至流形设置中。

现在我们来看黎曼流形。黎曼流形具备黎曼度量。黎曼度量为我们提供了每个切空间上的标量积，可用于衡量流形上曲线的角度和长度。它定义了距离函数，并自然而然地将流形转换为度量空间。

假设读者了解曲率这一概念，我们来看黎曼曲率张量（Riemann curvature tensor）和黎曼流形的截面曲率。我们可以把黎曼曲率张量理解为流形的曲率，这与我们对曲率的直观理解是一致的。

曲率

读者可以在标准来源中找到截面曲率的定义，其思路是向平面分配曲率。切空间中平面 p 的截面曲率与初始方向在 P 中的测地线（geodesic）所掠过表面的高斯曲率成正比。直观上，这是一个穿过给定平面的二维切片，你需要度量其二维曲率。

符号

该论文关注平滑的 d 维黎曼流形 (M,g)，该流形使用黎曼度量 g。点 x ∈ M 的切空间是 TxM。邻域被定义为：Bx(r) = { v ∈ TxM, ||v|| ≤ r }，即以 0 为中心、半径 r 位于切空间 TxM 内的球。在任意点 x ∈ M，度量 g 自然地推导出切空间 < · , · > : TxM x TxM → R 上的内积。黎曼曲率张量用 R(x)[u, v] 来表示，其中 x ∈ M，u, v ∈ TxM。截面曲率是 K(x)[u, v]，x ∈ M, u, v ∈ TxM，其定义如下：

该论文用 d(x, y) 表示 M 中两个点之间的距离（根据黎曼度量得出）。测地线 γ : R → M 是一条等速曲线，其长度等于 d(x, y)，即测地线是连接 x 和 y 的最短路径。

指数映射 Exp_x (v) 将 v ∈ TxM 映射到 y ∈ M，则存在测地线 γ，使 γ(0) = x，γ(1) = y，(d/dt)γ(0) = v。这个概念很难理解，读者可以按照下面的方法理解指数映射。

将指数映射看作沿着切向量 v 的方向将点 x 推动一小段距离。如果我们可以将该点沿着测地线 γ 推动 1 个距离单位，那么我们将到达点 y。

另一个理解方式是投影。假设点 p1 的坐标为 (x_1, y_1, z_1)，z_1 = 0，即 p1 在 x-y 平面上。向 p1 添加向量 p2 (x_2, y_2, z_2)，其中 z_2 不等于 0，即 p3 = p1+p2。现在，使用投影定理，将 p3 投影回 x-y 平面得到 p4。根据投影定理，p4 与 p1 间的距离最短。测地线即球面或其他曲面或流形上两点之间的最短路线。指数映射类似于该示例中的投影算子。

主要算法

在黎曼流形上执行优化的主要算法如下所示：

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

算法 1 依赖流形的指数映射，对于易于计算指数映射的情况很有用（而多种常见流形的指数映射是容易计算的）。作者用可视化的方式进行了展示：

图 1：鞍点位于球面上的函数 f。

函数 f 的定义是：f(x) = (x_1)^2 − (x_2)^2 + 4(x_3)^2，如图 1 所示。该算法在 x_0 处进行初始化，x_0 是鞍点。在其切空间中向 x_0 添加噪声，然后计算指数映射，将点 x_0 映射回流形上的点 x_1。然后算法运行黎曼梯度下降，并在 x* 处停止，x* 即局部极小值。

主定理背后的概念

该算法背后的思路很简单，但底层证明较为复杂。我尝试简要直观地解释结果并提供一些见解。详细证明及相关文献参见原论文。

假设

该论文作出了多项假设，前两个假设关于 f，最后一个假设关于 M：

简要来讲，利普希茨连续是连续性的定量版本。给出 x 和 y 之间的距离 d(x,y)，则利普希茨函数对 f(x) 和 f(y) 之间的距离设置定量上限。如果 C 是 f 的利普希茨值，则该距离至多为 C×d(x, y)。假设 1 和假设 2 是梯度和 Hessian 的标准利普希茨条件，即常数 β 和 ρ 分别描述梯度和 Hessian 在「最糟糕情况下」的分离情况。这些假设主要是为了确保梯度和 Hessian 可微分。

类似地，假设 3 对 M 的截面曲率设置了上限。直观来看，该假设旨在确保指数映射不会无限增大。例如，对于点 x∈M，其切空间 TxM 和 x 周围的曲率是极大的。TxM 中点的指数映射 Exp_x (v) 可能得到点 y∈M，y 距离 x 非常远。这样算法就没用了，因为该算法仅希望稍微离开鞍点到达另一个点，以便避开鞍点，向另一个驻点前进。

主定理

主定理如下所示。本质上，该定理确保目标函数（向驻点收敛）的下降速率。证明策略是，经过特定次数的迭代后，当逼近鞍点时，该函数的值大概率会下降。

上图看起来比较复杂，我们可以从中得到以下信息：

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

该论文的证明策略是，经过特定次数的迭代后，当逼近鞍点时，该函数的值大概率会下降。作者进一步证明，完成扰动和执行算法的 T 步后，如果迭代仍然远离鞍点，则函数会下降。

结论

该论文研究了受限优化问题，即对满足多个流形约束条件和一些关于 f(x) 假设的函数 f(x) 执行最小化。该研究证明，只要函数和流形具备恰当的平滑度，则扰动黎曼梯度下降算法能够避开鞍点。

入门鞍点模型优化数学

相关数据

机器学习技术

机器学习是人工智能的一个分支，是一门多领域交叉学科，涉及概率论、统计学、逼近论、凸分析、计算复杂性理论等多门学科。机器学习理论主要是设计和分析一些让计算机可以自动“学习”的算法。因为学习算法中涉及了大量的统计学理论，机器学习与推断统计学联系尤为密切，也被称为统计学习理论。算法设计方面，机器学习理论关注可以实现的，行之有效的学习算法。

来源：Mitchell, T. (1997). Machine Learning. McGraw Hill.

参数技术

在数学和统计学裡，参数（英语：parameter）是使用通用变量来建立函数和变量之间关系（当这种关系很难用方程来阐述时）的一个数量。

来源：维基百科

收敛技术

在数学，计算机科学和逻辑学中，收敛指的是不同的变换序列在有限的时间内达到一个结论（变换终止），并且得出的结论是独立于达到它的路径（他们是融合的）。通俗来说，收敛通常是指在训练期间达到的一种状态，即经过一定次数的迭代之后，训练损失和验证损失在每次迭代中的变化都非常小或根本没有变化。也就是说，如果采用当前数据进行额外的训练将无法改进模型，模型即达到收敛状态。在深度学习中，损失值有时会在最终下降之前的多次迭代中保持不变或几乎保持不变，暂时形成收敛的假象。

来源：Wikipedia Google ML glossary

张量技术

张量是一个可用来表示在一些矢量、标量和其他张量之间的线性关系的多线性函数，这些线性关系的基本例子有内积、外积、线性映射以及笛卡儿积。其坐标在维空间内，有个分量的一种量，其中每个分量都是坐标的函数，而在坐标变换时，这些分量也依照某些规则作线性变换。称为该张量的秩或阶（与矩阵的秩和阶均无关系）。在数学里，张量是一种几何实体，或者说广义上的“数量”。张量概念包括标量、矢量和线性算子。张量可以用坐标系统来表达，记作标量的数组，但它是定义为“不依赖于参照系的选择的”。张量在物理和工程学中很重要。例如在扩散张量成像中，表达器官对于水的在各个方向的微分透性的张量可以用来产生大脑的扫描图。工程上最重要的例子可能就是应力张量和应变张量了，它们都是二阶张量，对于一般线性材料他们之间的关系由一个四阶弹性张量来决定。

来源：维基百科

线性回归技术

在现实世界中，存在着大量这样的情况：两个变量例如X和Y有一些依赖关系。由X可以部分地决定Y的值，但这种决定往往不很确切。常常用来说明这种依赖关系的最简单、直观的例子是体重与身高，用Y表示他的体重。众所周知，一般说来，当X大时，Y也倾向于大，但由X不能严格地决定Y。又如，城市生活用电量Y与气温X有很大的关系。在夏天气温很高或冬天气温很低时，由于室内空调、冰箱等家用电器的使用，可能用电就高，相反，在春秋季节气温不高也不低，用电量就可能少。但我们不能由气温X准确地决定用电量Y。类似的例子还很多，变量之间的这种关系称为“相关关系”，回归模型就是研究相关关系的一个有力工具。

来源：王松桂等编线性统计模型线性回归与方差分析高等教育出版社 Wikipedia

梯度下降技术

梯度下降是用于查找函数最小值的一阶迭代优化算法。要使用梯度下降找到函数的局部最小值，可以采用与当前点的函数梯度（或近似梯度）的负值成比例的步骤。如果采取的步骤与梯度的正值成比例，则接近该函数的局部最大值，被称为梯度上升。

来源：Vapnik V. N. (2000). The Nature of Statistical Learning Theory. Information Science and Statistics. Springer-Verlag.Wikipedia

映射技术

映射指的是具有某种特殊结构的函数，或泛指类函数思想的范畴论中的态射。逻辑和图论中也有一些不太常规的用法。其数学定义为：两个非空集合A与B间存在着对应关系f，而且对于A中的每一个元素x，B中总有有唯一的一个元素y与它对应，就这种对应为从A到B的映射，记作f：A→B。其中，y称为元素x在映射f下的象，记作：y=f(x)。x称为y关于映射f的原象*。*集合A中所有元素的象的集合称为映射f的值域，记作f(A)。同样的，在机器学习中，映射就是输入与输出之间的对应关系。

来源：Wikipedia

目标函数技术

目标函数f(x)就是用设计变量来表示的所追求的目标形式，所以目标函数就是设计变量的函数，是一个标量。从工程意义讲，目标函数是系统的性能标准，比如，一个结构的最轻重量、最低造价、最合理形式；一件产品的最短生产时间、最小能量消耗；一个实验的最佳配方等等，建立目标函数的过程就是寻找设计变量与目标的关系的过程，目标函数和设计变量的关系可用曲线、曲面或超曲面表示。

来源：百度百科