AAAI 2018 | 如何高效进行大规模分类？港中文联合商汤提出新方法

选自arXiv

机器之心编译

参与：Panda

大规模分类技术对人脸识别等任务的实际应用有着切实的价值。中国香港中文大学和商汤科技近日公布的一篇 AAAI 2018 论文介绍了一种旨在高效解决大规模分类问题的方法。机器之心对该研究成果进行了编译介绍。

近些年来，在深度学习的发展和数据集的爆发式增长的推动下，人工智能领域已经见证了一波突破浪潮（Shakirov 2016）。伴随着这一趋势，涉及极大数量类别的大规模分类变成了一项重要的任务。这种任务常常出现在使用了工业级数据集的人脸识别（Sun, Wang, and Tang 2014）或语言建模（Chen, Grangier, and Auli 2015）等应用中。

大规模分类带来了很多新难题，其中最为突出的可能是训练的计算难度。具体而言，现在的分类器常常采用的是深度网络架构，其中通常包含一系列用于特征提取的变换层和一个将顶层特征表示与每种类别的响应连接起来的 softmax 层。这个 softmax 层的参数大小与类别的数量成正比。在训练这样一个分类器时，对于样本构成的每个 mini-batch，都会通过求特定于类别的权重和被提取的特征之间的点积来计算对所有相关类别的响应。当类别数量很大时，上面所描述的算法会面临两大显著难题：（1）参数大小可能超出内存容量，尤其是当该网络是在容量有限的 GPU 上训练时；（2）计算成本将急剧增长，甚至达到无法实现的程度。

解决这些难题的现有方法（Mnih and Teh 2012; Jean et al. 2015; Wu et al. 2016）大都源自自然语言处理，这往往需要处理大型词汇库。这些方法具有一个共同思想：基于之前从训练语料库收集到的统计信息来重点关注常见词。但是，我们往往难以将这些方法扩展到其它领域，因为这些方法需要一个关键条件才能工作，即不同类别的频率要高度不平衡。而人脸识别等应用却并不存在这种情况。

我们在探索这一问题时进行了一项实证研究（见第 3 节）。在这项研究中，我们观察到了两个重要结果：（1）在大多数情况下，一个类别的样本只会和少量其它类别产生混淆；（2）当使用了 softmax 损失时，对于每个样本而言，从这个小的类别子集反向传播回来的信号会主导其学习过程。这些观察结果表明，对于每个样本 mini-batch，在类别的一小部分上执行计算就足够了，同时可排除影响可以忽略不计的其它类别。受这一研究的启发，我们探索了一种用于解决大规模分类难题的新方法。我们的基本思想是开发一种可以识别少量活跃类别的方法，这些类别可以为每个样本 mini-batch 产生显著的信号。这种方法需要即准确又有效。更具体而言，它应该要能正确识别那些与给定样本真正相关的类别，但同时又不会造成过多的计算开销。要同时满足这两个需求可不简单。

我们实现这一目标的努力由两个阶段构成。首先，我们得到一个最优类别选择器（optimal class selector）。我们通过实验表明，通过使用活跃类别的最优选择，学习后的网络可以在每次迭代中仅使用选择出的类别的 1% 就达到同等水平的表现。但是，这种最优选择需要计算所有类别的响应，这个过程本身的成本就过于高昂。然后在第二个阶段，我们基于动态类别层次开发出了这种最优选择器的一种有效近似。这种动态类别层次能有效地得到类别之间的接近程度，我们可以将其用于近似地确定 mini-batch 的活跃类别，从而极大地降低成本。注意这里的类别层次是根据与单个类别相关的权重向量动态更新的。因此，活跃类别的选择同时考虑了样本特征和权重向量。这让我们的方法有别于之前提到的依赖于先验统计的方法。另外，我们观察到真正的活跃类别的平均数量往往会随着训练的进行而减少，我们由此开发出了一种自适应的分配方案，这能实现成本和表现之间的更好权衡。

在大规模基准 LFW（Huang et al. 2007）、IJB-A（Klare et al. 2015）、Megaface（Kemelmacher-Shlizerman et al. 2016）上的实验表明，我们的方法可以极大地降低训练时间和内存需求。

论文：通过动态类别选择加速用于大规模分类的训练（Accelerated Training for Massive Classification via Dynamic Class Selection）

链接：https://arxiv.org/abs/1801.01687

