近日，香港中大-东升国际官网科技结合尝试室的新论文“Accelerated Training for Massive Classification via Dynamic Class Selection”被AAAI 2018录用为Oral Presentation。该论文着力于解决超大规模分类问题(过百万类)对模型训练带来的一系列挑战，尤其是超大规模Softmax层造成的推算瓶颈。具体而言，该论文提出了一种新型的Dynamic Selective Softmax，可能以较低的价值在每次迭代中凭据类别空间的结构动态选择一幼部门类别参加推算，在保障精度根基一致的前提下，能够极度显著地提升训练速度，并大幅度削减训练过程所占用的显存。本文中我们将具体介绍该论文中提出的步骤，并介绍一些可能的后续工作等。

值得指出的是，这项工作是由东升国际官网科技在城市级人脸识此外场景所驱动。而此项工作的成就也反映了在人为智能领域产业利用对于学术创新的沉要意思。

作者：张行程，杨磊，闫好汉，林达华

一个现实的问题—人脸鉴别

随着数据的迅速堆集，数据的类别数量也在不休增长，大规模分类的问题受到越来越宽泛的器沉，人脸鉴别就是其中一个沉要的例子。在先前的一些人脸识此外工作中[2]，基于分类的训练方式因其单一且能提供高效监督信息的特点，为学界和工业界宽泛使用。

图1 基于分类步骤的人脸鉴别训练流程

然而，如下图所示，随着类别数量急剧增长，两个现实的问题浮出水面：1)推算Softmax所必要的推算量会大大增长，使得Softmax的推算成为造约网络训练速度的瓶颈。2)类别数量的增长会导致分类层的参数量大大增长，在如今GPU显存有限的情况下，会极大造约可能参加分类的类别数量。

图2 类别数量增长时

对应的推算量和显存的变动

针对类别数增长时带来的推算增长和显存增长的挑战，本论文提出了一种全新的选择性Softmax推算框架，我们称之为“基于动态类别选择的Softmax”(Dynamic Selective Softmax)。该框架能够显著削减训练过程中的推算量以及显存亏损，并且获得近似齐全Softmax训练的机能。

对两个指标的观察

我们界说了两个指标来援手我们分析大规模分类的问题。第一个指标叫做CP_K，即前K累加概率和，暗示Softmax推算出的前K大的概率的总和。CP_K的值越大暗示概率越集中在前K个的类别中。

进一步地，从Softmax的梯度公式可知，除了真实标签之表，其它类此外梯度和概率大幼成正比。这注明若是概率是集中在前K个类别中，那么对应的梯度值也是集中在前K个类别中。

因而，我们进一步界说了一个指标NCG_K，即前K归一化累计梯度。这个指标衡量了梯度在前K个类别上的集中水平。

凭据界说，我们用一个在Ms1MCeleb上训练好的Resnet-101模型，画出了NCG_K随着迭代轮数变动的曲线。

从上图中我们能够得到几点沉要的观察：1)在无数情况下，一个样本只容易和一幼部门的类别混合。2)当使用Softmax作为损失函数时，从这一幼部门类别产生的梯度主导了所有的梯度。3)随着训练的进行，容易混合的类此外集中会越来越幼。

图3 Softmax推算中的“活跃类别”

如图所示，这K个概率值最大的类别主导了Softmax推算，我们将其称之为“活跃类别”。

选择性Softmax框架

基于上述观察，我们提出了一种选择性的Softmax框架。该框架引入了一个选择器，该选择器通过结合当前特点和分类的权沉矩阵，可能高效且正确地遴选出分类上可能产生较强监督信号的“活跃类别”。凭据之前的分析，“活跃类别”能够近似提供和所有类别同样有效的监督信息，因而，对于这占整体类别比例很幼的“活跃类别”，我们能够利用一些稀少性的操作来加快整体的推算流程。

如下图所示，我们将大规模分类所必要的巨大的权沉矩阵搁置于CPU的内存中，凭据选择器遴选出的类别，能够从这个巨大的权沉矩阵中遴选出必要的权沉向量，搁置到GPU的显存中。当在GPU上推算出对应的梯度之后，再异步地将求出的梯度稀少更新到存在于CPU上的权沉矩阵中。

图4 选择性Softmax工作流程示意图

To Be or not to be的困局

