然而，由于各种原因，匹配目标和排名目标之间的这种分离 / 区分导致了较低的商业回报率。给定一个用户查询，我们必须使用复杂的模型，并花费大量的计算资源来对数百甚至数千个候选广告进行排名。也许最令人失望的是，排名模型反馈，许多相关的广告不是由高 CPM 提供的，也不会显示出来。
为了解决这个问题，百度启动了“Mobius”项目，目的是推动 构建 百度的赞助搜索引擎的下一代查询 – 广告匹配系统。这个项目希望能将不同的学习目标（包括查询广告相关性和许多其他业务指标）统一在一起，以降低响应延迟 、 计算资源的限制和对用户体验的微小负面影响。
Mobius-V1 作为下一代查询广告匹配系统的第一个版本， 集成了 上述解决方案 来应对挑战 ， 目前 已经在百度 的 赞助搜索引擎中部署 上线 。
百度赞助搜索的愿景
百度的赞助搜索曾经采用三层漏斗状结构，如图 3 所示。顶层匹配层（用 O Matching 表示）的优化目标是使所有查询广告对之间的平均相关得分最大化：
然而，根据对百度赞助搜索引擎表现的长期分析，我们发现匹配目标和排名目标之间的区别 / 分离往往导致更低的 CPM，这是商业搜索引擎的关键业务指标之一。当排名层中的模型报告匹配层提供的许多相关广告由于估计没有较高的 CPM 而不会显示在搜索结果上，这是 无法 令人满意的。
随着计算资源的快速增长，百度搜索广告团队（“凤巢”）最近成立了 Mobius 项目，旨在研发百度赞助搜索中的下一代查询广告匹配系统。如图 4 所示，本项目的蓝图期望将多个学习目标（包括查询广告相关性和许多其他业务指标）统一到百度赞助搜索的单个模块中，以降低响应延迟、有限的计算资源和对用户体验的微小不利影响为前提。
我们在 Mobius 的第一版，即 Mobius-V1，首次尝试教匹配层，除了查询和广告相关性之外，还将 CPM 作为一个额外的优化目标。这里我们将 Mobius-V1 的目标表述如下：
因此，如何准确预测 Mobius-V1 中数十亿对用户需求和广告候选项的 CTR 成为一个挑战。在本文的其余部分，我们将详细描述如何设计、实现和部署 Mobius-V1。
MOBIUS：下一代查询广告匹配系统
3.1 主动学习 CTR 模型
6 年多来，百度赞助的搜索引擎一直在使用深度神经网络（DNN）来构建 CTR 模型（规模巨大）。最近，Mobius-V1 采用了一种创新架构。构建 Mobius-V1 的一个直观而简单的方法是在排名层重用原始的 CTR 模型。这是 一种大规模稀疏的有利于记忆的深度神经网络（DNN）。然而，无论是用户查询还是尾部广告的 CTR 预测都存在严重偏差。
3.2 快速广告检索
在百度赞助的搜索引擎中，我们使用图 6 所示的深层神经网络（即用户查询 DNN 和广告 DNN）分别获取查询和广告的嵌入。给定一个查询嵌入，Mobius 必须从数十亿个广告候选中检索出最相关和最高的 CPM 广告，如等式（2）所述。当然，尽管暴力搜索理论上可以发现我们要寻找的所有广告（即 100% 广告召回率），但对每个查询进行穷尽计算是不现实的。在线服务往往具有有限的延迟约束，广告检索必须在短时间内完成。因此，我们利用近似最近邻（ANN）搜索技术来加快检索过程，如图 7 所示。
3.2.1 ANN 搜索
如图 6 所示，通过余弦相似度将用户向量和广告向量相结合，然后将余弦值通过 softmax 层生成最终的 CTR。这样，余弦值和 CTR 单调相关。学习模型后，就可以清楚地看出它们是正相关还是负相关。如果它是负相关的， 通过否定广告向量， 可以很容易地把它转换成正相关。这样，我们 就能 将 CTR 排序问题简化为余弦排序问题，这是一个典型的人工神经网络搜索设置。
近似最近邻（ANN）搜索的目标是，对于给定的查询对象，只需扫描语料库中的一小部分对象，就可以从大型语料库中检索出“最相似”的对象集。这是 一个从计算机科学发展早期开始就被积极研究的 基本问题。通常，用于 ANN 的流行算法基于空间划分的思想，包括基于树的方法、随机散列方法、基于量化的方法、随机划分树方法等等，我们发现随机树划分方法相当有效。在其他变体中，有一个已知的随机分区树方法的实现称为“烦恼”。
3.2.2 Maximum Inner Product Search （ MIPS ）
在上述解决方案中，在用户向量和广告向量匹配后，考虑与业务相关的权重信息。实际上，这个权重在广告排名中至关重要。为了在排序过程中考虑权重信息，我们通过加权余弦问题将快速排序过程形式化，如下所示：
其中 w 是业务相关权重，x 是用户查询嵌入，y 是广告向量。注意，加权余弦引起了内积搜索问题，通常称为最大内积搜索（MIPS）。在这一行中，多个框架可以应用于快速的内部产品搜索。
3.2.3 向量压缩
为数十亿个广告存储一个高维浮点特征向量需要大量的磁盘空间，如果这些特征需要存储在内存中以便快速排序，则会带来更多问题。一般的解决方案是将浮点特征向量压缩成随机二进制（或整数）哈希码或量化码。压缩过程可以在一定程度上降低检索召回率，但也可能带来显著的存储效益。
对于当前的实现，我们采用了一种基于量化的方法（如 K-Means）对索引向量进行聚类，而不是对索引中的所有广告向量进行排序。当一个查询到来时，我们首先找到查询向量分配到的集群，然后从索引中获取属于同一个集群的广告。乘积量子化（PQ）的思想更进一步，将向量分割成若干子向量，并将每一个子向量分别聚类。在 CTR 模型中，如第 3.1 节所述，我们将查询嵌入和 ad 嵌入分成三个子向量 ， 然后将每个向量分配给一个三元组的簇质心。例如，如果我们为每组子向量选择 103 个质心，则可以利用 109 个可能的簇质心，这对于 10 亿个尺度的多索引来说是足够的。在 Mobius-V1 中，我们使用了一种称为优化产品量化（Optimized Product quantification，OPQ）的变异算法。
实 验
4.1 离线评估
如表 1 所示，我们的模型可以保持与原始排名模型 差不多 的 AUC，但是显著提高相关性模型的得分（从 0.312 到 0.575）。换句话说，在 Mobius-V1 中，低相关性但高 CPM 的查询广告对被成功地识别为坏情况。
此外，我们将每种方法预测 出来 CTR 最高的 10 万个查询广告对交给百度众包团队，由人工专家对查询广告相关性从 0 到 4（0: 无关联，4: 相当相关）进行人工评分。主观意见报告也证明了 Mobius-V1 中的 CTR 模型在发现相关的查询广告对方面表现良好。
此外，我们使用相同的集合分别从两个广告索引系统中检索广告，这些索引系统分别由随机分区树（ANN Re-Rank）和 OPQ（Compressed Code MIPS）提供。表 2 显示，OPQ 使广告覆盖率提高了 33.2%。
4.2 在线 AB 测试
从平均响应时间和内存使用率两个角度对 Mobius-V1 采用的两种不同的广告检索策略进行了在线 A/B 测试。如 表 2 所示 ，与随机分区树方法相比，OPQ 可以提供更低的延迟，并将平均响应时间减少 48ms/ 查询。此外，我们还研究了具有更大商业价值但需要更多计算资源的 3% 高 CPM 广告的平均响应时间。结果表明，OPQ 将查询延迟缩短了 75%（从 120ms 缩短到 30ms），并大大节省了内存消耗。
4.3 部署上线
在 Mobius-V1 成功通过了线下评测和在线 A/B 测试后，我们决定 将其部署到 百度内外的多个平台上。这些平台包括手机上的百度应用程序、个人电脑上的百度搜索，以及我们赞助的搜索引擎服务的许多其他附属网站 / 应用程序。我们对整个在线流量 连续做了 7 天监测，表 3 显示了 CPM、CTR 和 ACP 的统计数据。其中， CPM 是评价一个赞助搜索引擎性能的主要指标。与之前的系统相比，Mobius-V1 使百度应用程序的 CPM 和百度搜索的 CPM 分别提高了 3.8% 和 3.5%，这是我们赞助搜索引擎的主要门户网站。
相关工作
5.1 查询广告匹配
5.2 CTR 预估
随着最近出现的深度学习，许多用于 CTR 预测的方法利用各种深度神经网络，通过从原始查询和文本广告中自动学习，主要缓解创建和维护手工制作的特征的问题。百度搜索广告（“凤巢”） 自 2013 年以来就 已经成功 应用超高维和超大规模深层神经网络来 训练 CTR 模型。
结论
本文通过回答以下四个问题，向大家介绍百度赞助搜索引擎下一代查询广告匹配系统 Mobius 项目：
动机 ： 为什么我们要提出 Mobius 项目？
我们过去采用三层漏斗形结构，从数十亿个候选广告中筛选和分类数百个广告进行展示。然而，匹配目标和排名目标之间的分离 / 区分会导致较低的商业回报。为了解决这个问题，我们建立了 Mobius-V1，这是我们首次尝试让匹配层考虑到业务影响度量（如 CPM），而不是简单地预测数十亿个查询广告对的 CTR。
挑战 ： 我们在构建 Mobius-V1 时遇到了哪些挑战？
解决方案 ： 我们如何设计和实施 Mobius 来应对这些挑战？
反馈 ： Mobius-V1 在百度赞助的搜索引擎中表现如何？
我们已经在百度赞助搜索引擎中部署了 Mobius-V1。线上和线下的实验结果表明，这种新的匹配系统将 CPM 提高了 3.8%，广告覆盖率提高了 33.2%。
未来工作
自 2013 年以来，百度搜索广告（又称凤巢） 就 成功部署了超大型深度神经网络来训练 CTR 模型。为了超越 CTR 模型，Mobius 被确立为一个创新和前瞻性的项目 ， 将优化用户体验和业务目标统一起来的想法也启发了 feed 等其他产品。
未来 还有 许多潜在的方向 可以探索 。例如，我们希望能够在匹配层引入更多的业务目标，如 ROI（投资回报率），作为额外的学习目标，以便发现更为友好的商业广告。此外，我们还为数十亿候选广告和查询提供更多优化目标，计算复杂度将显著增加。考虑到 对较低 响应延迟的要求和计算资源的限制，赞助搜索引擎的有效性和效率之间 需要进行 权衡。
Mobius 项目的关键步骤是通过近似近邻搜索（ANN）实现快速的广告检索任务。目前系统使用余弦相似性来近似 CTR，基于它们的单调相关性。如果最后一层比较复杂，按余弦（或加权余弦）排序会有问题。团队正在研究 用复杂的方法进行搜索，它可以被未来的 Mobius 版本采用。另一个很有前途的方向是采用基于 GPU 的快速神经网络系统，该系统已被证明对一般人工神经网络任务非常有效。
http://research.baidu.com/Public/uploads/5d12eca098d40.pdf
