电商搜索广告召回系统

plus2047 于 2022-12-31 发布

搜索广告问题综述

推荐或者搜索，广义上都可以视为信息检索 (Information Retrieval) 问题，可以抽象为给定一个查询指令 (Query), 从一个候选集（物品库）中返回一个候选列表，通常这个列表是有序的。在推荐问题中，Query 是用户信息和上下文信息，在搜索问题中，除了用户信息和上下文信息，还有用户的搜索文本 (Keyword). 搜索文本是搜索 Query 中最重要的部分，即使没有所有的其他信息，仅有文本，搜索引擎一般也可以工作的不错，比如没有登陆的网页搜索、电商搜索。在召回阶段，很多召回算法不借助用户信息，仅依靠搜索文本运行，也即非个性化的算法。

搜索问题的 Query 主要是搜索文本，个性化推荐的 Query 主要是用户信息，两者具有一些显著的差异。第一，搜索文本的结果相对而言是稳定的，可能除了有些商品失效、有些新商品加入之外，固定的搜索文本的搜索结果几乎不变。用户期望对于同样的搜索文本，得到同样的搜索结果。而个性化推荐每次请求都需要不同的结果，用户不希望看到同样的推荐结果。第二，搜索文本具有很强的头部效应，可能 TOP 100K 或者 TOP 1M 的热门 Query 就能覆盖 80% 以上的流量。但用户每天也总是会创造出新的 Query, 无论收集多少 Query 也不可能覆盖所有 Query. 换种说法，搜索问题只需要较少的热门 Query 就能覆盖大部分流量，但无论如何也不可能枚举全部 Query. 个性化推荐问题流量相对均衡，不能用少数用户覆盖大部分流量，但却可能枚举所有用户。

这两个差异，以及文本本身的特性，导致了对于搜索召回，倒排索引、离线计算、统计方法可以发挥较大的作用。

总体来看，搜索广告的召回阶段跟「广告」关系不是很大，跟搜索本身的召回问题相似。两者的差别有，

  1. 广告的物品库远比搜索要小，同时对平台营收贡献大，因此更可能使用一些代价较高的算法，比如离线全库打分，甚至在线全库打分
  2. 广告商品尽管物品库比较小，但相对于全体物品库，平均而言更为热门，因为商家既然肯为一个商品购买广告，这至少不是一个已经被遗忘的商品
  3. 广告物品具有相对较强的实时性，比如随时可能因为当天预算耗尽 (budget) 等原因失效，然后又因为日期刷新重新有效

广告物品库尽管变动更为频繁，但每天变动的商品仍然只占较小比例，算法层面上不需要太多特别的考虑。但工程上需要注意状态检查，不要把预算耗尽等无效的商品展示出去，造成 Over Delivery 问题。

接下来介绍几种常见的召回算法。

文本召回

最经典的召回算法当然是基于倒排表的文本召回。对商品的标题、Bidding Keyword 等等字段建立倒排索引，然后基于 Query 文本进行召回即可。

有成熟的工具可以进行倒排索引召回，包括 ElasticSearch, Vespa 等。这些工具也可以用于本文中的一些其他召回算法，比如 Vector Recall.

这里简单的介绍一下倒排索引技术。倒排索引技术是所有文本搜索的基础，按照惯例，倒排索引中的条目称为「文档」（对于电商场景，一条文档就是一个商品）。建立倒排索引时，只需要给出每个文档关联的文本内容，比如标题、关键字等等。线上 Serve 时，倒排索引工具能够根据搜索搜索关键字把含有这些关键字的文档检索出来。

文本召回不仅成熟简单，而且非常重要。

  1. 对于文本搜索场景，文本召回一般会在所有召回方法中贡献最多流量，毕竟搜索 Query 本身就是文本
  2. 文本召回可以通过向物品添加各种标签增强性能，并与 NLP 模型整合，比如命名实体识别 NER, 各类 Tag 提取模型，Query Rewrite 技术等
  3. 文本召回对长尾 Query 效果好，其他方法由于训练数据不足等原因，常常在长尾 Query 上效果不佳

Vector Recall

模型化召回最经典的工作就是双塔模型。这方面最经典的工作是微软的 DSSM. 尽管 DSSM 是个很老的工作了，但后续的模型与 DSSM 差异不大。

