type
Post
status
Published
date
Nov 16, 2022
slug
2022.11.16 再读 fb embedding-based 召回的老文章
summary
2022.11.16 再读 fb embedding-based 召回的老文章
tags
算法
召回
推荐
category
算天算地系列
icon
password
Embedding-based Retrieval in Facebook Search, 2020
文章里，Facebook 针对社交搜索场景的向量召回，介绍了从样本选择、特征工程、模型设计、离线评估、在线 Serving 的全流程，当然最有意思的部分还属“样本选择”部分，召回本来就是负样本的艺术，这篇文章讲的很接地气，类似 google 的很多文章，都让人感觉很踏实，大道至简，贴合业务，解决实际问题，不搞花里胡哨的东西。如今 2 年多过去，无意中从书架上看到，再读一遍此文，又有不一样的感受，在原来的理解基础上补充了近几年的一些想法。
1. 背景
不同于传统的网络搜索，社交网络上的检索问题不仅仅关注于 query 的文字信息，还要关注于上下文信息的相关性。虽然向量召回在其他的搜索引擎中有了广泛运用，FB 之前的搜索还是主要在使用布尔匹配。所以这篇文章讨论了 FB 向量召回的实践方案。
2. 模型训练
2.1 离线评估指标
模型返回的 top K 结果集合 ，目标结果集合：，基于某种准则，比如用户点击或者专家排序等。在这篇文章里，作者采样了 10000 个搜索结果，去收集 <query, target result> pair 对，然后取平均的 recall@K 作为结果。也就是拿Top K 召回结果与用户实际点击做交集，然后计算 precision/recall；
在其他公司的实践中，离线评估的指标各有不同，比如 Airbnb 所使用的方法是看“用户实际点击”在“召回结果”中的平均位置；
另外，召回要做离线评估是很难的，因为召回的结果未被用户点击，不能说明用户不喜欢，而可能是因为这个召回结果在 ranking 阶段被干掉了，根本没有给用户曝光过。
2.2 损失函数
本文用的是 triplet loss，给定 triplet ，其中 是 query， 和 分别是正和负样本，triplet loss ，其中距离函数 D = 1 - cosine相似度，而 cosine 相似度则用 query 和 doc 塔输出的 embedding 计算。 作为 margin value 用来决定 positive pair 和 negative pair 之间的距离，是一个可以调节的超参数，对效果有显著影响，文章中提到不同的参数会影响 5-10% KNN recall variance。
但是，我认为用 BPR loss = 可能效果更好，因为少了 m 这个超参数，而且在 hinge loss 中，当距离之差大于 m 后，这一个样本对 loss 的贡献就变成 0 了，而 BPR 则没有限制，两者距离越大越好。
2.3 模型结构
2.4 样本选择
- 本文用“点击正例”和“随机负例”已经达到了很好的效果。如果召回候选池大小是 N，每个正例采样 n 个负例，大致保证 K = N/n。
- “随机负例” (从负例池里随机采样) 的效果要远好于“展现未点击负例” (从 session 里展现未点击样本里随机采样)；
- 原因很简单，能展现的样本都是经过 ranking 筛选的，相对点击样本来说已经是 hard 样本了，而召回要面对的绝大多数都是 easy 样本。
- “点击正例”和“展现正例” (即有展现的 doc 都算正例)，在同样数据量的情况下，模型效果持平，“展现正例”并没有带来明显增益；
- Hard Negative Mining
- Online hard negative mining：一种 in-batch 的 hard 负例，即对每个正例的 query，都从同一个 batch 内其他正例的 doc 里按相似度降序采样 n 个，组成一个新的样本作为 hard 负例。文章里 n = 2 效果最好，过了效果就开始下降。
- Offline hard negative mining：
- (1) generate top K results for each query (用 ANN). (2) select hard negatives based on hard selection strategy. (3) retrain embedding model using the newly generated triplets. (4) the procedure can be iterative.
- hard selection strategy：最 hard 的样本反而不是最好的，本文发现 rank 在 101-500 的能获得最好的效果。
- 只用 hard 负例打不过“随机负例”，原因是 the "hard" model put more weights on non-text features but did worse in text match than the "easy" model.
- 混合 easy 负例和 hard 负例效果最好，本文实测最好比例 easy:hard=100:1
- 从 “hard” 模型向 “easy” 模型做 transfer learning 能提升效果，反过来不行。
- Hard Positive Mining
- 寻找没有被召回但依然是 positive 的样本，“To this aim, we mined potential target results for failed search sessions from searchers’ activity log“，文章里仅用这种 hard positive 都能与用“点击正例”获得相同 level 的结果，数据量仅有“点击正例”的 4%；
- 即使是“随机负例”这么简单的东西，其实也不简单，随机并不意味着是等概率随机，因为有高热 item 以及其他各种工程实现问题的存在，如果只是等概率随机，也容易导致效果不行，具体关于负样本的选择技巧，可以参考之前总结的这篇文章 2021.03.04 召回-负例的艺术(wip) 。
- “展现未点击” 样本似乎啥用也没有。
3. 特征工程
没啥可说的，比较常规。
- Text features. 非常有用，注意用法
- We compared models trained with character n-grams vs word n-grams and found the former can yield a better model.
- on top of character trigrams, including word n-gram representations additionally provides small but consistent model improvement
- Location features. 非常有用
- Social embedding features. 感觉一般
4. 线上服务
4.1 ANN（Approximate Nearest Neighbor）
本文比较了多种实现方法以及多种参数，并有几点发现：
树方法，如 KD-tree，Ball-tree，Annoy 哈希方法，如 Local Sensitive Hashing (LSH) 量化方法，如 Product Quantization (PQ) 近邻图方法，如 Hierarchical Navigable Small World (HNSW)
- Tune recall against number of scanned documents：聚类是不均匀的，因此不能只考虑聚类数，还要考虑被 scan 的 doc 数。
- Tune ANN parameters when there is non-trivial model change：ANN 的参数和模型有关，如果模型发生了重大的变更，比如增加了 hard 样本之类的，需要试着调下 ANN 的参数。
- Always try OPQ：OPQ 是个好东西。
- Choose pq_bytes to be d/4：对于 PQ 算法，经验上的参数选择，d 是向量维度。
- Tune nprobe, num_clusters, and pq_bytes online to understand the real perf impact：不要一直离线测，重要的还是在线测。
4.2 系统部署
- 在 location 和 term text 的索引基础上，增加了关于 nn 模型的信息。added a (nn <key> :radius <radius>) query operator which matches all documents whose <key> embedding is within the specified radius of the query embedding.
4.3 Query and Index Selection
query selection：为避免 over-triggering, huge capacity cost and junkiness increase，对于一些特定的 query，比如用户想搜索他们之前搜过或者点过的内容，如果 nn 召回不能带来有效的信息增益，那么就不会触发这一次的 nn 召回。
index selection：在建索引的时候，只选择了月活用户，近期事件，热门的事件，以及热门 group。大部分公司在构建索引的时候都会采取这样的策略，很多长时间不活跃的内容可以不构建索引，以减少存储消耗。
5. 召回后链路的优化
优化链路一致性问题，担心新召回路的 doc 不被现有的 ranking 认可，导致推不出去。本文给出的解决方案主要有下面两种：
- Embedding as ranking feature，尝试将 query 和 doc 的 embedding 之间的 cosine 相似度，Hadamard 积，甚至 embedding 本身传给下游的 ranking 模型进行学习，本文发现 cosine 相似度效果最好。
- Training data feedback loop，文章认为向量化召回的召回率高但是精度低 (就是容易召回一些不相关的 doc)，因此人工对向量化召回的结果进行标注，然后 re-train the relevance model，用于过滤掉那些不相关的召回结果。
6. 进一步的优化
6.1 hard 样本的挖掘
已经融合到 2.4 节样本选择里了，主要是 hard 负例的挖掘，比如 in-batch 负例，以及离线 hard 负例，即离线模拟召回过程，取排序在中段的样本作为 hard 负例。
6.2 Embedding Ensemble
- easy 样本让模型学习到整个召回候选空间的样本分布，因此召回率很高，但是精度不高 (即排在前面的可能不如后面的更好)；
- hard 样本可以帮助优化精度，在一个小候选集上能做到很好的 ranking，但是面对大规模的候选，召回率不行。
因此，本文提到了一种 multi-stage 的方式，具体做法有两种：
- bagging 方式，多个模型的结果进行加权求和的方式，Weighted Concatenation
- 线上召回时，为了能够使用 FAISS，必须将多个模型产出的 embedding 融合成一个向量。做法也非常简单，将权重乘在 user embedding 或 item embedding 一侧，然后将各个模型产出的 embedding concat 起来即可。这样能够保证拼接向量之间的 cosine 相似度，与各单独向量 cosine 之后的加权和，是成正比的；
- 本文发现，使用“曝光未点击”作为 hard negative 训练出来的 hard model，离线指标好，但是线上没有效果；
- 反而，利用 offline hard negative 训练出来的 hard model，与 easy model 融合后效果最好。
- boosting 方式，就是把召回分成了 easy 阶段和 hard 阶段，hard 阶段类似一个小粗排，文章提到使用“曝光未点击”作为 hard negative 训练出来的 hard model 没效果，用 offline hard negative 训练出来的 hard model 有效果。