【速览】TPAMI 2019 | 正交深度神经网络

原创温宇馨中国图象图形学学会CSIG

学会“成果速览”系列文章旨在将图像图形领域会议期刊重要成果进行传播，通过短篇文章让读者用母语快速了解相关学术动态，欢迎关注和投稿~

◆ ◆ ◆ ◆

正交深度神经网络

Jia, Kui and Li, Shuai and Wen, Yuxin and Liu, Tongliang and Tao, Dacheng

TPAMI 2019

撰稿人：温宇馨

推荐理事：林宙辰

原文标题：Orthogonal Deep Neural Networks

◆ ◆ ◆ ◆

摘要

基于谱正则化的深度神经网络（Deep Neural Networks，以下简称DNNs）通常会取得更好的泛化性能，因此近期受到了广泛的关注。本文推导出了一个全新的泛化误差界（Generalization Error bound，以下简称GE bound）, 受DNNs权重矩阵奇异值的大小和波动范围影响，并且证明了在该GE bound下，正交深度神经网络（Orthogonal Deep Neural Networks，以下简称OrthDNNs）将取得最小的泛化误差。基于这个证明，本文提出了一个有效的算法构造OrthDNNs，并称其为Singular Value Bounding (SVB) 算法。此外，本文还提出了Bounded Batch Normalization (BBN) 来解决传统的Batch Normalization (BN) 不适用于OrthDNNs的问题。

研究背景

以卷积神经网络（Convolutional Neural Networks，以下简称CNNs）为代表，DNNs在许多机器学习任务中，如图像识别，取得了良好的结果。尽管简单的随机梯度下降法能找到一个好的解，但是现代DNNs通常具有很高的模型复杂度并且过度参数化，这促使了研究者们提出方法来缓解过拟合的问题，包括early stopping，weight decay，data augmentation以及dropout training等等。这些方法主要是为了解决DNNs训练困难的问题，并且提高DNNs中每个参数被利用的效率。然而这些方法却不能告诉我们什么样的解才是好的解（比如如何让DNNs具有良好的泛化性能）。实际上，已经有部分工作提出了如何经验性地提高DNNs的泛化性，如惩罚DNNs 雅克比矩阵的Frobenius norm，但是这些工作却没有提出相应方法的有效理论依据。本文就是为了解决该问题而提出的。

本文基于算法鲁棒性的泛化误差分析（generalization analysis via algorithmic robustness），引入了局部各向同性（local isometry）的概念，并且通过局部各向同性刻画泛化误差。另外，本文证明了DNNs在特定数据分布上满足局部各向同性，其局部各向同性的程度仅由权重矩阵的奇异值的大小及波动范围决定，从而证明了DNNs的GE bound是可以通过DNNs权重矩阵的奇异值的大小及波动范围来刻画的。

基于该GE bound，本文进一步导出当DNNs每一层的权重矩阵具有相等的奇异值时，即DNNs的权重矩阵正交（方阵）或DNNs的权重矩阵每行/每列正交时（如不引起歧义，以下用OrthDNNs代替DNNs中权重矩阵正交），我们能取得最优的GE bound。然而，由于获取严格的OrthDNNs需要相应的权重矩阵落入Stiefel流形上，这需要很高的计算复杂度，不适用于规模较大的DNNs，因此我们提出了一种近似OrthDNNs的办法，并且称之为SVB算法。在SVB算法中, 我们要求每个权重矩阵的奇异值都落在1附近的一个窄带内，以此达到近似正交的效果。此外，我们还提出了DBN以及BBN算法，用于解决传统BN不适用于正交神经网络的问题，即让传统BN算法对特征图中每个通道的放缩程度趋于一致。我们在图像分类问题上进行了全面的研究，以此证明OrthDNNs可以有效地提高泛化性。更有趣的是，我们发现近似的OrthDNNs相比起严格的OrthDNNs，不仅计算复杂度降低了，而且不会带来性能的下降。我们展示了对我们所验证的所有的网络结构及数据集，OrthDNNs都能比正常的DNNs取得更好的性能；另外，对于被扰动的图片，OrthDNNs也能取得更好的性能。

这项工作的初步版本在CVPR2017 [5]中曾有所展现。在最新录用的PAMI论文中，在以下几个方面对原始版本进行了补充：

本文提出了新的GE bound用于刻画DNNs，并且证明了在该GE bound下DNNs权重矩阵的奇异值的大小和波动范围是至关重要的；
本文证明了OrthDNNs在该GE bound下能取得最好的结果，并且充分对比了严格的OrthDNNs以及近似的OrthDNNs之间的区别；
本文扩展了原有的工作，在更多先进的网络结构及机器学习任务上进行了实验，验证了所提出的方法能够带来重要的性能提升。

