关于极限分类，这里有你想知道的一切

雷锋网 AI 科技评论按，在一个搜索已经无处不在的世界里，我们大多数人都有过对搜索结果不满意的体验。如果你的初始查询不返回你想要的结果，你会怎么办？当然，你可以浏览当前的前 1 亿个查询的列表，假设你只需要一秒钟就可以阅读一个查询，这一过程将花费你三年的时间。

说真的，谁有这么多时间来帮我收集数据？

幸运的是，微软的一个团队决定在这些非常真实和具有挑战性的问题上进行创新性的尝试。事实上，他们的解决方案在墨尔本举行的第 12 届 ACM 网络搜索和数据挖掘国际会议（WSDM 2019）上引起了轩然大波，该解决方案表明上述任务可以在数毫秒内完成。雷锋网 AI 科技评论将他们的博文编译整理如下。

微软印度研究院（Microsoft Research India）首席研究员 Manik Varma 解释说：「多标签分类是一门构建算法的科学，它可以回答涉及不确定性的多项选择问题，而这些问题可能有多个正确的答案。」Varma 把这个问题比作从一家餐馆的菜单中点一顿家庭餐，你需要确定在给定的预算内，选择菜单中的哪些菜最令人满意。与传统的多分类相比，这可能是一个更难解决的问题，因为在传统的多分类中，人们只需要从菜单中选择一道菜。因此，尽管进行了几十年的研究，计算机科学家只能解决涉及少量选择的问题，将搜索引擎上的查询建议作为一项多标签分类任务来考虑甚至是一个没有希望实现的课题。

「5 年前，多标签算法几乎无法扩展到涉及 5000 个选择的问题，」谈到极限分类，Himanshu Jain 回忆道，他是前面提到的那篇 WSDM 论文的合著者，也是印度理工学院 Varma 的博士生，曾在微软实习。2013 年，Varma 的团队发表了一篇论文，将可以考虑的选择数量爆炸性地从 5000 提升到 1000 万。这改变了游戏的本质，并促使了机器学习中一个新的研究领域——极限分类的出现。极限分类处理涉及大量选择的多分类和多标签问题。从那时起，极限分类为排名和推荐应用程序开创了一个新的样式，例如搜索引擎会推荐相关的查询。

Varma 解释说：「当选择从一千个变为一百万个时，好答案的标准就发生了变化。不幸的是，世界上没有一个人类专家能够通过一个 1000 万个选项的列表来找出所有正确的答案。」事实上，许多新的研究问题都出现在这种规模上，而机器学习界并没有传统地看待这一问题，每个问题只有部分答案以极限的规模存在，因此即使是最基本的机器学习技术（如交叉验证）也有可能出错。这些新的研究问题，加上高影响力的排名和推荐应用，使极限分类成为学术界和工业界的热门研究方向。在过去的六年里，极限分类的研究取得了显著的进步。Varma 观察到，关于极限分类的论文已在各种会议上发表，包括 AAAI, AISTATS, ICML, IJCAI, KDD, NIPS, SIGIR, WSDM, WWW 等，基准任务的预测精度从 2013 年的 19% 提高到今天的 65%。

遗憾的是，极限分类的技术挑战不仅在于提高预测精度，还需要减少训练时间、预测时间和模型大小。训练分类器所需的时间是极限分类中最大的问题之一。Varma 解释说，2013 年，他们在和维基百科大小差不多的数据集上，对他们基于树的极限分类器 MLRF 在 1000 个核心集群上进行训练，花了 7 个小时，这种速度在 Bing 的规模上简直是不可接受的，因此必须开发一种新的算法。

他们决定称这种算法为 Slice。

算法的工作原理

Slice 代表可扩展的线性极限分类器，它可以比 MLRF 快一万倍以上。该算法能够准确有效地扩展到涉及 1 亿个标签和 2.4 亿个训练点的问题，为世界上所有其他分类器的扩展能力打开了一个新的大门。Slice 为每个标签学习一个线性分类器，但在标签数量上减少了从线性到对数的训练和预测成本。只有少数标签（比如对数标签）在任何给定的特征空间区域中都是活动的，它的实现正是利用了这一点。在给定测试点的情况下，基于近似最近邻搜索，快速确定所属特征空间的区域。然后，它只评估该区域中活动标签的分类器，这一过程会产生对数预测成本。在训练过程中，如果 D 维中有 N 个带 L 标签的点，slice 通过只训练最难的负示例（时间复杂度 O（（n log l）/L））而不是所有（时间复杂度 O（n））负样本，将训练成本从 O(NDL) 降低到 O(ND log L)。这是通过一种新的基于近似识别线性分类器生成模型的负采样技术实现的。这项技术对于低维深度学习尤其有效，因为它可以有效地从数亿个点上对几百个最难的样本进行分类，而不会损失精度。雷锋网(公众号：雷锋网)

这复杂吗？

复杂。

值得吗？

值得。

极限分类为排名和推荐问题创建了一个新的范例。通过将每个项目作为单独的标签进行排名或推荐，我们可以学习一个极限分类器，它以用户的特征向量为输入，预测相关标签的子集作为输出，然后根据应用程序将与预测标签相对应的项目作为推荐包或排名列表返回给用户。在某些情况下，这种方法的结果相比传统的方法会有很大的改善。

在 Bing 搜索引擎上再次执行上述推荐相关查询的任务。你可以将 Bing 上的前 1 亿个查询都视为单独的标签，以用户查询为输入，并预测 1 亿个标签（查询）的相关子集作为输出，这是对你的查询问题的一种极限分类重新表述。

通过这种方式处理问题，Bing 可以提出更相关的建议，并将查询的成功率提高 12%，从而使数百万用户能够更高效地找到想要的答案。

「我第一次听到 Manik 关于极限分类的演讲是在几年前，当时，我花了一段时间才明白他想做什么。这是一种全新的看待多标签分类的方法，其效率以及模型大小是该方法不可能奏效的原因之一。多年来，Manik 和他的合作者已经取得了巨大的进步，他们为机器学习开创了一个子领域。顶级的 ML 会议现在有关于极限分类的专题研讨。我认为这项研究将继续对科学界产生影响。这是一个很好的例子，它展示了持续的研究如何使不可能的事情成为可能。」——微软印度研究院总经理 Sriram Rajamani。

除了搜索和信息检索，极限分类还可以应用于计算广告、推荐系统、计算机视觉甚至自然语言处理。例如，你可以使用极限分类来预测下一个将在 Bing 上键入的单词是什么。或者，你可以用它来识别你在会议上遇到的陌生人。或者，你甚至可以用它来推荐下一个你应该听的音乐曲目。当然，世界上数百万人已经受益于极限分类法，通过 Bing 广告系统，他们能更有效地找到和购买他们正在寻找的商品和服务。

极限分类目前应用非常广泛。它开启了研究的新前景，并回避了问题：还有什么其他的问题可以被重新定义为极限分类问题，我们现在有更好的解决办法吗？

via：https://www.microsoft.com/en-us/research/blog/everything-you-always-wanted-to-know-about-extreme-classification-but-were-afraid-to-ask/

雷锋网版权文章，未经授权禁止转载。详情见。