大规模分类是指在数量很大的类别（成百上千乃至数百万）上的分类任务，这已经变成了人脸识别等很多真实系统的一大关键部分。包括深度网络在内的在近些年取得了显著成功的现有方法基本上都是为类别数量适中的问题所设计的。当被应用大规模问题时，这些方法会遇到很多难题，比如过大的内存需求和计算成本。我们提出了一种解决这个问题的新方法。这个方法可以基于一组在工作过程中构建的动态类别层次而有效且准确地为每个 mini-batch 识别出少量「活跃类别（active class）」。我们还在此之上开发了一个自适应的分配方案，可以实现表现与成本之间的更好权衡。我们的方法在多种大规模基准上都能显著降低训练成本和内存需求，同时还能维持有竞争力的表现。

方法

我们的方法的基本思想是为每个样本 mini-batch 选择数量较少的活跃类别，然后根据它们计算一个选择性 softmax 和梯度。在这一节，我们首先会提供整个流程的一个概述，然后会继续详细讨论选择活跃类别的方法。具体来说，我们会从一个最优的但成本高昂的方案开始，然后基于动态类别层次开发一个有效的近似。此外，我们还会引入一个自适应分配方案，可以随着网络状态的改变而调整算法参数，这样可以实现表现与成本之间的更好平衡。最后，我们将给出我们的实现的有用细节。

选择性 softmax

选择性 softmax 相当于迫使非活跃类别的概率为零，同时重新归一化活跃类别的概率。如果活跃类别选择正确，那么这就会非常接近完全的 softmax，因为非活跃类别原本的概率实际上就接近于零。由此，所得到的梯度也会近似接近于原来的梯度。

活跃类别的最优选择

选择性 softmax 能提供完整 softmax 的优良近似，同时还能显著降低成本。但是，这种方法的有效性取决于我们是否能准确和有效地选择活跃类别。这也是我们研究中的关键难题。

近似的选择

我们提出使用哈希森林（HF：Hashing Forest）来近似最优的选择方案。这种方法的要点是通过递归式的分割来将权重向量空间分割为小单元。具体来说，一开始时整个空间只是一个单元，然后递归式地应用如下的随机分割。在每次迭代中，它会选择一个带有超过 B 个点的单元，然后在其中随机选择一对点，然后使用最大边界计算用于分割所选点的超平面。该超平面会将这个单元一分为二。这个过程会持续进行，直到任何单元内的点都不超过 B 个。注意，这种递归式分割流程本质上是构建该单元的二元树。算法 1 给出了构建该树的总体流程。

因为每个单元都是以随机的方式进行分割的，所以单个哈希树可能不足以可靠地得到类之间的接近程度。为了提升搜索的准确度，我们会构建 L 个哈希树，它们集中到一起会形成一个哈希森林。树的数量 L 可以根据成本和准确度之间的权衡通过实验的方式确定。

自适应分配

第 3 节中的实证研究表明：由于模型的判别能力越来越强，预测的概率和梯度都会随着训练的进行而变得更加集中。受此启发，我们提出了一种改进过的训练方案，该方案能自适应地调整会影响计算资源的使用的参数（比如在早期 epoch 中允许更多活跃类别），从而有助于实现表现与成本之间的更好平衡。

该方案控制了三个参数：（1）M，每次迭代中活跃类别的数量；（2）L，哈希树的数量；（3）结构更新的间隔 T。具体而言，我们会每隔 T 次迭代重建一次哈希森林，以保持更新。一般来说，在降低 T 的同时增大 M 和 L 可以提升表现，但会付出更高的计算成本。我们的策略是基于多种启发式方法定期调整 M、L 和 T。具体而言，我们会将整个训练过程分成几个阶段，我们会根据网络更新后的状态重置这些设计参数。

实现细节

为了说明清晰，上面所讨论的算法仅涉及一个实例。在实际过程中，我们会在每次迭代中使用多个实例构成的 mini-batch。用 X 表示从当前 mini-batch 提取出的一组特征 x，那么 S(X) 是 S(x) 的并集。另外，为每次迭代中所使用的活跃类别集合设置一个最大大小也通常会很方便。当 S(X) 的基数大于最大大小时，将会应用基于活跃类别的重新归一化概率的采样。

实验

方法比较

我们将我们提出的方法与多个基准进行了比较。下面简要介绍了这些方法。

