新加坡国立大学李千骁：动力学系统与监督学习的关系探索

2023-08-19 20:38分类：茶道阅读：

2019年10月31日下午，在北京智源大会的“人工智能的数理基础专题论坛”上，学者李千骁做了题为《A Dynamic System Approach To DeepLearning-Approximation,Optimization and Generalization》（即：动力学系统与监督学习中的优化/逼近/泛化的关系探索）的主题演讲。李千骁，新加坡国立大学数学系助理教授，新加坡高性能计算研究院研究员。本次讲座，李千骁从数学中一个非常重要的领域-动力学系统出发，为我们揭开深度学习的优化、逼近以及泛化的面纱，并且为我们展示了他与北京大学、普林斯顿大学、新加坡大学的同事共同研究的成果。以下是智源编辑为大家整理的讲座内容，请大家阅读。

整理：钱小鹅

编辑：王炜强

背景

众所周知，从样本是否标记我们可以将机器学习分为监督学习和无监督学习。监督学习即输入标记样本，通过这些样本训练得到分类器的参数（或者映射关系），最终我们可以用分类器进行数据的回归和分类。那么，如果我们采用（连续）动力学系统来描述，那么基本的监督学习则可以表示为：

F*：X→Y

其中函数的输入为X?R^d（比如：图片，时序信息等），输出为（比如：类别，数值预测值等）。

图1：监督学习典型实例

不妨我们考虑输入-输出为K个样本对{x^i,y^i=F(x^i)}_i^K。我们的目标是使用已知的数据逼近X到Y的映射。我们首先定义假设空间H：

回归以及分类的线性模型：

浅层神经网络：

深层神经网络：

简单来说，训练（学习）的过程即是从假设空间中找到最优解F*来逼近，常用的求解损失函数的风险最小化方法我们介绍以下两大类：

Empirical risk minimization(ERM)

Population risk minimization(PRM)

通常情况下，我们想求解的是PRM问题，但是我们只能求解ERM问题，而ˉF与F ?之间的“鸿沟”即为我们常常遇到的泛化问题。

图2：监督学习三个逼近解的关系图释

深度学习有什么新发现？

正如我们上述提到的假设空间，在深度学习领域，假设空间是非常复杂的，我们想要做的是从数学理论这一方面出发，弄清楚组合的构成。那么其背后的数学原理可以分为三方面：

Approximation: approximation rates for deep NNsand decomposition to near-identity function.
Optimization: back-propagation and related work.
Generalization: over-parameterization.

而解决如上三方面的问题，在数学中恰好有一个领域：动力学系统。我们可以使用动力学系统中的流向地图(flow-maps)来表示假设空间。下面我们给出两个简单的例子来说明流向地图和假设空间之间的关系。

1.在动力学系统框架中，我们将输入

作为动力学微分方程

的初始条件。其中为控制（训练）参数，f的形式是机器学习模型中选择的（比如，在深度学习中，f即为线性传播函数以及非线性的激活函数的组合）并且确保f以及?xf均为连续的（注：Clarke, 2005[5]提出了比文中给出的连续性更弱的条件）。那么该流向地图的假设空间可以写成：

其中g: X→Y与输出空间匹配。

2. 另一个非常典型的例子为残差网络，该网络是非常经典的深度学习网络框架，而这个网络框架我们可以将其写为如下格式的偏微分方程(假设残差网络为T层)：

不难看出，上述公式与欧拉离散格式的差分方程：

所得的流向地图非常接近，唯一不同之处，也是我们比较关心的问题是，前向动力学表示为偏微分方程，残差网络表达式为差分方程。当然，目前有很多学术论文及科研工作者都在研究这方面的内容，这样的例子可以列举很多，感兴趣的读者可以阅读相关的论文。本次讲座中，李千骁着重给我们介绍了由此形成的动力学微分方程的优化、逼近和泛化问题，具体内容如下：

Optimization:(mean-field)optimal control
Approximation: controllability and approximationof homeomorphisms by flow-maps
Generalization: random approximations of zeros ofequations

首先我们介绍优化：平均场最优控制。

我们不妨使用微分方程

来描述状态动力学，其中初始条件x_0，因此，使用流图假设空间的PRM问题可以表述为：

注意：我们将Φ(g(?),?)写成Φ(?,?)。

这是一个非常典型的平均场控制问题，因为我们需要“训练”得到的参数θ并不是一个值，而是输入和输出的全部分布情况。在这个问题中，有两个问题是需要我们关心和解决的：

Necessary conditions for optimality

考虑

满足

那么θ*需要满足哪些条件呢？

首先我们定义哈密顿算子H:R^d×R^d×Θ→R，其中：

我们给出如图3所示定理：

图3：定理Mean-field PMP

从上图中我们不难看出PMP具有如下重要属性：

