首届国际理论计算机联合大会（International Joint Conference on Theoretical Computer Science，IJTCS）于2020年8月17日-22日在线上举行，主题为“理论计算机科学领域的最新进展与焦点问题”，由北京大学与中国工业与应用数学学会（CSIAM）、中国计算机学会（CCF）、国际计算机学会中国委员会（ACM China Council）联合主办，北京大学前沿计算研究中心承办。

 

　　8月18-22日，大会“机器学习理论”分论坛如期举行，清华大学李建副教授主持。小编为大家带来论坛精彩回顾。

 

On Generalization and Implicit Bias of Gradient Methods in Deep Learning
李建，清华大学

 

　　深度神经⽹络在许多应⽤场景中都有着优异的表现，但其背后的原因却仍待⼈们探索。本次报告从泛化误差与隐式偏向两个⻆度对深度学习中的梯度⽅法进⾏了讨论。

 

　　由于深度神经⽹络的参数远多于训练数据的数量，传统学习理论中的泛化误差如 VC 维数与拉德⻢赫复杂度⽆法有效解释其泛化能⼒。讲者提出了⼀种新的 Bayes-Stability 框架，并⽤其得到了随机梯度 Langevin 动⼒学（SGLD）优化算法的泛化误差的界。相⽐于前⼈的⼯作，所给出的界优化掉了较⼤的 Lipschitz 常数，具有较为简单的证明与良好的拓展性，并能够对 Zhang 等⼈16年的实验做出较好的解释。讲者也在多个⽹络架构与数据集上验证了结果。

 

　　设想⼀个分类问题，多种边界的划分⽅式均能够得到相同的分类结果，但优化算法所得的结果往往具有着某些特殊性质，如⽤梯度下降的⽅法完成⼆分类会得到满⾜ svm 问题 maximum margin 的解，这种倾向被称为隐式偏向（implicit bias），其对理解深度神经⽹络具有着重要的作⽤。在分类问题中，需要⾜够⼤的 margin 来进⾏计算，但对于同质的⽹络，成倍放⼤数据的值也会导致 margin 的成倍放⼤，⽽当 margin 过⼤时亦将给训练带来不便，因⽽讲者提出了 smoothed normalized margin 以解决此问题，并证明通过梯度下降的⽅法对同质⽹络进⾏训练时，其与正常的 margin 会收敛到相同的 KKT 点。在报告的最后，讲者讨论了训练时间⻓短对模型鲁棒性的影响，认为训练时间的增⻓可能会提⾼模型的鲁棒性。

 

Provable Representation Learning in Deep Learning
Jason Lee, Princeton University

 

　　讲者认为深度学习的成功在于它能学到有效的特征表示 （representation）。这些特征表示可以迁移到其他任务中，也可以在无标注的数据集中学习。这是其他机器学习算法做不到的，例如随机森林，核方法等。表示学习在无数领域取得了成功，例如迁移学习，元学习，强化学习，语言模型，自监督训练，其他数据集不足的领域等等。

 

　　Maurer 和 Baxter 研究了表示学习的理论建模与泛化界。然而他们结果的最大问题在于他们给出的泛化界中完全没有体现出来每个任务中样本数量产生的影响，因此过于宽松，完全不能用于解释现实中表示学习的优秀效果。讲者及其合作者研究的主要贡献为，通过增加两条较为自然的假设，证明了和普通监督学习任务一样紧的下界。

 

　　第二部分是关于自监督学习下的表示学习。现实情境中很多时候并没有有标记的数据，此时常用的手段是直接从数据中设计标记，然后学习。通常来说是利用输入的其他部分去预测收入的被“挖掉”的部分，该方法在计算机视觉，自然语言处理中都有应用，且效果优异，甚至超过部分监督学习算法。讲者及其合作者选择对图片补全任务进行理论分析，在条件独立性假设下，理论证明了自监督学习的确能学到有效的表示。

 

Understanding Deep "Alchemy"
朱占星，北京大学

 