问题设置理论分析

（1）背景知识

在阐述本文的理论推导之前，首先简要介绍相关的符号及背景知识。详细的推导过程请参照原论文，在此处不过分展开。

泛化误差

泛化误差的定义为：

其中为期望误差，为经验误差，为训练集的个样本。

基于算法鲁棒性的泛化误差分析

一般的GE bound推导都是基于Rademacher复杂度或者VC维的，但是这种GE bound只考虑了模型的容纳性而忽略了算法本身的作用。为了建立更好的GE bound，本文从依赖于算法的分析方法开始，选择了基于算法鲁棒性的泛化误差分析方法，较大程度依赖于[1]中的工作。

我们先定义鲁棒性：

鲁棒性可以直观理解为训练样本的loss与落在其附近的真实样本的loss之间的变化值。其中的大小由样本空间及数量决定。有了鲁棒性的定义，我们直接给出[1]中基于算法鲁棒性的泛化误差的理论：

其中第一项为loss的变化值，第二项可以理解为一个与模型无关的量。而且为了确定的切割方法，我们引入了覆盖数（covering number），定义如下：

其中图像等常见的流形都满足覆盖数。另外，为了刻画loss的变化值，我们定义了δ-各向同性：

直觉上，假设DNNs（如不引起歧义，以下用T表示）满足δ-各向同性，我们即可通过刻画其鲁棒性来定义其泛化误差：

DNNs的表示与符号

如上所述，我们用T表示DNNs，即

其中代表权重矩阵，代表非线性操作。

（2）理论分析

在背景知识中我们留下了一个假设：DNNs满足δ-各向同性。在接下来的理论分析中，我们首先会在引理3.1中证明线性的神经网络满足δ-各向同性，并且把δ-各向同性用DNNs权重矩阵的最大最小奇异值表示；紧接着，我们在引理3.2中证明了非线性DNNs T将输入空间划分为若干个regions，并且在每个region里T均可被视为线性DNNs。然后在引理3.3中我们会证明覆盖球中的半径γ的上界可以由权重矩阵的最大奇异值表示。紧接着在引理3.4中我们证明了非线性的DNNs T在每个覆盖球内都满足局部δ-各向同性。由这些引理共同导出定理3.1，考虑了DNNs T的收缩功能之后，即可导出本文的主要结论定理3.2。

DNNs的δ-各向同性

首先明确，对于DNNs，本文仅对样本空间中能够引起loss变化的样本感兴趣，即：

直觉上，如果中的不能引起网络的变化，则说明DNNs T丢弃了这部分变化的信息，自然地，这些x不是我们感兴趣的样本。因此我们着重考察所张成的子空间，其中由能够引起T变化的样本构成。自然地，我们可以在这种我们感兴趣的子空间中定义-各向同性，如下给出定义：

对于线性DNNs，本文证明其对于我们感兴趣的数据变化是满足δ-各向同性的，即引理3.1：

具体证明过程可参照原文，此处不过分展开。

对于非线性DNNs，我们需要引入新的定义来对其进行刻画：

定义6、定义7以及定义8分别刻画了hyperplane arrangement、region与neuron，我们可以用下图直观地表示上述概念：

图中实线部分代表了不同的hyperplane，而不同的颜色区域代表了不同的region。DNNs T通过neuron的概念定义出不同的region。其中为选择函数，代表选择第k个元素。在以下定理中我们证明了非线性的DNNs T可以被分割成不同的region（上图不同颜色的色块），并且在每个region内都满足δ-各向同性。

上述引理适用于使用ReLU及maxpooling的非线性DNNs T。具体推导详见原论文。至此，我们证明了非线性的DNNs对于我们感兴趣的数据变化满足局部δ-各向同性。紧接着则是讨论DNNs不同的region是否也可以通过DNNs的权重矩阵表示，有下述引理：

引理3.3刻画了覆盖球中的半径γ的上界可以由权重矩阵的最大奇异值决定，具体推导详见原论文。

引理3.4进一步说明了非线性DNNs T满足局部δ-各向同性并可被γ球覆盖，具体推导详见原论文。至此我们已经介绍完所有的引理了，接下来我们可以得出本文的主要结论。

对泛化界的主要结论

对于非线性DNNs，我们证明了其满足局部δ-各向同性并可被γ球覆盖，因此我们可以得出以下结论：

该结论的形式与定理2.1基本一致，其中定理2.1中第一项loss的变化值被进一步展开了，此展开基于T满足的局部δ-各向同性及可被γ球覆盖的性质；而第二项基本保持不变。

注意到在定理3.1中，我们对loss函数引入了Lipschitz常数的概念，这可能会造成问题：即若同一个数据点（以可忽略的概率）出现了不一样的label时，Lipschitz常数A为无穷大，这会导致定理3.1失效。因此我们进一步定义了Pairwise error function来代替Lipschitz常数：