凭据上文的介绍，选择性Softmax框架的一大主题是“活跃类别”的选择器，若何找到一种高效且正确的选择器成为这个推算框架的关键。首先我们钻研了两种最为直观的选择器。

第一种是随机选择器。在每一轮迭代中，除了当前训练样本、的类别，还会通过随机采样得到其余的类别。该随机选择器不依赖于当前样本的特点和分类层权沉矩阵的信息，险些没有额表的功夫开销，也由于是随机拔取，没有引入任何额表信息，该步骤的机能能够被视为是选择器的机能下界。

第二种是最优选择器。在每一轮迭代中，会凭据当前样本的特点和整个特点矩阵点乘的了局，从中拔取响应最大的类别，用这些类别来作为“活跃类别”。这种步骤保障了每次拔取出来的活跃类别都是最优的，但是由于引入了整个权沉矩阵参加推算，无法削减前传的推算开销，这有悖于我们削减推算量的初衷。但最优选择器每次都拔取了最活跃的类别，该步骤的机能能够被视为是选择器机能的上界。

如图所示，随机选择器固然速度快，但是损失了精度;最优选择器固然保障了精度，但是没有削减推算开销。这两种选择器都无法满足东升国际官网设计要求，因而，我们但愿找到一种在速度和精度上都能够获得较好平衡的“活跃类别”选择器。

哈希丛林选择器

为了有一个速度和精度上能够达到优良平衡的选择器，我们提出了哈希丛林选择器。我们将从哈希丛林的构建和哈希丛林的使用两个方面来介绍这一算法。

对于哈希丛林的构建，我们首先来看一棵哈希树的构建。对于N个类别分类的权沉矩阵，我们能够将这个权沉矩阵看作是N个类此外均匀特点向量，那么我们就得到了D维空间的N个点。首先，我们从这N个点中随机选择2个点，推算出距离这两个点距离最大的超平面，也即，该超平面把这两个点划分在了空间的两侧。那么，凭据这个推算出的超平面，我们就能够把空间中的其它点分为两部门，即在超平面的分歧侧。这样，我们就把空间分成了两个子空间。对于每一个子空间，我们会沉复上面的过程，即每次随机拔取2个点，推算出超平面对空间进行划分，当子空间中点的个数不超过B个点时终场持续划分。经过若干次操作后，当所有子空间中的点的个数都不超过B个点时，构建过程实现。若是将每个划分的超平面视为中央节点，将最终划分后的了局视为叶子结点，那么构建的这个结构就能够被当成是一棵哈希树。

从一棵哈希树的构建过程能够看出，我们构建哈希树时选取的是随机算法，因而，为相识除随机拔取带来的不不变性，我们会同时天生L棵哈希树，这样就组成了哈希丛林。

图5 哈希丛林的构建

对于哈希丛林的使用，我们也先来看每棵哈希树对应的操作。对于每一颗哈希树，树上的中央节点都是一个超平面。因而，当一个新的特点向量来了之后，首先会被根结点的超平面分到左子树或者右子树，接着又会被相应子树的根节点持续往下分类，直到落入一个叶子结点中。那么叶子结点中所蕴含的类别就被以为是和这个特点向量类似的类别。

对于丛林中的每一棵树，城市沉复这个过程，最终会得到一个类此外候选集中，若是候选集中中的类别超出了我们所需的类别数量，我们再通过推算其余弦距离，最终拔取余弦距离最幼的那些类别作为东升国际官网“活跃类别”。

更好的平衡—动态选择性Softmax

固然哈希丛林的选择器在保障正确率的同时大大提升了东升国际官网效能，但从之前对两个指标的观察中，我们能够看到，随着训练的进行，所必要的活跃类别数越来越少，因而我们能够针对选择器中引入的参数做动态调整，进一步优化推算资源的配置。

为此，我们引入了一个阈值，每隔一段功夫，在验证集中上推算出CP_K(前K概率累加和)，我们拔取的类别数K刚好使得算出的CP_K超过界说的阈值。相迸宗预先设定好采样类别数，这种方式随着训练的进行，K的值会越来越幼，也即必要采样的类别数会越来越少，这样能够进一步削减无用的推算资源亏损。