Vector Recall (or EBR, Embedding Based Retrieval) 的基本结构是，Item 侧特征（商品标题、类别等等）、Query 侧特征（Query 文本、预测的 Query 类别等等，以及可选的用户侧特征，用户侧特征在这里从属于广义的 Query 侧特征），分别通过 Item Embedding 模型和 Query Embedding 模型，得到 Query Embedding & Item Embedding,

\[\text{EMB}_{\text{Query}} = \text{Model}_{\text{Query}}(F_{\text{Query}}) \\ \text{EMB}_{\text{Item}} = \text{Model}_{\text{Item}}(F_{\text{Item}})\]

$F$ 代表特征。然后，定义两者之间的距离函数，

\[\text{Dist} = L(\text{EMB}_{\text{Query}}, \text{EMB}_{\text{Item}})\]

常见的距离定义包括 L2 欧几里得距离，$\cos$ 距离，dot product 等等。模型可以根据用户行为日志进行训练。最简单的做法就是用户有点击的 Query, Item pair 视为正样本（距离为 0）否则视为负样本（距离为 1）。可以引入负采样、Magin Loss 等深度学习模型训练时常用的技巧，与 pCTR 模型相似。

模型训练之后，Item Embedding 可以预计算并缓存。ElasticSearch, Vespa 等工具都支持向文档中加入 Embedding 字段。在线 Serve 时，只需要计算 Query Embedding, 然后使用这些工具进行 KNN (K Nearest Neighbors) 检索即可。算法层面，常见的 KNN 算法有 HNSW 等。这方面的工作很丰富。

召回问题的限制是，为了使用 KNN 算法，模型必须是双塔结构，也就是 Query 和 Item 分别通过一个深度模型生成 Embedding 向量，两个模型之间，除了最后的距离函数（也是损失函数）之外，不能有交互，否则无法使用 KNN 召回。因此，类似于 DIN 模型这类需要引入 Query 侧和 Item 侧交叉的模型就不能使用。Query 侧文本和 Item 侧文本也不能拼接之后通过同一个语言模型（如 BERT 模型），而只能分别通过两个独立的语言模型。

特征层面，在搜索场景中，最有效的特征当然是 Text Embedding, 包括商品 Title Embedding 和 Query Text Embeddding. 先进的预训练语言模型（如 BERT 家族模型）能够大大提升召回性能，并且只需 Fine-tune 即可食用。其他的常见特征包括，Item 侧：统计信息（如历史点击率、历史点击次数），Item 类别信息（人工整理或商家设置的精确类别），其他模型产出的 Item 侧特征。Query 侧：统计信息，如 Query 历史点击类别概率分布，其他模型产出的 Query 相关特征，比如命名实体识别等等。Query 由于无法穷举，其统计类特征一般无法保证高覆盖率，而且长尾部分特征质量差。

训练数据基于用户行为日志，正样本一般是用户产生了行为（点击）的 Query-Item 对，负样本则比较多样化，除了曝光但没有点击这一部分日志之外，还可以加入全局负采样或者 Batch 内负采样（Batch 内除正样本外均两两互相视为负样本）。对于 Recall 模型而言，模型需要从所有样本中召回负样本，因此负采样非常重要。也可以以某些策略够早一些 Hard Negative 负样本，比如正样本同 Category 下的 Item. Vector Recall 的损失函数、任务设计跟 pCTR 模型有相似之处，可以参照 Ranking 一节。

CF/i2i 召回

协同过滤 (CF) 是推荐系统领域的经典工作，现在也常常用于复杂推荐系统的召回步骤。比较常用的是 ItemCF, 由于 Item 相对固定，这类算法可以离线生成一个 Item 相似度表，然后对每个用户，召回用户最近点击 Item 的相似 Item. 这是一类简单、有效、可解释性好的算法。

这个 Item 表也称为 i2i (item to item) 表。除经典的 CF 算法之外，统计方法还有 Swing 算法等。基于模型的方法，则可以仿照 Vector Recall 的双塔模型，利用 Item Embedding 做 item to item KNN 召回，甚至可以直接使用现有的 Vector Recall Embedding. 如果训练 i2i 模型，训练数据可以根据用户同一个 Query 的点击序列给出。

在搜索场景中，由于 Query 的存在，i2i 表的应用不那么直观。介绍两种用法，其一是，可以根据已有的召回结果，取一些高质量的 item 作为 seed，如 pre-rank 靠前 item, 各个 queue 高分 item 等，进行 i2i 召回。其二是，与推荐系统一致，直接用用户行为做 seed.