（1）Softmax：完整版本的 softmax，在每次迭代中所有类别都是活跃类别。

（2）Random：一种朴素的方法，会在每次迭代中随机选择固定数量的类别来进行 softmax 计算。

（3）PCA：一种简单的哈希方法。它会将权重向量投射到一个低维空间，并会根据被投射向量的每个条目的极性将其编码成二值哈希码。对于来自类别 c 的样本，会选择具有相同哈希码的类别。

（4）KMeans：另一种用于寻找活跃类别的简单方法。它会根据对应的权重向量将所有类别聚类成 1024 组。对于来自类别 c 的样本，会选择包含 c 的组。

（5）Optimal：最优选择方案，它会完整计算 Wx 并选择具有最高响应的类别作为活跃类别。这能提供表现的上限，但成本非常高昂。

（6）HF：我们提出的方法的基本版本，它使用一个会定期更新的哈希森林来近似最优选择方案。

（7）HF-A：我们提出的方法的一个改进版本，使用了自适应分配方案来调节计算资源的使用，以便实现更好的平衡。

结果

我们在 MSCeleb-1M 上使用不同的方法训练了网络，并在 Megaface & Facescrub 上对它们进行了测试。表 1 给出了不同方法的一些数值结果。图 2 在成本基础上比较了它们的表现。这里的表现是用 top-1 识别准确度衡量的，成本则包括类别选择与计算受限的 softmax 和梯度的时间。

表 1：IJB-A 列中的量是当 FPR 为 0.001 时的 TPR，在 Megaface 识别任务中的是 top-1 准确度

图 2：不同方法的人脸识别准确度与对应的计算成本。当点在左上角时表示使用低成本实现了优良的表现。注意 x 轴是对数标度

结果表明：

（1）对于随机采样，当活跃类别数量增大时，表现会缓慢增长。这说明随机采样对于选择活跃类别而言并不是一种有效的方法。

（2）K 均值和 PCA 等基于聚类的方法表现并不很好，这说明只使用权重向量的聚类而忽视样本特征 x 不足以得到优良的表现。

（3）最优选择方法的表现非常好，甚至还略微超过了完全 softmax 方法。但这种方法在类别选择方面开销严重，因为它需要计算所有类别的响应。

（4）我们的方法（HF）明显显著优于其它方法。在同等的成本基础上，它可以得到显著更好的表现。另一方面，为了达到相同的表现，它所需的成本会低得多（有时候低差不多一个数量级）。

（5）HF-A 在基础版本之上还有明显的提升，这清楚地表明了自适应分配策略的优势。值得注意的是，它只需完全 softmax 方法 10% 的成本就能超越其表现。这是一个出色的改进。

（6）噪声对比估计（NCE）和 Hierarchical Softmax（HSM) 的结果远不如经典方法。这样的结果说明这两种方法也许并不适合大规模分类问题。

图 3 给出了相对于近似精度的表现，即所选择的类别和最优选择之间的平均重叠量。我们可以看到更好的近似通常会有更好的表现。由我们提出的 HF 方法所选择的类别非常接近最优子集（比其它方法精确很多），由此能得到显著更优的表现。

图 3：不同方法的人脸识别准确度与近似精度。注意 x 轴是对数标度

大规模实验

我们还使用 ResNet-101 进行了一次大规模实验，其中训练集是 MS-Celeb-1M 和 Megaface (MF2) 的并集，总共包含 75 万个类别。训练是在一台带有 8 个英伟达 Titan X GPU 的服务器上完成的。在这项实验中，HF-A 可以将每次迭代的训练时间从 3.5s 降低至 1.5s，也即提速 60%。注意这是指整个网络的总体速度（而不只是 softmax 层）。另外，每个 GPU 的总体内存消耗也从 10.8G 降低至了 8.2G。这得益于 softmax 层对 GPU 内存的需求的极大减少，如表 2 所示。研究还表明我们的方法可以实现与完全 softmax 相媲美的表现，同时每次迭代仅需选择 1% 的类别。这个结果说明我们的方法可以很好地延展到大规模分类问题上。

表 2：大规模实验中的表现与成本

图 4：Random、Optimal 和 HF 在不同数据集上使用不同的活跃类别数量 M 时所应对的表现

图 5：不同的哈希树数量 L 所应对的表现

图 6：不同的结构更新间隔 T 所应对的表现

本文为机器之心编译，转载请联系本公众号获得授权。