　　深度学习的成就一定程度上依赖于工程上的设计技巧，而缺失理论分析，因此围绕深度学习科学性的争论一直没有得到解决，限制了其在理论和应用层面的进一步发展。本次报告介绍了讲者及其合作者对深度学习理论解释做出的诸多尝试，而重点聚焦在训练方法和技巧上。

 

　　讲者首先介绍了随机梯度下降（SGD）中的各向异性噪声（anisotropic noise）对跳出尖锐局部最优（sharp minima）和正则化影响（regularization effect）。这项研究结合标准动力学提出推广的 SGD 优化方法，创造性地通过量化噪声协方差和损失函数曲线描述跳出局部最优的效率，揭示了这方面优于各向同性（isotropic）的噪声结构，证实了各向异性的噪声使得优化过程更平缓而稳定，从而提高了泛化效果。

 

　　然后他讲解了使用批正则化（batch normalization）和权重衰减（weight decay）的神经网络的动力学。其工作揭示了权重的优化路线是类似球形运动的动力学（sopheric motion dynamics），通过提出有角更新（angular update）的量化方式来衡量批正则化和权重衰减优化效率。对这种特殊动力学的均衡条件的研究表明，这样的优化方法有以下的好处：一是权重的范数会自动调节到满足均衡条件，从而避免了梯度消失或爆炸；二是优化曲线只会在半径足够大的局部最优上震荡，不会陷入尖锐的局部最优；三是有角更新的幅度会随着学习率下降，因此优化过程不会提前收敛。

 

　　最后讲者讨论了知识蒸馏（knowledge distillation）机制的迁移能力。其研究分析了蒸馏学习在泛化能力上的局限性，包括迁移风险，数据效率和不完美教师蒸馏（imperfect teacher distillation）等方面。针对这些问题，提出了新的正则化策略来减轻迁移学习对优化方向的负面影响（Deep Transfer learning Never Hurt）。

 

　　这些新的发现对理解深度学习的黑盒，特别是训练优化过程中的魔术做出了尝试，并且启发出新的算法层面的设计。

 

Guarantees for Tuning the Step Size Using a Learning-to-Learn Approach
鬲融 ，Duke University

 

　　讲者首先指出虽然当下深度学习取得了令人瞩目的成就，但一个一直令无数从业者头疼的问题是调节训练参数，例如 step size, weight decay, batch normalization, momentum 等等。每当遇到一个新的任务，可怜的研究生们就需要人力尝试各种参数的排列组合。那么有没有办法减少调参数的工作量，让计算机自己学习如何调节参数呢？这件事是有可能的，思路是用元学习的方法去学一个新的优化方法（optimizer）。

 

　　具体来说，将优化方法（optimizer）也当成一组参数 θ。首先利用该优化方法运行 t 步，得到轨迹。然后定义对于轨迹的元目标函数，例如轨迹上平均的损失函数。然后用梯度下降去优化优化方法中的参数 θ。这一方法有点类似卷积神经网络和强化学习中的 policy gradient 算法，但这两个方法的共同点是优化起来较为困难。而实际上对于上述的元学习方法也是如此，为了让这个元学习方法训练收敛，我们甚至需要调更多的参数，这似乎本末倒置了。

 

　　讲者认为该方法主要在以下四个方面可能出现问题：
       1. 梯度爆炸或者梯度消失。例如第一步利用该优化方法运行 t 步这个过程就很容易导致梯度爆炸或者梯度消失。
       2. 可能有大量差的局部最优解。该元学习方法优化的 loss 曲面可能和一般学习问题中的需要优化的 loss 曲面性质差距很大。
       3. 由于训练时是在多个不同的 task 上训练，在原问题上的泛化能力也是未知的。
       4. 缺乏任何理论保证。

 