关于 i2i 召回可以参照这几篇文章，

i2i 方法可以视为图算法的一种，在 User-Query-Item 图上引入了 Item 侧的一阶相似。类似的，Query Rewrite 可以视为 Query 侧的一阶相似。

在搜索场景中，可能是由于文本特征效果太强，除 i2i 之外的图算法，如 GCN, GraphSage 等，较难取得效果。这些图模型如果不引入文本特征，如 GCN, 与文本方法差距很大。如果引入文本特征，如 GraphSage, 则比文本方法提升不大。

离线预计算

搜索场景特有的一种暴力技术是离线预计算，也即离线的对于一部分热门 Query, 全库（也即全部有效商品）使用复杂模型打分，然后取 TOP. 最粗暴的策略是全库直接过 Ranking or Pre-rank 模型，然后取 TOP N 缓存。或者单独训练一个模型。

这种做法之所以能够成立，是因为，

  1. 搜索场景热门 Query 具有非常强的头部效应，可能 TOP 100K or TOP 1M Query 就能覆盖 50% - 80% 流量，这部分流量贡献的收入比例会更高
  2. 广告场景，物品库小

离线预计算的一种可行的做法是，

  1. 统计过去一段时间（比如一周）的热门 Query, 取 TOP K 热门 Query
    1. N 根据目标的流量覆盖比例、算力成本进行权衡
    2. 可以进行一些 Query Normalisation, 比如过滤特殊字符、大小写转换等等
  2. 对合法商品库做一个快照
  3. 全库商品过 Filter
    1. 比如状态检查、Relevance filter (如果有)
  4. 全库商品过打分模型，取 TOP N 缓存

有一些可以降低计算成本的策略，比如增量计算等等。

由于搜索的头部效应非常严重，离线预计算能够覆盖相当一部分流量。只要打分模型足够好，能取得较大提升。

打分模型的选取，可以直接复用 Ranking or Pre-rank 模型，甚至在这一步就引入 Bidding 进行 eCPM 排序。也可以专门训练 pCTR 模型。

值得一提，一般而言，在 recall 阶段使用的深度模型如 DSSM 通常是双塔模型，不能在 Query 侧和 Item 侧做特征交叉。但离线预计算时算力限制小，可以引入交叉。

用户行为统计召回

由于热门 Query 是相对稳定的（今天的热门 Query, 大概率昨天也已经有很大流量了），搜索场景还可以有一种很奇葩的召回算法：直接统计每个 Query 下高点击 Item, 召回 TOP N.

这一做法仔细稍加思考会发现似乎有问题：如果一个 Item 能够得到点击，则它已经被其他方法找回了，该方法就不该起作用。但实际系统中，该方法仍然能带来一些收益：第一，冷启动策略等会随机召回一些 item, 有些个性化召回策略对不同的用户召回的结果是不一致的，因此该方法仍然能收集到一些其他方法没有的物品。第二，该方法可以对 Query 进行 Normalisation 甚至进行聚类以提高性能。第三，对于电商搜索广告场景，统计用户点击时，可以把正常搜索结果（非广告结果）也包含在内，而广告库是在不断变化的，非广告商品也可能会由于用户充值变成广告商品。如果广告和非广告搜索用的是不同的召回系统，这种做法还可以从搜索系统中受益。

搜索广告召回流程

搜索广告在召回步骤中同时还要进行一些过滤、有效性检查等处理。一种可以接受的基本流程是，

  1. 多路召回的各个召回路 (Queue) 返回找回结果 —— 各 Queue 需要自行确保广告有效性，这是因为不同的 Queue 确认广告有效性的方法不同，比如倒排索引工具一般可以支持动态的删除（或者 Disable）一些 item, 从而保证召回的结果总是有效的，而离线预计算只能召回之后做状态检查
  2. Deduplicate 去重
  3. Relevance Filter. 后文我们将会介绍 Relevance 模型，该模型负责保证 Item 和 Query 文本具有基本的关联性
  4. Pre-rank 打分并取 TOP，将结果传递给 Rank 阶段

本文受限于篇幅和知识，很遗憾不能展开介绍给多细节。下文将会继续介绍 Rank 模型和 Relevance 模型。