至此，我们可以得到本文的主要结论定理3.2：

直觉上，该结论证明了对于非线性DNNs，其GE bound受到其权重矩阵的奇异值的绝对大小以及波动范围的影响。当且仅当权重矩阵奇异值都等于1时，GE bound取得最小值，此时可以获得最好的GE bound。根据该结论，我们提出了OrthDNNs，并且提出了相应的算法。

算法简介

本文提出了近似OrthDNNs，用于解决严格OrthDNNs的计算复杂度问题，并且将其命名为SVB算法。下面将具体介绍SVB算法：SVB算法可以视为基于随机梯度下降的投影梯度下降法，经过次正常的随机梯度下降迭代后，我们取出DNN T中的所有权重矩阵，使用奇异值分解（SVD）方法计算左奇异向量矩阵，奇异值矩阵以及右奇异向量矩阵，并且将奇异值矩阵中的超过一个窄带范围的奇异值投影会窄带的端点上（或上），获得新的奇异值矩阵。然后再用构建出新的权重矩阵。当超参数ε很小时，即可理解为经过这样投影方法后的权重矩阵被约束成近似的正交矩阵，因而我们构建出了OrthDNNs。与其他投影梯度下降法一样，在SVB中我们首先让朝着梯度下降方向前进，紧接着我们把解再次投影回Stiefel流形附近。我们经验性地观察到这样的投影是可以让DNNs的训练收敛的。而由于我们次迭代后才进行一次投影，所需要SVD的计算成本相比起正常的训练是可以忽略的。

另外一方面，由于传统的BN算法与OrthDNNs不兼容，我们进一步提出了BBN算法。具体做法如下：传统的BN算法可以被视为

其中μ与Φ为输入特征的均值以及方差，γ与β为可学习的参数。我们不希望经过BN破坏OrhDNNs的结构，因此与SVB算法一样，我们采用了投影梯度下降的方法。对于每一组，我们希望其落在窄带内，若不满足，则通过控制将其投影至窄带端点上（或上）。这样，我们可以保证不同的neuron被放大或缩小是一致的。从而避免BN算法破坏OrthDNNs的正交性。

特别地，对于CNNs，其第层的权重矩阵为的张量，不能直接进行SVD分解，其中与分别代表卷积核的高和宽，和分别代表输出与输入卷积核的维度。我们将该张量展开成的矩阵进行SVD分解，原因如下：每一层的卷积操作可以理解为个大小为的滤波器，我们希望每个滤波器之间相互正交，因此我们选择将其展开成的矩阵来构建OrthDNNs。注意到这样的展开并不完全等价于从卷积操作展开成完全相同的线性操作（若需要展开成完全相同的线性操作需要将卷积核权重矩阵嵌入到一个双循环矩阵中）。我们的初步的实验验证了SVB对两种卷积展开的形式都带来了性能上的提升，对不同展开方法造成结果的差异的进一步探究将在未来的工作中完成。

实验验证

我们进行了一系列的实验来验证我们提出的方法的有效性，我们着重验证了其对于图像分类任务的性能提升。对于不同的对比实验，我们在CIFAR10上进行实验；而对于算法效果的验证，我们在不同的数据集，包括CIFAR10，CIFAR100，ImageNet以及不同的网络结构上进行了实验。

严格OrthDNNs与近似OrthDNNs的对比实验

我们首先在仅含卷积层的ConvNet与带有shortcut结构的ResNet上对比了严格的OrthDNNs与近似的OrthDNNs对分类性能的影响。对于严格的OrthDNNs我们使用投影梯度下降法，对权重矩阵进行正常的随机梯度下降后将其投影回Stiefel流形上；而对于近似的OrthDNNs，除了我们提出的SVB算法外，我们还采用了另外两种方法，包括在[2]中被提及的直接惩罚权重矩阵的正交性的方法（以下简称Soft Regularization）：

以及在[3]中被提及的Spectral Restricted Isometry Property（SRIP）算法：

结果如下表所示：

可以看到，无论是严格的OrthDNNs还是近似的OrthDNNs，相比起原有的标准随机梯度下降法都可以带来性能上的提升，并且三种不同的近似OrthDNNs方法都极大程度减少了计算复杂度，使得它们能够真正被应用到训练中。

近似OrthDNNs中强约束与弱约束的对比实验

进一步地，我们需要研究不同的近似OrthDNNs方法对性能的提升程度。我们将近似OrthDNNs算法分为两种：在损失函数上加惩罚项的弱约束，比如Soft Regularization以及SRIP；以及我们提出的直接对DNNs的权重矩阵进行修改的SVB算法。对每种方法我们进行了5次试验，并且将其最小误差值，误差的均值与误差标准差计算出来，实验结果如下：