不需要任何与相关的导数；
参数集是通用的；
如果和已知，那么最大值条件是关于t逐点并且解耦的；
训练过程不需要梯度下降；
可以训练量化网络；
训练过程可以并行计算；

这些对于深度学习网络的训练过程都是非常好的属性，可以加速网络训练，提高计算机的利用效率。

Sufficient conditions for optimality

首先我们回顾PRM问题:

我们将其嵌入一个更大空间中：

那么PRM问题可以转为上述问题求解P(0,μ)。

我们定义值函数(value function) v(t,μ)为P(t,μ)的最优结果。我们的目标是推导出 v(t,μ)的递推式，如果满足条件则为最优值和最优控制，这是动态规划的方法[Bellman 1966][5]。因此我们有图4给出的定理：

图4：定理 Mean-field HJB Equation

接下来，我们讨论逼近问题。

回顾我们流图的假设空间：

取所有时间的并集，表示为：

问题来了，在空间中，函数逼近空间有多大呢？

我们不妨重新将空间表示为：

其中我们将

称为控制簇。

我们发出这样的疑问？如果F是简单的控制簇，H是否仍然是稠密的？

不妨从简单出发，我们先考虑一维问题：

我们定义g(x)=x，从ODE(常微分方程)解的存在性和唯一性，直接观察得到（如图5）：

图5: A Negative Result In One Dimension

由这个例子，我们继续引申思考：那么F满足哪些属性时，可以保证H空间中有任意连续增函数的逼近解呢？回答这个问题，我们首先给出一个定义（如图6）：

图6: 定义Well Function

了解了well function的定义后，李千骁给出他在[L,lin & Shen, 2019][4]中证明的定理来说明F满足的属性。

图7:定理F满足的属性

从定理中我们可以看出，F需要满足三个条件，但是这三个条件其实很容易满足，根据上述定理，我们可以写出目前深度学习中常用激活函数的控制簇：

那么高维问题又将会如何？让人惊喜的是：

一维的结果可以扩展到任意d维
对于L^p逼近，一维中的条件“增函数”将不再需要.[Brenier and Gangbo, 2003][6]

我们仍然首先给出一个新的定义(如图8)：

图8：定义 Broadcasted Control Family

李千骁在其论文中给出了高维空间中的逼近条件（如图9）:

图9:定理高维空间中逼近的必要条件

最后，我们讨论泛化问题。

首先，我们回顾发现，ERM和PRM并不相同(如图10)：

图10：PRM 和 ERM 的定义回顾

泛化问题即是：

给定ERM的解θ^(N,*)以及PRM的解θ^*,我们是否可以找到|J(θ^(N,*))-J(θ^*)|的确界？

在基于流图的假设空间中，这并不是一件小事，因为经典学习理论表明：

然而，对于任意T，我们的假设空间是无限维的。因此，有必要考虑一个问题：我们是否可以有一个基本的泛化估计？关于这个问题，李千骁也给我们介绍了他的最新研究成果(如图11)：

图11：定理时间连续下泛化的基本结果

结语

本次讲座，李千骁为我们带来了从动力学系统研究深度学习的优化、逼近以及泛化问题(如图12中给出的讲座总结和展望)，并发现了这些问题中有很多方面的理论是相通的，算法实现上也可以做很好的迁移。

图12：Summary and Outlook

当然还有很多问题值得我们继续探索和思考，比如：什么样的动力学系统是足够模拟深度学习的所有实例？如何将上述的理论知识运用到深度学习的数值逼近中？函数是否可以做进一步的简化？逼近属性是否在任意情况都需要全部满足？算法中涉及到的复杂度如何计算等，感兴趣的读者可以继续思考探索。

参考文献

[1]Qianxiao Li, Long Chen, Cheng Tai, and Weinan E (2018). “MaximumPrinciple Based Algorithms for Deep Learning”. In: Journalof Machine Learning Research 18.1, pp. 1–29. ISSN: 1532-4435.

[2]Qianxiao Li and Shuji Hao (2018). “An Optimal Control Approach to Deep Learning andApplications to Discrete-Weight Neural Networks”. In: Proceedingsof the 35th International Conference on Machine Learning. Vol. 80.Proceedings of Machine Learning Research. PMLR, pp. 2985–2994.

[3]Weinan E, Jiequn Han, and Qianxiao Li (2019). “Amean-field optimal control formulation of deep learning”. In: Researchin the Mathematical Sciences 6.1, p. 10. ISSN: 2522-0144.

[4]Qianxiao Li, Ting Lin, and ZuoweiShen (2019). “Approximation of Functions by Dynamical Systems”. In: Inpreparation.?

[5]Richard Bellman(1966).“DynamicProgramming”.In: Science 01 June. Vol. 153. Issue 3731. pp. 34-37.

[6]Brenier Y, Gangbo W.(2003).“L-pApproximation of maps by diffeomorphisms”. In: Springer-Verlag. ISSN:0944-2699.