对于新引入的阈值和另表两个参数，树的数量和更新周期
；凇把盗烦跗诙喑⑹苑制绲目赡，训练不变后追求更精准的选择」剽一理想，我们发现单一的线性更新的方式就能够获得不错的成效，也即：阈值由幼到大线性增长，树的数量由少线性增多，更新周期由大线性减幼。

尝试了局

我们在两个散布迥异的人脸鉴别数据集上来验证选择性Softmax的机能。第一个数据集是Ms1M Celeb，该数据集蕴含10万人共1000万张图，由于原始的数据集有比力多的噪声，我们进行了一些算帐，现实用于尝试的是8.7万人约460万张图。第二个数据集是Megaface Challenge 2的训练数据。该数据集共有67万人约470万人。我们在4个分歧的人脸鉴别尺度和谈上测试了步骤的机能，即LFW非受限的人脸验证和谈，人脸鉴别和谈，IJB-A的1:1人脸验证和谈以及Megaface的人脸鉴别和谈。

在这些分歧的和谈上，东升国际官网提出的步骤有着一致的机能，在指数级别地削减推算量的同时，能够获得逼近于齐全Softmax的机能。从表图1中能够看到，在获得一样机能的情况下，哈希丛林的功夫开销比最优选择器或者齐全的Softmax要幼一个数量级;在一样的功夫亏损下，哈希丛林的机能远超其它的一些算法。并且能够从图中看到，动态的哈希丛林能够进一步地提升算法的机能。

表图1. 选择性Softmax和其它步骤的比力

除了在幼模型上的比力尝试，我们还将Ms1MCeleb和Megaface Challenge 2两个数据集中并在一路，得到一个75万分类的大数据集，用Resnet-101在这个数据集上进行了尝试。在这个大尝试中，我们在险些不损耗机能的情况下，能够将每轮的训练迭代功夫从3.5s缩短为1.5s，起到了60%的加快成效。并且由于我们将巨大的权沉参数放到了CPU的内存中，我们险些移除了权沉矩阵所占用的所有显存。从整体网络的显存亏损上看，我们能够将显存开销减幼24%。

表图2. 在Resnet101上进行

75万人脸分类的训练

除了得到更好的机能，我们也具体分析了哈希丛林中分歧决定因子对最后了局的影响。由下图能够得到几个观察：1)不论用何种选择器，随着采样类别数主张增长，模型的机能城市随之增长。2)基于哈希丛林的选择器在采样类别数量很幼时，就能够逼近最优选择器的机能。3)对于哈希丛林中树的数量不是出格敏感，在超过50颗树机遇能就趋于不变。4)当哈希丛林的更新周期在1个epoch内时，对机能的影响不显著，若是更新周期超过了一个1 epoch，可能由于构建哈希丛林的权沉矩阵信息太过长远而造成整体机能的降落。

表图2. 采样类别数对机能的影响

表图3. 树的数量对机能的影响

图表4. 更新周期对机能的影响

思虑与最后的话

回首本文的算法，我们针对大规模分类时Softmax带来的问题，提出了基于动态类别层级选择的算法，高效且正确地找到了“活跃类别”，并且我们进一步提出了动态分配的规划来进一步充分利用推算资源。在分歧测试集上的尝试了局，充分验证了本文步骤的有效性。另表，除了本文中提出的哈希丛林选择器，该动态选择性Softmax的推算框架还能够矫捷引入分歧的采样算法，在现实的使用情况中，能够凭据速度和精度的分歧需要来选择分歧的采样算法。在将来，我们但愿进一步探寻该步骤的天堑，当数据规模再大一个甚至几个量级时，会不成预防线引入更多的噪声。倒剽些噪声达到无法人为算帐的规模时，可能会对构建的动态的层级结机关成好多滋扰，使得选择器无法正确分辨“活跃类别”和“噪声类别”等信息，若何在这种情况下改进东升国际官网选择性Softmax是一个值得持续探索的问题。

有关文件：

【1】“Accelerated Training for Massive Classification via Dynamic Class Selection”, Xingcheng Zhang, Lei Yang, Junjie Yan and Dahua Lin, AAAI 2018.

【2】“Deep learning face representation from predicting 10,000 classes”， Sun, Yi, Xiaogang Wang, and Xiaoou Tang, CVPR 2014.

Github代码：

https://github.com/yl-1993/hfsoftmax