如上表所示，不同的近似OrthDNNs均对提升分类性能有帮助，其中SVB以及SRIP方法对结果提升较为明显。而相比起传统的BN，改良后的BBN能进一步提升SVB算法的性能。（注意到BBN算法可能与弱约束算法不兼容，因此在这些算法上可以带来性能的进一步提升）。

在更多网络结构及数据库上的实验

上述消融实验说明了本文提出的SVB算法的有效性，我们将进一步在不同的网络结构以及数据库上对SVB算法的效果进行验证。在CIFAR10以及CIFAR100上，我们采用了ResNet-56，Wide ResNet-28-10，ResNeXt-29(16*64d)三种结构进行实验，实验结果如下图所示：

可以看到在使用了SVB与BBN后，不同的网络结构均有了性能上的提升。另外观察到CIFAR100上的提升通常比CIFAR10上的提升大，我们认为这是受到了CIFAR100每类物体具有更少的训练样本（CIFAR10的十分之一）的影响。

另外，我们在ImageNet数据库上进行了实验，采用了ResNet-152，DenseNet-264以及ResNeXt-101(64*4d)三种结构，实验结果如下图所示：

可以看到我们提出的SVB及BBN算法在ImageNet这种大规模的学习问题上也可以带来性能上的提升。

不同样本规模下的实验

我们希望知道SVB及BBN算法对不同数量的训练样本带来的提升的区别，因此我们在ImageNet上进行了一个对比实验：我们取出ImageNet中每一类的1/10，1/5，1/2以及全部的训练样本组成了全新的四个不同规模的数据集，其中规模更大的数据集包含所有规模小的数据集的所有样本。我们使用ResNeXt-101(64*4d)模型进行实验，结果如下图所示：

可以看到，SVB以及BBN算法能在各种规模的数据集上带来性能上的提升，并且数据集的训练样本规模越小，这种提升就越明显。

算法对鲁棒性的提升

至此，我们已经探究了由SVB及BBN算法构建的近似OrthDNNs，在训练样本及测试样本独立同分布的情况下带来的性能提升。下面我们将进一步探究当测试样本被污染时，也就是说训练样本及测试样本来自不同的分布时，我们提出的算法是否依然有效。我们选用了[4]中的ImageNet-C数据集，该数据集是ImageNet的变体数据集，新的图像包含了噪声、模糊、天气变化、数码化等15种不同的扰动，并且每种变化有5个不同的强度。现有的研究表明传统的DNNs对这些扰动是非鲁棒的，并且就算在其中一种扰动上进行了fine-turn也不能保证在其他扰动上获得良好的效果。我们在ImageNet数据集上进行正常的训练，且对比了有无使用SVB及BBN带来的鲁棒性的不同，实验结果如下所示：

可以看到使用了SVB及BBN算法后，DNNs对不同程度的扰动均有了性能的提升，并且相比起在没有扰动的情况下（在正常测试样本下测试）有更大的提升。且当扰动为中等规模的情况下（corruption severity levels为3）时提升最大。这进一步说明了SVB及BBN算法能够给DNNs带来鲁棒性。

总结

本文为近期受到广泛关注的谱正则化方法提出了理论分析，并且为DNNs提出了一个新的GE bound，该GE bound由DNNs的权重矩阵的奇异值的大小及波动范围影响。我们进一步证明了在该GE bound下，当DNNs的权重矩阵的奇异值都相等，即权重矩阵正交时，能够取得最好的泛化误差。基于上述理论分析，我们提出了一种近似OrthDNNs的算法SVB，并且提出了能够与OrthDNNs兼容的BN算法的改进BBN。我们在图像分类任务上进行了大量实验，验证了我们方法的有效性。

参考文献

[1] Huan Xu and Shie Mannor. Robustness and generalization. Machine Learning, 86(3):391–423, 2012.

[2] Di Xie and Jiang Xiongand Shiliang Pu. All you need is beyond a good init: Exploring better solution for training extremely deep convolutional neural networks with orthonormality and modulation. In Computer Vision and Pattern Recognition, 2017.

[3] Nitin Bansal, Xiaohan Chen, and Zhangyang Wang. Can we gain more from orthogonality regularizations in training deep cnns? In Proceedings of the 32Nd International Conference on Neural Information Processing Systems, NIPS’18, pages 4266–4276, 2018.

[4] Dan Hendrycks and Thomas Dietterich. Benchmarking neural network robustness to common corruptions and perturbations. In International Conference on Learning Representations, 2019.

[5] Jia, Kui, et al. "Improving training of deep neural networks via singular value bounding." Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2017.

往期精选

征文

第二十届全国图象图形学学术会议(NCIG2020)征文通知