　　针对以上问题讲者及其合作者考虑了一个几乎最简单的模型，取优化方法为梯度下降或者随机梯度下降，应用于二次函数拟合的目标函数。通过在这一简单模型上的分析，说明了对于梯度爆炸/梯度消失的问题，最简单粗暴的原优化方法的确一定会出现该问题。而该问题可以通过设置一个优化的元目标函数，将元梯度限制到多项式范围内。然而即使使用了优化的元目标函数，数值误差问题也难以避免。关于元学习方法的泛化能力问题，这一简单模型说明了，若数据集很小，则应将元目标函数定义在一个独立的验证集上，否则会出现过拟合。若数据集足够大，则直接定义在训练集上也没有问题。

 

Deep Learning for Algorithm Design
宋乐，Georgia Institute of Technology

 

　　讲者首先介绍了传统算法和深度学习算法的不同。传统算法相对来说是一步接着一步地构建，每一步都可以进行合理的逻辑解释，而深度学习算法更像是一个黑盒子，通过大量数据进行训练，最终只关注输入与输出，并不能完全地对算法的每一步合理解释。接着他从两个算法相关的应用场景出发，进行详细介绍。

 

　　第一个应用场景是 combination optimization algorithm。主讲人以社交网络图处理问题为例，比较了传统方法和深度学习方法的区别。其中传统算法使用贪心算法和马尔可夫决策链算法的组合模型，其优化问题通常表现为 NP-hard problem。而相比之下，使用深度学习算法更加简洁。使用 GNN 算法，首先通过一系列迭代获取每个节点的嵌入（embedding）特征，这一过程通过参数化的神经网络实现。每个节点的特征对应的权重参数在训练过程中不断更新，最终得到最优化参数。相比之下，深度学习问题能更好的解决组合优化问题，且基于 GNN 的强化学习（Reinforcement learning）比传统方法表现出了更快的速度。

 

　　第二个应用场景是 Unrolled Iterative Algorithm。以 RNA 的二级结构预测问题为例，使用了基于深度学习的展开算法 E2EFold 和其他方法。在最终预测上，E2EFold 算法取得了最好的结果。

 

　　最后，从理论角度进行总结。以算法敏感性、鲁棒性、算法复杂度、泛化边界、算法收敛等方面的广义理论定义出发，对深度学习算法性能的对比研究提供了思路。

 

Domain Adaptation with Theoretical Guarantees
马腾宇，Stanford University

 

　　在迁移学习中，经典模型方法通常要求 domain 的迁移要尽可能的小，而现实中的 domain 迁移都很大。其中一个主要的理论挑战是，如何定义源 domain 和目标 domain 之间的关系假设。这次报告第一部分便是建立在目标 domain 的未标注的标签比源 domain 更加分散的假设下。对于一般模型，其输入数据通常可提取两类特征：1）信号特征用来决定最终标签；2）伪特征与源域的标签有关，与目标域的标签无关。

 

　　Domain 的迁移常见的解决思路为：
       1. 自监督训练，利用带标签的数据先训练出一个模型。在域迁移的过程中，使用该模型对未标签的目标域数据进行标签，然后与有真值标签的数据一同输入进行分类器的重新训练。每次训练出的新模型进行新的预测来更新标签。随着训练次数增加，最终对目标域数据标注出正确的标签。
       2. 熵最小化算法，通过调整预训练分类器的参数，使得最终预测出的标签分布与真实分布之间熵最小。

 

　　讲者继而通过数学推导论证了减少训练过程对伪特征的提取等价于减少预测分布与真实分布之间的熵值，从而证明了两种算法其本质上是相同的。最后给出了自训练算法在彩色 MNIST 数据集和人脸数据集上不同 domain 的成功迁移例子，证明了算法的有效性，可以有效的减少对伪特征的依赖。

 

　　报告第二部分对迁移学习的另外一个方面进行了探讨：如何智能的向已训练好的模型在线地输入新 domain 的数据，从而使得模型可以适应新的 domain。报告主要探讨了几种输入的新 domain 数据的方式：1）直接输入；2）将新 domain 数据随机穿插在已有 domain 中输入。讲者指出第二种方法相对较为合适，同时插入新 domain 中比较难的样本，更有利于模型的迁移。