【博士论文】通过秩的概念理解深度学习，206页pdf

尽管深度学习在科学和工业界极为流行，但对其正式理解仍然有限。常见的实践主要基于试错和直觉，这常常导致次优结果。因此，人们对开发深度学习的正式理论表现出极大兴趣，希望这能揭示实证发现的本质，并引导出改进神经网络效率、可靠性和性能的原则性方法。

本文提出将秩的概念作为发展深度学习理论的关键。具体而言，基于某些神经网络架构与张量分解之间的联系，我们运用秩的概念来研究泛化和表达能力的基本方面。

关于泛化，神经网络神秘的泛化能力被广泛认为源于一种隐式正则化——一种基于梯度的训练倾向于选择低复杂度预测器的趋势，但这种复杂度的度量尚不明确。通过动态分析，我们在几种类型的神经网络架构中确立了向低秩的隐式正则化（对于相应的秩概念）。值得注意的是，这种隐式的秩最小化不同于任何类型的范数最小化，这与之前的观点相反。我们讨论了这一发现对解释自然数据（如音频、图像和文本）泛化能力的意义，以及在实际应用中的影响（新的正则化方案）。 关于表达能力，我们理论上描述了图神经网络通过分离秩来建模交互的能力，分离秩是量子物理中常用于量化纠缠的度量。作为我们理论的实际应用，我们设计了一种边稀疏化算法，该算法能保留图神经网络建模交互的能力。实证评估表明，该算法显著优于替代方法。 在过去的十年里，深度学习取得了前所未有的成功，并且在很大程度上推动了被公众称为“人工智能”的技术突破（见例如[128, 153, 195, 77, 31, 2]）。然而，尽管深度学习在科学和工业界极为流行，对其正式理解仍然有限。常见的实践主要基于试错和直觉，这常常导致次优结果，以及在安全性和鲁棒性等重要方面的妥协[201, 144]。因此，人们对开发深度学习的正式理论表现出极大兴趣，希望这能揭示实证现象，并引导出改进神经网络效率、可靠性和性能的原则性方法。 从学习理论的角度来看，理解深度学习需要解决优化、泛化和表达能力的基本问题。优化关注的是基于梯度的方法在最小化非凸神经网络训练目标方面的有效性。泛化处理的是神经网络在其训练数据之外的表现。最后，表达能力指的是实际大小的神经网络表示丰富函数类的能力。 本论文集中讨论了泛化和表达能力这两个基本问题。它提出了将秩的概念作为发展深度学习理论的关键。我们的方法采用了来自动力系统理论和张量分析的工具，基于某些神经网络架构与张量分解之间的最近联系[51, 48, 52, 132, 118, 119]。主要的理论贡献及其实践意义总结如下。 通过隐式秩最小化实现泛化（第二部分）

深度学习的一个核心谜题是神经网络通过基于梯度的方法训练时，尽管其可学习参数远多于训练样本，但仍能在自然数据（如音频、图像和文本）上实现泛化。这种泛化即使在没有任何显式正则化的情况下也会发生[226]。因此，传统观点认为，基于梯度的训练会引发一种隐式正则化——一种基于某种复杂度度量的倾向，即用最小复杂度的预测器来拟合训练样本[166, 165]。自然数据能够产生泛化，因此被理解为训练过程中隐式最小化的复杂度度量与数据复杂度之间的一致性。更具体地说，自然数据易于被低复杂度的预测器拟合。 数学上形式化上述直觉被认为是深度学习理论中的一个主要开放问题。实现这一目标的一个显著挑战是我们缺乏对预测器复杂度的定义，这些定义既在神经网络训练过程中隐式最小化，又能捕捉自然数据的本质（即自然数据可以用低复杂度拟合的意义）。最初在[166]中提出的一个广泛希望是，基于范数最小化的描述可能适用。也就是说，已知对于线性回归，基于梯度的方法会收敛到最小欧几里得范数的解（见例如[226]第5节），希望这一结果可以推广到神经网络，只需允许用不同的（可能依赖于架构的）范数替代欧几里得范数[81, 197, 83, 82, 140, 109, 217, 216]。 研究这一前景的标准测试平台是矩阵分解——一种等价于线性神经网络的模型，即没有非线性的全连接神经网络[188]。在第1章（基于[177]）中，我们证明了，与先前的观点相反[81]，矩阵分解中的隐式正则化不能通过范数来捕捉。具体而言，我们表明在某些情况下，它会将所有范数驱向无穷大，以最小化秩为代价。这表明，与其通过范数来看隐式正则化，更有用的解释可能是秩最小化。 利用这一解释，在第2章和第3章（分别基于[178]和[179]）中，我们确立了从线性神经网络到更实际的非线性神经网络（具有多项式非线性，等同于张量分解）的低秩倾向。通过描述基于梯度的方法在此类网络上引发的动态，我们表明这些方法导致对低秩的偏向，对于定义在张量上的依赖于架构的秩概念。就我所知，我们的结果构成了第一个关于非线性神经网络中隐式正则化最小化秩概念的证据。后续的研究表明，类似的现象也发生在其他类型的神经网络中[106, 213, 204, 65]。 考虑到秩的概念在某些非线性神经网络中捕捉了隐式正则化，我们实证探讨了它们作为解释自然数据泛化的复杂度度量的潜力。我们发现可以用极低秩的预测器拟合标准图像识别数据集。这使我们相信，秩的概念可能为解释深度学习中的隐式正则化和自然数据的特性提供了一条途径，将其转化为泛化。 在实际影响方面，基于我们的理论，我们开发了一种显式正则化方案，用于改进卷积神经网络在涉及非局部交互的任务中的性能。其他研究团队也基于我们的隐式秩最小化分析设计了实际的深度学习系统[112, 102]。 通过分离秩理解图神经网络的表达能力（第三部分）

在第5章（基于[180]）中，我们扩展了上述神经网络与张量分解的联系，用于研究图神经网络（GNNs）的表达能力[89]。GNNs广泛用于建模表示为图顶点的实体之间的复杂交互[58, 122, 73, 222, 218]。然而，对其建模交互能力的正式描述仍然缺乏。我们通过分离秩（量子物理中常用的量化纠缠的度量）正式化交互强度，填补了这一空白。通过秩的概念，我们描述了某些GNNs建模给定顶点子集与其补集之间交互的能力，即输入顶点的给定分区两侧之间的交互。 我们的分析表明，GNN建模交互的能力主要由分区的游走指数决定——这是一个由分区边界出发的游走次数定义的图论特征。这正式化了传统观点，即GNN可以建模输入图中更互连区域之间的更强交互。实验结果证实了这一结果，表明GNN在需要跨越高游走指数分区进行交互的任务上表现更好。 作为我们理论的实际应用，我们设计了一种边稀疏化算法。边稀疏化涉及从图中删除边，以减少计算和/或内存成本，同时试图保持图的某些选定特性（参见[21, 198, 87, 36, 186, 211, 138, 39]）。在GNNs的背景下，我们的兴趣在于随着删除的边数量增加，保持预测准确性。我们提出了一种称为Walk Index Sparsification（WIS）的边删除算法，该算法能保留GNN建模交互的能力。WIS简单、计算效率高，在我们的实验中，其在各边稀疏水平上的可达到预测准确性方面显著优于替代方法。更广泛地说，它展示了通过理论分析GNNs可通过分离秩建模的交互来改进GNNs的潜力。